Implemetation of Astar

Can someone please go through this?

#include <iostream>

#include <string>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <list>

#include <set>

#include <cmath>

#include <cstring>

#include <stdio.h>

#include <string.h>

#include <sstream>

#include <stdlib.h>

#include <vector>

#include <iomanip>

#include <ctime>

using namespace std;

#define SIZE    10

int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};

int sx,sy,fx,fy,f_cost_cell[100][100];

int distance(int x,int y,int p,int q);

int heuristic(int x,int y);

static int maze[SIZE][SIZE];

struct Vector
{
std::pair<int, int> er;
Vector(int e_ = 0, int r_ = 0) : er(std::make_pair(e_, r_)) {}
bool operator<(const Vector& rhs) const
{ return er < rhs.er; }
};

struct op

{

int x,y,cost,h,total_cost;

op(int _x,int _y,int _cost)

{

x=_x;y=_y;cost=_cost;

h=heuristic(x,y);

total_cost=cost+h;

}

bool operator<(const op &b)const

{

}

};

int distance(int x,int y,int p,int q)

{if(maze[p][q]>maze[x][y]) return 3;

if(maze[p][q]==maze[x][y]) return 2;

return 1;

}

int heuristic(int x,int y)

{

return abs(x-fx)+abs(y-fy);

}

int astar(int x,int y)

{

int i,j,m,n,cost,cnt;
priority_queue<op>Q;
set<Vector>C;
set<Vector>O;
O.insert(Vector(sx,sy));
Q.push(op(x,y,0));

memset(f_cost_cell,-1,sizeof(f_cost_cell));

while(!Q.empty())

{
op P=Q.top();

Q.pop();

x=P.x;y=P.y;
const bool is_inq = C.find(Vector(x,y)) != C.end();

if (is_inq) continue;

C.insert(Vector(x,y));

cout<<endl<<"current node"<< x<<" "<<y<<endl;

if(f_cost_cell[x][y] != -1) continue;

f_cost_cell[x][y]=P.cost+P.h;

cout<<"here"<<endl;

for(i=0;i<4;i++)

{

m=x+dx[i];

n=y+dy[i];

if (maze[m][n] ==8) continue;

if(m>=0 && m<SIZE && n>=0 && n<SIZE){

cost = distance(x,y,m,n);
const bool is_in_C = C.find(Vector(m,n)) != C.end();
const bool is_in_O = O.find(Vector(m,n)) != O.end();

if((is_in_C) || (is_in_O)) {

if (cost > P.total_cost)
cost = P.total_cost;      //g(m) = g(n)+c(n,goal)
else if (cost< P.total_cost)
cost = distance(x,y,m,n); //g(m)

C.erase(Vector(m,n));
O.insert(Vector(m,n));
Q.push(op(m,n,cost));
}
else if ((!is_in_C) || (!is_in_O)){
cost=P.total_cost;
Q.push(op(m,n,cost));}

cout<<m<<" "<<n<<endl;
}

}

}

}

void matrix () {

srand (time(NULL));

for (int j=0;j<SIZE;j++){
cout<<endl;
for(int k=0;k<SIZE;k++){
maze[j][k] = rand()%6;
}
}

for (int j=3;j<6;j++){
cout<<endl;
for(int k=3;k<5;k++){
maze[j][k] = 8;
}
}
for (int j=4;j<7;j++){
cout<<endl;
for(int k=8;k<10;k++){
maze[j][k] = 8;
}
}

for (int j=2;j<6;j++){
cout<<endl;
for(int k=2;k<3;k++){
maze[j][k] = 8;
}
}

for (int j=0;j<SIZE;j++){
cout<<endl;
for(int k=0;k<SIZE;k++){
cout<<setw(3)<<maze[j][k];
}
}

}
void matrix_print(){
for (int j=0;j<SIZE;j++){
cout<<endl;
for(int k=0;k<SIZE;k++){
cout<<setw(3)<<maze[j][k];
}

}
cout<<endl;
}

int main()

{

int j,k;

cout<<"Matrix Description :"<<endl;

matrix();

cout<<endl<<"Start :";

cin >>sx>>sy;

if (maze[sx][sy] == 8){
cout<<"The start is an obstacle"<<endl;
exit(0);}

cout<<"Goal :";

cin>>fy>>fx;

if (maze[fx][fy] == 8){
cout<<"The goal is an obstacle"<<endl;
exit(0);}

astar(sx,sy);

cout<< "the fcost is "<< f_cost_cell[fx][fy]<<endl;

matrix_print();

return 0;

}

• Welcome to Code Review. Could you please add a bit more description of your code in your question. You could add something if you want something specific out of the review (but everything can be reviewed either way) – Marc-Andre Dec 14 '16 at 14:45

I'll focus on the cleanliness issues since that probably needs work first:

• You don't really need to put a blank line between each #include. It just makes the code needlessly longer. You also don't need <string.h> when you have <cstring> and <stdio.h> should be <cstdio> for C++.

• For #define constants:

#define SIZE    10


prefer const in C++:

const int SIZE = 10;


• Code within curly braces should have the same indentation.
• There should be a space between each operator.
• There shouldn't be random blank lines.
• Opening curly braces should either be on the same line as the function name or right below it, or in some consistent and reasonable combination.

For example, this:

if (maze[sx][sy] == 8){
cout<<"The start is an obstacle"<<endl;
exit(0);}


should look like this:

if (maze[sx][sy] == 8) {
cout << "The start is an obstacle" << endl;
exit(0);
}


There are many occurrences in your code, but this is a start. Do consider looking at some resources or other implementations for good examples of this.

• Try to have just one variable per line for more readability:

int sx,sy,fx,fy,f_cost_cell[100][100];


it should look like this:

int sx;
int sy;
int fx;
int fy;
int f_cost_cell[100][100];


However, if you're going to keep them on one line anyway, then at least add a space after each comma so that it's a little easier tell each variable apart.

• I strongly recommend a C++ container class such as std::vector in place of your arrays. There are many reasons why arrays aren't encouraged in C++, so the sooner you cease using them, the better.

• Thank You Sir @Jamal. I will surely clean up my code. But is my logic correct ? – Anirudha Bhaskar Dec 14 '16 at 18:20