Announcement: Remember: you are giving away your fantastic ideas for free, and somebody else might even make money from them (or appear to). That's just how the world works! If you're worried about it, maybe you shouldn't post your ideas here.


Caravel Forum : DROD Boards : Feature Requests : "Get Nearest [Entity Type]" (Generalized "Get Natural Target")
New Topic New Poll Post Reply
Poster Message
Xindaris
Level: Master Delver
Avatar
Rank Points: 279
Registered: 06-13-2015
IP: Logged
icon "Get Nearest [Entity Type]" (0)  
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!
Click here to view the secret text


[Last edited by Xindaris at 05-22-2016 02:00 AM]
05-22-2016 at 01:58 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 2314
Registered: 12-28-2004
IP: Logged
icon Re: "Get Nearest [Entity Type]" (0)  
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

____________________________
I am a skelliopath.
05-22-2016 at 01:53 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
Xindaris
Level: Master Delver
Avatar
Rank Points: 279
Registered: 06-13-2015
IP: Logged
icon Re: "Get Nearest [Entity Type]" (0)  
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!
Click here to view the secret text


[Last edited by Xindaris at 05-22-2016 02:45 PM]
05-22-2016 at 02:43 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Nuntar
Level: Smitemaster
Avatar
Rank Points: 2972
Registered: 02-20-2007
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+2)  
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
05-22-2016 at 06:54 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 2314
Registered: 12-28-2004
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+1)  
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.

____________________________
I am a skelliopath.
05-23-2016 at 09:47 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
Xindaris
Level: Master Delver
Avatar
Rank Points: 279
Registered: 06-13-2015
IP: Logged
icon Re: "Get Nearest [Entity Type]" (0)  
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!
Click here to view the secret text


[Last edited by Xindaris at 05-23-2016 04:18 PM]
05-23-2016 at 04:10 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Dragon Fogel
Level: Smitemaster
Rank Points: 889
Registered: 06-21-2014
IP: Logged
icon Re: "Get Nearest [Entity Type]" (0)  
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).
05-23-2016 at 04:37 PM
View Profile Send Private Message to User Show all user's posts High Scores Quote Reply
LeoS
Level: Master Delver
Rank Points: 257
Registered: 04-02-2015
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+1)  
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 :lol

And by the way, what's wrong with evil eyes that they get lumped in with Stalwarts and Citizens?
05-23-2016 at 06:03 PM
View Profile Send Private Message to User Show all user's posts High Scores Quote Reply
Insoluble
Level: Smitemaster
Avatar
Rank Points: 981
Registered: 09-04-2014
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+2)  
quote:
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:
Click here to view the secret text


[Last edited by Insoluble at 05-23-2016 09:53 PM]
05-23-2016 at 09:52 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
kieranmillar
Level: Smitemaster
Rank Points: 1307
Registered: 07-11-2014
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+1)  
What's the difference between regular brained monster movement and stalwart movement? (Aside from stopping to turn, of course). Is there any?

____________________________
(07:23 PM) Pearls: Kieran is correct.

[Last edited by kieranmillar at 05-23-2016 11:12 PM]
05-23-2016 at 11:12 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
Nuntar
Level: Smitemaster
Avatar
Rank Points: 2972
Registered: 02-20-2007
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+1)  
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
05-23-2016 at 11:29 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
uncopy2002
Level: Smiter
Rank Points: 365
Registered: 07-28-2014
IP: Logged
icon Re: "Get Nearest [Entity Type]" (+1)  
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.
05-23-2016 at 11:35 PM
View Profile Send Private Message to User Show all user's posts High Scores Quote Reply
New Topic New Poll Post Reply
Caravel Forum : DROD Boards : Feature Requests : "Get Nearest [Entity Type]" (Generalized "Get Natural Target")
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.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.