Monster path finding in 4.0.5

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

[Sky]

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

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