Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old March 28, 2017, 00:19   #31
Nick
Vanilla maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 51
Posts: 6,325
Donated: $60
Nick is on a distinguished road
Thanks for all the responses.

Quote:
Originally Posted by Derakon View Post
You say that, but what about lava, immobile monsters, and other such barriers?
Good point. For immobile monster place-swapping is sometimes possible; lava is an interesting one.

Quote:
Originally Posted by Derakon View Post
Does this mean that we track noisiness on a per-tile basis? Do we track noises not caused by the player?
Player noise would be generated every turn as a heat map, with the starting value dependent on stealth and possibly player action. I would start by tracking no other noises, but try to allow for that to be added later.

Quote:
Originally Posted by Derakon View Post
Sounds plausible to me. What happens if we have a monster tracking the player by noise, then they stumble onto the player's scent trail? What happens after that if the player teleports? What if the monster saw the player teleport?
Monsters (probably all?) would prioritise sound over scent, because it's more immediate. A teleported player would no longer generate sound, but scent would remain, so some monsters would just stop and some would track to where the player left from. If they saw - probably would continue scent tracking anyway, but they would be fairly close so it wouldn't make a lot of difference.

Quote:
Originally Posted by luneya View Post
Sounds like a good start. Presumably we want to have it so that different monsters use different tracking procedures. Most monsters will use sight first, then sound, and otherwise stay put, as they don't have scent or telepathic tracking ability. Those that do have the latter abilities will rely on them. Pick thematically appropriate monsters to be able to scent-track: hounds, obviously, perhaps giants/ogres (Fee Fi Fo Fum...), etc.
This is exactly how I'm thinking of it.

Quote:
Originally Posted by luneya View Post
As for telepathy, I would envision two types. The commonest type, which would be exemplified by monsters like the mind flayer, would be essentially identical to the current pathing. The monster always knows where the player is, but doesn't know the correct path, and so if there's no near-straight-line route, it gets hung up on a wall.

A more sophisticated telepathy, where the monster has full knowledge of the dungeon and always chooses the most efficient route, should be implemented but only made available to uniques, and particularly only to those which should thematically have it: Sauron, the Nazgul, Saruman, Osse, Arien, and perhaps one or two other such great powers that I'm forgetting. (Tunnelers like Morgoth and wall-walkers like Adunaphel can be excluded from this class, as they'll get as good of a result with just the other telepathy.) Since the set of monsters with this power is quite restricted and only one or two will likely be generated on any level at a time, we can afford to use a computationally expensive algorithm to get their movement right if necessary.
I like this a lot.

Quote:
Originally Posted by t4nk View Post
That seems good to me. I'd suggest to remove 'noise' and 'scent' from struct square, and instead introduce several 'flow maps' in struct chunk - two dimensional arrays of bytes (or uint16_t or whatever): one for player noise, recalculated on each player's turn, and one for each stair and perhaps several for other kinds of noise
For code readability purposes, do you mean?

Quote:
Originally Posted by t4nk View Post
Also, if different actions produce different amounts of noise, that should be displayed in the UI (a la Dungeon Crawl).
That sounds sensible - how do they do it?

Quote:
Originally Posted by bio_hazard View Post
With these pathfinding algorithms, any chance the player will get actions to (try to) confuse their trail? Dropping food or throwing stones or torches, etc?
I think not to start out with, but it's a possibility for later.

Quote:
Originally Posted by Patashu View Post
For scent based tracking, Brogue has a very good implementation that would be worth stealing.

The scent distance metric is the second one described on this page:

http://brogue.wikia.com/wiki/King's_move

Every move in Brogue, all scent weakens by 3, then you throw your scent on every tile in LoS according to this metric. If the scent is fresher than what's on that tile, it gets updated. This effectively means that monsters who track you via scent will follow along an optimal path to your new location.

You can look in the Brogue source code to see how it's implemented, and also some optimizations, for example, rather than aging all scent by 3, there's a global counter that increments by 3 every turn, and new scent adds the global counter to its value before being placed on tiles, meaning that rather than old scent being 'weakened', new scent is 'strengthened'.
I think that's pretty much how it's done in O/FA, too.
__________________
One Ring to rule them all, One Ring to find them,
One Ring to bring them all and in the darkness bind them.
Nick is offline   Reply With Quote
Old March 28, 2017, 00:47   #32
t4nk
Adept
 
Join Date: May 2016
Posts: 239
t4nk is on a distinguished road
Quote:
Originally Posted by Nick View Post
For code readability purposes, do you mean?
For readability, as an optimization (people seem to be concerned about it ) of both struct square and the heatmaps (fitting into cache), but most importantly, for ease of adding more heatmaps (Sil has 400+ of them!) and for possibility of them carrying additional information.
Something like:
Code:
struct heatmap {
    uint16_t **grids;
    /* some other stuff that might be useful... */
};

struct chunk {
    stuff; /* as currently */

    struct heatmap *heatmaps;
    int num_heatmaps;
};
Quote:
That sounds sensible - how do they do it?
Pretty much like hitpoints are displayed, updated on each turn, for example:
Code:
Noise: [######..]
or just as numbers:
Code:
Noise: 4/9

Last edited by t4nk; March 28, 2017 at 01:47.
t4nk is offline   Reply With Quote
Old March 28, 2017, 02:02   #33
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 2,923
fizzix is on a distinguished road
I think the approach nick outlines is probably a good starting point. We can compute a whole bunch of heatmaps each turn based off of scent and sounds. Let's try that and see how quickly the game runs, if it winds up being too slow, we can start considering optimizations.
fizzix is offline   Reply With Quote
Old March 28, 2017, 18:29   #34
bio_hazard
Knight
 
bio_hazard's Avatar
 
Join Date: Dec 2008
Posts: 554
bio_hazard is on a distinguished road
Maybe variant territory, but what about localization based on use of magic? This would be thematic. The footprint would be based on the number of mana used in the spell, and only "wizardy" monsters would pay attention to this gradient.
bio_hazard is offline   Reply With Quote
Old March 30, 2017, 06:54   #35
Carnivean
Swordsman
 
Join Date: Sep 2013
Posts: 471
Carnivean is on a distinguished road
Quote:
Originally Posted by luneya View Post
As for telepathy, I would envision two types. The commonest type, which would be exemplified by monsters like the mind flayer, would be essentially identical to the current pathing. The monster always knows where the player is, but doesn't know the correct path, and so if there's no near-straight-line route, it gets hung up on a wall.
A monster would have to be fairly dumb to just head straight into a wall, thinking it to be the quickest route to the player. Even a dog in a yard will run side to side seeking an exit. If there is an exit from the room, then there should be an intelligence based chance of the monster using it.
Carnivean is offline   Reply With Quote
Old April 8, 2017, 20:03   #36
luneya
Apprentice
 
Join Date: Aug 2015
Posts: 94
luneya is on a distinguished road
Quote:
Originally Posted by Carnivean View Post
A monster would have to be fairly dumb to just head straight into a wall, thinking it to be the quickest route to the player. Even a dog in a yard will run side to side seeking an exit. If there is an exit from the room, then there should be an intelligence based chance of the monster using it.

Most of the monsters with this sort of telepathy will likely be wall-walkers like the various ghosts, so it's not stupid. For the rest, it seems fair to postulate that some monsters are dumber than dogs

More seriously, an animal that hunts primarily by telepathy is probably weak in the more physical senses, perhaps even completely blind. Or it might be so telepathically locked-in that it doesn't think to look around the room for alternate exits, or that it's not willing to walk directly away from its prey on the off-chance that it'll find another route (even though it sees a door across the room, it doesn't know how the hallway curves). Any of these would justify a behavior exactly like the current pathfinding.

We could, of course, create a new pathfinding algorithm with slightly different behavior if that seems more appropriate, but why go to the effort of doing that when we already have something that's known to work and does almost exactly what we want?
luneya is offline   Reply With Quote
Old April 8, 2017, 23:29   #37
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 3,887
Donated: $40
Pete Mack is on a distinguished road
If you want PASS_WALL and KILL_WALL monsters to path-find correctly, you need a different heat map when there are internal permawalls (vaults) present, alternatively, use whenever one of them does run into a permawall, let them proceed towards a vault entrance, then use the regular heat map inside the vault. The latter is not efficient, but they will eventually get to the player.
Pete Mack is offline   Reply With Quote
Old April 19, 2017, 18:03   #38
Sky
Swordsman
 
Join Date: Oct 2016
Location: Glasgae
Age: 44
Posts: 418
Sky is on a distinguished road
A small point but relevant to this thread: does every mob in the game have perfect infravision?

I just went with the old "the computer can, the player can't" that was the norm in videogames in the 80s and 90s. But since we are moving to buff the AI, how about we stop having mobs that see you while they are in full darkness.

.. not to mention, it would finally give some use to all those staves of darkness we squelch...
Sky is offline   Reply With Quote
Old April 19, 2017, 18:54   #39
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,253
AnonymousHero is on a distinguished road
Quote:
Originally Posted by Sky View Post
But since we are moving to buff the AI, how about we stop having mobs that see you while they are in full darkness.
I think you mean "while @ is in full darkness"? I mean, I can see a lamppost (for example) perfectly well even if I'm in the dark...

(Sounds like a good idea, btw.)
AnonymousHero is offline   Reply With Quote
Old April 19, 2017, 18:57   #40
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 3,887
Donated: $40
Pete Mack is on a distinguished road
Well yes. Bottom line, you need multiple Dijkstra flow maps, as I and others have mentioned before.
One for passwall/killwall (technically only needed on levels with vaults), one for ordinary monsters, one for fire immune monsters (technically only for levels with lava), and optionally a 'flow by smell' map for stupid (animal) monsters.

My recommendation is to treat all KILL_WALL/PASS_WALL monsters as immune to lava.

Quote:
Originally Posted by Carnivean View Post
A monster would have to be fairly dumb to just head straight into a wall, thinking it to be the quickest route to the player. Even a dog in a yard will run side to side seeking an exit. If there is an exit from the room, then there should be an intelligence based chance of the monster using it.
Pete Mack is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
YAWP: My first ever win, quickly followed up by finding The One Ring on DLVL 104! fruviad AAR 3 January 2, 2017 22:39
Finding a solution to ID Nick Vanilla 51 April 3, 2014 02:18
Path of Exile? HallucinationMushroom Idle chatter 68 December 2, 2013 14:11
Path to target request juggle5 Vanilla 9 May 17, 2011 13:07
Does Entroband reward one with experience for finding awesome items? BlackFlame Variants 3 February 18, 2010 07:28


All times are GMT +1. The time now is 16:24.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, vBulletin Solutions, Inc.