Creating the nodes for path finding during run time - more like path making and more

Question

I'm making my 1st game. I'm using javascript as I currently want to learn to make games without needing to learn another language but this is more of a general game dev question.

It's a 2d turn-based tile/grid game. You can check it here http://www.patinterotest.tk/ it creates a movable area when you hover a player and it implements the A* algorithm for moving the player.

The Problem: I want to make the 'dynamic movable area creation' already implement a limited number of steps for a player.

The Questions:

• What is a good way to do this?

• Is there another algorithm to use for this?

• The A* algorithm needs a start and destination, with what I want to do I don't have a destination

• Or should I just limit the iteration of the A* algorithm to the steps variable?

Answer 1

Since your game is a 2D tile-based game, I assume you're modelling each tile as a node, and the map is essentially a grid of nodes.

In this case, there is no weight on any edge of the graph, so I don't see why you're using A* which was designed for finding minimum distances on weighted graphs. You should be using plain breadth first search

• The number of iterations you do with BFS is the max number of steps your character can take
• The path to any node can be extracted by keeping a predecessor list. Any path extracted this way is the shortest path because the graph is unweighted.
• The set of reachable nodes is basically any node BFS traverses; which you can use to generate your "dynamic movable area".

It will run the fastest because you don't need to do any distance considerations or heuristic calculations in the case of A* or Dijkstra (which is basically A* without using heuristics or H(x) = 0).

A*/Dijkstra is overkill unless you got a weighted graph.

Answer 2

Sounds more like a you'd want a breadth first search, instead of a depth first like A*, a common one is Dijkstra's algorithm. It is typically used for path finding, but you don't need to have a goal in mind. You can almost use it as is, except you want to limit the depth to the number of moves the player has.

A gif from the wikipedia page shows how this fits your situation:

Answer 3

Just execute A* each and every step.

If this is too slow, think about optimising it. Then there are several approaches, for example jump-point-search makes the A* itself faster. You can also try and work out the circumstances when you need to recompute the path, and only doing so then.