Finding a moving target in a maze

Question

I'm making a game that is a bit of a mix of snake and pacman.

Basically, two players go through the maze and each time they pick up a piece of candy, a cube is added to their tail. If one player touches the other's tail, he steals that piece for himself and the game is over when one player has all the pieces.

Right now they both move randomly unless there's a piece of candy one space away that is not their tail.

I'm trying to find a method/algorithm (preferably a different method for each player) for both players to target/avoid the other player. Any advice?

Answer 1

For an algorithm that finds paths for snakes eating fruit, see this related question: How to find a safe path for an AI snake?

As for the adversarial part - snakes eating each other's tails - unfortunately you've created a game where either: both players can force a draw, or the game will never end. This is because:

• The game only ends if one player loses their whole tail (i.e. left with just a head)
• The snakes move one grid at a time at the same speed, and they can either:
  • Both move towards each other (reduce distance by 2)
  • One moves towards the other, the other moves away (distance unchanged)
  • Both move away from each other (increase distance by 2)

So the only way a game could end is if the snakes are an odd distance away, because that's the only way one snake could eat the other's tail completely, and this happens:

..ht    .ht.    hH..     Snake 1: ht (lose)
....    .H..    .T..     Snake 2: HT (win)
TH..    .T..    ....

But notice that snake 1 could always force a draw if it also moves towards the other snake, making their heads run into each other. Also note that if the snakes are an even distance away, the game could never end.

So you'll need to change your game design, like add other winning conditions, such as:

• Player that eats the most things (candy or tail) wins
• Normal snakes: players can't each other's tails, or only conditionally (after eating a powerup?)
• Snakes can move at variable speeds
• Eliminate the draw condition (e.g. only the larger snake wins if both heads collide)

Answer 2

It depends on how complex you want your AI behaviors to be. If you want the most realistic, do some research on the A* algorithm. The other easier option would most likely be depth first search. Definitely look into AI pathfinding and you should find your solution.