PATHFINDING

A* (A-Star) is a pathfinding algorithm that finds the shortest route between two points by making educated guesses.

Think of it as a person in a maze holding a compass pointing to the exit.

How it works (The 3 Steps)

When a Ghost is at an intersection, A* looks at the available tiles and gives each one a "Score" (F) based on two numbers:

G-Cost (Distance Walked): How far have I travelled from the start to get here?
H-Cost (The Guess): How far is it from here to the target "as the crow flies"? (This is the compass part).

The Formula:

Score = Distance Walked + Distance Left

The Difference

Dumb Pathfinding (Dijkstra): Checks every possible path in a circle, expanding outward like a puddle of water until it hits the target. It's accurate but slow.
A Pathfinding:* Checks the paths that point toward the target first. If a path moves away from the target, A* ignores it unless all other options are blocked.

In Pac-Man Terms

When a Ghost asks "Which way should I go?", A* calculates:

Left Turn: Moves away from Pac-Man. (High Score = Bad).
Right Turn: Moves closer to Pac-Man. (Low Score = Good).

The Ghost picks the lowest score and moves that way immediately.

In the Main Scene Add a script to Main

Create references to

TileMapLayer

Player

Create variables for the

AStarGrid

The Tile Size

AStarGrid2D is a built-in class which is specialized for partial 2D grids. It is simpler to use because it doesn't require you to manually create points and connect them together. This class also supports multiple types of heuristics, modes for diagonal movement, and a jumping mode to speed up calculations.

Create a function to setup the grid

The grid region is our tile map

The cell size is our tile size

We don't allow diagonal movement

Update the grid

Manhattan Movement restricts movement to:

UP, DOWN, LEFT, RIGHT

Next, loop through all tiles to find obstacles

Because we painted the physics layers

If a tile has a collision shape it gets

Marked as a solid. (Obstacle)

Create a function to get a path for the ghost

Convert world pixels to grid coordinates
Save the starting cell and target cell

Ask astargrid to find a path
Save it in a variable

Convert the grid coordinates back into

World pixels for the ghost to move to

Get Ghost Path Function Explained

This function is the "Translator" between the Ghost (who lives in a world of pixels) and the Grid (which lives in a world of integer coordinates).

Here is the breakdown using a Ghost at pixel (50, 50) trying to reach Pac-Man at (100, 50).

Tile Size is 24x24.

The Code Breakdown

1. The Inputs

func get_ghost_path(start_global_pos: Vector2, target_global_pos: Vector2) -> Array[Vector2]:

What it does: The function takes the Ghost's actual screen position (start_global_pos) and Pac-Man's screen position (target_global_pos).
Example Data:
- start_global_pos = (50, 50) (Ghost)
- target_global_pos = (100, 50) (Pac-Man)

2. Convert Pixels -> Grid ID

var start_cell = tile_map.local_to_map(to_local(start_global_pos))

var target_cell = tile_map.local_to_map(to_local(target_global_pos))

What it does: The AStar grid doesn't know what "50 pixels" means. It only knows "Tile 1" or "Tile 2". We convert the specific pixel location into a generic tile ID.
The Math: Roughly 50 / 24 = 2.08. We round down to 2.
Example Data:
- start_cell becomes Vector2i(2, 2)
- target_cell becomes Vector2i(4, 2)

3. Ask for the Path

var id_path = astar_grid.get_id_path(start_cell, target_cell)

What it does: We ask the AStar algorithm: "How do I get from Tile (2,2) to Tile (4,2)?" AStar checks its map of walls and finds the steps.
Example Data: id_path becomes a list of tiles:
- [(2, 2), (3, 2), (4, 2)]
- (Start -> Step Right -> Arrive)

4. Prepare the Output List

GDScript

var path_world_points: Array[Vector2] = []

What it does: Creates an empty list to store the final result.

5. The Loop: Grid ID -> Center Pixels

for cell_id in id_path:

var world_pos = tile_map.map_to_local(cell_id)

path_world_points.append(world_pos)

What it does: This is the most crucial step. The Ghost cannot move to "Tile (3, 2)" directly; it needs a pixel coordinate.
Why map_to_local? If we just multiplied 3 times 24, we would get 72. That is the top-left corner of the tile. If the ghost moves there, it will scrape the wall.
The Magic: map_to_local returns the center of the tile.
1. 72 (corner) + 12 (half size) = 84.
Example Data Loop:
1. Convert Tile (2, 2) => (60, 60) pixels.
2. Convert Tile (3, 2) => (84, 60) pixels.
3. Convert Tile (4, 2) => (108, 60) pixels.

6. The Return

return path_world_points

What it does: Sends this list of cantered pixel coordinates back to the Ghost.
Result: The Ghost now receives: [(60, 60), (84, 60), (108, 60)]. It can now simply slide from point to point and stay perfectly in the middle of the tunnel!

To test the pathfinding

Add a debug variable

Call setup_pathfinding

In the ready function

Create a function to draw

A red debug line

In the process function

Draw the line from 1,1 to Player

Test the game to check that a path is constantly redrawn to the player

PATHFINDING

How it works (The 3 Steps)

The Difference

In Pac-Man Terms

In the Main Scene Add a script to Main

Create references to

TileMapLayer

Player

Create variables for the

AStarGrid

The Tile Size

Create a function to setup the grid

The grid region is our tile map

The cell size is our tile size

We don't allow diagonal movement

Update the grid

Manhattan Movement restricts movement to:

UP, DOWN, LEFT, RIGHT

Next, loop through all tiles to find obstacles

Because we painted the physics layers

If a tile has a collision shape it gets

Marked as a solid. (Obstacle)

Create a function to get a path for the ghost

Convert world pixels to grid coordinates
Save the starting cell and target cell

Ask astargrid to find a path
Save it in a variable

Convert the grid coordinates back into

World pixels for the ghost to move to

Get Ghost Path Function Explained

The Code Breakdown

To test the pathfinding

Add a debug variable

Call setup_pathfinding

In the ready function

Create a function to draw

A red debug line

In the process function

Draw the line from 1,1 to Player

Test the game to check that a path is constantly redrawn to the player

Pacman Player

Pacman Ghosts

PATHFINDING

How it works (The 3 Steps)

The Difference

In Pac-Man Terms

In the Main Scene Add a script to Main

Create references to

TileMapLayer

Player

Create variables for the

AStarGrid

The Tile Size

Create a function to setup the grid

The grid region is our tile map

The cell size is our tile size

We don't allow diagonal movement

Update the grid

Manhattan Movement restricts movement to:

UP, DOWN, LEFT, RIGHT

Next, loop through all tiles to find obstacles

Because we painted the physics layers

If a tile has a collision shape it gets

Marked as a solid. (Obstacle)

Create a function to get a path for the ghost

Convert world pixels to grid coordinatesSave the starting cell and target cell

Ask astargrid to find a pathSave it in a variable

Convert the grid coordinates back into

World pixels for the ghost to move to

Get Ghost Path Function Explained

The Code Breakdown

To test the pathfinding

Add a debug variable

Call setup_pathfinding

In the ready function

Create a function to draw

A red debug line

In the process function

Draw the line from 1,1 to Player

Test the game to check that a path is constantly redrawn to the player

Pacman Player

Pacman Ghosts

Convert world pixels to grid coordinates
Save the starting cell and target cell

Ask astargrid to find a path
Save it in a variable