Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old March 23, 2017, 18:42   #11
takkaria
Veteran
 
takkaria's Avatar
 
Join Date: Apr 2007
Posts: 1,827
Donated: $40
takkaria is on a distinguished road
Quote:
Originally Posted by t4nk View Post
Angband's pathfinding is the craziest thing ever.


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.
Well, the scent and noise point in the right direction, but then the monster has to set a 'target' grid (tx, ty). That's why that bizarre calculation is done.
__________________
"Physician, heal thyself."
takkaria is offline   Reply With Quote
Old March 23, 2017, 18:50   #12
debo
Veteran
 
debo's Avatar
 
Join Date: Oct 2011
Location: Toronto, Canada
Posts: 2,330
debo is on a distinguished road
The scent thing is actually really smart. There's a good writeup of it on roguenexus. (I implemented something similar recently on a personal project just with unit increments once a monster is in LOS and it works fine also.)
__________________
Glaurung, Father of the Dragons says, 'You cannot avoid the ballyhack.'
debo is offline   Reply With Quote
Old March 24, 2017, 02:22   #13
t4nk
Adept
 
Join Date: May 2016
Posts: 249
t4nk is on a distinguished road
Quote:
Originally Posted by takkaria View Post
Well, the scent and noise point in the right direction, but then the monster has to set a 'target' grid (tx, ty). That's why that bizarre calculation is done.
My impression is that mon->tx, mon->ty and side_dirs[] is the original pathfinding, and the noise map was added later and monsters don't make good use of it (e.g., RF_GROUP_AI monsters ignore it almost always?)
It definitely could use some improvements
t4nk is offline   Reply With Quote
Old March 24, 2017, 05:06   #14
Nick
Vanilla maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 52
Posts: 6,653
Donated: $60
Nick is on a distinguished road
Quote:
Originally Posted by t4nk View Post
My impression is that mon->tx, mon->ty and side_dirs[] is the original pathfinding, and the noise map was added later and monsters don't make good use of it (e.g., RF_GROUP_AI monsters ignore it almost always?)
It definitely could use some improvements
The side_dirs[] array is just hard-coding of "if I'm trying to go in a direction, what are the other directions in order of how close to the original" - so if you're trying to go down (2) it will give in order 2 (correct), 1 (45 degrees to the right), 3 (45 degrees to the left), 4 (90 degrees to the right), 6 (90 degrees to the left), etc. Notice this is right biased - the second half of the array is for left-biased. This part is all fine (if a bit unnecessary on today's hardware). How it is used is sub-optimal, though, because it allows the monster to move at right angles to the direction it wants to go if it is blocked; this definitely needs work.

mon->ty and mon->tx were introduced by me to give the monster a target it will remember rather than calculating it fresh every time, and the intent is to eventually turn these into a proper pathfind rather than just follow scent and noise locally.

As for the multiply by 16, that's meant to get a better fix on direction but sucks and should be replaced.

Thanks for bringing this up, I was planning to get to it soon; I had it fully in my head at one point, but at that stage was in my "no gameplay change before 4.0" mode so couldn't fix anything...
__________________
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 24, 2017, 05:41   #15
t4nk
Adept
 
Join Date: May 2016
Posts: 249
t4nk is on a distinguished road
Quote:
Originally Posted by Nick View Post
Notice this is right biased - the second half of the array is for left-biased.
Yes, I was initially confused why it says "right/left bias", but now I see that it means "from the perspective of the monster", e.g., when the monster is going south the directions 1, 4, 7 are on his right (from the monster's point of view).

Quote:
mon->ty and mon->tx were introduced by me
I know that Sil and Sangband have them too. Was that a part of 4GAI then?

I think that side_dirs[] thing could just be replaced by A* (when the monster is at some sensible distance, perhaps mon->race->aaf, or maybe when monster's square_isview()), and at bigger distances monsters should use the flow map, if the scent is recent enough for them...
Nick, do you plan to do something with monsters' "telepathy"? (that is, with them always knowing player->px and player->py?)
t4nk is offline   Reply With Quote
Old March 24, 2017, 09:26   #16
t4nk
Adept
 
Join Date: May 2016
Posts: 249
t4nk is on a distinguished road
So after playing with some different algorithms (courtesy of https://qiao.github.io/PathFinding.js/visual/) I think I like "Trace" the best (as far as I can tell, it's basically A* that gives more weight to grids that have the biggest number of adjacent walls). So the monsters tend to "hug" walls, which, IMO, makes them look more life-like (they still can find straight paths in simple situations).
t4nk is offline   Reply With Quote
Old March 24, 2017, 15:05   #17
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,020
Derakon is on a distinguished road
Bear in mind that any one-to-one pathfinding solution (where each monster calculates its own path to the player independent of other monsters) is likely to bog down even on modern computers, considering the number of monsters on the level and the size of the level. A* is a one-to-one pathfinding solution, unfortunately. The heatmaps work because they do a single pass to generate the heatmap, which all monsters can then share for their needs.

However, you can play fancy tricks with heatmaps to get monsters to prefer following walls or similar behaviors; you just need to tweak the "heat value" in each tile based on what's surrounding it. E.g. something like this:
Code:
heat in this tile = lowest adjacent tile heat + 10 - (number of adjacent walls)
Derakon is offline   Reply With Quote
Old March 24, 2017, 15:35   #18
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 4,316
Donated: $40
Pete Mack is on a distinguished road
@ derakon-- you don't have to do pathfinding for every monster. You do it to make a map starting from the player, to every room in the dungeon. (Symbolically, pinch a string network of the dungeon at the player's location, and let the rest of it hang down. Strings under tension become routes.) Then the monsters follow it in reverse.
Pete Mack is offline   Reply With Quote
Old March 24, 2017, 16:03   #19
t4nk
Adept
 
Join Date: May 2016
Posts: 249
t4nk is on a distinguished road
Quote:
Originally Posted by Derakon View Post
Bear in mind that any one-to-one pathfinding solution (where each monster calculates its own path to the player independent of other monsters) is likely to bog down even on modern computers, considering the number of monsters on the level and the size of the level. A* is a one-to-one pathfinding solution, unfortunately. The heatmaps work because they do a single pass to generate the heatmap, which all monsters can then share for their needs.
You shouldn't judge by the slowness of CPython's VM. Of course, there are limits, but generally, in C the performance of that kind of code is simply incomparable. I'm not even proposing to run A* on every single monster across the whole levels?
Example: Sil has about 400 flow tables. Consider melee2.c:4484. Yeah, I know, you haven't played Sil, but maybe you should
In any case, I going to reduce the size of levels and number of monsters, irregardless of pathfinding

Last edited by t4nk; March 24, 2017 at 16:16.
t4nk is offline   Reply With Quote
Old March 24, 2017, 17:38   #20
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 2,927
fizzix is on a distinguished road
Quote:
Originally Posted by Pete Mack View Post
@ derakon-- you don't have to do pathfinding for every monster. You do it to make a map starting from the player, to every room in the dungeon. (Symbolically, pinch a string network of the dungeon at the player's location, and let the rest of it hang down. Strings under tension become routes.) Then the monsters follow it in reverse.
So ideally you actually want several heat maps. One from the player, and a few more from static points in the map (steal a page from Sil's book and heatmap from each stair.) Then you can have monsters that wander around the level, as well as ones that are tracking the player.

In the original map posted, where the pit fiend could not find the path, this is essentially working as intended. The pit fiend knows where @ is, but the number of spaces between the fiend and @ is larger than the tracking distance (which is monster dependent with a hard cap at the heat map value, 256 I think). So the fiend can't actually track @. BUT the fiend is within the minimum tracking distance (as the crow flies), so it is considered active and tries to move towards @, which is why it hops up and down along that wall. If you move closer to the fiend at some point it will be able to track the player, and it will move appropriately.

Now in my ideal conception monsters would be split into different states of awareness. At one end there's asleep, and at the other end there's in LoS of the player. These work the same as currently. But I'd like two other states, aware that player is nearby, and aware that player has been seen recently (but teleported away or whatever). The first state would track almost as currently, but the second state, "aware that the player has been seen recently", would be more interesting. In this state the monster is encouraged to wander in a specific direction. (In the case where the monster was teleported, this could be the last seen location of the player, in the case where the player teleported, this could be some random far away point). Then we can add a fifth state, which is unaware of the player but wandering anyway. This is a good state for packs of hounds (if you can somehow keep them somewhat coherent.) FWIW I did try implementing this stuff upon a time, but I failed and gave up. I could never get alternate heat maps to work properly, which was an inability on my part entirely.

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.
fizzix 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 23:39
Finding a solution to ID Nick Vanilla 51 April 3, 2014 03:18
Path of Exile? HallucinationMushroom Idle chatter 68 December 2, 2013 15:11
Path to target request juggle5 Vanilla 9 May 17, 2011 14:07
Does Entroband reward one with experience for finding awesome items? BlackFlame Variants 3 February 18, 2010 08:28


All times are GMT +1. The time now is 05:32.


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