Core/Maps: Parse MFBO adt chunk to properly handle height where player counts as falling under the map

* This fixes the height at which player is instantly killed when falling from The Frozen Throne
* Set PLAYER_FLAGS_IS_OUT_OF_BOUNDS on players under the map to enable release spirit button while still falling

Note: Extracting new maps is required

5 files changed, 122 insertions, 8 deletions

diff --git a/src/tools/map_extractor/CMakeLists.txt b/src/tools/map_extractor/CMakeLists.txt
index 32fccaa2038..58435a51121 100644
--- a/src/tools/map_extractor/CMakeLists.txt
+++ b/src/tools/map_extractor/CMakeLists.txt
@@ -14,6 +14,7 @@ file(GLOB_RECURSE sources *.cpp *.h)
 include_directories (
   ${CMAKE_SOURCE_DIR}/dep/CascLib/src
   ${CMAKE_SOURCE_DIR}/dep/cppformat
+  ${CMAKE_SOURCE_DIR}/dep/g3dlite/include
   ${CMAKE_SOURCE_DIR}/src/common
   ${CMAKE_SOURCE_DIR}/src/common/Utilities
   ${CMAKE_SOURCE_DIR}/src/server/shared
@@ -31,6 +32,7 @@ target_link_libraries(mapextractor
   casc
   common
   format
+  g3dlib
   ${BZIP2_LIBRARIES}
   ${ZLIB_LIBRARIES}
   ${Boost_LIBRARIES}
diff --git a/src/tools/map_extractor/System.cpp b/src/tools/map_extractor/System.cpp
index 2d36df68df1..a079ab42367 100644
--- a/src/tools/map_extractor/System.cpp
+++ b/src/tools/map_extractor/System.cpp
@@ -40,6 +40,8 @@
 #include "adt.h"
 #include "wdt.h"
 
+#include <G3D/Plane.h>
+
 namespace
 {
     const char* HumanReadableCASCError(int error)
@@ -351,7 +353,7 @@ void ReadLiquidTypeTableDBC()
 
 // Map file format data
 static char const* MAP_MAGIC         = "MAPS";
-static char const* MAP_VERSION_MAGIC = "v1.6";
+static char const* MAP_VERSION_MAGIC = "v1.7";
 static char const* MAP_AREA_MAGIC    = "AREA";
 static char const* MAP_HEIGHT_MAGIC  = "MHGT";
 static char const* MAP_LIQUID_MAGIC  = "MLIQ";
@@ -380,9 +382,10 @@ struct map_areaHeader
     uint16 gridArea;
 };
 
-#define MAP_HEIGHT_NO_HEIGHT  0x0001
-#define MAP_HEIGHT_AS_INT16   0x0002
-#define MAP_HEIGHT_AS_INT8    0x0004
+#define MAP_HEIGHT_NO_HEIGHT            0x0001
+#define MAP_HEIGHT_AS_INT16             0x0002
+#define MAP_HEIGHT_AS_INT8              0x0004
+#define MAP_HEIGHT_HAS_FLIGHT_BOUNDS    0x0008
 
 struct map_heightHeader
 {
@@ -442,14 +445,17 @@ bool  liquid_show[ADT_GRID_SIZE][ADT_GRID_SIZE];
 float liquid_height[ADT_GRID_SIZE+1][ADT_GRID_SIZE+1];
 uint8 holes[ADT_CELLS_PER_GRID][ADT_CELLS_PER_GRID][8];
 
-bool TransformToHighRes(uint16 holes, uint8 hiResHoles[8])
+float flight_box_max[ADT_CELLS_PER_GRID][ADT_CELLS_PER_GRID];
+float flight_box_min[ADT_CELLS_PER_GRID][ADT_CELLS_PER_GRID];
+
+bool TransformToHighRes(uint16 lowResHoles, uint8 hiResHoles[8])
 {
     for (uint8 i = 0; i < 8; i++)
     {
         for (uint8 j = 0; j < 8; j++)
         {
             int32 holeIdxL = (i / 2) * 4 + (j / 2);
-            if (((holes >> holeIdxL) & 1) == 1)
+            if (((lowResHoles >> holeIdxL) & 1) == 1)
                 hiResHoles[i] |= (1 << j);
         }
     }
@@ -482,6 +488,7 @@ bool ConvertADT(std::string const& inputPath, std::string const& outputPath, int
     memset(holes, 0, sizeof(holes));
 
     bool hasHoles = false;
+    bool hasFlightBox = false;
 
     for (std::multimap<std::string, FileChunk*>::const_iterator itr = adt.chunks.lower_bound("MCNK"); itr != adt.chunks.upper_bound("MCNK"); ++itr)
     {
@@ -696,6 +703,82 @@ bool ConvertADT(std::string const& inputPath, std::string const& outputPath, int
         }
     }
 
+    if (FileChunk* chunk = adt.GetChunk("MFBO"))
+    {
+        static uint32 const indices[] =
+        {
+            3, 0, 4,
+            0, 1, 4,
+            1, 2, 4,
+            2, 5, 4,
+            5, 8, 4,
+            8, 7, 4,
+            7, 6, 4,
+            6, 3, 4
+        };
+
+        static float const boundGridCoords[] =
+        {
+            0.0f, 0.0f,
+            0.0f, -266.66666f,
+            0.0f, -533.33331f,
+            -266.66666f, 0.0f,
+            -266.66666f, -266.66666f,
+            -266.66666f, -533.33331f,
+            -533.33331f, 0.0f,
+            -533.33331f, -266.66666f,
+            -533.33331f, -533.33331f
+        };
+
+        adt_MFBO* mfbo = chunk->As<adt_MFBO>();
+        for (int gy = 0; gy < ADT_CELLS_PER_GRID; ++gy)
+        {
+            for (int gx = 0; gx < ADT_CELLS_PER_GRID; ++gx)
+            {
+                int32 quarterIndex = 0;
+                if (gy > ADT_CELLS_PER_GRID / 2)
+                {
+                    if (gx > ADT_CELLS_PER_GRID / 2)
+                    {
+                        quarterIndex = 4 + gx < gy;
+                    }
+                    else
+                        quarterIndex = 2;
+                }
+                else if (gx > ADT_CELLS_PER_GRID / 2)
+                {
+                    quarterIndex = 7;
+                }
+                else
+                    quarterIndex = gx > gy;
+
+                quarterIndex *= 3;
+                G3D::Plane planeMax(
+                    G3D::Vector3(boundGridCoords[indices[quarterIndex + 0] * 2 + 0], boundGridCoords[indices[quarterIndex + 0] * 2 + 1], mfbo->max.coords[indices[quarterIndex + 0]]),
+                    G3D::Vector3(boundGridCoords[indices[quarterIndex + 1] * 2 + 0], boundGridCoords[indices[quarterIndex + 1] * 2 + 1], mfbo->max.coords[indices[quarterIndex + 1]]),
+                    G3D::Vector3(boundGridCoords[indices[quarterIndex + 2] * 2 + 0], boundGridCoords[indices[quarterIndex + 2] * 2 + 1], mfbo->max.coords[indices[quarterIndex + 2]])
+                );
+
+                G3D::Plane planeMin(
+                    G3D::Vector3(boundGridCoords[indices[quarterIndex + 0] * 2 + 0], boundGridCoords[indices[quarterIndex + 0] * 2 + 1], mfbo->min.coords[indices[quarterIndex + 0]]),
+                    G3D::Vector3(boundGridCoords[indices[quarterIndex + 1] * 2 + 0], boundGridCoords[indices[quarterIndex + 1] * 2 + 1], mfbo->min.coords[indices[quarterIndex + 1]]),
+                    G3D::Vector3(boundGridCoords[indices[quarterIndex + 2] * 2 + 0], boundGridCoords[indices[quarterIndex + 2] * 2 + 1], mfbo->min.coords[indices[quarterIndex + 2]])
+                );
+
+                auto non_nan_distance = [](G3D::Plane const& plane){
+                    auto d = plane.distance(G3D::Vector3(0.0f, 0.0f, 0.0f));
+                    assert(!G3D::isNaN(d));
+                    return d;
+                };
+
+                flight_box_max[gy][gx] = non_nan_distance(planeMax);
+                flight_box_min[gy][gx] = non_nan_distance(planeMin);
+            }
+        }
+
+        hasFlightBox = true;
+    }
+
     //============================================
     // Try pack area data
     //============================================
@@ -787,6 +870,12 @@ bool ConvertADT(std::string const& inputPath, std::string const& outputPath, int
     if (CONF_allow_float_to_int && (maxHeight - minHeight) < CONF_flat_height_delta_limit)
         heightHeader.flags |= MAP_HEIGHT_NO_HEIGHT;
 
+    if (hasFlightBox)
+    {
+        heightHeader.flags |= MAP_HEIGHT_HAS_FLIGHT_BOUNDS;
+        map.heightMapSize += sizeof(flight_box_max) + sizeof(flight_box_min);
+    }
+
     // Try store as packed in uint16 or uint8 values
     if (!(heightHeader.flags & MAP_HEIGHT_NO_HEIGHT))
     {
@@ -958,6 +1047,12 @@ bool ConvertADT(std::string const& inputPath, std::string const& outputPath, int
         }
     }
 
+    if (heightHeader.flags & MAP_HEIGHT_HAS_FLIGHT_BOUNDS)
+    {
+        outFile.write(reinterpret_cast<char*>(flight_box_max), sizeof(flight_box_max));
+        outFile.write(reinterpret_cast<char*>(flight_box_min), sizeof(flight_box_min));
+    }
+
     // Store liquid data if need
     if (map.liquidMapOffset)
     {
diff --git a/src/tools/map_extractor/adt.h b/src/tools/map_extractor/adt.h
index 0c3b3780c16..bb6980507b7 100644
--- a/src/tools/map_extractor/adt.h
+++ b/src/tools/map_extractor/adt.h
@@ -219,6 +219,22 @@ struct adt_MH2O
 
 };
 
+struct adt_MFBO
+{
+    union
+    {
+        uint32 fcc;
+        char   fcc_txt[4];
+    };
+    uint32 size;
+    struct plane
+    {
+        int16 coords[9];
+    };
+    plane max;
+    plane min;
+};
+
 #pragma pack(pop)
 
 #endif
diff --git a/src/tools/map_extractor/loadlib.cpp b/src/tools/map_extractor/loadlib.cpp
index 39bbe5b1412..067683577f4 100644
--- a/src/tools/map_extractor/loadlib.cpp
+++ b/src/tools/map_extractor/loadlib.cpp
@@ -96,7 +96,8 @@ u_map_fcc InterestingChunks[] =
     { { 'K', 'N', 'C', 'M' } },
     { { 'T', 'V', 'C', 'M' } },
     { { 'O', 'M', 'W', 'M' } },
-    { { 'Q', 'L', 'C', 'M' } }
+    { { 'Q', 'L', 'C', 'M' } },
+    { { 'O', 'B', 'F', 'M' } }
 };
 
 bool IsInterestingChunk(u_map_fcc const& fcc)
diff --git a/src/tools/mmaps_generator/TerrainBuilder.cpp b/src/tools/mmaps_generator/TerrainBuilder.cpp
index 33832f8986d..c4a32882c1d 100644
--- a/src/tools/mmaps_generator/TerrainBuilder.cpp
+++ b/src/tools/mmaps_generator/TerrainBuilder.cpp
@@ -80,7 +80,7 @@ struct map_liquidHeader
 namespace MMAP
 {
 
-    char const* MAP_VERSION_MAGIC = "v1.6";
+    char const* MAP_VERSION_MAGIC = "v1.7";
 
     TerrainBuilder::TerrainBuilder(bool skipLiquid) : m_skipLiquid (skipLiquid){ }
     TerrainBuilder::~TerrainBuilder() { }