Introduction

I was creating a game inspired from Pacman to brush up my coding skills that I learnt on the first semester of college only to come across a road block. How will the ghosts track the player and move towards you? The solution I used is the Greedy Best-First Search. Now before we dive into it we must first familiarize ourselves with how the ghosts move in the game itself.

Understanding the Ghost’s Movement

The ghost moves on a grid, where its primary goal is to either chase Pac-Man or, when scared, run away from him. To decide where to move next, the ghost needs to evaluate all possible directions and choose the best one. This is where pathfinding comes in. Specifically, the ghost evaluates its potential moves using a heuristic called the Manhattan Distance.

The Concept of Manhattan Distance

Manhattan Distance is a simple but effective way to measure the distance between two points on a grid. The term comes from the layout of streets in the Manhattan borough of New York, where streets are aligned in a grid pattern. In this system, the distance between two points is calculated by summing the absolute differences of their respective x and y coordinates.

For example, if the ghost is at position (2, 3) and Pac-Man is at (5, 5), the Manhattan Distance would be:

Horizontal distance = |5 - 2| = 3 Vertical distance = |5 - 3| = 2 Total Manhattan Distance = 3 + 2 = 5

Directions Array

The ghost can move up, down, left, or right and these options are represented as:

private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  • {-1, 0}: Move up
  • {1, 0}: Move down
  • {0, -1}: Move left
  • {0, 1}: Move right

The Pathfinding Method

The main method that determines the ghost’s movement is:

private int[] findBestPath(char[][] grid, int targetRow, int targetCol, boolean away)

Parameters:

  • grid: The game grid, which includes walls (‘W’), (‘c’) and (‘f)
  • targetRow, targetCol: The position of the player
  • away: A boolean that indicates if the ghost should move toward (false) or away from (true) the target.

Return Value:

The best direction (e.g., {1, 0} for moving down), or null if no valid move is found.

Movement Logic

The ghost uses the Manhattan Distance to evaluate its moves. This heuristic calculates the distance to the target as:

For each direction:

  1. The ghost checks if moving in that direction is valid using isValidMove.
  2. It calculates the Manhattan Distance from the potential new position to the target.
  3. It selects the move with the smallest distance (to chase) or the largest distance (to run away).

Supporting Methods

  • isValidMove: Ensures the ghost doesn’t move into walls or outside the grid boundaries.
  • isCollidingWithGhost: Prevents ghosts from colliding with each other.
  • updateGrid: Updates the game grid to reflect the ghost’s new position.

Example Walkthrough

Let’s say the ghost is at (2, 3) and Pac-Man is at (5, 5):

The algorithm evaluates all possible moves:

  • Up: (1, 3), distance = 6
  • Down: (3, 3), distance = 4
  • Left: (2, 2), distance = 6
  • Right: (2, 4), distance = 4

If away == false (not scared), the ghost chooses the move with the smallest distance (Down or Right).

If away == true (scared), the ghost chooses the move with the largest distance (Up or Left).

Pros:

  • Simplicity: The algorithm is easy to implement and computationally lightweight.
  • Speed: Evaluating only four directions makes it fast, especially on small grids.

Cons:

  • No Global Optimization: It doesn’t guarantee the shortest or most efficient path to the target.
  • Heuristic Limitations: The Manhattan Distance works well for simple grids but may not handle complex obstacles effectively.

Conclusion

Game Over.. The Greedy Best-First Search algorithm is an excellent choice for games like Pac-Man, where simplicity and responsiveness are key. It balances efficiency with functionality, allowing ghosts to behave dynamically without requiring heavy computations. By tweaking elements like the scare duration or movement randomness, developers can fine-tune ghost behavior for an engaging player experience.