I had this A* algorithm, and i was changing some code, while testing it, i got some results similiar to those you just posted, i was intrigued.

It turns out the funtion was returning errors every single time very early in the processing fase, so it spent little time actually processing, because of a bug.***hint***

Yes, I had some code on here in another thread with an A* algorithm. It was flawed because of the way I handled repeatedly searched nodes.

I will go ahead and test out my new one a bit more. From tests with other A* algorithms, mine seems to output the same results.

Check with a complete A* algorithm, with the open and closed lists.

Why did you delete the first post?

I deleted the first post till I verified it against another A* search.

Well, I coded an alternative A* search like the one found in Game Programming Gems using open and closed lists. I used stl methods for all the required data structures. The results it gave were the same as my results, but that algorithm was quite a bit slower.

As a note, I did notice that my A* implementation is VERY similar to some other optimized versions of A*. I just went about it in a slightly different way.

If you tried to do what I did, then you probably got it wrong somehow. The code I posted is misleading in a couple of parts if you don't know the types of node classes I used.

I should probably call it an optimization for the best-first search. I don't change anything that makes A* what it is. I just change the best-first part and redundant node checking of the method. I have applied the same optimization to my uniform cost and greedy searches. Heck, even my uniform cost is pretty fast now.

As far as whether or not it is optimal and complete. Well, I am using euclidean distance. I guess that means 100% since the heuristic doesn't over-estimate.

I didn't use a list for my open nodes, instead I had a priority queue based on path length, so I could always pick the shortest trivially (I used std::multi_map)

The closed nodes I stored in a std::map from a location (x,y) to the node, so I could find out whether there was a closed node in a location quickly.

So in fact, neither of them was a "list"

Mark

The point is not wether he is using lists or not, no one uses lists for a decent A* algorithm anyway. The point is that, this guy is saying he has an implementation that can calculate 1000000 paths in 6 seconds in a 1000x1000 map.

That is just wrong! A million PIV cluster couldn't do that!

You said you already tested against another implementation and the results were the same so repost the code.

[Edited by - White Rabbit on September 23, 2004 8:45:38 AM]

Quote: Original post by White Rabbit
The point is not wether he is using lists or not, no one uses lists for a decent A* algorithm anyway. The point is that, this guy is saying he has an implementation that can calculate 1000000 paths in 6 seconds in a 1000x1000 map.

That is just wrong! A million PIV cluster couldn't do that!

You said you already tested against another implementation and the results were the same so repost the code.

Where did I say those things? The time it takes my A* to run is just sqrt(runtime(regular-A*)) from the tests that I have done. That is just because I eliminated a O(n) search in the inner loop which is what every other one has done.

If you want to know, it takes my algorithm about 18 seconds to check through all one million nodes in a graph where each vertex has 4 connections. This is the case when the goal is not in the search space. Now, that is ONE (1) search. Where exactly did you get me saying that I generated 1000000 paths in 6 seconds?

In the first post you deleted.

Well, perhaps what I wrote was a bit misleading. If you want, I can send you the full source code of all my searches.