Heightfield Layer Portals

I worked today a bit on the layers again. I was trying to find the minimal data that needs to be stored. There were a couple of cases which required a bit more thinking.

For example should the layer contain that extra border or not? I decided that it should not. That required me to store the edges which may lead to a connected layer and it also means that the obstacle will need to be expanded by the agent radius, but that is something I was planning to do anyways.

It turned out to be a good choice to dig up the portals anyways. Now it is possible to calculate a hierarchical graph based on the portals only. The way the layer partitioning is done makes sure that the connections between two layers are always axis aligned. This makes things a lot easier and robust. As difference to the connections between navmesh tiles, with layers there can be a portal in the middle of a tile too. I will need to add support for this in Detour later.

I think I'll add a bit more info for the portals, for example which portals are connected to each other within a single layer.

Heightfield Layers Progress

I have been working on the heightfield layers a bit more. As I've explained earlier, I'm trying to make the temporary obstacle processing much faster by decomposing the walkable area into 2D layers.

Then the temp obstacles will be rasterized onto those 2D areas and build into pieces of navmesh. The idea is to try to limit the changes of a temporary obstacle processing to as local area as possible and to speed up the generation process in general by making the input data simpler.

Each layer stores area type and 2D heighfield. The area types should compress really well with RLE, and it should be possible to compress the heighfield using a simple linear spline fitting. Add LZ compression on top of that and the aux data for generating new tiles should not be a huge burden anymore.

Interestingly, this layered heighfield data is also something that can be used to make 2.5D HPA* (the papers so far have used 2D data). If someone out there is up for the challenge, let me know and I'll help you to decipher the data Recast creates.

Iterating Cube Vertices, Edges and Faces

This keeps haunting me. There must be an awesome way to arrange the data so that you can do a simple for loop and iterate over all cube vertices, edges and faces. I'm sort of after something you could use in matching cube like algorithms to fetch data from a sample grid without having to use lookup tables.

Vertices or sample offsets are easy:

    for (int i = 0; i < 8; ++i)
    {
        const int dx = i & 1;
        const int dy = (i>>1) & 1;
        const int dz = (i>>2) & 1;
        printf("%d: %d,%d,%d\n", i, dx,dy,dz);
    }        

Assuming that you have 3 values per sample, one along each axis, the following code can be used to walk through all the valid edges:

    for (int i = 0; i < 12; ++i)
    {
        const int ax = (i >> 2) & 3;
        const int as = (4-ax) >> 2;
        const int bs = (5-ax) >> 2;
        const int v = ((i&1) << as) | ((i&2) << bs);
        printf("va=%d vb=%d  dir=%c\n", v, v|(1<<ax), "XYZ"[ax]);
    }

But... I'm not satisfied, there must be a cleaner way.

I once figured out how to procedurally draw a cube with just one for loop, but I cannot remember how to do it anymore, IIRC it used rotating sequence of XYZ, ZXY, YZX somehow, much like how you calculate cross products.

Very Temporary Obstacle Avoidance pt. 2

I exposed my previous attempt at local obstacle avoidance to some more challenging situations and oh boy did it explode! For example the above shows really complicated case, which looks really innocent. There are a couple of problematic cases.

Firstly, the obstacles that reach to the sides are problematic to handle. The sides needs to classified regarding the goal direction (blue) but they can reach back to over 180 degrees in certain cases. I had to make a lot of special case code to make sure to detect when right is still right even if it is on left side. Yeah!

The second problem case is how to handle the terminator nodes (those red dots, which indicate that an obstacle touches a wall). Initially I thought just to use the line to goal to split detect if a terminator is left or right. It worked well for many of my tests, but there are cases like in the above video, where the terminator changes sides!

So anyhow, hours of hacks and tricks later, I thought I'd give up a little.

Few days later, I thought why not try the old local grid pathfinder I made some time ago. I took a well tested rasterizer, changed it to support convex polygon and in no time I had working prototype of local obstacle avoidance in DetourCrowd.

The code is pretty simple to understand, it should be pretty fast too. I did not test the impact yet, but my previous tests indicate that it is fast.

The local pathfinder operates on the yellow area you can see in the video. If the blocking obstacle is larger than that, path cannot be found. The navmesh and the obstacles are updated every now and then, I could potentially use lower update rate too.

There a couple of problems still left to be solved. Firstly, the currently is no reliable way to detect that the agent is stuck. Secondly, in some cases the local pathfinder finds a bit different route, which leads to flicker.

_

We'll see how this all works out. I hope to speed up the navmesh temp obstacle baking a little. It is still the best choice. I think the local grid path planner could be usable for simpler games or those who cannot spend the extra memory required by the tile cache.

Very Temporary Obstacle Avoidance

In the rush of trying to make everything perfect, it is sometimes hard to remember that a simpler solution could work too. This ties to my efforts to handle temporary obstacles.

If you want a rock solid way of handling temporary obstacles, there is no other way than to bake them into your navigation graph. There is just no way around it.

But at the same time there are huge number of cases, where you just would like to sprinkle few crates and barrels here and there for the player to shoot at, and will just break your navigation.

Purely local obstacle avoidance cannot handle them (or you are really lucky, if it does!). Local avoidance gets stuck in local minima (i.e. U-shaped cluster of obstacles), or platos (i.e. row of obstacles).

There is range of algorithms that fit somewhere in between local avoidance and global path planning. Which will solve the case of some temporary obstacles here and there, but will break of the obstacles for too complicated shapes.

Avoiding Temporary Obstacles Locally

One potential solution is to use small grid around the NPC to find around the obstacles. I have experimented with this earlier and it works really well. Another solution is to cluster the obstacles to for larger obstacles and use their silhouettes to find path around them.

That silhouette based obstacle avoidance is also discussed in an article in Game Programming Gems 3 called "A Fast Approach to Navigation Meshes" by Stephen White and Christopher Christensen. It is one of my all time favorite articles. I must have read it billion times.

I have tried to improve the algorithm few times in the past, but never quite got it right. I was working on a recent request last week and the idea popped up again, and I thought I'd give it a another go.

Basic Method

The basic process works so that you have a certain segment goal in the world where you would like to move to. First you check that if there is something blocking the way. In practice it means finding intersection between the segment from agents current location to the next sub-goal (i.e. next corner on the path) and all the temporary obstacles near by.

If something is blocking the way, we find tangent of the obstacle, and choose one side to steer around the obstacle. The side is selected based on which detour is shorter. The distance is approximated by a path from the start point, via the tangent point, to the goal location.

The first tricky problem with the method is how to handle multiple obstacles. Naively just visitin all the obstacles and finding a furthest tangents, will lead poor behavior when there is passages through the obstacles.

Obstacle Clusters

One solution to this is to first cluster all the overlapping obstacles. Then when you hit one obstacle in a cluster, you simply find the furthest tangents of all the obstacles in the cluster.

Sometimes this leads to a case where the newly chosen path will be still blocked. The solution is to check if there is some obstacles blocking the path to the new target, and iterate until the path is collision free.

Iterative algorithms are always tricky in realtime games and simulations. The goo things about this method is that just one iteration will give you a collision free solution. If the new path will lead to collision with another obstacle, that collision will eventually be the first hit and it will be corrected. The result is ugly, but it'll work. In practice this means that you can limit the iterations to 2-4 and it will handle most of the cases with gracefully!

Dealing with Obstacles Touching Walls

The next problem to solve is how to handle cases where one side of the obstacle touches navigation mesh boundary wall.

The solution I have used is to add special obstacles at the navmesh boundary, I call terminator nodes. When a terminator node falls on either side of the silhouette that side is marked as blocked and that is prohibited to be selected. If there is terminator node on both sides, it means that the path is blocked. This is really important feature of this method. It is not perfect, but it signals when it does not know that answer!

It Will Break

You should be also aware that using this method will eventually lead to situations where the path is blocked and the pathfinder cannot help you since it does not know about the blocker. You have to deal with it.

Your imagination is the limit how to handle such cases. You could for example just teleport the NPC to the other side of the obstacle, or the NPC could jump or climb over the obstacle using animation, the NPC could try to kick the blocking obstacle, shoot it, or you could detect that newly added obstacle creates a blocking wall and just break obstacles in the cluster until it is safe again.

That is, you need to have some kind of game mechanic to either break obstacles or skip them. One thing you should not do is to just disable the obstacle, since it can and will lead the agent to be inside the obstacle for long time.

Closing Words

There are quite a few more tricky details in the process I did not cover. I hope to polish those ideas a bit more and explain them at later stage. I think the method should be applicable to convex polygon obstacles too, which would make it even more usable. I have to try that out.

I think this method could be interesting choice for those who wish to add few obstacles here and there and whose game design can allow some game logic to pass through the obstacles when they block the NPCs path.

Implementing Undo the Simple Way

Over the years I have implemented all kinds of undos for the editors and tools I have made. I have tried all kinds of ways, ranging from storing delta information to abstract command class that can undo redo itself. There is one kind, though, that is by far my favorite:

class Document ()
{
   static int MAX_UNDO = 10;
   struct UndoState
   {
       String cmd;
       String path;
   };
   UndoState m_undoStack[MAX_UNDO];

   int m_undoHead = 0;    // Current state.
   int m_undoTip = 0;    // The highest state that is set.
}

// Adds undo state to the undo stack.
Document:: addUndoState(String cmd, String path)
{
   // This kills all the states after the current one
   m_undoTip = m_undoHead+1;
   // Buffer getting full, shift down.
   if (m_undoTip >= MAX_UNDO) {
       for (int i = 0; i < MAX_UNDO-1; ++i)
           m_undoStack[i] = m_undoStack[i+1];
       m_undoTip--;
   }
   // Store state
   m_undoHead = m_undoTip;
   m_undoStack[m_undoTip].cmd = cmd;
   m_undoStack[m_undoTip].path = path;
}

// Takes snapshot of the document.
Document::snapshot(String cmd)
{
   String path = getTempFileName();
   ZipWriter zip;
   saveState(&zip);
   zip.save(path);
   addUndoState(cmd, path);
}

// Returns true if can undo.
Document::canUndo()
{
   return m_undoHead > 0;
}

// Returns true if can redo.
Document::canRedo()
{
   return m_undoHead < m_undoTip;
}

// Reverts to previous state of the document.
Document::undo()
{
   if (!canUndo()) return;
   m_undoHead--;

   ZipReader zip;
   zip.load(m_undoStack[m_undoHead].path);
   loadState(&zip);
}

// Advances to next state of the document.
Document::redo()
{
   if (!canRedo()) return;
   m_undoHead++;

   ZipReader zip;
   zip.load(m_undoStack[m_undoHead].path);
   loadState(&zip);
}

// Saves document state.
Document::saveState(Writer* out)
{
   // Save document state
   ...
}

// Loads document state.
Document::loadState(Reader* in)
{
   // Load document state
   ...
}