Announcement: Be excellent to each other.


Caravel Forum : DROD Boards : Bugs : Brained Seep/Waterskipper Pathmapping Complications
New Topic New Poll Post Reply
Poster Message
TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

File: pathmap.jpg (107.2 KB)
Downloaded 166 times.
License: Public Domain
icon Brained Seep/Waterskipper Pathmapping Complications (+4)  
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.
02-04-2008 at 05:29 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Remlin
Level: Master Delver
Rank Points: 181
Registered: 04-28-2005
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (0)  
I'm not sure if I can tell what type of terrain is underneath those orthosquares. The top path is all floor, with one wall, and the westernmost square is water? And the bottom path is all water, except two bits of floor between the lake and the stream?
02-04-2008 at 05:59 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (0)  
Yes, that's correct. I probably shouldn't have used lighting to try and further highlight the path, but I wasn't sure if it was visible enough without it. I can upload a version without the lighting (just the orthosquares and checkpoints marking the path) if that would be more useful. (I used the textured water to help differentiate it from the land, which seemed good enough already)

EDIT: After further thought, I note I should correct one claim I made. Sometimes I forget the same things I try to teach:

TFMurphy wrote:
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.

This isn't entirely true: I forgot about brain-visible obstacles that waterskipper/seep could still move across: namely Force Arrows and Scrolls.

With the proposed change, they would instead act a little as if unbrained when over Force Arrows, unless they see a "faster" way off the obstacles. This is somewhat similar to a roach in the same position, except that the waterskipper/seep would still use brained movement preferences rather than their unbrained preferences. (The roach, instead, would be completely unbrained until it got to a path out of the Force Arrows/Scrolls) By comparison, without the change, I'm not sure I could easily predict where they'd want to go - they tended to react somewhat unbrained anyways in that situation due to the valid->obstacle score calculation. It's possible that there isn't much difference between the two regarding this situation, but it's difficult to be sure.

As far as I can see, the fix I listed in the first post doesn't significantly change how brained seep and waterskippers treat Force Arrows, but I could (as always) be missing certain fringe cases. Someone with access to more demos might be able to better answer that however.

[Last edited by TFMurphy at 02-04-2008 07:28 PM]
02-04-2008 at 06:01 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Briareos
Level: Smitemaster
Avatar
Rank Points: 3517
Registered: 08-07-2005
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (+1)  
TFMurphy wrote:
I can upload a version without the lighting (just the orthosquares and checkpoints marking the path) if that would be more useful. (I used the textured water to help differentiate it from the land, which seemed good enough already)
Ummm... is there any reason you can't simply attach a hold with just this one room? That way everyone can experience what you describe on their own...

Just my 2 EYPO-cents...

np: Pole - The Bell (Pole)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009) :(

[Last edited by Briareos at 02-04-2008 08:12 PM]
02-04-2008 at 08:09 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts Quote Reply
Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (0)  
Briareos wrote:
TFMurphy wrote:
I can upload a version without the lighting (just the orthosquares and checkpoints marking the path) if that would be more useful. (I used the textured water to help differentiate it from the land, which seemed good enough already)
Ummm... is there any reason you can't simply attach a hold with just this one room? That way everyone can experience what you describe on their own...

Just my 2 EYPO-cents...

np: Pole - The Bell (Pole)
Well I for one would not have downloaded it. Both options would be good though.

[Last edited by Syntax at 02-04-2008 08:36 PM]
02-04-2008 at 08:26 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

File: Pathmap Tests.hold (1.2 KB)
Downloaded 48 times.
License: Public Domain
icon Re: Brained Seep/Waterskipper Pathmapping Complications (+2)  
Fair enough. I've cleaned up the hold slightly and exported it. Play New Game brings you to the room shown in the screenshot. In the Editor are three other rooms: the second one is the same as the first but without the little river, thus demonstrating that the waterskipper does go into the niche without that there. The third and fourth were some testing rooms for some other things I was working on while exploring all this.

===

Whilst I'm discussing seep, I might as well bring up this quote in the source, located in the GetBrainDirectedMovement routine in Monster.cpp:

The Source wrote:
//2. Wall monsters should not beeline when brain-directed moves don't work,
//as this could take them away from the target, according to the search cost heuristic
//(causing oscillations).

Unfortunately, the check used for this is "if (... || (this->eMovement == WALL && i==paths.size()-1))". So the routine would have to check all paths first. Which is fine, except that the very first check that is done to each path checks whether it is an order to Wait. And since obstacles are still considered paths in the Wall Pathmap, there will always be a Wait path.

Any order to Wait automatically breaks the routine and tells the monster to use their own unbrained instincts. So the Seep *will* beeline if told to Wait, and will never get as far as this second check at the end to stop it from beelining.

So, the possibilities:
1) Remove the check and the source comment. It's not working, so it's not necessary.
2) Allow seep to obey the Wait command from Brains - this would have the same effect as what this extra check was trying to do, since there'll always be a Wait command.
3) Prevent seep from ever checking Wait paths. They'll keep going and check diagonals that could take them farther from their target than waiting would though, but it'd get to that final check in the end if all other paths are blocked.

#1 is the least invasive, since it's just source cleanup. I'm not sure of how the other two options would impact things, however: the only time a difference would occur is if the unbrained direction takes the seep further away from where the brain says the seep should be, and that rarely happens except with strange shaped walls combined with hordes. Still, thought I'd mention it, since it seems to be just clutter at the moment.
02-04-2008 at 08:33 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Briareos
Level: Smitemaster
Avatar
Rank Points: 3517
Registered: 08-07-2005
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (+1)  
Syntax wrote:
Well I for one would not have downloaded it. Both options would be good though.
Because you can't get a #1 score for it? ;)

np: Pole - Like Rain (But Different) (Pole)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009) :(
02-04-2008 at 09:09 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts Quote Reply
Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (0)  
Briareos wrote:
Syntax wrote:
Well I for one would not have downloaded it. Both options would be good though.
Because you can't get a #1 score for it? ;)

np: Pole - Like Rain (But Different) (Pole)
Probably right :)
02-04-2008 at 09:36 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
coppro
Level: Smitemaster
Rank Points: 1309
Registered: 11-24-2005
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (0)  
I'm against this for backwards compatibility.

That's why brained monsters think arrows aren't navigable, and why tar won't grow over various room features (like orthosquares and arrows). If we fixed something just because we can now, we'd invalidate way too many demos.
02-05-2008 at 12:37 AM
View Profile Show all user's posts Quote Reply
mrimer
Level: Legendary Smitemaster
Avatar
Rank Points: 5471
Registered: 02-04-2003
IP: Logged
icon Re: Brained Seep/Waterskipper Pathmapping Complications (0)  
Ugh...I agree there is a convoluted issue or two here, but I'm not sure what we want to do. I think I'm for cleaning up the dead code paths and not changing anything that would affect backwards compatibility.
03-01-2008 at 06:45 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : DROD Boards : Bugs : Brained Seep/Waterskipper Pathmapping Complications
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.9
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.