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'

\$\endgroup\$
  • 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 '15 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 '15 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 '15 at 15:42
3
\$\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\$
-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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.