Dragon Fogel
Level: Smitemaster
Rank Points: 2584
Registered: 06-21-2014
IP: Logged

Constructs cannot move over oremites under their own power, but brains ignore this.

While it's true that brains don't take everything into account, in all other cases they at least pay attention to whether the monster can move over the floor tile type they're detecting.

I had a quick look and there are only seven rooms with constructs, brains, and oremites. None of them rely on this behavior, though individual demos might break.

It's uncommon enough that I didn't realize it was the case until I tried to make a room about using oremites to create separate pathmaps for a construct and another monster.

skell
Level: Legendary Smitemaster

Rank Points: 3776
Registered: 12-28-2004
IP: Logged

Quoting TFMurphy from the private DROD 5 Development forum:

As of v5151, Constructs will refuse to cross oremites, even to kill something standing there. Since they have Flexible Flanking movement, they will tend to circle a player standing on one to the NW (maybe we'd want to remove the Flank and just leave them with Flexible Beelining?) Brains don't understand oremites to be an obstacle to Constructs and so they will still pick out paths that lead through them, but just like a normal monster being ordered to step on something they don't like, Constructs will refuse and ask for another square, just as normal.

It was certainly known behavior.

One explanation for this behavior could be that brains just can't conceptualize the idea of not being able to move over oremites, just like they can't understand serpent's inability to move diagonally, or gentryii being able to walk over active firetraps. Which for me isn't any more outrageous than the explanations offered here and brained monsters interactions with Stalwarts.

Please discuss whether this should stay or not. Fixing it is not a huge pain, though I hate the idea of doing it this close to 5.1.1 release, but I'd rather get it done now than later. I also may have a different perpective on this because I am familiar with the code and this (and other brained monster inconsistences) is direct consequences of how pathmaps are coded.

____________________________
My website

Dragon Fogel
Level: Smitemaster
Rank Points: 2584
Registered: 06-21-2014
IP: Logged

Gentryii avoiding firetraps is a "false negative" - a monster concluding that it can't move into a tile when it actually can.

The oremite behavior is a "false positive" - a monster trying to move into a tile when it can't.

We have a lot of examples of both, because brain pathmaps are fairly simplistic by design, but while there is at least one similar example of a false negative, there's nothing comparable in terms of false positives.

A similar false negative is just a tile with a toggleable force arrow on it. If the force arrow is off, brained monsters will move on the tile freely. If it's on, brained monsters won't move onto the tile even if the direction of the arrow would allow them to.

But there are no other false positives based on tile type. Most are based on things that are much more changeable - whether a tile has a sword or a monster in it, for instance. One of the few exceptions is orthosquares - but even there, the false positive is coming from the state of the tiles around it, not the orthosquare itself. You can construct a room where a pathmap goes through an orthosquare and it doesn't cause any problems because the monster enters and leaves the orthosquare through orthogonal directions. Same situation with a snake going through a diagonal-only path - the issue isn't with the diagonally-linked tiles, technically, but with the fact that the brain isn't accounting for the tiles around them.

Here, the false positive is that the brain is telling a monster to cross a tile that it cannot cross, ever, even if the tiles around it are somehow changed, unless a citizen or build command alters the tile itself. There's no other situation where this happens.

Nuntar
Level: Smitemaster

Rank Points: 4981
Registered: 02-20-2007
IP: Logged

The brain pathmap has well-known weaknesses, such as the fact that it sends serpents on a path that assumes they can move diagonally. But one thing it does understand and handle correctly, in all other cases, is which monsters can move on which floor types -- it directs spiders across shallow water but not roaches, and it has separate pathmap for seep and waterskippers that pathfind through walls and water respectively.

The natural expectation is that constructs should be able to pathfind around oremites, and anything else is a bug that should be fixed. I am honestly astonished that it's taken so long for this to come to light, but at least that means that fixing it won't affect very many published rooms.

____________________________
50th Skywatcher

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

I've been thinking about this topic for almost a week now, but kept putting off the ~30 min it would take to write up my feelings on the matter. But I did really want to add something here, so let's see if I can put my thoughts in order. (It's so much easier to write these things in my head when I'm at work all day, but it all gets so hard once you have the window open and want to start....)



It's certainly a compelling argument that brains should always consider the base floor types of each entity they direct. Of course, it's not the only way to internalise understanding of the brain's rules. Like skell, I'm more familiar with the way the pathmaps are generated, so it seemed perfectly fine to me for the brain to continue a sort of "one size fits all", where it shoves monsters into broad categories and gives them advice based on that, not caring when it fails. Snakes are the poster child of that, and Constructs fitting broadly into the Ground+Shallow Water map with a single exception did not feel far from that at all.

I'd also note that other than the big exceptions of Wall and Water, the current pathmaps all use Ground as a 'base subset', so much that Air/Shallow Water just seemed like natural extensions of them. What's being discussed here isn't "Ground+<something>" though, it's "Ground-<something>"... and that feels like it could be an exception too.



Still, like I said, it's a compelling argument. The base 'meta' rules for determining how brains work are clearly debatable, and I don't see a big reason why Constructs couldn't have their own unique map. But, what concerns me is the immediate consequences of that.

Currently, Constructs are given a standard Ground+Shallow Water pathmap. This means that they will pathfind through oremites, even though they can't walk over them. This has some obvious disadvantages: Constructs can't properly navigate gaps between oremites when brained as a result.

But excluding Oremites outright impacts other things. Currently, if you stand in the middle of a large area of oremites, then Constructs will usually be able to get to the edge and remain close enough to possibly be trouble when you finally move off them. Alternatively, if you move past a barrier of oremites into another section of the room closed off from the rest, the Constructs can usually pathfind their way towards their side of the Oremites and be there when you want to cross over again. If Oremites were removed from a Construct pathmap, they would instead become unbrained in both cases. This is a fairly large difference in current behaviour, and it doesn't quite feel right to me -- I feel like the Ground pathmap is so basic to what a brain already directs, that they should at least be able to get a Construct close enough to the player.



So... I have a addition to propose to this, should Constructs get their own pathmap at all, and that is the following: The new Construct pathmap should be able to path through Oremites, but at a vastly increased cost such that any non-Oremite path is prioritised.

In short, I'm proposing that a partial ruleset similar to what the Wall/Water pathmaps apply to all obstacles, is used by the Construct pathmap to apply to Oremites only. This would result in Constructs being able to navigate Oremite mazes easily, but still be able to track the player even if they've put path-blocking Oremites between them (as they currently do).

In this way, we get to apply the 'meta' understanding that brains always understand the base floor types of all enemies, as well as a possible 'meta' addition that pathmaps that are restricted in some way from crossing certain Ground tiles gain some method of pathfinding through obstacles. (In a similar manner, if we ever had a monster who could walk over all Ground tiles except Bridges, I would expect the brain to help it guard the only bridge leading to you.)



This wouldn't be a trivial change to make to the codebase in comparison to just adding a new pathmap, but it also wouldn't be that difficult either (I've had some thoughts on how it would be implemented, but I'm not going to have a DROD compiler running any time soon, so best I could contribute on that front is pseudocode or code snippets that someone else would have to debug/test). But if it needs to be delayed to 5.2, then I think that's fine -- I'd rather this be discussed and dealt with properly, rather than some change made quickly and then we regret not having done something else later.

bbb
Level: Master Delver
Rank Points: 218
Registered: 10-07-2013
IP: Logged

I agree agree with TFMurphy's sentiments, but not with his suggestion. The way I see it, the difference between the ground based pathmaps and wall/water maps is that Beethro shares the domain with the monsters, so the monster is trying to reach Beethro, while the wall/water monsters live somewhere else, so the monster is trying to come close to Beethro to be ready when Beethro reaches the border.

I would suggest either having the pathmap consider only oremite tiles within 5 tiles of the construct, or ignore only oremite tiles 5 tiles of Beethro.

Dragon Fogel
Level: Smitemaster
Rank Points: 2584
Registered: 06-21-2014
IP: Logged

bbb's suggestion sounds like it would be more complicated on the player end.

1000 tiles is a ridiculous amount considering that a room is roughly 1100 tiles total. There's just not enough space to make an obstacle-free path that's longer than an obstacle path.
Because of this, an observant player can notice that a seep will move towards a wall if they're next to a wall, but will still make brained moves if they're not, which is generally all you need to know to solve a room where you need to use the behavior. Under this proposal, oremites would work the same way for constructs.

Mind you, I'm fine with either TFMurphy's approach or the "brain doesn't pathfind over oremites at all" approach. I just think brained constructs should treat oremites as a problem.

hyperme
Level: Smitemaster

Rank Points: 1263
Registered: 06-23-2006
IP: Logged

This was brought to my attention, so I'm bumping it back up. My thoughts are that TFMurphy's idea of having Constructs treat oremites as very expensive tiles is a good idea.

From a game perspective, Seep already treat the maximally lethal floor tiles as brain-pathable, so Constructs treating the only mostly-lethal oremites as pathable but undesirable isn't out of nowhere.

From a flavour perspective, Constructs are meant to be smarter than the average monster, so it makes some sense that if a brain tries to send them over oremites when another path is available, the Construct will go the safer way.

____________________________
[Insert witty comment here]
Qzvlkx?

mrimer
Level: Legendary Smitemaster

Rank Points: 5200
Registered: 02-04-2003
IP: Logged

PR

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

Had a quick look over this out of the sake of curiousity, since I was wondering how someone else might got about implementing it. I liked the approach taken, but I noticed two things that should be mentioned.


First, I think there's a fairly serious bug: the new DMASK_SEMI has been defined as 0x16. Since these are bitwise constants, it means it's not a different bit to the rest of the masks, but instead the combination of DMASK_NE, DMASK_E and DMASK_S. That's going to instantly cause some issues with Oremites being considered pathmap obstacles (instead of semi-obstacles) when approached from some directions over others, and might cause problems with Horn pathmapping too.

Fix is fairly obvious of course: just needs to be defined as a new bit such as 0x100. eBlockedDirections is an UINT so there's no problem with having a 9th bit. (Might need to be wary about any code elsewhere that do direct comparisons to DMASK_ALL though, since "square.eBlockedDirections != DMASK_ALL" would return true if both DMASK_ALL *and* DMASK_SEMI is set.)



Secondly, we probably need a bit of a discussion on exactly what route a Construct wants to take if the only available paths go through Oremites. I kinda glossed over that with my suggestion by simply saying "a vastly increased cost", but when the only paths that remain are those that go through semi-obstacles (Oremites in this case), we still need a way to prioritise which of possibly several 'blocked paths' the Construct should head towards.

The initial implementation of one such system in the PR is different to what I'd originally imagined. It's also different to how Seep/Waterskippers handle it, but I'm kinda fine with it being different because, frankly, Seep/Waterskipper pathfinding is rather horrid (as I'll remind everyone in more detail in a bit). That said, the PR's implementation feels strange to me, so I figured it's worth taking the time to outline some possible choices.



In total, I'm going to go over 4 possible priority systems. Each of these systems will have the following things already in common: No path may go through a brain-visible obstacle and The construct will always prioritise a path that avoids all semi-obstacles, where 'semi-obstacle' refers to Oremites in this case. So we'll be looking at the differences that occurs only when the only paths that exist must go through at least 1 semi-obstacle.

One other thing to note is that each system can be described in two different ways. The first is the Pathmap Rule, which is the exact rule applied to how the pathmap is built and scored. This is what is actually coded into the game, since brain pathmaps are built by starting at the goal (the player) and applying scores to every valid tile around him and progressing from there.

The second is the Observed Result, which is basically the consequences of applying the Pathmap Rule when looked at from a single monster's perspective. In other words, once the Pathmap has been built, if we follow the scores backwards, a monster will be directed along a certain path to particular tiles, and these can be described as observed preferences. These aren't directly coded into the game, but they are the result of having coded the Pathmap in a particular way.

The Pathmap Rule is easier to think about from a programmer's perspective, but the Observed Result is generally what a player will find easier to remember when they're trying to figure out how a particular enemy will move.



System 1 - Current Implementation

The current system in 5.2 uses the following Pathmap Rule: Add an Obstacle Cost when moving from a non-obstacle to a semi-obstacle. The cost for a single Step is 1, while an Obstacle Cost adds 1000 to that for a total of 1001 (which we can read as 1 Step, 1 Obstacle). This means going from Floor to Oremite will cost an extra 1000, but going from Oremite to Oremite or Oremite to Floor is not penalized.

The Observed Result from this when there are only paths that go through semi-obstacles would therefore seem to be the following: A Construct will prioritise paths that minimize the number of connected semi-obstacle groups it moves through.

This means that a path that is blocked by a group of 10 connected Oremites tiles would be prioritised over one that is only blocked by 3 Oremite tiles that each have a Floor tile between them, even if Beethro is standing right next to the '3 Oremite tile'-blocked path. This is why this particular system feels a bit off to me, and why I felt it merited some more discussion.



System 2 - Seep/Waterskipper Rule

The system used by the Wall/Water Pathmaps to navigate Obstacles could be adapted for semi-obstacles too. That would result in the following Pathmap Rules: Add an Obstacle Cost when moving from a semi-obstacle to a semi-obstacle and When moving from a non-obstacle to a semi-obstacle, convert the current Steps Taken from goal to Obstacle Steps Taken. The second rule is a bit tricky to describe, but it basically means that if you took 9 Steps and passed through 3 Obstacles to get to a particular Floor tile (for a total score of 3009), then trying to go to a new Obstacle tile from that Floor tile would give a score of 10010 (10 Obstacles, 10 Steps) because all the Steps taken to get to that point get converted to Obstacle Steps. Of course, each tile will end up with the lowest score it can get based on various calculated paths, so if there was a way to get to it in 8 Steps, the score would be lower.

This is a somewhat complicated system, but it's fairly simple to code from a programmer's perspective, since you're just comparing two adjacent tiles using things already known about the Pathmap at that point. The problem is the Observed Result, which I struggle to describe, but goes something like this: A Construct will prioritise paths that minimize the number of steps taken to the goal after it enters the first semi-obstacle. If a path enters a connected region of non-obstacles, it can only leave that region into a neighboring semi-obstacle from the square that minimizes the number of steps left to reach the goal, and it may not re-enter that same connected region.

This wasn't the intended effect of the Pathmap Rule: I think it was believed that it would cause the Seep to ignore all connected wall regions that it couldn't reach itself, since they would all be converted back to obstacles. As mentioned, it was particularly simple way of coding something that would've hopefully had a more intuitive effect than the Seep drifting towards 'gaps' between Walls that it could never cross. But the actual result is fairly far from that. Thankfully it doesn't matter in the large majority of cases, but it's a pretty horrible system overall.



System 3 - Obstacle Minimization

The bare minimum and easiest to implement, and probably what I was originally imagining with my comment earlier in the thread. The Pathmap Rule is very simple: Add an Obstacle Cost when moving to a semi-obstacle. So every move to an Oremite tile would cost 1000 more.

This leads to the following Observed Result: A Construct will prioritise paths that minimize the number of semi-obstacles crossed.

This is both simple to code and fairly simple to predict. A path blocked by a group of 10 Oremite tiles would receive less priority than one blocked by 3 Oremite tiles, no matter where in the singular path those tiles are. The drawback to this is that it still doesn't matter where the player is beyond those blocked paths: he could be sitting on just the other side of the "10 tile" path, and a good 50 tiles along a brained path to the end of the "3 tile" path, and the Construct would still prefer to camp the "3 tile" path. However, it still ticks the boxes in being simple to learn and implement, so it's worth considering.



System 4 - Player Proximity

The final system I'm going to cover is an adaption of what I believe the Seep/Waterskipper Rule wanted to be. Unfortunately, the Pathmap Rule for this is actually fairly complicated, so I'm going to reverse the order and cover the Observed Result first that we'd like to get. If the only paths that exist are ones that go through semi-obstacles then: A Construct will prioritise the path that leads to the semi-obstacle bordering its non-obstacle region that is closest to the goal along the normal brained path. So this means that when the player gets closer to one part of the non-obstacle region the Construct is in, the Construct will prefer to move to that area, rather than counting the number of obstacles along various different paths.

This is what I personally feel would be the most intuitive result for me, so I've given a lot of thought today on how it might be implemented. The issue is that it can't be done in a simple way: you would need a second temporary Pathmap. The most straightforward way I can think to implement it is as follows:

* Create a normal brained pathmap that ignores all semi-obstacles (same as Constructs use in 5.1).
* If no semi-obstacles are in that pathmap, stop here: we can just copy this pathmap result and use it as normal.
* If at least 1 semi-obstacle exists in the pathmap, then save the temporary result and start creating the new pathmap from scratch, this time taking semi-obstacles into account.
* The score of any semi-obstacle tile is equal to its score in the temporary pathmap multiplied by 1001. (So the number of Steps taken in the temporary pathmap is convered to Obstacle Steps in the new pathmap.) Steps taken from a semi-obstacle tile to a non-obstacle tile are calculated as normal.

This sidesteps the issue that the Seep/Waterskipper Rule had, in that the scores we apply to connected non-obstacle regions no longer affect the revised scores we're giving to semi-obstacle tiles. The pathmap would then naturally build from those tiles, so that the closest semi-obstacles should be given the correct priority.

As noted though, the code is more involved for this solution. There is a shortcut we could take for this particular implementation of the rule though: the "normal brained pathmap" built in Step 1 is identical to the GROUND_AND_SHALLOW_WATER pathmap that may already be built. So it could be possible to custom build the GROUND_AND_SHALLOW_WATER_NO_OREMITES pathmap by having it refer to an existing GROUND_AND_SHALLOW_WATER pathmap to get the scores for semi-obstacle tiles. But like I said, it's a shortcut: if we want to use semi-obstacles for other kinds of pathmaps in the future, we would need a more general solution, and that may require building a temporary pathmap each time you want to update the semi-obstacle map.



Anyways, that's what I've come up with. Other systems could be suggested if anyone thinks of something more intuitive or easier to handle. I'd personally prefer either System 3 or 4. I only mentioned System 2 because it's already how one pathmap that paths through obstacles works, but I'd definitely prefer to avoid repeating its mistakes. (And it's too bad it's so entrenched that we can't consider doing anything about it, but at least it's not as bad as Stalwarts o/~)

Also, small admission: I haven't actually compiled and looked at the PR's code in practice, so my above analysis is based on how I expect the code to work rather than seeing it in practice. So apologies if I've gotten anything wrong. I still think it's worth discussing possible alternative priority systems in any case, since we'd want to limit the number of times this sort of thing changes.

---

[Last edited by TFMurphy at 11-10-2022 01:33 AM]

Nuntar
Level: Smitemaster

Rank Points: 4981
Registered: 02-20-2007
IP: Logged

I constructed this example to help illustrate the difference between the four implementations TFMurphy listed.



The same layout with a construct and oremites:


(Assuming of course that I've understood everything correctly....)

Implementation 1: All paths are penalised +1000 for one wall-to-floor step, and so the seep follows normal brain preferences -- it will move west to the tile directly north of Beethro and then alternate between two tiles.

Implementation 2 (actual brained seep behaviour): The seep moves to the eastern extremity of the horseshoe, because that's closest to Beethro along floor routes, even though seep can't move on floor.

Implementation 3: The seep moves to the western extremity, since there is only one floor tile on a possible path to Beethro. It would remain there if Beethro moves east or west along the wall.

Implementation 4: The seep moves to the western extremity, since that is the closest to Beethro, ignoring whether later tiles are wall or floor. If Beethro moves two tiles east so he is closer to the eastern extremity, the seep goes there instead.

(5.1 brained construct behaviour: The construct moves to the western extremity. If Beethro steps a couple of tiles east, the construct then steps north to try to stay in a diagonal line with him.)

It's pretty clear that (2) is the worst of the four, since even a fairly simple layout like this results in behaviour that's too weird for be easily understood. (And this discussion has reminded me that we urgently need to improve how we teach brained seep behaviour in EP.)

(1) is the next worst, since the seep/construct isn't acting especially intelligently and isn't trying to get as close to Beethro as it can within its limitations.

Either (3) or (4) would be acceptable to me, but I'm pretty sure I prefer (3) as it feels the most like the construct is trying its best to act intelligently and get to where it could pose a problem to Beethro.

EDIT: Just to illustrate how weird current brained seep behaviour is, if you remove the wall tile SW of Beethro, the seep still goes east. However, if you disconnect this wall from the outer edge of the room by removing a single tile at the edge, the seep goes west! (Thanks to Rabscuttle in chat for this observation.)

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-10-2022 02:01 AM]

Rabscuttle
Level: Smitemaster

Rank Points: 2520
Registered: 09-10-2004
IP: Logged

File: brainedseep.png (391.5 KB)
Downloaded 342 times.
License: Public Domain

It's kind of fascinating.

Because Beethro is next to a wall connected to that block next to him, the seep-pathing of the northern most bit of that wall is at least 7 steps, so when you step off to the floor, it becomes 8008, because of the step to obstacle step rule. If you take the long way around it is ~109, which becomes 110110 when you step onto the floor.

But when you disconnect walls next to Beethro from that bit of wall (removing the 7 and 109 paths), suddenly you can just go diagonally, and you get 1005 (one floor step, 5 wall steps), which only becomes 6006 when you step off and then the distance to the west side of the seep's wall is less than the east.

---

[Last edited by Rabscuttle at 11-10-2022 03:37 AM]

hyperme
Level: Smitemaster

Rank Points: 1263
Registered: 06-23-2006
IP: Logged

My current thoughts would be to go for option 3, since that's the one that I think is the most understandable. With each oremite tile costing 1001, it results in the case that an oremite-blocked Construct will prefer the path with the minimum number of oremite tiles, which seems reasonable. (Ease of implementation is also a bonus for me personally)

I agree that redoing Seep/Waterskipper is definitely to be avoided, since they are very weird.

____________________________
[Insert witty comment here]
Qzvlkx?

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

File: ConstructSetups.png (392.4 KB)
Downloaded 284 times.
License: Public Domain

Rabscuttle wrote:
But when you disconnect walls next to Beethro from that bit of wall (removing the 7 and 109 paths), suddenly you can just go diagonally, and you get 1005 (one floor step, 5 wall steps), which only becomes 6006 when you step off and then the distance to the west side of the seep's wall is less than the east.

Slight correction: 1005 would be "1 floor step, 4 wall steps", since it's 1 Obstacle + 5 Steps Total. Similarly, in the image, the path leading NE would go up 1001 each time instead of just 1000 (each tile being 1 Obstacle + 1 Step). The analysis itself is correct, but the exact numbers could matter when it comes to breaking ties within a region.

Nuntar wrote:
Implementation 1: All paths are penalised +1000 for one wall-to-floor step, and so the seep follows normal brain preferences -- it will move west to the tile directly north of Beethro and then alternate between two tiles.

The Construct would actually continue moving west due to movement preferences since all the tiles along the top of the horseshoe should have the same score, so this would be similar to the 5.1 Construct result for this setup, but with some slight changes since pathing must make a decision on whether a path is shorter going through the initial floor tiles, or directly over the oremites and curve around the western floor tiles.

Nuntar wrote:
Either (3) or (4) would be acceptable to me, but I'm pretty sure I prefer (3) as it feels the most like the Construct is trying its best to act intelligently and get to where it could pose a problem to Beethro.

I find this conclusion a little surprising, because I feel the exact same way but about (4) instead of (3): I feel that the Construct is making more intelligent decisions and would get in the way more often when following System 4.

Let me go over the thought process behind that so you can see my reasoning:

* If a path with no oremite tiles is found, then the Construct follows that path. This applies to all systems. So if we continue, then the player cannot be within the Construct's 'connected non-obstacle region'. Let's call that the Construct's territory.
* If there are no paths at all that go from the Construct to the player, even through an oremite tile, then the Construct is unbrained. This applies to all systems. If we continue, there must be a path that goes through at least 1 oremite tile.
* If all the available paths go through the same reachable oremite tile, then the Construct will always go to that oremite tile. This applies to all systems. If we continue, there must be a choice between more than 1 oremite tile that borders the Construct's territory, both eventually leading to the same area that the player is in.

Now that we've narrowed down our setup to what might differ between the systems, we continue:

* The Construct cannot leave its territory to pursue the player because of the oremite tiles. (This knowledge is constrained by the information given by the brain's pathmap: the Construct has no knowledge of paths that it could traverse but are covered by Brain-visible obstacles. It similarly has no knowledge of doors that could open to allow it to enter the player's area. This is outside brain pathmapping scope however, and none of the above systems offer any inherent advantage or disadvantage in stumbling across or otherwise taking advantage of these hidden paths.)
* The Construct cannot cross oremite tiles. Doing so, even if pushed, would at best temporarily break it, and at worst completely destroy it. So it should have no expectation of following the path beyond the oremite tiles. This means that a path that has fewer oremite tiles is not inherently more desirable or less dangerous.
* Therefore, the only hope the Construct has of being able to attack the player is if the player enters the Construct's territory once more. And since the only paths it sees to the player go through oremite tiles, it can make the assumption that the player is likely to enter the Construct's territory from those tiles. (Again, the Construct has no knowledge of other entrances such as Force Arrows or toggled doors, and can only work with what is given by brain pathmapping.)
* It follows that the best decision it could take is to head to one of the oremite tiles bordering its territory and wait for the player there, in an attempt to deny the player's entry or attack upon intrusion. So which "entrance" to the Construct's territory makes more sense to guard? The one that is blocked by fewer oremite tiles beyond the entrance? Or the one that the player is closer to?

Here's an example of the kind of setups I'm thinking of, where System 3 would feel actively less intelligent than System 4.



I also don't feel that (4) is inherently less understandable to a player than (3). Of course, how understandable a concept is can depend on how you internalise it or how well the concept is stated. While I can describe (3) more succintly (find the path that passes through the least amount of oremites), I still think (4) has a fairly intuitive feel to it. Let me try to restate it to get across what I mean: A brained Construct will always prioritise a path that avoids all oremite tiles. If the only paths available go through at least 1 Oremite tile, then the Construct will instead decide to guard an Oremite tile that borders its "territory" (connected non-obstacle region), choosing whichever Oremite tile the player is closest to.

I'll admit I find it a bit tricky to describe accurately without making it sound more complicated than it is from a player's perspective, but I end up internalising it as some fairly simple concepts: Construct can't leave its territory to pursue player, so Construct will try and guard whichever tile player is most likely to enter from. I think this gives the system a sort of naturally derived quality, as opposed to a more succinct but arbitrary rule that isn't as effective in its purpose.


=====


The upshot of all of the above, is that I find System 4 to be just as understandable to me as System 3, and that following (4) is a more intelligent decision by the Construct. I also think there are some setups where it's easier to predict where the closest Oremite tile is to the player for (4) than it is to find which path has the least Oremites for (3); though of course, the reverse is also quite clearly true.

But that doesn't mean I can say that (4) is objectively the best decision. Understanding is subjective, and I could be in the minority in finding "guarding territory" to be an intuitive concept for Construct pathmapping. Or maybe the succinctness/arbitrariness of (3) makes more thematic sense for Constructs. The added effort in implementing (4) is an additional drawback that would need to be overcome to use it.

I think my main point here is that I wanted to make clear my reasons for thinking (4) to be intuitive and a more intelligent decision by the Construct, in contrast to the reasons currently given in support of (3). I'm still happy with the simplicity that (3) offers (both in implementation and execution), but I'm still unsure if it's really the best fit.

---

[Last edited by TFMurphy at 11-10-2022 08:50 PM]

mauvebutterfly
Level: Smitemaster

Rank Points: 776
Registered: 05-03-2015
IP: Logged

As far as simply understood pathfinding rules go, another simple solution would be to have the construct revert to unbrained movement if it doesn't see a path. Essentially, brained constructs would treat oremites like force arrows. If the player is on oremites adjacent to somewhere in the construct's territory, the construct would path to them. If the player is any further out than that, the brain doesn't see a path and the construct reverts to default behaviour.

____________________________
106th Skywatcher

hyperme
Level: Smitemaster

Rank Points: 1263
Registered: 06-23-2006
IP: Logged

mauvebutterfly wrote:
As far as simply understood pathfinding rules go, another simple solution would be to have the construct revert to unbrained movement if it doesn't see a path. Essentially, brained constructs would treat oremites like force arrows. If the player is on oremites adjacent to somewhere in the construct's territory, the construct would path to them. If the player is any further out than that, the brain doesn't see a path and the construct reverts to default behaviour.

This is a possibility, but some people consider that to be less than optimal solution because it doesn't preserve current behaviour where Constructs can get close to an oremite patch the player is standing in.

My current worry about option four is that the actual workings seem difficult to understand. I think once you get it you get it, but it does require some time to wrap your mind around it.

(As a side note, now that I have wrapped my head around it, I'm not sure if the implementation would require two passes. When assigning scores to tiles, the algorithm also tracks how many steps a square is worth. Outside of Water and Wall paths, the steps and score values are equal, so it should be possible to shortcut some things. I will have to things to be sure however.)

____________________________
[Insert witty comment here]
Qzvlkx?

hyperme
Level: Smitemaster

Rank Points: 1263
Registered: 06-23-2006
IP: Logged

So I tried out the various options, and I think once you actually see it in play option 4 is more intuitive than the algorithm description implies.

From a technical perspective, I also think that generating a temporary path is unrequired. The pathing algorithm already tracks the number of steps a tile is from the target tile, which in most cases would be equal to the score in a temporary pathmap. The only exception is for Water and Wall paths, and I think it's fairly clear no-one wants new pathing with those kinds of quirks. This means going from the current implementation to a new one is a single-line change. (In theory some future element could count as a semi-obstacle for Water or Wall pathers, but doing a lot of work to service a hypothetical situation isn't worth it in this case.)

____________________________
[Insert witty comment here]
Qzvlkx?

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

File: PathmapExample.png (41.9 KB)
Downloaded 192 times.
License: Public Domain

hyperme wrote:
From a technical perspective, I also think that generating a temporary path is unrequired. The pathing algorithm already tracks the number of steps a tile is from the target tile, which in most cases would be equal to the score in a temporary pathmap. The only exception is for Water and Wall paths, and I think it's fairly clear no-one wants new pathing with those kinds of quirks. This means going from the current implementation to a new one is a single-line change. (In theory some future element could count as a semi-obstacle for Water or Wall pathers, but doing a lot of work to service a hypothetical situation isn't worth it in this case.)

Unfortunately, this isn't the case. GROUND_AND_SHALLOW_WATER and GROUND_AND_SHALLOW_WATER_NO_OREMITES path differently around oremites leading to different step distances to the same Oremite tile.


In the above example, the score for the NW exit to Beethro's room is 3, with 3 steps taken under GROUND_AND_SHALLOW_WATER. Under GROUND_AND_SHALLOW_WATER_NO_OREMITES, the score is 1018, with 18 steps taken. It's the same issue that Seep/Waterskippers have with trying to take a 'shortcut' across a connected non-obstacle region: they can't re-enter it once they leave it because it already has a lower score. There's no way for GROUND_AND_SHALLOW_WATER_NO_OREMITES to find a 3 step route to the NW tile because the floor tiles above will already have a lower score blocking that route. (And to my knowledge, the algorithm prioritises expanding the path with the lowest score, so it should fill out the floor path first before checking the surrounding oremites.)

Ironically, the WALL/WATER pathmaps *could* have solved their issue without requiring an extra temporary pathmap. Since they pathmap through all obstacles, the "normal brained pathmap" they would have to create in Step 1 would end up being a map devoid of all obstacles... which means that the number of steps from the goal would always be equal to the Chebyshev distance, avoiding the need of creating an extra pathmap.

This can't be done with System 4, because we still need to find a brained path from each semi-obstacle to the goal, and it has to use a pathmap that is not treating those semi-obstacles as penalties.

hyperme
Level: Smitemaster

Rank Points: 1263
Registered: 06-23-2006
IP: Logged

Ah. Thanks for catching the issue.

I think from an engineering perspective there isn't too much work to get everything wired up, since the pathmap code is setup pretty cleanly. Main issue will probably be where to put the temporary pathmap and how to feed it to the pathmap calculation function.

____________________________
[Insert witty comment here]
Qzvlkx?

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

If it can be done cleanly, it might be best to try and get some sort of dependency coded so that GROUND_AND_SHALLOW_WATER_NO_OREMITES directly references GROUND_AND_SHALLOW_WATER. As the game stands right now, GROUND_AND_SHALLOW_WATER will always exist if GROUND_AND_SHALLOW_WATER_NO_OREMITES is used, because only Brained Constructs use GROUND_AND_SHALLOW_WATER_NO_OREMITES, and a Brain has GROUND_AND_SHALLOW_WATER even if no other enemy is in the room, so it should create that pathmap type.

So if we can actively reference GROUND_AND_SHALLOW_WATER, we can avoid having to recreate something the game is already updating. The main concerns would be to make sure that GROUND_AND_SHALLOW_WATER is always updated before the NO_OREMITES version. Sanity checks to be certain that GROUND_AND_SHALLOW_WATER exists when GROUND_AND_SHALLOW_WATER_NO_OREMITES might also be wise, but that could be left as an Assert for now.

Not sure of the best way to handle this, mind. A pointer to pRoom->pPathMap would work... perhaps as an additional variable added to CPathMap so that it can reference its own container? The alternative would be sending it as an optional variable down the chain from something that references pPathmap directly so that CalcPaths can use it, but that might be messier.

hyperme
Level: Smitemaster

Rank Points: 1263
Registered: 06-23-2006
IP: Logged

Having looked into the various bits of code that make pathmaps, my current thoughts are along these lines:

1. We want to introduce a concept where one pathmap type can depend on another. (Currently, only for dealing with semi-obstacles)
2. Logic for this is simple enough. A function to ask if a movement type has a pathing dependency, and another to get it. Or a single function that can do both.
3. When creating a pathmap, if it has a dependency on another, you create the dependency if it doesn't exist.
4. CPathMap can be updated to include a pointer to another CPathMap, which is given to it when it is created. When a pathmap calculation needs information from a dependency, it has access. (this is where we need a safety check)
5. CPathMap is already written so that if you query pathmap scores via its functions, it will do any required calculations before returning the value. (if you grab values from the members directly you get what you deserve)

Overall, the main work will be in updating the creation of path map objects to handle some (read: one) pathmaps having a dependency. The changes to CPathMap should ideally be small.

____________________________
[Insert witty comment here]
Qzvlkx?