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.

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.

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.
• That 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.

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.