Survey regarding which AI 2d pathfinding and what method is easy to use

Started by
11 comments, last by Luqman Ibrahim 6 years, 4 months ago

A* is Dijkstra augmented with an admissible heuristic (i.e., a function that gives you a reasonable lower bound on the distance from an intermediate node to the goal). There might be situations where you don't have one, and then you are back to using something like plain Dijkstra. This probably only applies to very abstract cases, like finding a sequence of gem exchanges that reaches a desired configuration in the board game Bazaar.

Also, Dijkstra can be used to compute the distance from a node to all other nodes. This might be useful if you have a lot of agents trying to reach the same goal (e.g., Desktop Tower Defense).

 

Advertisement
12 hours ago, Luqman Ibrahim said:

But why some people still using Dijkstra? Just want to understand more

A* is an implementation of Dijkstra's shortest path algorithm.  It is an optimization based on having additional information that prioritizes the most likely work before the less likely work.  

Dijkstra's version finds the shortest path between nodes on ANY directed graph with non-negative weights. While game maps can be interpreted as a connectivity graph making a dense grid, they are only a single type of graph. The graph could be any thing at all that uses a directed graph. Not just maps and roads, but ANY data. All the web links on a site, dependencies between systems such as software modules or food chains, trees ranging from data storage trees to infectious disease trees or spelling dictionary trees, flow trees that can optimize finite state machines or data processing patterns or flow control. They can remove loops of logic during code compilation.  The general algorithm finds connectivity on ANY of these directed graphs.

Processing the shortest path on a map is a big issue in games, but in math and data processing such maps represents only the tiniest sliver of all problems.  It is only for that minuscule percent of problems where the A* optimizations can be used.  In the vast majority of graph searches the optimization cannot be used.

 

Allright, thank you guys! I think I understand why there are different path finding being used in certain games. Thank you for your patience in answering and spending your time, really appreciate it. :) 

This topic is closed to new replies.

Advertisement