I know very little about game development and I'm trying to wrap my head around pathfinding algorithms.

Consider this setup: an agent is on a 2D map and must find the shortest path to a globally know object but only has information about obstacles in his local vision scope (ie. only immediate obstacles are known, the general layout of the map is unknown).

Also, every move to an adjacent square is expensive and the pathfinding algorithm should minimize the number of moves.

Computational efficiency is also of utmost importance and more important than accuracy.

Is A* appropriate for this use-case?


2 Answers 2


You should use the D* algorithm, which is designed for this exact scenario. Specifically, the D* Lite implementation is the most efficient and simple variant.

  • 2
    \$\begingroup\$ Highly relevant. Understanding D*-lite is simple once you understand LPA* (the algorithm D*-lite is based on), but LPA* itself is fairly complex. So, if you plan on actually implementing D*-lite, the paper on LPA* would be the place to start (assuming you already understand A*, that is) \$\endgroup\$ Commented Apr 25, 2013 at 16:31

Many game AI implementations in that situation will choose to cheat, and give themselves full knowledge of the map, where their human opponent doesn't have that. You can then simply apply A* to the full map.

How sensible this looks for computer controlled units will depend on things like how maze like the maps are, and if the player is likely to learn the map layouts over time.

If this is for player controlled units you can also prevent the player selecting a destination which they've not explored yet, to force them to explore manually.

  • 2
    \$\begingroup\$ Good suggestions, not appropriate for my use case, but could be useful to others. (I'm developing an AI to compete in a game simulation) \$\endgroup\$ Commented Apr 25, 2013 at 0:58
  • 1
    \$\begingroup\$ there are also games that uses path finding implementation assumes that unexplored areas are crossable, while areas previously visited had not had any change in crossability since last visit (i.e. it would not know that a wall may have been destroyed or build until it visits the area again). \$\endgroup\$
    – Lie Ryan
    Commented Apr 25, 2013 at 9:49

You must log in to answer this question.

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