A * algorithm preliminary (source code)

There are a lot of articles and code about a * algorithm. Here is a source code I have organized, modified from other people's examples. In this code example, the influence of the map information on the addressing result can be used in the map containing different types of terrain information. Since the code can be debugged, you can see how every step is done, I don't have much explanation here. #include #include

#define cols 3 // Map #define rows 3 # Define Total_TILES 9

#define tilenum (x, y) (Y * COLS X 1) // Judgment is the first few plaids on the map

Struct node {long f, h, i; // Here, I added an I function, mainly for map information INT G; int X, y; int nodenum; struct node * parent; struct node * child [8] ; / * A Node May Have Upto 8 (null) children. * / Struct node * NextNode; / * for fling purposes * /};

Struct node * open; struct node * closed;

INT TILEMAP [TOTAL_TILES] = {/ 1, 1, 1, / 1, 2, 1, / 1, 1, 1}; // map information, currently from (0, 0) to (2, 2) The address results are (0, 0) -> (1, 1) -> (2, 2). If the 2 in the middle is modified to 4, it indicates that it is difficult to walk or the swamp pavement is difficult, and the address results are (0) -> (0, 1) -> (1, 2) -> (2, 2).

Struct stack {struct node * nodeptr; struct stack * nextstackptr;}; struct stack * stack;

void Push (struct NODE * Node) {struct STACK * tmp; tmp = (struct STACK *) calloc (1, sizeof (struct STACK)); tmp-> NodePtr = Node; tmp-> NextStackPtr = Stack-> NextStackPtr; Stack -> NextStackPtr = TMP;}

struct NODE * Pop () {struct NODE * tmp; struct STACK * tmpSTK; tmpSTK = Stack-> NextStackPtr; tmp = tmpSTK-> NodePtr; Stack-> NextStackPtr = tmpSTK-> NextStackPtr; free (tmpSTK); return (tmp) }

Struct node * checkopen (int tilenum) {struct node * tmp = open-> nextnode; while (tmp) {if (tmp-> nodenum == tilenum) return (tmp); else tmp = tmp-> nextNode;} return NULL);

Struct node * checkclosed (int tilenum) {struct node * tmp = closed-> nextnode; while (tmp) {if (tmp-> nodenum == tilenum) return (tmp); Else TMP = TMP-> NextNode;} return NULL);} void propagatedown (struct node * old) {Int C, g; struct node * child, * father;

g = OLD-> g; for (c = 0; c <8; C ) {= ((Child = OLD-> Child [C]) == null) Break; if (g 1 g) {child-> g = g 1; Child-> f = child-> g child-> h child-> i; // child-> f = child-> g child-> h; child -> parent = Old; push (child);}} while (stack-> nextstackptr! = Null) {father = pop (); for (c = 0; c <8; c ) {ix ((Child = Father-> Child [C]) == null) Break; if (Father-> g 1 g) {child-> g = father-> g 1; child-> f = child-> g CHILD-> H Child-> i; // child-> f = child-> g child-> h; child-> parent = father; push (child);}}}}}

Void INSERT (Struct Node * Successor) {struct node * tmp1, * tmp2; long f;

IF (open-> nextnode == null) {open-> NextNode = success}

f = sucpsor-> f; tmp1 = open; tmp2 = open-> nextnode; while (tmp2! = null) && (tmp2-> f)) {TMP1 = TMP2; TMP2 = TMP2-> NextNode;} Successor -> NextNode = TMP2; TMP1-> NextNode = Successor;

Void GenerateSucc (Struct Node * BestNode, long x, long y, long dx, long dy {int G, tilenums, c; struct node * old, * success

Tilenums = tilenum (x, y); // g = bestnode-> g tilemap [tilenums]; g = bestnode-> g 1; if ((old = checkopen (tilenums))! = Null) {for (c = 0; C <8; C ) {IF (BestNode-> Child [C] == null) Break;} bestnode-> child [c] = OLD; if (g g) {old- > PARENT = BESTNODE; OLD-> g = g; OLD-> f = g OLD-> H OLD-> i; // OLD-> f = g OLD-> H;}} else IF ((Old = CheckClosed (Tilenums))! = Null) {for (c = 0; c <8; C ) {if (BestNode-> Child [C] == null) Break;} bestnode-> child [c] = Old; if (g g) {old-> parent = bestnode; old-> g = g; // old-> f = g old-> h; old-> f = g OLD-> H OLD-> I; Propagatedown (OLD);}} else {success {success *) Calloc (1, sizeof (struct node)); successor-> parent = bestnode; successor-> nodenum = tilenums; successor- > g = g; // successor-> h = abs (x - dx) ABS (Y - DY); Successor-> h = (x - dx) * (x - dx) (Y - DY) * ( Y - DY); Successor-> i = Tilemap [Successor-> nodenum-1]; Successor-> f = g sucssor-> H sucssor-> i; // successor-> f = g sucpsor-> h; successor-> x = x; Successor-> y = y; insert (success); for (c = 0; c <8; C ) {if (BestNode-> Child [C] == null) Break;} bestnode-> child [c] = sucpsor;}}

Void GenerateSuccessors (Struct Node * BestNode, long dx, long dy) {long x, y;

/ * Upper-left * / x = bestnode-> x - 1; y = bestnode-> y - 1; if (x> = 0 && y> = 0) generateSucc (BestNode, X, Y, DX, DY); / * Upper * / x = bestnode-> x; y = bestnode-> y - 1; if (y> = 0) generateSUCC (BestNode, X, Y, DX, DY);

/ * Upper-right * / x = bestnode-> x 1; y = bestnode-> y - 1; if (x

/ * Right * / x = bestnode-> x 1; y = bestnode-> y; if (x

/ * Lower-right * / x = bestnode-> x 1; y = bestnode-> y 1; if (x

/ * Lower * / x = bestnode-> x; y = bestnode-> y 1; if (Y

/ * Lower-left * / x = bestnode-> x - 1; y = bestnode-> y 1; if (x> = 0 && y

/ * Left * / x = bestnode-> x - 1; y = bestnode-> y; if (x> = 0) generatesucc (BestNode, X, Y, DX, DY);}

struct NODE * ReturnBestNode (void) {struct NODE * tmp; tmp = OPEN-> NextNode; OPEN-> NextNode = tmp-> NextNode; tmp-> NextNode = CLOSED-> NextNode; CLOSED-> NextNode = tmp; return (tmp }

Struct Node * Findpath (Long SX, Long Sy, Long DX, Long Dy) {Struct Node * Node, * BestNode; Int TilenumDest = Tilenum (DX, DY); Open = (Struct Node *) Calloc (1, SIZEOF (Struct Node)); Closed = (struct node *) Calloc (1, sizeof (struct node));

Node = (struct node *) Calloc (1, sizeof (struct node)); node-> nodenum = tilenum (sx, sy); node-> g = 0; // node-> h = ABS (SX - DX) ABS (Sy - DY); Node-> H = (SX - DX) * (Sy - DX) * (Sy - DY); Node-> i = TileMap [Node-> Nodenum-1 ]; Node-> f = node-> g node-> h node-> i; // node-> f = node-> g node-> h; node-> x = sx; node-> y = Sy; open-> nextnode = node; for (;;) {bestnode = (struct node *) returnBestNode (); if (BestNode-> nodenum == tilenumdest) Break; GenerateSuccessors (BestNode, DX, DY);} return BestNode;

INT WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow) {Stack = (struct STACK *) calloc (1, sizeof (struct STACK)); struct NODE * Path = FindPath (0, 0, 2, 2) RETURN 0;} Although the above algorithm can find the destination address, there are several issues: 1) Efficiency problem: When the path to the end point does not exist, the cost of A * is relatively large, should be like a pre- Address algorithm or improve the current algorithm. 2) When the side angle angle angle of the local map cannot be leaving, there are many polylines in the addressing result. At this point, it can be found to be able to beautify the path. 3) There are currently eight in the addressing direction, corresponding to the eight directions of 2D, and feel that it should be able to extend to 3D space, do a 3D A * addressing. 3D should be 26 directions.