Shulou(Shulou.com)05/31 Report--

How to parse the Heuristics function, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

The heuristic function h (n) tells A * the minimum cost evaluation value from any node n to the target node. Therefore, it is important to choose a good heuristic function.

The role of heuristic function in A*

Heuristic functions can be used to control the behavior of A*.

In one extreme case, if h (n) is 0, only g (n) works, and the A* algorithm evolves into the Dijkstra algorithm, which ensures that the shortest path can be found.

If h (n) is always less (or equal) than the cost of moving from n to the target, then A* is guaranteed to find a shortest path. The smaller the h (n) is, the more points A* needs to expand and the slower it runs.

If h (n) is exactly equal to the cost of moving from n to the target, then A* will only follow the best path and will not extend to any other node and can run very fast. Although this cannot happen in all cases, you can still make h (n) exactly equal to the actual generation value in some special cases. As long as the information given is perfect, A* will run perfectly.

If h (n) is more expensive than moving from n to the target, A* is not guaranteed to find a shortest path, but it can run faster.

At the other extreme, if h (n) is much larger than g (n), only h (n) works, and the A* algorithm evolves into a greedy best first search algorithm (Greedy Best-First-Search).

So the choice of h (n) becomes an interesting situation, depending on what results we want in the A* algorithm. When h (n) is appropriate, we will get the shortest path very quickly. If the estimated cost of h (n) is too low, we will still get the shortest path, but the speed will slow down. If the estimated cost is too high, we will abandon the shortest path, but A* will run faster.

This feature of A* is very useful in game development. For example, you may find that in some cases, you would rather have a "good" path than a "perfect" path. To balance the relationship between g (n) and h (n), you can modify either of them.

Note: technically, if the heuristic function value underestimates the actual cost, the A* algorithm should be called the simple An algorithm (simply A). However, I will continue to call it the A* algorithm because their implementation is the same, and the game programming community does not distinguish between the An algorithm and the A* algorithm.

Speed and accuracy?

The ability of A* to change its behavior based on heuristic and cost functions is very useful in games. The tradeoff between speed and accuracy can improve the speed of the game. For most games, you don't need the best path between two points. All you need to know is an approximate path. The path you need often depends on what happens next in the game, or how fast the computer running the game is.

Suppose you have two kinds of terrain in your game, the plain and the mountain, and their movement costs are 1 and 3 respectively. The length of the path along the plain is three times as long as that of the mountain. This is because there may be a plain path around the mountains. You can set the heuristic distance between the two map units to 1.5 to speed up the search for A*. So A* will change the cost of moving in the mountains from 3 to 1.5, which is not as big as 3 to 1. The cost of moving in the mountains is not as high as it used to be, so it doesn't take much time to find a path around the mountains. Alternatively, you can speed up the search of A* by telling A* that the cost of moving in the mountains is 2 instead of 3, in order to reduce the number of searches on the paths around the mountains. Now, the search path along the plains is only twice as fast as that along the mountains. Both methods give up the ideal path to get faster search speed.

The tradeoff between speed and accuracy does not need to be fixed. You can choose dynamically based on the CPU rate, the number of time slices used for pathfinding, the number of objects on the map, the importance of the objects, the size of the group, the difficulty level, or any other factor. A dynamic compromise heuristic function method is to assume that the minimum cost through a grid space is 1, and then establish a cost function (cost function) within the scope of the following formula:

G'(n) = 1 + alpha * (g (n)-1)

If the alpha value is 0, the value of the modified cost function will always be 1. In this case, the terrain cost is completely ignored, and the work of A* becomes a simple judgment of whether a grid can pass or not. If the value of alpha is 1, the initial cost function will be used and you will get all the advantages of the A* algorithm. You can set alpha to any value between 0 and 1.

You should also consider choosing between the absolute minimum cost and the expected minimum cost returned by the heuristic function. For example, if most of the terrain on your map is grass with a movement cost of 2 and some terrain is a road with a movement cost of 1, you might consider letting the heuristic function assume that there are no roads and only return twice the distance.

The choice between speed and accuracy does not have to be global. In some areas of the map, you can make dynamic choices based on the importance of their accuracy. For example, assuming that we can stop and recalculate the path or change direction at any point, why bother with the accuracy of the subsequent path? In this case, it is more important to choose a path quickly. Or, for a safe area on the map, the exact shortest path is not that important, but safety and accuracy are necessary when crossing the dangerous area.

Measurement

A* calculate f (n) = g (n) + h (n). In order to add two values, the two values must be measured in the same unit. If g (n) is measured in hours and h (n) in meters, A* will think that g or h is too big or too small, so either you can't get a good path, or A* will run more slowly.

Exact heuristic function

If your heuristic function value is exactly equal to the distance of the best path, as shown in the figure in the following section, you will see that there are very few nodes in the A* extension. What the A* algorithm does is calculate f (n) = g (n) + h (n) at each node. When h (n) and g (n) match exactly, the value of f (n) does not change along the path. The f value of all nodes not on the correct path is greater than that of the node on the correct path. Since A* does not consider points with higher f values before considering points with lower f values, it certainly will not deviate from the shortest path.

Pre-calculated exact heuristic function

One way to construct accurate heuristic functions is to pre-calculate the length of the shortest path between each pair of nodes. This is not feasible for the maps of most games. However, there are several ways to approximate heuristic functions:

Fit the coarse mesh of appropriate density (coarse grid) on the fine mesh (fine grid). The shortest path between any pair of nodes in the coarse grid is calculated in advance.

Pre-calculate the shortest path between any pair of path points (waypoints). This is a generalization of the coarse grid method.

Then add a heuristic function h' to estimate the cost from any location to its adjacent path point. (if necessary, the latter can also be obtained by pre-calculation.) The final heuristic function will be:

H (n) = h'(n, W1) + distance (W1, w2) + h' (w2, goal)

Or, if you want a better but more expensive heuristic, calculate the above with all W1, W2 near the node and near the target, respectively.

Linear exact heuristic function

In special cases, heuristic functions can be made accurate without pre-calculation. If your map has no obstacles or slow-moving areas, the shortest path from the initial point to the target point should be a straight line.

If you are using a simple heuristic (you don't know about the obstacles on the map), then it should match the exact heuristic. If not, there may be a problem with the type and unit of measure of the heuristic function you choose.

Heuristic function in Grid Map

There are some well-known heuristic functions available in grid maps.

The distance of the heuristic function matches the allowed movement:

In a square grid, allow movement to the 4 neighborhood, using the Manhattan distance (L1).

In a square grid, movement to the 8 neighborhood is allowed, using a diagonal distance (L ∞).

In a square grid that allows movement in any direction, the Euclidean distance (L2) may be appropriate, but it may not. If you use A* to find a path on the grid, but you are not allowed to move on the grid, you may want to consider other forms of presentation of the map.

In the hexagonal mesh, six directions are allowed to move, and the Manhattan distance suitable for the hexagonal mesh is used.

Manhattan distance (Manhattan distance)

For square grids, the standard heuristic function is the Manhattan distance. Consider your cost function and determine the minimum cost D for moving from one location to the next. In a simple case, you can set D to 1. In a directional grid that can move in four directions, the heuristic function is D times the distance from Manhattan:

Function heuristic (node) =

Dx = abs (node.x-goal.x)

Dy = abs (node.y-goal.y)

Return D * (dx + dy)

How to determine D? The unit of measurement you use should match your cost function. For the best path, and the "acceptable" heuristic function, D should be set to the lowest generational value of movement between adjacent squares. On a terrain where there are no obstacles and the minimum movement cost is D, for each step closer to the target, g increases the movement cost of D and h reduces the cost of D. When g and h are added, f remains the same; this is an indication that the heuristic function matches the unit of measure of the cost function. You can also make A* run faster by giving up the optimal path to increase the cost D or reducing the ratio between the lowest and highest marginal costs.

Diagonal distance

If you are allowed to move diagonally in the map, you need a different heuristic function (sometimes called Chebyshev distance (Chebyshev distance)). 4 units to the east, 4 units to the north, 4 units (4 east, 4 north) to the Manhattan distance is 8 miles D. However, for diagonal distance, you can simply move four diagonal lengths, so the heuristic function will be 4D. The following function is used to deal with diagonals, assuming that the movement cost of both lines and diagonals is D:

Function heuristic (node) =

Dx = abs (node.x-goal.x)

Dy = abs (node.y-goal.y)

Return D * max (dx, dy)

If the cost of moving along the diagonal is not D, but similar to D2 = sqrt (2) * D, then the above heuristic is not for you. You will want a more complex and accurate function:

Function heuristic (node) =

Dx = abs (node.x-goal.x)

Dy = abs (node.y-goal.y)

Return D * (dx + dy) + (D2-2 * D) * min (dx, dy)

Here, we calculate the number of steps required not to walk diagonally, and then subtract the number of steps saved by walking diagonally. There are min (dx, dy) steps on the diagonal, and the cost of each step is D2, which can save the cost of 2D non-diagonal steps.

Patrick Lester writes this heuristic function in a different way, using the explicit expressions of dx > dy and dx < dy. The above code has the same test method, but it hides the internal call to the min function.

Euclidean distance

If you are allowed to move along any angle (rather than in the direction of the grid), you should probably use a straight line distance:

Function heuristic (node) =

Dx = abs (node.x-goal.x)

Dy = abs (node.y-goal.y)

Return D * sqrt (dx * dx + dy * dy)

In this case, however, it may be troublesome for you to use A* directly because the cost function g does not match the heuristic function h. Since the Euclid distance is shorter than the Manhattan distance or diagonal distance, you will still get the shortest path, but A* will take longer to run:

Euclidean distance after squared

I have seen some pages about A* that recommend that you use the square of distance to avoid the time-consuming square root calculation of Euclidean distance.

Function heuristic (node) =

Dx = abs (node.x-goal.x)

Dy = abs (node.y-goal.y)

Return D * (dx * dx + dy * dy)

Please don't do this! This will undoubtedly lead to the problem of the unit of measurement. Because you want to add the values of the functions g and h, their units of measure need to match. When A* calculates f (n) = g (n) + h (n), the square of the distance will be much more expensive than the function g, and you will stop because the heuristic function is overrated. For longer distances, this will approach the extreme case of g (n) without any help in calculating f (n), and the A* algorithm will degenerate into a greedy best first search algorithm (Greedy Best-First-Search).

You can also reduce the unit of measure for heuristic functions. However, at this point you will face the opposite problem: for shorter distances, the cost of heuristic functions is much lower than that of g (n), and the A* algorithm will degenerate to the Dijkstra algorithm.

If you analyze and find that the cost of the square root is significant, either use the fast square root to approach the Euclidean distance, or use the diagonal distance as the approximate value of the Euclidean distance.

Multiple targets

If you want to search for one of several targets, build a heuristic function h'(x), which is H2 (x), h3 (x), h4 (x), … Where H2, h3, and h4 are heuristic functions near each target point.

If you want to search for a point near a target, ask the A* algorithm to find a path to the center of the target area. When the node being processed is from an open set (OPEN set), it exits when a node close enough is obtained.

The Breaking ties method when the values are equal

On some grid maps, there are many paths of the same length. For example, in areas where the terrain is flat with no change, the use of meshes produces many paths of equal length. A* may search for all paths with the same f value instead of one of them.

Equality of f value

To solve this problem, we need to adjust the value of g or h; it is usually easier to adjust the value of h. The tie breaker must be determined based on the vertex (that is, it should not be just a random number), and it must make the f value different. Because A* sorts f values, making f values different means that only one of all "equivalent" f values will be searched.

One way to choose between equal values is to slightly change the unit of measure of the (nudge) h value. If we decrease the unit of measure, then as we move toward the target point, the f value will gradually increase. Unfortunately, this means that A* will be more likely to extend nodes close to the original point than to nodes close to the target. We can slightly increase the unit of measure (or even 0.1%). A* will be more inclined to expand nodes close to the target point.

Heuristic * = (1.0 + p)

The choice of factor p should make p

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.