16
\$\begingroup\$

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?

| improve this question | |
\$\endgroup\$
19
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 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\$ – BlueRaja - Danny Pflughoeft Apr 25 '13 at 16:31
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 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\$ – David Chouinard Apr 25 '13 at 0:58
  • \$\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 Apr 25 '13 at 9:49

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.