Navmesh walkable seeds are ignored if a redundant seed is encountered

[Xyxen]

Details

During navmesh generation, if a walkable seed is picked that resides in a previously-sampled area, all remaining walkable seeds are ignored. Obviously, this can cause portions of the map to be left uncovered. Avoiding placing down redundant seeds isn't reasonably possible: how do you determine this procedurally without generating the mesh to find out?

Steps to reproduce

Start with any map lacking a navmesh. I've chosen gm_bigcity here. Enter nav editing mode, and crank things down so generation doesn't take more than a few seconds:

sv_cheats 1
nav_edit 1

// Generate just enough areas to demonstrate the problem.
nav_generate_incremental_range 200

// "Disable" visibility calculations by setting the distance as low as possible.
nav_max_view_distance 1

// Disable expensive analysis steps (this is the default anyway).
nav_quicksave 1

Pick a spot, and place down a pair of walkable seeds (nav_mark_walkable) right next to each other, followed by one off on its own. This order is important, as the seeds are iterated in order of creation.

Now run nav_generate_incremental.

Notice that only the area around the first seed has been generated. (The region is slightly oblong, encompassing the 200 unit area around the second seed, but this is strictly due to the range limit considering all seeds, rather than only the current one.) It's expected that the area around the third seed should be sampled as well.

Steps to resolve

Seed selection occurs in CNavMesh::SampleStep(void). When a region of the map has been fully sampled, m_currentNode becomes NULL (because seeds have no parent). When this happens, CNavMesh::GetNextWalkableSeedNode(void) is called to obtain the next one.

The calling code expects that a NULL return value indicates that the seed list has been exhausted. However, the following lines in GetNextWalkableSeedNode violate that expectation:

...
    // check if a node exists at this location
    CNavNode *node = CNavNode::GetNode( spot.pos );
    if ( node )
        return NULL;
...

When a redundant seed is found, the next seed should be tested instead of giving up like this. As such, GetNextWalkableSeed should be changed to the following:

CNavNode *CNavMesh::GetNextWalkableSeedNode( void )
{   
    while (m_seedIdx < m_walkableSeeds.Count()) {
        WalkableSeedSpot spot = m_walkableSeeds[m_seedIdx];
        ++m_seedIdx;

        // check if a node exists at this location
        CNavNode *node = CNavNode::GetNode(spot.pos);
        if (node)
            continue;

        return new CNavNode(spot.pos, spot.normal, NULL, false);
    }

    // all seeds have been visited
    return NULL;
}

Which gives the expected result in the above example:

[willox]

This should now be fixed on the dev branch.

[Xyxen]

I'm no longer experiencing any issues with this. Thanks for the lightning-fast turnaround!