Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Path-finding issue

This thread is locked; no one can reply to it. rss feed Print
Path-finding issue
imaxcs
Member #4,036
November 2003

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! :)

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

imaxcs
Member #4,036
November 2003

Quote:

Is the the minimum amount of code?

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

Quote:

Perhaps you could narrow it down to say a function that has the problem? Is it create_path?

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.

Quote:

Explain what c, r, g, h, and f are.

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.

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

imaxcs
Member #4,036
November 2003

Quote:

Looks to me like you can only create unidirectional paths with your method.

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

Quote:

Why aren't nodes stored as a graph where the links contain the g, h, and f?

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

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

imaxcs
Member #4,036
November 2003

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.

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Audric
Member #907
January 2001

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))

CGamesPlay
Member #2,559
July 2002
avatar

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.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

Audric
Member #907
January 2001

(see my edit above)

imaxcs said:

I changed the g-value to 14 instead of ten for all diagonal movements

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)

imaxcs
Member #4,036
November 2003

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

1#ifndef __PATH_H
2#define __PATH_H
3 
4#include <deque>
5#include <list>
6#include <iostream>
7#include <algorithm>
8#include <vector>
9 
10#include "node.h"
11 
12using std::deque;
13using std::list;
14using std::cout;
15using std::endl;
16using std::cin;
17using std::random_shuffle;
18using std::vector;
19 
20class CPath
21{
22 private:
23 const static int MAX_NODE_CHECKS = 1000;
24 const static int MAPSIZE = 20;
25 protected:
26 list<CNode*> openlist;
27 list<CNode*> closedlist;
28 list<CNode*> path;
29 public:
30 inline CPath() {}
31 inline virtual ~CPath() {}
32 inline CPath(const CPath& src) {}
33 
34 int get_h(int ac, int ar, int bc, int br);
35 int get_g(int ac, int ar, int bc, int br);
36 bool node_valid(int c, int r);
37 list<CNode*>::iterator node_in_list(int c, int r, list<CNode*>& list_);
38 void delete_list(list<CNode*>& list_);
39 list<CNode*>::iterator get_best_f(list<CNode*>& list_);
40 bool create_path(const vector< vector<char> >& map, int ac, int ar, int bc, int br, int bw, int bh);
41 
42 void clear(void);
43 
44 inline list<CNode*>::const_iterator get_path_begin(void) const { return (path.begin()); }
45 inline list<CNode*>::const_iterator get_path_end(void) const { return (path.end()); }
46 inline list<CNode*>::const_iterator get_openlist_begin(void) const { return (openlist.begin()); }
47 inline list<CNode*>::const_iterator get_openlist_end(void) const { return (openlist.end()); }
48 inline list<CNode*>::const_iterator get_closedlist_begin(void) const { return (closedlist.begin()); }
49 inline list<CNode*>::const_iterator get_closedlist_end(void) const { return (closedlist.end()); }
50};
51 
52#endif

path.cpp

1#include "path.h"
2 
3int CPath::get_h(int ac, int ar, int bc, int br)
4{
5 int delta_x = abs(ac - bc);
6 int delta_y = abs(ar - br);
7 return (static_cast<int>(fabs(sqrt(pow(delta_x, 2) + pow(delta_y, 2)) * 10.0f)));
8 //return ((abs(ac - bc) + abs(ar - br)) * 10);
9}
10 
11int CPath::get_g(int ac, int ar, int bc, int br)
12{
13 int g = 10;
14 
15 if (ac != bc && ar != br)
16 g += 4;
17 
18 return g;
19}
20 
21bool CPath::node_valid(int c, int r)
22{
23 if (c > MAPSIZE - 1 || c < 0 || r > MAPSIZE - 1 || c < 0)
24 return false;
25 return true;
26}
27 
28list<CNode*>::iterator CPath::node_in_list(int c, int r, list<CNode*>& list_)
29{
30 list<CNode*>::iterator it = list_.begin();
31 while(it != list_.end())
32 {
33 if ((*it)->get_c() == c && (*it)->get_r() == r)
34 return it;
35 *it++;
36 }
37 return 0;
38}
39 
40void CPath::delete_list(list<CNode*>& list_)
41{
42 list<CNode*>::iterator it = list_.begin();
43 while(it != list_.end())
44 delete *it++;
45}
46 
47list<CNode*>::iterator CPath::get_best_f(list<CNode*>& list_)
48{
49 list<CNode*>::iterator best = list_.begin();
50 list<CNode*>::iterator it = list_.begin();
51 while(it != list_.end())
52 {
53 if ((*it)->get_f() < (*best)->get_f())
54 best = it;
55 it++;
56 }
57 return best;
58}
59 
60bool CPath::create_path(const vector< vector<char> >& map, int ac, int ar, int bc, int br, int bw, int bh)
61{
62 
63 // see, if we can return immediately
64 if (ac == bc && ar == br)
65 return true;
66 
67 // add the current node to the closedlist
68 openlist.push_front(new CNode(ac, ar, 0, get_h(ac, ar, bc, br)));
69 
70 // create a target-node ( not in one of the lists ), so we can use target_reached() more easily
71 //const CNode* tar = new CNode(target->get_c(), target->get_r(), 0, 0);
72 
73 // set the current node, which will be altered during the walk through the map
74 const CNode* cur = openlist.front();
75 
76 while(cur->get_c() != bc || cur->get_r() != br)
77 {
78 int c, r;
79 int i;
80 
81 // check, if the openlist is empty or the closedlist too full
82 if (!openlist.size() || int(closedlist.size()) > MAX_NODE_CHECKS)
83 return false;
84 
85 // put the node with the best f-value in the closedlist
86 list<CNode*>::iterator best_f = get_best_f(openlist);
87 closedlist.push_front(*best_f);
88 openlist.erase(best_f);
89 
90 // change the cur-variable
91 cur = *best_f;
92 
93 // add the surrounding nodes to the openlist
94 for(i = 0;i < 8;i++)
95 {
96 c = cur->get_c();
97 r = cur->get_r();
98 
99 if (i == 0)
100 c++;
101 else if (i == 1)
102 c--;
103 else if (i == 2)
104 r++;
105 else if (i == 3)
106 r--;
107 else if (i == 4)
108 {
109 c++;
110 r++;
111 }
112 else if (i == 5)
113 {
114 c--;
115 r++;
116 }
117 else if (i == 6)
118 {
119 r--;
120 c++;
121 }
122 else if (i == 7)
123 {
124 r--;
125 c--;
126 }
127 
128 int g = get_g(cur->get_c(), cur->get_r(), c, r);
129 
130 if (node_valid(c, r) && map[c][r] != '1' && node_in_list(c, r, closedlist) == 0)
131 {
132 list<CNode*>::iterator node_in_openlist = node_in_list(c, r, openlist);
133 if (node_in_openlist == 0)
134 openlist.push_front(new CNode(c, r, cur->get_g() + g, get_h(c, r, bc, br), cur));
135 else if ((*node_in_openlist)->get_parent()->get_g() > cur->get_g())
136 {
137 int g = get_g(cur->get_c(), cur->get_r(), (*node_in_openlist)->get_g(), (*node_in_openlist)->get_g());
138 
139 (*node_in_openlist)->set_parent(cur);
140 (*node_in_openlist)->set_g(cur->get_g() + g);
141 (*node_in_openlist)->recalculate_f();
142 }
143 }
144 }
145 }
146 
147 // coming here, it means that there is a valid path
148 // now track back the way to the start by accessing the parent and save it in the path-variable
149 while(cur != closedlist.back())
150 { // while start not reached
151 path.push_back(new CNode(*cur));
152 cur = cur->get_parent();
153 }
154 
155 return true;
156}
157 
158void CPath::clear(void)
159{
160 delete_list(path);
161 delete_list(openlist);
162 delete_list(closedlist);
163}

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

Thanks! :)

Audric
Member #907
January 2001

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.

imaxcs
Member #4,036
November 2003

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.

kentl
Member #2,905
November 2002

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.

Audric
Member #907
January 2001

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

Quote:

(heuristic)... slightly overestimates the remaining distance (...) On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short

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

imaxcs
Member #4,036
November 2003

I will look into your suggestions, thanks! :)

Evert
Member #794
November 2000
avatar

Have you tried using another metric (weight function, or whatever the name is in graph theory) weigh the edges? Right now, you're using <math>\left|x\right| + \left|y\right|</math>; try using <math>x^2 + y^2</math> 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.

Johan Halmén
Member #1,550
September 2001

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.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Homer Cuevas
Member #3,055
December 2002
avatar

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. :)

_______________________________________________________
[Website]

Go to: