Tiled world consisting of one tile - dtNavMesh::init fails

[GoogleCodeExporter]

If you happen to have a setup whereby the tile size is the same (or bigger) 
than the world size then the following code fails:

bool dtNavMesh::init(const dtNavMeshParams* params)
{
    ...

    // Init ID generator values.
    m_tileBits = dtMax((unsigned int)1, dtIlog2(dtNextPow2((unsigned int)params->maxTiles)));
    m_polyBits = dtMax((unsigned int)1, dtIlog2(dtNextPow2((unsigned int)params->maxPolys)));
    m_saltBits = 32 - m_tileBits - m_polyBits;
    if (m_saltBits < 10)
        return false;  <--- FAILS HERE

Is this because it is trying to assign at least one bit to the tile ID when it 
should be assigning 0 bits?

Thanks,
Neil

Original issue reported on code.google.com by armstron...@gmail.com on 8 Jun 2010 at 2:47

[GoogleCodeExporter]

In order to keep the IDs unique and valid there needs to be at least one bit 
for polys and one for tiles. I cannot remember exact details, but I think there 
was something related to generating the masks and shifts which generated bad 
data when tile or poly bits were zero.

Original comment by memono...@gmail.com on 8 Jun 2010 at 5:18

• Changed state: WontFix

[GoogleCodeExporter]

So - it's not possible to have a world where there's only one tile?

Actually, I'm investigating an issue whereby encodePolyId and decodePolyId 
return different values...I wonder if that was causing issues? I haven't got to 
the bottom of it yet - but it would appear the "it" (tile index value?) upsets 
the "salt" value when the "it" is at max value.

encodePolyId(0, 3, 0);

decodePolyId returns "salt" of 1...but it was set to 0.

FYI: m_polyBits = 20, m_tileBits = 2, m_maxTiles = 4

I'm not really sure why encoding the poly id adds one to the "it" value...that 
seems to cause the issue.

Original comment by armstron...@gmail.com on 8 Jun 2010 at 5:38

[GoogleCodeExporter]

Ok - it appears you can fix this issue by not adding 1 to the "it" value and 
never letting "salt" start at 0 for a tile - i.e. initialise it to 1.

Where you increment the "salt" counter in "removeTile" it'd probably be a good 
idea to encode and decode it...to deal with wrapping issues.

Code changes:

    // Encodes a tile id.
    inline dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const
    {
        return (salt << (m_polyBits+m_tileBits)) | ((it) << m_polyBits) | ip;
    }

    // Decodes a tile id.
    inline void decodePolyId(dtPolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip) const
    {
        salt = (ref >> (m_polyBits+m_tileBits)) & ((1<<m_saltBits)-1);
        it = ((ref >> m_polyBits)) & ((1<<m_tileBits)-1);
        ip = ref & ((1<<m_polyBits)-1);
    }

    // Decodes a tile salt.
    inline unsigned int decodePolyIdSalt(dtPolyRef ref) const
    {
        return (ref >> (m_polyBits+m_tileBits)) & ((1<<m_saltBits)-1);
    }

    // Decodes a tile id.
    inline unsigned int decodePolyIdTile(dtPolyRef ref) const
    {
        return ((ref >> m_polyBits)) & ((1<<m_tileBits)-1);
    }

Original comment by armstron...@gmail.com on 8 Jun 2010 at 5:57

[GoogleCodeExporter]

Original comment by memono...@gmail.com on 9 Jun 2010 at 5:41

• Changed state: Accepted

[GoogleCodeExporter]

Fixed in R173. I made salt to be always non-zero as you suggested.

Original comment by memono...@gmail.com on 8 Jul 2010 at 12:05

• Changed state: Fixed

[GoogleCodeExporter]

This fix doesn't quite work. My fault, I didn't tell you all the changes I'd 
made (Ooops):

bool dtNavMesh::init(const dtNavMeshParams* params)
{
    ...
    // Init ID generator values.
    m_tileBits = dtMax((unsigned int)0, dtIlog2(dtNextPow2((unsigned int)params->maxTiles)));

Change the 1 to a 0

Also, personally, I'd change the following code:

dtNavMesh::removeTile( .. )
{
    ...
    // Update salt, salt should never be zero.
    tile->salt++;
    dtTileRef saltRef = (dtTileRef)encodePolyId(tile->salt, 0, 0);
    tile->salt = decodePolyIdSalt((dtPolyRef)saltRef);
    if ( tile->salt == 0 )
        tile->salt = 1;

Original comment by armstron...@gmail.com on 24 Aug 2010 at 11:58