I''m using the A* system for doing some simple path finding. It pretty much works okay. I get a path from my start x,y to my end x,y. I do have a few problems though. One of them is that the path I get isn''t "smart." The path will go out of the way, but still get to the destination. This is fine it''s just not intelligent, and also results in more moves than it should take. My other problem is that if the target desination is inside of an unreachable space the system seems to freeze up. I do not know if it is stuck inside of an endless loop, or if it is just taking a long time to check all remaining tiles on the map.

|```````|
| Dest  |
|_______|    Start
 

I''m using a modified version of A* that I found on the internet (Can''t remember who did it atm). I converted it to use vectors, and I may or may not have messed things up in the process. I''ve tried fixing the problems, but I do not know a lot about A*. I''d really like to solve the endless loop/check all tiles problem mentioned above. Does anyone know what can cause what I''ve described?

Your example isn''t clear; are you trying to say you get the green line when you really want the red? Personally I can''t see how you''d easily force the first bit (without a deliberate hack) but the second part is obviously suboptimal. There are lots of examples of people making errors in their A* implementation (some posted recently in this forum), presumably because there''s quite a few key details that are glossed over in the usual tile-based implementations due to the uniform node properties, but which may well become very important when you start using vectors and so on. I think a little pseudocode from you would help to narrow down where the problem lies.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Your algorithm produces the green path because it has no way of seeing the blocking wall that surrounds the goal until it actually gets there. Thus, any node along the green path (and red path for that matter) has to have a heuristic that takes into account the wall. This is not reasonable as it would require you to actually compute (or accurately underestimated) path lengths to the goal from any node. The point of A* is that you shouldn''t have to do this, just estimate the path length using an heuristic. There are ad hoc solutions you can implement... with the usual limitations.

Some more information about your domain would help to work out an optimal solution method. How large is the domain? Do you need to use vectors because of an implementation limitation? Are you dealing with a softbot or a robot (the latter implying that yes, you do need vectors... although that''s not strictly true!). Do you need the resolution of movement provided by vectors? Can you obtain additional information cheaply (e.g., visibility data from a given location)? Is the map static or dynamic? Is the map available to the agent or just the path?

Some or all of this information would greatly enhance our ability to assist you in improving your pathfinder.

Cheers,

Timkin

In the little picture I posted the path that the bot takes is green. It's a correct, but stupid path. Timkin, I think you misunderstood when I mentioned vectors. I meant the STL vectors available in C++. The map is 100x100 tiles. Most obstacles are static (walls, trees, furniture,etc), but there are monsters that move around. Currently I just recalculate a path whenever a monster gets bumped into. That's been working fine, though it may be a cheap solution. The entire map with all its data is available when looking for a path. At the moment when calculating if the tile is walkable I just call an IsSolid function on the map tile. Should I post the class I am using, and perhaps someone could spot my mistakes and suggest improvments?

[edited by - ddh on January 11, 2004 7:26:10 PM]

quote:

---

Original post by ddh
In the little picture I posted the path that the bot takes is green. It''s a correct, but stupid path.

---

Technically, if you''re using A*, it''s an incorrect path, as it should produce the shortest path if one is available. For example, turning left when it is parallel to the ''door''.

quote:

---

Timkin, I think you misunderstood when I mentioned vectors. I meant the STL vectors available in C++. The map is 100x100 tiles. Most obstacles are static (walls, trees, furniture,etc), but there are monsters that move around. Currently I just recalculate a path whenever a monster gets bumped into. That''s been working fine, though it may be a cheap solution. The entire map with all its data is available when looking for a path. At the moment when calculating if the tile is walkable I just call an IsSolid function on the map tile.

---

None of that is all that relevant, really. What is important are things like:
- what heuristic do you use to estimate the distances?
- what operations do you perform on the open and closed lists of nodes?
- are all unblocked nodes/tiles of equal weight, or does it cost different amounts to traverse different tiles?

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

All open tiles have the same cost. I''m using the Manhatten distance formula to calculate cost.

This is the class I am using..

astar.h:

class AStar{	struct NODE	{		char x, y;		long f;		int	Parent, ID;	};	void ConstructPath(NODE n);	bool IsInOPEN(NODE n);	bool IsInCLOSED(NODE n);	void RemoveFromOPEN(NODE n);	void GenerateSuccs(NODE n);	void GenerateSucc(int x,int y,int Parent);	NODE GetBestNode();	NODE GetNodeFromCLOSED(int ID);	int cID;	NODE nStart,nGoal;	vector<NODE> OPEN;	vector<NODE> CLOSED;public:	vector<NODE> PATH;	bool FindPath(POINT StartPos,POINT EndPos);};

astar.cpp:

void AStar::ConstructPath(NODE n){	NODE nTemp=n;	vector<NODE> AltPath;	while (nTemp.ID != -1) {		PATH.push_back(nTemp);		nTemp=GetNodeFromCLOSED(nTemp.Parent);	}	PATH.push_back(nTemp);	for (int i=(int)PATH.size()-1;i>=0;i--) {		AltPath.push_back(PATH[i]);	}	PATH=AltPath;}bool AStar::IsInOPEN(NODE n){	for (UINT i=0;i<OPEN.size();i++) {		if ((OPEN[i].x == n.x) && (OPEN[i].y == n.y))			return true;	}	return false;}bool AStar::IsInCLOSED(NODE n){	for(UINT i=0;i<CLOSED.size();i++) {		if ((CLOSED[i].x == n.x) && (CLOSED[i].y == n.y))			return true;	}	return false;}void AStar::RemoveFromOPEN(NODE n){	for (UINT i=0;i<OPEN.size();i++) {		if ((OPEN[i].x == n.x) && (OPEN[i].y == n.y)) {			OPEN.erase(OPEN.begin()+i);			return;		}	}}void AStar::GenerateSucc(int x,int y,int Parent){	if ((x<0) || (y<0)) return;	if ((x>=MAP_X) ||(y>=MAP_Y)) return;	if(Map.IsSolid(x,y))		return;	NODE n;	n.x=x;	n.y=y;	n.ID=cID++;	n.Parent=Parent;	n.f = abs(nGoal.x - n.x) + abs(nGoal.y - n.y);	if ((!IsInOPEN(n)) && (!IsInCLOSED(n)))		OPEN.push_back(n);}void AStar::GenerateSuccs(NODE n){	GenerateSucc(n.x  ,n.y-1,n.ID); // Up	GenerateSucc(n.x-1,n.y  ,n.ID); // Left	GenerateSucc(n.x+1,n.y  ,n.ID); // Right	GenerateSucc(n.x  ,n.y+1,n.ID); // Down	RemoveFromOPEN(n);	CLOSED.push_back(n);}NODE AStar::GetNodeFromCLOSED(int ID){	for (UINT i=0;i<CLOSED.size();i++)		if (CLOSED[i].ID == ID)			return CLOSED[i];	return CLOSED[0]; // to silence the warning}NODE AStar::GetBestNode(){	long f=OPEN[0].f;	UINT ArrPos=0;	for (UINT i=1;i<OPEN.size();i++) {		if(OPEN[i].f<f) {		//if (OPEN.f&lt;=f) {<br></font><br>			f=OPEN[<font color=purple>i</font>].f;<br>			ArrPos=i;<br>		}<br>	}<br>	<font color=blue>return</font> OPEN[<font color=purple>ArrPos</font>];<br>}<br><font color=blue>bool</font> AStar::FindPath(POINT StartPos,POINT EndPos)<br>{<br>	PATH.clear();<br>	OPEN.clear();<br>	CLOSED.clear();<br>	cID=0;<br>	<font color=gray>// – Search initialization —————<br></font><br>	NODE n;<br>	n.f=n.Parent=n.ID=-1;<br>	n.x=(<font color=blue>char</font>)StartPos.x;<br>	n.y=(<font color=blue>char</font>)StartPos.y;<br>	nStart=n;<br>	n.f=n.Parent=n.ID=0;<br>	n.x= (<font color=blue>char</font>)EndPos.x;<br>	n.y= (<font color=blue>char</font>)EndPos.y;<br>	nGoal=n;<br><br>	OPEN.push_back(nStart);<br>	<font color=gray>// – Pathfinding ————————-<br></font><br>	<font color=blue>while</font> (!OPEN.empty()) {<br>		n=GetBestNode();<br>		<font color=blue>if</font> ((n.x==nGoal.x) && (n.y==nGoal.y))<br>			<font color=blue>break</font>;<br>		GenerateSuccs(n);<br>	}<br><br>	<font color=blue>if</font> (OPEN.empty())<br>		<font color=blue>return</font> <font color=blue>false</font>;<br>	<font color=blue>else</font> {<br>		ConstructPath(n);<br>		PATH.erase(PATH.begin());<br>		<font color=blue>return</font> <font color=blue>true</font>;<br>	}<br>}<br></pre><!–ENDSCRIPT–><br><br>Thanks for everyone''s input so far.   

The vector issue is irrelevant as Kylotan points out. The problem you face is that to use A*, your heuristic must never overestimate the cost to the goal. That's fine, Manhattan Distance wont do that if you can only move in the four principal directions. However, your heuristic grossly underestimates the cost to the goal and there is a sudden jump in the cost function surface for the tiles adjacent and outside of the wall surrounding the goal. This is what is causing your algorithm to be fooled. Unfortunately, without ad hoc changes given the map, there is no solution (unless you compute exact path lengths from each node to the goal... which negates the point of using search.

Since your map is only 100x100 tiles, then the answer to your problem is to implement the Distance Transform Algorithm. Here's a link to an old thread in which I provide the algorithm:
http://www.gamedev.net/community/forums/topic.asp?topic_id=100389
Given that you're dealing with a regular MxN grid, you might be able to optimise the algorithm further... the implementation described above works for an arbitrary polygonal tiling.

Basically the DT algorithm works on a flood-fill principle from the goal out... and then a gradient descent of cost to the goal. It's very fast on small maps such as yours and gives the shortest path to the goal from any point (that the goal can be accessed from) on the map, meaning that if your goal doesn't move but you have dynamic obstacles, you can always efficiently find a lowest path to the goal given your current location.


Cheers,

Timkin

[edited by - Timkin on January 12, 2004 2:17:19 AM]

Thank you for your response. It seems simple to implement. I will do some googling, and mess around with this at a later time. Currently 3am and I am a bit tired.

edit:

Well I did a little more reading, and went over my code some more. I found out why i wasn't getting smart paths. I was not including the cost of the parent node when I was calculating the new node cost. I've fixed this, and now it seems to work well. It no longer hugs around walls. Sadly I do still have the problem of it taking a very long time (in effect freezing the application) to stop if the goal is unreachable.

[edited by - ddh on January 12, 2004 6:10:56 AM]

quote:

---

However, your heuristic grossly underestimates the cost to the goal and there is a sudden jump in the cost function surface for the tiles adjacent and outside of the wall surrounding the goal. This is what is causing your algorithm to be fooled.

---

Uhm what do you mean with this Timkin, a properly implemented a* shouldnt have any problem with this sort of thing.

I only looked at the code briefly but to me the problem seems to be the

void AStar::GenerateSucc(int x,int y,int Parent) 

function which needs to check if the new parent has a lower cost than the current parent.

quote:

---

Original post by Isokron
Uhm what do you mean with this Timkin, a properly implemented a* shouldnt have any problem with this sort of thing.

---

Mmmm, upon reading what I wrote again I can see how it looks wrong...(and in a sense it is) what I was trying to get at was that if your heuristic grossly underestimates the true cost of getting from a node to the goal, then A* reverts to a greedy search with f(n) ~= g(n), meaning that a lot of time is going to be wasted looking at the wrong path... this is what I meant by being fooled...

...but of course, that wasn''t the problem that ddh was trying to solve... so yes, I''m a bit of an idiot today... I think I got sidetracked between my first and second post. Since ddh has found the solution, then there isn''t much need for this... but... by not including the parent cost, you''re forgetting one of the basic rules of your cost function... that it must be monotonically increasing with depth of the search tree. Since f(n) will always underestimate the true cost, f*(n), and since f(n) should always increase with depth of the tree, then it can be shown that the first path returned by A* (under these conditions) is the optimal path with cost f*(n).

Sorry for my misleading post.

As for the problem with the goal not being accessible... A* cannot help you there ddh. You either need to use an ad hoc check on the map, or implement the DT algorithm, which solves that problem trivially.

Cheers,

Timkin