NAV-MESH Generation (for an RTS game)

2D convex poly graph built using a similar method to Havok AI’s 2019 GDC talk “Math for Game Developers: Generating and using Navigation Meshes”

My latest personal project is a networked, 2-player RTS game featuring a navigation mesh that is relatively efficient given a random set of obstacles that are scattered across the map.

I followed Ben Sunshine-Hill’s example for a 3D navigation mesh found in his 2019 GDC talk “Math for Game Developers: Generating and using Navigation Meshes”. The steps I used were as follows:

  • Pixelization - turn the world into a 2d grid and block grid spaces for each obstacle

  • Grassfire - set '“fire” to the boundary tiles, then spread inward until the radius of an actor is covered. This is so that we are only left with an area that the center of each actor can stand on.

  • RDP - decimate the grid edges into simpler shapes

  • Bridge regions - take any holes in the world and connect them back to the main outer polygon by creating a “bridge” between them.

  • Fill the bridged region with convex polys - Step through the now completely unified polygon and create convex polys where possible.

  • Connect the convex poly’s into a graph for pathfinding

After creating the navigation graph (blue lines)

Escape Velocity: Starship

In semester 3, I upgraded Starship’s graphics to use our personal engines’ new 3D capabilities, learning how to implement basic lighting with normal maps as well as generating an icosphere and deforming it with Perlin noise to create the shape of the asteroids.

Generating thousands of verts each with Perlin noise and recalculating their normals can be expensive to do for every asteroid that gets created, so I make a pool of generated asteroid shapes when the world gets created and use that. Here is the generation function:

void World::GenerateAsteroidShapes()
{
    int numUniqueAsteroidShapes = g_gameConfigBlackboard.GetValue( "numUniqueAsteroidShapes", 10 );
    int asteroidLOD = g_gameConfigBlackboard.GetValue( "asteroidLOD", 4 );
    for ( int i = 0; i < numUniqueAsteroidShapes; i++ )
    {
        VertexBuffer* asteroidShape = g_theRenderer->CreateVertexBuffer_PCUN( sizeof( Vertex_PCUN ) );
        std::vector<Vertex_PCUN> verts;
        verts.reserve( 15360 );
        AddVertsForIcosphereZ3D( verts, Vec3::ZERO, 1.f, asteroidLOD, Rgba8::DARK_GRAY );

        for ( Vertex_PCUN& vert : verts )
        {
            float scale = 3.f;
            int numOctaves = 7;
            float octavePersistance = 0.5f;
            float octaveScale = 2.f;
            bool renormalize = true;
            float noise = Compute3dPerlinNoise( vert.m_position.x, vert.m_position.y, vert.m_position.z, scale, numOctaves, octavePersistance, octaveScale, renormalize );
            float vertLength = vert.m_position.GetLength();
            vert.m_position.SetLength( vertLength + noise );
        }
        RecalculateNormals_Simple( verts );
        g_theRenderer->FillVertexBuffer_PCUN( asteroidShape, verts.data(), (int) verts.size() );
        m_asteroidShapes.push_back( asteroidShape );
    }
}

I used a monolithic Actor class for this project, and I couldn’t be happier about it. The entire game felt like one big prototype where I was in a race to get as many new cool features in as I could. After all, this was my free time to explore what made me happy and interested in game development, so I used it wisely.

Directional+Blinn Phong lighting. Model by NebulaTank: https://sketchfab.com/NebulaTank/models

Directional+Blinn Phong lighting. Model by NebulaTank: https://sketchfab.com/NebulaTank/models

One of the goals of the project was lighting, so I ended up with ambient, directional, and eventually Blinn Phong specular lighting. But first I had to write a new vertex layout for my Renderer that had normals on it as well as a Obj parser to load the 3d models in from Blender. I also experimented with outline shaders and cartoony shaders.

Faction shader. Model by NebulaTank: https://sketchfab.com/NebulaTank/models

Faction shader. Model by NebulaTank: https://sketchfab.com/NebulaTank/models

A lot of the fun of the shaders in the project was in the Shield effect. I used an icosphere, which I originally intended to only be used for the asteroids, and a shader that used a Constant Buffer per actor with its recent collision data. Based on how recently the collision hit, and at what normal, the shield would grow and shrink around the ship.

You can also see the cartoony effect that I used on the asteroid and shield shaders.

Takeaways

This project was start to finish exciting for me because I felt like I was always pushing the boundary of what I know, as well as reusing those new concepts in different and interesting ways along the journey. I am happiest programming when I am in that flow state of learning and doing.