Path Finding and Binary Heaps

cazador7907 · wrote on 20 Dec 2010, 03:22

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?

andre · wrote on 21 Dec 2010, 08:58

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.

cazador7907 · wrote on 21 Dec 2010, 12:54

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.

goetz · wrote on 21 Dec 2010, 13:15

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.

andre · wrote on 21 Dec 2010, 13:30

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.

goetz · wrote on 21 Dec 2010, 13:38

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

andre · wrote on 21 Dec 2010, 13:56

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

goetz · wrote on 21 Dec 2010, 13:58

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

cazador7907 · wrote on 21 Dec 2010, 15:15

:-)

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.

vcsala · wrote on 21 Dec 2010, 17:26

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.

chakie · wrote on 3 Jan 2011, 16:18

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.

chakie · wrote on 3 Jan 2011, 16:19

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.

cazador7907 · wrote on 3 Jan 2011, 21:57

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.