Wow, great article! It was worth the wait :-)

To be fair, while the problem is technically solved, WoW has never really made it a priority to ship solid AI -- so it's almost a bit unfair to pick on it. Sure, it'd be cool if Blizzard hired an experienced navigation mesh programmer, but would the different show in the average case?

If anything, WoW is a rather depressing example that games can make huge amounts of money without good pathfinding.

alexjc
AiGameDev.com

What game is that with the shotgun and the enemy stuck by the crate? (The 2nd clip in...)

Thanks! =)

Eric, I'd prefer not to mention any of these specific games by name, since I want the emphasis to be on the AI pathfinding problem across the industry, rather than picking out the flaws in specific games (P.S. check your e-mail).

All the examples as presented show the nav-mesh as a 2d projection onto the space. How would you handle a case like a bridge over a road, where in you could go over or under. Or a building with multiple floors?

Wonderful article. Really nailed it into me that Navmeshes are great. I now know more about them then I did before, and I thought I knew how they fully worked :)

Now I wait for the article in 10+ years decrying navmeshes and a inevitable need for something better (or simply improved navmeshes!). Hopefully, however, Navmeshes are a good solution for a long while, much more so then waypoints at least :D

[PaulB]
> All the examples as presented show the nav-mesh
> as a 2d projection onto the space. How would you
> handle a case like a bridge over a road, where in
> you could go over or under. Or a building with
> multiple floors?

Thank you, Paul; good question!

Scroll up a bit -- I've added this question to the list and answered it with an example image.

> [Andrew] Wonderful article.

Thanks, Andrew! :)

Seems to me waypoints aren't in conflict with navigation mesh, they're just an alternative or simplication to raycasting. Also, in both cases you would need a solution for points that you have to jump or climb or fall (or give up) to intelligently follow the player, which you seem to have exploited in a couple examples.

This is mostly why I no longer play against AI's. Its just so frustrating when they are incapable of handling the environment. I now play TeamFortress2 almost exclusively since humans at least look convincing when navigating the maps. Its honestly quite depressing.

> [Henrik]
> Seems to me waypoints aren't in conflict with
> navigation mesh, they're just an alternative or
> simplication to raycasting.

You can always use waypoints for giving AIs explicit paths -- for example, scripting an AI's movement during a cinematic sequence. That's possible (and often necessary) regardless of what pathfinding representation you use, and it's not what I'm discussing in my article.

What I'm criticizing is the use of waypoints for pathfinding. Technically, yes, it's "just an alternative," but it's generally an inferior alternative, since it's not a robust approach to pathfinding and causes all the problems I discuss above.

> [Henrik]
> Also, in both cases you would need a solution
> for points that you have to jump or climb or
> fall (or give up) to intelligently follow the
> player ...

Yes, that's true regardless of what representation you use for pathfinding.

Excellent article and great video Paul.

I too would like to know what game is in the stuck on crate clip.

I'm working on my first 2D web based action RPG.

I'll probably be using a waypoint system for pathing because it's easier to program.

What level of math is required to implement something like this? Calculus?

I'm thinking of some type of grid-based waypoint system for my simple flash based game.

A good number of the problems with waypoints that you've shown are due to programmer and/or designer error; many of them aren't even that difficult to fix.

Having worked on games that use both, I can safely say that (much like any feature in games) it ultimately comes down to how well the system is implemented.

I've worked with mesh system where the AI pathed unnaturally, cutting all corners as close as possible, generally running in a straight line between them. I've also has to deal with breaking up the mesh appropriately any time a table, chair, crate or other obstacle was placed or moved. In complex obstacle filled environments, like building interiors, a mesh based system starts to become unwieldy. You may even end up with a separate avoidance system within the system to avoid needing the create "islands" around these obstacles.

I've also worked with a waypoint/node based system that handles nearly every bug you mentioned above, including smooth pathing between distant nodes. It doesn't handle every case (nor does the navigation mesh system); but it does handle all of the cases that it needs to.

In short, use the right tool for job and heed the fact that navigation meshes are not always the right tool, even in fully interactive 3D environments.

The majority of issues you seem to point out as issues in waypoint systems are issues in Navigation Meshes as well.

AI doesn't have to zig zag with a waypoint system and any good implemented systems it doesn't.

For AI to handle flying over ledges like you shown requires a special case for your navigation mesh (which can be added just as fine to a waypoint system).

The advantage of a navigation mesh is purely it can requires less data to describe the same thing in waypoints. Which can simply be shown by as the density of your waypoints approaches infinity your waypoints get closer and closer to describing your navigation mesh. This is due to navigation meshes are just closed waypoints. As a result, any additional issues in a waypoint system over a navigation is either due to density or implementation issues.

Density can be handled by a hierarchical system. Also waypoints handle adding of dynamic blockers can be simpler than navigation meshes.

BTW I do prefer navigation meshes in general, but they aren't some magical solution since the properties are essentially the same except with some slightly different handling of situations.

I think that at least for anything with NPC's trying to engage the player (pretty much anything that is not a strategy game) extra navigation maps for the AI will fall by the wayside. Wether or not the AI can walk there/take cover (and against what) will be handled by the AI analyzing it's surroundings.
An AI would be prepped with data about it's model (height, width, length, mass, appendages, weapons (if applicable also data about it or methods to determine weapon characteristics), what have you), it's objective (flee in terror, guard, engage on sight etc), characteristics (ie use cover, spray and pray, take aim, feint, sneak) and data abouts its (or as for weapons methods to gain data by trial and error) surroundings (Tiny bridges out of teakwood have a weight capacity of x, Cover out wood are useless against my weapons, mist disables my weapons (That's somethings the AI should notice after thr first shots and avoid after that)

I hear what he is saying, and navigation meshes are a superior solution, but most of the problems he shows in the video can just as easily happen in games that use navigation meshes.

Navmesh is definitely another solution but it comes with its own problems. Having worked on a large GTA scale game that used navmesh that got so complicated it was almost like building the world twice. Once for the visibile geometry and then almost as long again to clean up the navmesh around it.

I still think there's a better solution than either of them... course if I knew what it was I'd be a rich man :P

Fantastic article. I know only basic programming yet everything made perfect sense. Thanks for enlightening us all, the field needs more people like you.

I for one think the Navigation Mesh is superior to the traditional waypoint method. Is it the end of the line? No, the nav. mesh has it still has it's on inherent problems, but overall it is the better system for the time being.

That's a really good article. We chose to use Navmeshes because each character can quickly determine the amount of free space around them in any direction. This is useful when coordinating large numbers of characters without having one character push another character into a wall or off of a ledge. Typically collision probes are too expensive for every AI character to use, but with the Navmesh it's very fast to get this information given the polygon that the character is starting in.
One of our GDC talks (http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt) from a few years back also gives some approaches for automatically generating Navmeshes and modifying them at runtime (no audio with the slides, but hopefully somewhat useful).

A great article, I wish the gaming industry would take this with open arms, rather than keeping them shut on these things.

One question tho, how would path-finding mesh work on enviroments where you and AI can move in 3 dimensions? (For example a space-ship-shooter type of game.)

PS.
Second game in the clip I haven't seen, interested a bit. What's the name?

Out of curiosity, what is the possibility of doing real time line of sight based navigation on today's platforms?

It was possible but very slow 10 years ago, however this makes intelligent characters independent of the environment which is a big win for production time and decouples character technology from environment building.

If you are looking 10 - 20 years down the road is this something you are also thinking about perhaps?

> [LittleBrain]
> I hear what he is saying, and navigation meshes
> are a superior solution, but most of the
> problems he shows in the video can just as
> easily happen in games that use navigation
> meshes.

True -- some of the problems in the video are not specifically related to waypoint graphs; they were more intended to show that the industry as a whole still doesn't always take pathfinding seriously.

And yes, navigation meshes are not a panacea; there have been some games that have used navigation meshes but still had pathfinding issues.

> [DavidM]
> One of our GDC talks
>(http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt)
> from a few years back also gives some
> approaches for automatically generating
> Navmeshes and modifying them at runtime (no
> audio with the slides, but hopefully somewhat
> useful).

Thanks, David! I've added this to the article.

EDIT: I've also added you to the list of middleware vendors mentioned in the article. Cool stuff! Looks like exactly the approach I've found to work.

Looks like kotaku took notice.

Some *interesting* comments there. Gives a bit of insight on what players really think/understand about AI and pathfinding. Here are a couple of the highlights...

"Really all AI is designed to do these days is put up a bit of a fight and then die. Don't see that changing much for a while."

"ive recently been playing alot of snes games, and the AI hasnt seemed to have improved from then to now."

"But like a few of you have said, why bother when in general the gaming public isn't going to notice or care?"

"i havent seen ai really improve in 10 years, and at that time the only improvement i saw was in half life, with ai that used cover, some of the time, in principle."

http://kotaku.com/5029669/the-problems-with-pathfinding

Also, not that it hasn't been said already, but nice article, the video was great. It seems like it really comes down to whether a company really cares and/or has budgeted the time and money to reflect their decision (but that really applies to AI in general).

How about the AI in Assassin's Creed folks? The guards that are following the assassin throughout the rooftops of the entire cities, jumping and running everywhere?

I totally agree with you julius, there are some great games out there that do some amazing pathfinding, I just wonder how much an average gamer really thinks about it when he sees it. I've got a sneaking suspicion that a lot of them just take it for granted and complain when it misbehaves.

Great article! I generally agree with everything said. My only complaint is the video early in the article shows a myriad of navigation bugs, not necessarily related to the navigation network or its representation.

The spirit of the article is spot on - Modern AI calls for a number of features that become very difficult to manage with waypoints (obstacle avoidance, smoother/more natural movement, group navigation or formations, the list goes on).

Our old system here used waypoints. Some complain about the navmesh pipeline being more of a hassle, but that's a tolls problem, and a much easier problem to solve than fixing all the downfalls of waypoints in games employing modern AI features.

Wow, men, pretty nice

This made remember i talked of something like this when I was on a Genetic Algorithm class where the npc would navigate the whole map using a collision mesh, create a couple of paths and from those path start optimizing until a shortest path was decided.

Great post Paul.

I also enjoyed your article on the AI Wisdom books. I read almost all of the articles you mention in preparation for my GSoC project. I am implementing an open soruce navmesh generator for the open sourced game engine Crystal Space/CEL.

The code is a bit behind schedule, due mostly to my indecision in what algorithms to use to optimize the navigation mesh. The original plan is to use Hertel-Mehlron to do the triangulation and then pass the result mesh for simplification to some merging algorithms, and do some culling of unusable or isolated fragments. Do you think this is a good approach?

What is the fastest/optimal algorithm to handle this sort of task? (but relatively simple to implement).

I am putting off some of the more advanced features for a second phase of the project, stuff like dynamic navmesh generation (for destructible environments), solving jumps, doors, elevators, ladders links, handling tunnels/crawl spaces, etc... however there really isn't that much information on strategies to implement these features (even in the articles you appended to your post).

I was thinking about jumping cells(polygons), my idea is that if we calculate the relative height between adjacent cells, if the cell is at 0.5m high he can jump, if the cell is at [0.0, 0.2]m high he can walk, if the cell is at 2.0m high he can hang and climb, if the cell is at -2.0m he can jump and roll, etc... Adding this field would add more memory requirements, this is just a naive approach to the problem but do you think it could work?

Any pointers by Paul or any other of the hundreds of AI experts that read this blog would be very helpful to create a good, flexible and open sourced implementation of a navigation mesh.
TIA.

Thanks for the article, it is a great "sales pitch" for the use of navigation meshes.

> [DannyBlue]
> The code is a bit behind schedule, due mostly
> to my indecision in what algorithms to use to
> optimize the navigation mesh. The original plan
> is to use Hertel-Mehlron to do the
> triangulation and then pass the result mesh for
> simplification to some merging algorithms, and
> do some culling of unusable or isolated
> fragments. Do you think this is a good
> approach?

Yes, I do; that's an approach I've used with some success in the past (though in retrospect it would have been a good idea for me to have added more support for more designer control, if I'd had the time to implement that sort of thing).

> What is the fastest/optimal algorithm to handle
> this sort of task? (but relatively simple to
> implement).

Hard to say. I'd recommend checking out all the articles I link to above. My approach was essentially just a greedy merging algorithm, and it rejected any remaining polygons based on various factors: the Z values of their normals (i.e. the poly faces sideways or downwards), surface area (throw out polys that are too small), and connectivity (toss any polys that aren't connected to other nav mesh polys).

As others have already mentioned, using a nav mesh wouldn’t automatically fix these problems. Another point is that in some of the cases the issue may be with the capabilities of the object doing the search as opposed to the pathing logic itself. If you look closely at the segment with the panthers you’ll notice that the Player jumps to get up and down that one area. There’s possibly a break in the mesh there and if so then their pathing code might not take jumps into consideration but I’ve seen the same thing when the NPCs weren’t set up the with ability to jump, either by design, lack of animation or omission. Along the same lines the pathing in the river could be due to the monster not having the ability to swim, which you’ll notice the Player does. Sure, it doesn’t look good but the issue may not be with the pathing code or the search space.

Someone had asked about jumping so I thought I’d pass along some of what we did. To improve load speed we preprocess the cell linkages and other related data. Part of this is determining all the potential jump cells. When something tries to jump off the mesh we’ll check the list of potential jump cells and see if there’s one in line that the avatar could actually jump to. Since you could have different guys with different sizes and abilities we’ll determine this when jumping or searching for a path. Other factors like if you can hang from the cell and the hang height of the avatar would be factored in as well. Assuming your avatars have standard jump abilities you could factor these jump cells into your pathing. Since there was the potential for avatars to make great leaps in what we were working on we took a different path to reduce the search space. What we did instead was set down “breadcrumbs” every time the Player would jump off of one part of the mesh onto another and we’d factor those into the search. These could also be preplaced in the mission as needed.

Regarding physical objects in the mesh one thing you can do is weight any cell with objects in it higher so the search will prefer to use other cells. When objects are added or removed you update the cell information accordingly. If you still need to go into or through that cell then, as someone else mentioned, you may need to come up with another alternative. For one game we came up with a supplemental LoS pathing solution. In another our solution was much simpler. Anything that wasn’t cut out of the mesh was an object that could be destroyed so anytime an NPC would bump into one they’d just do a melee attack, destroy it and keep moving on.

If the problem with using the collision mesh for a navigation mesh is the number of collision polygons, you could have a compile time tool that takes the collision mesh and outputs a navigation mesh of the collision mesh's perimeter.

I just wanted to alert you to some of the cutting edge research being done on pathfinding, particularly a dynamic lookahead heuristic thats been worked on, that I think you may find interesting. I've got most of the details here at my blog:
http://www.oddco.ca/zeroth/zblog/2008/07/29/dynamic-pathfindingcutting-edge-research/

I attended the presentation, thought it was a pretty awesome algorithm. It certainly shares a lot of similarities with navigation meshes.

Peace,

Zeroth

Just curious, wouldn't it be easy to simply add the ability to stick an invisible "navmesh" attribute on any given surface, as simple as adding textures? Like, if I was using Hammer to work up a new map for HL2 as I was building I would do a pass where I marked all the surfaces where people could move around and run as navigable? Then just hit compile and let el computadora do all the hard work.

I've seen some questions from some people about implementing a NavMesh system from scratch for their own games. In my previous game studio I've implemented one and wanted to give some information about it.

Unfortunately most of the published articles in the game programming related books (eg: Game programming gems and AI Game Programming Wisdom ones) are too specific on one part of the problem. They are good articles but they are mainly suited for optimizing an already existing system. They don't give too much insight about the overall system and how to implement one from scratch.

One good source I used is (which is already in the list)
"Efficient Navigation Mesh Implementation" by John C. O'Neill (Journal of Game Development, March 2004)
This article talks about the problem overall, presents data structures and the pathing algorithm on the mesh. It is fairly good although doesn't go too deep on the some hard implementation details. Unfortunately this article is extremely hard to find, Not sold anymore, I've seen used copies on amazon. Fortunately we had a copy in the company.

Even after this article you'll be left with lots of low level implementation details. From simple 3D geometric math to Triangulation, 2D-3D Boolean operations... For these don't look further than the CS literature and articles on "Computational Geometry". (Well a warning here: Computational Geometry is a CS Masters course on most colleges and require a good understanding of Linear Algebra as a prerequisite.)
This book is especially a good one:
Computational Geometry: Algorithms and Applications by Mark de Berg
There are also really good (and technical) articles on "ACM Digital Library". - Requires membership to access - a Well worth membership.

On the side note, Since navmeshes generate graphs, you'll also have know graph data structures and traversals. (A* and djikstra). Well there are a ton of literature. And I assume any AI programmer should already know about graphs.

On the scheduling side, it took me about 1.5-2 months to implement. (Tool and engine side, and bug fixing and a presurizing lead alltogeter :) ). It had no runtime mesh modification support, designers had to switch navmeshes when they wanted to modify it. For dynamic small obstacles sphere avoidance algorithm worked fine. Generally I was really happy with the result. Although all I can say is, it is not a trivial task to implement a robust Navmesh system.

In my current company we are using NavPower. Even though it is alittle bit expensive I appreciate it alot. It saves you from lots of headaces and development time.

A couple of comments about World of Warcraft in particular (I admit it, I'm an addict):

Whatever navigation system it's using, it's not a waypoint graph. Enemies path in straight lines directly toward their targets, sliding along walls/cliffs when they reach them. They can move to any location in an open area. Looks like a nav mesh system to me.

Second, WoW has a clever system for solving AI pathfinding trouble: make it the player's problem. If an NPC can't reach its target, it will "evade", resetting its health and returning back to its start location. Since the player was presumably trying to kill the monster, this forces them to choose not to stand on special rocks and cliffs and other places that cause pathfinding failures.

This is horrible from an "AI should make the monsters behave realistically" perspective, but brilliant from an "AI should never let the monsters be pushovers" perspective.

Basically, if you're going to have an AI failure, err on the side of preventing exploits.

Wouldn't it make more sense to use a negative nav mesh, i.e. a map of places the AI can't pass trough?

> [Jason]
> Whatever navigation system it's using, it's not
> a waypoint graph

That's why I said "most" of these games use waypoint graphs for pathfinding, rather than "all" :)

In any event, the video was more a demonstration of some of the pathfinding issues modern games still face, and was intended to motivate the discussion. Some of the bugs are clearly unrelated to the pathfinding representation.

> [Michael]
> Wouldn't it make more sense to use a negative nav
> mesh, i.e. a map of places the AI can't pass
> trough?

The "points-of-visibility" approach does this. That approach can work, but I find it's generally easier to run a search algorithm (such as "A*") on spaces you *can* walk on than spaces you can't. The navigation mesh approach also lets you mark areas with flags to indicate what kinds of creatures can move through there and how they should do so; it's a bit more difficult to do that with a points-of-visibility approach.

Thank you Paul for this great Post !
There have been a lot of good articles in the past Gems/AI Wisdom books, however they're mostly addressing the low-level CSG Operations. What I found to be the most difficult is the handling of non-blocking dynamic objects and tricky movement capabilities. Three examples here:
1. How to handle partially overlapping areas, 1 above and 1 down below, where the lower one is filled with water and the upper is some sort of bridge. This means you could do a "waterjump" to reach the upper one, but there is no real edge generated from the base geometry.
2. Floating Objects. In a Quake-Style Game Items like Armors are sometimes found floating between 2 Jumppads. I can't assign this item to an area and detecting the nearest "best" one is tricky.
3. Dynamic Objects which can be moved e.a. a winding bridge or a latter. Or even a sequence of jumppads.
So far the only solution I've seen is to get rid of the 2.5D Represention and switch over to using simplified BSP-Trees like JP van Waveren did since Quake III. Am I wrong ? Are there any good lectures on this topic ?

[MarkusK]
> 1. How to handle partially overlapping areas, 1
> above and 1 down below, where the lower one is
> filled with water and the upper is some sort of
> bridge. This means you could do a "waterjump"
> to reach the upper one, but there is no real
> edge generated from the base geometry.

Yes, in this case, it may be difficult to get the results you need from an approach based on automatically generating a nav mesh from the base geometry.

> 2. Floating Objects. In a Quake-Style Game
> Items like Armors are sometimes found floating
> between 2 Jumppads. I can't assign this item to
> an area and detecting the nearest "best" one is
> tricky.

I'm not sure I understand; what is the need to assign it to any navigation mesh regions at all? If the question is how bots should be able to plan a path to jump and get the armor, it should be possible to either do this dynamically (by testing various jump arcs that intersect the armor, and making sure they land on the navigation mesh somewhere), or by setting up some number of scripted jump trajectories.

> 3. Dynamic Objects which can be moved e.a. a
> winding bridge or a latter. Or even a sequence
> of jumppads.

Yes, in this case, parts of your navigation mesh need to move. The only tricky part is updating the connectivity data when your polys become adjacent to existing nav mesh polys; there are lots of ways to handle this, including scripting.

> [Michael Leza]
> Just curious, wouldn't it be easy to simply add
> the ability to stick an invisible "navmesh"
> attribute on any given surface, as simple as
> adding textures? Like, if I was using Hammer to
> work up a new map for HL2 as I was building I
> would do a pass where I marked all the surfaces
> where people could move around and run as
> navigable? Then just hit compile and let el
> computadora do all the hard work.

Potentially, yes, though you could also end up with a lot more polys than you actually need for navigation. You also run into issues in cases where you want to tweak the nav mesh separately from the geometry -- for example, you want units to walk at least 3 meters from a wall for reasons specific to your game design. It's easiest to do this with a separate mesh; with the approach you describe, you'd probably need to subdivide a lot of existing polys so you could mark them as "navmesh" on one side and not the other.

I think at least two of the games you pick on are MMO's, World of Warcraft and Age of Conan? I remember a time when path finding in MMOs were just straight linear pathing. The question is if correct pathing is even possible under the requirements of the massive multiplayer environment. There's a lot more to pick on in these types of games but they're so easy to fix that it's obviously a resource versus correctness compromise. Good article though.

>Now I wait for the article in 10+ years decrying navmeshes and a >inevitable need for something better (or simply improved ?>navmeshes!). Hopefully, however, Navmeshes are a good solution >for a long while, much more so then waypoints at least :D

I quote this because I would expect that demand to come from games with 3-D nav requirements (more than Mesh+height) as in underwater, air, or space based environments (my video game wet dream is the battle room from Ender's Game).

I am not well versed in the issue so perhaps there is already something for 3 Space pathing that works well but is difficult to apply to surface based environments. Either way this article is a great example of what time and knowledge can provide, rather than just making fun of something or whining about it. Thanks.

P.S.
>Anything that wasn’t cut out of the mesh was an object that >could be destroyed so anytime an NPC would bump into one >they’d just do a melee attack, destroy it and keep moving on.
I found incredibly comic. Think of traffic jams, long lines, or that corner you always bang into.

Are there instances where you'd need a "navigation volume"? i can see where you might have a flying unit in your bridge example who wants to fly up from under the bridge to on top of it. is there any way you've seen to extend your mesh idea to cover more "space" or at the point you need that are you back to setting "flyer waypoints" in space and just using your the mesh to find landing points? (i think that's how the FAA operates, so maybe it's not such a bad model)

I can imagine with a sense of volume, you might find it easier to reason that the tank wanting to path around the sandbags has a "step height" tall enough to go straight over them (not even considering deformable terrain or the laughability of sandbags being a deterrent to tanks IRL), essentially treating the wall as if it were part of the ground mesh. Otherwise, how can you fix the issue with hovering units/flyers/etc. without writing it off to a collision detection problem or making different meshes for each type just like you'd have to with waypoints?

My opinion:
Meshes > Waypoints. Got it.
Meshes > *. Not so sure.

> Are there instances where you'd need
> a "navigation volume"? i can see where you
> might have a flying unit in your bridge example
> who wants to fly up from under the bridge to on
> top of it.

Yes. Again, you usually want every polygon in your navigation mesh to have an associated "height" value that indicates how much open space is available above the polygon (where your definition of "above" is either directly vertical or in the direction of the polygon's plane normal, depending on the needs of your game).

If you do it correctly, you should have no problem setting up a mesh to allow a flier to move from below the bridge to over top of it.

All you're doing is using A* to find the list of navigation mesh polygons that will get the flier from one point to another, and once you know that, you can much more easily figure out a path in terms of actual vertices.

> I can imagine with a sense of volume, you might
> find it easier to reason that the tank wanting
> to path around the sandbags has a "step height"
> tall enough to go straight over them ...

Yes, having a "step height" for each character is definitely recommended; that will help ensure that your characters know how to do pathfinding in a way that corresponds to their movement capabilities.

You might have to consider with the step height of that tank going over the sandbags whether this is an efficient decision as this might unnecessarily slow down the tank and the cost to this climb-step has to be considered in the A* costs.

An incredible article. Thank you!

I think, that the simplest way to generate navmesh - is on "Figure 21. Extending the waypoint approach with circles" with extension like...

Then 2 circles intersect, you can place portal \ graph node at this intersection and think about area inside this circle amidst neighbour portal \ graph node as a navimesh poly. You make connected graph this way.
Then graph is done, you make postporcess - eleminate nodes that are formed a straight poly and merge them.
sorry for tangled story, i made some explanatory pics
pic1 - make graph node from circles intersections
http://img80.imageshack.us/img80/707/placenodesat7.jpg
pic2 - form navimesh polys
http://img225.imageshack.us/img225/7103/formpolysyr4.jpg
pic3 - optimize by merge postprocess
http://img262.imageshack.us/img262/7902/mergepolysij3.jpg

Hello,

Great article, wow! lots of comments!...

well, I have some questions:

- Is it worth to use polyhedron-based navigation mesh for flying creatures, maybe in a 3D labyrinth? and how may I create an editor for that kind of mesh?

- How can I say that is it posible to jump from a polygon to another? Considering jumping down of the bridge or jumping across a fissure? [I think my idea (I didn't read it anywhere else) of the polyhedron-based navigation mesh may solve it]

I'll read the references ^_^

Thanks a lot!!!

~ Alfonso J. Ramos - Theraot@gmail.com

Oh, sorry, sorry, It has been a serius subject of study (I think) to create the polyhedrical approach [has been implemented perhaps?], I will be looking forward for the next solution for pathfinding, I am sure that this is not fully solved.

- Alfonso J. Ramos - Theraot@gmail.com

Great article! Really a nice, comprehensive and complete comparison of Way-Point-Graphs and NavMeshes. We try to convince game studios of the same thing, and your article really helps to find great arguments.
We also provide a solution for automated NavMesh generation including several classifiers for Bots influencing the NavMesh generation (falling and jump heights, max slopes, size classifiers etc).
It would be great if you could add our company to the above mentioned middleware solutions, as well.

> [Thorsten]
> It would be great if you could add our company
> (Xaitment) to the above mentioned middleware
> solutions, as well.

Done!

> [Alfonso J. Ramos]
> Great article, wow! lots of comments!...
> well, I have some questions:
>- Is it worth to use polyhedron-based navigation
> mesh for flying creatures, maybe in a 3D
> labyrinth? and how may I create an editor for
> that kind of mesh?

All you need to do in most cases is add a "height" parameter to each navigation mesh poly to extrude it upwards. There's a bit of discussion of this in the section that contains Figure 22.

For some games that are *truly* 3D and have no fixed up and down, such as "Descent," you can use convex polyhedra instead of 2D polygons with heights.

>How can I say that is it posible to jump from a
> polygon to another? Considering jumping down of
> the bridge or jumping across a fissure? [I
> think my idea (I didn't read it anywhere else)
> of the polyhedron-based navigation mesh may
> solve it]

There are several ways to handle this. The most robust solution is to create a special nav mesh polygon hanging down off both sides of the bridge you mention, and across the fissure, and mark it as a "jump" region. Then your pathfinding system needs to know that creatures should jump whenever they cross a "jump" region.

You could also do it in a more traditional way, and drop markers/annotations/hints into the world with start and end points for each possible jump. This gives you a bit more control over the exact start and end locations of each jump, and possibly the trajectories as well, but I prefer the first solution since it's integrated into the navigation mesh.

> [Tomat]
> I think, that the simplest way to generate
> navmesh - is on "Figure 21. Extending the
> waypoint approach with circles" with extension
> like...

I think that's a good approach, but I'm not sure it's much simpler than dropping vertices into the world and connecting them.

If you imagine a case where you have a sequence of rectangular polygons, a manual nav mesh editor like the one I've described requires you to drop 2 vertices plus 2 more for each polygon (since each neighboring pair of polys shares 2 vertices). With the approach you describe, you still have to place 1 vertex for each of the circles, and you also have to allow the user to specify a radius for each circle as well as the direction of the circle's surface normal (since many navigation mesh polygons will be on sloped surfaces).

So it's basically an equivalent amount of work.

In the case where your nav mesh consists of triangles connected in more of a random mesh, a vertex-based approach is simplest; in that case, triangles often share 2 or 3 of their vertices with their neighbors, and describing them with center points plus a radius and a normal probably wouldn't get you anything.

After over 8 years in the game AI world, this is the best article I have ever read on navmeshes. Bravo!

Awww, shucks :)

Thanks, Paul!

why not scrap them both and start with a floor that is, essentially, a nav mesh? That way there need be no polygons to describe anything and collisions could be detected by setting up objects like walls --which would seem to need polygons and coordinates anyway.

> [shandooga]
> why not scrap them both and start with a floor
> that is, essentially, a nav mesh?

If you do that, you're tying the hands of your artists and level designers by forcing them to fit into the needs of your pathfinding system.

Artists and level designers need to be able to build the geometry of the game world using a potentially very large number of polygons to represent the game world ... while you want a navigation mesh to be as simple as possible for the sake of efficient pathfinding and easy editing.

Again, a cobblestone street on a curved road is a good example. You can usually represent the navigation mesh for a road like that with one big rectangle, but you don't want to go to your artists and say, "Make this all one big rectangle."

If you do that, there's no way for them to do the cobblestones (assuming you want real, bumpy stones and not just fake it with normal-mapped cobblestones), and there's no way to make the road curved.

You really need to use separate representations for the render geometry, the collision geometry, and the pathfinding.

Keep in mind that you'll often want to tweak both the collision geometry and the pathfinding to be different from the render mesh -- in the case of the collision mesh, this includes things like adding invisible walls to prevent the player from going into certain areas or simplifying complex areas of collision for better collision performance; in the case of pathfinding, this includes being able to tell your AIs "keep more distance from this wall when you're walking down this hallway" or "don't go down this street, even though there's a render mesh and a collision mesh there."

I think I may have an idea about jumping and stepping off things.

Ether a programmed side to the poligon or another poligon block to signal that another type of behaviour can be used. Useing the bridge and road in Stormwind as an example the edges of the poligons next to the water would be programmed to let the NPC know that at a sertain ammount of life the NPC can perform another action and jump to the side at the line then end up in the waterand hopefuly safe. It could be adjusted for just about anything even marking obsitcles in the mesh as hidable behind and others as just off the edge as walls and huge drops. Another fun thing it might alow is for an NPC to make what might seem like a risk assesment alowing the NPC to only jump off cliffs if thay will have a sertain amount of life left at the end of the fall so the fall risk is programmed at the top of the cliff and ledge. The NPC would then step off to chase the player if thay will survive the fall. Hopefuly this wont be implemented on the scryers or aldor lifts in warcraft though for anyone that has badly timed the aldor lift you'll know why.

If you alow for more layers of polygons you could have some programmed to overide the walking space mechanic and let the NPC know theres an object that it can jump on if need be.

Jumping mechanics would probably be handled by three types of jump lines. One thats a one way jump and cant go back, one that alows falling off a small ledge if you back track and the other that alows for turning around and jumping back the way the NPC jumpecd in the first place.

I tend to visualise stuff like this and its hard to describe so i'm sorry if you cant pick though what i'm trying to say. If you can I hop e it helps.

Jumping is more or less a solved problem. In the past, I've seen it done either via connected pairs of annotations, or by special "jump"-type navigation mesh polygons marking regions that creatures can jump across.

I also recommend checking out these two articles:

"Jumping, Climbing, and Tactical Reasoning: How to Get More Out of a Navigation System" -- Christopher Reed, Benjamin Geisler (AI Game Programming Wisdom 2, 2003)

"Navigating Doors, Elevators, Ledges, and Other Obstacles" -- John Hancock (AI Game Programming Wisdom, 2002)

Thanks!

The whole nav-mesh idea is great. In a limited way, it was done for Kratos in the God of War series. What they did is have the map rendered in 2 strokes, the viewable map, and the playable map (userland).

Userland is where the character lives and can interact in. Which is why you cant jump off that big crate, or take a dive off a ledge.
The viewable map is all the fancy architecture that you can see, but not interact with. The objects were placed in the userland,

you could probably engineer something similar for the ai, using a raycast to determine accurate paths, and use simple heights to see if the AI can hide behind it*. That'd take care of flying enemies, tanks, motorcycles, humans, etc.

of course, It's a tad more complicated than simply rendering only a flat 2d mesh, but it'd provide more accurate results, especially if you have a very large group of various monsters/enemies attacking.

This approach would be a lot more complex, and the trade off would be CPU power. but then again, you could just have the player live in this space as well, and just have the AI aware of what's going on.

plus, some games could use some better optimization. If I recall correctly, F.E.A.R. ran like crud for the same visual effects of games in the same class.