Sign in to follow this  
kaysik

STL or arrays for your path finding

Recommended Posts

My current A* implimentation uses a simple STL vector to store the lists of open/closed nodes which works great. For my current little demo this works fine and I have no problems but I'm wondering how many people use use pre-allocated arrays for this type of thing? The performance hit from STL is nothing for what I'm doing and the easy of use makes it a great choice, but when scaled to a larger world with more entities it could well become a problem. Do many people here even use the STL for this sort of thing? and if so has it ever been a problem? I'm not planning on changing my current setup as it works fine, but I keep wondering if other people have had performance problems when useing the STL?

Share this post


Link to post
Share on other sites
Don't forget that there's more to the STL than vector, and each facility it provide has certain guarantees for performance. For the most part, code in the STL is better and faster than anything you'd write yourself for the same purpose. So, you need a container that allows random access to elements in constant time, and you rightly used vector. If you're afraid of the cost of repeated reallocation inherent to this particular container, you could reserve the amount of space you know you need before you fill it. If you do this, you'll have exactly the same performance characteristics of an array, but with all of the creature comforts of an STL container.

Share this post


Link to post
Share on other sites
I typically write custom container classes for my search algorithms so I can reduce the overhead of data manipulation and reduce the levels of indirection usually faced with adapting STL containers to a task like search.

Timkin

Share this post


Link to post
Share on other sites
Personally I used std::map to store open and closed nodes (keyed by position), std::multi_map to store open nodes (modelling a priority queue, with the cost as the key), and a few other things (A std::vector for the final path itself)

Mark

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this