[/font]
[/font][size="5"][font="Microsoft Sans Serif"]
Part 1: World Description[/font]
[font="Microsoft Sans Serif"][size="3"]The game world is logically divided into lots (i.e. user-changeable areas) and the rest of the world (users can only interact with this area and cannot actually build on it or do much to change it). The lots are inserted into the world at essentially random places and they are pretty much completely dynamic, from changing terrain to walls to objects placed on them), but are at least guaranteed to be convex polygons.[/font]
[font="Microsoft Sans Serif"][size="3"]The world also has roads and paths that are essentially cheaper for agents to travel on, so they tend to move to them and then along them for longer trips. Some roads are for cars and bicycles only, some are useable by cars, bikes, and pedestrians and some are for bikes and pedestrians only. There might end up being other permutations or even more types of agents as well.[/font]
[font="Microsoft Sans Serif"][size="3"]The world also has water areas (both sea and lakes/ponds) that will be routed upon as well, by various agent types (swimmers, boats, etc). Steep-sloped areas might also be routable via climbing animations, but more expensive to move on for path-finding, so they'll only be used in specific circumstances and/or by specific types of agents.[/font]
[font="Microsoft Sans Serif"][size="3"]Finally, a number of objects may be routable as well - bridges, for example. And since objects can be placed or deleted by users, the objects must have routing information built into them that can be "attached" to whatever data structure(s) we end up using to represent the world, lots, etc.[/font]
[size="2"][font="Microsoft Sans Serif"][size="3"]Lots are connected to the world via portals. Routable objects will also be connected via portals. Portals are simply links between 2 different pieces of the world and may or may not be on the same navmesh/grid/graph (or whatever we end up using that has its own local-space coordinates) and can be traversed via normal movement, teleportation, or a custom animation. Other examples of portals would be stairs between levels of a lot (custom animation to move the agent), doors between rooms (custom animation to move the agent and open/close the door), teleportals (instantly jump to another part of the world), or a boundary between land and water (move normally, then animate slower, then finally, change to a swim move-type or the reverse for exiting the water). Portals are by default open, but can be locked to specific agents. Like all edges between search nodes, portals can be one-way or two-way.
[size="5"]
Part 2: Requirements
[/font][font="Microsoft Sans Serif"][size="3"]1) Quickly and efficiently path-find (10-20 asynchronous path plan queries per frame, most of which will be short-distances) between different areas of the world, taking into account all of the following:
[/font]
- [font="Microsoft Sans Serif"][size="3"]the different types of areas that can be pathed-upon
2) Can very quickly handle synchronous queries that just ask whether or not a path exists between 2 points
3) Can handle relatively infrequent large updates to the world abstraction layer, but frequent small, local updates (i.e. objects moving within the world happens frequently and their footprints in the data must be updated, but large changes to lots will also happen (much less frequently) and will be allowed more time to
update if necessary. In other words, the pathfinding world data structures must scale from small, frequent changes to large, infrequent changes. Note that such changes will also be asynchronous and may affect current path plans in progress. Limiting the re-plans from this would be ideal.
4) Path plan queries must be able to account for changes in status of portals, lots, and/or routable objects for specific agents (i.e. portal 3 is locked for this path-find for this agent). These status changes will be sent by the caller as part of the path plan query. In addition, the caller will also specify the minimum width for the agent for this particular path-plan.
5) The results of the path plan must return a list of points for the path along with a set of points describing a corridor boundary to either side of the path that
describes the routable area around the center points of the path. The agent and the avoidance system will thus have enough information to freely move around the center of the path without doing a lot of expensive line-of-sights tests or replans.
6) The path planner will always return a path if one exists, but if one does NOT exist, then it will return a path that gets it as close as possible to the goal point.
7) Path planner must be able to account for local-space path-planning. For example, it must be able to return a valid path on a routable object that is moving within the world.
[/font][font="Microsoft Sans Serif"][size="3"]
[font="Microsoft Sans Serif"] [/font]
[font="Microsoft Sans Serif"] [/font]In my humble opinion, this is actually a very daunting list of requirements for a path planner! I've always been happy when given a difficult problem, however, so I started doing some research and lots of thinking.[/font]
[font="Microsoft Sans Serif"][size="5"]Part 3: Solution 1[/font]
[font="Microsoft Sans Serif"][size="3"] The first solution to this problem borrows heavily from the work my colleague and I did on a previous game's path planner. To start off, I realized that the world is too large for efficient planning using one big navmesh/grid/graph. A typical world in that game, for example, had well over 50,000 search nodes (which made A* go very, very slow) and the plans I've seen for this game's maps are at least that big. Thus, like the previous game, we'll start with an HPA*-based architecture (described in "Hierarchical Path Planning for Multi-size Agents in Heterogeneous Environments" at [/font][font="Microsoft Sans Serif"][size="3"][color="#0000ff"]http://harablog.files.wordpress.com/2009/01/haa.pdf[/color][/font][font="Microsoft Sans Serif"][size="3"]).[/font]
[font="Microsoft Sans Serif"][size="3"] To solve some known problems we ran into, we'll use navmeshes for all the layers and connect them where appropriate via portal nodes. The navmeshes will be composed of convex polygons and we'll strive to avoid long, thin polygons whenever possible when creating the Navmesh. The good news is, we already have code to create such a navmesh given our terrain and a quadtree with footprint boundaries for objects and other obstacles. It uses the GLU Tesselator and it's very fast - fast enough to use in real-time for relatively small meshes. The only problem with the existing code is that it can only generate the navmesh from scratch. Effort will be needed to allow it to update an existing navmesh to accommodate a small localized change. I'm assuming (for now) that this will be possible, even if it's a non-trivial task.[/font]
[font="Microsoft Sans Serif"][size="3"] To allow for quick queries on whether a path is possible or not, when we create the navmesh, we'll perform flood fills on the polygons and mark all connected areas with connection group indices. That way, to tell if a path exists is just a quick query to find the start and goal polygons, check their connection group indices and if they're not the same, then no path is possible.[/font]
[font="Microsoft Sans Serif"][size="3"] At the top layer of the hierarchy will be the world navmesh. Below that will be navmeshes that are embedded in it (such as lots or routable objects). The borders were a large problem in our previous game and I suspect still will be with this solution, but I have a few tricks to use some heuristics that I think will minimize this problem now. To the world mesh, a lot or routable object will simply be a polygon with edge costs based somewhat loosely on the structure of the interior of the routable area. For example, a "cluttered" lot might have a higher cost to enter than a completely clear lot. This is a non-trivial problem, however, and I expect that a fair amount of work will be needed to deal with the problems the borders between hierarchy layers inevitably introduces. Nonetheless, it IS a solvable problem.[/font]
[font="Microsoft Sans Serif"][size="3"] One optimization that is a big help for this problem is to add "preferred" entry points to the lots and routable object meshes. We didn't have those in our previous game and thus had to decide (by some complex heuristics based on the front door and mailbox positions on a lot) where the best entry points for a lot were. Mostly, this worked, but sometimes it failed
and caused some wonky paths. Having some pre-defined entry points would greatly help the path planner deal with the hierarchy-boundary problem, so we'll specify in the design that these will be needed for lots and routable objects as part of their navigation info. Users can then decide where to best enter their lot and designers can decide ahead of time where to enter/exit routable objects and we'll speed up the path planner by getting rid of the step to decide best entry points.[/font]
[font="Microsoft Sans Serif"][size="3"] Finally, the planner will keep an octree of all the navmeshes in the world so that we can quickly determine which navmesh any 3D point in the world belongs to. Note that this does introduce a restriction that no two navmeshes can occupy the same space in world coordinates. After talking with the designers though, this is fine.[/font]
[font="Microsoft Sans Serif"][size="3"] To query the path planner, the start and goal are provided along with any context info. The following algorithm is then followed:
[/font]
[font="Microsoft Sans Serif"][size="3"]1) Find polygons for start and goal point (along with which navmesh contains them).
2) Do "trivial" checks:[/font][font="Microsoft Sans Serif"][size="3"]
[/font]
- [font="Microsoft Sans Serif"][size="3"]If start and goal are in same polygon, return a straight-line path
[/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
3) Update navmesh data structures with temporary restrictions from path context (make costs infinite for edges of locked portals, lots, and objects)[/font][/font][/font][/font]If both start and goal are in the same navmesh, then do an A* search on that navmesh[font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
4) If start and goal are on different navmeshes, do an A* search on the navmesh that is in the highest layer. If they are both in the same layer (i.e. lot-to-lot path planning), then do a path find in the layer above them[/font][/font][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
5) Go through each node in this initial path and find the nodes that correspond to entry points, lower-layer navmesh points, and exit points (always in that order, with the exit point being optional if the lower-layer navmesh point is at the end of the path (and the same logic for the start point and initial entry point). Note that because we have preferred entry/exit points for our lower-layer navmeshes, we can skip the step that was required in our previous game to find the "best" entry/exit points before running the lower-layer search as well as the code that changed the higher-layer path to use the modified start/exit points instead.[/font][/font][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
6) For all other points, find the widths around them that are clear so that we can return the corridor around the path. Interestingly, this turned out to be a non-trivial problem when I looked into how to do this, but that research is also how I ended up finding the link that led me to Solution 2[/font][/font][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
7) For each set of special points, perform an A* search on the navmesh that corresponds to that higher-layer point using the entry and exit points as the start and goal points[/font][/font][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
8) Repeat steps 5 - 7 recursively for lower-layer navmeshes until all special nodes are filled in with paths at the top layer[/font][/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"]
9) S[/font][font="Microsoft Sans Serif"]mooth the path, fill in elevations as needed, etc.[/font][/font][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
10) Restore default edge costs of nodes affected by step 3[/font][/font][font="Microsoft Sans Serif"][font="Microsoft Sans Serif"][size="3"]
11) Return the results[/font][/font]
[size="3"][font="Microsoft Sans Serif"][size="2"] There's likely some steps that I'm missing as I'm doing this from memory, but I think that's the gist of how solution 1 would work. It's basically a generalization of how we did path planning for our previous game using navmeshes instead of grids and waypoint graphs with some improvements and optimizations.[/font]
[font="Microsoft Sans Serif"][size="3"]
[/font][font="Microsoft Sans Serif"][size="3"]How do we handle navigation on navmeshes that are moving around? Well, the answer is deceptively simple - as part of the return values for each path point, we return a pointer to the navmesh it belongs to. The navmesh itself can be queried by the animation/movement system at each step to see what the current offset is (and this can be done recursively so that you can navigate on a navmesh that is moving within another navmesh that is moving within....well, ad nauseum. Just add all the offsets, like animation does with bone offsets). There are a couple of problems with this I can think of, and I suspect there's a few I haven't thought of as well, but I believe they're solvable, so I'm not going to worry too much about it right now.[/font]
[font="Microsoft Sans Serif"][size="3"] Note that handling such things as allowed movement types and agent width restrictions would be handled at the A* level. Handling movement types is relatively easy (I think) by just checking against valid movement types allowed by each edge (set during navmesh creation), but width restrictions may not be. I know it's possible without being forced to use different navmeshes for each agent size as I know other games have done it, but I'll need to do more research to figure out details. Again, though, I believe this to be a solvable problem, so for now, I'm ignoring it in the interests of getting a high-level design done in a timely manner.[/font]
[font="Microsoft Sans Serif"][size="3"] So, that's solution 1. It's sketchy in parts and there's too much hand-waving in other parts for me to feel comfortable with it as a recommended architecture, so I would definitely need to do more research and some prototyping to flesh things out more...which was exactly what I was doing when I ran across solution 2...
[/font]
[font="Microsoft Sans Serif"][size="5"]
Part 4: Solution 2[/font]
[font="Microsoft Sans Serif"][size="3"] While doing some research for solution 1 (namely, figuring out how to determine the path corridor points), I stumbed across a thesis by Douglas Jon Demyen called "Efficient Triangulation-based Pathfinding" ([/font][font="Microsoft Sans Serif"][size="3"]http://skatgame.net/mburo/ps/thesis_demyen_2006.pdf[/font][font="Microsoft Sans Serif"][size="3"]). It's a hefty paper (141 pages) and it took me a couple days to read and fully grok it, but it's worth it. The way he does path finding is pretty brilliant, in my opinion, and drastically cuts down the number of nodes that need to be searched. I'm honestly surprised that I haven't heard more about this considering that it was published in 2007.[/font][font="Microsoft Sans Serif"][size="3"]
[/font][font="Microsoft Sans Serif"][size="3"] For solution 2, the world would be structured somewhat like solution 1 except I'm seriously debating whether a hierarchy is needed. At this point, I'm leaning towards no and that of course would solve the problems that are introduced by a hierarchy. However, before I definitely answer that question, I really need to prototype this system and see how well it performs on a large navmesh.[/font][font="Microsoft Sans Serif"][size="3"]
[/font][font="Microsoft Sans Serif"][size="3"] The three benefits to this system compared to solution 1 are:
[/font][font="Microsoft Sans Serif"][size="3"]
1) Because it uses a Constrained Delauney Triangulation method, there are known methods to quickly do small localized updates to the navmesh[/font][font="Microsoft Sans Serif"][size="3"]
2) Despite using triangles instead of full-fledged n-sided convex polygons, there are, in general, far fewer nodes to search in a typical path-find query. The reason for this is because the method reduces the search down to just the major decision points on a path and progressively fills out the path with almost pre-set path-finds on a smaller and smaller scale. In a way, this is a built-in hierarchy of path-finding. In addition, it tends to quickly know where dead-ends are and completely ignore them without searching them at all. This by itself is a HUGE optimization over A*[/font][font="Microsoft Sans Serif"][size="3"]
3) Because of the smaller number of nodes searched (in general), it may very well eliminate the need for a hierarchical path-planner architecture. The hierarchy is already built into the navmesh! While I need more data to confirm that this will be faster and that it will handle meshes of the size we use without problem, I'm reasonably sure that it will handle larger meshes in general and could at least get rid of one or more layers of the hierarchy from solution 1.[/font][size="2"][font="Courier New"][font="Microsoft Sans Serif"][size="3"]
[/font]
[/font][size="3"][font="Microsoft Sans Serif"]The secret is how it constructs the navmesh in the first place by denoting each triangle/node as a level 0, 1, 2, or 3. Level 0 nodes are islands not connected to any other nodes. Level 1s are leaves of a tree that is essentially a dead-end. Level 2 nodes are roots of level 1 trees that connect the entire tree to other level 2 nodes or level 3 nodes (though there is a stricter definition to handle some special cases like loops). Level 3 nodes are the top layer and they are where all navigable edges of the triangle are unconstrained and joined to level 2 or level 3 nodes only. There's some special case handling for rings and such, but essentially assigning levels to each node does most of the work of path planning right off the bat by pre-finding the dead-ends, corridors, and major decision points in a map. It's pretty brilliant, I think, and much easier to understand intuitively (to me, anyway) than other path-finding data representations. It emulates the way our brains do path-finding much better than any other method I've ever seen.[/font]
[font="Microsoft Sans Serif"][size="3"]Another optimization that is built into the navmesh generation algorithm is finding choke points - since we know where the "corridors" are, we can pre-compute the narrowest point along that corridor and then use that as a quick search at the higher layers of the path-find to cut off whole corridors at a time if they are too narrow.
[/font][font="Microsoft Sans Serif"][size="3"]Of course, it's not all good as there are still a few problems and some requirements I'm not sure the architecture will currently handle (portals, for example) and I suspect that there will be some interesting problems when trying to stitch together the navmeshes. I'm also sure there are some problems I haven't thought of yet. And this is assuming I even understood what I read correctly (which, given that it was a 141 page thesis, is not guaranteed!). Nonetheless, I believe it warrants further investigation and prototyping before even trying to complete the research for solution 1.
[/font][font="Microsoft Sans Serif"][size="3"]Based on all this, these would be the general steps for a path-finding query, many of which are still the same as solution 1.
[/font][font="Microsoft Sans Serif"][size="3"]
1) [/font][font="Microsoft Sans Serif"][size="3"]Find triangles for start and goal point
2) Do "trivial" checks[/font][font="Microsoft Sans Serif"][size="3"]
[/font]
- [font="Microsoft Sans Serif"][size="3"]If start and goal are in same polygon, return a straight-line path
[/font][font="Microsoft Sans Serif"][size="3"]
3) Check for other special cases that need to be handled separately (see section 7.1 of Demyen's paper)
4) [/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"]Update navmesh data structures with temporary restrictions from path context (make costs infinite for edges of locked portals, lots, and objects)
5) [/font][/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"]Find the most abstract layer for the start and goal nodes, which will determine what layer the initial search is run in
6) [/font][/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"]Run TRA* (Triangulation Reduction A*, described in section 7.2 of Demyen's paper) on the layer determined in step 4. I don't fully understand this part yet, so I'm sure there's more to it than this, but that's what I'm working on researching now
[/font][/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"]
7) For all returned points, find the widths around them that are clear so that we can return the corridor around the path. The good news is that there's some built-in functionality for this already in the navmesh abstraction and an algorithm is presented in the paper to find this information. Hopefully, it will just be a matter of using the algorithm at the appropriate time
[/font][/font][font="Microsoft Sans Serif"][size="3"][font="Microsoft Sans Serif"]
8) Smooth the path, fill in elevations as needed, etc.[/font][/font][font="Microsoft Sans Serif"][size="3"]
9) Restore default edge costs of nodes affected by step 3[/font][font="Microsoft Sans Serif"][size="3"]
10) Return the results
[/font][font="Microsoft Sans Serif"][size="3"]So that's where I'm at right now in my search for a good path finding architecture for our requirements. It's all very rough and hand-wavy still, which tells me I have more research to do.[/font]
