Hi!

I am just working on a test-program for my path-finding algorithm and I found out that it doesn't always work correct. Here are the files:

path.cpp
[code path.cpp]
#include "path.h"

void load(const string& filename)
{
ifstream file(filename.c_str());

map.resize(MAPSIZE);
for(int i = 0;i < MAPSIZE;i++)
map<i>.resize(MAPSIZE);

if(file.is_open())
{
string line;

// read the map and store it
for(int i = 0;i < MAPSIZE;i++)
{
if (getline(file,line,'\n'))
{
for(int j = 0;j < MAPSIZE;j++)
{
map[j]<i> = line[j];
if (line[j] == 'A')
{
ac = j;
ar = i;
}
if (line[j] == 'B')
{
bc = j;
br = i;
}
}
}
else
{
cout << "Error while parsing the map!" << endl;
exit(-1);
}
}

// read the start
getline(file,line,'\n');
if (sscanf(line.c_str(), "%d %d", &ac, &ar) < 2)
{
cout << "Error while parsing the map!" << endl;
exit(-1);
}

// read the target
getline(file,line,'\n');
if (sscanf(line.c_str(), "%d %d %d %d", &bc, &br, &bw, &bh) < 4)
{
cout << "Error while parsing the map!" << endl;
exit(-1);
}
}
else
{
cout << "Couldn't open mapfile!" << endl;
exit(-1);
}

return;
}

int get_h(int ac, int ar, int bc, int br)
{
int delta_x = abs(ac - bc);
int delta_y = abs(ar - br);
//return (static_cast<int>(fabs(sqrt(pow(delta_x, 2) + pow(delta_y, 2)) * 10.0f)));
return ((abs(ac - bc) + abs(ar - br)) * 10);
}

bool node_valid(int c, int r)
{
if (c > MAPSIZE - 1 || c < 0 || r > MAPSIZE - 1 || c < 0)
return false;
return true;
}

bool node_in_list(int c, int r, list<CNode*>& list_)
{
list<CNode*>::iterator it = list_.begin();
while(it != list_.end())
{
if ((*it)->get_c() == c && (*it)->get_r() == r)
return true;
*it++;
}
return false;
}

void delete_list(list<CNode*>& list_)
{
list<CNode*>::iterator it = list_.begin();
while(it != list_.end())
delete *it++;
}

list<CNode*>::iterator get_best_f(list<CNode*>& list_)
{
list<CNode*>::iterator best = list_.begin();
list<CNode*>::iterator it = list_.begin();
while(it != list_.end())
{
if ((*it)->get_f() < (*best)->get_f())
best = it;
it++;
}
return best;
}

bool create_path(void)
{

// see, if we can return immediately
if (ac == bc && ar == br)
return true;

// add the current node to the closedlist
closedlist.push_front(new CNode(ac, ar, 0, get_h(ac, ar, bc, br)));

// create a target-node ( not in one of the lists ), so we can use target_reached() more easily
//const CNode* tar = new CNode(target->get_c(), target->get_r(), 0, 0);

// set the current node, which will be altered during the walk through the map
const CNode* cur = closedlist.front();

while(cur->get_c() != bc || cur->get_r() != br)
{
int c, r;
int i;

// add the surrounding nodes to the openlist (in a random order)
vector<int> tmp(8);
for(i = 0;i < 8;i++)
tmp<i> = i;
random_shuffle(tmp.begin(), tmp.end());
for(i = 0;i < 8;i++)
{
int g_modifier = 10;
c = cur->get_c();
r = cur->get_r();

if (tmp<i> == 0)
c++;
else if (tmp<i> == 1)
c--;
else if (tmp<i> == 2)
r++;
else if (tmp<i> == 3)
r--;
else if (tmp<i> == 4)
{
c++;
r++;
g_modifier += 4;
}
else if (tmp<i> == 5)
{
c--;
r++;
g_modifier += 4;
}
else if (tmp<i> == 6)
{
r--;
c++;
g_modifier += 4;
}
else if (tmp<i> == 7)
{
r--;
c--;
g_modifier += 4;
}

if (node_valid(c, r) && map[c][r] != '1' && !node_in_list(c, r, openlist) && !node_in_list(c, r, closedlist))
{
openlist.push_front(new CNode(c, r, cur->get_g() + g_modifier, get_h(c, r, bc, br), cur));
}
}

// check, if the openlist is empty or the closedlist too full
if (!openlist.size() || int(closedlist.size()) > MAX_NODE_CHECKS)
return false;

// put the node with the best f-value in the closedlist
list<CNode*>::iterator best_f = get_best_f(openlist);
closedlist.push_front(*best_f);
openlist.erase(best_f);

// change the cur-variable
cur = *best_f;
}

// coming here, it means that there is a valid path
// now track back the way to the start by accessing the parent and save it in the path-variable
while(cur != closedlist.back())
{ // while start not reached
path.push_back(new CNode(*cur));
cur = cur->get_parent();
}

return true;
}

void save_screenshot(const char *path)
{
BITMAP *bmp = create_bitmap(SCREEN_W,SCREEN_H);
if(!bmp) return;
unsigned char *buff = new unsigned char[4*SCREEN_W*SCREEN_H];
if(!buff)
{
destroy_bitmap(bmp);
return;
}

glReadPixels(0,0,SCREEN_W,SCREEN_H,GL_RGBA,GL_UNSIGNED_BYTE,buff);

int y;
for(y=0;y<SCREEN_H;y++)
memcpy(bmp->line[y],buff+4*SCREEN_W*(SCREEN_H-1-y),4*SCREEN_W);

save_bitmap(path,bmp,NULL);

destroy_bitmap(bmp);
delete buff;
}

void draw(void)
{
GfxRend::FillScreen(Rgba::WHITE);

// draw the grid
for(int i = 0;i < MAPSIZE;i++)
{
GfxRend::Line(i * TILESIZE, 0.0f, i * TILESIZE, MAPSIZE * TILESIZE, Rgba::BLACK);
for(int j = 0;j < MAPSIZE;j++)
GfxRend::Line(0.0f, j * TILESIZE, MAPSIZE * TILESIZE, j * TILESIZE, Rgba::BLACK);
}

// draw the obstacles
for(int i = 0;i < MAPSIZE;i++)
for(int j = 0;j < MAPSIZE;j++)
if (map<i>[j] == '1')
GfxRend::Rect(i * TILESIZE, j * TILESIZE, TILESIZE, TILESIZE, Rgba::BLACK);

// draw the openlist
for(list<CNode*>::const_iterator it = openlist.begin();it != openlist.end();it++)
{
int x = (*it)->get_c() * TILESIZE;
int y = (*it)->get_r() * TILESIZE;
GfxRend::Rect(x, y, TILESIZE, TILESIZE, Rgba::GREEN);
CText::o().write((*it)->get_g(), x, y, "G");
CText::o().write((*it)->get_h(), x, y + 8, "H");
CText::o().write((*it)->get_f(), x, y + 16, "F");
}

// draw the closedlist
for(list<CNode*>::const_iterator it = closedlist.begin();it != closedlist.end();it++)
{
int x = (*it)->get_c() * TILESIZE;
int y = (*it)->get_r() * TILESIZE;
GfxRend::Rect(x, y, TILESIZE, TILESIZE, Rgba::RED);
CText::o().write((*it)->get_g(), x, y, "G");
CText::o().write((*it)->get_h(), x, y + 8, "H");
CText::o().write((*it)->get_f(), x, y + 16, "F");
}

// draw the path
for(list<CNode*>::const_iterator it = path.begin();it != path.end();it++)
{
int x = (*it)->get_c() * TILESIZE;
int y = (*it)->get_r() * TILESIZE;
GfxRend::Rect(x, y, TILESIZE, TILESIZE, Rgba::BLUE);
CText::o().write((*it)->get_g(), x, y, "G");
CText::o().write((*it)->get_h(), x, y + 8, "H");
CText::o().write((*it)->get_f(), x, y + 16, "F");
}

GfxRend::RefreshScreen();

save_screenshot("screenshot.png");
}

void unload(void)
{
for(int i = 0;i < MAPSIZE;i++)
map<i>.resize(0);
map.resize(0);
}

int main(void)
{
Setup::SetupProgram();
Settings::StoreMemoryBitmaps(true);
Setup::SetupScreen(SCREENW, SCREENH, WINDOWED);
set_color_depth(32);
Settings::SetAntialiasing(true);
CText::o().init();

// load the map
load("map/map.map");

// create the path
if (!create_path())
{
cout << "Can't create path!" << endl;
return 0;
}

// draw the path
draw();

// loop
while(!key[KEY_ESC])
;

// destroy the path and the lists
delete_list(path);
delete_list(openlist);
delete_list(closedlist);

// unload the map
unload();
}
END_OF_MAIN()
</code>

path.h
[code path.h]
#ifndef __PATH_H
#define __PATH_H

#include <OpenLayer.hpp>
#include <loadpng.h>
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
#include <list>

#include "node.h"
#include "text.h"

using namespace ol;
using std::vector;
using std::string;
using std::ifstream;
using std::cout;
using std::endl;
using std::list;
using std::pair;

vector< vector<char> > map;
list<CNode*> openlist;
list<CNode*> closedlist;
list<CNode*> path;
int ac;
int ar;
int bc;
int br;
int bw;
int bh;

const static int SCREENW = 800;
const static int SCREENH = 600;
const static int MAPSIZE = 20;
const static int TILESIZE = 30;
const static int MAX_NODE_CHECKS = 10000;

#endif
</code>

node.cpp
[code node.cpp]
#include "node.h"

CNode::CNode(int c, int r, int g, int h, const CNode* parent)
{
c_ = c;
r_ = r;
g_ = g;
h_ = h;
f_ = g + h;
parent_ = parent;
}

CNode::~CNode()
{
}

CNode::CNode(const CNode& src)
{
c_ = src.c_;
r_ = src.r_;
g_ = src.g_;
h_ = src.h_;
f_ = src.f_;
parent_ = src.parent_;
}
</code>

node.h
[code node.h]
#ifndef __NODE_H
#define __NODE_H

class CNode
{
private:
protected:
int c_;
int r_;
int g_;
int h_;
int f_;
const CNode* parent_;
public:
CNode(int c, int r, int g, int h, const CNode* parent = 0);
virtual ~CNode();
CNode(const CNode& src);

inline int get_c(void) const { return (c_); }
inline int get_r(void) const { return (r_); }
inline int get_g(void) const { return (g_); }
inline int get_h(void) const { return (h_); }
inline int get_f(void) const { return (f_); }
inline const CNode* get_parent(void) const { return ((!parent_) ? this : parent_); }

virtual bool operator < (const CNode& node) const { return (f_ > node.f_); }
};

#endif
</code>

(I will omit text.cpp and text.h because they aren't necessary)

I attached a picture of the problem. The yellow circle shows where the algo makes the mistake. IMO, the path should go straight down instead of doing a zigzag.

Finally, here is the map-file for this example:

map.map
[code map.map]
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00111111111111110000
00000000000000000000
00000000000000000000
00011111111111111111
00000000000000000000
00000000000000000000
00000000000000000000
00000011111111011111
00000010000000010000
00000010111111110000
00000010000000000000
3 3
16 17 1 1
</code>

The first two numbers after the grid are the starting position in columns and rows and the second four are the position of the target (the two 1s don't have any meaning yet).

Thanks for your help!

Is the the minimum amount of code? Perhaps you could narrow it down to say a function that has the problem? Is it create_path? Explain what c, r, g, h, and f are.

Yes, I guess. If I took something out, I might have taken out the error too.

Most likely! Or one of the functions it calls like get_best_f() or get_h(). I think the error is somewhere within the heuristic, but I dunno.

Well, c and r are the column and the row of the node. g, h and f are the values used by every normal A* algorithm:
g - cost to move from the start to this node
h - cost to move from this node to the end (heuristic)
f - g + h (determines which node to take next)

I know it's not very easy. I needed to post all the code, because in most cases, it works correct, but only in very rare cases (as this one) it doesn't.

Looks to me like you can only create unidirectional paths with your method. Why aren't nodes stored as a graph where the links contain the g, h, and f?

[edit]
Added a negative.

But there is a horizontal path in there as well! I changed the g-value to 14 instead of ten for all diagonal movements exactly like [url http://www.policyalmanac.org/games/aStarTutorial.htm
]this tutorial[/url] suggested.

Could you explain that a bit more in detail? I don't know what you are talking about right now.

No, unidirectional as in point A to B, and not point B to C or even point B to A (though the latter could be accomplished by traversing the lsit backwards).

What I mean is having each node store a list of Link structures. Each Link structure holds a Node that can be directly reached from its node, as well as the g, f, and h. This way simply coat the level with nodes and then move between them. They don't have to be on every tile. For instance:

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
02000000000000000000
02111111111111112000
00200000000000020000
00020000000000000000
00211111111111111111
00000000000000000000
00000000000000000000
00000020000002000000
00000011111111211111
00000010200002010000
00000012111111110000
00000010200000020000

The 2s are nodes, and the character simply moves in a straight line between them.

Oh sorry, I missunderstood you!

Your approach is not A*, but it seems to be more like raycasting. I want the A*-way. The units shouldn't be able to move between nodes that are not adjacent to each other in one step.

I hope you understood me now.

No, my method is A*, you just don't use a grid. A* is simply using weighted steps to compute a path along a graph. A graph is just a bunch of locations that are connected.

The way you have it now, every square is a node, and every node is connected to its 8 adjacent nodes. Every connection has a weight of 1, because it takes the same amount of time to move to any square.

The way I suggest, you only place nodes at important places (corners), and the weight of each connection equals the distance.

Perhaps a better way to demonstrate what I mean is: Use your code to find a route from A to B, then from B to C, then from C to B.

It looks as if g was not taken into account, making diagonal movement as fast as straight horizontal/vertical one.
Could you try to make run a straight north-south line? if it zigzags, you got your problem narrowed down.

Then try putting an absurdly high value of g for diagonal movement, to "forbid" it, and run your original problem: if the algorithm uses ANY diagonal, your code definitely doesn't take g into account.

edit: (heuristic from above) :

//return (static_cast<int>(fabs(sqrt(pow(delta_x, 2) + pow(delta_y, 2)) * 10.0f)));
  return ((abs(ac - bc) + abs(ar - br)) * 10);

Your heuristic expects diagonal movement to be as fast as horizontal one. So it takes the x+1 step getting closer (from a large perspective) to the final goal, as a future step will be able to take it (at no cost) off this dead-end.
Since your actual step costs are 10 and 14, you need a heuristic which weights 10 * min(abs(delta_x), abs(delta_y)) + 14 * abs(abs(delta_x) - abs(delta_y))

Well, in his model diagonal movement is as fast as normal up/down movement.

[edit]
Now you're saying it isn't... Is that so?

[edit]
In the case that you don't want diagonal movement to be weighted more than straight, simply bias it towards moving in a straight line. Say moves which are in the same direction as the previous move come at a -5 cost, adjust to suit.

(see my edit above)

When I first saw the post, there was indeed already a bunch of g_modifier+=4 in 4 of 8 direction cases, (an edit probably)

I have an update on my problem. It seems like my algorithm has problems with concave obstacles (see attached). The path leads slightly in the concave structure, then out again, but it should really go around it. As you see in the screenshot, it doesn't matter whether it is horizontal, vertical or diagonal, so this shouldn't be the error.

I am pretty sure the error lies in the create_path-function, so here is the shortened, wrapped in a class, path-finding-algo:

ac - start-column
ar - start-row
bc - end-column
br - end-row

path.h

path.cpp

I hope this makes it easier for you to help me with my problem.

Thanks!

Well, it seems the diagonal moves are still not considered significantly more costly than straight moves. Any change if g = 15 for them (instead of g = 14) ? or g = 20? or g = 100 ?
Even 14 is an approximation of sqrt(2)/2*10 after all.

I attached the map with g = 20!
The path is now correct, but it takes so much more time to calculate, which can't be right.

edit: and g = 15 is approximately the same as 14.

Lot's of source code to go through. Create an animation much as you have done your screenshots. Show a frame for each iteration in the loop you have in create_path, so that you visually can see how the algorithm works.

Perhaps the most likely problem is that you are checking nodes which wouldn't need to be checked? In that case you will see it immediately if you do the above for debug purposes.

I think I'm stuck there, sorry. The g h and f values on the graph should be enough for someone experienced with A* to troubleshoot further, but I'm not one

edit:
http://www.policyalmanac.org/games/aStarTutorial.htm

http://www.policyalmanac.org/games/heuristics.htm
I made you reinvent the wheel.
Today's lesson: When in doubt, ask google.

I will look into your suggestions, thanks!

Have you tried using another metric (weight function, or whatever the name is in graph theory) weigh the edges? Right now, you're using ; try using instead and see if that helps.

I'm not sure if it will; from the description of the problem it sounds like nodes aren't properly recalculated or updated when you backtrack through the closed list, but I haven't looked at your code in detail. I also haven't touched my own in several years, so I'm probably a bit rusty on the details.

I don't know A* but I've implemented a path finder like yours, only I never implemented diagonal movements. Do you have trouble with your code or with your algorithm? Or do you want us to find out that?

My algo checks every single possible cell recursively, which takes time, but the result is the shortest path.

I have tried A-star a long time ago (2003) in Aether, We used the manhattan distance formula and it worked great. I tried other methods but it seems that this one was optimal for our game which uses 8 directions. You could try visiting this site for more information.

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S8

Hope this helps.