Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old March 24, 2017, 17:05   #21
t4nk
Adept
 
Join Date: May 2016
Posts: 246
t4nk is on a distinguished road
Quote:
Originally Posted by fizzix View Post
In the technical side of this Angband runs into a few problems. The levels tend to be very large, which is necessary in order to fit these giant vaults we have, but makes tracking problems and heat map generation more computationally intensive. If we could shrink level size by half or so, it opens up a lot of options for better tracking, wandering monsters, etc. It's a tradeoff worth considering.
And I say again, it's not nearly as slow as you people think. You know, you can actually try that. Just increase mon-play:flow-depth in constants.txt to something reasonable, like 200 (note that flow is always recalculated after player's move, see monster_swap()). The result might surprize you... (you can view the flow propagation with Ctrl+A and _)

edit: Angband's level is what, 198x66 max? Let's say 200x100, or 20000 grids. Let's even devote a uint16_t for each grid (for storing noise - scent is kind of useless, IMO) (edit: come to think of it, a byte should suffice, by anyway...). I assure you that it's entirely practical to process a 40kb array every single frame, many times over even... Angband's flow depth is so tiny (32) because it just uses it in a pretty crazy way. The gory details are in get_moves_flow() (if (found_direction) { ... }) and it's kind of insane

Last edited by t4nk; March 24, 2017 at 17:22.
t4nk is offline   Reply With Quote
Old March 24, 2017, 19:44   #22
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 2,925
fizzix is on a distinguished road
Quote:
Originally Posted by t4nk View Post
And I say again, it's not nearly as slow as you people think. You know, you can actually try that. Just increase mon-play:flow-depth in constants.txt to something reasonable, like 200 (note that flow is always recalculated after player's move, see monster_swap()). The result might surprize you... (you can view the flow propagation with Ctrl+A and _)

edit: Angband's level is what, 198x66 max? Let's say 200x100, or 20000 grids. Let's even devote a uint16_t for each grid (for storing noise - scent is kind of useless, IMO) (edit: come to think of it, a byte should suffice, by anyway...). I assure you that it's entirely practical to process a 40kb array every single frame, many times over even... Angband's flow depth is so tiny (32) because it just uses it in a pretty crazy way. The gory details are in get_moves_flow() (if (found_direction) { ... }) and it's kind of insane
Yeah, we can definitely do the player map (I do think I extended that to 1024 squares or something, which certainly should be far enough). The problem really comes if you try to compute multiple paths on each turn, which you'll need to do if you want to do stuff like tracking to approximate or last known locations.

Static heat maps are much easier. They only need to be computed once, when the level forms (and then whenever the player or a monster decides to create or destroy a wall...)
fizzix is offline   Reply With Quote
Old March 24, 2017, 23:44   #23
Antoine
Ironband/Quickband Maintainer
 
Join Date: Nov 2007
Posts: 951
Antoine is on a distinguished road
Only some types of monster should be able to track the @ over great distances.
__________________
Ironband - http://angband.oook.cz/ironband/
Antoine is offline   Reply With Quote
Old March 25, 2017, 03:59   #24
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 4,015
Donated: $40
Pete Mack is on a distinguished road
In path calculation, it's not number of squares that matter, it's number of vertices and edges. As a crude first approximation, the number of vertices is bounded by the number of corner squares in the map, and the number of edges is between 3 and 4x greater. There's a concept of 'visibility graph' that is roughly the kind of graph wanted. With a visibility graph, with hallways reduced to a single node, the problem is really quite small. Note that visibility graphs are pretty easy in the special case of rooms and hallways assembled from axis-aligned grid-based rectangles.

Further, for player moves between adjacent nodes, recomputing the shortest path is much cheaper than the initial Dykstra algorithm used to compute a minimum spanning tree.
Pete Mack is offline   Reply With Quote
Old March 27, 2017, 21:37   #25
Nick
Vanilla maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 52
Posts: 6,454
Donated: $60
Nick is on a distinguished road
I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:
  • Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
  • Sight: If the monster sees the player, they can head straight for them. Easy.
  • Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
  • Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I would see this as a starting point - what do others think?
__________________
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 27, 2017, 22:44   #26
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,809
Derakon is on a distinguished road
Quote:
Originally Posted by Nick View Post
Sight: If the monster sees the player, they can head straight for them. Easy.
You say that, but what about lava, immobile monsters, and other such barriers?

Quote:
Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
Does this mean that we track noisiness on a per-tile basis? Do we track noises not caused by the player?

Quote:
Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.
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?
Derakon is offline   Reply With Quote
Old March 27, 2017, 22:57   #27
luneya
Adept
 
Join Date: Aug 2015
Posts: 105
luneya is on a distinguished road
Quote:
Originally Posted by Nick View Post
I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:
  • Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
  • Sight: If the monster sees the player, they can head straight for them. Easy.
  • Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
  • Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I would see this as a starting point - what do others think?
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.

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.
luneya is offline   Reply With Quote
Old March 27, 2017, 23:32   #28
t4nk
Adept
 
Join Date: May 2016
Posts: 246
t4nk is on a distinguished road
Quote:
Originally Posted by Nick View Post
I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:
  • Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
  • Sight: If the monster sees the player, they can head straight for them. Easy.
  • Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
  • Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I would see this as a starting point - what do others think?
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 (perhaps teleportation should make noise? presumably teleporting stuff leaves a pocket of vacuum that collapses with a loud sound - in gameplay terms, that's a method to nerf teleportation a bit).
The maps for stairs would allow to introduce monsters patrolling between stairs, like in Sil, which is cool and good for gameplay (IMO).
The smell idea is also good, it should make corridors a little bit more dangerous (and currently smell, as implemented, does very little, pretty much nothing in practice).
Also, if different actions produce different amounts of noise, that should be displayed in the UI (a la Dungeon Crawl).
t4nk is offline   Reply With Quote
Old March 27, 2017, 23:35   #29
bio_hazard
Knight
 
bio_hazard's Avatar
 
Join Date: Dec 2008
Posts: 562
bio_hazard is on a distinguished road
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?
bio_hazard is offline   Reply With Quote
Old March 27, 2017, 23:40   #30
Patashu
Swordsman
 
Patashu's Avatar
 
Join Date: Jan 2008
Posts: 493
Patashu is on a distinguished road
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'.
__________________
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu
Patashu 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 09:38.


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