A * search

This algorithm is the best known as the Best First search algorithm and is also widely used in games for pathfinding. Its performance is very efficient and expanding paths that are already expensive are avoided through this algorithm.

f(n) = g(n) + h(n), where g(n) the cost (so far) to reach the destination node, h(n) is the estimated cost to get from the node to the goal, and f(n) is the estimated total cost of the path through n to the goal. It is implemented using a priority queue by increasing f(n).

Read more at: https://en.wikipedia.org/wiki/A*_search_algorithm

Get Learning Android Game Development now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.