Wednesday, 28 November 2012

Monster pathfinding

I once wrote an algorithm which enabled a computer character to find its way through a maze. I didn't really know what I was doing at the time, but I got the idea when I heard about some research into robots that work together to solve problems. I came up with the idea of a character that replicated itself throughout a maze until it found the exit, then sent a message back through all its clones to the origin point, and then highlighted the path. Not necessarily the best path, but a path nonetheless.

Then I heard about a bit of research which showed that if you put a blob of slime mould in a maze, it eventually grows into a shape that shows you the most efficient path through the maze. Here's a video which is in German, but looks quite cool:

I didn't know it, but I had stumbled upon something similar to the A* Pathfinding algorithm, which is a commonly used method for giving computer characters some form of artificial intelligence.

Think about a game where a monster is trying to get you. The monster might just walk towards you all the time, but what if there is a wall in between you and the creature? Should it just stop, or should it try to get around the obstacle to get at you? If so, which direction should it go? And what if it's not just a single obstacle, but the monster is trying to navigate a field of obstacles to get to you?

This sort of thing goes on all the time in games. Think about a game like Starcraft, where you click a point on a map to send troops, and they have to walk around rocks or lakes to get there. Pathfinding has to happen often, and it must happen quickly. It looks like the A* method is popular and powerful, but I don't think I can use it my Dudegame because my maps are not simple grid systems. They have obstacles all over the place, and not in regularly spaced intervals. I could rework the mapping system, and make all the obstacles fit to regular patterns, but I don't want to. I think for now I'll just use dumb monsters that either follow a preset path or just move blindly towards you. I don't think Zelda had clever monsters, and that seemed to work out OK.

No comments:

Post a Comment