Jump to content
  • Advertisement
Sign in to follow this  
mypel16000

A star

This topic is 1969 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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|

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Are you sure you don't have a using namespace std; somewhere? Possibly inside include.h? Alternatively you can rename your map variable.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!