I'm beginner at Java and I want to make ghosts chase Pac-Man in game. I read some algorithm like A* or Dijkstra but I don't know how to implement them in my game. Please help me.
AI is not intelligent, it just acts like it
I don't think the effort of implementing such algorithms is worth, given the simplicity of a game such as Pac-Man.
I. Millington & J. Funge talk right about Pac-Man AI in their book "Artificial Intelligence for Games", paragraph 1.1.2:
[...] Pac-Man had definite enemy characters that seemed to conspire against you, moved around the level just as you did, and made life tough.
Pac-Man relied on a very simple AI technique: a state machine [...]. Each of the four monsters [...] was either chasing you or running away. For each state they took a semi-random route at each junction. In chase mode, each had a different chance of chasing the player or choosing a random direction. In run-away mode, they either ran away or chose a random direction. All very simple and very 1979.
Pac-Man developers didn't use neither A* or Dijkstra's algorithm for making enemies chase the player. Monsters who got at intersections chose a new, random direction (not turning back), one of which was the right one to chase the player.
The reason it worked smoothly was because "ghosts" were sort of cooperating and able to patrol most of the level, eventually trapping the player and killing them.
A simple solution
This said, you can try this approach instead of trying to implement A* in the first place. My suggested algorithm assumes that:
- Every level can be treated as a grid whose tiles' size is known, and level walls must be placed accordingly to such grid. A square grid is ideal for this purpose;
- Ghosts can move either horizontally or vertically, not diagonally;
- Ghosts reverse their horizontal and vertical speeds when collision with level walls occur.
Then, a generic ghost AI behavior to change path could be described as follows:
function ChangeDirection(): SPD = desired constant speed if horizontal speed == 0: if chance 1 out of 3 and no collisions leftwards: horizontal speed = -SPD vertical speed = 0 if chance 1 out of 3 and no collisions rightwards: horizontal speed = SPD vertical speed = 0 else if chance 1 out of 3 and no collisions downwards: horizontal speed = 0 vertical speed = -SPD if chance 1 out of 3 and no collisions upwards: horizontal speed = 0 vertical speed = SPD end
When implemented, this function must be executed when at least one of these two events occur:
- Grid snap: every time a ghost snaps with the grid (which means, every time its position is such that it fits perfectly inside a single grid tile), the function can be called to test the opportunity to change direction. This results in actual turning left or right when the monster reaches a corner or any crossing point; in any case, the
ChangeDirectionalgorithm doesn't allow a ghost to U-turn back;
- Wall collision: every time a ghost collides with a wall object, it means it can't move further, and a new direction to move towards is required. This time, we must consider the direction the ghost came from a valid path to be chosen; for this reason, before executing the
ChangeDirectionalgorithm we must tell the ghost to reverse its horizontal and vertical speeds, then the algorithm is applied: note that when colliding with a wall, the ghost is definitely snapping with our virtual level grid because we contrain its movements along the grid.
At this point a ghost's update function would look something like this:
function Update(): if colliding with wall at next step: reverse horizontal speed reverse vertical speed if ghost snaps to grid: ChangeDirection() update ghost position end
Note that we reverse both horizontal and vertical speed although we know only one of them is non-zero from time to time, just for the sake of a compact code.