Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


A star


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 mypel16000   Members   -  Reputation: 46

Like
-3Likes
Like

Posted 22 January 2013 - 03:38 PM

I have this A* code, but I am desperate, it keeps giving me errors and I have no idea about what is going on. The code is quite big, but I can post the build errors so you guys can spot where the problems are; I'm not sure if anyone can help, as to help, one needs to be an ace at this.

Build errors:


In function 'std::string pathFind(const int&, const int&, const int&, const int&)':|
|156|error: reference to 'map' is ambiguous|
|16|error: candidates are: int map [60][60]|

c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.4.1\include\c++\bits\stl_map.h|86|error:
template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map|

|156|error: reference to 'map' is ambiguous|
|16|error: candidates are: int map [60][60]|

c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.4.1\include\c++\bits\stl_map.h|86|error:
template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map|

|93|warning: unused variable 'xdx'|
|93|warning: unused variable 'ydy'|


||=== Build finished: 6 errors, 2 warnings ===|

 

#include <iostream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
#include "include.h"
using namespace std;

const int n=60; // horizontal size of the map
const int m=60; // vertical size size of the map
int map[n][m];
static int closed_nodes_map[n][m]; // map of closed (tried-out) nodes
static int open_nodes_map[n][m]; // map of open (not-yet-tried) nodes
static int dir_map[n][m]; // map of directions
const int dir=8; // number of possible directions to go at any position
// if dir==4
//static int dx[dir]={1, 0, -1, 0};
//static int dy[dir]={0, 1, 0, -1};
// if dir==8
static int dx[dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dy[dir]={0, 1, 1, 1, 0, -1, -1, -1};

class node
{
    // current position
    int xPos;
    int yPos;
    // total distance already travelled to reach the node
    int level;
    // priority=level+remaining distance estimate
    int priority;  // smaller: higher priority

    public:
        node(int xp, int yp, int d, int p)
            {xPos=xp; yPos=yp; level=d; priority=p;}

        int getxPos() const {return xPos;}
        int getyPos() const {return yPos;}
        int getLevel() const {return level;}
        int getPriority() const {return priority;}

        void updatePriority(const int & xDest, const int & yDest)
        {
             priority=level+estimate(xDest, yDest)*10; //A*
        }

        // give better priority to going strait instead of diagonally
        void nextLevel(const int & i) // i: direction
        {
             level+=(dir==8?(i%2==0?10:14):10);
        }

        // Estimation function for the remaining distance to the goal.
        const int & estimate(const int & xDest, const int & yDest) const
        {
            static int xd, yd, d;
            xd=xDest-xPos;
            yd=yDest-yPos;

            // Euclidian Distance
            d=static_cast<int>(sqrt(xd*xd+yd*yd));

            // Manhattan distance
            //d=abs(xd)+abs(yd);

            // Chebyshev distance
            //d=max(abs(xd), abs(yd));

            return(d);
        }
};

// Determine priority (in the priority queue)
bool operator<(const node & a, const node & b)
{
  return a.getPriority() > b.getPriority();
}

// A-star algorithm.
// The route returned is a string of direction digits.
string pathFind( const int & xStart, const int & yStart,
                 const int & xFinish, const int & yFinish )
{
    static priority_queue<node> pq[2]; // list of open (not-yet-tried) nodes
    static int pqi; // pq index
    static node* n0;
    static node* m0;
    static int i, j, x, y, xdx, ydy;
    static char c;
    pqi=0;

    // reset the node maps
    for(y=0;y<m;y++)
    {
        for(x=0;x<n;x++)
        {
            closed_nodes_map[x][y]=0;
            open_nodes_map[x][y]=0;
        }
    }

    // create the start node and push into list of open nodes
    n0=new node(xStart, yStart, 0, 0);
    n0->updatePriority(xFinish, yFinish);
    pq[pqi].push(*n0);
    open_nodes_map[x][y]=n0->getPriority(); // mark it on the open nodes map

    // A* search
    while(!pq[pqi].empty())
    {
        // get the current node w/ the highest priority
        // from the list of open nodes
        n0=new node( pq[pqi].top().getxPos(), pq[pqi].top().getyPos(),
                     pq[pqi].top().getLevel(), pq[pqi].top().getPriority());

        x=n0->getxPos(); y=n0->getyPos();

        pq[pqi].pop(); // remove the node from the open list
        open_nodes_map[x][y]=0;
        // mark it on the closed nodes map
        closed_nodes_map[x][y]=1;

        // quit searching when the goal state is reached
        //if((*n0).estimate(xFinish, yFinish) == 0)
        if(x==xFinish && y==yFinish)
        {
            // generate the path from finish to start
            // by following the directions
            string path="";
            while(!(x==xStart && y==yStart))
            {
                j=dir_map[x][y];
                c='0'+(j+dir/2)%dir;
                path=c+path;
                x+=dx[j];
                y+=dy[j];
            }

            // garbage collection
            delete n0;
            // empty the leftover nodes
            while(!pq[pqi].empty()) pq[pqi].pop();
            return path;
        }

        // generate moves (child nodes) in all possible directions
        for(i=0;i<dir;i++)
        {
            int xdx = x+dx[i]; int ydy=y+dy[i];

            if(!(xdx<0 || xdx>n-1 || ydy<0 || ydy>m-1 || map[xdx][ydy]==1 || closed_nodes_map[xdx][ydy]== 1))
            {
                // generate a child node
                m0=new node( xdx, ydy, n0->getLevel(),
                             n0->getPriority());
                m0->nextLevel(i);
                m0->updatePriority(xFinish, yFinish);

                // if it is not in the open list then add into that
                if(open_nodes_map[xdx][ydy]==0)
                {
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    pq[pqi].push(*m0);
                    // mark its parent node direction
                    dir_map[xdx][ydy]=(i+dir/2)%dir;
                }
                else if(open_nodes_map[xdx][ydy]>m0->getPriority())
                {
                    // update the priority info
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    // update the parent direction info
                    dir_map[xdx][ydy]=(i+dir/2)%dir;

                    // replace the node
                    // by emptying one pq to the other one
                    // except the node to be replaced will be ignored
                    // and the new node will be pushed in instead
                    while(!(pq[pqi].top().getxPos()==xdx &&
                           pq[pqi].top().getyPos()==ydy))
                    {
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();
                    }
                    pq[pqi].pop(); // remove the wanted node

                    // empty the larger size pq to the smaller one
                    if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
                    while(!pq[pqi].empty())
                    {
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();
                    }
                    pqi=1-pqi;
                    pq[pqi].push(*m0); // add the better node instead
                }
                else delete m0; // garbage collection
            }
        }
        delete n0; // garbage collection
    }
    return ""; // no route found
}

 

 


Edited by mypel16000, 22 January 2013 - 03:40 PM.


Sponsor:

#2 Paradigm Shifter   Crossbones+   -  Reputation: 5411

Like
7Likes
Like

Posted 22 January 2013 - 03:44 PM

Don't call a variable 'map' after a using namespace std statement.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#3 Paradigm Shifter   Crossbones+   -  Reputation: 5411

Like
2Likes
Like

Posted 22 January 2013 - 03:58 PM

Also, your estimate function is a bit dud.

Casting the Euclidean distance to an int means an offset of (1,1) returns a distance of 1 - same as manhattan or chebyshev. It works a bit better for distances larger than that.

Returning a reference to a static local is going to break if you run on separate threads. Just return the int (or better, a float).

EDIT: All your returning of static locals is just bad anyway. You really don't want to do that.

Edited by Paradigm Shifter, 22 January 2013 - 04:00 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#4 BeerNutts   Crossbones+   -  Reputation: 2981

Like
7Likes
Like

Posted 22 January 2013 - 04:01 PM

Don't call a variable 'map' after a using namespace std statement.

 

Or even better, don't have "using namespace std"

 

There's a reason it's within it's own namespace, that's so you can have variables/typedefs/classes/structs/enums with the same name (like map) and not have any issues. Once you start typing std::string instead of string, it'll be second nature.


My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#5 Trienco   Crossbones+   -  Reputation: 2215

Like
0Likes
Like

Posted 22 January 2013 - 11:23 PM

What's worrying me even more is that I can't tell if this is a header or source file (the former would basically result in a lot of crying and forehead to table contact, because of the "using" and all the static variables). And even worse is the fact that the code looks like you really need to take a step back and understand memory management in C++. It's not just the abuse of the word "garbage collection" (which is a concept that is basically the exact opposite of what you're doing), but all the pointless new and delete calls in combination with leaking memory like crazy and apparently thinking that somehow "push(*pointer)" would not still create a copy of your object, making it very pointless to do an expensive allocation on the heap.


f@dzhttp://festini.device-zero.de

#6 mypel16000   Members   -  Reputation: 46

Like
0Likes
Like

Posted 26 January 2013 - 12:32 PM

This isn't solving my problems. I don't care about memory, so don't talk about that. Even after deleting the namespace std and using std:: before everything, it doesnt work, I've tried renaming all troubled variables to something different, but nothing... I get these errors:

 

 

|| In function 'std::string pathFind(const int&, const int&, const int&, const int&)':|
|155|error: reference to 'map' is ambiguous|
|15|error: candidates are: int map [60][60]|
|86|error:                 template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map|
|155|error: reference to 'map' is ambiguous|
|15|error: candidates are: int map [60][60]|
|86|error:                 template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map|


#7 SiCrane   Moderators   -  Reputation: 9629

Like
3Likes
Like

Posted 26 January 2013 - 12:40 PM

Did you also get rid of it in the include files that you bring in? That is include.h and anything that include.h includes.

#8 mypel16000   Members   -  Reputation: 46

Like
-3Likes
Like

Posted 26 January 2013 - 12:41 PM

If this doesn't work, can you give me a pre-made recipe or something please!



#9 mypel16000   Members   -  Reputation: 46

Like
-3Likes
Like

Posted 26 January 2013 - 12:43 PM

Yes, I got rid of the include "include.h" Is there a pre-made code I can have?



#10 Mussi   Crossbones+   -  Reputation: 2060

Like
1Likes
Like

Posted 26 January 2013 - 12:44 PM

Are you sure you don't have a using namespace std; somewhere? Possibly inside include.h? Alternatively you can rename your map variable.

#11 mypel16000   Members   -  Reputation: 46

Like
-2Likes
Like

Posted 26 January 2013 - 12:46 PM

I have tried renaming map and YES! I AM SURE I HAVE DELETED using namespace std. 



#12 SiCrane   Moderators   -  Reputation: 9629

Like
0Likes
Like

Posted 26 January 2013 - 12:50 PM

Try posting your current code.

#13 mypel16000   Members   -  Reputation: 46

Like
-2Likes
Like

Posted 26 January 2013 - 12:53 PM

Its posted at the beggining.... It's the same. I have gone back to what i had on the first place as by changing the names, i started getting hundreds of errors



#14 SiCrane   Moderators   -  Reputation: 9629

Like
0Likes
Like

Posted 26 January 2013 - 01:04 PM

If your current code is exactly the same as the code you originally posted then you still need to remove the using namespace std from the file and all the include files that you include as well as add std:: in front of the identifiers from the std namespace. If the code is not exactly the same as the code that you originally posted, then try posting your current code along with the current errors.

I can get your original code to compile by removing the using directive and the #include "include.h" and inserting std:: in the appropriate places.

#15 mypel16000   Members   -  Reputation: 46

Like
-2Likes
Like

Posted 26 January 2013 - 01:07 PM

its the same, but without using namespace std, include "include.h", and with all the std::s. Do you really need it again?



#16 SiCrane   Moderators   -  Reputation: 9629

Like
4Likes
Like

Posted 26 January 2013 - 01:09 PM

Why do you think I'm asking?

#17 mypel16000   Members   -  Reputation: 46

Like
-6Likes
Like

Posted 26 January 2013 - 01:17 PM

there is no point.... you aren't gonna help in anyway like that. I just need a pre-made implementation please



#18 Washu   Senior Moderators   -  Reputation: 5368

Like
6Likes
Like

Posted 26 January 2013 - 02:01 PM

We are not going to do your homework for you. We may assist you by providing information about the issues with your code, but we're not going to do the work for you. YOU are the one coming to us for help in solving the issue, US implementing it for you would not help YOU to solve YOUR problem. More importantly, it wouldn't teach you anything either.

In time the project grows, the ignorance of its devs it shows, with many a convoluted function, it plunges into deep compunction, the price of failure is high, Washu's mirth is nigh.
ScapeCode - Blog | SlimDX


#19 mypel16000   Members   -  Reputation: 46

Like
0Likes
Like

Posted 27 January 2013 - 04:22 AM

Thank you for all the -1s.... I am just desperate as I have been trying to fix this for weeks. I have realised that the error isn't in the code... It is just in my project. I am using Code::Blocks and SFML. Even if I don't include it in the main function and even if I don't include anything froom the rest of the project in it. It returns all the same errors (see above). It is the most bizarre thing I have ever seen, and I have no idea what might be causing it. Is there some compatibility issue with codeblocks or just something? The code for the working one is this:
.length();i++)>;y++)>;i++)>;y++)>.h>.h>

 

 

#include <iostream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
#include <cstdlib>
#include <stdio.h>

int n=60; // horizontal size of the map
int m=60; // vertical size size of the map
int map[60][60];
int closed_nodes_map[60][60]; // map of closed (tried-out) nodes
int open_nodes_map[60][60]; // map of open (not-yet-tried) nodes
int dir_map[60][60]; // map of directions
const int dir=8; // number of possible directions to go at any position
// if dir==4
//static int dx[dir]={1, 0, -1, 0};
//static int dy[dir]={0, 1, 0, -1};
// if dir==8
static int dx[dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dy[dir]={0, 1, 1, 1, 0, -1, -1, -1};

class node
{
    // current position
    int xPos;
    int yPos;
    // total distance already travelled to reach the node
    int level;
    // priority=level+remaining distance estimate
    int priority;  // smaller: higher priority

    public:
        node(int xp, int yp, int d, int p)
            {xPos=xp; yPos=yp; level=d; priority=p;}

        int getxPos() const {return xPos;}
        int getyPos() const {return yPos;}
        int getLevel() const {return level;}
        int getPriority() const {return priority;}

        void updatePriority(const int & xDest, const int & yDest)
        {
             priority=level+estimate(xDest, yDest)*10; //A*
        }

        // give better priority to going strait instead of diagonally
        void nextLevel(const int & i) // i: direction
        {
             level+=(dir==8?(i%2==0?10:14):10);
        }

        // Estimation function for the remaining distance to the goal.
        const int & estimate(const int & xDest, const int & yDest) const
        {
            static int xd, yd, d;
            xd=xDest-xPos;
            yd=yDest-yPos;

            // Euclidian Distance
            d=static_cast<int>(sqrt(xd*xd+yd*yd));

            // Manhattan distance
            //d=abs(xd)+abs(yd);

            // Chebyshev distance
            //d=max(abs(xd), abs(yd));

            return(d);
        }
};

// Determine priority (in the priority queue)
bool operator<(const node & a, const node & b)
{
  return a.getPriority() > b.getPriority();
}

// A-star algorithm.

// The route returned is a string of direction digits.
std::string pathFind( const int & xStart, const int & yStart,
                 const int & xFinish, const int & yFinish )
{
    static std::priority_queue<node> pq[2]; // list of open (not-yet-tried) nodes
    static int pqi; // pq index
    static node* n0;
    static node* m0;
    static int i, j, x, y;
     int xla = 60;
     int ydy = 60;
    static char c;
    pqi=0;

    // reset the node maps
    for(y=0;y<m;y++)
    {
        for(x=0;x<n;x++)
        {
            closed_nodes_map[x][y]=0;
            open_nodes_map[x][y]=0;
        }
    }

    // create the start node and push into list of open nodes
    n0=new node(xStart, yStart, 0, 0);
    n0->updatePriority(xFinish, yFinish);
    pq[pqi].push(*n0);
    open_nodes_map[x][y]=n0->getPriority(); // mark it on the open nodes map

    // A* search
    while(!pq[pqi].empty())
    {
        // get the current node w/ the highest priority
        // from the list of open nodes
        n0=new node( pq[pqi].top().getxPos(), pq[pqi].top().getyPos(),
                     pq[pqi].top().getLevel(), pq[pqi].top().getPriority());

        x=n0->getxPos(); y=n0->getyPos();

        pq[pqi].pop(); // remove the node from the open list
        open_nodes_map[x][y]=0;
        // mark it on the closed nodes map
        closed_nodes_map[x][y]=1;

        // quit searching when the goal state is reached
        //if((*n0).estimate(xFinish, yFinish) == 0)
        if(x==xFinish && y==yFinish)
        {
            // generate the path from finish to start
            // by following the directions
            std::string path="";
            while(!(x==xStart && y==yStart))
            {
                j=dir_map[x][y];
                c='0'+(j+dir/2)%dir;
                path=c+path;
                x+=dx[j];
                y+=dy[j];
            }

            // garbage collection
            delete n0;
            // empty the leftover nodes
            while(!pq[pqi].empty()) pq[pqi].pop();
            return path;
        }

        // generate moves (child nodes) in all possible directions
        for(i=0;i<dir;i++)
        {
            xla=x+dx[i]; ydy=y+dy[i];

            if(!(xla<0 || xla>n-1 || ydy<0 || ydy>m-1 || map[xla][ydy]==1
                || closed_nodes_map[xla][ydy]==1))
            {
                // generate a child node
                m0=new node( xla, ydy, n0->getLevel(),
                             n0->getPriority());
                m0->nextLevel(i);
                m0->updatePriority(xFinish, yFinish);

                // if it is not in the open list then add into that
                if(open_nodes_map[xla][ydy]==0)
                {
                    open_nodes_map[xla][ydy]=m0->getPriority();
                    pq[pqi].push(*m0);
                    // mark its parent node direction
                    dir_map[xla][ydy]=(i+dir/2)%dir;
                }
                else if(open_nodes_map[xla][ydy]>m0->getPriority())
                {
                    // update the priority info
                    open_nodes_map[xla][ydy]=m0->getPriority();
                    // update the parent direction info
                    dir_map[xla][ydy]=(i+dir/2)%dir;

                    // replace the node
                    // by emptying one pq to the other one
                    // except the node to be replaced will be ignored
                    // and the new node will be pushed in instead
                    while(!(pq[pqi].top().getxPos()==xla &&
                           pq[pqi].top().getyPos()==ydy))
                    {
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();
                    }
                    pq[pqi].pop(); // remove the wanted node

                    // empty the larger size pq to the smaller one
                    if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
                    while(!pq[pqi].empty())
                    {
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();
                    }
                    pqi=1-pqi;
                    pq[pqi].push(*m0); // add the better node instead
                }
                else delete m0; // garbage collection
            }
        }
        delete n0; // garbage collection
    }
    return ""; // no route found
}

int main()
{
    srand(time(NULL));

    // create empty map
    for(int y=0;y<m;y++)
    {
        for(int x=0;x<n;x++) map[x][y]=0;
    }

    // fillout the map matrix with a '+' pattern
    for(int x=n/8;x<n*7/8;x++)
    {
        map[x][m/2]=1;
    }
    for(int y=m/8;y<m*7/8;y++)
    {
        map[n/2][y]=1;
    }

    // randomly select start and finish locations
    int xA, yA, xB, yB;
    switch(rand()%8)
    {
        case 0: xA=0;yA=0;xB=n-1;yB=m-1; break;
        case 1: xA=0;yA=m-1;xB=n-1;yB=0; break;
        case 2: xA=n/2-1;yA=m/2-1;xB=n/2+1;yB=m/2+1; break;
        case 3: xA=n/2-1;yA=m/2+1;xB=n/2+1;yB=m/2-1; break;
        case 4: xA=n/2-1;yA=0;xB=n/2+1;yB=m-1; break;
        case 5: xA=n/2+1;yA=m-1;xB=n/2-1;yB=0; break;
        case 6: xA=0;yA=m/2-1;xB=n-1;yB=m/2+1; break;
        case 7: xA=n-1;yA=m/2+1;xB=0;yB=m/2-1; break;
    }

    std::cout<<"Map Size (X,Y): "<<n<<","<<m<<std::endl;
    std::cout<<"Start: "<<xA<<","<<yA<<std::endl;
    std::cout<<"Finish: "<<xB<<","<<yB<<std::endl;
    // get the route
    clock_t start = clock();
    std::string route=pathFind(xA, yA, xB, yB);
    if(route=="") std::cout<<"An empty route generated!"<<std::endl;
    clock_t end = clock();
    double time_elapsed = double(end - start);
    std::cout<<"Time to calculate the route (ms): "<<time_elapsed<<std::endl;
    std::cout<<"Route:"<<std::endl;
    std::cout<<route<<std::endl<<std::endl;

    // follow the route on the map and display it
    if(route.length()>0)
    {
        int j; char c;
        int x=xA;
        int y=yA;
        map[x][y]=2;
        for(int i=0;i<route.length();i++)
        {
            c =route.at(i);
            j=atoi(&c);
            x=x+dx[j];
            y=y+dy[j];
            map[x][y]=3;
        }
        map[x][y]=4;

        // display the map with the route
        for(int y=0;y<m;y++)
        {
            for(int x=0;x<n;x++)
                if(map[x][y]==0)
                    std::cout<<".";
                else if(map[x][y]==1)
                    std::cout<<"O"; //obstacle
                else if(map[x][y]==2)
                    std::cout<<"S"; //start
                else if(map[x][y]==3)
                    std::cout<<"R"; //route
                else if(map[x][y]==4)
                    std::cout<<"F"; //finish
            std::cout<<std::endl;
        }
    }
    getchar(); // wait for a (Enter) keypress
    return(0);
}

 




This works fine on its own if you want to try it
To implement it to my project, I created a .cpp file and copied all of this code (apart from the main). I then said #include "Astar.cpp" in my main.cpp, where the main is and all other files are included.length();i++)>;y++)>;i++)>;y++)>.h>.h>

Edited by mypel16000, 27 January 2013 - 04:27 AM.


#20 JTippetts   Moderators   -  Reputation: 8598

Like
5Likes
Like

Posted 27 January 2013 - 08:10 AM

I can pretty much promise you that the problem is with your code, and not a bug or problem with Code::Blocks itself, especially if you think #include-ing a .cpp file is the right way to do things. It's generally a bad idea to #include a .cpp file. You should include only .h header files.

 

I am puzzled by some of your architectural choices. You have a node class so you are trying to use C++, but then you have a whole raft of static globals and a global pathFind function, when all of that stuff should probably live inside a class of its own so that you can avoid the static global hell you have now. Declare your classes in AStar.h, implement them in AStar.cpp, then #include AStar.h wherever you need to use it. Be sure to use include guards (something along the lines of #pragma once or #ifndef ASTAR_H #define ASTAR_H #endif) if you need to include AStar.h into multiple compilation units where there might be a chance that it gets included twice.

 

Also, I note that even though several posters strongly recommended that you post the actual code that you have a problem with, you still decided to post code that, by your own words, "works" rather than the actual code that does not work. (I put the word works in quotations, because I haven't gone through the process of digging through that code to see if it actually does work or not, and from a cursory examination, I highly doubt that it doesn't have any bugs especially since it looks to me like you're going to end up leaking memory like crazy.

 

 Look carefully at your new/delete calls in findPath(). You allocate a node, but then you call pq[pqi].push(*n0), pushing the newly allocated node by value onto the priority queue. Then you delete the new node. If all you are going to use the new node for is to push it by value (which results in the contents of the node being copied into a new node maintained by the queue) then why do you need to even new/delete a node at all? Just use a local. I mean, if you were storing pointers to nodes in your queue then yes, sure, you could dynamically allocate, but you aren't storing pointers. All those new/delete calls are doing is slowing your code down and giving you an awesome and exciting way to potentially leak memory all over the floor.

 

I am puzzled as well by your use of an array of 2 priority queues for your open set. In your section for generating moves, you include some code that gives me chills to look at with the comment "replace the node by emptying one pq to the other one." Oh, God, why? Keeping the open list updated is already one of the more performance-heavy operations of a pathfinder; why in the name of St. Peter would you want to make it even slower by doing a full queue copy just to update a node?

 

You earlier asked for a premade solution. I'm not going to give that to you either, but I highly suggest you check the long-time go-to list of pathfinding links at http://www-cs-students.stanford.edu/~amitp/gameprog.html to learn a bit more. You also might want to brush up on your C++ skills and structure. Remember this: if you have some kind of weird compilation error, the error is almost certainly in your code, not the compiler. Some people do still find compiler bugs, whatever the platform. However, those bugs generally crop up only in very advanced usage; all the basic usage cases such as what you are attempting will have long ago had their bugs ironed out. 






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS