Principle and Implementation Technology of Path-Finding Algorithm in Instant Strategic Games
Author: Shen Lu
In the past few years, when I met school in school, I often worked with my classmates in the dormitory of the "Red Alert", and I have been exploring the "Red Alert" so hidden programming mystery behind the "Red Alert". Recently, find a free time, finally put the previous ideas into implementation, write an instant strategic game with VC (executing the program in the attachment). In this case, the principle of the path-finding algorithm in the instant strategic game is written to everyone.
Imagine, when you are in front of the computer, you are talking to the thousandth of horses on the screen, suddenly found that the tanks have stopped the obstacle, you will definitely be very dissatisfied with their stupid behavior. . Therefore, in a real-time computer game, a real-time finding algorithm is used as a movable object (eg, "The" Red Police "tank, soldier) calculates a more" smart "walking route.
First, the path finding algorithm for individual objects
The most basic problem that needs to be solved in the diameter algorithm is to avoid obstacles. The most easy implementation is (see Figure 1):
From the start point to the end point to pull a straight line A. Walking along the straight line A facilitates the obstacle, it is walked around the obstacle in a clockwise direction until it comes to the straight line A. Repeat step 2, it will be able to finally reach the destination.
figure 1
(Note: The red dot indicates the starting point, the blue dot indicates the end; the yellow linear is marked as a, black linear marked B, red straight line marked B)
The path calculated by this algorithm is not the shortest, sometimes it will go out of silly route, but the speed is very fast, can meet the real-time requirements in the game in the lower grade PC, the diameter diameter algorithm in the "Red Police" It is based on this (using a more advanced A * algorithm in the Empire Times, which is limited to the space here). The above algorithms can be improved, so that the travel route of the movable object is more reasonable.
(1) Looking at Figure 1, it is clear that the moving object should be wrapped around the ball in the counterclockwise, not the rendezvous direction. Thus, when an obstacle is encountered, the surround direction is first to be judged. If the counterclockwise travel is in a shorter path, the counterclockwise direction can be hit by a shorter path, then the counterclockwise direction is selected, and vice versa.
(2) Try to take a straight line path to reduce bypass. As shown in FIG. 1, the travel route B is calculated first in the above algorithm, and then when the movable object is traveling on the route B, every step is pulled from the current position to the end point, if the line C is linear C, if along the straight line C. Adversely meets a certain section of the walking route B that has not yet passed (there is no obstacle in the middle), stop the winding, directly pressing the straight line C to the route B, thus shortening the way.
(3) When the end point is surrounded by an obstacle, the moving object can never reach the end, whether it is bypass the clockwise direction or counterclockwise, can only return to the original place, and cannot travel. The method of processing in this case is a week around the barrier, and the nearest way is nearest from the end.
The finding algorithm in this paper mainly involves the generation technology of straight line and surrounding obstacle route. The rasterization of the straight line can be referred to any computer graphics textbook, which is no longer described here. The generating algorithm for surrounding the obstacle route is given below (in a clockwise direction).
figure 2
When walking around the obstacle, first determine the direction of the current obstacle relative to the movable object, labeled an integer i (see Figure 2). For example, the obstacle is in the direction 5 in the right side of the movable object. Then the movable object is followed by the direction J = (i N) MOD 8 (n = 1..7) until the obstacle is obsolete. If the obstacle is located directly above (7), the movable object first looks at the upper left direction (0 = (7 1) mod 8) whether it can pass, if it is not limited, then the left direction (1 = (7 2) mod 8) However, it is not possible to simply press the arrow as shown in the figure to try the rest of the remaining directions until it is found and walks in the direction. If the obstacle is located in the lower left (2), then press (3), lower right (4), right (5), upper right (6), above (7), left (0), left side ( 1) Wait for the seven directions to see if there is a path. As for the processing of obstacles relative to other locations of the movable object, this type is pushed. Repeat steps 1, 2, can complete the clockwise wrap around the obstacle. This algorithm detailed pseudo-language description, repeated calling function clockwisewalkonestep can be wound around the obstacle. Boolean Clockwisewalkonestep (Int & Ncol, Int & nrow, INT & I);
{
Int n;
For (n = 1; n <= 7; n )
{
i = (i n) MOD 8;
IF (Map [ncol, nrow] .ispassable (i) = true)
Break;
}
IF (n == 7 && map [ncol, nrow] .ispassable (i) = false)
Return False;
Switch (i)
Case 1:
{
Ncol = ncol-1;
i = 7;
Break;
}
Case 2:
{
IF (Map [ncol, nrow] .ispassable (3) == false // Try to take vertical or horizontal direction
{
Ncol = ncol-1;
NROW = nrow 1;
i = 7;
}
Else
{
NROW = nrow 1;
i = 0;
}
Break;
}
Case 3:
{
NROW = nrow 1;
i = 1;
Break;
}
Case 4:
{
IF (Map [ncol, nrow] .ispassable (5) == false)
{
Ncol = ncol 1;
NROW = nrow 1;
i = 1;
}
Else
{
Ncol = ncol 1;
i = 2;
end
}
Break;
}
Case 5:
{
Ncol = ncol 1;
i = 3;
Break;
}
Case 6:
{
IF (Map [ncol, nrow] .ispassable (7) == false)
{
Ncol = ncol 1;
NROW = nrow-1;
i = 3;
}
Else
{
NROW = nrow-1;
i = 4;
}
Break;
}
Case 7:
{
NROW = nrow-1;
i = 5;
Break;
}
Case 0:
{
IF (Map [ncol, nrow] .ispassable (1) = false)
{
Ncol = ncol-1; nROW = nrow-1;
i = 5
}
Else
{
Ncol = ncol-1;
i = 6;
}
Break;
}
}
Return True;
}
Second, walking path generation technology in dynamic obstacle environments
The algorithm just described is only applicable to a single-movable object to generate a walking path in a stationary obstacle environment. However, in the actual instant strategic game, a group of tanks are often in a dynamic map, and different tanks are obstacles when they meet during walking, and are movable obstacles. Therefore, it is necessary to make a modification of the above algorithm such that the object avoids the movable obstacle in motion.
The most intuitive solution is to recculate the walking path immediately, and the disadvantage of this method is to repeat the calculation path, which is too much. In fact, when an object collides a movable obstacle in a motion state, you can wait for a while, then find that the movable obstacle has been moved, you can continue to move forward in the original walking path, thereby saving repetition The time of calculating the path; Recalculate the walking path avoids movable obstacles. Obviously, use this method to reduce a lot of repetition calculations and speed up the execution speed. The calculation method is shown in the case of the calculation.
// Traverse all movable objects
For (i = 1; i <= n; i )
{
Switch (TANK [i] .state) {
Case Run:
{
IF (TANK [i] receives command commands)
{
TANK [i] .goalpos = destination address;
TANK [i] .state = findnewpath;
}
IF (TANK [i] .pos == routelist [TANK [I]]. getndpos ()) // arrived at the end point
{
TANK [I] .state = stillness;
Break;
}
Tank [i] .posnext = routelist [TANK [i]]. Getnextpos (); // Remove the next step
IF (Map [Tank [i] .posnext] .passable == true)
{
TANK [i] .state = moving;
Tank [i] .currentmovingpos = tank [i] .pos;
MAP [TANK [I] .posnext] .passable = false;
Map [tank [i] .pos] .passable = false;
}
Else
{
IF (map [tank [i] .posnext] .state == stillness || (TANK [i] .waittime> specified time && tank [i] .priornum> map [tank [i] .posnext] .priornum))
TANK [i] .state = findnewpath;
Else
TANK [i] .waittime ;
}
Break;
}
Case FindNewPath:
{
According to TANK [i] .goalpos, calculate the walking path of TANK [i], and add Routelist [TANK [I]];
IF (routelist [tank [i]] is empty)
TANK [i] .state = findnewpath;
Else
{
TANK [i] .state = run; tank [i] .waittime = 0;
}
Break;
}
Case moving:
{
// During linear interpolation between POS and POSNext
IF ((TANK [i] .currentmovingpos nstep) { Tank [i] .currentmovingpos = nstep; TANK [i] .state = moving; } Else { Tank [i] .currentmovingpos = tank [i] .posnext; TANK [i] .state = run; TANK [I] .waittime = 0; MAP [TANK [I] .posnext] .passable = false; Map [TANK [i] .pos] .passable = true; TANK [i] .pos = tank [i] .posnext; } } Case STILLNESS: { IF (TANK [i] receives command commands) { TANK [i] .goalpos = destination address; TANK [i] .state = findnewpath; } Break; } } } Draw background first; For (i = 1; i <= n; i ) Draw (Tank [i] .currentmovingpos); Figure 3 Moving object state conversion diagram In the above algorithm, the movable object has four states (see Figure 3): Stillness, Run, FindneWPath, Moving. In the initial case, the movable object is in the Stillness state. When accepting the command command, you enter the FindNewPath state. Once the walking path is calculated, the movable object is set to the RUN state. In the RUN state, remove the next coordinates from the walkpath list, if the position of the coordinate is obstacted, the state change is move, and the coordinate interpolation between the two steps before and after, and then returns to the RUN state; if found The original calculated walking path is not applicable, and it is returned to the RUN state from the RUN state to the FindNewPath status, and wait for the new path. Finally, when the end point is reached, the state of the movable object is STILLNESS. See the actual effect of this algorithm, please download the DEMO program. Author: Shen Lu Email: uulushen@public1.sz.js.cn Address: Suzhou City, Jiangsu Province getters Road 704 Postal Code: 215000
