A* Shocker
Author
I am reviewing the different approaches to pathfinding. yesturday i wrote a class to output the performance of the search so i can compare the results and i was shocked by the results.
For the same start and goal nodes:
Breadth-first Astar
Length of Path 33 33
nodes Searched 311 118
NoOfIterations 310 34
Looks good so far...
Time taken 3223 10039
//using queryperformancecounter.
So even though Astar goes through the search loop nearly 10 times less, it takes nearly three times longer?
I know this is down to the sorting algorithm, i use the STL List sort function.
So... is this method of sorting in-efficient or is that just how long sorting takes.
I should point out that both algorithms still came in at under 1 millisecond so still acceptable.
list sorting is very inefficient. Consider using a std::set or std::map?
But... but that''s what HITLER would say!!
But... but that''s what HITLER would say!!
I assume you are using sorting for open list. It would probably be more efficient to use std:: push_heap() and std:: pop_heap() functions implemented on a std::vector than sorting a std::list. (since you never need a fully sorted open list, only be able to find the node with the minimum total cost)
edit: stupid smiley code
[edited by - SiCrane on March 12, 2003 3:42:10 AM]
edit: stupid smiley code
[edited by - SiCrane on March 12, 2003 3:42:10 AM]
Just because descriptions of A* describe an open list and a closed list doesn''t mean that linked lists are the way to implement it. The descriptions are just talking about the lists abstractly. For the actual implementation of the open and closed lists, structures like trees, heaps, and hash tables should be considered. Look at what operations the lists need to support in deciding what data structure to implement them with.
I use a tree and a linked list to link the leaf nodes one with other. I can walk from a node to its parent going to the root, an from a leaf node directly to the next leaf node.
--------------------------
Rory Gallagher and Chico Science music !!!!!!!
---------------------------
--------------------------
Rory Gallagher and Chico Science music !!!!!!!
---------------------------
Here's a great article on this topic.
A* pathfinding for beginners
I use A* in my engine and I insert new nodes into my open and close list in sorted order. The performance is acceptible.
[edited by - Ironside on March 13, 2003 7:39:15 PM]
A* pathfinding for beginners
I use A* in my engine and I insert new nodes into my open and close list in sorted order. The performance is acceptible.
[edited by - Ironside on March 13, 2003 7:39:15 PM]
Author
Thanks for all the above responce,
I started my studies with the A* for beginners, but i did pay much attention to his heap code, as i am using C++ and not Blitz, maybe i should go and have a re-read.
The ordered insert sounds like the option i shall follow up.
I knew that sorting would slow things down, but i was expecting the sorting to take less time than exploring all the nodes.
Thanks again. Any further advise would be much appriciated.
[edited by - DefCom on March 14, 2003 4:15:04 AM]
I started my studies with the A* for beginners, but i did pay much attention to his heap code, as i am using C++ and not Blitz, maybe i should go and have a re-read.
The ordered insert sounds like the option i shall follow up.
I knew that sorting would slow things down, but i was expecting the sorting to take less time than exploring all the nodes.
Thanks again. Any further advise would be much appriciated.
[edited by - DefCom on March 14, 2003 4:15:04 AM]
I implemented my A* using static arrays. The purpose of the array is to detect whether I am on the closed or open list.
e.g.
astarmap[ x ][ y ].isOpen();
astarmap[ x ][ y ].isClosed();
then I have functions
astarmap[ x ][ y ].getParentX();
astarmap[ x ][ y ].getParentY();
to get the parent and
astarmap[ x ][ y ].getPreviousX();
astarmap[ x ][ y ].getPreviousY();
astarmap[ x ][ y ].getNextX();
astarmap[ x ][ y ].getNextY();
to get the previous and next nodes. I find this much faster
on small maps about 60x60 worked fine.
To see its demo, you can visit www.websamba.com/hammer2k/ and
download our game. Hope this helps!
e.g.
astarmap[ x ][ y ].isOpen();
astarmap[ x ][ y ].isClosed();
then I have functions
astarmap[ x ][ y ].getParentX();
astarmap[ x ][ y ].getParentY();
to get the parent and
astarmap[ x ][ y ].getPreviousX();
astarmap[ x ][ y ].getPreviousY();
astarmap[ x ][ y ].getNextX();
astarmap[ x ][ y ].getNextY();
to get the previous and next nodes. I find this much faster
on small maps about 60x60 worked fine.
To see its demo, you can visit www.websamba.com/hammer2k/ and
download our game. Hope this helps!
quote:Original post by Hammer2k2
I implemented my A* using static arrays. The purpose of the array is to detect whether I am on the closed or open list.
e.g.
Yeah, that''s how I did my closed list, just set a flag on the actual map tile. However, there''s two drawbacks: 1) it''s not thread-safe - you can''t search two paths at once and 2) you need to reset all the flags to zero every time you search a new path.
Of course, both of those problems go away if you have a special array just for the closed list, but then you''re wasting a lot of memory.
Also, you can''t structure your open list like that, you need to be able to pick the node with the lowest cost off the open list - how would do it with your thing?
If I had my way, I''d have all of you shot!
codeka.com - Just click it.This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
