Prev/Next Blog
by date

Plan for Xavier "eXoDuS" Amado

Name:	Xavier "eXoDuS" Amado
Date Posted:	May 01, 2005
Rating:	4.2 out of 5
Public:	YES
Comments:	YES
RSS Feed:	or Subscribe with .
Profile Page:	View profile page for Xavier "eXoDuS" Amado

Blog post

Next iteration on my AI pathfinding work.

In my previous plan I talked how I implemented path finding using a set of predefined way points placed by the mapper. This system works great for interiors, since it gives the mapper full control of how the ai will interact with the map, eliminating the nasty situations when the ai tries to go through places where the nodes could get linked but you couldn't pass through, like a fence, a balcony, etc. Now, that system was flawed if you wanted to use it in an exterior engine like Torque. Why? Simply because it's too big to place nodes one by one, it's time consuming and annoying. Some time ago in a previous game project, I had coded a simple Navigation Graph that autogenerated nodes and links:

This system was good, but the problem was editing it in circunstances where you might not be happy with the autogeneration, it was nearly impossible, since each node in the navgraph was just an engine struct, containing the position and some other information. I hacked together an editor that could add nodes to the navgraph, and update the links, but that was flawed too, getting it to be able to selected and delete a node would be nearly impossible, since they were just points in space.
So here i am in a bored night, with no intention to go to bed, cooking the idea I've been having for some time. What if I mix both ideas? Create a navgraph made of aiWayPoint objects that I used in my other system and allow the mapper full flexibility, by quickly genearating a navigation graph and adding waypoints manually for interiors. It sounded great...

Now, that was cool, but it was getting the world editor very very busy, and annoying to work with, I'm always thinking on end-user usability with my code. So what to do? What to do? Ok, we should somehow hide the navigation graph, I started by hiding the id's for aiWayPoint objects in the WorldEditor code, but after adding lots of if is AiWaypoint code everywhere, I noticed that I was making the worldEditor uglier than it already is! Let's create a new editor then, mmm let's call it... mmm JoeEditor... no no... AIEdtior, yeah that's a cool catching name. Ok, now I had the navGraph not showing at all in the worldEditor and an aiEditor that showed only the navGraph, not the objects. Next obvious step, show the links! After some hacking and screaming at the stupid editor, the links were working, and rendering properly.

The editor shows nodes in red dots and links in green, selected nodes in blue and it's links in red. You can move the nodes around etc. The AI toolbar menu contains an option for Generating the navGraph (in case you modified the terrain, screwed it up, or changed the navGraph settings) and another option for calculating the links (if you moved nodes, added new nodes, whatever).

Of course, neither the navGraph object or the aiWayPoint object does any rendering, nor are they ghosted, it all happens server side (the editor accesses the server side objects directly) so there's no network chewing involved even with big big big navGraphs.

That's about it for now, there's lots more work to put in this puppy, but I'm happy with the results so far, specially for being all done in just one night :p

What do you think? See ya next plan.

Recent Blog Posts

List:	05/21/05 - Plan for Xavier "eXoDuS" Amado 05/01/05 - Plan for Xavier "eXoDuS" Amado 04/03/05 - Plan for Xavier "eXoDuS" Amado 03/25/05 - Plan for Xavier "eXoDuS" Amado 05/29/04 - Plan for Xavier "eXoDuS" Amado 11/11/03 - Plan for Xavier "eXoDuS" Amado 01/15/03 - Plan for Xavier "eXoDuS" Amado 05/14/02 - Plan for Xavier "eXoDuS" Amado

Submit your own resources!

Xavier "eXoDuS" Amado (May 01, 2005 at 10:24 GMT)

Forgot to mention, I was thinking on making the navGraph spread all over the missionArea, instead of setting a position, size and node density values like I have now. What do you guys think?

John Kabus (BobTheCBuilder) (May 01, 2005 at 14:20 GMT) Resource Rating: 5

Hey Xavier, looks awesome man. Can you select multiple nodes and disable them, so the AI can be limited to, or kept away, from certain areas? Also it would great to have AI groups that could be added to each node, allowing different (potentially overlapping) areas for individual or groups of characters - this would be especially useful for NPCs.

Ben Garney (May 01, 2005 at 17:44 GMT)

Super cool work, ex. I love it!

(Yeah, I think this would be a good use of the mission area. Have you looked into optimizing the navgraph yet?)
Edited on May 01, 2005 17:49 GMT

Xavier "eXoDuS" Amado (May 01, 2005 at 19:47 GMT)

@John: Yes, you can shift click multiple nodes and hit delete, thus removing it from the navgraph completely.

@Ben: Thanks, I'm glad you do. No I haven't looked into optimizing it yet, any suggestions before I do ?
Edited on May 01, 2005 19:51 GMT

Nick Zafiris (May 01, 2005 at 23:08 GMT)

Great work Xavier! Keep it up!

Matthew Langley (May 01, 2005 at 23:23 GMT) Resource Rating: 5

wow, looks very cool. I like the idea of autogenerating AI Waypoints... I'm conceptualizing a much simpler idea in T2D. That your getting it worked out in 3D really is inspiring :)

Matt Sanders (May 01, 2005 at 23:38 GMT)

That looks SWEET X can't wait to see more. :)

Xavier "eXoDuS" Amado (May 02, 2005 at 02:31 GMT)

Thanks for your comments guys.

Firas (May 02, 2005 at 05:16 GMT)

thats really greate can't wait to test it :)

Jameson Bennett (May 02, 2005 at 15:08 GMT)

Excellent! Isolating the AI stuff into it's own UI is a good idea. I am glad to see some work on navgraphs again, your work is inspiring!
A quick suggestion comes to mind:
Autogeneration based on the surface material, allowing the artist to quickly paint out the areas they dont want to be mapped.

Great job and keep it up!

OneST8 (May 02, 2005 at 18:55 GMT) Resource Rating: 4

This looks absolutely fantastic and I also like Jameson's idea of autogeneration based on surface material.

Simply brilliant work.

Well Done.

Xavier "eXoDuS" Amado (May 02, 2005 at 20:37 GMT)

Thanks, I'll have to keep that in mind for future versions.

Gonzo T. Clown (May 10, 2005 at 12:28 GMT)

Since you said the system can handle big big graphs, could it be done in realtime instead? Optimizing a realtime graph shouldn't be very difficult to do. Although I haven't yet implemented any solutions, I have few ideas for real time nav I would be willing to share if you are interested.
Edited on May 10, 2005 12:30 GMT

Xavier "eXoDuS" Amado (May 10, 2005 at 16:54 GMT)

@Gonzo: No, my navgraph is generated once and only once, after that it's saved and load along with the mission. I don't see the point for a dynamic navgraph? And i don't think it's possible either in large maps, adding the nodes doesn't take much time, what does take time is linking them together.

Gonzo T. Clown (May 11, 2005 at 05:58 GMT)

Damnit! It ate my post, ok, the shortened version...

Quote:
I don't see the point for a dynamic navgraph?

No map dependancies or limitations

No mapper influence needed

Better "one size fits all" solution

Greater flexibility

Finer control, smoother operation

Massive performance savings

performance not affected by map size

AI can manage themselves in any environment

etc...

Quote:
And i don't think it's possible either in large maps

I think it's very possible, and I believe that it will perform much better. That's precisely the reason I'm asking you about this. Judging from your pics and descriptions, you are practically tripping over some ideas that I have been pondering and I just wanted to see if you were interested in testing some new ideas. Your skills with the navGraphs greatly exceed mine and as I stated earlier, as best I can tell, you could probably just make some changes to your current code and have a performance test ready in no time. It would take me months to get where you are, but it would only take you a few days to get where I'm wishing I was, lol. Bottom line, you dont have to do squat till you've thought over my design to see if you even think it's worth a try.
Edited on May 11, 2005 06:09 GMT

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