search

ameisen / SV-SpriteMaster

SpriteMaster Mod for Stardew Valley
Mozilla Public License 2.0
13 stars 11 forks source link

OptimizeWarpPoints = true breaks pathfinding #13

Closed Yagisan closed 2 years ago

Yagisan commented 2 years ago

This was an interesting bug to track down, and is present in both 0.14.0 and 0.15.0-alpha.1

After a certain number of new locations are added, when OptimizeWarpPoints = true, pathfinding is broken on the Juliet & Jessie ClearingHouse map.

Please see this video 1:31 to see the behaviour with OptimizeWarpPoints = true

When OptimizeWarpPoints = false pathfinding works correctly.

Please see this video 1:26 to see the behaviour with OptimizeWarpPoints = false

This issue has been difficult to track down, as without a certain number of mods, it behaves like OptimizeWarpPoints = false.

I have prepared the minimum number of mods that I needed to reproduce this bug here 140MB

I am happy to test any debugging builds of SpriteMaster to help track down this issue.

Yagisan commented 2 years ago

I have replicated this in 0.15.0-Alpha.2

ameisen commented 2 years ago

Relevant timestamps in videos:

https://youtu.be/F0UT5utYOJ0?t=66

https://youtu.be/lLH-lVia7wk?t=68

ameisen commented 2 years ago

This was due to the pathfinding code using a stable priority queue, and pre-loading it with all locations (with their distance set to int.MaxValue as a sentinel).

This resulted in updating their positions in the queue not honoring warp/door order within a location - that is, if a location had [A, B] in their warps, but the original order in the queue was [B, A], they would retain the [B, A] order in the queue if their priority were the same. This resulted in a divergence in behavior from vanilla code.

This is fixed in 51836e1b344258b665b82f004d34a5d2aecb133e.

Yagisan commented 2 years ago

Thank you. I've confirmed this is fixed.