### A* algorithm in c++!

This is not an algorithm to get you an A* in your GCSE’s. Don’t be so silly. A* (Astar) is a path finding algorithm used to find…. paths.
It is very similar to Dijkstra’s algorithm, if you know what that is. I found a great explanation here: http://www.policyalmanac.org/games/aStarTutorial.htm , so I’m not just going to recreate that in a lesser form without diagrams. If you want to understand it, go check that out.

The following source code  makes no attempt at clarity or efficiency. Nor does it claim to make good use of spelling. It does, however, work. It also has no formatting thanks to wordpress. But perhaps if you cut and paste it into a c++ program, it might get sorted for you. Who knows.

It first randomly generates a small world, which is filled with walls (0’s) and empty space ( ). This is seeded the same everytime, but could be changed with a call to time(0) (#include<time.h> I *think*). The A* algorithm is the called to find a route from the top left to the bottom right.

Next, the end of the A* is printed. Start in the bottom right, and just go in the direction indicated (u for up, r for right, l for left, d for down). Keep doing this until you reach the starting position. Or not if it has failed, which is possible!

Lastly I get the computer to compute the route, and print it out with little @ symbols. Lovely.

SOURCE CODE:

Astar– This is a word document!

#include <iostream>
#include <stdlib.h>
using namespace std;

enum {OPEN, CLOSED, NOTCONSIDERED};
enum {WALL, EMPTY};
enum {NONE,UP,DOWN,LEFT,RIGHT,PATH};

const int worldx = 20, worldy = 20;
int world[worldx][worldy], worldF[worldx][worldy], worldG[worldx][worldy], worldH[worldx][worldy], worldopen[worldx][worldy], worldparent[worldx][worldy];
int personx = 0, persony=0, consideringx=0, consideringy=0, targetx = worldx-1, targety = worldy-1;
void printworld(void)
{
for(int i = 0; i<worldx; i++)
{
for(int j = 0; j<worldy; j++)
{
if(i!=persony || j!= personx)
{
if(world[j][i] == 0)
{
cout<<world[j][i];
}
else
{
cout<<” “;
}
}
else
{
cout<<“\$”;
}
}
cout<<“\n”;
}
cout<<“\n\n\n”;
}

void printworldparent(void)
{
for(int i = 0; i<worldx; i++)
{
for(int j = 0; j<worldy; j++)
{
if(worldparent[j][i] == UP)
{
cout<<‘u’;
}
if(worldparent[j][i] == DOWN)
{
cout<<‘d’;
}
if(worldparent[j][i] == LEFT)
{
cout<<‘l’;
}
if(worldparent[j][i] == RIGHT)
{
cout<<‘r’;
}
if(worldparent[j][i] == NONE)
{
cout<<‘.’;
}
if(worldparent[j][i] == PATH)
{
cout<<‘@’;
}
}
cout<<“\n”;
}
cout<<“\n\n\n”;
}

int main(void)
{
bool done = 0;
srand(1);

for(int i = 0; i<worldx; i++)
{
for(int j = 0; j<worldy; j++)
{
worldG[i][j] = 999999; //BIG NUMBER!
worldparent[i][j] = NONE;
worldopen[i][j] = NOTCONSIDERED;
world[i][j] = rand()%4;
if(world[i][j] >=EMPTY)
{
world[i][j] = EMPTY;
}
}
}
printworld();

/////////////////
//A* goes here!//
/////////////////

worldopen[consideringx][consideringy] = OPEN;
if(consideringx-1>=0 && world[consideringx-1][consideringy] != WALL)
{
worldopen[consideringx-1][consideringy] = OPEN;
worldparent[consideringx-1][consideringy] = RIGHT;
}
if(consideringx+1<worldx && world[consideringx+1][consideringy] != WALL)
{
worldopen[consideringx+1][consideringy] = OPEN;
worldparent[consideringx+1][consideringy] = LEFT;
}
if(consideringy-1>=0 && world[consideringx][consideringy-1] != WALL)
{
worldopen[consideringx][consideringy-1] = OPEN;
worldparent[consideringx][consideringy-1] = DOWN;
}
if(consideringx+1<worldy && world[consideringx][consideringy+1] != WALL)
{
worldopen[consideringx][consideringy+1] = OPEN;
worldparent[consideringx][consideringy+1] = UP;
}
worldopen[consideringx][consideringy] = CLOSED;
for(int i = -1; i<2; i+=2)
{
if(consideringx+i<worldx && consideringx+i>=0 && worldopen[consideringx+i][consideringy] == OPEN)
{
worldG[consideringx+i][consideringy] = 1;
worldH[consideringx+i][consideringy] = abs(consideringx+i – targetx) + abs(consideringy – targety);
worldF[consideringx+i][consideringy] = worldG[consideringx+i][consideringy] + worldH[consideringx+i][consideringy];

}
}
for(int i = -1; i<2; i+=2)
{
if(consideringy+i<worldy && consideringy+i>=0 && worldopen[consideringx][consideringy+i] == OPEN)
{
worldG[consideringx][consideringy+i] = 1;
worldH[consideringx][consideringy+i] = abs(consideringx – targetx) + abs(consideringy+i – targety);
worldF[consideringx][consideringy+i] = worldG[consideringx][consideringy+i] + worldH[consideringx][consideringy+i];

}
}
///////////////////////////////////////////////////////////////////////
for(int counter = 0; counter<1000; counter++)
{
int biggestsofar = 1000000; //larger number!!
for(int i = 0; i<worldx; i++)
{
for(int j =0; j<worldy; j++)
{
if(worldF[i][j] <= biggestsofar && worldopen[i][j] == OPEN)
{
biggestsofar = worldF[i][j];
consideringx = i;
consideringy = j;
}
}
}

worldopen[consideringx][consideringy] = CLOSED;

for(int i = -1; i<2; i+=2)
{
if(consideringx+i<worldx && consideringx+i>=0 && worldopen[consideringx+i][consideringy] != CLOSED)
{
if(worldopen[consideringx+i][consideringy] == NOTCONSIDERED && world[consideringx+i][consideringy] == EMPTY)
{
worldopen[consideringx+i][consideringy] = OPEN;
}
if(worldopen[consideringx+i][consideringy] == OPEN)
{
if(worldG[consideringx+i][consideringy] > worldG[consideringx][consideringy]+1)
{
worldG[consideringx+i][consideringy] = worldG[consideringx][consideringy]+1;
worldH[consideringx+i][consideringy] = abs(consideringx+i – targetx) + abs(consideringy – targety);
worldF[consideringx+i][consideringy] = worldG[consideringx+i][consideringy] + worldH[consideringx+i][consideringy];
if(i<0)
{
worldparent[consideringx+i][consideringy] = RIGHT;
}
if(i>0)
{
worldparent[consideringx+i][consideringy] = LEFT;
}
}
}
}
}
for(int i = -1; i<2; i+=2)
{
if(consideringy+i<worldx && consideringy+i>=0 && worldopen[consideringx][consideringy+i] != CLOSED)
{
if(worldopen[consideringx][consideringy+i] == NOTCONSIDERED && world[consideringx][consideringy+i] == EMPTY)
{
worldopen[consideringx][consideringy+i] = OPEN;//yes???
}
if(worldopen[consideringx][consideringy+i] == OPEN)
{
if(worldG[consideringx][consideringy+i] > worldG[consideringx][consideringy]+1)
{
worldG[consideringx][consideringy+i] = worldG[consideringx][consideringy]+1;
worldH[consideringx][consideringy+i] = abs(consideringx – targetx) + abs(consideringy+i – targety);
worldF[consideringx][consideringy+i] = worldG[consideringx][consideringy+i] + worldH[consideringx][consideringy+i];
if(i<0)
{
worldparent[consideringx][consideringy+i] = DOWN;
}
if(i>0)
{
worldparent[consideringx][consideringy+i] = UP;
}
}
}
}
}
for(int i = 0; i<worldx; i++)
{
for(int j =0; j<worldy; j++)
{
if(worldopen[i][j] == OPEN && i == targetx && j == targety)
{
done = 1;
}
}
}
if(done)
{
break;
}
}
///////////////////////////////////////////////////////////////////////
printworldparent();

////////////FIND ROUTE BACK/////
consideringx = targetx; consideringy = targety;

for(int counter = 0; counter<worldx*worldy; counter++)
{
if(worldparent[consideringx][consideringy] == UP)
{
worldparent[consideringx][consideringy] = PATH;
if(consideringy – 1 >=0)
{
consideringy -= 1;
}
}
if(worldparent[consideringx][consideringy] == DOWN)
{
worldparent[consideringx][consideringy] = PATH;
if(consideringy + 1 <worldy)
{
consideringy += 1;
}
}
if(worldparent[consideringx][consideringy] == RIGHT)
{
worldparent[consideringx][consideringy] = PATH;
if(consideringx + 1 <worldx)
{
consideringx += 1;
}
}
if(worldparent[consideringx][consideringy] == LEFT)
{
worldparent[consideringx][consideringy] = PATH;
if(consideringx – 1 >=0)
{
consideringx -= 1;
}
}
if(consideringx == personx && consideringy == persony)
{
break;
}
}
printworldparent();

//make sure the window stays open

int exit;
cin>>exit;

return 0;
}