Path Finding and Binary Heaps

andre

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

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

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

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

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

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

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

cazador7907

:-)

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

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

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

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

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.