Monster path finding in 4.0.5

[Pete Mack]

@ 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.

[Derakon]

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:

heat in this tile = lowest adjacent tile heat + 10 - (number of adjacent walls)

[t4nk]

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]

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).

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?)

[Nick]

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...

[t4nk]

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

[debo]

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.)

[takkaria]

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.

[t4nk]

Angband's pathfinding is the craziest thing ever.

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.

[Nick]

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.

[Derakon]

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.

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.

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.

[Pondlife]

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?

[Pete Mack]

Dykstra works on graphs. You'd run the algorithm on rooms, not squares. But I don't know what to do about destructed areas.

[Pondlife]

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?

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.

[kandrc]

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.