fix: prevent entities from overlapping when arriving at the same cell

Update UpdateMoveSystem to maintain the moveMap as entities move
within a tick. When an entity snaps to a grid cell:
- Block the new cell in the moveMap immediately
- Unblock the old cell

Before snapping, check if the target cell was already claimed by
another entity earlier in the same tick. If so, repath instead of
overlapping.

3 files changed, 48 insertions, 1 deletions

diff --git a/go.mod b/go.mod
index 2c62952..398b4b5 100644
--- a/go.mod
+++ b/go.mod
@@ -7,6 +7,7 @@ toolchain go1.24.4
 require (
 	github.com/hajimehoshi/ebiten/v2 v2.8.8
 	github.com/martinlehoux/kagamigo v0.6.1
+	github.com/stretchr/testify v1.11.1
 	golang.org/x/exp v0.0.0-20250620022241-b7579e27df2b
 	golang.org/x/image v0.28.0
 )
@@ -14,6 +15,7 @@ require (
 require (
 	github.com/BurntSushi/toml v1.5.0 // indirect
 	github.com/a-h/templ v0.3.906 // indirect
+	github.com/davecgh/go-spew v1.1.2-0.20180830191138-d8f796af33cc // indirect
 	github.com/ebitengine/gomobile v0.0.0-20250329061421-6d0a8e981e4c // indirect
 	github.com/ebitengine/hideconsole v1.0.0 // indirect
 	github.com/ebitengine/purego v0.8.4 // indirect
@@ -22,7 +24,7 @@ require (
 	github.com/jezek/xgb v1.1.1 // indirect
 	github.com/kataras/i18n v0.0.8 // indirect
 	github.com/niemeyer/pretty v0.0.0-20200227124842-a10e7caefd8e // indirect
-	github.com/stretchr/testify v1.11.1 // indirect
+	github.com/pmezard/go-difflib v1.0.1-0.20181226105442-5d4384ee4fb2 // indirect
 	golang.org/x/net v0.41.0 // indirect
 	golang.org/x/sync v0.15.0 // indirect
 	golang.org/x/sys v0.33.0 // indirect
diff --git a/integration_test.go b/integration_test.go
index 8305719..b8f9ba5 100644
--- a/integration_test.go
+++ b/integration_test.go
@@ -5,6 +5,8 @@ import (
 	"time"
 
 	"age_of_empires/physics"
+
+	"github.com/stretchr/testify/assert"
 )
 
 func TestGatherLoop(t *testing.T) {
@@ -62,3 +64,31 @@ func TestGatherLoop(t *testing.T) {
 		t.Errorf("Unit failed to gather resources within %d ticks. ResourceAmount: %d", maxTicks, game.ResourceAmount)
 	}
 }
+
+func TestTwoEntitiesMovingToSameCellDontOverlap(t *testing.T) {
+	// Two units close together both ordered to the same cell should not overlap.
+	game := &Game{}
+
+	target := physics.Point{X: 500, Y: 0}
+
+	unitA := game.Append(NewEntityBuilder().
+		WithPosition(physics.Point{X: 200, Y: 0}).
+		WithMove().WithOrder().Build())
+	unitB := game.Append(NewEntityBuilder().
+		WithPosition(physics.Point{X: 100, Y: 0}).
+		WithMove().WithOrder().Build())
+
+	moveMap := game.getMoveMap()
+	MainAction(game, unitA, target, moveMap)
+	MainAction(game, unitB, target, moveMap)
+
+	// MOVE_SPEED=10, cell=100 → 10 ticks per cell. B detours around A → ~60 ticks.
+	for range 60 {
+		game.Update()
+	}
+
+	assert.False(t, game.Move[unitA].IsActive, "Entity A should have stopped moving")
+	assert.False(t, game.Move[unitB].IsActive, "Entity B should have stopped moving")
+	assert.NotEqual(t, game.Position[unitA], game.Position[unitB],
+		"Entity A and B should NOT overlap: A at %s, B at %s", game.Position[unitA], game.Position[unitB])
+}
diff --git a/physics/move.go b/physics/move.go
index 94da69f..b898ec7 100644
--- a/physics/move.go
+++ b/physics/move.go
@@ -192,7 +192,22 @@ func UpdateMoveSystem(moveMap MoveMap, masks []ecs.Mask, moves []Move, positions
 			*position = moveToward(*position, next)
 			continue
 		}
+		// About to snap to next cell — check it's still free
+		if moveMap.Blocked[next] {
+			slog.Info("cell blocked on arrival, repathing", slog.String("next", next.String()))
+			path, ok := SearchPath(*position, move.Destination, moveMap)
+			if !ok {
+				slog.Info("no path found", slog.String("destination", move.Destination.String()))
+				move.IsActive = false
+				continue
+			}
+			move.Path = path[1:]
+			continue
+		}
+		oldCell := Point{X: position.X / 100 * 100, Y: position.Y / 100 * 100}
 		*position = next
+		moveMap.Blocked[next] = true
+		delete(moveMap.Blocked, oldCell)
 		remainingPath := move.Path[1:]
 		if next == move.Destination {
 			move.IsActive = false