A* Search Algorithm | Board Infinity

Introduction

A* is a popular pathfinding and graph traversal technique that is pronounced "A star." The programme effectively creates a path on the network that can be traversed by people.

One of the finest and most often used methods for path discovery and graph traversals is the A* algorithm.
This technique is often used in games and online maps to effectively discover the shortest distance.
It resembles a best-first search algorithm in many ways.

**Working of A* algorithm**

A* also constructs a lowest-cost path tree from the start node to the target node, much like Dijkstra. The fact that A* utilizes a function f(n)f(n) for each node to estimate the overall cost of a path involving that node sets it apart from other search engines and makes it superior for many queries.

Using this function, A* extends the pathways that are already less expensive: f(n)=g(n)+h(n),f(n)=g(n)+h(n),where:

Total estimated cost of route across node nn is given by f(n)f(n).
g(n)g(n) is the cost to go to node nn.
Estimated cost from nn to goal is h(n)h(n).

Since this is the heuristic portion of the cost function, it is somewhat of a guess.

Steps:

Create an OPEN list. OPEN is composed of just one node at first, the start node S.
If the list is empty, give an error message and quit.
The node n with the least f(n) value should be moved from the list OPEN to the list CLOSED. Return success and leave if node n represents the desired state.
Increase node n.
Trace the route from any successor to n to S, and if it is the destination node, return success and the solution. If not, proceed to the next step.
Apply the evaluation function f to the node for each successor node. Add the node to OPEN if it hasn't already been there.
Repeat from Step 2

Code:

#include <list>
#include <algorithm>
#include <iostream>

using namespace std;
class point {
public:
point( int a = 0, int b = 0 ) { x = a; y = b; }
bool operator ==( const point& o ) { return o.x == x && o.y == y; }
point operator +( const point& o ) { return point( o.x + x, o.y + y ); }
int x, y;
};

class map {
public:
map() {
char t[8][8] = {
{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 1, 0}, {0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}
};
w = h = 8;
for( int r = 0; r < h; r++ )
for( int s = 0; s < w; s++ )
m[s][r] = t[r][s];
}
int operator() ( int x, int y ) { return m[x][y]; }
char m[8][8];
int w, h;
};

class node {
public:
bool operator == (const node& o ) { return pos == o.pos; }
bool operator == (const point& o ) { return pos == o; }
bool operator < (const node& o ) { return dist + cost < o.dist + o.cost; }
point pos, parent;
int dist, cost;
};

class aStar {
public:
aStar() {
neighbours[0] = point( -1, -1 ); neighbours[1] = point( 1, -1 );
neighbours[2] = point( -1, 1 ); neighbours[3] = point( 1, 1 );
neighbours[4] = point( 0, -1 ); neighbours[5] = point( -1, 0 );
neighbours[6] = point( 0, 1 ); neighbours[7] = point( 1, 0 );
}

int calcDist( point& p ){
// need a better heuristic
int x = end.x - p.x, y = end.y - p.y;
return( x * x + y * y );
}

bool isValid( point& p ) {
return ( p.x >-1 && p.y > -1 && p.x < m.w && p.y < m.h );
}

bool existPoint( point& p, int cost ) {
list<node>::iterator i;
i = find( closed.begin(), closed.end(), p );
if( i != closed.end() ) {
if( ( *i ).cost + ( *i ).dist < cost ) return true;
else { closed.erase( i ); return false; }
}
i = find( open.begin(), open.end(), p );
if( i != open.end() ) {
if( ( *i ).cost + ( *i ).dist < cost ) return true;
else { open.erase( i ); return false; }
}
return false;
}

bool fillOpen( node& n ) {
int stepCost, nc, dist;
point neighbour;

for( int x = 0; x < 8; x++ ) {
// one can make diagonals have different cost
stepCost = x < 4 ? 1 : 1;
neighbour = n.pos + neighbours[x];
if( neighbour == end ) return true;

if( isValid( neighbour ) && m( neighbour.x, neighbour.y ) != 1 ) {
nc = stepCost + n.cost;
dist = calcDist( neighbour );
if( !existPoint( neighbour, nc + dist ) ) {
node m;
m.cost = nc; m.dist = dist;
m.pos = neighbour;
m.parent = n.pos;
open.push_back( m );
}
}
}
return false;
}

bool search( point& s, point& e, map& mp ) {
node n; end = e; start = s; m = mp;
n.cost = 0; n.pos = s; n.parent = 0; n.dist = calcDist( s );
open.push_back( n );
while( !open.empty() ) {
//open.sort();
node n = open.front();
open.pop_front();
closed.push_back( n );
if( fillOpen( n ) ) return true;
}
return false;
}

int path( list<point>& path ) {
path.push_front( end );
int cost = 1 + closed.back().cost;
path.push_front( closed.back().pos );
point parent = closed.back().parent;

for( list<node>::reverse_iterator i = closed.rbegin(); i != closed.rend(); i++ ) {
if( ( *i ).pos == parent && !( ( *i ).pos == start ) ) {
path.push_front( ( *i ).pos );
parent = ( *i ).parent;
}
}
path.push_front( start );
return cost;
}

map m; point end, start;
point neighbours[8];
list<node> open;
list<node> closed;
};

int main( int argc, char* argv[] ) {
map m;
point s, e( 7, 7 );
aStar as;

if( as.search( s, e, m ) ) {
list<point> path;
int c = as.path( path );
for( int y = -1; y < 9; y++ ) {
for( int x = -1; x < 9; x++ ) {
if( x < 0 || y < 0 || x > 7 || y > 7 || m( x, y ) == 1 )
cout << char(0xdb);
else {
if( find( path.begin(), path.end(), point( x, y ) )!= path.end() )
cout << "x";
else cout << ".";
}
}
cout << "\n";
}

cout << "\nPath cost " << c << ": ";
for( list<point>::iterator i = path.begin(); i != path.end(); i++ ) {
cout<< "(" << ( *i ).x << ", " << ( *i ).y << ") ";
}
}
cout << "\n\n";
return 0;
}

write your code here: Coding Playground

Conclusion

A-star (A*) is a powerful artificial intelligence algorithm with many applications. But it is only as effective as its heuristic function. A* is the most often used pathfinding algorithm because of its reasonable flexibility. It has found use in a variety of software systems, including game creation where characters must navigate through difficult terrain and obstacles to get to the user, as well as machine learning and search optimization.