all the pathfinding source i've seen on the internet in c++ uses arrays. i concede that this is faster, but for the complexity of my game i'd rather use object oriented pathfinding.
i tried converting my homebrew pathfinder from java, but this was near impossible for me without STL::contains.
does anyone have source for OO A*? or tips? or discussion?
help writing OO A* in C++
Well, the algorithm for A* is on the A* wikipedia article: http://en.wikipedia.org/wiki/A*
Implement the open list as a binary heap.
Your nodes are just structs with pointers to neighbors.
Your start node is then just the seed for the beginning of the search. Traversal should be straight forward as each node has pointers to the possible next nodes.
It's pretty straight forward.
It seems like maybe you are just used to copy/pasting other people's solutions and are not practiced in just implementing algorithms for yourself. What specifically are you having trouble with? What have you tried already?
-me
Implement the open list as a binary heap.
Your nodes are just structs with pointers to neighbors.
Your start node is then just the seed for the beginning of the search. Traversal should be straight forward as each node has pointers to the possible next nodes.
It's pretty straight forward.
It seems like maybe you are just used to copy/pasting other people's solutions and are not practiced in just implementing algorithms for yourself. What specifically are you having trouble with? What have you tried already?
-me
Pathfinding is an algorithm. Can you explain why the increased complexity of the game merits "object oriented" pathfinding, and what you mean here by "object oriented".
Can you tell us more about why you couldn't convert your Java version? Are you trying to do it without containers, or are you saying that you couldn't get it to work with them?
Can you tell us more about why you couldn't convert your Java version? Are you trying to do it without containers, or are you saying that you couldn't get it to work with them?
Author
Quote:Original post by rip-off
Pathfinding is an algorithm. Can you explain why the increased complexity of the game merits "object oriented" pathfinding, and what you mean here by "object oriented".
Can you tell us more about why you couldn't convert your Java version? Are you trying to do it without containers, or are you saying that you couldn't get it to work with them?
When I say object-oriented I mean with the use of Node objects rather than arrays.
I don't know how to implement the STL containers in this case. I know that the equivalent to 'contains' (needed when checking if a node is in the open list or closed list) would be checking for find==0. however this 'find' only exists for the set container. simple things like this are keeping me from getting anywhere.
should i have all the data members of the Node object be public? or should I write out accessors and mutators?
And by complexity, I mean the heuristic that takes into account terrain and movement cost will be very complicated (taking into account smells and lighting and many other factors) and my NPCs will be finding their way into building and exiting them. This is much cleaner and easier for me to implement with Node objects, as a pointer between regions (indoors and outdoors) can be more easily checked.
The stl implements things such as "find" as algorithms that operate on iterators such that they can then write it once and have it work on all of their containers that implement the appropriate iterators.
http://www.cplusplus.com/reference/algorithm/
http://www.cplusplus.com/reference/algorithm/
Author
A small hiccup. How do I define the function that set::find uses to determine if two elements are equal?
More generically, how do I check that I am not creating duplicate Node objects in getNeighbors?
More generically, how do I check that I am not creating duplicate Node objects in getNeighbors?
Quote:Original post by overeasy
A small hiccup. How do I define the function that set::find uses to determine if two elements are equal?
More generically, how do I check that I am not creating duplicate Node objects in getNeighbors?
Overload the == operator for your node class I think. I'm using pointers to nodes in my own project, maybe that's an option for you as well.
Author
Quote:Original post by MussiQuote:Original post by overeasy
A small hiccup. How do I define the function that set::find uses to determine if two elements are equal?
More generically, how do I check that I am not creating duplicate Node objects in getNeighbors?
Overload the == operator for your node class I think. I'm using pointers to nodes in my own project, maybe that's an option for you as well.
sounds promising. code example?
If you're using pointers you don't need to overload the == operator, boiling down to calling std::find(pointers.begin(), pointers.end(), pointerToCompare).
Author
Quote:Original post by Mussi
If you're using pointers you don't need to overload the == operator, boiling down to calling std::find(pointers.begin(), pointers.end(), pointerToCompare).
No, because they might be separate instances that have entirely the same values.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
