Navigation System design process

[namreeb]

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

If you look at the cons, this was part of my solution #2. The problem with this is that a) quite a few tiles, regardless of their size, will need to have their mesh regenerated. I wish I had specifics on this, but I don't. And b) Some dynamic objects actually change, so we want a quick way to adapt to this.

Also, if you employ a macro pathfinding to determine which tiles to load, this has the potential to make your portal dataset much, much larger.

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?

Sorry, I forgot to mention that. 3-D (flying and swimming) is not even on my radar screen at the moment. Recast and Detour doesn't do 3-D as yet so if I want a proper mesh I'll probably be writing it myself. Not important to us yet.

[!@^^@!]

aha, well i was just thinking about cataclysm since it's gonna introduce flying mounts in the old continents so 3d navigation seemed like a reasonable feature to implement while at it...

btw regarding those dynamic objects, have you considered elevators like the one in howling fjord? or does that kind of object work somehow else im not aware of?
as a suggestion to a possible solution of elevators i was thinking about hardcoding thier positions and make the bot see them as the "portals" you mentioned...
(sorry if it's a stupid suggestion, im not really sure i've understood everything correctly as im new to this)

anyway it's hellwa good job even getting so far with this so keep it up

[namreeb]

3-D is definitely necessary for a "complete" navigation system. I just haven't started to tackle it yet =)

I haven't looked in to the details of elevators in Thousand Needles/Searing Gorge as yet, but it is a good example of an actually-dynamic dynamic object. My hope is that the ultimate solution to this issue will allow me to recalculate the object's impact on the mesh as the object's position/orientation changes. This would also mean the amendment process would have to be both efficient and probably rate limited (every nth frame or some such thing).

Edit: As I think about it, the elevators might be rather tricky and end up being a special case. The reason is that you will have to project their position based on the time it will take you to travel to it. That is, you could be 80 yards from it when the elevator is at your level and erroneously set course to it not realizing it wont be there by the time you arrive.

[adaephon]

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.)

Ah ok, as I said I haven't really gotten into exploring the internals of WoW much yet - I'm intending to now that uni is finished and future employment is sorted I might actually have some free time. I have noticed that the game uses simplified collision geometry in some locations (Stormpeak's large staircases jumps to mind) and assumed dynamic objects would use something similar.

[adaephon]

Also, the following may be useful for your mesh subdivision:
GPC General Polygon Clipper library from The University of Manchester
General Polygon Clipper - Wikipedia, the free encyclopedia

[Apoc]

As for the issue with elevators and whatnot; once Mikko adds the ability to add 'jumps' (not the same as a portal; a jump literally 'jumps' you from one position to another) the fix is rather trivial. We simply read the DBCs (yes; all transports, including elevators, boats, zeps, etc) and figure out where we need to add the jumps, and viola.

There's lots of stuff Mikko is working on (<3 the guy for being so awesome with us), when we have more tools to play with; we'll be able to generate some really awesome meshes.

[!@^^@!]

woa nice, you should almost consider selling the library for something like 10% of every bot license sold :P

[RoKFenris]

About your problem with server side / dynamic objects, are you able to create an "overlay" mesh, something that when enabled gets used instead of the piece of the usual mesh it covers? If you are able, I think it would be the easiest way to handle server side (and specially dynamic) objects, with the extra advantage that you could also create hand-crafted meshes for places where the automatic meshing might me less than acceptable, or where you want to deviate from the usual behavior (your crossroads example comes to mind).

For long range navigation, it might be interesting to create a navigation graph with WoW's default subzones. I believe their definition can be read from WoW's data files, their number is low enough that the navigation graph could be coded by hand if needed, and their connections should be already logical enough. They don't cover the whole map, though, but you can always find the closest reachable ones to both starting and end points and plot your course from that.

[klufas]

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.



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

May I ask what Onyx is? Searched with no luck on a definitive answer.

[pendra]

I've been working on a navmesh based system along similar lines off and on for the last few months. I've shamelessly stolen a lot of ideas from recast but I'm not using any of mikko's code directly since I need to be able to deal with swimming, flying, and phased terrain, jump links, etc. I also find that I can make a somewhat cleaner implementation if I write it for wow only, as opposed to trying to remain general purpose.

It's a pretty massive undertaking. I've got about 20k lines of code so far and probably have another 20k to go before it's really practical.

Here's some stuff I've found that might be interesting to you per your planning.

1) Every M2 in the game that is collidable has a collision mesh. The WoW Dev wiki calls this a bounding volume, but that's not what it is. For example, the collision mesh of a tree is just the trunk, no branches, and has a simplified shape to reduce the computational complexity of the collision detection.

If you input only the collision meshes into recast you can avoid tree branches and other doodads that are not collidable.

The majority of m2s are not collidable, shrubs, grass, graphical accents on WMOs, etc.

2) There aren't very many dynamic collidable objects in WoW, so I wouldn't get too hung up on them at least for a first pass implementation.

All I've found for dynamic collidables are:

-- Stuff that moves, doors, zepplins, boats, etc.
-- Stuff the player can interact with, signs, chairs, combat dummies, etc.
-- Stuff that is not there all the time, like seasonal doodads, stuff related to world events, etc.

If you think you have trees and fences that are dynamic you're probably missing something in your parsing of the static data. I haven't seen any of that at least in Kalimdor/Eastern Kingdoms.

Cataclysm is going to bring phased terrain which will make this a lot more painful, of course.

I chose to deal with dynamics by hard coding the doors and taxis and pretending everything else is static. If we encounter a collidable object that we don't already know about, then remember it and regenerate the static mesh to include it.

This means my characters will never walk where santa is sitting in ironforge, even in july, but who cares. There aren't very many such things.

3) I would not try to deal with avoiding hostile mobs and such in the navigation mesh. Just build a heat map overlay that increases the cost of using particular regions based on the probability of hostiles in the area. Then when you pathfind you just take the heat map into account when calculating path cost. This solves your crossroads problem and your STV problem. Finding roads and stuff will probably prove unnecessary if you do this, since you can chose to avoid high heat paths automatically if you want to.

The heat map data can be accumulated by your bot itself, just remember the locations of all the non-aggroed mobs you see on your radar and store them. Then all you have to do is login with a lvl 80 somewhere and run around the world data mining to prime the system.

4) Using "macro pathfinding" over ADTs/tiles doesn't work particularly well in practice, I find, since there are too many tiles where you have multiple elevation levels the player can walk on. For example, if you're inside a cave, perhaps you can walk north out of a tile, but you could not if you were on the surface.

A better way, I think, to decrease compute time for long range navigation is to drop breadcrumbs onto your navmesh, and then precompute the navigation path tree between all breadcrumbs ahead of time. When you are pathfinding you can then use the navigation path tree to help on long journeys. You just navigate to the nearest bread crumb, follow the tree to the breadcrumb nearest your destination, and local path find from there.

A good way to drop breadcrumbs is as follows:

a) Drop one at each point of interest. flight masters, inn keepers, NPCs that have quests, etc.

b) Add more breadcrumbs on the resulting tree until each edge in the graph is below a given length.

This will tend to give you paths between all major points of interest and on the roads between them, and you can rely on never having to do local navigation for paths longer than a few hundred yards, and you only have to load ADTs for the bits on the ends.

6) Avoid doing any kind of projection/processing on the raw WoW triangle geometry. There are a lot of degeneracies. If you need to add additional objects to the mesh, etc, do it the way mikko does it. Rasterize them into the raw voxel space and then compute a mesh from that. Computational geometry is hard and numerical precision issues are very problematic.

[namreeb]

You're right about the doodad issue. A bug in our scaling was causing models with a scale less than 1.0 to be set to 0. That was our issue.

In response to your #4, in our solution, each edge of the tile will have a list of portals (one portal meaning an exit from the current tile and an entrance to the next one). The entire tile will also have a map of each of its portals distance from one to the other. In your case of a cave, the pathfind would fail when it tries to lookup the path distance from the portal of the tile you just entered to a potential exit portal. Does that make sense?

[attn]

It might be not related directly to topic but I've decided use pre-recordered Routes for bot to navigate on long distance, for ex. travel between zones. When route recordered I assume player always choose shortest/safest route which is hard implement in navigation mesh.

It also might simplify navigation mesh to be implemented only for local zones.

[namreeb]

As far as simplicity goes, if you are generating the mesh individually for each ADT, you'll have to have a way to transition between tiles (what if you're grinding right on the border between two, for example?). Our solution for this (a macro-pathfinding on the portals between tiles) is an ideal solution for longer journeys as well. Uncompressed, the mesh for all of Azeroth is only ~180Mb, so memory usage will not be an issue.

[namreeb]

Just an update: I have begun the portal identification code.

[namreeb]

Another update: We now are generating a list of portals for each tile in a continent. Azeroth has 31,000 of them. We are optimizing that list by combining equivalent edges (right edge of a tile and left edge of the tile to its right) and using their intersecting areas. This brings the count down to about 6700. After removing those portals from which you cannot path to any other portal, the number gets even smaller.