-4
\$\begingroup\$

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

    {

        return total_cost>b.total_cost;    

    }

};



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;

}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Marc-Andre Dec 14 '16 at 14:45
3
\$\begingroup\$

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;
    
  • Please keep your indentation and whitespace consistent:

    • 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:

    Instead of this:

    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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.