From Grid to Graph

Before we can run pathfinding algorithms, we need to understand how a 2D grid becomes a graph. This mapping is the foundation for everything that follows.

What is a Graph?

A graph is a collection of:

• Nodes (vertices): Points or locations
• Edges: Connections between nodes
• Weights: Costs associated with edges (optional)

Think of a social network: people are nodes, friendships are edges. Or a road map: intersections are nodes, roads are edges, distances are weights.

Grid as Graph

A 2D grid maps naturally to a graph:

Grid cell = Node

• Each cell in the grid becomes a node
• Each node has coordinates (row, col)

Movement = Edge

• Moving to a neighbor creates an edge
• In a 4-direction grid: up, down, left, right
• In an 8-direction grid: includes diagonals

Movement cost = Weight

• Each edge has a weight (usually 1)
• Can vary: grass = 1, road = 0.5, mud = 2

Obstacles = No edges

• Walls block movement
• No edges connect to or from wall cells

Simple Example

Let’s look at a 4×4 grid with one obstacle:

[ ] [ ] [ ] [ ]
[ ] [X] [ ] [ ]
[ ] [ ] [ ] [ ]
[S] [ ] [ ] [G]

Where:

• S = Start
• G = Goal
• X = Wall
• [ ] = Empty cell

This becomes a graph with:

• 15 nodes (16 cells minus 1 wall)
• Edges connecting neighbors (up/down/left/right)
• Weights of 1 for each edge

Visualizing the Graph

Here’s how the grid maps to graph structure:

Nodes:

• (0,0), (0,1), (0,2), (0,3)
• (1,0), (1,2), (1,3) ← (1,1) is wall, so no node
• (2,0), (2,1), (2,2), (2,3)
• (3,0), (3,1), (3,2), (3,3)

Edges (examples):

• (0,0) → (0,1) with weight 1
• (0,0) → (1,0) with weight 1
• (1,0) → (2,0) with weight 1
• No edges to/from (1,1) because it’s a wall

Neighbors in a Grid

For a cell at position (row, col), its neighbors depend on movement type:

4-direction movement (up, down, left, right):

• (row-1, col) - up
• (row+1, col) - down
• (row, col-1) - left
• (row, col+1) - right

8-direction movement (includes diagonals):

• All 4-direction neighbors, plus:
• (row-1, col-1) - up-left
• (row-1, col+1) - up-right
• (row+1, col-1) - down-left
• (row+1, col+1) - down-right

Diagonal moves often have higher cost (√2 ≈ 1.41) to account for longer distance.

Edge Costs

Edge weights represent the cost of moving between cells:

Uniform cost:

• All moves cost 1
• Simplest case
• Good for basic pathfinding

Variable cost:

• Different terrain types have different costs
• Grass = 1, Road = 0.5, Mud = 2, Water = 5
• Algorithms find cheapest path considering terrain

Example:

[G] [R] [G]
[G] [M] [G]

Where G=Grass(1), R=Road(0.5), M=Mud(2)

The path might prefer roads even if slightly longer, because 0.5 + 0.5 = 1.0 < 2.0 (mud cost).

Graph Representation in Code

Here’s how you might represent this in code:

# Grid as 2D array
grid = [
    [0, 0, 0, 0],  # 0 = empty, 1 = wall
    [0, 1, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

# Get neighbors of a cell
def get_neighbors(row, col, grid):
    neighbors = []
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right
    
    for dr, dc in directions:
        new_row, new_col = row + dr, col + dc
        # Check bounds
        if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]):
            # Check if not a wall
            if grid[new_row][new_col] != 1:
                neighbors.append((new_row, new_col))
    
    return neighbors

# Example: neighbors of (0, 0)
# Returns: [(1, 0), (0, 1)]

Visualizing the Grid Structure

Here’s a simple example of how a grid maps to a graph. Each cell can be a node, and movement between cells creates edges:

Hover to See Details

When you hover over a cell in the grid above, you can see:

• Its coordinates (row, col)
• Its neighbors (up to 4 in 4-direction movement)
• Edge costs (usually 1)

This helps you see that the graph isn’t abstract - it’s a concrete representation of the grid.

Key Takeaways

Before moving forward:

1. Grid cells = Graph nodes - Each cell becomes a node
2. Movement = Edges - Moving to neighbors creates edges
3. Costs = Weights - Each edge has a weight (movement cost)
4. Walls block edges - No edges connect to/from walls
5. Neighbors depend on movement type - 4-direction vs 8-direction

What’s Next?

Now that we understand how grids become graphs, we’re ready to explore Dijkstra’s algorithm. It will use this graph structure to find the cheapest path from start to goal.