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.
-
-
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 :-)
-
:-)
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.
-
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.