Function A* (Start, Target)

Var closed := empty set

var q := make_queue(path(start))

When q is not empty

var p := remove_first(q)

The last node of var x: = p.

If x is closed

continue

If x = target

Return p

Add x to closed

Every y(x) in the successor.

Queue (q, p, y)

The ability of returning failure A* to change its behavior is based on heuristic cost function, which is very useful in the game. The compromise between speed and accuracy will make your game run faster. In many games, you don't really need to get the best path, just approximate it. What you need depends on what happens in the game or how fast the machine running the game is. Suppose your game has two kinds of terrain, plain terrain and mountain terrain, and the moving cost in plain terrain is 1, while the moving cost in mountain terrain is 3, then the A-star algorithm will think that the distance on flat terrain can be three times that of mountain terrain for equivalent search. This is because there may be a path from the plain to the mountain. Setting the evaluation distance between two adjacent points to 1.5 can speed up the search process of A*. Then A* will compare 3 with 1.5, which is no worse than comparing 3 with 1. However, sometimes it may be better to move on the mountain than to go around at the foot of the mountain. So it is not always reliable to spend more time looking for an algorithm to bypass the mountains. Similarly, to achieve this goal, you can improve the speed of A-star algorithm by reducing the search behavior at the foot of the mountain. This weakness can adjust the mountain action cost of A-star algorithm from 3 to 2. Both methods will give reliable action strategies.