STL or arrays for your path finding
Author
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?
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.
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
Timkin
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
Mark
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
