Analysis of the Path Search Algorithm UESTC 20013080 Lin Wei 2002.9.12 Introduction: This article describes important improvements to the famous path search algorithm A * algorithm, making it more practical for large-scale, high efficiency, multi-blocking, fuzzy solution tasks in. I hope this paper has a role in pouring jade, so that the reader can raise an anti-three. The A * algorithm mentioned here is widely used in many fields. For example, our familiar instant strategy game is using this algorithm to implement path search. But in the artificial intelligence book, it is only, but there are very few examples. The theory and the actual gap are too large. Some professionals have written code, but the code has the advantage of explaining the algorithm, and in terms of efficiency and practicality. Lack. A * is an inspiration test search plus dynamic plan. Specific implementation relies on two queues Open queues and Close queues. From a little start to detect a few adjacent plaids If you can move and the current movement is the starting point to which of the historical best methods, the lattice is inserted from the small to large inserting the Open queue from the small to large, and several directions are taken out. The node that is the smallest value is placed in a close and then begins with a few adjacent directions. In the Open queue, the conditions are placed in the Open queue. This step is moving on the map, 2. There is no existence in Open, 3. From the starting point to this step, the actual distance from the step is smaller than this three conditions, the node is placed in the Open queue. The specific algorithm netizen has described again, but the approximate algorithm is as follows:
While True Begin1. Add the S point to the Open queue (order to sort the distance from the E point walk from the number of steps from small to large sort) 2. Sort queue Open queue is the minimum number of first points, and save In the CLOSE queue 3. From the list, you will take a step from one of the four (or 8) directions. 4. Estimating step 3 walking to the distance to the target point, and pressing this location The estimated distance is ranked from small to large and put it in Open. Road and save in Path END Chart 1: a * Path Search Algorithm Process Specific Directance and Detailed Algorithm You can see the code http://www.joynb.net/maker/qfind_c.htm (where sort_queue and store_queue are open and close Queue) I think it is necessary to make it eligible for instant strategic games to change the size of the search, that is, limit the size_queue size. Once the size is exceeded, it does not reach the end point, then take a point of the closest point of the end. (From its estimated distance from it to the end point) as the end of the search. II Once the Open queue is empty, the search end does not find the end point, and at this time, it is still found in the above method to find a nearest end point. Such search will not be done without marginally. The above program, everyone will find a deadly place where the speed is influential, and the test search is unchanged, and the program is tedious for each addition to take out two queues, this is the time consuming time. Work, followed by checking whether it is in the queue, this is also very slow, and finally, the array of dynamic planning data (the shortest distance) is saved, and every time you find a big array, this is unacceptable of. What I said is to solve the above problem from the data structure to make the Open / Close two queues no longer involve memory allocation issues, first create a node array Node [MAPH] corresponding to each node above the map. ]; Node has a pointer next and father, next refers to the next node of the queue, Father points to its parent node. Since the Open / Close two queues cannot appear a node two times in a queue, the Open queue is described as long as it point to a node address & node [y] [x] and let Node [y] [x] Next points to the next node, if there is no node, this next is NULL. The same reason is also described in this way. When you look at each search, you don't have to be allocated, insert the node (x, y) as long as the node (x, y) Node [MAPH] [MAPW] The above data and the Open / Close two pointers easily gave several functions such as addToPenQueue. At initialization, one-time distribution ** node is Node [MAPH] [MAPW] (TastarNode definition as follows) Open / Close is no longer allocated for two Tastarnode pointers, initialization Open / Close is equal to NULL In other words, in turn in the open node [y] [x] in accordance with the method of the ordinary end meter, let Open / Close point to node [Maph] [MAPW] in one element, then this The element refers to the next element to form a linked list. Due to the pre-algorithm, check if there is no addition, it will not be added if there is no additional elements, and Open / Close does not have a repetitive element.
Struct Tastarnode {AdWord POS; / / ((Y << 16) | x) When the setting is set, the set unchanged short actualcost; // save the actual overhead estimatecost from the starting point to the node; / / Save this value for the valuation overhead The JudgeCost function is provided to MAX_SHORT SUMCOST; //, the front of the two, for inserting the sorting tastarnode * father; // Parent Node Tastarnode * prev; // on the Open or next Link A node is used to easily remove tastarnode * next; // in the Open or next chain CHAR Modified; // 1 This node is modified, 2/3 represents if Open / Close Table} ** node, * open, * close; // node [MAPH] [MAPW] and Open / Close queue chart 2: Algorithm contact data structure chart 3: Graphical explanation of the algorithm search process See the right search audit map It is possible to simply see that the Open queue does not require memory allocation when inserting / delete and the NEXT pointer of the node and Node [H] [W]. This is an exciting improvement
The image is shown in Node [H] [W] and Open tables. When the Node is initialized, EstimateCost is set to max, and a variable description is required. The Open queue is 1 bit 1. If the second bit is 1 in the close, you can know the relationship between the nodes and the queue, and use an array to record the node location of the optimal distance. And according to the state variables in the previous state, if it is no longer recorded, it is not recorded, and the data is restored according to this array after the path search is completed. Look at the search trial map, you can simply see that the Open queue does not require memory allocation when inserting / delete, and as long as the Node pointer is changed and the Node [H] [W] in the NEXT pointer of the node. This is an exciting improvement, we first joined the search restrictions Secondary, then removed the memory allocation, and then put each time you find a node from the search chain list from the search chain list, the path algorithm has saved a lot. Unnecessary processes, then see the practical aspect, first determine if the map can be moved without directly judging in the algorithm, it is best to set a virtual function moveable (x, y) to implement (I use the function pointer in the program), Because a block in the game is different for the ground unit and in the air unit, it can be moved, and therefore, it is not a wise choice to directly operate the map element, and the valuation function Judgecost (x, y) should also be set to Function or function pointer is implemented, after all, the method of estimating value is flexible, and it cannot be limited here. And which direction is searching for each search? Use Dirmask to describe the 0-7-bit representative from top to top eight directions, 0 represents no search, 1 means search, then four direction search can be replaced with 0x55 (1010101b), eight directions can be used 0xff is set, so that you can set only three ways to search for 3 directions, which can meet some simple pathfinding tasks, such as the movement of NPC enemies in the RPG can be set. Finally, the range problem is set, the maximum size of the OPEN table can be set to 100-200 (four directions) or 200-300 (eight directions) and the size of the Close table is the maximum number of processing nodes to be set to (Maph) * MAPW) / 16 This setting does not cost a lot of overhead when the soldier walks into a barrel terrain, but goes to the tip of the barrel terrain. Its specific value can be adjusted properly. Of course, the value is, the more the search is, the larger the overhead, the larger (MAPH * MAP) / 16 This value I feel relatively close to the intersteration of the intersteration, the other optimization, due to all the data in the Open queue It is the continuous slogan insertion, and when the data is more efficient, it does not meet high. At this time, there is also a lot of ways to continue to optimize, such as the establishment of a HASH hash table, or use the binary tree to replace the co-spectation, you can refer to the A * code written by the leading company (http://www.joynb.net/maker/ Inside the Path.zip, this is very good, but it can't get a lot of memory allocation / release. So I don't think so much. It is a lot of calculation methods, but the quality of writing is also related to the size of the search: the absolute value of the coordinate difference is equal to the weight, the square and the top, can look at the leading code valuation function. How is written? I saw that there is an article on the Internet that the estimated distance of the current node to the end cannot be larger than the actual distance. What can be called a * algorithm, otherwise it can only call a A algorithm (said in Artificial Intelligence), because it is not necessarily the shortest path, Oh, but if it is only satisfied that the valuation is less than the real value, you can find the shortest path. Then, the search is close to the end. Below is a comparison using different valuation functions:
Chart 4: Judgecost = ABS (DX) ABS (DY) Chart 5: Judgecost = ABS (DX), ABS (DY) Weighted Search, aspect of the two valuation functions, asterisk is the path The point is the search node. When JudgeCost is greater than the real value, from a node algorithm is more willing to search for a point close, in other words, the JudgeCost, the more you buy it, you can close to the end, you can clearly see the left and right two pairs. (click to zoom in). Therefore, we use the coordinates to handle or directly ask for and multiply and multiply (such as 8), when the terrain is complex, the practicality of this method is more similar, and the scale gap of the variety of the seed is more than the figure. Difficult number. So the general purpose use of Weighted DX = ABS (X-ENDX), DY = ABS (Y-end); if (DX> DY) Result = 10 * DX 6 * Dy; Else Result = 10 * DY 6 * DX; this means, the multiplication of 10 and by 6 is the number of trials proved more than the number, so that the size of the search is controlled and reduced, it is not ignored. Here is an example (http://www.joynb.net/maker/pathfind.zip), you can test the search size. If we apply it to the instant strategic game, there are still some points to pay attention to, the collective search should use the policies, share a path, and encounter moving things in the middle. Try to join a plinker path node See if you can spare; you can't wait to move your object yourself; go to time without another search path, big scene to preset some path nodes in advance to make long-distance search, save the path, save the path in direction Save the space saved by coordinates. . . . When you encounter the enemy troops, you can shoot yourself, or send two instructions to the command queue of the soldiers who are blocking the road 1. Remove the current position and wait; 2. Back to the current location, this can produce one one The wonderful effect of the road, the red police has already achieved :-) Hope, it is the march issue, and I started researching this algorithm a year ago, I wrote a three hundred rows of procedures and cooperation, now Take it out to change. A speech, welcome to the letter: Skywindt@yeah.net Electronic Technology University Communications Engineering School 20013080 Ban Linwei September 27, 2002, Friday, References: 1. "Artificial Intelligence Technology" Xi'an Electronic Board ISBN7-5606-0811-6 / TP.04172. "Streamline A * Algorithm" http://www.joynb.net/maker/qfind_c.htm3. "Humanized View Technology" http://mays.soage.com/develop/ai/200204 /RealPath.htm4. "Amit's A * Pages" http://theory.stanford.edu/~amitp/gameprogramming/5. "Intelligent PF" http://www.gamasutra.com/features/19970801/pathfinding.htm6. "THE GAME AI Page" http://www.gameai.com/ This article electronic version and source program: http://www.joynb.net/maker/astar.htm
