Jump to content
  • Advertisement
Sign in to follow this  
overeasy

help writing OO A* in C++

This topic is 3002 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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/

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Mussi
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.


sounds promising. code example?

Share this post


Link to post
Share on other sites
If you're using pointers you don't need to overload the == operator, boiling down to calling std::find(pointers.begin(), pointers.end(), pointerToCompare).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!