Navigation System design process

[namreeb]

I've been spending a fair amount of my "wow time" lately designing a navigation system for a bot project I am involved with. I am (hopefully) nearing the end of the development process and thought that the community could benefit from some of the experience I've gained in the process. I have outlined this process below.

A brief outline of our development journey thus far. I realize that some posts are vague and skip a huge chunk of the development cycle. I am attempting to skim through the relatively common sense and/or arbitrary design decisions to move on to the more in-depth ones which offer more potential value to another brave soul taking this journey now or in the future. I understand that this road has probably been traveled by many before me, so if the information presented here is not relevant to you, please feel free to skip it.

1. Initially, it was decided that a breadcrumb (waypoint) system was not powerful enough for what we may want to do later. Specifically, our direction may (read: will) change as the world around us changes.
2. A navmesh system is the ideal solution, but requires immense amounts of work to do correctly.
3. If you consider the phrase "re-inventing the wheel", we have several wheels at our disposal to make things easier on ourselves. The two main operations we will need to do here are reading terrain data from our WoW installation and ultimately creating a mesh of a given region inside the WoW universe. For these two operations, we use StormLib to read the MPQ data and Recast and Detour to generate both our mesh, and for using the mesh to find an arbitrary path.
4. The intermediary operation here is creating a parser for the data inside the MPQs (ADTs, WMOs, etc.) and building a composite of all available geometry for a specific region. As far as I know, there is no "wheel" to do this that is both public and functional.
5. We ran into our first problem at this stage. WMOs inside a given ADT do not obey the boundaries defined by an ADT. That is, a house or cave can lie on the border between two ADTs. Fortunately, such a WMO is referenced by both ADTs, so we need only trim the WMO and rely on the fact that we will mesh the other half of it when we mesh the neighbor tile. Note that this requires creating some new vertices and triangles as there will undoubtedly be some that cross the boundary. The geometry for this is trivial.
6. Detour gave us an option for either a "tiled" mesh or a "static" mesh. A static mesh is used for levels where the terrain information is... (*gasp*)... static! A tile mesh is for levels where terrain information will be added and subtracted. Though our terrain doesn't change much, which meshed tiles we want to have loaded does change depending on our position. Also, we may want more than one tile loaded at once depending on our "patrol area". Note that since we have started this project, the author of Recast and Detour has begun to combine the static and tiled meshes into one structure in his API.
7. Detour also gives us an easy way to dump the mesh structure (for future use in path finding) to a file and read in later without concerning ourselves with the geometry used to create it. This means we can dump only the mesh, and not take up extra disk space by saving the source geometry.
8. Once you reach this point, it is only a matter of traversing the WoW universe automatically and mesh everything! I say only because the code for this is relatively simple, though it can take 10+ hours to do the whole thing. We had experimented with creating two mesh-generating threads, but we ran into situations where having the right two ADTs loaded uses up more than 2Gb of RAM, so we went back to just one. Since on the disk our data is only coming from a few select files (the MPQs), this also gave us some concurrency issues that just aren't worth it in my opinion.
9. When designing your meshing app, it is advisable (and perhaps self-evident) to group all of the MPQ reading, parsing and Recast and Detour functions into a library you can use inside WoW, then make a separate app to do the mesh generation which uses this same lib.
10. At this point, you have a mesh that is loadable by your "bot" and can be used to find your way from point A to point B. Note that nothing we have done here thus far requires you to be using injection, but for simplicity sake we assume you are.
11. Once we reached this step, we were faced with several design decisions and several potential problems. I am therefore splitting this up into a separate post.

Edit: After checking with them and receiving their blessings, I would like to be specific and say that MaIN was good enough to supply a parser and when I say 'we' I mean Apoc and I.

[namreeb]

... Continuing

I should reiterate at this point that our development (both on a coding and on a conceptual level) continues. Facts presented here seemingly as fact may turn out to be false, but serve as our working assumptions.

Our first in-game issue:

1. Once we were in game trying to generate a path, we needed a robust method to determine which ADTs' meshes to load. Identifying your current continent and your position are already covered on this forum and it is assumed you can do this.
   
2. It is not guaranteed that your path requires only one ADT, even if your path begins and ends in the same tile (for example, if there is a non-walkable mountain range dividing the ADT in half). Moreover, ADT selection can be very difficult if you are walking across several ADTs.
   
3. The best solution we have come up with for this is to employ a kind of 'macro pathfinding'. When Detour generates a navigation mesh, it identifies what it calls 'portals', which are walkable polygons on the edge of a tile which can reach walkable polygons on the neighboring edge. More plainly, it locates doorways out of a given tile which have a corresponding doorway on the other side. Our macro pathfinding solution says that as the mesh is being generated we path-find from every portal to every other portal on the current tile, saving the walkable path distance between them.
   
4. Once an entire continent has its mesh generated, the portal information we've produced will, when assembled, give us an enhanced reachability matrix for every portal in the continent (by enhanced I mean that we not only know reachability = yes or no, but the distance in question for neighboring portals). We can use this information to run a path finding algorithm on (say A*) to find the optimal portal selection for our journey. This will dictate which ADTs to load, and enable us to generate the detailed path from start to finish.
   
5. Note that there is a potential for optimization here in how you generate the path. Consider a journey from the Blood Elf starting area to Booty Bay. This will require a large number of ADTs and the path find could take a VERY long time (perhaps several minutes), during which time if you simply call the path finder, the WoW client will be frozen; not to mention that you will likely run out of memory. There are two potential solutions to this. Either you create a separate thread to do the path finding so that the client does not freeze, or if you are really clever, you can also generate the path incrementally. Remember that from the macro path finding we know which portals we will be taking. Let us also assume we were clever enough to store the portals exact x, y, z coordinates when we identified them. An incremental path find would begin by simply finding the path from your start position to the initial portal. This will take substantially less time than the worst-case scenario mentioned above. With the separate thread, you can begin generating the path from the first portal to the second portal while you are en route to the first portal (I hope this is clear!). This process is then repeated while you are en route to the second portal from the first, and so on until you generate a path from the last portal to the final destination. Note that this method also limits the amount of ADTs you need to have open at a given time, which can very quickly become a serious memory problem.
   
6. We have not begun experimenting with long-range journeys yet, so this solution remains untested. If problems arise, I will be sure to update this posting.

Our second in-game issue, and the reason we have not tested long-range journeys:

1. To put it plainly, even short-range journeys don't work!
2. In addition to the terrain and object data the client is aware of, the server introduced dynamic game objects to the client when the player moves in range of them. That range, I believe, is 100 yards (the unit of measure in WoW coordinates).
3. Dynamic objects can be anything from a relatively insignificant stop sign to a very troublesome tree or fence. We can get from the client's memory the file name of the model, as well as its position and orientation.
4. This is the current problem we are facing, and I've come up with three solutions.
5. Solution 1: Implement some sort of obstacle avoidance logic to try to blindly move around the object. In my opinion this is a dirty, nasty, stinky, ugly kludge and will only be seriously considered if other options prove impractical.
6. Solution 2: Reload the relevant tile(s) geometry and regenerate the mesh(es). The pros and cons we've come up with thus far for this solution are as follows:
   
   Pros:
   * Highly accurate. Our new mesh will incorporate the new geometry and give us detailed information about how to walk around the object.
   * Robust. This will not only allow us to walk around an object, but potentially over or through it
   Cons:
   * Slow! Regenerating a mesh takes a long time. After creating the mesh for Azeroth and Kalimdor, we averaged about 80 seconds per ADT.
   * Slow again! We cannot possibly see all dynamic objects in an ADT, thus we will be re-meshing it repeatedly. Note that there are probably nice and clean ways of modifying your mesh only once for each dynamic object. This would be self-defeating, however, in the case of an opening door or the intermittent Darkmoon Faire. Too many special cases in this solution, in my opinion.
   * Slo... well, not optimal! This would render the pregeneration of meshes almost entirely pointless. All that would be worth doing before the game runs is to clip the universe down into manageable sized tiles. Right now for us a tile is an ADT, but if you were to choose this method you might turn that in to say 100 tiles per ADT (a 10x10 square grid).
7. Solution 3: Amend the mesh by replacing those polygons which have a dynamic object in them with a new polygon or set of polygons which exclude the area occupied by the non-walkable triangles of the model.
   
   Pros:
   * Almost as accurate, if done cleverly enough.
   * Allows us to keep our pregenerated mesh.
   Cons:
   * Hard! I have not found anyone doing anything like this, so the math to do this must be largely original. I believe I have a solution in mind, which I will outline later in my "mesh amendment" discussion.

Lastly, a list of things we have not implemented yet either in code or even very deeply in concept:

1. Cost. This will be needed for those terrain triangles which are slower to traverse than others. Right now this is just water.
2. Highway preference. Traversing Stranglethorn Vale in the shortest route may not be the quickest as you will likely die over and over because of invisible gorillas jumping out at you. Once we have cost I assume we will have a method of giving preference to highways and roadways. Once this is done, it will simply be a matter of identifying the appropriate textures.
3. We need some way to determine (hopefully automatically as opposed to manually defining black-out areas) where NOT to go. For example, walking through Crossroads as an Alliance character.

[namreeb]

Mesh Amendment Thoughts...

Sorry this is not very organized or coherent. It's an on-going thought process, and one that may be completely wrong. I am separating this from the other two posts to be explicit that nobody should try implementing because you assume that I mention it here that the solution is viable.

First I thought we would just take a given dynamic object's model, and 'flatten' it (or project all vertices down onto the plane of the terrain polygon it is on) and use the bounding area as our exclusion. It occurred to me though that, for say a huge canopy tree, the overall width of the model may be large, but we are only concerned with avoiding the trunk. That is, the leaves are something we can easily walk under.

So, let us instead project onto our 2-D space the vertices of the model which are less than our walkable height above the given terrain plane.

This will give us a collection of dots, for which we have to find a nice and tight boundary for. For our purposes, we will assume this is a convex polygon (specifically known as a convex hull). For this, we turn to a Graham Scan. To read about a Graham Scan, go here:

Graham scan - Wikipedia, the free encyclopedia

For a neat Java example, go here:

Convex Hull: Graham's scan

So, once we do this, we will have a polygon defining an area to remove from the mesh region defined by a composite of polygons. This should be an acceptable solution in both accuracy and efficiency, if done correctly.

A couple of thoughts:

I haven't even started considering the math involved in removing a polygon from a larger polygon (or composite of polygons). Anybody have any insights on this? Presumably we'll have to add vertices to the list and edges to connect them to the mesh. We'll then probably need some sort of cleanup function to go and remove the internal flattened vertices as well as the removed vertices from the original mesh, both of which will now be 'dangling'; that is, no edges connected to them.

In the case of an archway of some kind, we may end up with multiple convex hulls. Not sure how to distinguish these other than identifying some kind of outlier groups. Anybody have any insights on this?

It would be great if we could save this work into the mesh file into an amendment section. As I stated before in the re-meshing case this would get tricky because there are some objects which are more dynamic than others! I'm thinking about things like the Darkmoon Faire, or the gate into Baron's room in UD Strat, or the BG gates, etc.

[mongoosed]

This sounds like the be-all end-all for bot navigation, and it looks very promising. In tandem with unit information you could write a bot that implements advanced behavior in real-time based on information from the current terrain and target locations. It is almost as if you are coding new AI for the game's npc's themselves.

Great work namreeb.

[Apoc]

Just an amendment to one of his 'facts'; I've actually tested running a very long path. (Via loading an entire continent at once, Azeroth) From EPL -> Booty Bay takes less than 10s to generate a path. Although; it took nearly 2GB of memory to store the path. The pathfinder is very fast, so the issue lies with memory consumption.

[adaephon]

This sounds really interesting .

A few suggestions:

1. In regards to your mesh amendment: You discuss including cost into your path finding to avoid water / prioritise highways. Presumably this means that your pathing mesh will have a cost value associated with each polygon/triangle. If you can dynamically modify this value (which you should be able to, and rather efficiently), then instead of trying to remove polygons from your pathing mesh you could simply mark their cost as ridiculously high if they contain a dynamic object.

2. Once again in regards to your mesh amendment: If you are grabbing the model out of the MPQs (note: I haven't done extensive work here) then presumably you could also grab the associated collision data, which would be some sort of bounding box. This would be much more simplified and would also remove some of the issues associated with large canopy trees and the like.

3. @Apoc: If memory use is the issue rather than speed then you could use a Level of Detail system for your path similar to what graphics rendering does. Find the whole path if that only takes a negligible time, then remove all pathing data except for a few nodes from all but the current tile (for instance you might include full path for current tile and only entrance / exit / midpoint for other tiles). Simply regenerate the path for each tile once your character reaches it

[namreeb]

1. In regards to your mesh amendment: You discuss including cost into your path finding to avoid water / prioritise highways. Presumably this means that your pathing mesh will have a cost value associated with each polygon/triangle. If you can dynamically modify this value (which you should be able to, and rather efficiently), then instead of trying to remove polygons from your pathing mesh you could simply mark their cost as ridiculously high if they contain a dynamic object.

The problem with that is the mesh polygon in question may encompass an area much larger than the base of the dynamic object. It could conceivably encompass half of the ADT. The only area we want to be marked as impassible (or extremely costly in this scenario) would be the convex hull of the dynamic object in this polygon.

2. Once again in regards to your mesh amendment: If you are grabbing the model out of the MPQs (note: I haven't done extensive work here) then presumably you could also grab the associated collision data, which would be some sort of bounding box. This would be much more simplified and would also remove some of the issues associated with large canopy trees and the like.

Not sure I follow you here. What do you mean by collision data if not the geometry of the model? I don't see what is more simpler than what.

3. @Apoc: If memory use is the issue rather than speed then you could use a Level of Detail system for your path similar to what graphics rendering does. Find the whole path if that only takes a negligible time, then remove all pathing data except for a few nodes from all but the current tile (for instance you might include full path for current tile and only entrance / exit / midpoint for other tiles). Simply regenerate the path for each tile once your character reaches it

I believe you are suggesting the exact same thing that I presented in item #5 of our first in-game issue.

[~OddBall~]

This is in regards to onyx?

[adaephon]

Yeh number 3 is fairly similar to what you were discussing.

As for the collision data, games will normally use a simplified mesh for collisions rather than trying to calculate over the entire complex mesh (i.e. a bounding box). If you're talking about intersecting the base of the dynamic object with a polygon or several in your navigation mesh, then you could potentially be intersecting a polygon with several sides (imagine the base of a tree might be more circular in shape with 30 edges). However, for determining collisions, the game might use this object's bounding box. At the base of this dynamic object, the bounding box will likely be a square, and thus intersection with your nav mesh will likely be a much simpler process, but functionally no less accurate.

[Apoc]

Yeh number 3 is fairly similar to what you were discussing.

As for the collision data, games will normally use a simplified mesh for collisions rather than trying to calculate over the entire complex mesh (i.e. a bounding box). If you're talking about intersecting the base of the dynamic object with a polygon or several in your navigation mesh, then you could potentially be intersecting a polygon with several sides (imagine the base of a tree might be more circular in shape with 30 edges). However, for determining collisions, the game might use this object's bounding box. At the base of this dynamic object, the bounding box will likely be a square, and thus intersection with your nav mesh will likely be a much simpler process, but functionally no less accurate.

Usually true. But have you played WoW? WoW very rarely actually uses bounding boxes. It seems they more or less just use the terrain data as the collision, and just TraceLine for collision tests. So if we use the usual rect-based collision method; we lose quite a bit of level geometry, that has the possibility to completely remove valid paths. (Think for instance; winding paths that can be traversed; but using the rect-based collision boxes, would be completely cut out, and thus not allowing us to get to some area of the world which is usually easily gotten to.)

[omfgman]

About the gameobject collsion issues:

You have the meshes of those objects from the client files.
Coudn't you just read their positions from a private server database and add them to the navmesh? (i guess those coordinates are sniffed from official servers so it should be quite accurate?)

[namreeb]

About the gameobject collsion issues:

You have the meshes of those objects from the client files.
Coudn't you just read their positions from a private server database and add them to the navmesh? (i guess those coordinates are sniffed from official servers so it should be quite accurate?)

Yes. This was the solution I simply forgot to mention. It's not one that I prefer because I don't trust the accuracy of those databases. It also does not account for things like opening doors.. though if that is our only remaining problem it shouldn't be too hard to just hard code exceptions for them somehow.

This is in regards to onyx?

That's what we are designing this for, yes. However, nothing about what we are doing is unique to Onyx.

[audible83]

For dynamic objects. Instead of remaking whole adt, why not tile the adt into smaller tiles and remake the tiles covered by the object?

[!@^^@!]

Very interesting indeed, however since you say that this might be a bot movement/navigation killer, i can't stop wondering what about flying mount navigation because i don't see that you have taken that into consideration anywhere?

(yay first post in +2 years lol)

[audible83]

Flying mounts are relatively easy. However you need support for a few flags to be set, like CanFly IsFlying etc and then add +50 on the Z value.

Alternatively, you can make a seperate Flying mount mesh. Lots of possibilities.