Path Finding and Binary Heaps



  • I have developed a simple graph structure and now it's time for my players to find their way across the graph! Each node of the graph has a name value and a simple heuristic. The heuristic is the distance of the node to the destination ( I thought that this would be simplest way of doing things). The edges of the graph contain distances between nodes and basic cost information for traversing the edge.

    In researching potential path finding algorithms, I settled on the A-Star algorithm. For some reason, it just makes sense to me. As I designed my version of the algorithm, i implemented he open and closed lists as binary heaps. I did this because the graph (33 nodes, max, 45 edges, max) is very small and, there are (at most) five computer players. This means that the even though adding and subtracting data from the heaps might take a little bit of time, based on the above numbers, I can live with it for a while.

    What I am having a problem with is the data that should be added to the Open and Closed heaps. I'm considering just storing pointers to the graph nodes in the heap. The other option would be create a simple structure and store select database from the graph nodes in the structure and THEN store either entire structure in the heap or store a pointer to the new structure in the heap. But, this later approach seems a little cumbersome to me.

    I'm a little new to C++ but, as I understand pointers, I sort of think that the most efficient way to do this would be to just store the point to the original graph node.

    Any advice on how to handle this problem of shifting data around? And, how have others handled this sort of situation?



  • Why do you implement your own graph algorithms and data structures? There are very efficient ones already around that you can use as they are. The Boost Graph Library contains all you need, I think. It does have a problem: it is extremely heavily templated which makes it flexible and performant, but quite hard to understand in the beginning. The benefit is that there are plenty of efficient algorithms available already, and they can be easily extended using algorithm visitors.



  • I want to develop the data structures on my own first so that I can completely understand what's involved in their creation and use. When it comes to implementing the structures in a game, I'll probably use the graph as it was implemented in Boost.



  • For my diploma thesis in university I had to deal with graphs too. In that library the nodes were created on the heap with new. In the data structures (e.g. connections) of the graph were only pointers to the nodes. I'd suggest you go the same way.



  • Boost Graph gives you a lot of control over how you represent your graphs, as long as you make sure your data structures support certain minimum interfaces. I don't think Boost hides the way the graph is implemented from your sight. If anything, it doesn't do that enough, making it hard to work with sometimes.



  • Andre, he will eventually use Boost Graph, if I understood correctly. But he want's to implement a graph "library" himself to learn how things work. That's not a real bad idea, IMHO. Almost everyone did some tiny string class in C++ for educational purposes, although there's std::string or QString :-)



  • True enough. I did graph stuff myself, and it is educational to do. I don't remember ever implementing my own string class though ;-)



  • For me, that was looooong ago in university. To learn how operator+ could be overloaded :-)



  • :-)

    I don't think that I will go as far as to implement my own string classes. My educational background is History. The only subjects farther from computer science, I think, is the study of dead languages or perhaps acting.

    Just as an update, I managed to get both the binary heap and the graph working correctly.



  • You know, this kind of things ("implement my own string classes") seems to be some kind of "common" nice memories for us who studied computer science on the university several (+10) years ago.



  • A* is a good choice for path finding. I used it myself a while ago for pathfinding in a hex based map for a strategy game. Worked nicely.



  • Apropos Boost, sometimes its way faster to just do something yourself compared to trying to understand some Boost classes. They are usually poorly documented and the API:s are not too intuitive.



  • This is what I found when I started working with Boost. I did some basic math and figured that I wouldn't really gain any significant performance improvements over using my own code.

    Of course, I am running this code on a very small set of data. At the most, some of the datasets will only contain perhaps 100 elements. If I were coding against a very large (and/or complicated) set of data (i.e. pattern matching across thousands of elements is a good example) then I would rethink my using Boost.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.