Followers 0

# A star

## 21 posts in this topic

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;
}
else delete m0; // garbage collection
}
}
delete n0; // garbage collection
}
return ""; // no route found
}


Edited by mypel16000
-4

##### Share on other sites
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
2

##### 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.

0

##### 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|
0

##### Share on other sites

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

-4

##### Share on other sites

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

-4

##### 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.
1

##### Share on other sites

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

-3

0

##### Share on other sites

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

-3

##### Share on other sites
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.
0

##### Share on other sites

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

-3

##### Share on other sites

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

-7

##### Share on other sites

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;
}
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
-1

##### Share on other sites

I can pretty much promise you that the problem is with your code

Well, considering his new thread about this very issue ( http://www.gamedev.net/topic/637918-a-star-tutorials-sfml/ ), I don't think the problem is in "his" code, because apparently all he did so far is copy/paste some seriously awful code from the internet, include the .cpp in another .cpp, be confused about it not working and then asking for someone to do all the programming for him.

Okay, technically it still is in his code, considering that "include <Astar.cpp>" was most certainly not in the original code. Still, this looks like yet another case of wanting to write a game without first learning the absolute basics of the chosen language. Edited by Trienco
0

##### Share on other sites

I/we can get your previous code to compile just fine using the exact instructions that had been given previously.  I even went out of my way to download and install Code::Blocks to test it out so I can show you that it is not a Code::Blocks issue.

The fact you copied and pasted this code and expected it to work is a red flag to us.  You can't do that.  Could you tell us what what your code is doing actually right now?  You don't need it to compile for you to get a good idea on what will happen.  Just follow your code line by line.

We do want to help you as this is what this community is for.  Though we aren't just going to give you all the answers to your program and write all your code for you.  Again we see you tried to include a .cpp file, that was a huge red flag for us even more to see that you aren't ready for this.

here is a quick lesson in working with multiple files.

Lets say you have the following class:

class Foo
{
public:
Foo();

int GetX();

private:
int x;
};


What should we do with this class?  We should put it in a header file.  Though if we just did that and started including it with no include guards then we would be in trouble.  We would be getting compiler errors galore!  So what do we do to stop that?  We use include guards

Foo.h

// The first thing you need to do in header files is use include guards
#ifndef FOO_H_ // It's just common to name it like this.  it doesn't HAVE to be like that
#define FOO_H_ // make sure you do use the same name though for no own.

class Foo
{
public:
Foo();

int GetX();

private:
int x;
};

// Ok, now after your class and code that belongs in a header file you need a #endif
#endif //Your header file now has include guards  Include this header file when you need to use it.


Lets say you want to write the implementation details for the Foo Class.  You need to do that in it's separate .cpp file (also called source files).  First is first, you include the Foo.h header file then implement your class.  You do not use include guards .cpp files.  Only in header files.

Now you're ready to use this anywhere.  When ever you need to use the Foo class you would just include Foo.h.  That easy.

Just slow down what you want to do and start from the basics to learn the language.  Sadly we can't go out and make the next biggest game without knowing how to use the language.

Again, we want to help you, but we can't just give your all your code nor can you expect to just find your code online and use it that way.

2

## Create an account

Register a new account