Platformer Dynamic Navigation 4/n

Simulating paths inside the triangulated space

In the previous post, I finally had a fast enough constrained triangulation I can use to generate a navmesh every frame. But all I could do was basic navigation with no constraints on the navigation type. A platformer may have a lot of different constraints but the most common one being gravity. So let’s try to handle that first.

Incorporating Gravity in the mix

The path we have vs The path we want

The first thing I did is to define a new building block, which I call surfaces, which are continuous edges the agent can walk on. The definition of walk on is an edge which will satisfy a specific function, which will take a new parameter gravity.

internal bool isARestSurface(TriangulationResult& triangles, u32 adj, Vector2 a, Vector2 b, Vector2 unitGravity)
{
    bool result = false;
    if(adj != 0 && isRemovedTriangle(triangles, (adj >> 2) - 1))
    {
        r32 d1   = dotProduct( a, unitGravity);
        r32 d2   = dotProduct( b, unitGravity);
        Vector2 per = unit(perp(a - b));
        result = (absolute(d1 - d2) > 0.001f 
              || (dotProduct(per, unitGravity) >= 0)) == false;
    }

    return result;
}

For now we assume the gravity to be the same in all the level, but this will need to change, as we may have different zones with diffferent gravities. But let’s keep it simple for now.

Once we have this, we iterate over all the triangles, and when we find an edge that satisfies the restSurface criteria, we iterate the points to find adjacent edges that also validate the criteria. I wrote a little helper for doing just this

for(SurfaceIterator it = iterateSurface(triangles, points, pointIndex, gravity); isValid(it); it = nextSurface(it))
{         
    u32 edgeDefinition = getEdgeDefinition(it);
    u32 ti             = getTriangleIndex(it);
    u32 pi             = getPointIndex(it);

    // @Note do stuff with the surface
}

With this taken care of, we can start the main process. When we have a point to start we find the triangle it belongs to, and restrain the triangulation to only triangles it can reach (as forced constraints could have created islands).

In the video we can see the area which is reachable from the mouse position (in red). This has the benefit of reducing our search space for further operations. Once we have this smaller triangulation, we can iterate over walkable surfaces to create an array of Platforms in this space. A platform is just an array of edges in the triangulation, and a simple bounding box approximation (which is subject to change, as this does not handle rotation well).

struct Platform
{
    u32 edges[64];
    u32 edgeCount;

    r32 xMin;
    r32 xMax;
    r32 yMin;
    r32 yMax;
};

Here what it looks like with different gravities. Now that we have the definitions of platforms, what we need is path between those, which is the actual complicated part.

Movement equation

What we need is at least an acceleration and a position on a platform that leads to another platform. For this I will use the same as in my game, meaning a position/velocity/acceleration combo.

Vector3 playerDelta = (0.5f * ddp * dtRatioSqr) + // Acceleration  m/s²
                      (velocity * dt);            // Velocity      m/s
velocity            += ddp * dt; 

So for now we will assume a starting position, an initial acceleration and a zero velocity. We just update the start position depending on the acceleration and velocity. As we are in the triangulation, I can just update my position and only check against the three edges of the triangulation I’m in.

Finding the point where the path exits the triangle

We can easily know if the next point of the path will be outside of the triangle. Each edge is defined to be clockwise, so if we take the distance to the edge the three will be the same sign. If we cross an edge then the sign will change.

bool take0     = lineSide(points[t0->b], points[t0->a], next) > 0.f;
bool take1     = lineSide(points[t0->c], points[t0->b], next) > 0.f;
bool take2     = lineSide(points[t0->a], points[t0->c], next) > 0.f;
u32 pointIndex = take0 ? 0 : (take1 ? 1 : (take2 ? 2 : 4));

Here is the whole code to determine if we cross an edge. Once I know that the next point is outside, I can do an intersection check to have the exact crossing point. After that, either the next triangle we’re in is in the triangulation and we continue the same way, or it is removed from the triangulation. If it is removed and the triangle belongs to a surface we stop else we calculate a reflection vector and update the velocity accordingly.

This methods has a drawback though. If the length of one delta is big enough, you can be on the other side of 2 edges and choose the wrong edge to cross. Let’ illustrate that with an example:

caption...

Here, we cross e and f, but the final point is closer to e, so the algorithm will choose this side which is wrong. To mitigate this, I chose another approach, like this :

r32 dsts[4] =
{
    intersectsT(start, next, points[t0->a], points[t0->b]),
    intersectsT(start, next, points[t0->b], points[t0->c]),
    intersectsT(start, next, points[t0->c], points[t0->a]),
    1.f,
};

dsts[0] = dsts[0] <= currentGoal ? U32Max : dsts[0];
dsts[1] = dsts[1] <= currentGoal ? U32Max : dsts[1];
dsts[2] = dsts[2] <= currentGoal ? U32Max : dsts[2];
u32 max0 = dsts[0] < dsts[1] ? 0 : 1;
u32 max1 = dsts[2] < dsts[3] ? 2 : 3;
u32 pointIndex = (dsts[max0] < dsts[max1]) ? max0 : max1;

We calculate the time before we intersect each side of the triangle. We remember how far we are on this line (the currentGoal), and we clean the result so that previous intersection is not chosen. If the chosen index is the third one (the 1.f in the array), it means that the next point is in the triangle. We then go update the velocity and calculate the next point :

start       = next;
velocity   += acceleration * dtStep;
next       +=  (0.5f * acceleration * dtSqr) + velocity * dtStep;
currentGoal = 0.f;

Else if this hits a forbidden edge, we stop, and it it is a removed triangle (aka a surface) we check to see if it’s a platform. If it is we stop, else we calculate a reflection vector to add to our velocity, update the velocity and next point accordingly, store the percent of the path we’re at.

One thing to be aware of when updating the percent of the line we’re in, is that calculating the intersection with [AB] and [BA] may have some very small delta due to the float precision. So when we update it, we use the intersection time we will test against, meaning [BA] because each triangle is in clockwise order, so if it is [AB] for this triangle, on the other side it will be [BA]. And not doing this can lead to errors if the delta between the two is bigger than your epsilon. The other way to solve it is have a bigegr epsilon, but then you cannot have very thin triangles, which is valuable when you add some constraints.

if (isRemovedTriangle(triangles, (a0->E[pointIndex] >> 2) - 1))
{
    Vector2 s   = points[t0->E[pointIndex]];
    Vector2 t   = points[t0->E[pointIndexTable[pointIndex][0]]];
    r32 interT  = dsts[pointIndex];
    result.endPoint = start + (interT - TRIANGULATION_FLOAT_EPSILON) * (next - start);

    Vector2 per  = unit(perp(s - t)); 
    keepAtIt     = (dotProduct(per, gravity) >= 0);
    velocity    -= 1.01f * dotProduct(velocity, per) * per;                        
                        
    start = result.endPoint;
    next  = result.endPoint + (1.f - interT) * dtStep * velocity;
    currentGoal = 0.f;
}
else
{
    r32 other = intersectsT(start, next, 
                            points[t0->E[pointIndexTable[pointIndex][0]],                                                                          points[t0->E[pointIndex]]);

    currentGoal = other + TRIABGULATION_FLOAT_EPSILON;

    u32 tIndex = (a0->E[pointIndex] >> 2) - 1;
    t0         = triangles.triangles + tIndex;
    a0         = triangles.adjacency + tIndex;
    f0         = triangles.flags     + tIndex;
}

With this done, we can have a path generation that is reasonably fast. We can probably improve the speed here. SIMD can probably be used even in the inner loop, as we test three side and a top value, which makes it align nicely with SIMD lanes.

The road so far

With that added in, we can generate paths in real time without anything baked.

But we still have some major problems:

• the first and most annoying problem for now: this is the movement of a point, not a shape, which makes it wrong for every entity in the game for now.

• Still need to add game specific stuff, like ladders, grabbing ledge, grabbing walls, etc…

  Let’s have a look at what it looks like for now if we cheat the first point by adding a very small physics bounding box to a sprite. Estimated path is in blue, entity bounding box is the small cube moving. The entity moves when i click on a platform, using the calculated path to go there :

See you next time, when If I figure out how to generate navigation mesh for some specific shapes. If you have any idea for this, please comment below.

Thank you for reading,

Guillaume