Placed buildings must block pathfinding #56
Labels
No labels
assets
bug
duplicate
enhancement
help wanted
invalid
question
testing
ui
wontfix
No milestone
No project
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set.
Reference
liamjd/UntitledColonyBuilder#56
Loading…
Add table
Add a link
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Placed buildings are currently invisible to pathfinding.
TerrainGrid._build_navigation()runs once insidegenerate(), andis_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 aPackedVector3Arrayof tile centres and the pawn interpolates along them, andPawncarries anArea3D, not aCharacterBody3D, 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
OCCUPIEDrule in #54: no physics fallback is quietly covering for you.Scope
In:
is_walkable()._main_regionwhen the blocked set changes.Out (each wants its own issue):
blocks_movementas aBuildingTypefield.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 overgrid_size^2cells to avoid three or fourremove_point()calls.Re-adding is not symmetric with removing, and this is where the bug will be.
_build_navigation()connects usingHALF_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 iterateFULL_NEIGHBOURSand 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 puttingremove()in the registry API before anything calls it.Where the blocked set lives
TerrainGridowns_astar. The #54 registry owns occupancy. Something has to join them. Three shapes, and the middle one is the recommendation:Buildingsreaches into_astardirectly. Leaks the graph out of its owner; two places now maintain it. No.TerrainGrid.block_cells(cells)/unblock_cells(cells).Buildingssays "these cells are blocked" andTerrainGridnever learns what a building is. A_blocked: Dictionaryfield, two methods, andis_walkable()gainsand not _blocked.has(cell). The graph stays in one place, and this does not foreclose the third option later.Navigationnode owning the A, withTerrainGridas 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.reroll()andnext_shape()callgenerate(), which rebuilds the graph from terrain alone. A stale_blockedset now corrupts_main_regionand therefore pawn spawning, not just the visuals — the same wart #54 flags about the registry not being cleared, but with teeth. Either clear both onregenerated, or re-apply the blocked set after_build_navigation(). Decide the ordering explicitly; do not let it fall out of signal connection order._main_regiongoes stale on every placement. It is computed once in_build_navigation()and is whatrandom_walkable_position()spawns onto. Blocking cells can shrink it or split it in two.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_regionafter any block/unblock. Recorded as a decision so it is not discovered later.PackedVector3Array; placing a building mid-walk does not invalidate it and the pawn strolls through the new wall. TheGameState.building_placedsignal #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 fromanchor+ a rotated entrance offset, the way #54 arguescells()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.Tests
test/unit/test_terrain_navigation.gd— new, following the existing real-TerrainGrid-with-flat-amplitude pattern intest_placement_rules.gd:find_path()across it routes around rather than through.HALF_NEIGHBOURSasymmetry.nearest_walkable().find_path()returning an empty array rather than erroring._main_regionsize shrinks by the number of blocked cells on the main landmass.Acceptance criteria
find_path()routes around a placed building instead of through it._main_regionis accurate after any block or unblock.reroll()/next_shape(), by whichever policy is chosen — and the choice is stated in the code, not implied.Buildingsnever touches_astardirectly.Correction:
remove_point()is not sufficient, because of the corner ruleThe 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:Take a blocked cell
C = (10, 10)and the diagonal(10, 11) -> (11, 10).deltais(1, -1), soside_bis(10, 10)—Citself. BlockingCmust close that diagonal, butCis neither endpoint of it, soremove_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 hasCas 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_NEIGHBOURSasymmetry 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:block_cells()andunblock_cells()then differ only in which way they write_blockedand whether they add or remove points. Neither carries bespoke edge logic, so neither can disagree with the other, andHALF_NEIGHBOURSstays confined to the full sweep in_build_navigation()where it is correct._main_regionis recomputed once at the end of each.Sequencing
is_walkable()answers a compound question once this lands — land and not blocked — andunblock_cells()needs the terrain half of it. Update_blockedbefore consulting the graph, and there is no need to add a point speculatively and retract it: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 pureremove_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, butAStar2Dbreaks 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
generate()empties_blockedbefore_build_navigation(), and the registry clears onregenerated. 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_regionand therefore pawn spawning. Pinned bytest_regenerating_clears_the_blocked_set.GameState.building_placed/building_removedsignals, not byBuildingscallingmap.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.