Running the Maze

This weekend I’ve been busy programming “mobiles”, creatures that can move around in the maze. In fact, I’ve implemented two mobiles, George and the roach. George is a simple guy; there’s a treasure chest, and he means to find it, provided that he doesn’t get killed doing so. The roach is even simpler: it has a magnetic attraction to George, and will always move closer to George if it can. It’s not smart about walls, though, so it often gets stuck in corners.

The game is simple. If the roach catches George, it wins. If George gets to the chest before the roach catches him, he wins. If George can’t get to the chest but the roach can’t get him, it’s a draw.

Early on in development, George got eaten a lot; he was smart about moving to the chest, but dumb about avoiding the roach. He’s smarter, now, but he still gets eaten sometimes. Here’s an animation that shows the action.

Dead george

More frequently, the roach just gets stuck somewhere rather distant from George. As I say, the roach is no genius.

Roach stuck

And once in a while, things get exciting.

George avoids

George is pretty smart. At each step, he figures out the best route to the chest that doesn’t get too close to the roach. If there is none, he’ll back away from the roach until he gets stuck. But if a route opens up, he’ll take it.

  • By karrde, December 10, 2012 @ 10:51 am

    Interesting how the same algorithm works well or poorly, depending on the maze and the starting positions.

  • By Will Duquette, December 10, 2012 @ 11:27 am

    Actually, George’s algorithm works pretty well in almost every case where there’s any way for to avoid the Roach. I had to dig for a case where George gets eaten. What I didn’t show were the rare cases where both George and the Roach get stuck: George can avoid the Roach, but can’t get to the Chest because the Roach is in the way.

Other Links to this Post

WordPress Themes