2
\$\begingroup\$

Given the amount of steps you can take in a grid, how could I implement a way to get all the possible places a unit can go to, in a game like Advanced Wars?

I have currently got A* path finding working, but it would be nice to have an indicator of the possible places to go to. I have linked to an image to make things more clear.

I was thinking of computing the path of every single tile on the grid to the unit tile, then working it out from there, but I can imagine that will take crazy amounts of resources.

Notice how the other units 'block' the path of the selected unit. So unfortunately its not a trivial 'draw a circle with radius X'

Notice how the other units 'block' the path of the selected unit. So unfortunately its not a trivial 'draw a circle with radius X'

Improve this question
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Try djikstra (a* without the heuristic) or a breadth first search with node that dies after x iteration (distance with djikstra path length with BFS) then store the final tree created for query when the player select a character to move at a tile within the tree zone. \$\endgroup\$
    – user29244
    Jan 16, 2015 at 5:17
  • \$\begingroup\$ Also see here gamedev.stackexchange.com/questions/61928/… or here rpgmaker.net/tutorials/527 For an explanation \$\endgroup\$
    – user29244
    Jan 16, 2015 at 5:22
  • \$\begingroup\$ Why dont you use BFS? It is one of the most basic algorithms and all you need is stack and bool flags. Also, it would be more efficient than other suggested algorithms (simply because you dont compute what you dont need). \$\endgroup\$
    – wondra
    Jan 16, 2015 at 15:42

2 Answers 2

Reset to default
4
\$\begingroup\$

Breadth First Search can calculate every location reachable from a start position, and it can also count how many steps to that location. (If some steps take more "moves" then use Dijkstra's Algorithm instead). See the fourth demo on this page. You would tell the algorithm to stop after some number of moves, so that it doesn't keep exploring the rest of the map. In this image I stopped it after 5 steps:

Breadth first search limited to distance 5

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Love your tutorials, thank you for them. My Dijkstra's/BFS alike solution here - gamedev.stackexchange.com/a/195239/93428 . At first I thought that Dijkstra's needs a priority queue, so Dijkstra's is basically BFS but with weighted nodes, am I correct? \$\endgroup\$
    – Candid Moon _Max_
    Aug 15, 2021 at 2:08
  • 1
    \$\begingroup\$ Yes, Dijkstra's is BFS is weighted nodes. The two main changes are the use of a priority queue, and the possibility that you visit a node a second time with a lower cost, so you need to put that node back into the priority queue. With BFS the first time you visit a node it's the best path so you never need to put it back into the queue a second time. \$\endgroup\$
    – amitp
    Aug 15, 2021 at 15:19
-1
\$\begingroup\$

You just need to modify your A* implementation to exit when there are no acceptable tiles left and save all tiles meeting the condition.

Start as usual and set a MaxCost value (that is max distance unit can walk). Then iterate possible tiles to go and add ones that are passable and whose cost is less than or equal than MaxCost to a list. Algorithm ends when there are no neighbor tiles left with walk cost less or equal to MaxCost.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .