Displaying possible moves in a tilemap given a maximum movement and tiles with navigation properties

Biscottino

Hello, I am new to the Godot engine and having trouble understanding how best use the tilemap node to implement a navigation mechanic.

My idea is to make a turn-based tactics style game on a grid and I have managed to make a sprite move over the tilemap avoiding obstacles. I do this by using the A-star class and passing in the id of some tiles go get a movement path. However, I have two problems with this: 1. Given an amount of maximum tiles to move, how can I display what possible moves the sprite can make? One way I thought of doing this is by taking the path the tiles in the "maximum movement circumference" around the sprite and as the destination for A-star and then cutting the given paths to length of less that maximum movement. This sounds workable but is extremely processing heavy and prefer to avoid it. The A-star documentation gives an estimate cost function that could be used to make a mask but that method is hidden. Is there another way to access it? 2. Right now I am treating the tiles that are not obstacles the same but I would like to give them different weights depending on the tile they are. For example, it should be more difficult to move over snow than over grass. I have seen the A-star documentation show a get method for the weight at a node in the map but no way to set that weight. Is there a way to do this?

Megalomaniak

This discussion was caught in the moderation queue since you have not confirmed your account yet.

Upon creating your account you should have received an account verification email. The confirmation email may have been incorrectly flagged as spam, so please also check your spam filter. Without confirming your account, future posts may also be caught in the moderation queue. You can resend a confirmation email when you log into your account if you cannot find the first verification email.

If you need any help, please let us know! You can find ways to contact forum staff on the Contact page. Thanks! :smile:

Biscottino

I have already confirmed using with the email. Do I need to repost the question or merely wait?

Megalomaniak

The topic was already manually approved when I posted the above notice.

llasram

The default AStar#_estimate_cost() method is just the Euclidean distance (Vector2#distance_to()) between the positions associated with the provided points. Its purpose is to allow sub-classes to override the estimation function used by the A* algorithm with something more problem-specific; for example, if doing grid-based movement with no diagonals you'd want "Manhattan distance" instead (sum of strictly vertical and horizontal distance).

The algorithm I believe you want here is mostly just a breadth-first search, though if you squint at it you could call it a variation of Dijkstra's algorithm. Here's a sketch of how you could do it in GDScript:

Create three collections (e.g. Dictionary) mapping starting starting points to movement costs: one of "reachable points," initially empty; one of "fringe points," initialized to map the starting point to cost 0; and one of "next fringe points," initially empty. Then repeatedly iterate over the fringe collection, doing:

If the point is already in in the reachable collection with equal or lower cost, stop processing this point.
Add the point to the reachable collection, with the associated cost.
Find each neighbor of the fringe point and the total cost to get there via current fringe point. Drop any point above the cost cutoff or already in the reachable collection with equal or lower cost. Otherwise, add the point to the "next fringe" collection, keeping the lower cost if already present.

Then "next fringe" becomes "fringe," set "next fringe" to be a new empty collection, and repeat until the fringe is empty. Then the "reachable" collection will contain all the reachable points.

This algorithm doesn't require the priority queue you need for Dijkstra's algorithm, and so is less theoretically efficient, but should be totally fine for searching on an actual grid.

HTH!

Biscottino

Thank you very much for your answer, @llasram. However, I feel that having the A-star navigation class (which is an extension of Djistra's algorithm depending on who you ask) already does this internally so I was wondering if there is a way of accessing that representation instead remaking that work. I am not trying to undervalue your answer because it does answer my question but I also want to leverage existing methods on the library.

llasram

@Biscottino I totally understand wanting to leverage existing engine facilities, especially since GDScript does not seem intended for computationally expensive game logic. But in this case I think the functionality just isn't there. Even though there is a deep relationship between A* search and Dijkstra's algorithm, there's a big implementation switch from finding a single shortest path between a specific source and destination node to finding the shortest path tree (up to some maximum path cost) of destinations reachable from a specific source.

In particular, the a_star.cpp implementation doesn't even have a notion of maximum allowed path cost -- it will search until it finds a path or exhausts the graph. Even if it did expose a way to get back out the g_score values after a search, the code would need to re-explore the entire grid every time you ran it!

Rutoga

This is also something that bothers me , I still plan to improve DFS with Weight table Do you have any good solutions now？

TwistedTwigleg

If you are using the Mono version of Godot, you may be able to leverage an existing C# A search library for use in Godot. I have not tried it myself, but I'd guess that it would mostly be just converting the data to what the A library uses, running it, and then converting it back to Godot. You could probably also use GDNative for this with a C++ A* search library as well, though it would require a bit more setup for compiling, binding, etc.