🎼 Battle 2
Note 1 has a bug in the final algorithm. Here it is again:
func collect(x, y, d int) {
if inHighlightSet(x, y) {
return
}
c := tileCost(x, y)
if c > d {
return
}
addToHighlightSet(x, y)
collect(x - 1, y, d-c)
collect(x + 1, y, d-c)
collect(x, y - 1, d-c)
collect(x, y + 1, d-c)
}Can you spot the problem now that I've pointed out that it exists? I've been testing with totally random terrain and didn't notice it until I looked at a featureless field of grass, but this is wrong enough to create some wacky-looking traversal zones.
The error is the early return in the case of the coordinate already being present in the highlight set. This is a problem, because each tile can be reached by multiple paths of differing costs, and if the algorithm reaches a tile by an expensive path first (seeing that tile as the terminus of the path), a cheaper path (with more movement to spare) won't examine the tile and fan out to adjacent, traversable tiles, leading to them being omitted from the set.
For now, I've simply removed the set check (which means lots of redundant calls to collect, which is what I was trying to avoid in the first place), but at least one possible fix should be simple enough: Instead of a set, use a map from tile coordinates to the highest d seen at the associated tile, and skip the current collect call only if the current d is not higher. There will still be redundant checks, but it should be an improvement over testing every possible path.