Thursday, March 25, 2010

My Favorite Protyping Environment

We kinda pioneered this idea with Kimmo of Mountain Sheep some moons ago. Before that I always used to have 1MB DebugDrawProtos.cpp which was hooked to my current game where I had all my protos hidden behind a console var :)

The idea is simple:
You have a simple project, where you can add one .cpp file and it will compile and appear as a new prototype to choose from when you start your application.
In order to make the threshold of adding something new low, all the protos are based on a simple base class, which has init(), update(dt), and draw() functions. Sometimes I customize this, if I'm prototyping just one feature, like with Project Cane.

This allows me to quickly create new sketches to try a bit alternative version and do AB testing between the two. Add IMGUI into the mix and you can have bunch of parameters to tweak too in no time!

This is how Project Cane is structured too. I have over ten or so different methods prototyped currently (will release it after GameAIConf) and I don't need to hesitate to add something new when I read a paper and get some crazy stupid new ideas while walking to work.

Detour Serialization API

I implemented some helpers to make the Detour navmesh data serialization simpler. I chose to simplify the method I disucussed in my earlier post. A bit more for you guys to implement, but the feedback was that most people would not use my advanced features anyway. Once you get to the point of making save games and run into a problem, let me know. I try to improve the API.

Detour API Changes

This change induced a couple of API changes.

First you will notice that the init() function has changed:

    bool init(const dtNavMeshParams* params);

I simply moved the parameters to a struct, the behavior is the same. I also added a function to return the init values, so it makes easier to store the navmesh state.

Second change is in addTile():

    dtTileRef addTile(unsigned char* data, int dataSize, int flags, dtTileRef lastRef = 0);

The tile coordinates are gone, they are now stored in the tile data instead. So they need to be passed to the dtCreateNavMeshData instead:

        params.tileX = tx;
params.tileY = ty;
...
if (!dtCreateNavMeshData(&params, &navData, &navDataSize))

The obscure boolean flag is gone now, and I added an enum flag instead (DT_TILE_FREE_DATA). Much more readable now.

There is new paramter too, lastRef. It can be used to put the tile at specified location and to restore the salt. This ensures that dtPolyRefs which are stored to disk will remain valid after a save game.

You will also see that removeTile() lost the coordinates too:

    bool removeTile(dtTileRef ref, unsigned char** data, int* dataSize);

The function uses tile reference to specify which tile to remove. I added a bunch of accessors to convert between tile pointers and refs and to query tiles at certain locations.

This allows to save and load tiles without loosing the navmesh state. See Sample_TileMesh::saveAll() and Sample_TileMesh::loadAll() as an example how to use this new functionality to save and load a whole dynamic navmesh state.

dtMeshHeader now has userId field too, which can be used to identify a navigation mesh, and you could load it from your resource pack instead of reading and writing the whole navmesh with your save game.

Delta State

New addition to storing navigation mesh structure, I added functionality to store just a navmesh tile state. This is useful if you change the polygon area type or flags at runtime and wish to restore that state after you have loaded your level.

First there is a function which returns the amount of space (in bytes) which is required to save the stave of the tile:

    int getTileStateSize(const dtMeshTile* tile) const;

Now that you have allocated a buffer (you may want to allocate just one buffer which is maximum of all the buffer sizes and reuse it), you can fill it with the data using following function:

    bool storeTileState(const dtMeshTile* tile, unsigned char* data, const int maxDataSize) const;

And the just dump that data to disk.

When you want to restore the state, just read the data and call this functions:

    bool restoreTileState(dtMeshTile* tile, const unsigned char* data, const int maxDataSize);

That's it. A little less automatic than what I hoped. Save games are special, and when to store and what is so game specific that I don't want to build too much of that into the core library.

Tuesday, March 23, 2010

Geometric vs. Sampling

Inspired by the relative success of the sampled hRVO thing, I though I'd dust off my old ClearPath proto and try out how it would compare with the sampling based method.

I have to admit that the recent ORCA explanation video also sparked some gas too. I think I got the ORCA thing finally after seeing it in that video.

Without further due here's the video.



Implementation

There are a couple of tricks I added on top of ClearPath. I use similar side bias as HRVO uses, that is based on the velocities and location of the objects, one side of the VO is expanded. It helps the agent to choose one side and reduces the side selection flickering.

Another trick I added is that I clamp the VO cone using a spike instead of a butt end like they do in the ClearPath paper. This makes the avoidance much smoother as can be seen in the head-to-head examples. It adds much needed prediction Clodéric mentioned in the comments of my last post.

I used different time horizon for static and moving obstacles, this allows the agents to move close to the walls while avoiding each other. This is quite important to get good behavior in crowded locations.

The sudden movements are caused by thin sliver section being opened and closed based on neighbour movement.

Geometric vs. Sampled

In many cases the geometric methods are much smoother than any sampling method. I think its biggest drawback is that the result is binary. You're either in or out. But that is also its strength too making the results accurate. The binary results also mean, that it is possible to get into situations where there is no admissible velocity at all.

Another con of the geometric method is the velocity selection. A common way is to just move the velocity to the nearest location at the border of the velocity obstacle. On crowded cases this results dead-locks as can be seen in the video too. I'm pretty sure that if the floating point results would be super accurate, the dead-locks would never resolve.

You can see similar clogging, which is present in my video, in the ClearPath video too (at the time they turn the speed to 10x).


The sampled VO looks smoother too, especially around the tip of the cone. In practice this means that you are less likely to run into situations where there is no admissible velocities. You will get high penalty for velocities which will collide with another agent, but sampling allows you to take the risk.

Sampling also allows to combine multiple different weights when calculating the best velocity. This allows a bit more interesting methods to smooth out velocity selection.

I'd love to see an academic paper which compares the pros and cons between these two methods and educated conclusion. Too bad most papers present their new method as the best thing since sliced bread and fail to address the cons properly.

Conclusion

The sampling method looks really good and smooth when I have 129x129 samples (like in the example picture above), but that amount of samples is totally impractical. I think sample counts around 200 start to become acceptable, I'd love to have less. I will try to see if I can cook up some wacky stable adaptive version to reduce the sample count.

I think the geometric method could be improved quite a bit if I could figure out better method to clamp the velocity to the boundary of the VO. Nearest point is evidently not good enough.

I do like both methods. I will continue trying to fix the cons of both as time permits. And I have a funny feeling that one of these methods might be good enough for a triple A quality agent movement. Well, that would still lack the animation bit, but that is another story.

Sunday, March 21, 2010

Custom hRVO



I have tried to pick up my ever growing queue of interesting local avoidance / velocity planning methods. There are certain things I liked about my TOI-sampling scheme, but the results were not quite what I would like it to be.

One of the things that initially got me into creating the TOI-sampling scheme was an assumption that it is good idea to move at maximum velocity most of the time. In practice this seems to be a faulty assumption. It creates a rushing behavior, much a like a headless chicken running around. Especially in crowded situations.

So one thing I have have been pondering is that what might happen if I just removed that assumption and used huge amount of samples instead to test different speeds too. Much like what RVOlib does.

You can see the results in the above video. I think it is much improved now. I used the sample scoring scheme as my previous TOI sampling used. The good thing about it is that it handles all kinds of nasty things really well.

One problem that this custom hRVO suffers is aliasing. The H is in lower case as the method does not quite use the hybrid-RVO method, but does has similar side bias as HRVO does. As clearly visible from the take over situation with 4 agents, the agents favor to pass each other from right. This reduces velocity selection flickering a lot in head-to-head and overtaking situations.

Another trick I added was to favor velocities close to the current velocity. In my previous attempts this has always resulted the agents to favor the wrong solutions too much, resulting cases where the agents hug each other each other, skip towards the sundown and live happily ever after.

In this experiment I also used the pathfinder from the previous blog post to avoid static obstacles.

Anyways, I think this was a successful experiment, even if not completely practical because of the huge number of samples per agent. Inspired by the Geometric Methods of Multi-agent Collision Avoidance video, I think I'm going to try the ORCA method the next to see if I can get similar quality with cheaper calculations.

Friday, March 19, 2010

Local Navigation Grids

I have tested several different methods for local obstacle avoidance over the past months. A little less recently, as I have been finishing a game, though. There is something that I really like about the Uncharted way of mixing and matching navmeshes for global search, and dynamic grid for more local path queries.

There is one potentially nasty thing about that combination and that is what to do when the local grid says that the path is blocked, but the global navmesh disagrees. I'm going to sidestep that question by making an assumption that all the stuff that is not in the global navmesh can be traversed some way. Let it be moving around, kicking or putting it on fire.

Implementation

Even if the method has some problems, I thought it was worth the try. I limited my implementation to a small grid which follows the agent. The idea behind this is that the grid only tries to solve the pathfinding problem between two global navigation nodes. In case of navmeshes this area would be the area of current navigation polygon, if you use waypoints, it could be the area between the waypoints.

Simplifying the Grid

Grids are really simple on what it comes to creating obstacles. The horrible side effect of grids is that they create huge graphs and that shows in performance. Since we are using small grid, something between 20x20 to 64x64 probably suffices, this is not a huge problem, but 64x64 is still 4096 nodes to be searched with A*.


There is one simple trick we can do to reduce the node count drastically. After the grid has been build, we simplify our search representation by storing the grid as RLE spans (oh yeah, I'm big fan of RLE!). In practice this reduces the node count from N^2 to 2N. In our node grid range (N=20..64), that means at about an order of magnitude less nodes!

(I do remember reading some GDC slides which described the same trick used by some RTS, but I could not find the reference.)

The side effect is that the cost calculations become nasty and messy. But let's not care about that yet. Instead, let's dumb our search down even further by making more assumptions.

Simplifying the Search

If we were not using the local grid, the path through that area would be a straight line. Instead of building a full fledged A* pathfinder for the local grid we can use this information to create something that will do a good job if the straight line exists, and in any other case it will just get us out of the way of the obstacles and local minima.


I chose to use breath first search for this. Because of the search space representation, it is quite efficient. The open list never gets really big, in practice open list size is usually around 4, and hardly ever peeks past 8 items.


In order to get favor that straight path, the neighbour nodes which are about to be added to the open list are sorted so that the node that is closest to the straight line from start to end point is added first. This bias makes sure that the nodes close to the center line are visited first. The open list is never sorted, just the new nodes that are added to it. It's not pretty, but it works really well in practice.


Finding the Final Path

During the search an index to the parent node is stored and pathfind basically consists of finding the node where the end location lies and tracing back the nodes until we reach the start location. When finding the end node, I choose the closest one that was visited during the breath first search. This makes sure that I get path to follow towards the target, even if the way is temporarily blocked.


Finally, the Funnel Algorithm is used to find straight path through the regions. Funnel Algorithm just needs a series of segments which define left and right edge of constraints to move along the funnel. In our case the portals are the shared edge between two regions.

In my prototype the slowest part was updating the grid, which was stored 1 bit per cell. Updating the grid takes in average 0.026 ms, this includes about 6 segments and 6 agents. I'm sure you can squeeze that number down by vectorizing the rasterization phase. Path query, including string pulling, takes about 0.012 ms in average. All results on 2.8GHz Core Duo. One path query uses around than 1.5kB of memory to store the required search space representation and the final path.

[EDIT] Updated time measurements above, the originals were measured in debug build.


Conclusion

It was interesting to try to the local grid method. I think it has great potential, but the potential problems of syncing the failures from local grid to the global structure are a nasty side effect. I think it might be possible to create an "interface of assumptions", for example the one I explained on the opening sentence, to improve it.

Monday, March 8, 2010

Simple Stupid Funnel Algorithm


[EDIT] Fixed that example scenario below.

There's a nice master class over at AIGameDev.com about pathfinding: Hierarchical Pathfinding Tips & Tricks with Alexander Kring. That slide about Left 4 Dead path smoothing hit my pet peeve. It makes me sad that people still use "let's trace the polygon edge midpoints" as the reference algorithm for path smoothing. Really sad.

Funnel algorithm is simple algorithm to find straight path along portals. Of the most detailed descriptions can be found in Efficient Triangulation-Based Pathfinding.

Here's implementation of simple stupid funnel algorithm. Instead of using queue and all that fancy stuff, simple stupid funnel algorithm runs a loop and restarts the loop from earlier location when new corner is added. This means that some portals are calculated a bit more often than potentially necessary, but it makes the implementation a whole lot simpler.



The above image shows six steps of the algorithm. Every time we process a new portal edge (the dashed lines highlighted in yellow), we first:
  • Check if the left and right points are inside the current funnel (described by the blue and red lines), if they are, we simple narrow the funnel (A-D).
  • If the new left endpoint is outside the funnel, the funnel is not update (E-F)
  • If the new left end point is over right funnel edge (F), we add the right funnel as a corner in the path and place the apex of the funnel at the right funnel point location and restart the algorithm from there (G).
The same logic goes for left edge too. This is repeated until all the portal edges are processed.

As seen in the above example, the algorithm recalculates some edge several times because of the restart, but since the calculations are so simple, this simple stupid trick makes the implementation much simpler and in practice is faster too.

inline float triarea2(const float* a, const float* b, const float* c)
{
const float ax = b[0] - a[0];
const float ay = b[1] - a[1];
const float bx = c[0] - a[0];
const float by = c[1] - a[1];
return bx*ay - ax*by;
}

inline bool vequal(const float* a, const float* b)
{
static const float eq = 0.001f*0.001f;
return vdistsqr(a, b) < eq;
}

int stringPull(const float* portals, int nportals,
float* pts, const int maxPts)
{
// Find straight path.
int npts = 0;
// Init scan state
float portalApex[2], portalLeft[2], portalRight[2];
int apexIndex = 0, leftIndex = 0, rightIndex = 0;
vcpy(portalApex, &portals[0]);
vcpy(portalLeft, &portals[0]);
vcpy(portalRight, &portals[2]);

// Add start point.
vcpy(&pts[npts*2], portalApex);
npts++;

for (int i = 1; i < nportals && npts < maxPts; ++i)
{
const float* left = &portals[i*4+0];
const float* right = &portals[i*4+2];

// Update right vertex.
if (triarea2(portalApex, portalRight, right) <= 0.0f)
{
if (vequal(portalApex, portalRight) || triarea2(portalApex, portalLeft, right) > 0.0f)
{
// Tighten the funnel.
vcpy(portalRight, right);
rightIndex = i;
}
else
{
// Right over left, insert left to path and restart scan from portal left point.
vcpy(&pts[npts*2], portalLeft);
npts++;
// Make current left the new apex.
vcpy(portalApex, portalLeft);
apexIndex = leftIndex;
// Reset portal
vcpy(portalLeft, portalApex);
vcpy(portalRight, portalApex);
leftIndex = apexIndex;
rightIndex = apexIndex;
// Restart scan
i = apexIndex;
continue;
}
}

// Update left vertex.
if (triarea2(portalApex, portalLeft, left) >= 0.0f)
{
if (vequal(portalApex, portalLeft) || triarea2(portalApex, portalRight, left) < 0.0f)
{
// Tighten the funnel.
vcpy(portalLeft, left);
leftIndex = i;
}
else
{
// Left over right, insert right to path and restart scan from portal right point.
vcpy(&pts[npts*2], portalRight);
npts++;
// Make current right the new apex.
vcpy(portalApex, portalRight);
apexIndex = rightIndex;
// Reset portal
vcpy(portalLeft, portalApex);
vcpy(portalRight, portalApex);
leftIndex = apexIndex;
rightIndex = apexIndex;
// Restart scan
i = apexIndex;
continue;
}
}
}
// Append last point to path.
if (npts < maxPts)
{
vcpy(&pts[npts*2], &portals[(nportals-1)*4+0]);
npts++;
}

return npts;
}

The array portals has all the portal segments of the path to simplify, first left edge point and the right edge point. The first portal's left and right location are set to start location, and the last portals left and right location is set to end location of the path. Something like this:

// Start portal
vcpy(&portals[nportals*4+0], startPos);
vcpy(&portals[nportals*4+2],
startPos);
nportals++;
// Portal between navmesh polygons
for (int i = 0; i < path->npolys-1; ++i)
{
getPortalPoints(mesh, path->poly[i], path->poly[i+1], &portals[nportals*4+0], &portals[nportals*4+2]);
nportals++;
}
// End portal
vcpy(&portals[nportals*4+0], endPos);
vcpy(&portals[nportals*4+2],
endPos);
nportals++;

The cool thing is that this algorithm can be used with pretty much any navigation format. Let it be a grid, quad-tree, connected squares, way-points or navigation mesh. As long as you pass it a list of line segments that describe the portal from one node to another.

This algorithm is also awesome when combined with steering. You can calculate the desired movement velocity by calculating the next few turns and the steer towards the next corner. It is so fast that you can calculate this every iteration just before you use your favorite steering code.

So there you have it. The next person who goes public and suggest to use edge midpoints and raycasting to find more straight path after A* will get his inbox flooded with Cute Overload weekly selection to instigate his pet hate too.

Saturday, March 6, 2010

Blind Sighted


So how do you go about creating a game for a device you have never seen, and all you know about it is an emulator and marketing pitch? The best you can do is to try to minimize the risks.

For Zen Bound we knew from the past that the touch screen transformed the inputs much more tactile. It almost feels like you're holding the object. So in order to guess how the bigger screen of iPad might change the game, I created a 1:1 model of the device to see how it affects it.

The thing we noticed was that at that size you don't use your finger anymore, but the whole hand. Also it helped us to decide the size of the object on screen and to estimate how we might need to change the rotation speed, etc. We will see how these things work out in practice.

So the bottom line is that if you have something unknown, you can transform it to an educated guess by probing the idea with a prototype. It is wonderful how you brain reorganizes stuff when you have some point of view to it. Let it be cartboard box and masking tape.

Friday, March 5, 2010

Save Games and All That

I have long postponed a task to improve Detour serialization. My use of the word may be a bit wonky, but I mean the business storing and restoring the game state. In case of Detour this also affects how you would initialize the navmesh too.

In pretty much all game projects I have participated in save games have been pretty much retrofitted into the game. It usually results a lot of stupid zombie coding and super long debugging sessions.

When I started thinking about Detour, I have tried to make decision which eventually will make the serialization implementation a bit simpler. That goes into how data is kept internally and what kind of data the API returns. For example there is no pointers, but handles instead.


Handles

Handles are simple abstraction which allows to keep track references to your data. The difference to a pointer is that handles can be invalidated, and you don't need to worry about someone having a reference to your data. The next time the data is accessed, the access will just fail, in which case the user should also invalidate the handle.

Usually in pointer based systems you use some sort of callback system, which tells the pointer owner that something has changed and you should remove the reference. Or it can result things like smart pointers or reference counting.

As the navigation data is solely owned by the navmesh, ref counting and smart pointers would not be a good choice. I also wanted the system to load the navmesh data as one contiguous chunk, which makes stuff like the usual ref counting not really a good choice.

Another good thing about the handles are that they can be stored in the disk as simple integers. These two facts: 1) simple handling of invalid references and 2) simple storing of returned data, make handles good choice when you need to pass handles to internal data through your API.


Detour Handles

Each detour handle contains three values: salt, tile ID, and polygon ID. Tile ID is simply an index to internal Detour tile array, polygon ID is index to a polygon within that time and salt is special ingredient which tells which version of tile we are using. The tile ref is constructed so that 0 (zero) value an be used as null handle.

Detour has fixed pool of tiles it reuses. Removed tiles are returned back to the pool and new tiles are allocated from the pool. Each of those tiles are identified by and index to the tile.

Every time a tile is removed the salt of that tile is incremented. This operation makes sure that if a tile changes, all handles which are pointing to the old data can be detected.

This also implies that if we save a dtPolyRef (the handle Detour uses) to disk when a save game is stored, we need to also restore the state of the Detour mesh when we restore a save game so that the handles are valid after save game is restored.


Saving Game State

The least information that needs to be stored on disk is the tile index and salt of each tile that we have in the current state of the navmesh. This allows the handles to survive the serialization. Additionally we may want to store the per polygon flags and areas too, as the API allows to change that too.

That is still piece of cake. But this is where things can get a bit complicated.

Pretty much every single game I've seen out there uses different way to load assets and even more so how they store and restore save games.

When save game is restored, some games load and initialize a full "section" of the game and then load a delta state on top of that. Some may first store the structure of the level and then load the assets that are needed.

While they both may sound like almost the same, the difference in load performance can be huge. The first, full section loading, allows us to place all the assets in such order that they are fast to load from disk, while the second method may be simpler if the world is allowed to change a lot but may and will result more fragmented loading, in which case seeking may kill your loading performance.

Streaming changes the game a bit too. I have never worked on a game which would have excessively used streaming. So I'm reaching out to you to have a bit better understanding of save game with streaming.

How do you handle asset loading and how do you restore the game state from a save-game?


Current Sketch

My current idea of how the API for serializing Detour navmesh looks something like this.

dtNavMeshSerializer nser;
nser.storeDelta(navmesh);
fwrite(nser.getData(), nser.getDataSize(), fp);

The serializer will create a contiguous clump of data which can be directly stored into disk. The process to restore the state is as follows:

dtNavMeshSerializer ser;
if (!ser.init(data,dataSize))
return false;
for (int i = 0; i < ser.getNavMeshResourceCount(); ++i)
{
const dtTileRes& tres = ser.getNavMeshResource(i);
navmesh->restoreTileState(tres.tileId, tres.stateData, tres.stateDataSize);
}

This assumes that the structure of the navmesh has not changed in between. If the structure may change, you will need to load the tile data before restoring.

dtNavMeshSerializer ser;
if (!ser.init(data,dataSize))
return false;

dtNavMesh* navmesh = new dtNavMesh;

if (!navmesh->init(ser.getInitParams())
return false;

for (int i = 0; i < ser.getNavMeshResourceCount(); ++i)
{
const dtTileRes& tres = ser.getNavMeshResource(i);
int dataSize = 0;
unsigned char* data = 0;
// Load data from disk.
if (!m_assetMgr.getNavmeshTileData(tres.resourceId, &data, &dataSize))
return false;
navmesh->addTile(data, dataSize, false, tres.tileId, tres.tileSalt);
// Restore state
navmesh->restoreTileState(tres.tileId, tres.stateData, tres.stateDataSize);
}

Note how the addTile looks different than currently. The tiles don't actually make any sense in random order, so in practice there is no need to pass the tile x and y coordinates when tile is added. This data can be stored in the tile header and acquired from there. Also not that tile ID and tile salt are also restored when tile is loaded to make sure the handles remain valid. That m_assetMgr is your custom asset manager, which will actually handle loading the navmesh data. This example also assumes that the asset manager handles allocating and releasing the data.

In case you use Recast to dynamically create the tiles you can use serializer to store the whole navmesh data too.

dtNavMeshSerializer nser;
nser.storeAll(navmesh);
fwrite(nser.getData(), nser.getDataSize(), fp);

Restoring the state would look something like this:

dtNavMeshSerializer ser;
if (!ser.init(data,dataSize))
return false;

dtNavMesh* navmesh = new dtNavMesh;

if (!navmesh->init(ser.getInitParams())
return false;

for (int i = 0; i < ser.getNavMeshResourceCount(); ++i)
{
const dtTileRes& tres = nser.getNavMeshResource(i);
navmesh->addTile(tres.tileData, tres.tileDataSize, true, tres.tileId, tres.tileSalt);
}

This code also restores the tile ID and tile Salt so that handles remain valid, but it does not store state, since the tile data already contains the state data too.


Conclusion

My ideas towards implementing the serialization are getting together. I'm requesting comments. Each game has unique requirements for storing save games and loading assets. There is no way I can please all, but I can try to make it little less painful for as many of you as possible.

Please, let me know if I overlooked some scenario with my sketch. And also please share how do you handle asset loading and how do you restore the game state from a save-game? If you don't want to share it here in my blog, feel free to mail it to me too!

Monday, March 1, 2010

Power of Less

I'm reading the book called The Power of Less. It is one of those books on how to get things done. In the first chapter the there is a list of six principles of productivity. They are:
  1. Set limitations
  2. Choose the essential
  3. Simplify
  4. Focus
  5. Create habits
  6. Start small
How does that apply to game project? I must admit that every successful project I have worked so far have pretty much worked the way noted above. Most of them through accident, though. Note for programmers, focus-on-everything a.k.a. "make it generic" is not included in the list for a good reason.

Sketch for Hierarchical Pathfinding Using Detour



Several people have asked me how to implement hierarchical pathfinding using Detour, usually because they have so much pathfinding data that it is not feasible to keep it all in memory. This is common scenario in MMO game for example.

If I were to build an MMO pathfinding from ground up, I would make sure the world structure would have easy to use abstraction already build it. That is, if I were to travel long distances, then it makes sense to find path via certain land marks first and then in final stage find the actual path.

If you need to retrofit pathfinding to existing game, the following method might work for you.


Tiles as Path Abstraction
Detour allows you to break down the world into tiles and lot in only the data that you need. This data structure can be exploited to create hierarchical path finder.

The idea is that you first find which tiles needs to be travelled in order to get to the destination and then you find path within one tile at a time until you reach the destination. We need connectivity graph between the tiles to do the high level search.


Building High Level Graph

Take a look at a the highlighted tile in above picture. There are two separate contiguous areas A and B in that tile. A is at the street level and B is partially underground. The areas are not connected, so depending how you enter the tile, each tile may have different kind of connectivity to neighbour tiles.

The first step in building the higher level graph is to identify these contiguous areas of the navmesh. The simplest way to do this is to first find all the portal edges of the tile and flood fill along the polygons and visit all the portal edges of the mesh. Finally you can use this data to identify contiguous areas and which portals belong to them.

In order to build navigation graph from this data we need to deduct A* nodes from the data. There are several ways to do this, I'll explain two of them: 1) Nodes at portals, 2) Nodes at area centers. These two methods allow to trade off quality of the path and speed of the search.


Nodes at Portal Edges



As the name implies this method places an A* node at each portal edge center. After that the area information is used to connect the nodes within single area to each other and finally, using all the tile data, nodes at overlapping (connected) edges are at the merged.

This method allows higher quality paths if you use actual path distance between the nodes instead of using euclidean distance between the nodes. The con of this method is that it can potentially create a lot of nodes and links.


Nodes at Area Centers



This method places the A* nodes at the center locations of the contiguous areas. The connections between the nodes are calculated using the all the tile data just like the nodes were merged in the previous method.

Multiple links between area can be removed, and in general this method creates a lot less links than the portal center method. The trade off is that the high level path quality is likely to be worse than with the edge method.


Area Flags



If you want to use flags which enable and disable agent movement on the mesh, then you need to take this into account when building the high level graph. You should partition the mesh so that each area with different flags ends up having own node or link. In this case the nodes at area centers can be easier to implement.


Finding the Path

There are several ways to use this information to find path once you have found the high level path.

Firstly you could just load the tiles that are necessary to find path from the start location to the goal location. This is not the most effective way to do it, though. Ideally there should be a way to identity which tiles to visit during pathfinding. But if your main concern is memory, this method allows you to load the correct tiles and focus pathfinding.

Another way to use the information is to just find path within one tile. That is, always find path to the exit portal of the current tile and path find again from there. The tricky part is how to choose a good point at the exit portal. One way, perhaps a bit naively, would be to choose the nearest point on the edge and move there.



A bit more advanced method could be to use the the tile portals with the string pulling method Detour uses and find "straight" path along the tiles first and then use the intersection point between portal edge and the high level straight path as target to exit the current tile. Rinse and repeat until the goal location has been found.

Alternatively you could also use a "workspace" which is something like the next 4 tiles to get a bit more quality off the second method without trading off too much memory.


The key to optimize pathfinder, and applies here too, is to make a little work as possible. This is even more true when your world is dynamic, as a lot of work can potentially be thrown away when something changes.