Legends-of-Azeroth-Pandaria-5.4.8

1
/*
2
* This file is part of the Pandaria 5.4.8 Project. See THANKS file for Copyright information
3
*
4
* This program is free software; you can redistribute it and/or modify it
5
* under the terms of the GNU General Public License as published by the
6
* Free Software Foundation; either version 2 of the License, or (at your
7
* option) any later version.
8
*
9
* This program is distributed in the hope that it will be useful, but WITHOUT
10
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
12
* more details.
13
*
14
* You should have received a copy of the GNU General Public License along
15
* with this program. If not, see <http://www.gnu.org/licenses/>.
16
*/
17

18
#include "PathCommon.h"
19
#include "MapBuilder.h"
20
#include "MapDefines.h"
21
#include "MapTree.h"
22
#include "ModelInstance.h"
23
#include "DetourNavMeshBuilder.h"
24
#include "DetourNavMesh.h"
25
#include "DetourCommon.h"
26
#include "DisableMgr.h"
27
#include "SharedDefines.h"
28

29
bool DisableMgr::IsDisabledFor(DisableType type, uint32 entry, Unit const* unit, uint8 flags) { return false; }
30

31
#define MMAP_MAGIC 0x4d4d4150   // 'MMAP'
32
#define MMAP_VERSION 7
33

34
namespace MMAP
35
{
36
    TileBuilder::TileBuilder(MapBuilder* mapBuilder, bool skipLiquid, bool bigBaseUnit, bool debugOutput) :
37
        m_bigBaseUnit(bigBaseUnit),
38
        m_debugOutput(debugOutput),
39
        m_mapBuilder(mapBuilder),
40
        m_terrainBuilder(nullptr),
41
        m_workerThread(&TileBuilder::WorkerThread, this),
42
        m_rcContext(nullptr)
43
    {
44
        m_terrainBuilder = new TerrainBuilder(skipLiquid);
45
        m_rcContext = new rcContext(false);
46
    }
47

48
    TileBuilder::~TileBuilder()
49
    {
50
        WaitCompletion();
51

52
        delete m_terrainBuilder;
53
        delete m_rcContext;
54
    }
55

56
    void TileBuilder::WaitCompletion()
57
    {
58
        if (m_workerThread.joinable())
59
            m_workerThread.join();
60
    }
61

62
    MapBuilder::MapBuilder(Optional<float> maxWalkableAngle, Optional<float> maxWalkableAngleNotSteep, bool skipLiquid,
63
        bool skipContinents, bool skipJunkMaps, bool skipBattlegrounds, bool skipArenas, bool skipDungeons, bool skipTransports,
64
        bool debugOutput, bool bigBaseUnit, int mapid, const char* offMeshFilePath, unsigned int threads) :
65
        m_terrainBuilder     (nullptr),
66
        m_debugOutput        (debugOutput),
67
        m_offMeshFilePath    (offMeshFilePath),
68
        m_threads            (threads),
69
        m_skipContinents     (skipContinents),
70
        m_skipJunkMaps       (skipJunkMaps),
71
        m_skipBattlegrounds  (skipBattlegrounds),
72
        m_skipArenas         (skipArenas),
73
        m_skipDungeons       (skipDungeons),
74
        m_skipTransports     (skipTransports),
75
        m_skipLiquid         (skipLiquid),
76
        m_maxWalkableAngle   (maxWalkableAngle),
77
        m_maxWalkableAngleNotSteep (maxWalkableAngleNotSteep),
78
        m_bigBaseUnit        (bigBaseUnit),
79
        m_mapid              (mapid),
80
        m_totalTiles         (0u),
81
        m_totalTilesProcessed(0u),        
82
        m_rcContext          (nullptr),
83
        _cancelationToken    (false)
84
    {
85
        m_terrainBuilder = new TerrainBuilder(skipLiquid);
86

87
        m_rcContext = new rcContext(false);
88

89
        // At least 1 thread is needed
90
        m_threads = std::max(1u, m_threads);
91

92
        discoverTiles();
93
    }
94

95
    /**************************************************************************/
96
    MapBuilder::~MapBuilder()
97
    {
98
        _cancelationToken = true;
99

100
        _queue.Cancel();
101

102
        for (TileList::iterator it = m_tiles.begin(); it != m_tiles.end(); ++it)
103
        {
104
            (*it).m_tiles->clear();
105
            delete (*it).m_tiles;
106
        }
107

108
        delete m_terrainBuilder;
109
        delete m_rcContext;
110
    }
111

112
    /**************************************************************************/
113
    void MapBuilder::discoverTiles()
114
    {
115
        std::vector<std::string> files;
116
        uint32 mapID, tileX, tileY, tileID, count = 0;
117
        char filter[13];
118

119
        printf("Discovering maps... ");
120
        getDirContents(files, "maps");
121
        for (uint32 i = 0; i < files.size(); ++i)
122
        {
123
            mapID = uint32(atoi(files[i].substr(0,4).c_str()));
124
            if (std::find(m_tiles.begin(), m_tiles.end(), mapID) == m_tiles.end())
125
            {
126
                m_tiles.emplace_back(MapTiles(mapID, new std::set<uint32>));
127
                count++;
128
            }
129
        }
130

131
        files.clear();
132
        getDirContents(files, "vmaps", "*.vmtree");
133
        for (uint32 i = 0; i < files.size(); ++i)
134
        {
135
            mapID = uint32(atoi(files[i].substr(0,4).c_str()));
136
            if (std::find(m_tiles.begin(), m_tiles.end(), mapID) == m_tiles.end())
137
            {
138
                m_tiles.emplace_back(MapTiles(mapID, new std::set<uint32>));
139
                count++;
140
            }
141
        }
142
        // for (auto&& map : transportMaps)
143
        // {
144
        //     mapID = map.first;
145
        //     if (std::find(m_tiles.begin(), m_tiles.end(), mapID) == m_tiles.end())
146
        //     {
147
        //         m_tiles.emplace_back(MapTiles(mapID, new std::set<uint32>));
148
        //         count++;
149
        //     }
150
        // }
151
        printf("found %u.\n", count);
152

153
        count = 0;
154
        printf("Discovering tiles... ");
155
        for (TileList::iterator itr = m_tiles.begin(); itr != m_tiles.end(); ++itr)
156
        {
157
            std::set<uint32>* tiles = (*itr).m_tiles;
158
            mapID = (*itr).m_mapId;
159

160
            sprintf(filter, "%04u*.vmtile", mapID);
161
            files.clear();
162
            getDirContents(files, "vmaps", filter);
163
            for (uint32 i = 0; i < files.size(); ++i)
164
            {
165
                tileX = uint32(atoi(files[i].substr(8,2).c_str()));
166
                tileY = uint32(atoi(files[i].substr(5,2).c_str()));
167
                tileID = StaticMapTree::packTileID(tileY, tileX);
168

169
                tiles->insert(tileID);
170
                count++;
171
            }
172

173
            sprintf(filter, "%04u*", mapID);
174
            files.clear();
175
            getDirContents(files, "maps", filter);
176
            for (uint32 i = 0; i < files.size(); ++i)
177
            {
178
                tileY = uint32(atoi(files[i].substr(5,2).c_str()));
179
                tileX = uint32(atoi(files[i].substr(8,2).c_str()));
180
                tileID = StaticMapTree::packTileID(tileX, tileY);
181

182
                if (tiles->insert(tileID).second)
183
                    count++;
184
            }
185

186
            // make sure we process maps which don't have tiles
187
            if (tiles->empty())
188
            {
189
                // convert coord bounds to grid bounds
190
                uint32 minX, minY, maxX, maxY;
191
                getGridBounds(mapID, minX, minY, maxX, maxY);
192

193
                // add all tiles within bounds to tile list.
194
                for (uint32 i = minX; i <= maxX; ++i)
195
                    for (uint32 j = minY; j <= maxY; ++j)
196
                        if (tiles->insert(StaticMapTree::packTileID(i, j)).second)
197
                            count++;                
198
            }
199

200
            // // For transport maps we're only interested in cells covering coordinates -1 to 1, which happen to be 31 and 32 when offset
201
            // if (isTransportMap(mapID))
202
            //     for (uint32 x = 31; x <= 32; ++x)
203
            //         for (uint32 y = 31; y <= 32; ++y)
204
            //             if (tiles->insert(StaticMapTree::packTileID(x, y)).second)
205
            //                 count++;
206
        }
207
        printf("found %u.\n\n", count);
208

209
        // Calculate tiles to process in total
210
        for (TileList::iterator it = m_tiles.begin(); it != m_tiles.end(); ++it)
211
        {
212
            if (!shouldSkipMap(it->m_mapId))
213
                m_totalTiles += it->m_tiles->size();
214
        }
215

216
    }
217

218
    /**************************************************************************/
219
    std::set<uint32>* MapBuilder::getTileList(uint32 mapID)
220
    {
221
        TileList::iterator itr = std::find(m_tiles.begin(), m_tiles.end(), mapID);
222
        if (itr != m_tiles.end())
223
            return (*itr).m_tiles;
224

225
        std::set<uint32>* tiles = new std::set<uint32>();
226
        m_tiles.emplace_back(MapTiles(mapID, tiles));
227
        return tiles;
228
    }
229

230
    /**************************************************************************/
231

232
    void TileBuilder::WorkerThread()
233
    {
234
        while (1)
235
        {
236
            TileInfo tileInfo;
237

238
            m_mapBuilder->_queue.WaitAndPop(tileInfo);
239

240
            if (m_mapBuilder->_cancelationToken)
241
                return;
242

243
            dtNavMesh* navMesh = dtAllocNavMesh();
244
            if (!navMesh->init(&tileInfo.m_navMeshParams))
245
            {
246
                printf("[Map %03i] Failed creating navmesh for tile %i,%i !\n", tileInfo.m_mapId, tileInfo.m_tileX, tileInfo.m_tileY);
247
                dtFreeNavMesh(navMesh);
248
                return;
249
            }
250

251
            buildTile(tileInfo.m_mapId, tileInfo.m_tileX, tileInfo.m_tileY, navMesh);
252

253
            dtFreeNavMesh(navMesh);
254
        }
255
    }
256

257
    void MapBuilder::buildMaps(Optional<uint32> mapID)
258
    {
259
        printf("Using %u threads to generate mmaps\n", m_threads);
260

261
        for (unsigned int i = 0; i < m_threads; ++i)
262
        {
263
            m_tileBuilders.push_back(new TileBuilder(this, m_skipLiquid, m_bigBaseUnit, m_debugOutput));
264
        }
265

266
        if (mapID)
267
        {
268
            buildMap(*mapID);
269
        }
270
        else
271
        {
272
            // Build all maps if no map id has been specified
273
            for (TileList::iterator it = m_tiles.begin(); it != m_tiles.end(); ++it)
274
            {
275
                if (!shouldSkipMap(it->m_mapId))
276
                    buildMap(it->m_mapId);
277
            }
278
        }
279

280
        while (!_queue.Empty())
281
        {
282
            std::this_thread::sleep_for(std::chrono::milliseconds(1000));
283
        }
284

285
        _cancelationToken = true;
286

287
        _queue.Cancel();
288

289
        for (auto& builder : m_tileBuilders)
290
            delete builder;
291

292
        m_tileBuilders.clear();
293
    }
294

295
    /**************************************************************************/
296
    void MapBuilder::getGridBounds(uint32 mapID, uint32 &minX, uint32 &minY, uint32 &maxX, uint32 &maxY)
297
    {
298
        // min and max are initialized to invalid values so the caller iterating the [min, max] range
299
        // will never enter the loop unless valid min/max values are found
300
        maxX = 0;
301
        maxY = 0;
302
        minX = std::numeric_limits<uint32>::max();
303
        minY = std::numeric_limits<uint32>::max();
304

305
        float bmin[3] = { 0, 0, 0 };
306
        float bmax[3] = { 0, 0, 0 };
307
        float lmin[3] = { 0, 0, 0 };
308
        float lmax[3] = { 0, 0, 0 };
309
        MeshData meshData;
310

311
        // make sure we process maps which don't have tiles
312
        // initialize the static tree, which loads WDT models
313
        if (!m_terrainBuilder->loadVMap(mapID, 64, 64, meshData))
314
            return;
315

316
        // get the coord bounds of the model data
317
        if (meshData.solidVerts.size() + meshData.liquidVerts.size() == 0)
318
            return;
319

320
        // get the coord bounds of the model data
321
        if (meshData.solidVerts.size() && meshData.liquidVerts.size())
322
        {
323
            rcCalcBounds(meshData.solidVerts.getCArray(), meshData.solidVerts.size() / 3, bmin, bmax);
324
            rcCalcBounds(meshData.liquidVerts.getCArray(), meshData.liquidVerts.size() / 3, lmin, lmax);
325
            rcVmin(bmin, lmin);
326
            rcVmax(bmax, lmax);
327
        }
328
        else if (meshData.solidVerts.size())
329
            rcCalcBounds(meshData.solidVerts.getCArray(), meshData.solidVerts.size() / 3, bmin, bmax);
330
        else
331
            rcCalcBounds(meshData.liquidVerts.getCArray(), meshData.liquidVerts.size() / 3, lmin, lmax);
332

333
        // convert coord bounds to grid bounds
334
        maxX = 32 - bmin[0] / GRID_SIZE;
335
        maxY = 32 - bmin[2] / GRID_SIZE;
336
        minX = 32 - bmax[0] / GRID_SIZE;
337
        minY = 32 - bmax[2] / GRID_SIZE;
338
    }
339

340
    void MapBuilder::buildMeshFromFile(char* name)
341
    {
342
        FILE* file = fopen(name, "rb");
343
        if (!file)
344
            return;
345

346
        printf("Building mesh from file\n");
347
        int tileX, tileY, mapId;
348
        if (fread(&mapId, sizeof(int), 1, file) != 1)
349
        {
350
            fclose(file);
351
            return;
352
        }
353
        if (fread(&tileX, sizeof(int), 1, file) != 1)
354
        {
355
            fclose(file);
356
            return;
357
        }
358
        if (fread(&tileY, sizeof(int), 1, file) != 1)
359
        {
360
            fclose(file);
361
            return;
362
        }
363

364
        dtNavMesh* navMesh = nullptr;
365
        buildNavMesh(mapId, navMesh);
366
        if (!navMesh)
367
        {
368
            printf("Failed creating navmesh!              \n");
369
            fclose(file);
370
            return;
371
        }
372

373
        uint32 verticesCount, indicesCount;
374
        if (fread(&verticesCount, sizeof(uint32), 1, file) != 1)
375
        {
376
            fclose(file);
377
            return;
378
        }
379

380
        if (fread(&indicesCount, sizeof(uint32), 1, file) != 1)
381
        {
382
            fclose(file);
383
            return;
384
        }
385

386
        float* verts = new float[verticesCount];
387
        int* inds = new int[indicesCount];
388

389
        if (fread(verts, sizeof(float), verticesCount, file) != verticesCount)
390
        {
391
            fclose(file);
392
            delete[] verts;
393
            delete[] inds;
394
            return;
395
        }
396

397
        if (fread(inds, sizeof(int), indicesCount, file) != indicesCount)
398
        {
399
            fclose(file);
400
            delete[] verts;
401
            delete[] inds;
402
            return;
403
        }
404

405
        MeshData data;
406

407
        for (uint32 i = 0; i < verticesCount; ++i)
408
            data.solidVerts.append(verts[i]);
409
        delete[] verts;
410

411
        for (uint32 i = 0; i < indicesCount; ++i)
412
            data.solidTris.append(inds[i]);
413
        delete[] inds;
414

415
        TerrainBuilder::cleanVertices(data.solidVerts, data.solidTris);
416
        // get bounds of current tile
417
        float bmin[3], bmax[3];
418
        getTileBounds(tileX, tileY, data.solidVerts.getCArray(), data.solidVerts.size() / 3, bmin, bmax);
419

420
        // build navmesh tile
421
        // build navmesh tile
422
        TileBuilder tileBuilder = TileBuilder(this, m_skipLiquid, m_bigBaseUnit, m_debugOutput);
423
        tileBuilder.buildMoveMapTile(mapId, tileX, tileY, data, bmin, bmax, navMesh);        
424
        //buildMoveMapTile(mapId, tileX, tileY, data, bmin, bmax, navMesh);
425
        fclose(file);
426
    }
427

428
    /**************************************************************************/
429
    void MapBuilder::buildSingleTile(uint32 mapID, uint32 tileX, uint32 tileY)
430
    {
431
        dtNavMesh* navMesh = nullptr;
432
        buildNavMesh(mapID, navMesh);
433
        if (!navMesh)
434
        {
435
            printf("Failed creating navmesh!              \n");
436
            return;
437
        }
438

439
        TileBuilder tileBuilder = TileBuilder(this, m_skipLiquid, m_bigBaseUnit, m_debugOutput);
440
        tileBuilder.buildTile(mapID, tileX, tileY, navMesh);
441
        //buildTile(mapID, tileX, tileY, navMesh);
442
        dtFreeNavMesh(navMesh);
443

444
        _cancelationToken = true;
445

446
        _queue.Cancel();        
447
    }
448

449
    /**************************************************************************/
450
    void MapBuilder::buildMap(uint32 mapID)
451
    {
452
        std::set<uint32>* tiles = getTileList(mapID);
453

454
        if (!tiles->empty())
455
        {
456
            // build navMesh
457
            dtNavMesh* navMesh = nullptr;
458
            buildNavMesh(mapID, navMesh);
459
            if (!navMesh)
460
            {
461
                printf("[Map %04i] Failed creating navmesh!\n", mapID);
462
                return;
463
            }
464

465
            // now start building mmtiles for each tile
466
            printf("[Map %04i] We have %u tiles.                          \n", mapID, (unsigned int)tiles->size());
467
            for (std::set<uint32>::iterator it = tiles->begin(); it != tiles->end(); ++it)
468
            {
469
                uint32 tileX, tileY;
470

471
                // unpack tile coords
472
                StaticMapTree::unpackTileID((*it), tileX, tileY);
473

474
                TileInfo tileInfo;
475
                tileInfo.m_mapId = mapID;
476
                tileInfo.m_tileX = tileX;
477
                tileInfo.m_tileY = tileY;
478
                memcpy(&tileInfo.m_navMeshParams, navMesh->getParams(), sizeof(dtNavMeshParams));
479
                _queue.Push(tileInfo);
480
            }
481

482
            dtFreeNavMesh(navMesh);
483
        }
484

485
        printf("[Map %04i] Complete!\n", mapID);
486
    }
487

488
    /**************************************************************************/
489
    void TileBuilder::buildTile(uint32 mapID, uint32 tileX, uint32 tileY, dtNavMesh* navMesh)
490
    {
491
        if(shouldSkipTile(mapID, tileX, tileY))
492
        {
493
            ++m_mapBuilder->m_totalTilesProcessed;
494
            return;
495
        }
496

497
        printf("%u%% [Map %04i] Building tile [%02u,%02u]\n", m_mapBuilder->currentPercentageDone(), mapID, tileX, tileY);
498

499
        MeshData meshData;
500

501
        // get heightmap data
502
        m_terrainBuilder->loadMap(mapID, tileX, tileY, meshData);
503

504
        // get model data
505
        m_terrainBuilder->loadVMap(mapID, tileY, tileX, meshData);
506

507
        // if there is no data, give up now
508
        if (!meshData.solidVerts.size() && !meshData.liquidVerts.size())
509
        {
510
            ++m_mapBuilder->m_totalTilesProcessed;
511
            return;
512
        }
513

514
        // remove unused vertices
515
        TerrainBuilder::cleanVertices(meshData.solidVerts, meshData.solidTris);
516
        TerrainBuilder::cleanVertices(meshData.liquidVerts, meshData.liquidTris);
517

518
        // gather all mesh data for final data check, and bounds calculation
519
        G3D::Array<float> allVerts;
520
        allVerts.append(meshData.liquidVerts);
521
        allVerts.append(meshData.solidVerts);
522

523
        if (!allVerts.size())
524
        {
525
            ++m_mapBuilder->m_totalTilesProcessed;
526
            return;
527
        }
528

529
        // get bounds of current tile
530
        float bmin[3], bmax[3];
531
        m_mapBuilder->getTileBounds(tileX, tileY, allVerts.getCArray(), allVerts.size() / 3, bmin, bmax);
532

533
        m_terrainBuilder->loadOffMeshConnections(mapID, tileX, tileY, meshData, m_mapBuilder->m_offMeshFilePath);
534

535
        // build navmesh tile
536
        buildMoveMapTile(mapID, tileX, tileY, meshData, bmin, bmax, navMesh);
537

538
        ++m_mapBuilder->m_totalTilesProcessed;
539
    }
540

541
    /**************************************************************************/
542
    void MapBuilder::buildNavMesh(uint32 mapID, dtNavMesh* &navMesh)
543
    {
544
        std::set<uint32>* tiles = getTileList(mapID);
545

546
        // old code for non-statically assigned bitmask sizes:
547
        ///*** calculate number of bits needed to store tiles & polys ***/
548
        //int tileBits = dtIlog2(dtNextPow2(tiles->size()));
549
        //if (tileBits < 1) tileBits = 1;                                     // need at least one bit!
550
        //int polyBits = sizeof(dtPolyRef)*8 - SALT_MIN_BITS - tileBits;
551

552
        int polyBits = DT_POLY_BITS;
553

554
        int maxTiles = tiles->size();
555
        int maxPolysPerTile = 1 << polyBits;
556

557
        /***          calculate bounds of map         ***/
558

559
        uint32 tileXMin = 64, tileYMin = 64, tileXMax = 0, tileYMax = 0, tileX, tileY;
560
        for (std::set<uint32>::iterator it = tiles->begin(); it != tiles->end(); ++it)
561
        {
562
            StaticMapTree::unpackTileID(*it, tileX, tileY);
563

564
            if (tileX > tileXMax)
565
                tileXMax = tileX;
566
            else if (tileX < tileXMin)
567
                tileXMin = tileX;
568

569
            if (tileY > tileYMax)
570
                tileYMax = tileY;
571
            else if (tileY < tileYMin)
572
                tileYMin = tileY;
573
        }
574

575
        // use Max because '32 - tileX' is negative for values over 32
576
        float bmin[3], bmax[3];
577
        getTileBounds(tileXMax, tileYMax, nullptr, 0, bmin, bmax);
578

579
        /***       now create the navmesh       ***/
580

581
        // navmesh creation params
582
        dtNavMeshParams navMeshParams;
583
        memset(&navMeshParams, 0, sizeof(dtNavMeshParams));
584
        navMeshParams.tileWidth = GRID_SIZE;
585
        navMeshParams.tileHeight = GRID_SIZE;
586
        rcVcopy(navMeshParams.orig, bmin);
587
        navMeshParams.maxTiles = maxTiles;
588
        navMeshParams.maxPolys = maxPolysPerTile;
589

590
        navMesh = dtAllocNavMesh();
591
        printf("[Map %04i] Creating navMesh...\n", mapID);
592
        if (!navMesh->init(&navMeshParams))
593
        {
594
            printf("[Map %04i] Failed creating navmesh!                \n", mapID);
595
            return;
596
        }
597

598
        char fileName[25];
599
        sprintf(fileName, "mmaps/%04u.mmap", mapID);
600

601
        FILE* file = fopen(fileName, "wb");
602
        if (!file)
603
        {
604
            dtFreeNavMesh(navMesh);
605
            char message[1024];
606
            sprintf(message, "[Map %04i] Failed to open %s for writing!\n", mapID, fileName);
607
            perror(message);
608
            return;
609
        }
610

611
        // now that we know navMesh params are valid, we can write them to file
612
        fwrite(&navMeshParams, sizeof(dtNavMeshParams), 1, file);
613
        fclose(file);
614
    }
615

616
    /**************************************************************************/
617
    void TileBuilder::buildMoveMapTile(uint32 mapID, uint32 tileX, uint32 tileY,
618
        MeshData &meshData, float bmin[3], float bmax[3],
619
        dtNavMesh* navMesh)
620
    {
621
        // console output
622
        char tileString[21];
623
        sprintf(tileString, "[Map %04i] [%02i,%02i]: ", mapID, tileX, tileY);
624
        printf("%s Building movemap tiles...\n", tileString);
625

626
        IntermediateValues iv;
627

628
        float* tVerts = meshData.solidVerts.getCArray();
629
        int tVertCount = meshData.solidVerts.size() / 3;
630
        int* tTris = meshData.solidTris.getCArray();
631
        int tTriCount = meshData.solidTris.size() / 3;
632

633
        float* lVerts = meshData.liquidVerts.getCArray();
634
        int lVertCount = meshData.liquidVerts.size() / 3;
635
        int* lTris = meshData.liquidTris.getCArray();
636
        int lTriCount = meshData.liquidTris.size() / 3;
637
        uint8* lTriFlags = meshData.liquidType.getCArray();
638

639
        const TileConfig tileConfig = TileConfig(m_bigBaseUnit);
640
        int TILES_PER_MAP = tileConfig.TILES_PER_MAP;
641
        float BASE_UNIT_DIM = tileConfig.BASE_UNIT_DIM;
642
        rcConfig config = m_mapBuilder->GetMapSpecificConfig(mapID, bmin, bmax, tileConfig);
643

644
        // this sets the dimensions of the heightfield - should maybe happen before border padding
645
        rcCalcGridSize(config.bmin, config.bmax, config.cs, &config.width, &config.height);
646

647
        // allocate subregions : tiles
648
        Tile* tiles = new Tile[TILES_PER_MAP * TILES_PER_MAP];
649

650
        // Initialize per tile config.
651
        rcConfig tileCfg = config;
652
        tileCfg.width = config.tileSize + config.borderSize*2;
653
        tileCfg.height = config.tileSize + config.borderSize*2;
654

655
        // merge per tile poly and detail meshes
656
        rcPolyMesh** pmmerge = new rcPolyMesh*[TILES_PER_MAP * TILES_PER_MAP];
657
        rcPolyMeshDetail** dmmerge = new rcPolyMeshDetail*[TILES_PER_MAP * TILES_PER_MAP];
658
        int nmerge = 0;
659
        // build all tiles
660
        for (int y = 0; y < TILES_PER_MAP; ++y)
661
        {
662
            for (int x = 0; x < TILES_PER_MAP; ++x)
663
            {
664
                Tile& tile = tiles[x + y * TILES_PER_MAP];
665

666
                // Calculate the per tile bounding box.
667
                tileCfg.bmin[0] = config.bmin[0] + x * float(config.tileSize * config.cs);
668
                tileCfg.bmin[2] = config.bmin[2] + y * float(config.tileSize * config.cs);
669
                tileCfg.bmax[0] = config.bmin[0] + (x + 1) * float(config.tileSize * config.cs);
670
                tileCfg.bmax[2] = config.bmin[2] + (y + 1) * float(config.tileSize * config.cs);
671

672
                tileCfg.bmin[0] -= tileCfg.borderSize * tileCfg.cs;
673
                tileCfg.bmin[2] -= tileCfg.borderSize * tileCfg.cs;
674
                tileCfg.bmax[0] += tileCfg.borderSize * tileCfg.cs;
675
                tileCfg.bmax[2] += tileCfg.borderSize * tileCfg.cs;
676

677
                // build heightfield
678
                tile.solid = rcAllocHeightfield();
679
                if (!tile.solid || !rcCreateHeightfield(m_rcContext, *tile.solid, tileCfg.width, tileCfg.height, tileCfg.bmin, tileCfg.bmax, tileCfg.cs, tileCfg.ch))
680
                {
681
                    printf("%s Failed building heightfield!            \n", tileString);
682
                    continue;
683
                }
684

685
                // mark all walkable tiles, both liquids and solids
686

687
                /* we want to have triangles with slope less than walkableSlopeAngleNotSteep (<= 55) to have NAV_AREA_GROUND
688
                 * and with slope between walkableSlopeAngleNotSteep and walkableSlopeAngle (55 < .. <= 70) to have NAV_AREA_GROUND_STEEP.
689
                 * we achieve this using recast API: memset everything to NAV_AREA_GROUND_STEEP, call rcClearUnwalkableTriangles with 70 so
690
                 * any area above that will get RC_NULL_AREA (unwalkable), then call rcMarkWalkableTriangles with 55 to set NAV_AREA_GROUND
691
                 * on anything below 55 . Players and idle Creatures can use NAV_AREA_GROUND, while Creatures in combat can use NAV_AREA_GROUND_STEEP.
692
                 */
693
                unsigned char* triFlags = new unsigned char[tTriCount];
694
                memset(triFlags, NAV_AREA_GROUND_STEEP, tTriCount*sizeof(unsigned char));
695
                rcClearUnwalkableTriangles(m_rcContext, tileCfg.walkableSlopeAngle, tVerts, tVertCount, tTris, tTriCount, triFlags);
696
                rcMarkWalkableTriangles(m_rcContext, tileCfg.walkableSlopeAngleNotSteep, tVerts, tVertCount, tTris, tTriCount, triFlags, NAV_AREA_GROUND);
697
                rcRasterizeTriangles(m_rcContext, tVerts, tVertCount, tTris, triFlags, tTriCount, *tile.solid, config.walkableClimb);
698
                delete[] triFlags;
699

700
                rcFilterLowHangingWalkableObstacles(m_rcContext, config.walkableClimb, *tile.solid);
701
                rcFilterLedgeSpans(m_rcContext, tileCfg.walkableHeight, tileCfg.walkableClimb, *tile.solid);
702
                rcFilterWalkableLowHeightSpans(m_rcContext, tileCfg.walkableHeight, *tile.solid);
703

704
                // add liquid triangles
705
                rcRasterizeTriangles(m_rcContext, lVerts, lVertCount, lTris, lTriFlags, lTriCount, *tile.solid, config.walkableClimb);
706

707
                // compact heightfield spans
708
                tile.chf = rcAllocCompactHeightfield();
709
                if (!tile.chf || !rcBuildCompactHeightfield(m_rcContext, tileCfg.walkableHeight, tileCfg.walkableClimb, *tile.solid, *tile.chf))
710
                {
711
                    printf("%s Failed compacting heightfield!            \n", tileString);
712
                    continue;
713
                }
714

715
                // build polymesh intermediates
716
                if (!rcErodeWalkableArea(m_rcContext, config.walkableRadius, *tile.chf))
717
                {
718
                    printf("%s Failed eroding area!                    \n", tileString);
719
                    continue;
720
                }
721

722
                if (!rcMedianFilterWalkableArea(m_rcContext, *tile.chf))
723
                {
724
                    printf("%s Failed filtering area!                  \n", tileString);
725
                    continue;
726
                }
727

728
                if (!rcBuildDistanceField(m_rcContext, *tile.chf))
729
                {
730
                    printf("%s Failed building distance field!         \n", tileString);
731
                    continue;
732
                }
733

734
                if (!rcBuildRegions(m_rcContext, *tile.chf, tileCfg.borderSize, tileCfg.minRegionArea, tileCfg.mergeRegionArea))
735
                {
736
                    printf("%s Failed building regions!                \n", tileString);
737
                    continue;
738
                }
739

740
                tile.cset = rcAllocContourSet();
741
                if (!tile.cset || !rcBuildContours(m_rcContext, *tile.chf, tileCfg.maxSimplificationError, tileCfg.maxEdgeLen, *tile.cset))
742
                {
743
                    printf("%s Failed building contours!               \n", tileString);
744
                    continue;
745
                }
746

747
                // build polymesh
748
                tile.pmesh = rcAllocPolyMesh();
749
                if (!tile.pmesh || !rcBuildPolyMesh(m_rcContext, *tile.cset, tileCfg.maxVertsPerPoly, *tile.pmesh))
750
                {
751
                    printf("%s Failed building polymesh!               \n", tileString);
752
                    continue;
753
                }
754

755
                tile.dmesh = rcAllocPolyMeshDetail();
756
                if (!tile.dmesh || !rcBuildPolyMeshDetail(m_rcContext, *tile.pmesh, *tile.chf, tileCfg.detailSampleDist, tileCfg.detailSampleMaxError, *tile.dmesh))
757
                {
758
                    printf("%s Failed building polymesh detail!        \n", tileString);
759
                    continue;
760
                }
761

762
                // free those up
763
                // we may want to keep them in the future for debug
764
                // but right now, we don't have the code to merge them
765
                rcFreeHeightField(tile.solid);
766
                tile.solid = nullptr;
767
                rcFreeCompactHeightfield(tile.chf);
768
                tile.chf = nullptr;
769
                rcFreeContourSet(tile.cset);
770
                tile.cset = nullptr;
771

772
                pmmerge[nmerge] = tile.pmesh;
773
                dmmerge[nmerge] = tile.dmesh;
774
                nmerge++;
775
            }
776
        }
777

778
        iv.polyMesh = rcAllocPolyMesh();
779
        if (!iv.polyMesh)
780
        {
781
            printf("%s alloc iv.polyMesh FIALED!\n", tileString);
782
            delete[] pmmerge;
783
            delete[] dmmerge;
784
            delete[] tiles;
785
            return;
786
        }
787
        rcMergePolyMeshes(m_rcContext, pmmerge, nmerge, *iv.polyMesh);
788

789
        iv.polyMeshDetail = rcAllocPolyMeshDetail();
790
        if (!iv.polyMeshDetail)
791
        {
792
            printf("%s alloc m_dmesh FIALED!\n", tileString);
793
            delete[] pmmerge;
794
            delete[] dmmerge;
795
            delete[] tiles;
796
            return;
797
        }
798
        rcMergePolyMeshDetails(m_rcContext, dmmerge, nmerge, *iv.polyMeshDetail);
799

800
        // free things up
801
        delete[] pmmerge;
802
        delete[] dmmerge;
803
        delete[] tiles;
804

805
        // set polygons as walkable
806
        // TODO: special flags for DYNAMIC polygons, ie surfaces that can be turned on and off
807
        for (int i = 0; i < iv.polyMesh->npolys; ++i)
808
        {
809
            if (uint8 area = iv.polyMesh->areas[i] & NAV_AREA_ALL_MASK)
810
            {
811
                if (area >= NAV_AREA_MIN_VALUE)
812
                    iv.polyMesh->flags[i] = 1 << (NAV_AREA_MAX_VALUE - area);
813
                else
814
                    iv.polyMesh->flags[i] = NAV_GROUND; // TODO: these will be dynamic in future
815
            }
816
        }
817

818
        // setup mesh parameters
819
        dtNavMeshCreateParams params;
820
        memset(&params, 0, sizeof(params));
821
        params.verts = iv.polyMesh->verts;
822
        params.vertCount = iv.polyMesh->nverts;
823
        params.polys = iv.polyMesh->polys;
824
        params.polyAreas = iv.polyMesh->areas;
825
        params.polyFlags = iv.polyMesh->flags;
826
        params.polyCount = iv.polyMesh->npolys;
827
        params.nvp = iv.polyMesh->nvp;
828
        params.detailMeshes = iv.polyMeshDetail->meshes;
829
        params.detailVerts = iv.polyMeshDetail->verts;
830
        params.detailVertsCount = iv.polyMeshDetail->nverts;
831
        params.detailTris = iv.polyMeshDetail->tris;
832
        params.detailTriCount = iv.polyMeshDetail->ntris;
833

834
        params.offMeshConVerts = meshData.offMeshConnections.getCArray();
835
        params.offMeshConCount = meshData.offMeshConnections.size()/6;
836
        params.offMeshConRad = meshData.offMeshConnectionRads.getCArray();
837
        params.offMeshConDir = meshData.offMeshConnectionDirs.getCArray();
838
        params.offMeshConAreas = meshData.offMeshConnectionsAreas.getCArray();
839
        params.offMeshConFlags = meshData.offMeshConnectionsFlags.getCArray();
840

841
        params.walkableHeight = BASE_UNIT_DIM*config.walkableHeight;    // agent height
842
        params.walkableRadius = BASE_UNIT_DIM*config.walkableRadius;    // agent radius
843
        params.walkableClimb = BASE_UNIT_DIM*config.walkableClimb;      // keep less that walkableHeight (aka agent height)!
844
        params.tileX = (((bmin[0] + bmax[0]) / 2) - navMesh->getParams()->orig[0]) / GRID_SIZE;
845
        params.tileY = (((bmin[2] + bmax[2]) / 2) - navMesh->getParams()->orig[2]) / GRID_SIZE;
846
        rcVcopy(params.bmin, bmin);
847
        rcVcopy(params.bmax, bmax);
848
        params.cs = config.cs;
849
        params.ch = config.ch;
850
        params.tileLayer = 0;
851
        params.buildBvTree = true;
852

853
        // will hold final navmesh
854
        unsigned char* navData = nullptr;
855
        int navDataSize = 0;
856

857
        do
858
        {
859
            // these values are checked within dtCreateNavMeshData - handle them here
860
            // so we have a clear error message
861
            if (params.nvp > DT_VERTS_PER_POLYGON)
862
            {
863
                printf("%s Invalid verts-per-polygon value!        \n", tileString);
864
                continue;
865
            }
866
            if (params.vertCount >= 0xffff)
867
            {
868
                printf("%s Too many vertices!                      \n", tileString);
869
                continue;
870
            }
871
            if (!params.vertCount || !params.verts)
872
            {
873
                // occurs mostly when adjacent tiles have models
874
                // loaded but those models don't span into this tile
875

876
                // message is an annoyance
877
                //printf("%sNo vertices to build tile!              \n", tileString);
878
                continue;
879
            }
880
            if (!params.polyCount || !params.polys) 
881
            {
882
                // we have flat tiles with no actual geometry - don't build those, its useless
883
                // drop tiles with only exact count - some tiles may have geometry while having less tiles
884
                printf("%s No polygons to build on tile!              \n", tileString);
885
                continue;
886
            }
887
            if (!params.detailMeshes || !params.detailVerts || !params.detailTris)
888
            {
889
                printf("%s No detail mesh to build tile!           \n", tileString);
890
                continue;
891
            }
892

893
            printf("%s Building navmesh tile...\n", tileString);
894
            if (!dtCreateNavMeshData(&params, &navData, &navDataSize))
895
            {
896
                printf("%s Failed building navmesh tile!           \n", tileString);
897
                continue;
898
            }
899

900
            dtTileRef tileRef = 0;
901
            printf("%s Adding tile to navmesh...\n", tileString);
902
            // DT_TILE_FREE_DATA tells detour to unallocate memory when the tile
903
            // is removed via removeTile()
904
            dtStatus dtResult = navMesh->addTile(navData, navDataSize, DT_TILE_FREE_DATA, 0, &tileRef);
905
            if (!tileRef || dtResult != DT_SUCCESS)
906
            {
907
                printf("%s Failed adding tile to navmesh!           \n", tileString);
908
                continue;
909
            }
910

911
            // file output
912
            char fileName[255];
913
            sprintf(fileName, "mmaps/%04u_%02i_%02i.mmtile", mapID, tileY, tileX);
914
            FILE* file = fopen(fileName, "wb");
915
            if (!file)
916
            {
917
                char message[1024];
918
                sprintf(message, "[Map %04i] Failed to open %s for writing!\n", mapID, fileName);
919
                perror(message);
920
                navMesh->removeTile(tileRef, nullptr, nullptr);
921
                continue;
922
            }
923

924
            printf("%s Writing to file...\n", tileString);
925

926
            // write header
927
            MmapTileHeader header;
928
            header.usesLiquids = m_terrainBuilder->usesLiquids();
929
            header.size = uint32(navDataSize);
930
            fwrite(&header, sizeof(MmapTileHeader), 1, file);
931

932
            // write data
933
            fwrite(navData, sizeof(unsigned char), navDataSize, file);
934
            fclose(file);
935

936
            // now that tile is written to disk, we can unload it
937
            navMesh->removeTile(tileRef, nullptr, nullptr);
938
        }
939
        while (0);
940

941
        if (m_debugOutput)
942
        {
943
            // restore padding so that the debug visualization is correct
944
            for (int i = 0; i < iv.polyMesh->nverts; ++i)
945
            {
946
                unsigned short* v = &iv.polyMesh->verts[i*3];
947
                v[0] += (unsigned short)config.borderSize;
948
                v[2] += (unsigned short)config.borderSize;
949
            }
950

951
            iv.generateObjFile(mapID, tileX, tileY, meshData);
952
            iv.writeIV(mapID, tileX, tileY);
953
        }
954
    }
955

956
    /**************************************************************************/
957
    void MapBuilder::getTileBounds(uint32 tileX, uint32 tileY, float* verts, int vertCount, float* bmin, float* bmax)
958
    {
959
        // this is for elevation
960
        if (verts && vertCount)
961
            rcCalcBounds(verts, vertCount, bmin, bmax);
962
        else
963
        {
964
            bmin[1] = FLT_MIN;
965
            bmax[1] = FLT_MAX;
966
        }
967

968
        // this is for width and depth
969
        bmax[0] = (32 - int(tileX)) * GRID_SIZE;
970
        bmax[2] = (32 - int(tileY)) * GRID_SIZE;
971
        bmin[0] = bmax[0] - GRID_SIZE;
972
        bmin[2] = bmax[2] - GRID_SIZE;
973
    }
974

975
    /**************************************************************************/
976
    bool MapBuilder::shouldSkipMap(uint32 mapID) const
977
    {
978
        if (m_mapid >= 0)
979
            return static_cast<uint32>(m_mapid) != mapID;        
980

981
        if (m_skipContinents)
982
            if (isContinentMap(mapID))
983
                return true;
984

985
        if (m_skipJunkMaps)
986
            switch (mapID)
987
            {
988
                case 13:    // test.wdt
989
                case 25:    // ScottTest.wdt
990
                case 29:    // Test.wdt
991
                case 42:    // Colin.wdt
992
                case 169:   // EmeraldDream.wdt (unused, and very large)
993
                case 451:   // development.wdt
994
                case 573:   // ExteriorTest.wdt
995
                case 597:   // CraigTest.wdt
996
                case 605:   // development_nonweighted.wdt
997
                case 606:   // QA_DVD.wdt
998
                case 651:   // ElevatorSpawnTest.wdt
999
                case 1060:  // LevelDesignLand-DevOnly.wdt                    
1000
                    return true;
1001
                default:
1002
                    if (isTransportMap(mapID))
1003
                        return true;
1004
                    break;
1005
            }
1006

1007
        if (m_skipBattlegrounds)
1008
            switch (mapID)
1009
            {
1010
                case 30:    // AV
1011
                case 37:    // ?
1012
                case 489:   // WSG
1013
                case 529:   // AB
1014
                case 566:   // EotS
1015
                case 607:   // SotA
1016
                case 628:   // IoC
1017
                case 726:   // Twin Peaks
1018
                case 727:   // Silvershard Mines
1019
                case 761:   // The Battle for Gilneas
1020
                case 968:   // Rated Eye of the Storm
1021
                case 998:   // Temple of Kotmogu
1022
                case 1010:  // CTF3
1023
                case 1105:  // Deepwind Gorge                    
1024
                    return true;
1025
                default:
1026
                    break;
1027
            }
1028

1029
        if (m_skipArenas)
1030
            switch (mapID)
1031
            {
1032
                case 559:   // Nagrand Arena
1033
                case 562:   // Blade's Edge Arena
1034
                case 572:   // Ruins of Lordaeron
1035
                case 617:   // Dalaran Sewers
1036
                case 618:   // The Ring of Valor                  
1037
                    return true;
1038
                default:
1039
                    break;
1040
            }
1041

1042
        return false;
1043
    }
1044
    /**************************************************************************/
1045
    bool MapBuilder::isTransportMap(uint32 mapID) const
1046
    {
1047
        switch (mapID)
1048
        {
1049
            // transport maps
1050
            case 582:
1051
            case 584:
1052
            case 586:
1053
            case 587:
1054
            case 588:
1055
            case 589:
1056
            case 590:
1057
            case 591:
1058
            case 592:
1059
            case 593:
1060
            case 594:
1061
            case 596:
1062
            case 610:
1063
            case 612:
1064
            case 613:
1065
            case 614:
1066
            case 620:
1067
            case 621:
1068
            case 622:
1069
            case 623:
1070
            case 641:
1071
            case 642:
1072
            case 647:
1073
            case 672:
1074
            case 673:
1075
            case 712:
1076
            case 713:
1077
            case 718:
1078
            case 738:
1079
            case 739:
1080
            case 740:
1081
            case 741:
1082
            case 742:
1083
            case 743:
1084
            case 747:
1085
            case 748:
1086
            case 749:
1087
            case 750:
1088
            case 762:
1089
            case 763:
1090
            case 765:
1091
            case 766:
1092
            case 767:                
1093
                return true;
1094
            default:
1095
                return false;
1096
        }
1097
    }
1098

1099
    bool MapBuilder::isContinentMap(uint32 mapID) const
1100
    {
1101
        switch (mapID)
1102
        {
1103
            case 0:
1104
            case 1:
1105
            case 530:
1106
            case 571:
1107
                return true;
1108
            default:
1109
                return false;
1110
        }
1111
    }
1112

1113
    /**************************************************************************/
1114
    // bool MapBuilder::isTransportMap(uint32 mapID) const
1115
    // {
1116
    //     return transportMaps.find(mapID) != transportMaps.end();
1117
    // }
1118

1119

1120

1121
    /**************************************************************************/
1122
    bool TileBuilder::shouldSkipTile(uint32 mapID, uint32 tileX, uint32 tileY) const
1123
    {
1124
        char fileName[255];
1125
        sprintf(fileName, "mmaps/%04u_%02i_%02i.mmtile", mapID, tileY, tileX);
1126
        FILE* file = fopen(fileName, "rb");
1127
        if (!file)
1128
            return false;
1129

1130
        MmapTileHeader header;
1131
        int count = fread(&header, sizeof(MmapTileHeader), 1, file);
1132
        fclose(file);
1133
        if (count != 1)
1134
            return false;
1135

1136
        if (header.mmapMagic != MMAP_MAGIC || header.dtVersion != uint32(DT_NAVMESH_VERSION))
1137
            return false;
1138

1139
        if (header.mmapVersion != MMAP_VERSION)
1140
            return false;
1141

1142
        return true;
1143
    }
1144

1145
    rcConfig MapBuilder::GetMapSpecificConfig(uint32 mapID, float bmin[3], float bmax[3], const TileConfig &tileConfig) const
1146
    {
1147
        rcConfig config;
1148
        memset(&config, 0, sizeof(rcConfig));
1149

1150
        rcVcopy(config.bmin, bmin);
1151
        rcVcopy(config.bmax, bmax);
1152

1153
        config.maxVertsPerPoly = DT_VERTS_PER_POLYGON;
1154
        config.cs = tileConfig.BASE_UNIT_DIM;
1155
        config.ch = tileConfig.BASE_UNIT_DIM;
1156
        // Keeping these 2 slope angles the same reduces a lot the number of polys.
1157
        // 55 should be the minimum, maybe 70 is ok (keep in mind blink uses mmaps), 85 is too much for players
1158
        config.walkableSlopeAngle = m_maxWalkableAngle ? *m_maxWalkableAngle : 55;
1159
        config.walkableSlopeAngleNotSteep = m_maxWalkableAngleNotSteep ? *m_maxWalkableAngleNotSteep : 55;
1160
        config.tileSize = tileConfig.VERTEX_PER_TILE;
1161
        config.walkableRadius = m_bigBaseUnit ? 1 : 2;
1162
        config.borderSize = config.walkableRadius + 3;
1163
        config.maxEdgeLen = tileConfig.VERTEX_PER_TILE + 1;        // anything bigger than tileSize
1164
        config.walkableHeight = m_bigBaseUnit ? 3 : 6;
1165
        // a value >= 3|6 allows npcs to walk over some fences
1166
        // a value >= 4|8 allows npcs to walk over all fences
1167
        config.walkableClimb = m_bigBaseUnit ? 3 : 6;
1168
        config.minRegionArea = rcSqr(60);
1169
        config.mergeRegionArea = rcSqr(50);
1170
        config.maxSimplificationError = 1.8f;           // eliminates most jagged edges (tiny polygons)
1171
        config.detailSampleDist = config.cs * 16;
1172
        config.detailSampleMaxError = config.ch * 1;
1173

1174
        switch (mapID)
1175
        {
1176
            // Blade's Edge Arena
1177
            case 562:
1178
                // This allows to walk on the ropes to the pillars
1179
                config.walkableRadius = 0;
1180
                break;
1181
            // Blackfathom Deeps
1182
            case 48:
1183
                // Reduce the chance to have underground levels
1184
                config.ch *= 2;
1185
                break;
1186
            default:
1187
                break;
1188
        }
1189

1190
        return config;
1191
    }
1192

1193
    /**************************************************************************/
1194
    uint32 MapBuilder::percentageDone(uint32 totalTiles, uint32 totalTilesBuilt) const
1195
    {
1196
        if (totalTiles)
1197
            return totalTilesBuilt * 100 / totalTiles;
1198

1199
        return 0;
1200
    }
1201

1202
    uint32 MapBuilder::currentPercentageDone() const
1203
    {
1204
        return percentageDone(m_totalTiles, m_totalTilesProcessed);
1205
    }
1206

1207
}
1208