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

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?

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.

• "In this case, there is no weight on any edge of the graph" Well I'm not sure what you are meaning because for me the weight exists and equals, say 1.0. "The number of iterations you do with BFS is the max number of steps your character can take" <- This is not really true as you need to calculate the 'predecessor list' and That costs O(n²) (square of the distance) and you must calculate that if the world changes (and precalculate a big world might be memory costly). – Valmond Mar 21 '12 at 10:08
• Sorry for the misleading phrase, I was referring to actual loop you would have in code. The complexity of BFS is O(V+E) nonetheless. Also, If every edge of a graph has equal weight, then it's considered unweighted graph. If an edge has 0 weight, then the 2 nodes it connects can be modeled as a single node. Finally, the predecessor list can be implemented within the BFS loop and will requires same # of operations as BFS, complexity-wise still O(V+E); look at link to back to Dijkstra algo on that page. – XiaoChuan Yu Mar 21 '12 at 17:51
• The set of reachable nodes is basically any node BFS traverses; which you can use to generate your "dynamic movable area". <-- this line made me understand why plain bfs would be enough, thank you – bigbadbabybear Mar 21 '12 at 21:43

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. 