Monster path finding in 4.0.5

[Pondlife]

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.

[Sky]

what about mobs that start awake? you would have half the dungeon on your back in a few turns.

[Derakon]

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.

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

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

[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]

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?

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

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

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

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

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

[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

[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]

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