🔒 Locked

A* Shocker

Started by DefCom Mar 12, 2003 at 2:21 AM 13 replies 1.3k views

Original Post

Mar 12, 2003 at 2:21 AM

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.

Sneftel

296

Sneftel

Mar 12, 2003 at 2:29 AM

list sorting is very inefficient. Consider using a std::set or std::map?

But... but that''s what HITLER would say!!

SiCrane

Mod

473

SiCrane

Mar 12, 2003 at 2:41 AM

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]

manuelb

Mar 13, 2003 at 4:50 AM

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

Timkin

149

Timkin

Mar 13, 2003 at 6:31 PM

You don''t need to sort the list if you do an ordered insert (and I find it more efficient).

Ironside

Mar 13, 2003 at 6:38 PM

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]

DefCom

Author

DefCom

Mar 14, 2003 at 2:34 AM

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]

Hammer2k2

Mar 14, 2003 at 4:37 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!

Dean Harding

Mar 14, 2003 at 5:05 AM

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.

Syntax

Mar 15, 2003 at 1:32 PM

One of the best ways to optimize the A* algorithm, is optimizing its priority queues (don''t flame me for being obvious yet) One of the best methods is using a binary heap

http://www.purists.org/pqueue/

This allows for quick insertion and removal at O(log n).

you will find that if you can reduce the time that it takes to insert and remove items from the priority queue, your A* will run much faster..let me know if this helps..

-Lucas

Argus

Mar 18, 2003 at 3:15 AM

Also consider that whatever heuristic you are using takes time to compute. If it is complex, then it may be beaten to short-term solutions by brute-force.

I doubt that''s the case here, but bear it in mind as a possibility.

DefCom

Author

DefCom

Mar 18, 2003 at 1:09 PM

Hi, thanks all for your advise and suggestions. I am now using the STL priority queue (instead of list and sort), so about 5 updated lines of code later... These are my ''time taken'' results for the same path

Astar (sort) 9519
Breadth Search 3294
Astar (priority) 762

Splendid!

I will be posting my code on my website soon, if anyone is at all interested.

Once again, Thanks.

PS thanks Argus, While calculating the heuristic doesn''t take up enough resources to worry about at this time, I had completely forgotten to mention it in my supporting documentation and is certainly worth making a point of. Thanks.

Talyssan

Mar 19, 2003 at 3:57 AM

Defcom, are your final figures with a path length of 33 as with your orginal post?

My own A* implementation gets about the same with a custom made HOT Queue (can''t remember what it stands for). Regardless, I''ve found the HOTQueue pretty useless and was thinking about changing it all over to the STL. Now I think I''ll stick with maybe a simplified version of what I''ve got.

Congratz on getting it sorted out btw. Took me a while too to get it working right.

DefCom

Author

DefCom

Mar 24, 2003 at 1:04 PM

Hi,

I have just posted my console mode code on my site at: PathFinding

This is not there for Flaming (not that any of you on this board do that), just for general interest.

There is also a 3d demo of it too.

One minor point, The timer occasionally is really high? On my 800mhz laptop if any of the solutions have a count over 3000, i repeat the path.

Oh Talyssan, yes it was for the 33step path.

Thanks again everyone.

Edit: fixed link

[edited by - Defcom on March 24, 2003 2:06:20 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.