Prev/Next Blog
by date

When You Wish Upon A*

Name:	Dan Keller
Date Posted:	Jan 12, 2008
Rating:	Not Rated
Public:	YES
Comments:	YES
RSS Feed:	or Subscribe with .
Profile Page:	View profile page for Dan Keller

Blog post

Although Torque is an essentially complete game engine, it lacks one major component: AI. I'm sure you know what I'm talking about. You open the aiPlayer files and think, "Is this it? Where's the code that lets the bot, you know, try to kill me? Or even find me, for that matter?" Well, the first part is another subject for another day. The second part is where I decided to begin. The general consensus on the internet seemed to be that a* was the best and fastest pathfinding method, so that's what I chose. Using the information from this excellent article, I began. I won't go into the gory details of a* here, the article explains it better than I ever could. Now, a week later, I have a working (although far from finished) implementation.

Now, I know that there's another a* resource out there, but I still prefer to use my own. This is mostly because of flexibility. The other resource (part of the iAI engine) places nodes for the entire mission area, and only on the terrain. Of course, there are some major things iAI's a* system has that mine doesn't, like doing more than a castray to see if two points can be linked, realistic move costs, path smoothing, etc. However, mine is (at this point) mostly a proof-of-concept.

In my implementation, small grids of nodes are added with NavMesh objects, and the nodes are then linked together.

Because the nodes are stored separately from the NavMesh objects, a path can go across any number of objects without a performance drop. (I went over the path in red for clarity)

Some things I hope to add are
-smooth paths
-better walkability tests
-optimize
-track down the annoying bug where the paths are re-calculated 4 or 5 times when an object is moved
-add real AI

More screenshots and (hopefully) code to come!

Recent Blog Posts

List:	07/29/08 - Nuclear Asteroids (beta testers wanted) 07/20/08 - Summer Jobs, TGB, and Nuclear Fission 04/05/08 - A* Again (but this time it's done and you can downlad it) 03/10/08 - Complete AI System for Torque 02/07/08 - Neural Network AI 01/12/08 - When You Wish Upon A*

Submit your own resources!

Andy Hawkins (Jan 12, 2008 at 08:19 GMT)

Looks good. I'll be tracking this one intently because your solution will allow my aliens and player bots to fly around buildings.

Of course one thing bugs me about A* and path finding in general. In real life when a human tries to find a location (perhaps another human) if they don't know their way, they don't always choose the optimum path - and sometimes get lost.

Also I don't want bots knowing where I am until they see me - then they can do their optimum path thingo. Is this possible to implement?

Andy Hawkins (Jan 12, 2008 at 14:12 GMT)

Oh and clever double entendre by the way :)

Ed Johnson (Jan 12, 2008 at 18:27 GMT)

Very Cool! Cant wait to see where this goes!

Deozaan (Jan 12, 2008 at 18:55 GMT)

Andy/Dan, I suggest you read Amit's A* Pages. Amit goes into a lot of depth explaining A* (and briefly some other algorithms) . He even talks about getting AI to not know where you are and having to explore until they find you, sometimes ending up at dead ends.

He also talks about how to speed it up for large maps (nodes are farther apart for long pathfinding searches) and moving units in groups.

Really a lot of great info there. I researched quite a bit of it about a year ago and I understood most of the concepts but the implementation was a little above my skill. I'd give exact links but I don't remember where in Amit's A* Pages he talks about the specific things since it was so long ago.

Anyway, he even includes some source code in various languages (C++ included) and even without that it's a great resource for A* info.

Dan Keller (Jan 14, 2008 at 01:19 GMT)

Here's an example of a more complex path:

Andy Hawkins (Jan 14, 2008 at 09:25 GMT)

that's cool. So it know's how to "read" a dif / dts?

Dan Keller (Jan 14, 2008 at 16:29 GMT)

Not exactly. I placed a bunch of NavMesh objects manually and it just does a raycast to make the points "stick to" the floor.

Maddermadcat (Jan 14, 2008 at 23:29 GMT)

Ah, so it's possible to edit the NavMeshes manually? I think I prefer that way, generating maps automatically might end up with AIs doing some pretty weird stuff.

Dan Keller (Jan 15, 2008 at 03:16 GMT)

I've added a "find cover" routine that starts searching for a path with no definite goal, using a heuristic that prefers points farther away from the player, and stops when it finds a point with sufficient cover. It works surprisingly well.

Andy Hawkins (Jan 15, 2008 at 04:46 GMT)

It's like Christmas all over again :)

Ian Roach (Jan 18, 2008 at 04:04 GMT)

Hi dan , had a few questions for ya, could you email me at iroach@westnet.com.au ?

Thanks

Dan Keller (Jan 21, 2008 at 21:06 GMT)

I've got four "pathfinding behaviors" finished that will be a major stepping stone towards a complete AI system. They are:
*findBasicPath - Just find the shortest path between two points
*findCover - Run away and hide from a point
*sneakUp - Find a path to a point using only nodes that can't be seen from that point
*wander - Walk around randomly

I hope to add "findPartialCover" and "findAlternatePath" behaviors.

I've also modified aiPlayer so it handles paths internally, avoiding some problems I was having with path objects.
Edited on Jan 21, 2008 21:11 GMT

Jason MacWilliams (Jan 24, 2008 at 21:03 GMT)

So are you willing to release some code to the community? We are looking for an A* path system (local) for a project right now (with only small bot covered regions) and all we can find are global grid resources. We are mostly looking for something that includes simple path finding and finding cover and would love to check out your code.

Dan Keller (Jan 25, 2008 at 23:00 GMT)

I'm planning on releasing the code eventually, but it isn't really finished yet.

Maddermadcat (Feb 04, 2008 at 01:35 GMT)

Hope you'll be done by the time I get to working on AI. =P

Most people, I imagine (myself for sure, heh) would want to have friendly and enemy AIs -- you should look into getting teams working.

You must be a member and be logged in to either append comments or rate this resource.