Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Evil Mr Sock

Generic A*

This topic is 5226 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

I''m looking for a set of A* code that very clearly takes in the Start X,Y and Goal X,Y, and needs only two functions written for it : a straightforward GetValidity and GetCost, and when the path has been generated, has a clear implementation of reading the path. This is for use with a 2d map with 8-directional movement. All I want is the core, basic principle, unnapplied to any specific game or program. I''ve read through four or five implementations of the algorithm, including all the ones I found linked from the main Gamedev.net site and the hexagonal pathfinder that seems to be frequently linked to here, and the closest I''ve gotten to what I wanted is Matthew''s implementation of it in AI Game Programming Wisdom. Unfortunately, he uses coding techniques that are a little too complex, leaving me with a simultaneous AI and C++ learning curve. I don''t need something THAT open to expansion immediately. I''d rather have something a bit more boiled down first so that I can get a working structure in place in my game, and then I can devote more time to the more complex iterations of the algorithm. I''m perfectly willing to believe that this doesn''t exist: the code that I''ve seen so far has either been basic, but not generic, or generic, but not basic. But I thought I''d ask around.

Share this post


Link to post
Share on other sites
Advertisement
A* is simple - I just finished implementing it myself. I''d give you the code, but it''s a mess and yet unoptimized. Besides, it''s unidirectional (don''t really see the advantage in bidirectionalism, speedwise).

My suggestion is to alot ~5 h to it and just code it yourself. Start here, then read this for optimizations and finally have a look around here.




"Finishing in second place, simply means you are the first loser." - PouyaCat

Share this post


Link to post
Share on other sites
I got my A* implementation from here:

http://www.geocities.com/SiliconValley/Lakes/4929/astar.html

There is some nice example code that will fit pretty much anything since the A* engine is built as a template.

The actual Node class is what you will overhaul for your own purposes.

Also note that A* is just an algorithm and in itself is pretty generic. It''s the nodes that are particular. If you use a hex board, then you just change the GetChildren() (or whatever its called) function to get 6 instead of 4. The actual engine would remain untouched.

Share this post


Link to post
Share on other sites
quote:
Original post by leiavoia
Also note that A* is just an algorithm and in itself is pretty generic. It''s the nodes that are particular. If you use a hex board, then you just change the GetChildren() (or whatever its called) function to get 6 instead of 4. The actual engine would remain untouched.
C++ doesn''t lend itself to a generic A* implementation that would be *fast* in all cases, though. Or at least I couldn''t make one, and the implementation in the link you gave is also very slow for "special" purposes like a grid map. Hmm, maybe I''ll try again..

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!