2

I am building a similar game to Bubble Bobble. This is the scenario:

enter image description here

where E represents enemies, and P represents the player. If a user falls through the lower hole, it reappears through the superior one.

Assume that players can fall and jump.

Also, even though I said I based it on "Bubble Bobble", the characters can jump "through" platforms to go up. They have to find the proper corners.

My problem here is that I have to program the AI of the enemies, to find and search the player.

What would be the best algorithm to find the shortest path to meet the player?

Enrique Moreno Tent
  • 121
  • 4
  • Consider modelling your map as a graph. – Benjamin Hodgson Feb 23 '15 at 22:02
  • Interesting, Could you expand a little on that? – Enrique Moreno Tent Feb 23 '15 at 22:03
  • Well, you'd put nodes at key waypoints in the map, and edges connecting nodes that can be 'easily' navigated. To chase down the player, enemies would compute the shortest path between themselves and the player using a shortest-path algorithm such as Dijkstra's (or its more sophisticated brother A*). Of course you'd need to tune the algorithm to achieve a fun/difficulty balance. AFAIK this approach is the engine of most AI-navigation applications in games. – Benjamin Hodgson Feb 23 '15 at 22:06
  • Could you maybe post an example on how would you layout the nodes? I also need to be able to calculate in which cases I need to jump upwards, fall downwards or maybe jump to avoid falling while moving horizontally. – Enrique Moreno Tent Feb 24 '15 at 09:05
  • I'm not a game developer so you'd probably get some better advice from Google. (I know that's a cop-out, sorry!) – Benjamin Hodgson Feb 24 '15 at 13:42

1 Answers1

10

"The best algorithm to achieve this"? Define "best". A simple A* algorithm will generate the most efficient possible path for an enemy to take to reach the player, but would you really want to play against a perfect computer? That's a recipe for frustration right there.

The Pac-Man "AI" was actually 4 very simple algorithms that told the 4 ghosts where to move towards, which gave each one a distinct "personality" and hunting style. If they acted intelligently and worked together, they could hunt Pac-Man down, corner him, and kill him consistently, and it would suck to play the game. Instead, the developer came up with a system that is challenging but fun. For something like this, I'd advise a similar tactic: come up with a handful of different simplistic algorithms and test them to see what version(s) are the most fun, individually and together.

Mason Wheeler
  • 82,151
  • 24
  • 234
  • 309
  • 3
    +1. For more info see [The Pac-Man Dossier](https://home.comcast.net/~jpittman2/pacman/pacmandossier.html). The ghost AI is very naive and simple; they only look at which tile in a crossroad is closest to the target, regardless of the path through the maze they'll have to take to get there. The only difference between them is what they consider the target to be. E.g. the red one targets your tile, but the pink one targets a square a few steps ahead. It works remarkably well, and as far as most people can tell both ghosts appear to be coordinating to box you in. – Doval Feb 23 '15 at 22:17
  • Thanks for the input. I upvoted it, because it is very interesting. But my question points towards figuring out how to make the enemy navigate the map. I guess you suggest making a graph, as Benjamin does. Could you maybe give me more info how you would layout the nodes in this specific case? – Enrique Moreno Tent Feb 24 '15 at 09:04
  • 1
    @Dbugger: If the map was just a grid of squares, from which each character can move in the four cardinal directions (and maybe diagonally?), Pac-Man style, this could be trivially modeled as a graph in which each square is a node and each open connection between two squares is an edge. Of course, if the world model contains gravity, then not all movement directions are equal, so that makes the calculations a bit more complicated. Try Googling "pathfinding for platformers" for some helpful research in this area. – Mason Wheeler Feb 24 '15 at 09:44