From 9770f22a2846c68dbeea0780d595ad49ea6c490d Mon Sep 17 00:00:00 2001 From: Bjørn Lindeijer Date: Sat, 5 Feb 2005 14:31:39 +0000 Subject: Supposed to make it more readable, but I don't think really worked. --- src/astar.cpp | 623 ++++++++++++++++++++++++++++++++++++---------------------- src/astar.h | 11 +- src/map.cpp | 10 + src/map.h | 16 +- 4 files changed, 419 insertions(+), 241 deletions(-) diff --git a/src/astar.cpp b/src/astar.cpp index 601a2da9..d6e60227 100644 --- a/src/astar.cpp +++ b/src/astar.cpp @@ -1,28 +1,51 @@ #include "astar.h" -#include "being.h" -#include "map.h" +#define MAP_WIDTH 200 +#define MAP_HEIGHT 200 + +// path-related constants const int numberPeople = 1; int onClosedList = 10; -const int notfinished = 0;// path-related constants +const int notfinished = 0; -//Create needed arrays +// Declare needed arrays //char tiledMap.getPathWalk [MAP_WIDTH][MAP_HEIGHT]; -int openList[MAP_WIDTH*MAP_HEIGHT+2]; //1 dimensional array holding ID# of open list items -int whichList[MAP_WIDTH+1][MAP_HEIGHT+1]; //2 dimensional array used to record -// whether a cell is on the open list or on the closed list. -int openX[MAP_WIDTH*MAP_HEIGHT+2]; //1d array stores the x location of an item on the open list -int openY[MAP_WIDTH*MAP_HEIGHT+2]; //1d array stores the y location of an item on the open list -int parentX[MAP_WIDTH+1][MAP_HEIGHT+1]; //2d array to store parent of each cell (x) -int parentY[MAP_WIDTH+1][MAP_HEIGHT+1]; //2d array to store parent of each cell (y) -int F_cost[MAP_WIDTH*MAP_HEIGHT+2]; //1d array to store F cost of a cell on the open list -int G_cost[MAP_WIDTH+1][MAP_HEIGHT+1]; //2d array to store G_cost cost for each cell. -int H_cost[MAP_WIDTH*MAP_HEIGHT+2]; //1d array to store H cost of a cell on the open list -int pathLength; //stores length of the FOUND path for critter -int pathLocation; //stores current position along the chosen path for critter -int* path_bank ; - -//Path reading variables + +/** 1 dimensional array holding ID# of open list items */ +int openList[MAP_WIDTH * MAP_HEIGHT + 2]; + +/** + * 2 dimensional array used to record whether a cell is on the open list or + * on the closed list + */ +int whichList[MAP_WIDTH + 1][MAP_HEIGHT + 1]; + +/** 1d array stores the x location of an item on the open list */ +int openX[MAP_WIDTH * MAP_HEIGHT + 2]; + +/** 1d array stores the y location of an item on the open list */ +int openY[MAP_WIDTH * MAP_HEIGHT + 2]; + +/** 2d array to store parent of each cell (x) */ +int parentX[MAP_WIDTH + 1][MAP_HEIGHT + 1]; + +/** 2d array to store parent of each cell (y) */ +int parentY[MAP_WIDTH + 1][MAP_HEIGHT + 1]; + +/** 1d array to store F cost of a cell on the open list */ +int F_cost[MAP_WIDTH * MAP_HEIGHT + 2]; + +/** 2d array to store G_cost cost for each cell */ +int G_cost[MAP_WIDTH + 1][MAP_HEIGHT + 1]; + +/** 1d array to store H cost of a cell on the open list */ +int H_cost[MAP_WIDTH * MAP_HEIGHT + 2]; + +int pathLength; /**< length of the FOUND path for critter */ +int pathLocation; /**< current position along the chosen path for critter */ +int* path_bank; + +// Path reading variables int pathStatus; int xPath; int yPath; @@ -38,287 +61,427 @@ void pathfinder_exit() { } /** Find path */ -PATH_NODE *find_path(int pathfinderID, int s_x, int s_y, int e_x, int e_y) { - int onOpenList=0, parentXval=0, parentYval=0, - a=0, b=0, m=0, u=0, v=0, temp=0, corner=0, numberOfOpenListItems=0, - addedGCost=0, tempG = 0, path = 0, x=0, y=0, - tempx, pathX, pathY, cellPosition, - newOpenListItemID=0; +PATH_NODE *find_path(int pathfinderID, int s_x, int s_y, int e_x, int e_y) +{ + int onOpenList = 0, parentXval = 0, parentYval = 0; + int a = 0, b = 0, m = 0, u = 0, v = 0, temp = 0, corner = 0; + int numberOfOpenListItems = 0, addedGCost = 0, tempG = 0, path = 0, x = 0; + int y = 0, tempx, pathX, pathY, cellPosition, newOpenListItemID = 0; // If starting location and target are in the same location... - if (s_x==e_x && s_y==e_y && pathLocation>0)return NULL; - else if (s_x==e_x && s_y==e_y && pathLocation==0)return NULL; - - // If dest tile is NOT_WALKABLE, return that it's a NOT_FOUND path. - if (tiledMap.getPathWalk(e_x, e_y) == NOT_WALKABLE) { - xPath = s_x; - yPath = s_y; - return NULL; - } + if (s_x == e_x && s_y == e_y && pathLocation > 0) return NULL; + else if (s_x == e_x && s_y == e_y && pathLocation == 0) return NULL; + + // If dest tile is NOT_WALKABLE, return that it's a NOT_FOUND path. + if (tiledMap.getPathWalk(e_x, e_y) == NOT_WALKABLE) { + xPath = s_x; + yPath = s_y; + return NULL; + } // Reset some variables that need to be cleared - for(x=0;x= F_cost[openList[2*u]])v = 2*u; - if(F_cost[openList[v]] >= F_cost[openList[2*u+1]])v = 2*u+1; - } else { - if (2*u <= numberOfOpenListItems) { //if only child #1 exists - //Check if the F cost of the parent is greater than child #1 - if (F_cost[openList[u]] >= F_cost[openList[2*u]])v = 2*u; + u = v; + // If both children exist + if (2 * u + 1 <= numberOfOpenListItems) { + // Check if the F cost of the parent is greater than each + // child. + // Select the lowest of the two children. + if (F_cost[openList[u]] >= F_cost[openList[2 * u]]) + v = 2 * u; + if (F_cost[openList[v]] >= F_cost[openList[2 * u + 1]]) + v = 2 * u + 1; + } else { + // If only child #1 exists + if (2 * u <= numberOfOpenListItems) { + // Check if the F cost of the parent is greater than + // child #1 + if (F_cost[openList[u]] >= F_cost[openList[2 * u]]) + v = 2 * u; } } - if (u!=v) { // if parent's F is > one of its children, swap them + if (u != v) { + // If parent's F is > one of its children, swap them temp = openList[u]; openList[u] = openList[v]; openList[v] = temp; - } else break; //otherwise, exit loop - } while (u!=v); //reorder the binary heap + } + else { + // Otherwise, exit loop + break; + } + } while (u != v); // Reorder the binary heap -// Check the adjacent squares. (Its "children" -- these path children -// are similar, conceptually, to the binary heap children mentioned -// above, but don't confuse them. They are different. Path children -// are portrayed in Demo 1 with grey pointers pointing toward -// their parents.) Add these adjacent child squares to the open list -// for later consideration if appropriate (see various if statements -// below). + // Check the adjacent squares. (Its "children" -- these path + // children are similar, conceptually, to the binary heap children + // mentioned above, but don't confuse them. They are different. + // Path children are portrayed in Demo 1 with grey pointers + // pointing toward their parents.) Add these adjacent child + // squares to the open list for later consideration if appropriate + // (see various if statements below). for (b = parentYval - 1; b <= parentYval + 1; b++) { for (a = parentXval - 1; a <= parentXval + 1; a++) { - // If not off the map (do this first to avoid array out-of-bounds errors) - if (a!=-1 && b!=-1 && a!=MAP_WIDTH && b!=MAP_HEIGHT) { - // If not already on the closed list (items on the closed list have - // already been considered and can now be ignored). - if (whichList[a][b]!=onClosedList) { + // If not off the map (do this first to avoid array + // out-of-bounds errors) + if (a != -1 && b != -1 && + a != MAP_WIDTH && b != MAP_HEIGHT) + { + // If not already on the closed list (items on the + // closed list have already been considered and can now + // be ignored). + if (whichList[a][b] != onClosedList) { // If not a wall/obstacle square. - if (tiledMap.getPathWalk(a, b) != NOT_WALKABLE) { + if (tiledMap.getPathWalk(a, b) != NOT_WALKABLE) { // Don't cut across corners - corner = WALKABLE; + corner = WALKABLE; if (a == parentXval-1) { if (b == parentYval-1) { - if (tiledMap.getPathWalk(parentXval-1, parentYval)==NOT_WALKABLE || tiledMap.getPathWalk(parentXval, parentYval-1)==NOT_WALKABLE) // cera slash - corner = NOT_WALKABLE; - } else if (b==parentYval+1) { - if (tiledMap.getPathWalk(parentXval, parentYval+1)==NOT_WALKABLE || tiledMap.getPathWalk(parentXval-1, parentYval)==NOT_WALKABLE) - corner = NOT_WALKABLE; + if (tiledMap.getPathWalk(parentXval - 1, parentYval) == NOT_WALKABLE || tiledMap.getPathWalk(parentXval, parentYval - 1) == NOT_WALKABLE) // cera slash + corner = NOT_WALKABLE; + } else if (b == parentYval + 1) { + if (tiledMap.getPathWalk(parentXval, parentYval + 1) == NOT_WALKABLE || tiledMap.getPathWalk(parentXval - 1, parentYval) == NOT_WALKABLE) + corner = NOT_WALKABLE; } - } else if (a == parentXval+1) { - if (b == parentYval-1) { - if (tiledMap.getPathWalk(parentXval, parentYval-1)==NOT_WALKABLE || tiledMap.getPathWalk(parentXval+1, parentYval)==NOT_WALKABLE) + } else if (a == parentXval + 1) { + if (b == parentYval - 1) { + if (tiledMap.getPathWalk(parentXval, parentYval - 1) == NOT_WALKABLE || tiledMap.getPathWalk(parentXval + 1, parentYval) == NOT_WALKABLE) + corner = NOT_WALKABLE; + } else if (b == parentYval + 1) { + if (tiledMap.getPathWalk(parentXval + 1, parentYval) == NOT_WALKABLE || tiledMap.getPathWalk(parentXval, parentYval + 1) == NOT_WALKABLE) corner = NOT_WALKABLE; - } else if (b==parentYval+1) { - if (tiledMap.getPathWalk(parentXval+1, parentYval)==NOT_WALKABLE || tiledMap.getPathWalk(parentXval, parentYval+1)==NOT_WALKABLE) - corner = NOT_WALKABLE; } } - if(corner==WALKABLE) { - // If not already on the open list, add it to the open list. - if (whichList[a][b]!=onOpenList) { - // Create a new open list item in the binary heap. - newOpenListItemID = newOpenListItemID + 1; //each new item has a unique ID # - m = numberOfOpenListItems+1; - openList[m] = newOpenListItemID;//place the new open list item (actually, its ID#) at the bottom of the heap + if (corner == WALKABLE) { + // If not already on the open list, add it + // to the open list. + if (whichList[a][b] != onOpenList) { + // Create a new open list item in the + // binary heap. + // Each new item has a unique ID # + newOpenListItemID += 1; + m = numberOfOpenListItems + 1; + // Place the new open list item + // (actually, its ID#) at the bottom of + // the heap + openList[m] = newOpenListItemID; + // Record the x and y coordinates of + // the new item openX[newOpenListItemID] = a; - openY[newOpenListItemID] = b;//record the x and y coordinates of the new item - - //Figure out its G_cost cost - if (abs(a-parentXval) == 1 && abs(b-parentYval) == 1)addedGCost = 14;//cost of going to diagonal squares - else addedGCost = 10;//cost of going to non-diagonal squares - G_cost[a][b] = G_cost[parentXval][parentYval] + addedGCost; - - //Figure out its H and F costs and parent - H_cost[openList[m]] = 10*(abs(a - e_x) + abs(b - e_y)); - F_cost[openList[m]] = G_cost[a][b] + H_cost[openList[m]]; - parentX[a][b] = parentXval ; parentY[a][b] = parentYval; - - //Move the new open list item to the proper place in the binary heap. - //Starting at the bottom, successively compare to parent items, - //swapping as needed until the item finds its place in the heap - //or bubbles all the way to the top (if it has the lowest F cost). - while(m!=1) { // While item hasn't bubbled to the top (m=1) - //Check if child's F cost is < parent's F cost. If so, swap them. - if(F_cost[openList[m]]<=F_cost[openList[m/2]]) { - temp = openList[m/2]; - openList[m/2] = openList[m]; + openY[newOpenListItemID] = b; + + // Figure out its G_cost cost + if (abs(a - parentXval) == 1 && + abs(b - parentYval) == 1) + { + // Cost of going to diagonal + // squares. + addedGCost = 14; + } + else { + // Cost of going to non-diagonal + // squares. + addedGCost = 10; + } + + G_cost[a][b] = + G_cost[parentXval][parentYval] + + addedGCost; + + // Figure out its H and F costs and + // parent. + H_cost[openList[m]] = + 10 * (abs(a - e_x) + abs(b - e_y)); + F_cost[openList[m]] = + G_cost[a][b] + H_cost[openList[m]]; + parentX[a][b] = parentXval; + parentY[a][b] = parentYval; + + // Move the new open list item to the + // proper place in the binary heap. + // Starting at the bottom, successively + // compare to parent items, swapping as + // needed until the item finds its + // place in the heap or bubbles all the + // way to the top (if it has the lowest + // F cost). + + // While item hasn't bubbled to the + // top (m = 1) + while (m != 1) { + // Check if child's F cost is < + // parent's F cost. If so, swap + // them. + if (F_cost[openList[m]] <= + F_cost[openList[m / 2]]) + { + temp = openList[m / 2]; + openList[m / 2] = openList[m]; openList[m] = temp; - m = m/2; - } else break; - } - - numberOfOpenListItems = numberOfOpenListItems+1;//add one to the number of items in the heap - //Change whichList to show that the new item is on the open list. + m = m / 2; + } + else { + break; + } + } + + // Add one to the number of items in + // the heap. + numberOfOpenListItems += 1; + // Change whichList to show that the + // new item is on the open list. whichList[a][b] = onOpenList; - } else { // If whichList(a,b) = onOpenList - // If adjacent cell is already on the open list, check to see if this - // path to that cell from the starting location is a better one. - // If so, change the parent of the cell and its G_cost and F costs. - //Figure out the G_cost cost of this possible new path - if(abs(a-parentXval)==1 && abs(b-parentYval)==1)addedGCost = 14;//cost of going to diagonal tiles - else addedGCost = 10;//cost of going to non-diagonal tiles - - tempG = G_cost[parentXval][parentYval] + addedGCost; - - // If this path is shorter (G_cost cost is lower) then change - // the parent cell, G_cost cost and F cost. - if(tempGnext = new PATH_NODE( + path_bank[pathLocation * 2 - 2], + path_bank[pathLocation * 2 - 1]); + if (temp->next == NULL) throw "Unable to create path node"; + temp = temp->next; + pathLocation++; + } + if (temp != NULL) { + temp->next = new PATH_NODE(e_x, e_y); + } + else { + throw "Null reference"; + } - PATH_NODE *ret = NULL, *temp = NULL; - pathLocation = 1; - ret = new PATH_NODE(s_x, s_y); - temp = ret; - //alert(stringa,"","","","",0,0); - while(pathLocationnext = new PATH_NODE( - path_bank[pathLocation * 2 - 2], - path_bank[pathLocation * 2 - 1]); - if(temp->next==NULL) throw "Unable to create path node"; - temp = temp->next; - pathLocation++; + return ret; } - if(temp!=NULL)temp->next = new PATH_NODE(e_x, e_y); - else throw "Null reference"; - return ret; - } - return NULL; // Path not found + // Path not found + return NULL; } -/** Read the path data */ -void ReadPath(int pathfinderID) { - //If a path exists, read the path data - // from the pathbank. - pathLocation = 1; //set pathLocation to 1st step +void ReadPath(int pathfinderID) +{ + // If a path exists, read the path data from the pathbank. + // Set pathLocation to 1st step + pathLocation = 1; while (pathLocation