Repository navigation
navigation: re-copy the rooms around the player on a cached getPath - #98
Merged
Merged
Conversation
Reference d2bs reads collision from the rooms on every getPath (ActMap::GetMapData -> getCollFromRoom), so a path asked for after a door opens goes through it. FindPath kept each level's collision slab for the whole game, so a repath after Pather.openDoors still saw the door closed. On a cache hit FindPath now re-copies the player's room and its nearby rooms into the cached primary / secondary grids (barricade marks included). Collision only changes where the game has units, which on the client is around the player; those rooms are loaded, so the refresh adds no room data and costs a handful of room copies per call. Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>
ResurrectedTrader
force-pushed
the
getpath-live-collision
branch
from
October 8, 2026 10:57
20200a2 to
b573e5f
Compare
CopyRoomCollision and MarkBarricades become LevelGrid members. Barricades are marked once, after every room's collision is copied, so a later room copy can no longer overwrite a tower mark; MarkBarricades checks the level's overlay itself. Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>
Owner
Author
|
Done in the latest commit:
Perf: the pathfinding benchmarks (150 timings of our A*) are within noise against main, +0.9% total, while the unchanged reference A* in the same runs swings by up to ±13%. The benchmarks time the search on prebuilt grids, so they don't exercise the per-call refresh this PR adds. Build, tests (171/171) and format check pass. |
A level's rooms do not overlap and a tower sits inside its own room, so marking right after the room's copy is always correct. CopyRoomCollision does both; MarkBarricades becomes a private per-room helper, and the callers just copy rooms. Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>
Owner
Author
|
Reworked as discussed:
Perf, our A* across 150 benchmark timings, Build, tests (171/171) and format check pass. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
d2bs:
getPathreads collision straight from the rooms on every call (reference/d2bs/Map/Diablo_II/ActMap.cpp,ActMap::GetMapData->getCollFromRoom, which readsroom->pRoom1->Coll). A path asked for after a door opens goes through the door.d2bsng before:
FindPath(src/runtime/components/navigation/Pathfinder.cpp) builds a level's collision slab once and keeps it per thread until the level or the map seed changes. A code comment accepted that "doors opening / collision changes inside the same level aren't reflected". So kolbot'sPather.openDoorsfollowed by a repath still saw the door closed.Fix: on a cache hit,
FindPathre-copies the player's room and its nearby rooms (Unit::GetRoom+Room::GetNearby) into the cached grids, primary or secondary by level, and re-applies the barricade-tower marks for those levels. On the client, collision only changes where there are units, which is around the player, and those rooms are already loaded, so the refresh adds no room data. The full-level build still happens once per level and game, which keeps the burst cost the cache was added for (e.g.Attack.getIntoPosition's fan-out) low. Navigation still depends only on contract + utils.BuildLevelGridis split intoCopyRoomCollision/MarkBarricadeshelpers so the refresh uses the same copy. The test fakes gain aUnit::GetRoomstub (the test suite linksPathfinder.cpp).Cost: each cached call now copies about 10-25 rooms of 40x40 cells (tens of KB) under one read lock - microseconds, against 1-40 ms per A* in the existing benchmarks. The benchmarks (
js_tests.exe -tc="Benchmark*,Kurast*,Real*") runFindPathOnGridon fixture grids and do not exercise this path; their numbers are unchanged (e.g. real-map walk 1.0-4.1 ms, Flayer Jungle -> Travincal 38 ms).Restores: repathing after opening a door (kolbot
Pather.openDoors, thengetPathagain) finds the path through the opened door.There is no unit test: the fakes have no room model to change collision in. Not live-tested. Built Win32 Release,
build.ps1 testpasses,check-formatclean.🤖 Generated with Claude Code