Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old January 30, 2017, 18:43   #1
Pondlife
Scout
 
Join Date: Mar 2010
Location: UK
Posts: 32
Pondlife is on a distinguished road
Monster path finding in 4.0.5

It seems that monsters who can detect the player are still unable to reach him despite an obvious route. See the attached screenshot: the pit fiend knows I'm there because it moves up and down in lockstep with me; but cannot reach me because it seems to be unable to work out the path. It just keeps bashing its head against the wall.

I think something like A* (A star) or Dijkstra's algorithm should be able to cope with this sort of path-finding. And the current behaviour seems too simplistic, especially for intelligent monsters like a major demon.

Perhaps a better monster path-finding algorithm would tone down the power of TO a bit, by allowing more monsters to make their way back to the player rather than getting trapped like the pit fiend in the screenshot.
Attached Thumbnails
Click image for larger version

Name:	Tanion_2017Jan29_cropped.jpg
Views:	25
Size:	12.4 KB
ID:	1499  
__________________
Playing roguelikes on and off since 1984.
rogue, hack, moria, nethack, angband & zangband.
Pondlife is offline   Reply With Quote
Old January 30, 2017, 18:53   #2
Sky
Adept
 
Join Date: Oct 2016
Location: Glasgae
Age: 44
Posts: 238
Sky is on a distinguished road
what about mobs that start awake? you would have half the dungeon on your back in a few turns.
Sky is offline   Reply With Quote
Old January 30, 2017, 19:15   #3
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,629
Derakon is on a distinguished road
Quote:
Originally Posted by Pondlife View Post
It seems that monsters who can detect the player are still unable to reach him despite an obvious route. See the attached screenshot: the pit fiend knows I'm there because it moves up and down in lockstep with me; but cannot reach me because it seems to be unable to work out the path. It just keeps bashing its head against the wall.

I think something like A* (A star) or Dijkstra's algorithm should be able to cope with this sort of path-finding. And the current behaviour seems too simplistic, especially for intelligent monsters like a major demon.
A* pathfinding is Dijkstra's algorithm with a heuristic that improves average runtime in most cases. Anyway, it's too expensive to run in Angband where there may be hundreds of units moving around the level. I speak from experience; it was what I tried using when I was working on Pyrel, and the game chugged when there were substantial numbers of monsters. The maps are big (thousands of tiles) and the solutions returned by A* are 1-to-1, (so you have to calculate once for every monster on the level).

Angband uses a "heat map" approach instead, where each turn, tiles close to the player are marked by how close they are (so the player's tile is 0, adjacent to that is 1, adjacent to the 1s are 2, etc.), and monsters can pathfind simply by moving to the adjacent tile with the lowest number. That's very efficient for many-to-1 pathfinding, but requires creating the heat map each turn. I believe what you're seeing here is simply that the heat map generation routine caps how far it's willing to fill out before it stops, as a speed optimization, and any monsters that aren't on the heat map just use straight-line pathfinding.

We should experiment with making larger heat maps, since the current constraint is probably based on hardware that's at least a decade old. But I very much doubt we'll move to A* pathfinding anytime soon.
Derakon is offline   Reply With Quote
Old January 30, 2017, 19:27   #4
kandrc
Adept
 
Join Date: Dec 2007
Posts: 105
kandrc is on a distinguished road
Quote:
Originally Posted by Derakon View Post
A* pathfinding is Dijkstra's algorithm with a heuristic that improves average runtime in most cases. Anyway, it's too expensive to run in Angband where there may be hundreds of units moving around the level. I speak from experience; it was what I tried using when I was working on Pyrel, and the game chugged when there were substantial numbers of monsters. The maps are big (thousands of tiles) and the solutions returned by A* are 1-to-1, (so you have to calculate once for every monster on the level).

Angband uses a "heat map" approach instead, where each turn, tiles close to the player are marked by how close they are (so the player's tile is 0, adjacent to that is 1, adjacent to the 1s are 2, etc.), and monsters can pathfind simply by moving to the adjacent tile with the lowest number. That's very efficient for many-to-1 pathfinding, but requires creating the heat map each turn. I believe what you're seeing here is simply that the heat map generation routine caps how far it's willing to fill out before it stops, as a speed optimization, and any monsters that aren't on the heat map just use straight-line pathfinding.

We should experiment with making larger heat maps, since the current constraint is probably based on hardware that's at least a decade old. But I very much doubt we'll move to A* pathfinding anytime soon.
Since every monster is heading toward @, you only need to do pathfinding once per @ turn (not once per monster turn, which would be prohibitive). And BFS will do the job faster than Dijkstra, since every move has the same weight. This gives linear performance and you can do full-dungeon heat maps faster than the user can interact this way (only open space gets processed; tunnelers just move in straight lines). Users definitely *would* notice the lag when running, however.

If you really want to get smart about it, you can short-circuit BFS to stop once you've got a map to (from) the final awake monster who deigns to chase intruders.

But this does make for some badass monsters that find @ right away, no matter what.
kandrc is offline   Reply With Quote
Old January 30, 2017, 19:54   #5
Pondlife
Scout
 
Join Date: Mar 2010
Location: UK
Posts: 32
Pondlife is on a distinguished road
Quote:
Originally Posted by Derakon View Post
Angband uses a "heat map" approach instead, where each turn, tiles close to the player are marked by how close they are (so the player's tile is 0, adjacent to that is 1, adjacent to the 1s are 2, etc.), and monsters can pathfind simply by moving to the adjacent tile with the lowest number. That's very efficient for many-to-1 pathfinding, but requires creating the heat map each turn. I believe what you're seeing here is simply that the heat map generation routine caps how far it's willing to fill out before it stops, as a speed optimization, and any monsters that aren't on the heat map just use straight-line pathfinding.
I seem to remember some options in old versions like "flow by smell" and "flow by sound", but I think they were marked as experimental. 3.0 maybe? Did they go anywhere, or were they dead ends?

Quote:
We should experiment with making larger heat maps, since the current constraint is probably based on hardware that's at least a decade old. But I very much doubt we'll move to A* pathfinding anytime soon.
Making the heat-maps larger could improve things. At the moment it seems like TO is too powerful because it often ends up bottling-up monsters like this unless they have passwall.
__________________
Playing roguelikes on and off since 1984.
rogue, hack, moria, nethack, angband & zangband.
Pondlife is offline   Reply With Quote
Old January 30, 2017, 19:55   #6
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 3,660
Donated: $40
Pete Mack is on a distinguished road
Dykstra works on graphs. You'd run the algorithm on rooms, not squares. But I don't know what to do about destructed areas.
Pete Mack is offline   Reply With Quote
Old January 30, 2017, 19:58   #7
Pondlife
Scout
 
Join Date: Mar 2010
Location: UK
Posts: 32
Pondlife is on a distinguished road
Quote:
Originally Posted by Sky View Post
what about mobs that start awake? you would have half the dungeon on your back in a few turns.
Well, that's one downside for sure. But I think there are two questions:

1. Does the monster know where @ is? and
2. Can the monster find a path to @?

In my case, the U knows where I am, but can't find a path to me. But awake monsters would only know about the position of @ when they are in range wouldn't they?
__________________
Playing roguelikes on and off since 1984.
rogue, hack, moria, nethack, angband & zangband.
Pondlife is offline   Reply With Quote
Old January 30, 2017, 20:11   #8
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 7,629
Derakon is on a distinguished road
Quote:
Originally Posted by Pete Mack View Post
Dykstra works on graphs. You'd run the algorithm on rooms, not squares. But I don't know what to do about destructed areas.
Yeah, if it weren't for the fact that the map can be altered once created, there's any number of easy optimizations we could make.

Quote:
Originally Posted by kandrc
Since every monster is heading toward @, you only need to do pathfinding once per @ turn (not once per monster turn, which would be prohibitive).
I believe this is already the case; apologies for not being clear what I meant about "each turn". Though if a monster happens to chew through a wall and open a new short path to the player, ideally other monsters would notice the new path immediately rather than pathfind using stale data. In practice I suspect that such an error is so rare and trivial as to not be worth worrying about.

Quote:
Originally Posted by Pondlife
In my case, the U knows where I am, but can't find a path to me. But awake monsters would only know about the position of @ when they are in range wouldn't they?
I dimly recall that different monsters have different awareness levels, which indicate how far away they can be from @ while still getting updates. Sauron, Morgoth, all Zephyr hounds, etc. have max awareness and thus will chase you from across the level (assuming they can find a path), but many monsters will simply give up if they get far enough away from the player. I could be wrong about this though; it's been awhile since I looked at that part of the code.
Derakon is offline   Reply With Quote
Old January 30, 2017, 20:17   #9
Nick
Vanilla maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 51
Posts: 6,187
Donated: $60
Nick is on a distinguished road
I believe (I was looking at it during the no-gameplay-change phase) that there are simple optimisations which will probably fix the specific problem in the OP. I'm planning to get back to that stuff before too long.
__________________
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 online now   Reply With Quote
Old March 23, 2017, 13:44   #10
t4nk
Adept
 
Join Date: May 2016
Posts: 202
t4nk is on a distinguished road
Angband's pathfinding is the craziest thing ever.

Quote:
Originally Posted by Derakon View Post
Angband uses a "heat map" approach instead, where each turn, tiles close to the player are marked by how close they are (so the player's tile is 0, adjacent to that is 1, adjacent to the 1s are 2, etc.), and monsters can pathfind simply by moving to the adjacent tile with the lowest number.
If only it was so simple!

So, yeah, does anyone know why pathfinding is the way it is? What the hell is this hackery with side arrays, multiplying "flow" coordinates by 16 (?) and adding to player's position and... I mean, I don't even.
t4nk 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 07:49.


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