A * algorithm solving the shortest path

A * algorithm solving the shortest path ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------ Recently, a lot of friends asked me about the A * algorithm, The purpose is to write a program for the shortest path. This is in the game of the mouse Controlling Elf Sports (not a smart RPG, which is not considered by the mouse as a keyboard direction button), especially instant strategy. But I personally It is considered that the A * algorithm is only suitable for processing a static path to solve, when a large number of objects in the instant strategic game, it is difficult to achieve (nor not achievable, this requires a quite good valuation function, and can not search the path) I strange It is, the A * algorithm should be the basic knowledge of the algorithm. Anyone who has learned the algorithm should know. This should not be in this way. Everyone will flush the computer algorithm book, should look The arrival. (The book is even less than the book), since many friends asked, in various discussion groups, BBS and other places have repeatedly mentioned that the special flowers completed this article and included programs in a afternoon to meet our vast Amateur game production enthusiasts, professionals are free to see, so as to avoid the class door ax ^ _ ^ But if there is a mistake, you must point out. If your Internet time is very precious, please download the source code I annotated (3K) in the introduction A * Before the algorithm, first mention a broad-class priority search, and the breadth priority search is to expand each time the policy of possible development, such as one map, the object is allowed to move in the four directions, then, place the location, object upward The next left and right moves, save four states in memory, and then move again from these four starting points to the respective four directions ... (of course, the unreasonable mobile method can be removed, such as no Back movement) In fact, the entire search seems to be unfolded outward until it reaches the destination, it is clear that it can find the optimal solution, but the number of nodes is increasing, it is really used. In the game, the player will complain that the memory 128m is not enough to use ^ _ ^ and the increase in the number of nodes to be processed, the processing speed will slow down ... It can be said that this algorithm is not practical, and the A * algorithm is actually a kind of inspiration Search, so-called heuristic search, use an appraisal function to evaluate the value of each decision, decide which solution is tried first. This can greatly optimize ordinary breadth priority search. Generally, from the starting point (A ) To the shortest distance to the destination (b) is fixed, we can write a function judge () estimate A to B minimum distance, if the program has been trying to move from the starting point (a) to C point along a route, Then we It is believed that the estimated distance between the AB of this program is A to C actually walking the distance H plus the distance from c to b with judge (). So, no matter which step of our program search is expanded, it will calculate one After each decision, each decision is sorted together with the evaluation value and the waiting process, and then picked out some of the schemes of the shortest route to be processed to expand to the next step, and it is loop to the object to move to the purpose. Only, or all the scenarios have not found a path to the destination. (I usually set the timeout control code in the game, when the memory consumes too much or when you use the search)? No . How to write this algorithm is very important, how to ensure that you can find the shortest path? Afrigent condition is that your valuation function calculates the distance between the two points must be less than or equal to the actual distance. This can be strict from mathematics Prove, interested you can check the relevant information yourself. If your valuation function does not satisfy this, you can only call a A algorithm, and you can't guarantee the final result is the best, but it may be very fast. And the game We don't have to get the best solution. But undoubtedly, in the A * algorithm of that condition, the closer the value of the estimated value, the better the value of the real value, the procedure given below, I only use one Quite simple valuation function: Since the two points, if you have the shortest path in the absence of an obstacle. If you want to write a fast search algorithm, please find a good valuation function, have time, I will In this case, I have taken time to get annotated, and debug passes. If you think about thinking, you can come to E-mail to CloudWu@263.net ;-) / * Cloud wind solving shortest path code (Cloud Wu "

S Pathfinding Code) * January 8, 1999 (1999, Jan 8) * This code did not perform any optimization (including algorithm), but don't know how to optimize it, * it is for teaching purposes Do it, aiming to describe the use of the A * algorithm in the first road * diameter in the code. Since the program is not guaranteed to be a pure A * algorithm ;-) * you can On the basis of understanding this program, write a similar code according to your own understanding. But simple * copy it to your program is not allowed, if you really do it, please use its software directly * Document, write my name ;-) * There is any problem, or suggestion, please e-mail to Cloudwu@263.net * Welcome to my homepage http://member.netease.com/~cloudwu Cloud Breeze Studio) * (You can find some discussions about this problem, and other large amounts of information about game design) * * This program comes with a data file map.dat, saving a map data * //// #define ndebug # include #include #include #include #define mapMaxSize 100 // map area is up to 100X100 # define maxint 8192 // Define one Maximum integer, any two-point distance on the map does not exceed its #define stacksize 65536 // Save the Search Node Stack size #define Tile_Num (x, y) ((Y) * Map_W (x)) // Put X, Y coordinate Convert to the number #define tile_x (n) ((n)% map_w) // by the block number, Y coordinate #define Tile_Y ((N) / MAP_W) // tree structure, comparison Special, it is the reverse link of the leaf node to the root node. Typedef struct node * tree; struct node {int h; int Tile; Tree Father;}; type; type; Link next;}; link queue; // Save Node Tree Stack [stacksize] without processing walking method; // Save the processed node (search after search) int Stacktop; unsigned char map [mapMaxSize] [MapMaxSize] ; // Map Data INT DIS_MAP [MapMaxSize] [MapMaxSize]; / / When saving the search path, the intermediate target is optimally solved intmb_w, map_h; // map wide and high int start_x, start_y, end_x, end_y; // location , End point coordinate // initialization queue vid init_Queue () {queue = (link) malloc (sizeof (* queue)); queue-> node = null; queue-> f = -1; queue-> next = (link) Malloc (SIZEOF (* queue)); queue-> next-> f = maxint; queue-> next-> node = null; queue-> next-> next = null;} // to be processed into the queue, rely on the purpose Estimated distance insertion Void Enter_Queue (Tree node, int f) {link p = queue, father, q; while (f>

P-> f) {father = p; p = p-> next; assert (p);} Q = (link) malloc (SIZEOF (* Q)); assert (queue); Q-> f = F, Q -> node = node, q-> next = p; father-> next = q;} // will be out of the destination to estimate the nearest plan Tree get_from_queue () {tree bestchoice = queue-> next-> node; link Next = queue-> next-> next; free (queue-> next); queue-> next = next; stack [stacktop ] = bestchoice; assert (stacktop node); queue = queue-> next; free (p);}} // Valuation function, valuation X, Y to destination distance, The estimate must ensure that the actual value small INT JUDGE (INT X, INT Y) ABS (End_Y-Y); Return Distance;} // Try the next step to move to X, Y Y, INT X, INT Y, Tree Father {Tree P = Father; INTH; IF (MAP [Y]! = ') Return 1; // If (x, y) Is obstacles, failing while (p) {if (x == Tile_x (p-> tile) && y == TILE_Y (P-> Tile)) Return 1; // If (x, y) has passed, failed P = P-> father;} h = father-> h 1; if (h> = dis_map [y] [x]) Return 1; // If there is a better The scheme moves to (x, y) failed DIS_MAP [Y] = H; // Record the distance of this to (x, y) is the best distance // of history, this step scheme is written to the queue P = (Tree) Malloc (SIZEOF (* P)); p-> h = father-> h 1; p-> tile = tile_num (x, y); Enter_Queue (p, p- > h judge (x, y); return 0;} // path look for main function void Findpath (INT * PATH) {Tree root; INT I, J; stacktop = 0; for (i = 0; i tile = tile_num START_X, START_Y); root-> h = 0;

Root-> Father = null; Enter_Queue (root, judge (start_x, start_y)); for (;;) {Int x, y, child; tree p; root = get_from_queue (); if (root == null) {* PATH = -1; Return;} x = Tile_x (root-> tile); y = tile_y (root-> tile); if (x == end_x && y == end_y) Break; // reach the destination successfully returned Child = Trytile (x, y-1, root); // Try moving CHILD & = Trytile (x, y 1, root); // Try moving CHILD & = Trytile (X-1, Y, Root); / / Try to move Child & = Trytile (x 1, y, root) to the left; // Try to move if (Child! = 0) POP_STACK (); // If the four directions cannot be moved, release this dead node} // Retrospect, save the best path to Path [] in force (i = 0; root; i ) {path [i] = root-> tile; root = root-> father;} path [i ] = - 1; freeetree ();} void printpath {INT i; for (i = 0; Path [I]> = 0; i ) {gotoxy (tile_x (path [i]) 1, TILE_Y (PATH [I]) 1); CPRINTF ("/ xfe");}}} int}} int} int}}}} int}}} int}}} int}}} INTMAP () {file * f; INT I, J; f = fopen ("map.dat", "r"); Assert (f); fscanf (f, "% D,% D / N", & map_w, & map_h); for (i = 0; i = 0 && End_x> = 0); return 0;} void showMap () {INT I, J; CLRSCR (); For (i = 0; i