next »

[Tycho Brahe]

Hi TechTigs©

I've got a problem with my astar algorithm.
It has no problem finding a path to the target, however said paths always seem to be broken when they turn in empty space. For example take a look at this:
http://fc04.deviantart.net/fs71/f/2010/207/3/4/AStar_problem_by_14113.png

The dots represent nodes examined trying to find a path and the stars represent the path itself. The two '@' symbols are the start and end, with the top left being the start and the bottom right being the end.

For some reason when creating a path down in this example, the path not only breaks, but the nodes examined are in a larger area than they should be. this doesn't only happen when going from l-r to u-d but it does happen when changing direction once the examined node has the same x or y value of the target.

Has anyone had this problem before? or suggestions on what's causing it/ways of working around it. Any suggestions would be welcomed.

and before anyone asks, code is here: http://piratepad.net/De9HFPkb1j

It is a little convoluted and I have way too many classes than I need, but its still early stages.

Thanks in advance!

[shrimp]

When you say "breaks" do you mean that the backwards tracing through the tree of explored notes stops?

Also, you say it explores more nodes than it should, but it looks like it's explored a weird set of nodes. I'd expect it to be hugging the walls in the centre to get the shortest path...

Oh and piratepad.net gave me a "504 Gateway Time-out"

[nikki]

i could not see the code, but i believe there are some more problems... especially since your code needed 85000 millisecs for finding a very simple path (wich isn't the shortest path as far as i can tell)

[Tycho Brahe]

When you say "breaks" do you mean that the backwards tracing through the tree of explored notes stops?

Also, you say it explores more nodes than it should, but it looks like it's explored a weird set of nodes. I'd expect it to be hugging the walls in the centre to get the shortest path...

Oh and piratepad.net gave me a "504 Gateway Time-out"

Yes, by breaking I mean the backtrace fails. And I agree it does look like its going a weird route, however thats due to alterations I made to the heuristic, as before it was exploring in some REALLY strange directions, I'll change it back and try again.
I'm also getting the errors now for the piratepad, so I'll just post the code below

i could not see the code, but i believe there are some more problems... especially since your code needed 85000 millisecs for finding a very simple path (wich isn't the shortest path as far as i can tell)

As far as I know the time is mainly thanks to drawing the map and all the explored nodes every iteration.
[EDIT]
Also, its probably because I'm bubble sorting the open list, which is a really slow way to do things, but this is just a preliminary attempt
[/EDIT]

The code should compile in any standard c++ compiler, it just uses the standard library and some maths and time headers.

Code:

#include <iostream>
#include <cstdlib>
#include <vector>
#include <time.h>
#include <math.h>
#define GetRandom( min, max ) ((rand() % (int)(((max) + 1) - (min))) + (min))

const int width = 79;
const int height = 79;
const char empty = ' ';
const char filled = '.';
const char wall = 176;
const char path = 219;

class node
{
public:
	int x,y;
	double g_score, h_score, f_score;
};
class map_node
{
public:
	char data;
	int p_x, p_y;
	void previous(int x, int y)
	{
		p_x = x;p_y=y;
	}
	bool operator== (map_node a)
	{
		return this->data==a.data;
	}
	bool operator== (char a)
	{
		return this->data==a;
	}
	map_node& operator= (char a)
	{
		data = a;
		return *this;
	}
};

struct simple_coord
{
	int x,y;
};
map_node map[width][height]; //map
void draw_map()
{
	for(int i = 0;i<width;i++)
	{
		for(int j = 0;j<height;j++)
		{
			std::cout<<map[i][j].data;
		}
		std::cout<<"\n";
	}
}
void print_list(std::vector<node> list)
{
	node holder;
	for(unsigned int i=0;i<list.size();i++)
	{
		holder = list.at(i);
		std::cout<<holder.h_score<<",";
	}
}
std::vector<node> sort_list(std::vector<node> list)
{
	node a;
	node b;
	node a_holder;
	bool swapped = true;
	int swap_number = 0;
	//std::cout<<"swaps:";
	while(swapped == true)
	{
		swapped = false;
		for(unsigned int i = 1;i<list.size()-1;i++)
		{
			a = list.at(i);
			b = list.at(i-1);
			if(a.f_score<b.f_score)
			{
				swap_number++;
				//std::cout<<swap_number<<",";
				swapped = true;
				a_holder = a;
				list[i] = b;
				list[i-1] = a_holder;
			}			
		}
	}
	return list;
}

void get_path(simple_coord finish_point, simple_coord start_point)
{
	int x,y,t_x,t_y;
	x = finish_point.x;y=finish_point.y;
	while(x!=start_point.x&&y!=start_point.y)
	{
		map[x][y] = '*';
		t_x = x;t_y = y;
		x = map[t_x][t_y].p_x;
		y = map[t_x][t_y].p_y;
	}
	map[start_point.x][start_point.y] = '@';
	map[finish_point.x][finish_point.y] = '@';
}
int main(int argc, char** argv)
{
	//setup
	bool finished;
	int pause_int; //integer to hold input to pause the console
	clock_t start_t,end_t,diff_t;//timing variables
	std::vector<node> node_list; //open_list
	node start_node; //starting node
	node end_node; //the target node
	start_node.x = 3; //x
	start_node.y = 3; //y
	start_node.g_score = 0;//set up the initial g_score;
	end_node.x = 75; //x
	end_node.y = 75; //y
	finished = false;
	//initialising map
	for(int i = 0;i<width;i++)
	{
		for(int j = 0;j<height;j++)
		{
			map[i][j] = empty;
		}
	}
	//creating squares
	for(int i = 11;i<71;i++)
	{
		if(i!=35)
		{
			map[i][11] = wall;
			map[i][70] = wall;
			map[i][34] = wall;
			map[i][36] = wall;
			map[11][i] = wall;
			map[70][i] = wall;
			map[34][i] = wall;
			map[36][i] = wall;
		}
	}
	for(int i =0;i<79;i++)
	{
		map[i][0] = wall;
		map[i][78] = wall;
		map[0][i] = wall;
		map[78][i] = wall;
	}
	//Randomly seed map
	/*for(int i = 0;i<79*79/3;i++)
	{
		map[GetRandom(0,79)][GetRandom(0,79)] = wall;
	}
	for(int i =0;i<70;i++)
	{
		map[30][i] = wall;
	}*/
	map[start_node.x][start_node.y] = filled;//fill start node
	map[end_node.x][end_node.y] = empty;//keep empty node empty
	//start timer
	start_t = clock();
	//preliminary info render
	std::cout<<"Beginning:\nInitial Setup\n";
	draw_map();//preliminary map draw
	//starting algorithm

	node_list.push_back(start_node);
	std::cout<<"\n";
	while(node_list.size()>0&&finished==false)
	{
		system("cls");
		draw_map();
		//std::cout<<".";
		//for(int i = 0;i<node_list.size();i++)
		//{			
			node current_node,holder_node;
			node_list = sort_list(node_list);
			current_node = node_list.front();
			node_list.erase(node_list.begin());
			bool n,e,s,w;
			w=current_node.x>0;
			e=current_node.x<width-1;
			n=current_node.y<height-1;
			s=current_node.y>0;
			if(current_node.x==end_node.x&&current_node.y==end_node.y)
			{
				finished=true;
			}
			else
			{
				if(w)
				{
					holder_node.x=current_node.x-1;
					holder_node.y=current_node.y;
					if(map[holder_node.x][holder_node.y] == empty)
					{						
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+2;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=2.00001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;

						map[holder_node.x][holder_node.y] = filled;
						node_list.push_back(holder_node);
					}
				}
				if(e)
				{
					holder_node.x=current_node.x+1;
					holder_node.y=current_node.y;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+2;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=2.00001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;

						map[holder_node.x][holder_node.y] = filled;
						node_list.push_back(holder_node);
					}
				}
				if(s)
				{
					holder_node.x=current_node.x;
					holder_node.y=current_node.y-1;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+2;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=2.00001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;

						map[holder_node.x][holder_node.y] = filled;
						node_list.push_back(holder_node);
					}
				}
				if(n)
				{
					holder_node.x=current_node.x;
					holder_node.y=current_node.y+1;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+2;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=2.00001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;

						map[holder_node.x][holder_node.y] = filled;
						node_list.push_back(holder_node);
					}
				}
				/*if(w&&s)
				{
					holder_node.x=current_node.x-1;
					holder_node.y=current_node.y-1;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y] = filled;
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+1;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=1.0000001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;
						node_list.push_back(holder_node);
					}	
				}
				if(e&&s)
				{
					holder_node.x=current_node.x+1;
					holder_node.y=current_node.y-1;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y] = filled;
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+1;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=1.0000001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;
						node_list.push_back(holder_node);
					}
				}
				if(w&&n)
				{
					holder_node.x=current_node.x-1;
					holder_node.y=current_node.y+1;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y] = filled;
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+1;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=1.0000001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;
						node_list.push_back(holder_node);
					}	
				}
				if(e&&n)
				{
					holder_node.x=current_node.x+1;
					holder_node.y=current_node.y+1;
					if(map[holder_node.x][holder_node.y] == empty)
					{
						map[holder_node.x][holder_node.y] = filled;
						map[holder_node.x][holder_node.y].p_x = current_node.x;
						map[holder_node.x][holder_node.y].p_y = current_node.y;

						holder_node.g_score=current_node.g_score+1;
						holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
						holder_node.h_score*=1.0000001;
						holder_node.f_score =holder_node.g_score+holder_node.h_score;
						node_list.push_back(holder_node);
					}
				}*/
			}
		//}		
	}
	std::cout<<"-----\n";
	simple_coord finish, start;
	finish.x = end_node.x;
	finish.y = end_node.y;
	start.x = start_node.x;
	start.y = start_node.y;
	get_path(finish,start);
	end_t = clock();
	diff_t = end_t-start_t;
	std::cout<<"took "<<diff_t<<" milliseconds\n";
	draw_map();
	std::cin>>pause_int;
	return 0;
}

[Tycho Brahe]

Hmm, thats even worse. Now it evaluates EVERY accessible node between the start and endpoint, gives even worse performance, and STILL doesnt give a complete path 

I think I'm going to re-write parts of it to bring it closer to straight a*

Wish me luck 

[st33d]

I've got an A* algorithm I'm tuning up at home that has a number of optimisations (including aborting a search early and giving the best route found so far - useful for impossible or difficult to reach targets). I'll post it up when I've finished tweaking it tonight.

I noticed a few things:

You don't specify an open and closed list. That's what makes an A* search, a search is not A* without those two lists (or so wikipedia says) - by putting nodes on either list you find the optimal route.

You're multiplying "h" for some reason. Usually the safest part to mess with is "g", which implies the cost of using that node, not how far it is from target.

[Tycho Brahe]

I do have an open list, it may just be that I've named it strangely. You're right about the closed list though, what I'm trying instead is using the map to define if a node has been visited or not, and storing the f/g/h_score long term. The h modification is based on a page about heuristics I read, believe me, without it it tries to evaluate Every node between the start and the end.

I don't think it's the h that's the problem, I've tried running it without it and got the same problems, so I think im going to alter my code more to bring it closer to vanilla a* and see if thy works.

[st33d]

The A* I'm using is an optimised version of the one here if you're interested:

http://www.tom-carden.co.uk/p5/a_star_web/applet/index.html

[Tycho Brahe]

Thanks for the link!

I've done a couple of optimisiations, such as stopping the bubble sorts every iteration, and managed to get it down to 382 milliseconds. However, its still trying to check every node between it and the target and is still not finding a path...

[Tycho Brahe]

YAY!

I've tracked down the problem, and it wanst in my algorithm, it was in the way I was tracing the route.

What I was doing was this:

Code:

while(x!=start_point.x&&y!=start_point.y)
{
 //Get the previous node/point
}

and this would stop as soon as the path got to the x/y coordinate of the start point.

What I've changed it to is this:

Code:

while(x!=NULL&&y!=NULL)
{
  //Get the previous node/point
}

Which stops as soon as it finds a node with null as its last point, which the start node would have as its previous x/y had not been initialised.

[shrimp]

Ah just noticed you got it working... anyway, here's what I typed!


The key thing about A* is the "distance-plus-cost heuristic" and the fact that the heuristic "cost to goal" value should be an underestimate, but you can bend that second point.

The open/closed lists are just a requirement for that general family of algorithms to run in a non-recursive manner. You *really* don't want to mess about with trying to avoid having either of them, certainly not before having a working implementation.

No thread on A* is complete without a link to this:
http://theory.stanford.edu/~amitp/GameProgramming/

In this code...

Code:

						holder_node.g_score=current_node.g_score+2;
holder_node.h_score=abs(holder_node.x-end_node.x)+abs(holder_node.y-end_node.y);
holder_node.h_score*=2.00001;

You seem to be saying that each step costs 2, but also multiplying the estimate to goal by 2 (and a bit)... Why not just make steps cost 1?
Also consider trying other heuristics instead of Manhattan distance... maybe straight line distance?

That .00001 bothers me a little bit... shouldn't really be needed til you get to fine tuning it, as it breaks/bends the rule of A* that the heuristic should be an underestimate (or exact estimate).

(Someday I hope to have an excuse to play with D*, LPA* and all those others linked on the Wikipedia page...)

[st33d]

Well done!

Got that optimised A* uploaded now:

getPath() in this file:

http://github.com/st33d/red-rogue/blob/master/src/com/robotacid/ai/DungeonGraph.as

And the A* nodes are these (a Pixel object is simply a x,y int pair, mDist() is Manhattan distancing)

http://github.com/st33d/red-rogue/blob/master/src/com/robotacid/ai/Node.as

Might give you some optimisation options if you're interested.

[Tycho Brahe]

Thanks guys!

@ed
yeah, the 2 thing was just a trial to see what would happen, I've removed it and the multiplication.

The lack of a closed list was thanks to the fact that I based this off a flood-fill algorithm that I'd written, so I already had some way of checking to see if I'd visited a node.

I tried pythagoras distance as well, but it didn't really give very good results (read, it broke completely) but thats probably more to do with the situation it was working in than anything else.

@st33d
Thanks. Am i right in thinking that the previous node section of a node just causes it to stack up? I considered using pointers and also just coordinates which could be searched for in the closed list, however the latter could be really slow, and the former might get a bit confused...

Also, it seems like you dont have a closed list? How are you managing visited nodes then? In a similar manner to me? or something different...

[st33d]

It uses pointers because it's a platform game, some of the nodes are down on the floor. If you migrate from using a top-down grid, you need pointers.

The parent node system sets up a path through the nodes, so all you have to do is follow from the finish node through the parents back to the start.

The closed list I realised is simply a matter of being a member of the closed list. That's what the closedId variable is. The closedId is set to the searchId, thus making it on the closed list. By having a searchId instead of a boolean, I don't have to reset the map before a search, I just have to compare and set to the current searchId.

[Tycho Brahe]

Ah, clever Idea for the searchID, Mind if i steal it?

Thats what I was thinking for the closed list as well. Basically its just a way of making sure nodes aren't added to the open list more than once per search.

[st33d]

Open sauce dude. 

[Tycho Brahe]

AH! The answer to all my problems came to me while I was sleeping.

Basically, nodes just outside of the area between the start and end nodes were never being selected as the lowest f_score nodes, even though they appeared (in debugging) to be being added to the open_list.

I realised that the problem was in my sorting algorithm. It was an adaptation of insertion sort, whereby I would iterate through the open list, adding in the new nodes when the f_score was less than the f_score of the node at the current position in the open list. The problem came when the new nodes f_score was never less than any of the existing nodes, and thus wasn't being inserted. I simply put in a check to see if the node had been added, and if not it would be added at the end.

It works now  

[EDIT]
Also, st33d, how fast is your a* implementation? I'm getting a minimum of about 105ms for it to find a path (at its simplest) in a graph (grid) of 79*79. What kind of speeds are you getting, is it faster than mine, or is that about the fastest a* will get.

[st33d]

I'm running it in AS3, so the speed difference isn't really comparable.

However, 105ms in C doesn't sound right. That's 0.1 seconds to do a really basic search. A* is supposed to be really, really fast. I can only recommend trying to implement classic A* from a tutorial and then compare that to your own code - then the issue might become obvious.

You don't need to do any sorting by the way. You just need to find the lowest "f", a sort is going to take much much longer than iterating through once for the lowest value. No sorting!

 

[Tycho Brahe]

I've taken another look at my code and found a ton of optimisations I could do, and done them. I've also tried compiling in release mode and that's brought the time down too. Now it runs at about 4ms for a simple path.

Its not true sorting, it simply goes through the list to find the position of where it should be inserted. I'm not 100% but I'd have thought that it would be quicker than iterating through the list to find the lowest f_score? For my method you typically only have to iterate through about 10-30% of the list before you insert, as new nodes have a lower f_score. When you get the lowest you simply get the first node in the list. With your method (assuming that new nodes are inserted at the back) I'd have thought that you'd be iterating through more like 50-90% of the list before you found the node. I could be wrong though.

[st33d]

Take this bit here:

Code:

for(j = 0; j < current.connections.length; j++){
	adjacentNode = current.connections[j];
	if(adjacentNode.closedId != searchId){
		if(adjacentNode.openId != searchId) {
			open.push(adjacentNode);
			adjacentNode.openId = searchId;
			adjacentNode.closedId = 0;
			adjacentNode.parent = current;
			adjacentNode.setF(finish);
		} else {
			// double check open nodes for a shorter route
			if(adjacentNode.g > current.g + current.mDist(adjacentNode)){
				adjacentNode.parent = current;
				adjacentNode.setF(finish);
			}
		}
	}
}

One thing I noticed in Tom Carden's implementation was that he was double checking connections. Because the the route corrects itself for new findings, the value of F on old nodes keeps changing. New nodes may not after all be better.