Moving a simple object seems easy. And path searching is complicated. Why does it bother when it comes to path searching? Consider the following:

The object (Unit) is initially at the bottom of the map and tries to move to the top. There is nothing in the area the object scans (in pink) to show that it cannot move up, so it keeps moving up. Near the top, it detects an obstacle and changes direction. Then it follows the U-shaped obstacle to its red path. In contrast, a Pathfinder will scan a larger area (the light blue part), but it will find a shorter path (the blue path) without letting the unit go to the concave obstacle.

However, you can extend a motion algorithm to deal with the obstacles shown above. Either avoid creating concave obstacles, or mark concave exits as dangerous (enter only if the destination is inside):

Rather than waiting until the last minute to find a problem, pathfinder lets you plan ahead. Movement without path search can work in many situations and can be extended to many more, but path search is a more common way to solve more problems.

Dijkstra accesses nodes in the graph, starting at the initial point where the object is located. It iteratively checks the nodes in the node set to be checked and adds the nearest unchecked node to the node set to be checked. The set of nodes expands outward from the initial node until it reaches the target node. Dijkstra’s algorithm is guaranteed to find a shortest path from the initial point to the target point, as long as all the edges have a non-negative substitution value. (I say “shortest path” because there are often many similarly short paths.) In the figure below, the pink nodes are the initial nodes, the blue ones are the target points, and the colored, diamond-like teal areas are the areas scanned by Dijkstra. The lightest areas are those farthest from the initial point, and thus form the frontier of exploration:

The best-first search (BFS) algorithm follows a similar process, except that it is able to estimate (called heuristic) the cost of getting any node to the target point. Instead of choosing the node closest to the original node, it chooses the node closest to the target. BFS does not guarantee finding a shortest path. However, it is much faster than Dijkstra because it uses a heuristic function to quickly navigate to the target node. For example, if the target is south of the starting point, BFS will tend to follow a southerly path. In the figure below, the yellower nodes represent the higher heuristic value (high cost to move to the target), while the darker nodes represent the lower heuristic value (low cost to move to the target). This shows that BFS runs faster than Dijkstra.

However, both of these examples are just the simplest cases — there are no obstacles on the map and the shortest path is straight. Now consider the concave obstacle described earlier. Dijkstra is slower, but it does guarantee a shortest path:

BFS, on the other hand, runs faster, but the path it finds is obviously not a good one:

The problem is that BFS is based on a greedy strategy, it tries to move towards the target even though it’s not the right path. Since it considers only the cost of reaching its goal and ignores the costs already incurred in the present, it keeps going even though the path becomes long.

Wouldn’t it be better to combine the best of both? A* algorithm invented in 1968 is A combination of heuristic approaches such as BFS and conventional methods such as Dijsktra algorithm. Somewhat differently, heuristics like BFS often give an approximate solution rather than a guaranteed optimal solution. However, although A* is based on heuristics that do not guarantee the best solution, A* guarantees finding A shortest path.

The heuristic function H (n) tells A* the estimate of the minimum cost from any node N to the target node. Choosing a good heuristic function is important.

The ability of A* to change its own behavior is based on heuristic cost functions, which are very useful in games. A compromise between speed and accuracy will make your game run faster. In many games, you don’t really need the best path, just an approximation. What you need depends on what’s happening in the game, or how fast the machine is running the game.

Suppose your game has two terrains, plains and mountains. The cost of moving in the plains is 1 and in the mountains it is 3. A* is going to search three times as far along flat land as it does along mountainous land. This is because there may be a path along the plains to the mountains. Setting the evaluation distance between the two adjacent points to 1.5 can accelerate the search process of A*. And then A star will compare 3 to 1.5, which is no worse than comparing 3 to 1. It is not as dissatisfied with mountainous terrain, so it won’t spend as much time trying to find a way around it. Alternatively, You can speed up A*’s search by the amount it searches for paths around mountains — just tell A* that movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.

The choice between speed and accuracy is not static. You can dynamically select based on CPU speed, the number of slices of time spent searching for paths, the number of units on the map, the importance of the object, the size of the group, the difficulty, or any other factor. One way to achieve a dynamic compromise is to establish a heuristic function that assumes that the minimum cost of passing through a grid space is 1, and then establish a cost function for measuring (scales) :

G ‘(n) = 1 + alpha * (g(n) — 1)

If alpha is 0, then the value of the improved cost function is always 1. In this case, the terrain cost is completely ignored, and the A* job becomes simply to determine whether A grid can pass. If alpha is 1, then the original cost function will work, and then you get all the advantages of A*. You can set alpha to any value from 0 to 1.

You can also consider making a choice about the return value of the heuristic: the absolute minimum cost or the expected minimum cost. For example, if most of the terrain on your map is grass at cost 2 and some of the rest is roads at cost 1, then you might consider having the heuristic function return 2* distances instead of roads.

The choice between speed and accuracy is not global. There are certain areas of the map where accuracy is important and you can make dynamic choices based on that. For example, if we might stop recalculating the path or change direction at some point, it is more important to choose a good path near the current position, so why bother with the accuracy of subsequent paths? Or, for a safe area on a map, the shortest path may not be very important, but when escaping from an enemy village, safety and speed are of Paramount importance. In safe areas, it is possible to consider taking an approximate path rather than an exact shortest path, so that pathfinding is fast. But in dangerous areas, the safety and speed of escape are important, that is, the accuracy of the path is important, so you can spend more time finding the exact path.

If your heuristic is exactly equal to the actual optimal path, as shown in the figure in the next section, you will see that there will be very few nodes for the A* extension. What happens inside the A* algorithm is that at every node it calculates f(n) = g(n) + h(n). When h(n) matches exactly g(n), the value of f(n) will not change along the path. All nodes that are not on the right path have an f value greater than the one on the right path. If there are already nodes with lower f values, A* will not consider nodes with higher f values, so it will certainly not deviate from the shortest path.

(Translator: This is not easy to translate, the original for now)

Then an heuristic function h ‘is added to evaluate the cost of getting to a nearby waypoint from any location. (The latter can also be calculated by preestimation, if desired.) The final heuristic function can be:

h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)

Or if you want a better but more expensive heuristic, evaluate the above equation with all w1 and w2 pairs near the node and the target, respectively. Translator: Or if you want a better but more expensive heuristic, evaluate the above with all pairs w1, W2 That are close to the node and the goal, respectively.)

In grid maps, there are some well-known heuristic functions.

(translator note: Manhattan distance – two in latitudinal direction combined with distance, in what direction the D (I, J) = | XI – XJ | | + YI – YJ |. For one who has a south north, east direction rules is layout of urban streets, the distance from one point to another point is in the north and the south on upward travel distance and in what direction of travel distance so the Manhattan distance is also called a taxi distance, Manhattan distance is not distance invariant, when axis changes, the distance between points is different – baidu know)

If your units can be moved at any Angle (other than in the direction of the grid) then you might want to use straight-line distances:

h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

However, if this is the case, you will run into trouble when using A* directly, because the cost function g will not match inspire the function h. Because the Euclidean distance is shorter than both the Manhattan distance and the diagonal distance, you can still get the shortest path, but A* will run longer:

One reason for poor performance comes from the ties heuristic function. Some paths are explored when they have the same f value, although we only need to search for one of them:

Ties in f values.

To solve this problem, we can add a small tie breaker to the heuristic function. The added value must be deterministic for the node (that is, it cannot be a random number), and it must differentiate f values. Because A* sorts f values, making f values different means that only one “Equivalent” f value will be tested.

One way to add value is to nudge the h’s units of measure a little. If we reduce the scale it Ethiopia, then the f note will increase gradually as we move toward the goal. Unfortunately, this means that A* tends to expand to nodes closer to the original point than to nodes closer to the target. One could add scale it Ethiopia (even 0.1%) and A* would tend to scale up towards the goal.

Heuristic *= (1.0 + p)

The factor p is selected such that p < the minimum cost of moving one step/the expected longest path length. Assuming you don’t want your path to be more than 1000 steps, you can make P = 1/1000. The result of this added value is that A* has fewer nodes to search for than before.

Tie-breaking scaling added to heuristic.

When obstacles are present, of course you still need to find your way around them, but be aware that when you get around them, the area A* will search is very small:

Tie-breaking scaling added to heuristic, works nicely with obstacles.

Steven Van Dijk suggests that a more straightforward approach is to pass H to a comparison function. When f values are equal, the comparison function checks for h and then adds value.

A different way to add value is to prefer the line (line) from the initial point to the target point:

dx1 = current.x – goal.x

dy1 = current.y – goal.y

dx2 = start.x – goal.x

dy2 = start.y – goal.y

cross = abs(dx1*dy2 – dx2*dy1)

Heuristic + * 0.001 = cross

This code calculates the vector cross-product between the start to goal vector and the current point to goal vector. When these vectors don’t line up, the cross product will be larger. As a result, this code chooses a path that slightly favors the line from the initial point to the target point. When there are no obstacles, A* not only searches very little area, but the path it finds looks pretty good:

Tie-breaking cross-product added to heuristic, produces pretty paths.

However, because this added value tends to be a straight path from the initial point to the target point, strange results can occur when obstacles appear (note that this path is still the best, but it just looks strange) :

Tie-breaking cross-product added to heuristic, less pretty with obstacles.

In order to interactively study the value-added method improvement, please refer to James Macgill A * is an applet (www.ccg.leeds.ac.uk/james/aStar… A* “approach, you’ll see the added value. When you use the “Fudge” method, you should see the result of adding the cross product to the heuric function above.

Another way to add value, however, is to carefully construct your A* priority queue so that newly inserted nodes with A special F value are always better than previously inserted nodes with the same F value.

You may also want to see more flexible (translator note: the original for sophisticated) add additional value of AlphA * algorithm (home1. Stofanet. Dk/breese/pape…