Okay, first off, some disclaimers. This isn't an obvious bug. It may not even *be* a bug in the end - though it's certainly an obtuse mechanic that makes things much more difficult to understand. It's also as old as JtRH, so I can't say exactly how many things this would break if changed. It's also a very very *difficult* one to explain, since it's waist deep in pathmapping mechanics. You have been warned.
However, all that said, it's strange enough for me to bring it up. Anyways, let me explain the conditions first.
Attached is a picture of an example room. It features a brained waterskipper all the way to the west, and Beethro sitting on the top of an open door all the way to the east. The open door doesn't mean anything: I'm using it simply as a marker. In fact, the checkpoints and orthosquares also in the room are just markers too, and you'll hopefully see why in just a moment.
Now, the question is: where should the waterskipper go? Which square should it be attracted to? Well, in its little self-contained lake, only one tile is identifiably closer to Beethro than any other: the little niche directly east of the brain. So it should go there, right?
Nope.
Complicating things is the little water rivulet that's branches from the vertical river, and heads near Beethro. If that wasn't there, the waterskipper *would* head for the little niche we already pointed out.
So why doesn't it? Well, here's where it gets complicated.
If Beethro stands on the bottom section of the door, the waterskipper will head for the bottommost orthosquare in the lake. If Beethro stands on the top section of the door, the waterskipper will head for the topmost orthosquare in the lake. And the reason behind *this* is due to how the scoring of squares is calculated.
The Bottom Path
I've marked the "
fastest path"
from each square Beethro stands on to the square that the waterskipper gets attracted to. Checkpoints are marked every five tiles. You'll note the length of each path is 23 squares.
When building the pathmap, we start from Beethro who has a score of 0. Tiles around him have a score of 1, and tiles around them have a score of 2, and so on.
Tiles that move through obstacles, however, have a score of 1000 more than usual. So a tile that's five squares from Beethro that moves through five obstacles would have a score of 5000 + 5 = 5005. So far, so good.
However, obstacle tiles that are next to non-obstacle tiles... the score we try to give them is instead 1001 * the number of moves we've already made to get here. So if we were following a path of water that was 15 squares long, and then suddenly stepped off into an obstacle on the 16th tile, we'd have a score of 16016.
We can summarise such a score as "
16 obstacles, 16 moves"
. So a score of 5013 would be a tile that took 5 obstacles to move through, with 13 moves total.
For each tile in the room, we want the lowest score possible. This means that we want the least number of obstacles, and then we break ties with the least number of moves.
Now let's look at the room. For *every* square in the stream, the minimum number of obstacles we have to pass through to get to Beethro is 0: Beethro is already next to one of the connected squares in the stream. So the entire stream's best scores are all linked to the path leading along the stream to Beethro.
But the waterskipper isn't on the stream: it's in a lake disconnected from the stream. So eventually, we have to leave the stream and cross the bank of land seperating it to reach the waterskipper. This requires a move from a non-obstacle square to an obstacle.
The 4th Checkpoint along the bottom path is 20 squares from Beethro. The tile NW of it is an obstacle. The lowest score we can give it is 21021: 21 obstacles, 21 moves. That's because all our moves are converted to obstacles as soon as we move from a valid square to an obstacle.
The bottom orthosquare on the lake ends up with a square that is 23 squares from Beethro, across 22 "
obstacles"
. That means that every square in the lake is 22 obstacles away from Beethro, and the waterskipper will be attracted to that area near the bottom where the moves are minimized.
So that's the bottom path. Where does the top path factor in?
===
The Top Path
When Beethro stands on the north square of the door, the waterskipper is attracted to the NE corner of the lake. Why does one square make all the difference?
Well, the bottom path is now 24 tiles long, passing through 23 "
obstacles"
. So if we take that path, every tile in the lake would be 23 "
obstacles"
away from Beethro.
If we look across the top path, however, we can count another path that doesn't touch the stream at all: in fact, it skirts around it to the north. It reaches the lake after passing through 22 obstacles. It thus goes through less "
obstacles"
than the bottom path does, and so is a better path to the lake.
But why does it skirt the river? Because the river is a connected segment that is already 0 obstacles away from Beethro. We can't allocate a better score than that to the river. But the dogleg the river takes increases the number of *moves* necessary, and so any path we take through the river has a greater number of "
obstacles"
to pass through: remember that each move we make counts as another "
obstacle"
as soon as we move to a real obstacle.
===
So we have two paths. One that uses the river, the other that avoids it like the plague. The difference between choosing them is one square. Neither of them brings them the "
closest"
to Beethro. And *both* of them together are far too complex for a player to guess at.
So Is It A Bug?
Well, it's not exactly what the source says should happen:
The Source wrote:
//This line alters the search on entering an obstacle
//connected component. The practical effect is that only
//valid movement inside one's connected component is considered.
//In other words, the search may begin in an obstacle,
//then leave it, but on re-entering an obstacle, the path cost
//will be set as though it never left the obstacle.
While this could be describing a number of different things, the presence of the bottom path that uses the river demonstrates that it's definitely not as if it never left the obstacle: it would've been faster to just take a direct line and ignore the river altogether.
So. How could this be "
fixed"
?
Well, obstacles in the pathmap are only used for calculating the distance from Beethro, so that we can check the same tiles from different directions. The score on these obstacles is never used by the waterskipper when it wants to *move* onto that tile. So, we could set the score of each of these tiles to exactly how many moves from Beethro they are along the straight line, ignoring everything in between.
Valid non-obstacle tiles would be calculated as normal: they'd naturally get the best score starting from the obstacle tiles that are closest to Beethro. Disconnected segments would no longer affect each other, because the score of all obstacles would not be based on what non-obstacles were between.
So, the changed code would possibly look something like this in the CalcPaths routine of PathMap.cpp:
//Calculate total distance score to this square (along path from current square).
UINT dwScore = coord.dwScore + 1; //one more step has been taken
if (square.eState == obstacle)
{
//invalid regions are marked by distance to the target, if possible
if (this->xTarget < this->wCols && this->yTarget < this->wRows)
{
const UINT dist = nDist(wNewX,wNewY,this->xTarget,this->yTarget);
dwScore = dist * (this->dwPathThroughObstacleCost + 1);
}
else
{
//use (probably) higher cost for considering a path through an invalid region
if (this->squares[GetSquareIndex(coord.wX, coord.wY)].eState == obstacle)
dwScore += this->dwPathThroughObstacleCost;
else
//Old way of calculating score of valid->obstacle tiles.
dwScore = (coord.wMoves+1) * (this->dwPathThroughObstacleCost + 1);
}
}
Note that the use of nDist in this change means that GameConstants.h would need to be included, or the definition of nDist would need to be restated for PathMap.cpp. I wasn't sure of an easier method of doing that, so I went with the #include.
===
So that's the specifics of the bug and the proposed change. But now the more important points: the pros, cons and other effects of actually doing it.
Why Should It Be Changed?
* It's an unnecessary complication to the rules that makes the movement of brained seep and waterskippers much harder to predict.
* The only rooms that should break at all are those where there are multiple isolated segments of wall/water are various strange dog-legged shapes, and Beethro is usually away from connected segments of wall/water where seep or waterskippers lurk. And it'd be difficult for the room to break in such a way as to make it impossible, unless the room was wholly designed around the exact movements of the seep/waterskippers.
Why Shouldn't It Be Changed?
* As said before, it's as old as JtRH, and it's difficult to know how many published rooms actually already make use of it. I did a test on TCB and a few other holds I have on my computer: the only room that broke out of them was Oremite Breeding Grounds: 2N in TCB. And it wasn't a huge break: I was able to go in and redo the room with about the same strategy as before. But that's just a tiny portion of the whole that could be affected: seeps are more prolific and more likely to be affected (since walls and doors are *everywhere*) by this.
* It's mostly unnoticed by the large majority of players, though this may be due to a general lack of understanding on how brains work, and the requirements of making a room that demonstrates this effect.
* Maybe the way they move now is useful - it might get seep closer to a door that will close later, or allow them to congregate near a corner that Beethro will later turn. But with both things happening together, this can make for a rather difficult to understand mechanic....
* Even though the requirements of getting it to happen are somewhat rare, it's still difficult to predict exactly what rooms the change will affect without just manually seeing what demos break.
So, yeah. In my opinion, there's certainly reasons either way to change it or leave it alone. It's the kind of thing I'd like to see fixed to make things easier to think through without actually having to walk everywhere and see how things change depending on my position. On the other hand, I'm not sure of the full ramifications such a change would make. (Although at least it doesn't seem as entrenched a mechanic as Slayer Wisp/Halph/Stalwart movement is, which pretty much *defies* exact explanation)
Anyways, if any further clarification is needed on this, feel free to ask.