Placed buildings must block pathfinding #56

Closed
opened 2026-08-31 09:52:49 +01:00 by liamjd · 1 comment
Owner

Placed buildings are currently invisible to pathfinding. TerrainGrid._build_navigation() runs once inside generate(), and is_walkable() asks exactly one question — is this tile water. Nothing in #54's registry touches the A* graph, so once buildings exist pawns will walk straight through them.

This issue covers making the A* graph aware of occupancy, and picking where the blocked set lives. It does not cover pawn movement itself, job assignment or haulage — it is the substrate those need.

The collider is a red herring

#54 notes that the spawned mesh has no collider and that this is correct. Worth stating plainly why it does not matter here either: the colliders in _build_mesh_library() exist so the mouse raycast can hit the ground. Pawn movement never touches physics — find_path() returns a PackedVector3Array of tile centres and the pawn interpolates along them, and Pawn carries an Area3D, not a CharacterBody3D, so there is no collide-and-slide for a building to obstruct.

The A graph is the only thing that will ever stop a pawn walking through a building.* Adding a collider would not fix navigation, and the missing one does not break it. Same shape of argument as the OCCUPIED rule in #54: no physics fallback is quietly covering for you.

Scope

In:

  • A blocked-cell set consulted by is_walkable().
  • Incremental A* update on place and on remove.
  • Recomputing _main_region when the blocked set changes.
  • Deciding what happens to the blocked set on terrain regeneration.
  • Tests for all of the above.

Out (each wants its own issue):

  • The entrance itself — that is #55. This issue only has to leave room for it.
  • Pawn re-pathing behaviour when a building lands mid-walk (noted under "Things that will bite").
  • Movement costs / weighted tiles for roads and paths.
  • blocks_movement as a BuildingType field.

Update the graph incrementally, do not rebuild it

AStar2D.remove_point() removes the point and every connection attached to it, so blocking a building is one call per occupied cell and none of the cliff-edge or diagonal-corner logic needs re-running. Rebuilding the whole graph instead means an 8-neighbour sweep plus a flood fill over grid_size^2 cells to avoid three or four remove_point() calls.

Re-adding is not symmetric with removing, and this is where the bug will be. _build_navigation() connects using HALF_NEIGHBOURS, which is only correct because it is a full sweep where every adjacent pair gets visited exactly once from one side. Restoring a single cell must iterate FULL_NEIGHBOURS and test _can_traverse() for that cell against each neighbour, or the tile comes back reachable from the north and not from the south. Write the unblock path at the same time as the block path — the same argument #54 makes for putting remove() in the registry API before anything calls it.

Where the blocked set lives

TerrainGrid owns _astar. The #54 registry owns occupancy. Something has to join them. Three shapes, and the middle one is the recommendation:

  • Buildings reaches into _astar directly. Leaks the graph out of its owner; two places now maintain it. No.
  • TerrainGrid.block_cells(cells) / unblock_cells(cells). Buildings says "these cells are blocked" and TerrainGrid never learns what a building is. A _blocked: Dictionary field, two methods, and is_walkable() gains and not _blocked.has(cell). The graph stays in one place, and this does not foreclose the third option later.
  • A separate Navigation node owning the A, with TerrainGrid as a pure data provider.* Where this ends up if navigation grows costs, layers or tile reservations. A bigger refactor than this needs today.

Dictionary-as-set for _blocked, following the existing house pattern (BuildingFootprint._has_disjoined_cells(), and #54's _occupancy).

Things that will bite

  • is_walkable() has three other callers, and they all inherit the new answer: _build_navigation(), nearest_walkable() and _find_largest_region(). That is mostly what you want, but it means the blocked set has to be correct before any of them run.
  • Terrain regeneration. reroll() and next_shape() call generate(), which rebuilds the graph from terrain alone. A stale _blocked set now corrupts _main_region and therefore pawn spawning, not just the visuals — the same wart #54 flags about the registry not being cleared, but with teeth. Either clear both on regenerated, or re-apply the blocked set after _build_navigation(). Decide the ordering explicitly; do not let it fall out of signal connection order.
  • _main_region goes stale on every placement. It is computed once in _build_navigation() and is what random_walkable_position() spawns onto. Blocking cells can shrink it or split it in two.
  • A building can disconnect the map. Dropped across a one-tile isthmus or the only ramp between two levels, it splits the walkable region — pawns get stranded and a building's own entrance can become unreachable. Detecting it means a flood fill per candidate site, which is not affordable every frame while the ghost is hovering. Recommendation: allow it. The Settlers lets you wall yourself in too. find_path() already returns an empty array when no route exists, so make sure every caller treats empty as "no route" rather than as an error, and recompute _main_region after any block/unblock. Recorded as a decision so it is not discovered later.
  • Existing paths go stale. A path is a snapshot PackedVector3Array; placing a building mid-walk does not invalidate it and the pawn strolls through the new wall. The GameState.building_placed signal #54 adds is the hook — pawns re-path on it, or check waypoint validity as they go. Out of scope here, but the signal has to carry enough to make it possible.

What this leaves for #55

Recorded here because the two issues constrain each other, not because any of it should be built in this one.

A pawn can never stand on a building's cells once they are blocked, so "go to the mine" must resolve to a tile outside the footprint. nearest_walkable() is the wrong tool for that even though it looks like it fits: its Chebyshev ring search only asks "is this tile walkable", never "is it connected to me", so it will happily snap to a tile on the far side of the warehouse or across a cliff. Keep it for map clicks, where snapping to the shoreline is the desired behaviour; do not reuse it for a destination that is already known exactly.

The entrance is what makes that destination exact — one well-defined tile per building, which is then the single interface point for haulage, jobs and serviceability checks. Two consequences for #55's design:

  • Building.entrance_cell() should derive from anchor + a rotated entrance offset, the way #54 argues cells() should derive rather than be stored. The entrance must rotate under the same transform as the footprint, or a rotated warehouse has its door in a wall. The arrow-in-the-shape-string option gets this for free, because the arrow is parsed out of the same grid the cells are; the separate coordinate-plus-cardinal-direction option makes it two things that can be rotated inconsistently. That is an argument for the arrows beyond readability.
  • An entrance facing water, a cliff face or another building's wall is legally placeable and permanently useless. Wants a placement rule that checks the entrance tile for walkability and for A* connectivity to the rest of the map — which is only possible once this issue lands.

Tests

test/unit/test_terrain_navigation.gd — new, following the existing real-TerrainGrid-with-flat-amplitude pattern in test_placement_rules.gd:

  • Blocking a cell removes its A* point, and find_path() across it routes around rather than through.
  • Blocking then unblocking the same cell restores a path identical to the original — this is the test that catches the HALF_NEIGHBOURS asymmetry.
  • Unblocking restores connectivity in both directions: path A→B and path B→A both succeed.
  • A blocked cell is not returned by nearest_walkable().
  • Blocking a chokepoint leaves find_path() returning an empty array rather than erroring.
  • _main_region size shrinks by the number of blocked cells on the main landmass.
  • Blocking cells and then regenerating produces a graph consistent with whatever regeneration policy is chosen — pin the decision with a test rather than a comment.

Acceptance criteria

  • Blocked cells are excluded from the A* graph, and find_path() routes around a placed building instead of through it.
  • Unblocking a cell restores exactly the connectivity it had before it was blocked, in both directions.
  • _main_region is accurate after any block or unblock.
  • The blocked set and the terrain graph cannot disagree after reroll() / next_shape(), by whichever policy is chosen — and the choice is stated in the code, not implied.
  • Buildings never touches _astar directly.
  • The GUT suite passes, including the new navigation tests.
Placed buildings are currently invisible to pathfinding. `TerrainGrid._build_navigation()` runs once inside `generate()`, and `is_walkable()` asks exactly one question — is this tile water. Nothing in #54's registry touches the A* graph, so once buildings exist pawns will walk straight through them. This issue covers making the A* graph aware of occupancy, and picking where the blocked set lives. It does **not** cover pawn movement itself, job assignment or haulage — it is the substrate those need. ## The collider is a red herring #54 notes that the spawned mesh has no collider and that this is correct. Worth stating plainly why it does not matter here either: the colliders in `_build_mesh_library()` exist so the **mouse raycast** can hit the ground. Pawn movement never touches physics — `find_path()` returns a `PackedVector3Array` of tile centres and the pawn interpolates along them, and `Pawn` carries an `Area3D`, not a `CharacterBody3D`, so there is no collide-and-slide for a building to obstruct. **The A* graph is the only thing that will ever stop a pawn walking through a building.** Adding a collider would not fix navigation, and the missing one does not break it. Same shape of argument as the `OCCUPIED` rule in #54: no physics fallback is quietly covering for you. ## Scope In: - A blocked-cell set consulted by `is_walkable()`. - Incremental A* update on place and on remove. - Recomputing `_main_region` when the blocked set changes. - Deciding what happens to the blocked set on terrain regeneration. - Tests for all of the above. Out (each wants its own issue): - The entrance itself — that is #55. This issue only has to leave room for it. - Pawn re-pathing behaviour when a building lands mid-walk (noted under "Things that will bite"). - Movement costs / weighted tiles for roads and paths. - `blocks_movement` as a `BuildingType` field. ## Update the graph incrementally, do not rebuild it `AStar2D.remove_point()` removes the point *and* every connection attached to it, so blocking a building is one call per occupied cell and none of the cliff-edge or diagonal-corner logic needs re-running. Rebuilding the whole graph instead means an 8-neighbour sweep plus a flood fill over `grid_size^2` cells to avoid three or four `remove_point()` calls. **Re-adding is not symmetric with removing, and this is where the bug will be.** `_build_navigation()` connects using `HALF_NEIGHBOURS`, which is only correct because it is a full sweep where every adjacent pair gets visited exactly once from one side. Restoring a single cell must iterate `FULL_NEIGHBOURS` and test `_can_traverse()` for that cell against each neighbour, or the tile comes back reachable from the north and not from the south. Write the unblock path at the same time as the block path — the same argument #54 makes for putting `remove()` in the registry API before anything calls it. ## Where the blocked set lives `TerrainGrid` owns `_astar`. The #54 registry owns occupancy. Something has to join them. Three shapes, and the middle one is the recommendation: - **`Buildings` reaches into `_astar` directly.** Leaks the graph out of its owner; two places now maintain it. No. - **`TerrainGrid.block_cells(cells)` / `unblock_cells(cells)`.** `Buildings` says "these cells are blocked" and `TerrainGrid` never learns what a building is. A `_blocked: Dictionary` field, two methods, and `is_walkable()` gains `and not _blocked.has(cell)`. The graph stays in one place, and this does not foreclose the third option later. - **A separate `Navigation` node owning the A*, with `TerrainGrid` as a pure data provider.** Where this ends up if navigation grows costs, layers or tile reservations. A bigger refactor than this needs today. Dictionary-as-set for `_blocked`, following the existing house pattern (`BuildingFootprint._has_disjoined_cells()`, and #54's `_occupancy`). ## Things that will bite - **`is_walkable()` has three other callers**, and they all inherit the new answer: `_build_navigation()`, `nearest_walkable()` and `_find_largest_region()`. That is mostly what you want, but it means the blocked set has to be correct before any of them run. - **Terrain regeneration.** `reroll()` and `next_shape()` call `generate()`, which rebuilds the graph from terrain alone. A stale `_blocked` set now corrupts `_main_region` and therefore pawn spawning, not just the visuals — the same wart #54 flags about the registry not being cleared, but with teeth. Either clear both on `regenerated`, or re-apply the blocked set *after* `_build_navigation()`. Decide the ordering explicitly; do not let it fall out of signal connection order. - **`_main_region` goes stale on every placement.** It is computed once in `_build_navigation()` and is what `random_walkable_position()` spawns onto. Blocking cells can shrink it or split it in two. - **A building can disconnect the map.** Dropped across a one-tile isthmus or the only ramp between two levels, it splits the walkable region — pawns get stranded and a building's own entrance can become unreachable. Detecting it means a flood fill per candidate site, which is not affordable every frame while the ghost is hovering. Recommendation: **allow it.** The Settlers lets you wall yourself in too. `find_path()` already returns an empty array when no route exists, so make sure every caller treats empty as "no route" rather than as an error, and recompute `_main_region` after any block/unblock. Recorded as a decision so it is not discovered later. - **Existing paths go stale.** A path is a snapshot `PackedVector3Array`; placing a building mid-walk does not invalidate it and the pawn strolls through the new wall. The `GameState.building_placed` signal #54 adds is the hook — pawns re-path on it, or check waypoint validity as they go. Out of scope here, but the signal has to carry enough to make it possible. ## What this leaves for #55 Recorded here because the two issues constrain each other, not because any of it should be built in this one. A pawn can never stand on a building's cells once they are blocked, so "go to the mine" must resolve to a tile outside the footprint. **`nearest_walkable()` is the wrong tool for that** even though it looks like it fits: its Chebyshev ring search only asks "is this tile walkable", never "is it connected to me", so it will happily snap to a tile on the far side of the warehouse or across a cliff. Keep it for map clicks, where snapping to the shoreline is the desired behaviour; do not reuse it for a destination that is already known exactly. The entrance is what makes that destination exact — one well-defined tile per building, which is then the single interface point for haulage, jobs and serviceability checks. Two consequences for #55's design: - `Building.entrance_cell()` should derive from `anchor` + a rotated entrance offset, the way #54 argues `cells()` should derive rather than be stored. **The entrance must rotate under the same transform as the footprint**, or a rotated warehouse has its door in a wall. The arrow-in-the-shape-string option gets this for free, because the arrow is parsed out of the same grid the cells are; the separate coordinate-plus-cardinal-direction option makes it two things that can be rotated inconsistently. That is an argument for the arrows beyond readability. - An entrance facing water, a cliff face or another building's wall is legally placeable and permanently useless. Wants a placement rule that checks the entrance tile for walkability **and** for A* connectivity to the rest of the map — which is only possible once this issue lands. ## Tests `test/unit/test_terrain_navigation.gd` — new, following the existing real-`TerrainGrid`-with-flat-amplitude pattern in `test_placement_rules.gd`: - Blocking a cell removes its A* point, and `find_path()` across it routes around rather than through. - Blocking then unblocking the same cell restores a path identical to the original — this is the test that catches the `HALF_NEIGHBOURS` asymmetry. - Unblocking restores connectivity in **both** directions: path A→B and path B→A both succeed. - A blocked cell is not returned by `nearest_walkable()`. - Blocking a chokepoint leaves `find_path()` returning an empty array rather than erroring. - `_main_region` size shrinks by the number of blocked cells on the main landmass. - Blocking cells and then regenerating produces a graph consistent with whatever regeneration policy is chosen — pin the decision with a test rather than a comment. ## Acceptance criteria - Blocked cells are excluded from the A* graph, and `find_path()` routes around a placed building instead of through it. - Unblocking a cell restores exactly the connectivity it had before it was blocked, in both directions. - `_main_region` is accurate after any block or unblock. - The blocked set and the terrain graph cannot disagree after `reroll()` / `next_shape()`, by whichever policy is chosen — and the choice is stated in the code, not implied. - `Buildings` never touches `_astar` directly. - The GUT suite passes, including the new navigation tests.
Author
Owner

Correction: remove_point() is not sufficient, because of the corner rule

The body says blocking is "one call per occupied cell and none of the cliff-edge or diagonal-corner logic needs re-running". That is true for cliff edges and false for diagonal corners, and the difference is a pawn walking through the corner of a building.

AStar2D.remove_point() removes the point and every edge incident to that point. But _can_traverse() gives a cell influence over edges it is not an endpoint of:

var delta := to - from
if delta.x != 0 and delta.y != 0:
	var side_a := Vector2i(from.x + delta.x, from.y)
	var side_b := Vector2i(from.x, from.y + delta.y)
	if not _can_traverse(from, side_a) or not _can_traverse(from, side_b):
		return false

Take a blocked cell C = (10, 10) and the diagonal (10, 11) -> (11, 10). delta is (1, -1), so side_b is (10, 10) — C itself. Blocking C must close that diagonal, but C is neither endpoint of it, so remove_point(C) leaves the edge intact and pawns cut the corner.

Each cell affects four such edges: the ones joining its orthogonal neighbours in pairs, i.e. (cx-1, cy)-(cx, cy-1), (cx, cy-1)-(cx+1, cy), (cx+1, cy)-(cx, cy+1), (cx, cy+1)-(cx-1, cy). Every one of them has C as a side cell.

Consequence for the implementation

This makes the block path and the unblock path the same problem, which is convenient — the fix subsumes the HALF_NEIGHBOURS asymmetry the body already warns about, rather than being a second special case beside it.

Both paths become: update _blocked, add or remove the points, then re-derive every edge the change can reach. That last step is one function, shared:

## Re-derives every edge the given cells can affect. A cell affects its own
## eight edges *and* the four diagonals that squeeze past its corners, which
## are edges it is not an endpoint of - so remove_point() cannot be the whole
## story in either direction.
func _refresh_connections_around(cells: Array[Vector2i]) -> void:
	# For each changed cell, sweep the 3x3 block around it and re-test each of
	# those cells against FULL_NEIGHBOURS, connecting or disconnecting to match
	# _can_traverse(). The 3x3 is what makes the corner diagonals reachable:
	# their endpoints are the changed cell's orthogonal neighbours.

block_cells() and unblock_cells() then differ only in which way they write _blocked and whether they add or remove points. Neither carries bespoke edge logic, so neither can disagree with the other, and HALF_NEIGHBOURS stays confined to the full sweep in _build_navigation() where it is correct. _main_region is recomputed once at the end of each.

Sequencing

is_walkable() answers a compound question once this lands — land and not blocked — and unblock_cells() needs the terrain half of it. Update _blocked before consulting the graph, and there is no need to add a point speculatively and retract it:

for cell: Vector2i in cells:
	_blocked.erase(cell)          # the set is current...
for cell: Vector2i in cells:
	if is_walkable(cell):         # ...so this now answers on terrain alone
		_astar.add_point(...)

A cell that is water never gains a point, rather than gaining one and losing it again.

Tests

Pinned on the branch in test/unit/test_terrain_navigation.gd:

  • test_a_pawn_cannot_cut_the_corner_of_two_blocked_cells — fails outright against a pure remove_point() implementation. This is the test that catches the above.
  • test_unblocking_reopens_a_diagonal_it_had_closed — the same rule on the way out.
  • test_no_neighbour_still_connects_to_a_blocked_cell — asks the question from the neighbours' side rather than the blocked cell's.

One deviation from the body's test list, recorded here rather than left to a reviewer to spot: "blocking then unblocking restores a path identical to the original" is asserted as identical cost, not identical waypoints. The connections themselves are pinned exactly by test_unblocking_restores_exactly_the_connections_it_had, but AStar2D breaks ties between two equally short routes on internal ordering, so waypoint-for-waypoint equality would be asserting an implementation detail of the engine rather than of this issue.

Decisions taken

  • Regeneration clears the blocked set. generate() empties _blocked before _build_navigation(), and the registry clears on regenerated. A reroll is a new world; buildings whose anchors are now in the sea are meaningless, and a blocked set that outlives its terrain corrupts _main_region and therefore pawn spawning. Pinned by test_regenerating_clears_the_blocked_set.
  • The graph is driven by the GameState.building_placed / building_removed signals, not by Buildings calling map.block_cells() itself, so that rubble, reservations and hazards can block cells later without going through the registry.

The cost of that second one is worth stating, because #83 lands on it directly: the listener runs during the emission, so the graph is stale for the duration of the signal. Any other listener that paths inside its own handler gets the pre-placement answer, and listener order becomes load-bearing. #83's re-path handler must connect after the navigation listener, or defer a frame. The guarantee that does hold unconditionally is the weaker one: the graph is current by the time place() returns.

## Correction: `remove_point()` is not sufficient, because of the corner rule The body says blocking is "one call per occupied cell and none of the cliff-edge or diagonal-corner logic needs re-running". That is true for cliff edges and **false for diagonal corners**, and the difference is a pawn walking through the corner of a building. `AStar2D.remove_point()` removes the point and every edge **incident to that point**. But `_can_traverse()` gives a cell influence over edges it is not an endpoint of: ```gdscript var delta := to - from if delta.x != 0 and delta.y != 0: var side_a := Vector2i(from.x + delta.x, from.y) var side_b := Vector2i(from.x, from.y + delta.y) if not _can_traverse(from, side_a) or not _can_traverse(from, side_b): return false ``` Take a blocked cell `C = (10, 10)` and the diagonal `(10, 11) -> (11, 10)`. `delta` is `(1, -1)`, so `side_b` is `(10, 10)` — `C` itself. Blocking `C` must close that diagonal, but `C` is neither endpoint of it, so `remove_point(C)` leaves the edge intact and pawns cut the corner. Each cell affects **four** such edges: the ones joining its orthogonal neighbours in pairs, i.e. `(cx-1, cy)-(cx, cy-1)`, `(cx, cy-1)-(cx+1, cy)`, `(cx+1, cy)-(cx, cy+1)`, `(cx, cy+1)-(cx-1, cy)`. Every one of them has `C` as a side cell. ### Consequence for the implementation This makes the block path and the unblock path the *same* problem, which is convenient — the fix subsumes the `HALF_NEIGHBOURS` asymmetry the body already warns about, rather than being a second special case beside it. Both paths become: update `_blocked`, add or remove the points, then re-derive every edge the change can reach. That last step is one function, shared: ```gdscript ## Re-derives every edge the given cells can affect. A cell affects its own ## eight edges *and* the four diagonals that squeeze past its corners, which ## are edges it is not an endpoint of - so remove_point() cannot be the whole ## story in either direction. func _refresh_connections_around(cells: Array[Vector2i]) -> void: # For each changed cell, sweep the 3x3 block around it and re-test each of # those cells against FULL_NEIGHBOURS, connecting or disconnecting to match # _can_traverse(). The 3x3 is what makes the corner diagonals reachable: # their endpoints are the changed cell's orthogonal neighbours. ``` `block_cells()` and `unblock_cells()` then differ only in which way they write `_blocked` and whether they add or remove points. Neither carries bespoke edge logic, so neither can disagree with the other, and `HALF_NEIGHBOURS` stays confined to the full sweep in `_build_navigation()` where it is correct. `_main_region` is recomputed once at the end of each. ### Sequencing `is_walkable()` answers a compound question once this lands — land **and** not blocked — and `unblock_cells()` needs the terrain half of it. Update `_blocked` **before** consulting the graph, and there is no need to add a point speculatively and retract it: ```gdscript for cell: Vector2i in cells: _blocked.erase(cell) # the set is current... for cell: Vector2i in cells: if is_walkable(cell): # ...so this now answers on terrain alone _astar.add_point(...) ``` A cell that is water never gains a point, rather than gaining one and losing it again. ### Tests Pinned on the branch in `test/unit/test_terrain_navigation.gd`: - `test_a_pawn_cannot_cut_the_corner_of_two_blocked_cells` — fails outright against a pure `remove_point()` implementation. This is the test that catches the above. - `test_unblocking_reopens_a_diagonal_it_had_closed` — the same rule on the way out. - `test_no_neighbour_still_connects_to_a_blocked_cell` — asks the question from the neighbours' side rather than the blocked cell's. One deviation from the body's test list, recorded here rather than left to a reviewer to spot: "blocking then unblocking restores a path identical to the original" is asserted as identical **cost**, not identical waypoints. The connections themselves are pinned exactly by `test_unblocking_restores_exactly_the_connections_it_had`, but `AStar2D` breaks ties between two equally short routes on internal ordering, so waypoint-for-waypoint equality would be asserting an implementation detail of the engine rather than of this issue. ### Decisions taken - **Regeneration clears the blocked set.** `generate()` empties `_blocked` before `_build_navigation()`, and the registry clears on `regenerated`. A reroll is a new world; buildings whose anchors are now in the sea are meaningless, and a blocked set that outlives its terrain corrupts `_main_region` and therefore pawn spawning. Pinned by `test_regenerating_clears_the_blocked_set`. - **The graph is driven by the `GameState.building_placed` / `building_removed` signals**, not by `Buildings` calling `map.block_cells()` itself, so that rubble, reservations and hazards can block cells later without going through the registry. The cost of that second one is worth stating, because #83 lands on it directly: the listener runs *during* the emission, so the graph is stale for the duration of the signal. Any other listener that paths inside its own handler gets the pre-placement answer, and listener order becomes load-bearing. #83's re-path handler must connect after the navigation listener, or defer a frame. The guarantee that does hold unconditionally is the weaker one: the graph is current by the time `place()` returns.
Sign in to join this conversation.
No project
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
liamjd/UntitledColonyBuilder#56
No description provided.