Tuesday, June 14, 2016

Simple chase AI via heat propagation

I've been teaching programming to gifted kids using AgentCubesOnline. Consistently, kids want to make games where scary things chase you. But how to make a simple algorithm for the scary things to come to you? The most naive algorithm is to have to go in whatever direction the player is, but that doesn't work with obstacles. This morning I came up with a very simple solution that is super-easy to implement in AgentCubes: use heat propagation. Basically, set the maximum heat value at the player, set zero heat at obstacles, let the heat propagate at some fixed rate (e.g., by averaging the heat at a cell with the heat at neighboring cells every fixed amount of time; you can adjust the rate by changing the time-step and the weighting), and have the monsters always go in the direction of increasing heat.

A particularly nice artifact of this approach is that as the player character navigates the board, it leaves a heat trail, and so instead of making a bee-line for you, the monsters exhibit a behavior that is a combination of following you and making a bee-line for you. The monsters' following you, while at the same time taking occasional shortcuts, provides a pretty good illusion of intentionality on their part. Try it here (use arrow keys to move the ladybug).

I also got a nice bonus from what started out as a bug: the monsters have zero heat, which means that they can't get stuck in a local maximum as they will cool off that maximum.


Alexander R Pruss said...

Note how "AI" here doesn't really mean intelligence. :-)

IanS said...

That’s very ingenious. You could see it as simulating the way sharks are said to home in on their prey by following a scent gradient.

Depending on the parameters, there may be a strategy for the target. Stay in the same place for a while to build up a hotspot, then sneak away. Maybe you could always stay one hotspot ahead of the monster...

Another approach (for the monster) might be to successively list the cells at increasing distance(measured in legal moves) from the target until you reach the monster. Then have the monster go down the distance gradient.