//=========================================================================== // MAZE // USING THE A-STAR SOLUTION ALGORITHM written by Timothy Ford // Modified by Nick Gessler // // //=========================================================================== #include #pragma hdrstop #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- //=========================================================================== // NON-BORLAND CODE //=========================================================================== /*****A* algorithm***** for the grid, integer values as follows: 0 = wall (Black) 1 = open (White) 2 = start (Red) 3 = end (Red) 4 = path (Cyan) ***********************/ #include #include #include #include #include #include using namespace std; //=========================================================================== // VARIABLE AND CLASS DECLARATIONS //=========================================================================== // Globals #define GRID_SIZE 60 #define TS 10 int grid[GRID_SIZE][GRID_SIZE]; // Function Prototypes void renderGrid(); void setSE(); void makeGrid(); void resetGrid(); enum { wallTile, openTile, startTile, endTile, pathTile, }; //-------------------------------------- Class Declaration and Instantiation class Astar { public: // Public Member Variables enum { SEARCHING, SUCCEEDED, FAILED, }; // Node class (class that has x, y, heuristic and parent pointer values class Node { public: Node() { parent = NULL; g = 0.0; h = 0.0; f = 0.0; } /*****getDistanceEstimate()***** *TAKES: int endx: x value of the endNode * int endy: y value of the endNode *RETURNS: float: the value of the distance equation squared *PURPOSE: to calculate and return the distance from this *node to the endNode ********************************/ float getDistanceEstimate( int endx, int endy ) { float dx = (float)( (float)x - (float)endx ); float dy = (float)( (float)y - (float)endy ); return ((dx*dx) + (dy*dy)); } /*****isSameState()***** *TAKES: Node *rhs: node to check x,y values *RETURNS: bool: is this the same state? *PURPOSE: true if the passed node has the same *x and y values as this node ************************/ bool isSameState( Node *rhs ) { if( x == rhs -> x && y == rhs -> y ) return true; else return false; } Node *parent; float g; // cost of this node + its parents float h; // heuristic estimate float f; // g + h int x, y; int type; }; class HeapComparison { public: /*****operator()***** *TAKES: Node *x: first node for comparison * Node *y: second node for comparison *RETURNS: bool: does x have higher f than y? *PURPOSE: this function is passed to the list sorting *functions, pop_heap, push_heap, and sort_heap *this function dictates the order of the list *the heap functions are an A* optimization *********************/ bool operator() ( const Node *x, const Node *y ) const { return x->f > y->f; } }; //---------------------------------------------------------- Member Functions Astar() { // Constructor } ~Astar() { // Destructor clearLists(); } //Reset function void clearLists() { OPEN.clear(); CLOSED.clear(); SUCCESSORS.clear(); } /*****getCoords()***** *TAKES: int xCoord: x coordinate for the desired grid value * int yCoord: y coordinate for the desired grid value *RETURNS: int: the tile value of grid[x][y] *PURPOSE: to return the tile value at coordinates xCoord, yCoord *Values that are out of bounds (bigger than size of grid) ************************/ int getCoords( int xCoord, int yCoord ) { if( xCoord < 0 || xCoord >= GRID_SIZE || yCoord < 0 || yCoord >= GRID_SIZE ) return wallTile; return grid[xCoord][yCoord]; } /*****setStartEnd()***** *TAKES: int x: x value of startNode * int y: y value of startNode * int q: x value of endNode * int r: y value of endNode *RETURNS: nothing *PURPOSE: initializes the startNode and endNode ************************/ void setStartEnd( int x, int y, int q, int r) { startNode = new Node; endNode = new Node; //Initialize the start and ending nodes startNode -> x = x; startNode -> y = y; startNode -> type = startTile; endNode -> x = q; endNode -> y = r; endNode -> type = endTile; //Set state of the search algorithm currentState = SEARCHING; //Initialize the heuristic variables for the start state startNode->g = 0; startNode->h = startNode->getDistanceEstimate( endNode -> x, endNode ->y ); startNode->f = startNode->g + startNode->h; //Starting node has no parents startNode->parent = NULL; //Push starting node onto OPEN list OPEN.push_back( startNode ); // Sort elements in heap push_heap( OPEN.begin(), OPEN.end(), HeapComparison() ); // Initialise counter for search steps stepCounter = 0; } /*****Search()***** *TAKES: nothing *RETURNS: unsigned int: corresponds to a particular state * SUCCEEDED: found the endNode * FAILED: didn't find the endNode * SEARCHING: still searching, keep calling trying *PURPOSE: A* algorithm. Starts at the lowest f valued node on *the OPEN list (first iteration is always the startNode) and *stores it as thisNode. The OPEN list contains every node that *hasn't been expanded, ie. has not had successors generated for *it The CLOSED list contains every node that has been expanded, *Search() then generates all the 0 to 8 successors of thisNode *and iterates through them. Any successor that is found to meet *both of the following conditions is placed in the OPEN list *and it's parent node is stored. * 1) If this successor is already a node on the OPEN list, and * the 'f' value of the node on the OPEN list is higher * than that of the successor. Consequentially, this * successor was reached faster (from a different direction) * than it was when it was first put on the OPEN list. * This successor must be updated on the OPEN list with * the lower 'f' value. * 2) If this successor is already a node on the CLOSED list, and * the 'f' value of the node on the CLOSED list is higher * than that of the successor. Consequentially, this * successor was reached faster (from a different direction) * than it was when it was first put on the CLOSED list. * Because this successor has already been expanded (it * is on the CLOSED list) and has a lower 'f' value * than its similar state on the CLOSED list, this * successor must be removed from the CLOSED list. * If this successor meets both criteria, it will be * placed on the OPEN list and expanded again. *If this successor is neither on the OPEN nor on the CLOSED lists, it *will be put on the OPEN list and have it's parent node stored. After *Search() has stored every worthwhile successor (those that have met *the two criteria), it will move the successors' parent onto the CLOSED *list. Search should then be called again, where it will expand the Node *on the OPEN list with the lowest 'f' value. If a node taken off the OPEN *list is the endNode, Search() will set the currentState flag to SUCCEEDED *and terminate the subroutine. If the OPEN list is empty, there are no *more states to expand, and therefore no way to get to the endNode. *******************/ unsigned int Search() { //Check to see if the search succeeded or failed if( ( currentState == SUCCEEDED) || ( currentState == FAILED ) ) return currentState; //The search fails if the OPEN list is empty (no more states to search) if( OPEN.empty() ) { currentState = FAILED; return currentState; } // Incremement stepCounter stepCounter ++; //Get the node with the lowest f value (list is always sorted in order //of f values) Node *thisNode = OPEN.front(); pop_heap( OPEN.begin(), OPEN.end(), HeapComparison() ); OPEN.pop_back(); // Check for the end state if( thisNode -> type == endTile ) { //Store the parent of end node so we can move back up the tree endNode->parent = thisNode->parent; //Make sure startNode isn't equal to endNode if( thisNode != startNode ) { //delete thisNode; delete thisNode; } currentState = SUCCEEDED; return currentState; } //End state not found else { //Generate successors for the node in question //Start by clearing the successor list of the last "thisNode" SUCCESSORS.clear(); //Push successors of thisNode into SUCCESSORS list. Node * newNode; //Store x and y coordinates of thisNode's parent so it doesn't go backwards //Make a case for the startNode (it has no parent) int parentX = -1; int parentY = -1; //Check to see that thisNode has a parent (ie, its not the start node) if( thisNode -> parent ) { parentX = thisNode -> parent -> x; parentY = thisNode -> parent -> y; } //Create successor by scanning around thisNode's x,y coords //Case: Left of thisNode if( (getCoords( (thisNode -> x)-1, (thisNode -> y) ) != wallTile) && !((parentX == (thisNode -> x)-1) && (parentY == (thisNode -> y))) ) { newNode = new Node; newNode -> x = (thisNode -> x)-1; newNode -> y = thisNode -> y; newNode -> type = getCoords( (thisNode -> x)-1, (thisNode -> y) ); SUCCESSORS.push_back( newNode ); } //Case: Right of thisNode if( (getCoords( (thisNode -> x)+1, (thisNode -> y) ) != wallTile) && !((parentX == (thisNode -> x)+1) && (parentY == (thisNode -> y))) ) { newNode = new Node; newNode -> x = (thisNode -> x)+1; newNode -> y = thisNode -> y; newNode -> type = getCoords( (thisNode -> x)+1, (thisNode -> y) ); SUCCESSORS.push_back( newNode ); } //Case: Upper Left of thisNode if( (getCoords( (thisNode -> x)-1, (thisNode -> y)-1 ) != wallTile) && !((parentX == (thisNode -> x)-1) && (parentY == (thisNode -> y)-1)) ) { newNode = new Node; newNode -> x = (thisNode -> x)-1; newNode -> y = (thisNode -> y)-1; newNode -> type = getCoords( (thisNode -> x)-1, (thisNode -> y)-1 ); SUCCESSORS.push_back( newNode ); } //Case: Above thisNode if( (getCoords( (thisNode -> x), (thisNode -> y)-1 ) != wallTile) && !((parentX == (thisNode -> x)) && (parentY == (thisNode -> y)-1)) ) { newNode = new Node; newNode -> x = thisNode -> x; newNode -> y = (thisNode -> y)-1; newNode -> type = getCoords( (thisNode -> x), (thisNode -> y)-1 ); SUCCESSORS.push_back( newNode ); } //Case: Upper Right of thisNode if( (getCoords( (thisNode -> x)+1, (thisNode -> y)-1 ) != wallTile) && !((parentX == (thisNode -> x)+1) && (parentY == (thisNode -> y)-1)) ) { newNode = new Node; newNode -> x = (thisNode -> x)+1; newNode -> y = (thisNode -> y)-1; newNode -> type = getCoords( (thisNode -> x)+1, (thisNode -> y)-1 ); SUCCESSORS.push_back( newNode ); } //Case: Lower Left of thisNode if( (getCoords( (thisNode -> x)-1, (thisNode -> y)+1 ) != wallTile) && !((parentX == (thisNode -> x)-1) && (parentY == (thisNode -> y)+1)) ) { newNode = new Node; newNode -> x = (thisNode -> x)-1; newNode -> y = (thisNode -> y)+1; newNode -> type = getCoords( (thisNode -> x)-1, (thisNode -> y)+1 ); SUCCESSORS.push_back( newNode ); } //Case: Below thisNode if( (getCoords( (thisNode -> x), (thisNode -> y)+1 ) != wallTile) && !((parentX == (thisNode -> x)) && (parentY == (thisNode -> y)+1)) ) { newNode = new Node; newNode -> x = thisNode -> x; newNode -> y = (thisNode -> y)+1; newNode -> type = getCoords( (thisNode -> x), (thisNode -> y)+1 ); SUCCESSORS.push_back( newNode ); } //Case: Lower Right of thisNode if( (getCoords( (thisNode -> x)+1, (thisNode -> y)+1 ) != wallTile) && !((parentX == (thisNode -> x)+1) && (parentY == (thisNode -> y)+1)) ) { newNode = new Node; newNode -> x = (thisNode -> x)+1; newNode -> y = (thisNode -> y)+1; newNode -> type = getCoords( (thisNode -> x)+1, (thisNode -> y)+1 ); SUCCESSORS.push_back( newNode ); } //Iterate through all the successors of thisNode for( vector< Node * >::iterator successor = SUCCESSORS.begin(); successor != SUCCESSORS.end(); successor ++ ) { //Store the g value for this successor in a temporary variable float newg = thisNode->g + 1.0; //Check to see if this successor is on the open or closed lists vector< Node * >::iterator openlist; for( openlist = OPEN.begin(); openlist != OPEN.end(); openlist ++ ) { if( (*openlist)->isSameState( (*successor) ) ) { break; } } if( openlist != OPEN.end() ) { //This successor state is on the OPEN list //Now check to see which has the lower g value if( (*openlist) -> g <= newg ) { delete (*successor); //the one on OPEN is cheaper than this one //so trash this successor and continue continue; } } vector< Node * >::iterator closedlist; for( closedlist = CLOSED.begin(); closedlist != CLOSED.end(); closedlist ++ ) { if( (*closedlist) -> isSameState( (*successor) ) ) { break; } } if( closedlist != CLOSED.end() ) { //This successor state is on the OPEN list //Now check to see which has the lower g value if( (*closedlist) -> g <= newg ) { //the one on CLOSED is cheaper than this one //so trash this successor and continue delete (*successor); continue; } } //This successor is fewer steps (g's value) away from the start //Than any occurance on the open or closed list //save parent so we can back track once (if?) we reach the end (*successor) -> parent = thisNode; //Store our temporary g value (*successor)->g = newg; //find the distance (squared) from this point to the endnode (*successor)->h = (*successor) -> getDistanceEstimate( endNode -> x, endNode -> y ); //Get the final heuristic value f (*successor)->f = (*successor) -> g + (*successor) -> h; //Remove successor from CLOSED if it was on it and had lower g if( closedlist != CLOSED.end() ) { //remove this successor from CLOSED so we don't try to compare it //again the next time around delete (*closedlist); CLOSED.erase( closedlist ); } //Update old version of this successor node on OPEN list if( openlist != OPEN.end() ) { delete (*openlist); OPEN.erase( openlist ); //resort the heap sort_heap( OPEN.begin(), OPEN.end(), HeapComparison() ); } //Put this successor (with newest values) into the OPEN list OPEN.push_back( (*successor) ); //Sort the OPEN list push_heap( OPEN.begin(), OPEN.end(), HeapComparison() ); } //Push thisNode onto CLOSED, it has been expanded CLOSED.push_back( thisNode ); } //End of the else, the currentState should only be unsuccessful at this point return currentState; } //Function that moves from the endNode to the startNode and changes the path //From '.' to 'X' void writePathToGrid() { if( currentState == SUCCEEDED ) { //Iterate back to the startNode from the endNode Node *nodeChild = endNode; Node *nodeParent = endNode->parent; do { if( nodeParent != startNode ) { nodeParent -> type = pathTile; grid[nodeParent->x][nodeParent->y] = pathTile; } nodeChild = nodeParent; nodeParent = nodeParent->parent; } while( nodeChild != startNode ); } return; } private: //OPEN list explained in comments before Search() vector OPEN; //CLOSED list explained in comments before Search() vector CLOSED; //SUCCESSORS is a list of successive nodes branching out from //any particular node. It is generated almost every iteration of SEARCH vector SUCCESSORS; unsigned int currentState; int stepCounter; //Start and end state pointers Node *startNode; Node *endNode; } aStarSearch; //=========================================================================== // FUNCTIONS //=========================================================================== //--------------------------------------------------------------- Render Grid void renderGrid() { int east, south; for( east = 0; east < GRID_SIZE; ++east ) { for( south = 0; south < GRID_SIZE; ++south ) { if( grid[east][south] == wallTile ) { Form1->Canvas->Pen->Color=clBlack; Form1->Canvas->Brush->Color=clBlack; Form1->Canvas->Rectangle (east*TS+20,south*TS+20,east*TS+TS+20,south*TS+TS+20); } else if( grid[east][south] == openTile ) { Form1->Canvas->Pen->Color=clWhite; Form1->Canvas->Brush->Color=clWhite; Form1->Canvas->Rectangle (east*TS+20,south*TS+20,east*TS+TS+20,south*TS+TS+20); } else if( grid[east][south] == startTile ) { Form1->Canvas->Pen->Color=clRed; Form1->Canvas->Brush->Color=clRed; Form1->Canvas->Rectangle (east*TS+20,south*TS+20,east*TS+TS+20,south*TS+TS+20); } else if( grid[east][south] == endTile ) { Form1->Canvas->Pen->Color=clRed; Form1->Canvas->Brush->Color=clRed; Form1->Canvas->Rectangle (east*TS+20,south*TS+20,east*TS+TS+20,south*TS+TS+20); } else if( grid[east][south] == pathTile ) { Form1->Canvas->Pen->Color=clAqua; Form1->Canvas->Brush->Color=clAqua; Form1->Canvas->Rectangle (east*TS+20,south*TS+20,east*TS+TS+20,south*TS+TS+20); } } } return; } //------------------------------------------------ Randomly generates a grid void makeGrid() { int i; int j; for( i = 0; i < GRID_SIZE; ++i ) { // Generate the walls and open paths for( j = 0; j < GRID_SIZE; ++j ) { grid[i][j] = random(2); } } return; } //-------------------------------------------------------- New Start and End void setSE() { unsigned int x, y, q, r; Form1->EditStatus->Text = " Waiting"; resetGrid(); do { // Set Start point x = (unsigned)(random(GRID_SIZE)); y = (unsigned)(random(GRID_SIZE)); } while( grid[x][y] == wallTile ); grid[x][y] = startTile; do { // Set End point q = (unsigned)(random(GRID_SIZE)); r = (unsigned)(random(GRID_SIZE)); } while( grid[q][r] == startTile || grid[q][r] == wallTile ); grid[q][r] = endTile; aStarSearch.setStartEnd( x, y, q, r ); return; } //--------------------------------------------------------------- Reset Grid void resetGrid() { int i, j; for( i = 0; i < GRID_SIZE; ++i ) { for( j = 0; j < GRID_SIZE; ++j ) { if( grid[i][j] > 1 ) grid[i][j] = openTile; } } return; } //------------------------------------------------------- Find Shortest Path void findQuickestPath() { unsigned int currentSearchState; Form1->EditStatus->Text = " Thinking"; Application->ProcessMessages(); do { currentSearchState = aStarSearch.Search(); } while( currentSearchState == Astar::SEARCHING ); //Search succeeded, print grid with path if ( currentSearchState == Astar::SUCCEEDED ) { aStarSearch.writePathToGrid(); renderGrid(); Form1->EditStatus->Text = " Success"; } // or search failed else { renderGrid(); //Print the grid without writing the path 'X's to it Form1->EditStatus->Text = " Impossible"; } aStarSearch.clearLists(); } //---------------------------------------------------------------- Initialize void initialize() { randomize(); makeGrid(); // Create the grid setSE(); // Set the starting and ending points renderGrid(); Form1->EditStatus->Text = " Waiting"; } //=========================================================================== // EVENT HANDLERS //=========================================================================== //------------------------------------------------------- Generate Map Button void __fastcall TForm1::ButtonGenerateMapClick(TObject *Sender) { initialize(); } //---------------------------------------------------------- Find Path Button void __fastcall TForm1::ButtonFindPathClick(TObject *Sender) { findQuickestPath(); } //------------------------------------------------------ New Start End Button void __fastcall TForm1::ButtonNewSEClick(TObject *Sender) { setSE(); renderGrid(); } //=========================================================================== // THAT'S ALL FOLKS //===========================================================================