4 files changed, 19 insertions, 7 deletions
diff --git a/modules/navigation/nav_map.cpp b/modules/navigation/nav_map.cpp
index cbc0adc574..344475fb37 100644
--- a/modules/navigation/nav_map.cpp
+++ b/modules/navigation/nav_map.cpp
@@ -541,7 +541,7 @@ void NavMap::sync() {
 		}
 
 		// Group all edges per key.
-		Map<gd::EdgeKey, Vector<gd::Edge::Connection>> connections;
+		HashMap<gd::EdgeKey, Vector<gd::Edge::Connection>, gd::EdgeKey> connections;
 		for (size_t poly_id(0); poly_id < polygons.size(); poly_id++) {
 			gd::Polygon &poly(polygons[poly_id]);
 
@@ -549,7 +549,7 @@ void NavMap::sync() {
 				int next_point = (p + 1) % poly.points.size();
 				gd::EdgeKey ek(poly.points[p].key, poly.points[next_point].key);
 
-				Map<gd::EdgeKey, Vector<gd::Edge::Connection>>::Element *connection = connections.find(ek);
+				HashMap<gd::EdgeKey, Vector<gd::Edge::Connection>, gd::EdgeKey>::Iterator connection = connections.find(ek);
 				if (!connection) {
 					connections[ek] = Vector<gd::Edge::Connection>();
 				}
diff --git a/modules/navigation/nav_map.h b/modules/navigation/nav_map.h
index 5232e42bed..0ebdea30e1 100644
--- a/modules/navigation/nav_map.h
+++ b/modules/navigation/nav_map.h
@@ -34,7 +34,7 @@
 #include "nav_rid.h"
 
 #include "core/math/math_defs.h"
-#include "core/templates/map.h"
+#include "core/templates/rb_map.h"
 #include "core/templates/thread_work_pool.h"
 #include "nav_utils.h"
 
diff --git a/modules/navigation/nav_utils.h b/modules/navigation/nav_utils.h
index 5b6c695ca4..a9f4e0e2fc 100644
--- a/modules/navigation/nav_utils.h
+++ b/modules/navigation/nav_utils.h
@@ -32,8 +32,9 @@
 #define NAV_UTILS_H
 
 #include "core/math/vector3.h"
+#include "core/templates/hash_map.h"
+#include "core/templates/hashfuncs.h"
 #include "core/templates/vector.h"
-
 #include <vector>
 
 class NavRegion;
@@ -49,15 +50,18 @@ union PointKey {
 	};
 
 	uint64_t key = 0;
-	bool operator<(const PointKey &p_key) const { return key < p_key.key; }
 };
 
 struct EdgeKey {
 	PointKey a;
 	PointKey b;
 
-	bool operator<(const EdgeKey &p_key) const {
-		return (a.key == p_key.a.key) ? (b.key < p_key.b.key) : (a.key < p_key.a.key);
+	static uint32_t hash(const EdgeKey &p_val) {
+		return hash_one_uint64(p_val.a.key) ^ hash_one_uint64(p_val.b.key);
+	}
+
+	bool operator==(const EdgeKey &p_key) const {
+		return (a.key == p_key.a.key) && (b.key == p_key.b.key);
 	}
 
 	EdgeKey(const PointKey &p_a = PointKey(), const PointKey &p_b = PointKey()) :
diff --git a/modules/navigation/navigation_mesh_generator.cpp b/modules/navigation/navigation_mesh_generator.cpp
index 2d6c78f704..110a4f5138 100644
--- a/modules/navigation/navigation_mesh_generator.cpp
+++ b/modules/navigation/navigation_mesh_generator.cpp
@@ -462,6 +462,14 @@ void NavigationMeshGenerator::_build_recast_navigation_mesh(
 #endif
 	rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height);
 
+	// ~30000000 seems to be around sweetspot where Editor baking breaks
+	if ((cfg.width * cfg.height) > 30000000) {
+		WARN_PRINT("NavigationMesh baking process will likely fail."
+				   "\nSource geometry is suspiciously big for the current Cell Size and Cell Height in the NavMesh Resource bake settings."
+				   "\nIf baking does not fail, the resulting NavigationMesh will create serious pathfinding performance issues."
+				   "\nIt is advised to increase Cell Size and/or Cell Height in the NavMesh Resource bake settings or reduce the size / scale of the source geometry.");
+	}
+
 #ifdef TOOLS_ENABLED
 	if (ep) {
 		ep->step(TTR("Creating heightfield..."), 3);