Roguelike AI – 6: A simple chase-and-follow heuristic.

By now, most of you probably know about A* pathfinding. It’s the best general pathfinding algorithm there is for quickly finding the shortest path to a given location in a maze, and it can make your monsters seem very smart and very familiar with the dungeon.

But you can give a whole herd of monsters a surprisingly smart “chase and follow” behavior that works a whole lot faster than A*. You can do this for three different reasons; First, your monsters don’t necessarily have to find the shortest path. Second, a whole lot of monsters can share the work. Third, you’ve already done most of the work when you calculated LOS.

The place to start is with the character’s line-of-sight calculations. When doing LOS calculations, you find all the monsters, walls, floortiles, etc, that are in the player’s line-of-sight. And this information, since you’re calculating it anyway, can be put to additional uses.

Since the monsters also need to know about line-of-sight to the player, you can save yourself most monster LOS calculations by storing the current LOS information in the map. That way, if the monster needs to do a Line-of-sight check on the character, it can just check the floortile it’s standing on for a line-of-sight marker, and if it finds one, it knows it has current LOS on the character.

One thing is that if you’re going to do LOS for monsters with the same calculation, you do have to do LOS for unlit squares, so your LOS calculations will get somewhat heavier in terms of CPU expended since you can’t take the usual out of a limited light radius to mean you don’t need LOS calcs for your full sight range.

If line-of-sight were just binary, you’d have to traverse all the squares turning it off every time the character moved, then traverse again turning it back on. That’s clearly a waste of effort, so instead of storing a bit, store a number. Each time you calculate line of sight, use a higher number. That way, you never have to re-traverse setting all these numbers to zero; if you can’t see something this round, then its LOS number is not going to be the LOS number of the current round. Basically, this amounts to just letting the LOS “expire” at the end of the round by switching to a higher number. But it leaves old LOS numbers lying around in tiles the character could once see, and these turn out to be useful for chasing the character.

The last thing you need to have to set up the monster “chase and follow” behavior this article is about, is the distance to the player character. Along with each LOS marker, store the distance to the character at the moment that LOS marker was computed. This has additional uses such as range checks for monsters with ranged attacks who have the character in current line-of-sight, but mostly it’s useful because monsters can use it to tell which direction to run.

Now your monsters can “chase and follow” in a competent way for no real investment of computer power; What’s stored in each square the character has seen, just as a result of doing the player’s line of sight calculations, is the last time it was visible to the character, and how far away the character was at the time. This is enough information to “track” the PC through the dungeon. Each monster that’s doing a chase-and-follow behavior just looks around itself to see if there’s a square that has a later LOS number than the square it’s on. If it finds one, it steps to that square. If all the squares around it have the same LOS number, it looks for one with a shorter range. If it finds it, it steps to that square.

This enables monsters to “chase” the character, doing their best to always keep him in sight, going around corners, finding their way through picky mazes even frequently taking shortcuts the character didn’t take, etc. And for each one of them, it’s a simple constant-time calculation.

It doesn’t make them particularly smart; they’ll be more likely to go the way the character went than going the shortest path. But it’s fast enough for hordes of monsters to do it without slowing anything down, and it’s usually very good results, and in the heat of the moment Snagrak the Goblin Archer probably isn’t going to think of the shortcut anyway.

There are a couple of ways to make it better. First, you can have monsters make outdated LOS marks (follow marks) in a few squares around themselves whenever they move doing chase-and-follow, so other monsters can follow the extra marks even if they’re standing on squares the PC has never actually seen.

Let’s say a monster is standing on a LOS mark of 455/23, meaning that on turn 455, the character was 23 squares away, and adjacent to itself it finds a LOS mark of 499/12; This LOS mark was made 44 turns later, and at a closer distance. Now, it steps to the new square, because the trail is much “hotter” – but it can share the good news with other nearby monsters too. In a radius of 2 squares around its old location, it puts down LOS markers of 498/101, 498/102, etc, in any square where that’s “hotter” than the mark that’s there now. This alerts any monster who’s doing “chase and follow” in that area to the more recent sighting of the character. And as they follow these marks, they’ll spread slightly colder marks of 497/101, 497/102, etc. for other monsters to follow. As long as the marks they spread are colder than the marks they’re following, this works excellently, even if it only spreads new marks in a radius of 1 or 2 squares.

This makes it so that if some monster in a room catches a glimpse of the character, it “shouts to its buddies” before giving chase, and the whole bunch of the monsters in that room come pouring out. Different monsters can vary in terms of how far the “shout” carries; pack hunters are likely to bay or howl (radius 5) and a milling mob or crowd is likely to become vaguely aware of you gradually (radius 0 or 1).

Another thing you can do is to have previous-round LOS marks – which are really “follow marks” – spread by floodfill from the character on some actions, such as teleporting, making a loud noise, using a cursed/aggravating item, or randomly about once every 50 turns (meaning that Snagrak and his buddies *do* remember the shortcut sometimes). The depth of the floodfill can be limited, proportional to the noise made, or if dinged by a curse by an enemy spellcaster, it can be the whole dungeon wide.

This yields a “chase and follow” behavior which is so good it’s necessary to put restrictions on it. In the first place, make it so “unintelligent” monsters can’t follow LOS marks more than some number of (say 20?) rounds old.

You can implement “scent tracking” by restricting the LOS marks that a scent tracker responds to, to either very recent or range zero.

You can restrict the “yelling to your buddies” behavior above to intelligent monsters and pack hunters.

And if you want a few *really* intelligent monsters, have them hunt the character using a more sophisticated pathfinding mechanism such as A* or similar, but lay down a trail of “follow marks” so that unintelligent monsters follow them on their shorter path to your player’s location.