Xindaris
Level: Smitemaster

Rank Points: 1531
Registered: 06-13-2015
IP: Logged

In the interest of making custom creatures that can chase down things other than the "natural targets", or even just those same things with a different priority order, this would be a super convenient command to have handy. Using probably much of the same machinery as "Get Natural Target", the command would ideally take anything from the same list as "Wait for Entity Type" and output as _ReturnX and _ReturnY the location of the nearest entity of that type, or if there is no such entity in the room, output whatever "Get Natural Target" outputs when there is no natural target in sight (i.e., when a character running that command is alone in a room with an invisible Beethro who isn't close enough to it). This would even enable customized monsters to chase each other around!

It's at least theoretically possible to script something that does this, I hear some holds use such scripts, but it would certainly be easier and possibly more lightweight computation-wise to have something built-in that does it.

____________________________
109th Skywatcher

Here are some links to Things!

---

[Last edited by Xindaris at 05-22-2016 02:00 AM]

skell
Level: Legendary Smitemaster

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

This has been discussed many times in the chat and my standard response is:
1. What algorithm is used to find the nearest entity? King-move distance? Manhattan Distance? Pythagorean distance? Pathfinding distance? What if there is no path, should its AI work like seep's?
2. How would you like to break ties?

It's a great thing to have but it needs a lot of thinking about how to exactly implement it, otherwise we'll end with Stalwarts 2.0

____________________________
My website | Facebook | Twitter

Xindaris
Level: Smitemaster

Rank Points: 1531
Registered: 06-13-2015
IP: Logged

Well, I just meant for it to find what's closest the exact same way that "Natural Target" does. I mean, it's my understanding that "Find Natural Target" (or just the way roaches et al find their target) has some notion of what's closest, right? For example in the case of Beethro and a timeclone both in the same room, one of them a certain distance to the west and the other the same distance to the east of it.

I guess if people wanted something more complicated than that you could have a different version that bothers with pathfinding, but I was imagining a relatively basic thing with at least this particular request.

____________________________
109th Skywatcher

Here are some links to Things!

---

[Last edited by Xindaris at 05-22-2016 02:45 PM]

Nuntar
Level: Smitemaster

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

Monsters choosing between multiple valid targets (and puffs choosing the nearest heat source) all use the same algorithm, namely king-move distance primarily, Pythagorean distance as first tiebreaker, latest in movement order as final tiebreaker. In most cases the player doesn't need to know the details to solve puzzles, but there are valid puzzles depending on this metric, e.g. the room in More Fluff where you have to navigate a puff through a room of brains. So it's clearly best for consistency / simplicity that this metric is offered.

I really see no reason why one would want to offer other metrics as alternatives (except maybe pathfinding). What puzzle potential is opened up by doing so?

____________________________
50th Skywatcher

skell
Level: Legendary Smitemaster

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

The problem with DROD is that if you put something into the game, you can be pretty damn sure it's going to stay mostly unchanged. My request is a call to really give it a proper thought so that you don't wake up one day and think "aww crap, I wish it worked differently" *eyes citizens and stalwarts*. Just look at how much fixing we did after TSS because the interactions in the game can get really complex and it's easy to miss stuff. Maybe I am too cautious but I prefer to make sure things are well-thought on paper before they get into the game because of that.

My stab on how to chose the one correct algorithm to use is to not chose one correct algorithm to use and, instead, give the player the ability to chose the options.

Distance algorithm:
- Chebyshev distance
- Manhattan distance
- Pythagorean distance
- Roach A* distance
- Seep A* distance
- <something else>

Tiebreaking:
- Pythagorean -> Move Order
- Move Order
- <something else>

But I can already tell by knowing the source code that this would require either a lot of code duplication (which is probably not happening) or a lot of refactoring, which means it would take a lot of time to implement, which means it's probably not going to happen.

Then again like with Get natural target we could start with just one or two options and maybe expand later.

____________________________
My website | Facebook | Twitter

Xindaris
Level: Smitemaster

Rank Points: 1531
Registered: 06-13-2015
IP: Logged

So, like, my issue is that I just read your post and I don't even know what any of those options under "Distance Algorithms" means, aside from the word "pythagorean" taken by itself. And this is coming from someone who's been studying math for several years, conquered (though admittedly not mastered) all 5 main official holds, done some very in-depth scripting in DROD's language, and a fair amount of mapping.

If I were presented with that list of options I would be hopping onto the forum or the chat every single time I wanted to use the feature to ask if anybody knows what any of those actually means. Similar to how I always have to look up or figure out by experimentation which number represents which weapon state in the "_MyWeapon" variable or which direction in "_MyO" (although I wouldn't have the latter any other way since its design allows for a neat several-lines-of-code-saving trick).

To me, it seems sensible to at least start with options that can be described in terms of things the game already does for existing creatures. That would boil down to probably just "unbrained roach distance" and "brained roach distance", maybe "stalwart distance" if feeling ambitious. Besides making some sort of sense to somebody who's been playing the game but has never actually studied pathing or distance-finding algorithms, I'm under the impression that would be easiest to program. Obviously I could be wrong, but I get that impression from the fact that, by their own descriptions, the game uses code at least similar to those things already.

____________________________
109th Skywatcher

Here are some links to Things!

---

[Last edited by Xindaris at 05-23-2016 04:18 PM]

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

Heck, for just getting an entity even stalwart movement pathfinding isn't a problem here - you're just looking for the target, not the entire path. Using movement order as the tiebreaker will be fine as long as the object you're looking for is under the monsters tab.

If it's not a monster, (you might want a character to find the nearest bomb or relay station or force arrow) then a different tiebreaker would have to be used. Probably location-based. Again, not a problem as long as it's consistent and human-understandable (even if not completely transparent).

LeoS
Level: Master Delver
Rank Points: 276
Registered: 04-02-2015
IP: Logged

I believe Manhattan Distance is when something is like three blocks away and it can still take you 30 minutes to get there by cab

And by the way, what's wrong with evil eyes that they get lumped in with Stalwarts and Citizens?

Insoluble
Level: Smitemaster

Rank Points: 1638
Registered: 09-04-2014
IP: Logged

Xindaris wrote:
So, like, my issue is that I just read your post and I don't even know what any of those options under "Distance Algorithms" means, aside from the word "pythagorean" taken by itself. And this is coming from someone who's been studying math for several years,

Probably because most of those are alternate terms for the common official names for the metrics they are referring to.

- Chebyshev distance is just an alternate name for the L_∞ metric. In other words, the distance between two points is the maximum of their horizontal and vertical distance. This is equivalent to the number of moves it would take a monster to reach you beelining with no obstacles in the way.

- Manhattan distance is the L_1 metric, i.e. the sum of the horizontal and vertical distances. Anyone actually familiar with Manhattan Island will agree that "Manhattan distance" is a horrible alternate name for L_1 since most of the more interesting bits of Manhattan do not form a nice grid, but whatever.

- Pythagorean distance is L_2 which you know.

A* is some sort of search algorithm that will go around obstacles. It is apparently widely used by other software, but the most important thing I happen to know about it is that this horrible thing is responsible for the travesty of stallwart movement. (I think it is not the A* algorithm itself so much as the fact that it does not have a logical built in tie breaking mechanism). Please, no more DROD elements that make use of this thing!

____________________________
Links to neat forum tools that I always have trouble finding:

---

[Last edited by Insoluble at 05-23-2016 09:53 PM]

kieranmillar
Level: Smitemaster
Rank Points: 2670
Registered: 07-11-2014
IP: Logged

What's the difference between regular brained monster movement and stalwart movement? (Aside from stopping to turn, of course). Is there any?

---

[Last edited by kieranmillar at 05-23-2016 11:12 PM]

Nuntar
Level: Smitemaster

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

The brain pathmap has a single target (namely the player) and pathfinds backwards by counting adjacent tiles as "1", tiles adjacent to those as "2" and so on. At the end, the brained entity looks at the value of each tile adjacent to itself, and chooses the lowest-scoring. Only at this step, if multiple adjacent tiles are equally good, does tie-breaking come into play. The tiebreaker is a list of the nine directions (including Wait) in preference order. This makes brained movement completely predictable if you know the preference order; and nearly always, all you actually have to remember is "orthogonal > wait > diagonal".

Stalwarts can't do this because they can have multiple targets. They pathfind forwards from their position until they find a valid target. This means that tiebreaking comes into play at every step, and things like adding a single wall tile that's not even on the stalwart's route can change the end result.

____________________________
50th Skywatcher

uncopy2002
Level: Smiter
Rank Points: 431
Registered: 07-28-2014
IP: Logged

To clarify on Insoluble's talk on metric:

A metric is a way to define distance. A L_n metric simply means for a point (x,y) (since it's DROD, it's 2D), we declare that the relation between the distance R and (x,y) is x^n + y^n = R^n.

Then, if we consider all points that have a specific distance (which is usually 1), we get a equidistant contour, where all points lying on this line have the same distance. For L_∞ metric, it's a square. L_2 is just a circle. L_1 is a diamond.



Kieranmillar: Regular brained monster movement is deterministic, as described exactly in the help files. Stalwart (and Slayer and Halph) movement is not, the tie-breaking is like an oracle and will change semi-randomly depending on the relative position and probably other things.

Xindaris
Level: Smitemaster

Rank Points: 1531
Registered: 06-13-2015
IP: Logged

This topic's fairly old, but it's still something I would love to see exist. It's maybe theoretically possible to script a target search for a specific entity type in drodscript, but believe me--I've tried--it is way too much trouble. It's well into the realm of "trying to script this leads to madness".

____________________________
109th Skywatcher

Here are some links to Things!

---

[Last edited by Xindaris at 10-21-2020 03:35 PM]