MapBuilder.cpp

Go to the documentation of this file.

/*
* This file is part of Project SkyFire https://www.projectskyfire.org. 
* See LICENSE.md file for Copyright information
*/
 
#include "PathCommon.h"
#include "MapBuilder.h"
 
#include "MapTree.h"
#include "ModelInstance.h"
 
#include "DetourNavMeshBuilder.h"
#include "DetourNavMesh.h"
#include "DetourCommon.h"
#include "DisableMgr.h"
 
#include <boost/asio/post.hpp>
#include <boost/asio/thread_pool.hpp>
 
#include <functional>
#include <thread>
#include <vector>
 
uint32 GetLiquidFlags(uint32 /*liquidType*/) { return 0; }
 
namespace DisableMgr
{
    bool IsDisabledFor(DisableType /*type*/, uint32 /*entry*/, Unit const* /*unit*/, uint8 /*flags*/ /*= 0*/) { return false; }
}
 
#define MMAP_MAGIC 0x4d4d4150   // 'MMAP'
#define MMAP_VERSION 5.2f
 
struct MmapTileHeader
{
    uint32 mmapMagic;
    uint32 dtVersion;
    float mmapVersion;
    uint32 size;
    bool usesLiquids : 1;
 
    MmapTileHeader() : mmapMagic(MMAP_MAGIC), dtVersion(DT_NAVMESH_VERSION),
        mmapVersion(MMAP_VERSION), size(0), usesLiquids(true) {}
};
 
namespace MMAP
{
    MapBuilder::MapBuilder(float maxWalkableAngle, bool skipLiquid,
        bool skipContinents, bool skipJunkMaps, bool skipBattlegrounds,
        bool debugOutput, bool bigBaseUnit, const char* offMeshFilePath) :
        m_terrainBuilder     (NULL),
        m_debugOutput        (debugOutput),
        m_offMeshFilePath    (offMeshFilePath),
        m_skipContinents     (skipContinents),
        m_skipJunkMaps       (skipJunkMaps),
        m_skipBattlegrounds  (skipBattlegrounds),
        m_maxWalkableAngle   (maxWalkableAngle),
        m_bigBaseUnit        (bigBaseUnit),
        m_rcContext          (NULL)
    {
        m_terrainBuilder = new TerrainBuilder(skipLiquid);
 
        m_rcContext = new rcContext(false);
 
        discoverTiles();
    }
 
    /**************************************************************************/
    MapBuilder::~MapBuilder()
    {
        for (TileList::iterator it = m_tiles.begin(); it != m_tiles.end(); ++it)
        {
            (*it).second->clear();
            delete (*it).second;
        }
 
        delete m_terrainBuilder;
        delete m_rcContext;
    }
 
    /**************************************************************************/
    void MapBuilder::discoverTiles()
    {
        std::vector<std::string> files;
        uint32 mapID, tileX, tileY, tileID, count = 0;
 
        printf("Discovering maps... ");
        getDirContents(files, "maps");
        for (uint32 i = 0; i < files.size(); ++i)
        {
            mapID = uint32(atoi(files[i].substr(0, 4).c_str()));
            if (m_tiles.find(mapID) == m_tiles.end())
            {
                m_tiles.insert(std::pair<uint32, std::set<uint32>*>(mapID, new std::set<uint32>));
                count++;
            }
        }
 
        files.clear();
        getDirContents(files, "vmaps", "*.vmtree");
        for (uint32 i = 0; i < files.size(); ++i)
        {
            mapID = uint32(atoi(files[i].substr(0, 4).c_str()));
            m_tiles.insert(std::pair<uint32, std::set<uint32>*>(mapID, new std::set<uint32>));
            count++;
        }
        printf("found %u.\n", count);
 
        count = 0;
        printf("Discovering tiles... ");
        for (TileList::iterator itr = m_tiles.begin(); itr != m_tiles.end(); ++itr)
        {
            std::set<uint32>* tiles = (*itr).second;
            mapID = (*itr).first;
 
            files.clear();
            char filter[13];
            snprintf(filter, sizeof(filter), "%04u*.vmtile", mapID);
            getDirContents(files, "vmaps", filter);
            for (uint32 i = 0; i < files.size(); ++i)
            {
                tileX = uint32(atoi(files[i].substr(8, 2).c_str()));
                tileY = uint32(atoi(files[i].substr(5, 2).c_str()));
                tileID = StaticMapTree::packTileID(tileY, tileX);
 
                tiles->insert(tileID);
                count++;
            }
 
            files.clear();
            snprintf(filter, sizeof(filter), "%04u*", mapID);
            getDirContents(files, "maps", filter);
            for (uint32 i = 0; i < files.size(); ++i)
            {
                tileY = uint32(atoi(files[i].substr(5, 2).c_str()));
                tileX = uint32(atoi(files[i].substr(8, 2).c_str()));
                tileID = StaticMapTree::packTileID(tileX, tileY);
 
                if (tiles->insert(tileID).second)
                    count++;
            }
        }
        printf("found %u.\n", count);
    }
 
    /**************************************************************************/
    std::set<uint32>* MapBuilder::getTileList(uint32 mapID)
    {
        TileList::iterator itr = m_tiles.find(mapID);
        if (itr != m_tiles.end())
            return (*itr).second;
 
        std::set<uint32>* tiles = new std::set<uint32>();
        m_tiles.insert(std::pair<uint32, std::set<uint32>*>(mapID, tiles));
        return tiles;
    }
 
    /**************************************************************************/
    void MapBuilder::buildAllMaps(unsigned int threads)
    {
        std::vector<uint32> mapsToBuild;
 
        for (TileList::iterator it = m_tiles.begin(); it != m_tiles.end(); ++it)
        {
            uint32 mapID = it->first;
            if (!shouldSkipMap(mapID))
                mapsToBuild.push_back(mapID);
        }
 
        printf("Using %u threads to extract mmaps\n", threads);
 
        if (threads == 0)
        {
            for (std::vector<uint32>::iterator it = mapsToBuild.begin(); it != mapsToBuild.end(); ++it)
                buildMap(*it);
 
            return;
        }
 
        boost::asio::thread_pool threadPool(threads);
 
        for (std::vector<uint32>::iterator it = mapsToBuild.begin(); it != mapsToBuild.end(); ++it)
        {
            uint32 mapID = *it;
            boost::asio::post(threadPool,
                [this, mapID]
                {
                    buildMap(mapID);
                });
        }
 
        threadPool.join();
    }
 
    /**************************************************************************/
    void MapBuilder::getGridBounds(uint32 mapID, uint32 &minX, uint32 &minY, uint32 &maxX, uint32 &maxY)
    {
        maxX = INT_MAX;
        maxY = INT_MAX;
        minX = INT_MIN;
        minY = INT_MIN;
 
        float bmin[3], bmax[3], lmin[3], lmax[3];
        MeshData meshData;
 
        // make sure we process maps which don't have tiles
        // initialize the static tree, which loads WDT models
        if (!m_terrainBuilder->loadVMap(mapID, 64, 64, meshData))
            return;
 
        // get the coord bounds of the model data
        if (meshData.solidVerts.size() + meshData.liquidVerts.size() == 0)
            return;
 
        // get the coord bounds of the model data
        if (meshData.solidVerts.size() && meshData.liquidVerts.size())
        {
            rcCalcBounds(meshData.solidVerts.getCArray(), meshData.solidVerts.size() / 3, bmin, bmax);
            rcCalcBounds(meshData.liquidVerts.getCArray(), meshData.liquidVerts.size() / 3, lmin, lmax);
            rcVmin(bmin, lmin);
            rcVmax(bmax, lmax);
        }
        else if (meshData.solidVerts.size())
            rcCalcBounds(meshData.solidVerts.getCArray(), meshData.solidVerts.size() / 3, bmin, bmax);
        else
            rcCalcBounds(meshData.liquidVerts.getCArray(), meshData.liquidVerts.size() / 3, lmin, lmax);
 
        // convert coord bounds to grid bounds
        maxX = 32 - bmin[0] / GRID_SIZE;
        maxY = 32 - bmin[2] / GRID_SIZE;
        minX = 32 - bmax[0] / GRID_SIZE;
        minY = 32 - bmax[2] / GRID_SIZE;
    }
 
    void MapBuilder::buildMeshFromFile(char* name)
    {
        FILE* file = fopen(name, "rb");
        if (!file)
            return;
 
        printf("Building mesh from file\n");
        int tileX, tileY, mapId;
        if ((fread(&mapId, sizeof(int), 1, file) != 1) || (fread(&tileX, sizeof(int), 1, file) != 1) || (fread(&tileY, sizeof(int), 1, file) != 1))
            return;
 
        dtNavMesh* navMesh = NULL;
        buildNavMesh(mapId, navMesh);
        if (!navMesh)
        {
            printf("Failed creating navmesh!\n");
            fclose(file);
            return;
        }
 
        uint32 verticesCount, indicesCount;
        if (fread(&verticesCount, sizeof(uint32), 1, file) != 1)
            return;
        if (fread(&indicesCount, sizeof(uint32), 1, file) != 1)
            return;
 
        float* verts = new float[verticesCount];
        int* inds = new int[indicesCount];
 
        if ((fread(verts, sizeof(float), verticesCount, file) != verticesCount) || 
            (fread(inds, sizeof(int), indicesCount, file) != indicesCount))
        {
            delete[] verts;
            delete[] inds;
            return;
        }
 
        MeshData data;
 
        for (uint32 i = 0; i < verticesCount; ++i)
            data.solidVerts.append(verts[i]);
 
        for (uint32 i = 0; i < indicesCount; ++i)
            data.solidTris.append(inds[i]);
 
        delete[] verts;
        delete[] inds;
 
        TerrainBuilder::cleanVertices(data.solidVerts, data.solidTris);
        // get bounds of current tile
        float bmin[3], bmax[3];
        getTileBounds(tileX, tileY, data.solidVerts.getCArray(), data.solidVerts.size() / 3, bmin, bmax);
 
        // build navmesh tile
        buildMoveMapTile(mapId, tileX, tileY, data, bmin, bmax, navMesh);
        fclose(file);
    }
 
    /**************************************************************************/
    void MapBuilder::buildSingleTile(uint32 mapID, uint32 tileX, uint32 tileY)
    {
        dtNavMesh* navMesh = NULL;
        buildNavMesh(mapID, navMesh);
        if (!navMesh)
        {
            printf("Failed creating navmesh!\n");
            return;
        }
 
        buildTile(mapID, tileX, tileY, navMesh);
        dtFreeNavMesh(navMesh);
    }
 
    /**************************************************************************/
    void MapBuilder::buildMap(uint32 mapID)
    {
        printf("[Thread %u] Building map %04u:\n", uint32(std::hash<std::thread::id>()(std::this_thread::get_id())), mapID);
 
        std::set<uint32>* tiles = getTileList(mapID);
 
        // make sure we process maps which don't have tiles
        if (!tiles->size())
        {
            // convert coord bounds to grid bounds
            uint32 minX, minY, maxX, maxY;
            getGridBounds(mapID, minX, minY, maxX, maxY);
 
            // add all tiles within bounds to tile list.
            for (uint32 i = minX; i <= maxX; ++i)
                for (uint32 j = minY; j <= maxY; ++j)
                    tiles->insert(StaticMapTree::packTileID(i, j));
        }
 
        if (!tiles->empty())
        {
            // build navMesh
            dtNavMesh* navMesh = NULL;
            buildNavMesh(mapID, navMesh);
            if (!navMesh)
            {
                printf("[Map %04i] Failed creating navmesh!\n", mapID);
                return;
            }
            // now start building mmtiles for each tile
            printf("[Map %04i] We have %u tiles. \n", mapID, (unsigned int)tiles->size());
            for (std::set<uint32>::iterator it = tiles->begin(); it != tiles->end(); ++it)
            {
                uint32 tileX, tileY;
 
                // unpack tile coords
                StaticMapTree::unpackTileID((*it), tileX, tileY);
 
                if (shouldSkipTile(mapID, tileX, tileY))
                    continue;
 
                buildTile(mapID, tileX, tileY, navMesh);
            }
 
            dtFreeNavMesh(navMesh);
        }
 
        printf("[Map %04u] Complete!\n", mapID);
    }
 
    /**************************************************************************/
    void MapBuilder::buildTile(uint32 mapID, uint32 tileX, uint32 tileY, dtNavMesh* navMesh)
    {
        printf("[Map %04i] Building tile [%02u,%02u]\n", mapID, tileX, tileY);
 
        MeshData meshData;
 
        // get heightmap data
        m_terrainBuilder->loadMap(mapID, tileX, tileY, meshData);
 
        // get model data
        m_terrainBuilder->loadVMap(mapID, tileY, tileX, meshData);
 
        // if there is no data, give up now
        if (!meshData.solidVerts.size() && !meshData.liquidVerts.size())
            return;
 
        // remove unused vertices
        TerrainBuilder::cleanVertices(meshData.solidVerts, meshData.solidTris);
        TerrainBuilder::cleanVertices(meshData.liquidVerts, meshData.liquidTris);
 
        // gather all mesh data for final data check, and bounds calculation
        G3D::Array<float> allVerts;
        allVerts.append(meshData.liquidVerts);
        allVerts.append(meshData.solidVerts);
 
        if (!allVerts.size())
            return;
 
        // get bounds of current tile
        float bmin[3], bmax[3];
        getTileBounds(tileX, tileY, allVerts.getCArray(), allVerts.size() / 3, bmin, bmax);
 
        m_terrainBuilder->loadOffMeshConnections(mapID, tileX, tileY, meshData, m_offMeshFilePath);
 
        // build navmesh tile
        buildMoveMapTile(mapID, tileX, tileY, meshData, bmin, bmax, navMesh);
    }
 
    /**************************************************************************/
    void MapBuilder::buildNavMesh(uint32 mapID, dtNavMesh* &navMesh)
    {
        std::set<uint32>* tiles = getTileList(mapID);
 
        // old code for non-statically assigned bitmask sizes:
        //int tileBits = dtIlog2(dtNextPow2(tiles->size()));
        //if (tileBits < 1) tileBits = 1;                                     // need at least one bit!
        //int polyBits = sizeof(dtPolyRef)*8 - SALT_MIN_BITS - tileBits;
 
        int polyBits = STATIC_POLY_BITS;
 
        int maxTiles = tiles->size();
        int maxPolysPerTile = 1 << polyBits;
 
        /*** calculate bounds of map ***/
 
        uint32 tileXMin = 64, tileYMin = 64, tileXMax = 0, tileYMax = 0, tileX, tileY;
        for (std::set<uint32>::iterator it = tiles->begin(); it != tiles->end(); ++it)
        {
            StaticMapTree::unpackTileID(*it, tileX, tileY);
 
            if (tileX > tileXMax)
                tileXMax = tileX;
            else if (tileX < tileXMin)
                tileXMin = tileX;
 
            if (tileY > tileYMax)
                tileYMax = tileY;
            else if (tileY < tileYMin)
                tileYMin = tileY;
        }
 
        // use Max because '32 - tileX' is negative for values over 32
        float bmin[3], bmax[3];
        getTileBounds(tileXMax, tileYMax, NULL, 0, bmin, bmax);
 
        /*** now create the navmesh ***/
 
        // navmesh creation params
        dtNavMeshParams navMeshParams;
        memset(&navMeshParams, 0, sizeof(dtNavMeshParams));
        navMeshParams.tileWidth = GRID_SIZE;
        navMeshParams.tileHeight = GRID_SIZE;
        rcVcopy(navMeshParams.orig, bmin);
        navMeshParams.maxTiles = maxTiles;
        navMeshParams.maxPolys = maxPolysPerTile;
 
        navMesh = dtAllocNavMesh();
        printf("[Map %04u] Creating navMesh...\n", mapID);
        if (!navMesh->init(&navMeshParams))
        {
            printf("[Map %04u] Failed creating navmesh!  \n", mapID);
            return;
        }
 
        char fileName[25];
        snprintf(fileName, sizeof(fileName), "mmaps/%04u.mmap", mapID);
 
        FILE* file = fopen(fileName, "wb");
        if (!file)
        {
            dtFreeNavMesh(navMesh);
            char message[1024];
            snprintf(message, sizeof(message), "[Map %04u] Failed to open %s for writing!\n", mapID, fileName);
            perror(message);
            return;
        }
 
        // now that we know navMesh params are valid, we can write them to file
        fwrite(&navMeshParams, sizeof(dtNavMeshParams), 1, file);
        fclose(file);
    }
 
    /**************************************************************************/
    void MapBuilder::buildMoveMapTile(uint32 mapID, uint32 tileX, uint32 tileY,
        MeshData &meshData, float bmin[3], float bmax[3],
        dtNavMesh* navMesh)
    {
        // console output
        char tileString[25];
        snprintf(tileString, sizeof(tileString), "[Map %04u] [%02i,%02i]: ", mapID, tileX, tileY);
        printf("%s Building movemap tiles...\n", tileString);
 
        IntermediateValues iv;
 
        float* tVerts = meshData.solidVerts.getCArray();
        int tVertCount = meshData.solidVerts.size() / 3;
        int* tTris = meshData.solidTris.getCArray();
        int tTriCount = meshData.solidTris.size() / 3;
 
        float* lVerts = meshData.liquidVerts.getCArray();
        int lVertCount = meshData.liquidVerts.size() / 3;
        int* lTris = meshData.liquidTris.getCArray();
        int lTriCount = meshData.liquidTris.size() / 3;
        uint8* lTriFlags = meshData.liquidType.getCArray();
 
        // these are WORLD UNIT based metrics
        // this are basic unit dimentions
        // value have to divide GRID_SIZE(533.3333f) ( aka: 0.5333, 0.2666, 0.3333, 0.1333, etc )
        const static float BASE_UNIT_DIM = m_bigBaseUnit ? 0.5333333f : 0.2666666f;
 
        // All are in UNIT metrics!
        const static int VERTEX_PER_MAP = int(GRID_SIZE/BASE_UNIT_DIM + 0.5f);
        const static int VERTEX_PER_TILE = m_bigBaseUnit ? 40 : 80; // must divide VERTEX_PER_MAP
        const static int TILES_PER_MAP = VERTEX_PER_MAP/VERTEX_PER_TILE;
 
        rcConfig config;
        memset(&config, 0, sizeof(rcConfig));
 
        rcVcopy(config.bmin, bmin);
        rcVcopy(config.bmax, bmax);
 
        config.maxVertsPerPoly = DT_VERTS_PER_POLYGON;
        config.cs = BASE_UNIT_DIM;
        config.ch = BASE_UNIT_DIM;
        config.walkableSlopeAngle = m_maxWalkableAngle;
        config.tileSize = VERTEX_PER_TILE;
        config.walkableRadius = m_bigBaseUnit ? 1 : 2;
        config.borderSize = config.walkableRadius + 3;
        config.maxEdgeLen = VERTEX_PER_TILE + 1;        // anything bigger than tileSize
        config.walkableHeight = m_bigBaseUnit ? 3 : 6;
        config.walkableClimb = m_bigBaseUnit ? 2 : 4;   // keep less than walkableHeight
        config.minRegionArea = rcSqr(60);
        config.mergeRegionArea = rcSqr(50);
        config.maxSimplificationError = 1.8f;           // eliminates most jagged edges (tiny polygons)
        config.detailSampleDist = config.cs * 64;
        config.detailSampleMaxError = config.ch * 2;
 
        // this sets the dimensions of the heightfield - should maybe happen before border padding
        rcCalcGridSize(config.bmin, config.bmax, config.cs, &config.width, &config.height);
 
        // allocate subregions : tiles
        Tile* tiles = new Tile[TILES_PER_MAP * TILES_PER_MAP];
 
        // Initialize per tile config.
        rcConfig tileCfg = config;
        tileCfg.width = config.tileSize + config.borderSize*2;
        tileCfg.height = config.tileSize + config.borderSize*2;
 
        // merge per tile poly and detail meshes
        rcPolyMesh** pmmerge = new rcPolyMesh*[TILES_PER_MAP * TILES_PER_MAP];
        if (!pmmerge)
        {
            printf("%s alloc pmmerge FAILED!\n", tileString);
            return;
        }
 
        rcPolyMeshDetail** dmmerge = new rcPolyMeshDetail*[TILES_PER_MAP * TILES_PER_MAP];
        if (!dmmerge)
        {
            printf("%s alloc dmmerge FAILED!\n", tileString);
            return;
        }
 
        int nmerge = 0;
 
        // build all tiles
        for (int y = 0; y < TILES_PER_MAP; ++y)
        {
            for (int x = 0; x < TILES_PER_MAP; ++x)
            {
                Tile& tile = tiles[x + y * TILES_PER_MAP];
 
                // Calculate the per tile bounding box.
                tileCfg.bmin[0] = config.bmin[0] + float(x*config.tileSize - config.borderSize)*config.cs;
                tileCfg.bmin[2] = config.bmin[2] + float(y*config.tileSize - config.borderSize)*config.cs;
                tileCfg.bmax[0] = config.bmin[0] + float((x+1)*config.tileSize + config.borderSize)*config.cs;
                tileCfg.bmax[2] = config.bmin[2] + float((y+1)*config.tileSize + config.borderSize)*config.cs;
 
                // build heightfield
                tile.solid = rcAllocHeightfield();
                if (!tile.solid || !rcCreateHeightfield(m_rcContext, *tile.solid, tileCfg.width, tileCfg.height, tileCfg.bmin, tileCfg.bmax, tileCfg.cs, tileCfg.ch))
                {
                    printf("%s Failed building heightfield! \n", tileString);
                    continue;
                }
 
                // mark all walkable tiles, both liquids and solids
                unsigned char* triFlags = new unsigned char[tTriCount];
                memset(triFlags, NAV_GROUND, tTriCount*sizeof(unsigned char));
                rcClearUnwalkableTriangles(m_rcContext, tileCfg.walkableSlopeAngle, tVerts, tVertCount, tTris, tTriCount, triFlags);
                rcRasterizeTriangles(m_rcContext, tVerts, tVertCount, tTris, triFlags, tTriCount, *tile.solid, config.walkableClimb);
                delete[] triFlags;
 
                rcFilterLowHangingWalkableObstacles(m_rcContext, config.walkableClimb, *tile.solid);
                rcFilterLedgeSpans(m_rcContext, tileCfg.walkableHeight, tileCfg.walkableClimb, *tile.solid);
                rcFilterWalkableLowHeightSpans(m_rcContext, tileCfg.walkableHeight, *tile.solid);
 
                rcRasterizeTriangles(m_rcContext, lVerts, lVertCount, lTris, lTriFlags, lTriCount, *tile.solid, config.walkableClimb);
 
                // compact heightfield spans
                tile.chf = rcAllocCompactHeightfield();
                if (!tile.chf || !rcBuildCompactHeightfield(m_rcContext, tileCfg.walkableHeight, tileCfg.walkableClimb, *tile.solid, *tile.chf))
                {
                    printf("%s Failed compacting heightfield! \n", tileString);
                    continue;
                }
 
                // build polymesh intermediates
                if (!rcErodeWalkableArea(m_rcContext, config.walkableRadius, *tile.chf))
                {
                    printf("%s Failed eroding area! \n", tileString);
                    continue;
                }
 
                if (!rcBuildDistanceField(m_rcContext, *tile.chf))
                {
                    printf("%s Failed building distance field! \n", tileString);
                    continue;
                }
 
                if (!rcBuildRegions(m_rcContext, *tile.chf, tileCfg.borderSize, tileCfg.minRegionArea, tileCfg.mergeRegionArea))
                {
                    printf("%s Failed building regions!  \n", tileString);
                    continue;
                }
 
                tile.cset = rcAllocContourSet();
                if (!tile.cset || !rcBuildContours(m_rcContext, *tile.chf, tileCfg.maxSimplificationError, tileCfg.maxEdgeLen, *tile.cset))
                {
                    printf("%s Failed building contours! \n", tileString);
                    continue;
                }
 
                // build polymesh
                tile.pmesh = rcAllocPolyMesh();
                if (!tile.pmesh || !rcBuildPolyMesh(m_rcContext, *tile.cset, tileCfg.maxVertsPerPoly, *tile.pmesh))
                {
                    printf("%s Failed building polymesh! \n", tileString);
                    continue;
                }
 
                tile.dmesh = rcAllocPolyMeshDetail();
                if (!tile.dmesh || !rcBuildPolyMeshDetail(m_rcContext, *tile.pmesh, *tile.chf, tileCfg.detailSampleDist, tileCfg.detailSampleMaxError, *tile.dmesh))
                {
                    printf("%s Failed building polymesh detail!\n", tileString);
                    continue;
                }
 
                // free those up
                // we may want to keep them in the future for debug
                // but right now, we don't have the code to merge them
                rcFreeHeightField(tile.solid);
                tile.solid = NULL;
                rcFreeCompactHeightfield(tile.chf);
                tile.chf = NULL;
                rcFreeContourSet(tile.cset);
                tile.cset = NULL;
 
                if (tile.pmesh)
                {
                    pmmerge[nmerge] = tile.pmesh;
                    dmmerge[nmerge] = tile.dmesh;
                    nmerge++;
                }
            }
        }
 
        iv.polyMesh = rcAllocPolyMesh();
        if (!iv.polyMesh)
        {
            printf("%s alloc iv.polyMesh FAILED!\n", tileString);
            return;
        }
        rcMergePolyMeshes(m_rcContext, pmmerge, nmerge, *iv.polyMesh);
 
        iv.polyMeshDetail = rcAllocPolyMeshDetail();
        if (!iv.polyMeshDetail)
        {
            printf("%s alloc m_dmesh FAILED!\n", tileString);
            return;
        }
        rcMergePolyMeshDetails(m_rcContext, dmmerge, nmerge, *iv.polyMeshDetail);
 
        // free things up
        delete[] pmmerge;
        delete[] dmmerge;
 
        delete[] tiles;
 
        // set polygons as walkable
        // TODO: special flags for DYNAMIC polygons, ie surfaces that can be turned on and off
        for (int i = 0; i < iv.polyMesh->npolys; ++i)
            if (iv.polyMesh->areas[i] & RC_WALKABLE_AREA)
                iv.polyMesh->flags[i] = iv.polyMesh->areas[i];
 
        // setup mesh parameters
        dtNavMeshCreateParams params;
        memset(&params, 0, sizeof(params));
        params.verts = iv.polyMesh->verts;
        params.vertCount = iv.polyMesh->nverts;
        params.polys = iv.polyMesh->polys;
        params.polyAreas = iv.polyMesh->areas;
        params.polyFlags = iv.polyMesh->flags;
        params.polyCount = iv.polyMesh->npolys;
        params.nvp = iv.polyMesh->nvp;
        params.detailMeshes = iv.polyMeshDetail->meshes;
        params.detailVerts = iv.polyMeshDetail->verts;
        params.detailVertsCount = iv.polyMeshDetail->nverts;
        params.detailTris = iv.polyMeshDetail->tris;
        params.detailTriCount = iv.polyMeshDetail->ntris;
 
        params.offMeshConVerts = meshData.offMeshConnections.getCArray();
        params.offMeshConCount = meshData.offMeshConnections.size()/6;
        params.offMeshConRad = meshData.offMeshConnectionRads.getCArray();
        params.offMeshConDir = meshData.offMeshConnectionDirs.getCArray();
        params.offMeshConAreas = meshData.offMeshConnectionsAreas.getCArray();
        params.offMeshConFlags = meshData.offMeshConnectionsFlags.getCArray();
 
        params.walkableHeight = BASE_UNIT_DIM*config.walkableHeight;    // agent height
        params.walkableRadius = BASE_UNIT_DIM*config.walkableRadius;    // agent radius
        params.walkableClimb = BASE_UNIT_DIM*config.walkableClimb;      // keep less that walkableHeight (aka agent height)!
        params.tileX = (((bmin[0] + bmax[0]) / 2) - navMesh->getParams()->orig[0]) / GRID_SIZE;
        params.tileY = (((bmin[2] + bmax[2]) / 2) - navMesh->getParams()->orig[2]) / GRID_SIZE;
        rcVcopy(params.bmin, bmin);
        rcVcopy(params.bmax, bmax);
        params.cs = config.cs;
        params.ch = config.ch;
        params.tileLayer = 0;
        params.buildBvTree = true;
 
        // will hold final navmesh
        unsigned char* navData = NULL;
        int navDataSize = 0;
 
        do
        {
            // these values are checked within dtCreateNavMeshData - handle them here
            // so we have a clear error message
            if (params.nvp > DT_VERTS_PER_POLYGON)
            {
                printf("%s Invalid verts-per-polygon value!\n", tileString);
                continue;
            }
            if (params.vertCount >= 0xffff)
            {
                printf("%s Too many vertices!\n", tileString);
                continue;
            }
            if (!params.vertCount || !params.verts)
            {
                // occurs mostly when adjacent tiles have models
                // loaded but those models don't span into this tile
 
                // message is an annoyance
                //printf("%sNo vertices to build tile!\n", tileString);
                continue;
            }
            if (!params.polyCount || !params.polys ||
                TILES_PER_MAP*TILES_PER_MAP == params.polyCount)
            {
                // we have flat tiles with no actual geometry - don't build those, its useless
                // keep in mind that we do output those into debug info
                // drop tiles with only exact count - some tiles may have geometry while having less tiles
                printf("%s No polygons to build on tile!\n", tileString);
                continue;
            }
            if (!params.detailMeshes || !params.detailVerts || !params.detailTris)
            {
                printf("%s No detail mesh to build tile!\n", tileString);
                continue;
            }
 
            printf("%s Building navmesh tile...\n", tileString);
            if (!dtCreateNavMeshData(&params, &navData, &navDataSize))
            {
                printf("%s Failed building navmesh tile!\n", tileString);
                continue;
            }
 
            dtTileRef tileRef = 0;
            printf("%s Adding tile to navmesh...\n", tileString);
            // DT_TILE_FREE_DATA tells detour to unallocate memory when the tile
            // is removed via removeTile()
            dtStatus dtResult = navMesh->addTile(navData, navDataSize, DT_TILE_FREE_DATA, 0, &tileRef);
            if (!tileRef || dtResult != DT_SUCCESS)
            {
                printf("%s Failed adding tile to navmesh!\n", tileString);
                continue;
            }
 
            // file output
            char fileName[255];
            snprintf(fileName, sizeof(fileName), "mmaps/%04u_%02i_%02i.mmtile", mapID, tileY, tileX);
            FILE* file = fopen(fileName, "wb");
            if (!file)
            {
                char message[1024];
                snprintf(message, sizeof(message), "[Map %04u] Failed to open %s for writing!\n", mapID, fileName);
                perror(message);
                navMesh->removeTile(tileRef, NULL, NULL);
                continue;
            }
 
            printf("%s Writing to file...\n", tileString);
 
            // write header
            MmapTileHeader header;
            header.usesLiquids = m_terrainBuilder->usesLiquids();
            header.size = uint32(navDataSize);
            fwrite(&header, sizeof(MmapTileHeader), 1, file);
 
            // write data
            fwrite(navData, sizeof(unsigned char), navDataSize, file);
            fclose(file);
 
            // now that tile is written to disk, we can unload it
            navMesh->removeTile(tileRef, NULL, NULL);
        }
        while (0);
 
        if (m_debugOutput)
        {
            // restore padding so that the debug visualization is correct
            for (int i = 0; i < iv.polyMesh->nverts; ++i)
            {
                unsigned short* v = &iv.polyMesh->verts[i*3];
                v[0] += (unsigned short)config.borderSize;
                v[2] += (unsigned short)config.borderSize;
            }
 
            iv.generateObjFile(mapID, tileX, tileY, meshData);
            iv.writeIV(mapID, tileX, tileY);
        }
    }
 
    /**************************************************************************/
    void MapBuilder::getTileBounds(uint32 tileX, uint32 tileY, float* verts, int vertCount, float* bmin, float* bmax)
    {
        // this is for elevation
        if (verts && vertCount)
            rcCalcBounds(verts, vertCount, bmin, bmax);
        else
        {
            bmin[1] = FLT_MIN;
            bmax[1] = FLT_MAX;
        }
 
        // this is for width and depth
        bmax[0] = (32 - int(tileX)) * GRID_SIZE;
        bmax[2] = (32 - int(tileY)) * GRID_SIZE;
        bmin[0] = bmax[0] - GRID_SIZE;
        bmin[2] = bmax[2] - GRID_SIZE;
    }
 
    /**************************************************************************/
    bool MapBuilder::shouldSkipMap(uint32 mapID)
    {
        if (m_skipContinents)
            switch (mapID)
            {
                case 0:    // Eastern Kingdoms
                case 1:    // Kalimdor
                case 530:  // Outland
                case 571:  // Northrend
                case 870:  // Pandaria
                    return true;
                default:
                    break;
            }
 
        if (m_skipJunkMaps)
            switch (mapID)
            {
                case 13:    // test.wdt
                case 25:    // ScottTest.wdt
                case 29:    // Test.wdt
                case 42:    // Colin.wdt
                case 169:   // EmeraldDream.wdt (unused, and very large)
                case 451:   // development.wdt
                case 573:   // ExteriorTest.wdt
                case 597:   // CraigTest.wdt
                case 605:   // development_nonweighted.wdt
                case 606:   // QA_DVD.wdt
                case 627:   // unused.wdt
                case 651:   // ElevatorSpawnTest.wdt
                case 930:   // (UNUSED) Scenario: Alcaz Island
                case 995:   // The Depths [UNUSED]
                case 1014:  // (UNUSED) Peak of Serenity Scenario
                case 1028:  // (UNUSED) Scenario: Mogu Ruins
                case 1029:  // (UNUSED) Scenario: Mogu Crypt
                case 1049:  // (UNUSED) Scenario: Black Ox Temple
                case 1060:  // LevelDesignLand-DevOnly.wdt
                    return true;
                default:
                    if (isTransportMap(mapID))
                        return true;
                    break;
            }
 
        if (m_skipBattlegrounds)
            switch (mapID)
            {
                case 30:    // Alterac Valley
                case 37:    // Azshara Crater
                case 489:   // Warsong Gulch
                case 529:   // Arathi Basin
                case 566:   // Eye of the Storm
                case 607:   // Strand of the Ancients
                case 628:   // Isle of Conquest
                case 726:   // Twin Peaks
                case 727:   // Silvershard Mines
                case 728:   // The Battle for Gilneas (Old Map)
                case 761:   // The Battle for Gilneas
                case 968:   // Rated Eye of the Storm
                case 998:   // Temple of Kotmogu
                case 1010:  // Mists of Pandaria CTF3
                case 1101:  // DefenseOfTheAleHouseBG
                case 1105:  // Deepwind Gorge
                    return true;
                default:
                    break;
            }
 
        return false;
    }
 
    /**************************************************************************/
    bool MapBuilder::isTransportMap(uint32 mapID)
    {
        switch (mapID)
        {
            // Transport maps
            case 582:  // Transport: Rut'theran to Auberdine
            case 584:  // Transport: Menethil to Theramore
            case 586:  // Transport: Exodar to Auberdine
            case 587:  // Transport: Feathermoon Ferry
            case 588:  // Transport: Menethil to Auberdine
            case 589:  // Transport: Orgrimmar to Grom'Gol
            case 590:  // Transport: Grom'Gol to Undercity
            case 591:  // Transport: Undercity to Orgrimmar
            case 592:  // Transport: Borean Tundra Test
            case 593:  // Transport: Booty Bay to Ratchet
            case 594:  // Transport: Howling Fjord Sister Mercy (Quest)
            case 596:  // Transport: Naglfar
            case 610:  // Transport: Tirisfal to Vengeance Landing
            case 612:  // Transport: Menethil to Valgarde
            case 613:  // Transport: Orgrimmar to Warsong Hold
            case 614:  // Transport: Stormwind to Valiance Keep
            case 620:  // Transport: Moa'ki to Unu'pe
            case 621:  // Transport: Moa'ki to Kamagua
            case 622:  // Transport: Orgrim's Hammer
            case 623:  // Transport: The Skybreaker
            case 641:  // Transport: Alliance Airship BG
            case 642:  // Transport: HordeAirshipBG
            case 647:  // Transport: Orgrimmar to Thunder Bluff
            case 662:  // Transport: Alliance Vashj'ir Ship
            case 672:  // Transport: The Skybreaker (Icecrown Citadel Raid)
            case 673:  // Transport: Orgrim's Hammer (Icecrown Citadel Raid)
            case 674:  // Transport: Ship to Vashj'ir
            case 712:  // Transport: The Skybreaker (IC Dungeon)
            case 713:  // Transport: Orgrim's Hammer (IC Dungeon)
            case 718:  // Transport: The Mighty Wind (Icecrown Citadel Raid)
            case 738:  // Ship to Vashj'ir (Orgrimmar -> Vashj'ir)
            case 739:  // Vashj'ir Sub - Horde
            case 740:  // Vashj'ir Sub - Alliance
            case 741:  // Twilight Highlands Horde Transport
            case 742:  // Vashj'ir Sub - Horde - Circling Abyssal Maw
            case 743:  // Vashj'ir Sub - Alliance circling Abyssal Maw
            case 746:  // Uldum Phase Oasis
            case 747:  // Transport: Deepholm Gunship
            case 748:  // Transport: Onyxia/Nefarian Elevator
            case 749:  // Transport: Gilneas Moving Gunship
            case 750:  // Transport: Gilneas Static Gunship
            case 762:  // Twilight Highlands Zeppelin 1
            case 763:  // Twilight Highlands Zeppelin 2
            case 765:  // Krazzworks Attack Zeppelin
            case 766:  // Transport: Gilneas Moving Gunship 02
            case 767:  // Transport: Gilneas Moving Gunship 03
            case 1113: // Transport: DarkmoonCarousel
            case 1132: // Transport218599 - The Skybag (Brawl'gar Arena)
            case 1133: // Transport218600 - Zandalari Ship (Mogu Island)
            case 1172: // Transport_Siege_of_Orgrimmar_Alliance - Transport: Siege of Orgrimmar (Alliance)
            case 1173: // Transport_Siege_of_Orgrimmar_Horde - Transport: Siege of Orgrimmar (Horde)
                return true;
            default:
                return false;
        }
    }
 
    /**************************************************************************/
    bool MapBuilder::shouldSkipTile(uint32 mapID, uint32 tileX, uint32 tileY)
    {
        char fileName[255];
        snprintf(fileName, sizeof(fileName), "mmaps/%04u_%02i_%02i.mmtile", mapID, tileY, tileX);
        FILE* file = fopen(fileName, "rb");
        if (!file)
            return false;
 
        MmapTileHeader header;
        int count = fread(&header, sizeof(MmapTileHeader), 1, file);
        fclose(file);
        if (count != 1)
            return false;
 
        if (header.mmapMagic != MMAP_MAGIC || header.dtVersion != uint32(DT_NAVMESH_VERSION))
            return false;
 
        if (header.mmapVersion != MMAP_VERSION)
            return false;
 
        return true;
    }
 
}