Path Finding and Binary Heaps
-
wrote on 21 Dec 2010, 13:15 last edited by
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.
-
wrote on 21 Dec 2010, 13:30 last edited by
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.
-
wrote on 21 Dec 2010, 13:38 last edited by
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 :-)
-
wrote on 21 Dec 2010, 13:56 last edited by
True enough. I did graph stuff myself, and it is educational to do. I don't remember ever implementing my own string class though ;-)
-
wrote on 21 Dec 2010, 13:58 last edited by
For me, that was looooong ago in university. To learn how operator+ could be overloaded :-)
-
wrote on 21 Dec 2010, 15:15 last edited by
:-)
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.
-
wrote on 21 Dec 2010, 17:26 last edited by
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.
-
wrote on 3 Jan 2011, 16:18 last edited by
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.
-
wrote on 3 Jan 2011, 16:19 last edited by
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.
-
wrote on 3 Jan 2011, 21:57 last edited by
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.