diff --git a/src/misc.cpp b/src/misc.cpp
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -28,6 +28,7 @@
 #include "core/pool_type.hpp"
 #include "game/game.hpp"
 #include "linkgraph/linkgraphschedule.h"
+#include "town_kdtree.h"
 
 #include "safeguards.h"
 
@@ -75,6 +76,8 @@ void InitializeGame(uint size_x, uint si
 	LinkGraphSchedule::Clear();
 	PoolBase::Clean(PT_NORMAL);
 
+	RebuildTownKdtree();
+
 	ResetPersistentNewGRFData();
 
 	InitializeSound();