Has anyone done any work with the A* algorithm? I am planning on implimenting it in my game for AI. I see tutorials on how to do it in 2D grids, but I don't know about 3D trimeshes. Does anyone have pointers in this subject or places to start learning more about this? I am not at this part yet, but will be getting to starting on it in about a day or so.
I've coded a lot of pathfinding algorithms.

Have you coded and understood a 2D version?

This is very important. A* isn't always intuitive for people to grasp. Once you get it though, doing it in 3D should be no problem. It's the exact same concept.
I looked here for a 2D grid example: http://www.policyalmanac.org/games/aStarTutorial.htm

I did my usual, unhelpful, skim. I am actually reading it now.

I didn't make anything in 2D as of now.

Right now, I understand how it works in 2D. I am not done reading that article, but it makes sense. I am just concerned about the H value when you hit 3D. I can't use the Manhattan method described in the article. Absolute distance doesn't look like a good idea. I just don't know how to proceed in this case.

Currently, here is my test case. I have a 3 story building. I have a trimesh that covers the 3 floors and 2 stairs connecting them. If I try to go from the 1st floor to the middle of the 3rd floor (with the H value as being the distance), then I am assuming that it will want to go to the middle of the room instead of up the stairs I know that it gets ruled out and I just check other nodes, but seems very wasteful.
H value is absolute distance. Yes you will have to check other nodes. Trust me, there is no better way of doing it. It's not wasteful compared to other search algorithms.

Though if you come up with a better way, I look forward to seeing your presentation at the next CS conference I attend ;D
Hmm... maybe loop across all nodes to find ones that are higher or sloped and go to those?
I am thinking about dynamically generating a slope map. Basically, make groups based on the slope of triangles. Find the path based on the groups. Then use that result as a method of clipping out triangles that aren't worth searching.

I will get to coding this once I have armature animations completed. (different topic)

Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
» All times are UTC - 5 Hours

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum