Core/MMAPs: Update recast

Update recast to https://github.com/recastnavigation/recastnavigation/commit/64385e9ed0822427bca5814d03a3f4c4d7a6db9f

1 files changed, 51 insertions, 25 deletions

diff --git a/dep/recastnavigation/Recast/Source/RecastLayers.cpp b/dep/recastnavigation/Recast/Source/RecastLayers.cpp
index 41458c1ea68..acc97e44f00 100644
--- a/dep/recastnavigation/Recast/Source/RecastLayers.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastLayers.cpp
@@ -27,7 +27,9 @@
 #include "RecastAssert.h"
 
 
-static const int RC_MAX_LAYERS = RC_NOT_CONNECTED;
+// Must be 255 or smaller (not 256) because layer IDs are stored as
+// a byte where 255 is a special value.
+static const int RC_MAX_LAYERS = 63;
 static const int RC_MAX_NEIS = 16;
 
 struct rcLayerRegion
@@ -42,25 +44,31 @@ struct rcLayerRegion
 };
 
 
-static void addUnique(unsigned char* a, unsigned char& an, unsigned char v)
-{
-	const int n = (int)an;
-	for (int i = 0; i < n; ++i)
-		if (a[i] == v)
-			return;
-	a[an] = v;
-	an++;
-}
-
 static bool contains(const unsigned char* a, const unsigned char an, const unsigned char v)
 {
 	const int n = (int)an;
 	for (int i = 0; i < n; ++i)
+	{
 		if (a[i] == v)
 			return true;
+	}
 	return false;
 }
 
+static bool addUnique(unsigned char* a, unsigned char& an, int anMax, unsigned char v)
+{
+	if (contains(a, an, v))
+		return true;
+
+	if ((int)an >= anMax)
+		return false;
+
+	a[an] = v;
+	an++;
+	return true;
+}
+
+
 inline bool overlapRange(const unsigned short amin, const unsigned short amax,
 						 const unsigned short bmin, const unsigned short bmax)
 {
@@ -87,12 +95,12 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 {
 	rcAssert(ctx);
 	
-	ctx->startTimer(RC_TIMER_BUILD_LAYERS);
+	rcScopedTimer timer(ctx, RC_TIMER_BUILD_LAYERS);
 	
 	const int w = chf.width;
 	const int h = chf.height;
 	
-	rcScopedDelete<unsigned char> srcReg = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
+	rcScopedDelete<unsigned char> srcReg((unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP));
 	if (!srcReg)
 	{
 		ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
@@ -101,7 +109,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 	memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount);
 	
 	const int nsweeps = chf.width;
-	rcScopedDelete<rcLayerSweepSpan> sweeps = (rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP);
+	rcScopedDelete<rcLayerSweepSpan> sweeps((rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP));
 	if (!sweeps)
 	{
 		ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps);
@@ -212,7 +220,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 
 	// Allocate and init layer regions.
 	const int nregs = (int)regId;
-	rcScopedDelete<rcLayerRegion> regs = (rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP);
+	rcScopedDelete<rcLayerRegion> regs((rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP));
 	if (!regs)
 	{
 		ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs);
@@ -259,7 +267,12 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 						const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
 						const unsigned char rai = srcReg[ai];
 						if (rai != 0xff && rai != ri)
-							addUnique(regs[ri].neis, regs[ri].nneis, rai);
+						{
+							// Don't check return value -- if we cannot add the neighbor
+							// it will just cause a few more regions to be created, which
+							// is fine.
+							addUnique(regs[ri].neis, regs[ri].nneis, RC_MAX_NEIS, rai);
+						}
 					}
 				}
 				
@@ -274,8 +287,13 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 					{
 						rcLayerRegion& ri = regs[lregs[i]];
 						rcLayerRegion& rj = regs[lregs[j]];
-						addUnique(ri.layers, ri.nlayers, lregs[j]);
-						addUnique(rj.layers, rj.nlayers, lregs[i]);
+
+						if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, lregs[j]) ||
+							!addUnique(rj.layers, rj.nlayers, RC_MAX_LAYERS, lregs[i]))
+						{
+							ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS.");
+							return false;
+						}
 					}
 				}
 			}
@@ -338,7 +356,13 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 					regn.layerId = layerId;
 					// Merge current layers to root.
 					for (int k = 0; k < regn.nlayers; ++k)
-						addUnique(root.layers, root.nlayers, regn.layers[k]);
+					{
+						if (!addUnique(root.layers, root.nlayers, RC_MAX_LAYERS, regn.layers[k]))
+						{
+							ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS.");
+							return false;
+						}
+					}
 					root.ymin = rcMin(root.ymin, regn.ymin);
 					root.ymax = rcMax(root.ymax, regn.ymax);
 				}
@@ -416,7 +440,14 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 					rj.layerId = newId;
 					// Add overlaid layers from 'rj' to 'ri'.
 					for (int k = 0; k < rj.nlayers; ++k)
-						addUnique(ri.layers, ri.nlayers, rj.layers[k]);
+					{
+						if (!addUnique(ri.layers, ri.nlayers, RC_MAX_LAYERS, rj.layers[k]))
+						{
+							ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: layer overflow (too many overlapping walkable platforms). Try increasing RC_MAX_LAYERS.");
+							return false;
+						}
+					}
+
 					// Update height bounds.
 					ri.ymin = rcMin(ri.ymin, rj.ymin);
 					ri.ymax = rcMax(ri.ymax, rj.ymax);
@@ -446,10 +477,7 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 	
 	// No layers, return empty.
 	if (layerId == 0)
-	{
-		ctx->stopTimer(RC_TIMER_BUILD_LAYERS);
 		return true;
-	}
 	
 	// Create layers.
 	rcAssert(lset.layers == 0);
@@ -612,7 +640,5 @@ bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
 			layer->miny = layer->maxy = 0;
 	}
 	
-	ctx->stopTimer(RC_TIMER_BUILD_LAYERS);
-	
 	return true;
 }