Index: source/simulation2/helpers/PathGoal.cpp
===================================================================
--- source/simulation2/helpers/PathGoal.cpp
+++ source/simulation2/helpers/PathGoal.cpp
@@ -1,4 +1,4 @@
-/* Copyright (C) 2018 Wildfire Games.
+/* Copyright (C) 2019 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -26,18 +26,20 @@
 
 static bool NavcellContainsCircle(int i, int j, fixed x, fixed z, fixed r, bool inside)
 {
-	// Accept any navcell (i,j) that contains a point which is inside[/outside]
-	// (or on the edge of) the circle
+	// Accept any circle (x, z, r) that contains a point which is:
+	//  - strictly inside the navcell
+	//  - exactly on the left/top edge of the navcell
+	// (and vice-versa if inside is false).
+	// We pick the left/top edges as this avoids ambiguity: a point can only belong to one navcell.
 
-	// Get world-space bounds of navcell
 	entity_pos_t x0 = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE);
 	entity_pos_t z0 = entity_pos_t::FromInt(j).Multiply(Pathfinding::NAVCELL_SIZE);
-	entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE;
-	entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE;
+	entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon();
+	entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon();
 
 	if (inside)
 	{
-		// Get the point inside the navcell closest to (x,z)
+		// Get the point inside the navcell closest to (x, z)
 		entity_pos_t nx = Clamp(x, x0, x1);
 		entity_pos_t nz = Clamp(z, z0, z1);
 		// Check if that point is inside the circle
@@ -61,18 +63,20 @@
 	fixed x, fixed z, CFixedVector2D u, CFixedVector2D v, fixed hw, fixed hh,
 	bool inside)
 {
-	// Accept any navcell (i,j) that contains a point which is inside[/outside]
-	// (or on the edge of) the square
+	// Accept any square (x, z, u, v, hw, hh) that contains a point which is:
+	//  - strictly inside the navcell
+	//  - exactly on the left/top edge of the navcell
+	// (and vice-versa if inside is false).
+	// We pick the left/top edges as this avoids ambiguity: a point can only belong to one navcell.
 
-	// Get world-space bounds of navcell
 	entity_pos_t x0 = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE);
 	entity_pos_t z0 = entity_pos_t::FromInt(j).Multiply(Pathfinding::NAVCELL_SIZE);
-	entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE;
-	entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE;
+	entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon();
+	entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon();
 
 	if (inside)
 	{
-		// Get the point inside the navcell closest to (x,z)
+		// Get the point inside the navcell closest to (x, z)
 		entity_pos_t nx = Clamp(x, x0, x1);
 		entity_pos_t nz = Clamp(z, z0, z1);
 		// Check if that point is inside the circle
@@ -123,7 +127,7 @@
 	int jmin = std::min(j0, j1);
 	int jmax = std::max(j0, j1);
 
-	// Direction to iterate from (i0,j0) towards (i1,j1)
+	// Direction to iterate from (i0, j0) towards (i1, j1)
 	int di = i1 < i0 ? -1 : +1;
 	int dj = j1 < j0 ? -1 : +1;
 
@@ -148,9 +152,9 @@
 
 	case CIRCLE:
 	{
-		// Loop over all navcells in the given range (starting at (i0,j0) since
+		// Loop over all navcells in the given range (starting at (i0, j0) since
 		// this function is meant to find the goal navcell nearest to there
-		// assuming jmin==jmax || imin==imax),
+		// assuming jmin == jmax || imin == imax),
 		// and check whether any point in each navcell is within the goal circle.
 		// (TODO: this is pretty inefficient.)
 		for (int j = j0; jmin <= j && j <= jmax; j += dj)
@@ -172,9 +176,9 @@
 
 	case INVERTED_CIRCLE:
 	{
-		// Loop over all navcells in the given range (starting at (i0,j0) since
+		// Loop over all navcells in the given range (starting at (i0, j0) since
 		// this function is meant to find the goal navcell nearest to there
-		// assuming jmin==jmax || imin==imax),
+		// assuming jmin == jmax || imin == imax),
 		// and check whether any point in each navcell is outside the goal circle.
 		// (TODO: this is pretty inefficient.)
 		for (int j = j0; jmin <= j && j <= jmax; j += dj)
@@ -196,9 +200,9 @@
 
 	case SQUARE:
 	{
-		// Loop over all navcells in the given range (starting at (i0,j0) since
+		// Loop over all navcells in the given range (starting at (i0, j0) since
 		// this function is meant to find the goal navcell nearest to there
-		// assuming jmin==jmax || imin==imax),
+		// assuming jmin == jmax || imin == imax),
 		// and check whether any point in each navcell is within the goal square.
 		// (TODO: this is pretty inefficient.)
 		for (int j = j0; jmin <= j && j <= jmax; j += dj)
@@ -220,9 +224,9 @@
 
 	case INVERTED_SQUARE:
 	{
-		// Loop over all navcells in the given range (starting at (i0,j0) since
+		// Loop over all navcells in the given range (starting at (i0, j0) since
 		// this function is meant to find the goal navcell nearest to there
-		// assuming jmin==jmax || imin==imax),
+		// assuming jmin == jmax || imin == imax),
 		// and check whether any point in each navcell is outside the goal square.
 		// (TODO: this is pretty inefficient.)
 		for (int j = j0; jmin <= j && j <= jmax; j += dj)