Archived

This topic is now archived and is closed to further replies.

Simple (not really) Pathfinding (yes, again)

This topic is 6417 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

quote:
Original post by Kylotan

[quote] Original post by Geta

And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric
(end of Original post by Geta)

What do you mean, added support for iterators? I keep redoing my pathfinding as I can never seem to get a good balance between clean code and good speed


Are you familiar with the STL container classes?

If so, then you should know what iterators are, and that the STL queue container class does not support them. I derived a pathqueue container class from the STL queue class and modified the pathgueue container to support iterators.

If not, then you may want to read a tutorial book on the STL or search the web for an online tutorial. STL comes with MSVC++ and the Metrowerks Codewarrior compiler dev studios (and probably other compilers too) and is well worth learning about.

Eric

Share this post


Link to post
Share on other sites
BeanDog, didn''t you read the posts on your last thread? If you divide that 1/20 of a second for many frames, your game doesn''t stop or slow down even if you move tens of units simultaneously. The only problem is that the units you''re trying to move, start moving a bit later than you actually click the screen. But it really doesn''t matter at all.

As far as I recall, it took some time for units to start moving even in C&C and Red Alert. And probably in Starcraft, too. Everyone is dividing AI routines into many frames.

And the search algo I think is used in C&C and Red Alert, is the Best First. This is just like A* but you always move the node that is closest to the goal (which one is closest, is approximated by simple airway- distance to the goal). Best First is actually really fast and it produces reasonable routes.

ps. I sent that region search idea

-Hans

Share this post


Link to post
Share on other sites
quote:
Original post by Geta

Are you familiar with the STL container classes?

If so, then you should know what iterators are, and that the STL queue container class does not support them. I derived a pathqueue container class from the STL queue class and modified the pathgueue container to support iterators.


I thought that queue was technically just an adaptor for the deque class? And therefore if you needed iterator access, why not just use the deque anyway? I was more interested in how you used the iterators, as I pretty much just add things to the queue and pop them off the front. Why do you need iterator access to the queue? I guess I''m just asking for a little more algorithmic detail here

In fact, isn''t there a dedicated priority_queue adaptor in the STL? For some reason I couldn''t use it for my A* implementation - I think it was the problem of needing to be able to delete from the inside, which could be why you use iterators?

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan

I thought that queue was technically just an adaptor for the deque class? And therefore if you needed iterator access, why not just use the deque anyway? I was more interested in how you used the iterators, as I pretty much just add things to the queue and pop them off the front. Why do you need iterator access to the queue? I guess I'm just asking for a little more algorithmic detail here

In fact, isn't there a dedicated priority_queue adaptor in the STL? For some reason I couldn't use it for my A* implementation - I think it was the problem of needing to be able to delete from the inside, which could be why you use iterators?


deque and queue are actually separate classes in STL. From what I know, queue is not just an adapter for the deque class, as it can be used with any other container class.

Iterator access to the open list (my pathqueue) was needed for
deletions from the inside of the list.

I forget exactly why I chose not to use the priority_queue adapter (this decision was made in 1997) and instead I choose to modify the queue. My guess would be, that I looked at the source code of both, and I felt that it was easier to modify the queue to do what I wanted, than to use the priority_queue adapter.

Eric


Edited by - Geta on June 22, 2000 9:23:16 AM

Share this post


Link to post
Share on other sites
Yes, I believe the priority_queue adapter inhibits access to any element except the top one, so modification of the open list (as A* requires) is not so practical with that implementation.

Out of interest, what data structure do you use for your closed list? I think I use some sort of mapped-bitset (just a minimal-storage hash table, I guess), but I don''t recall if that is actually in my A* implementation. (I have a few different pathfinding algorithms implemented and I''m not at my home computer )

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan

Yes, I believe the priority_queue adapter inhibits access to any element except the top one, so modification of the open list (as A* requires) is not so practical with that implementation.

Out of interest, what data structure do you use for your closed list? I think I use some sort of mapped-bitset (just a minimal-storage hash table, I guess), but I don't recall if that is actually in my A* implementation. (I have a few different pathfinding algorithms implemented and I'm not at my home computer )


I have used both the STL list and the STL map containers for CLOSE list implementations. I think they are about the same in performance in their role as CLOSE lists. They both can rely on the actual NODE pointer address that is stored, as a key value, for identification purposes, so non-contiguous x,y,z nodes can be supported.

Eric


Edited by - Geta on June 23, 2000 9:22:25 AM

Share this post


Link to post
Share on other sites