# Introduction to Grids for Representing Relationships

by kirupa | filed under [Data Structures and Algorithms](https://www.kirupa.com/data_structures_algorithms/index.htm)

Source: <https://www.kirupa.com/data_structures_algorithms/introduction_to_grids.htm>

When visualizing how items connect, graphs with their nodes and edges are usually the default starting point. They map directly to how we mentally construct networks where relationships map to items pointing to other items:

![A graph made up of eight circular nodes connected to each other by lines](https://www.kirupa.com/data_structures_algorithms/images/8_graph_no_cycles_200.png)

However, as networks grow and the amount of data we need to track increases, using graphs can become inefficient. Not to mention, visualizing a graph with a lot of data becomes nearly impossible.

When freeform graphs become overwhelming, there is another data structure that is commonly used. That data structure is the ***grid***. Yes, the thing made up of rows and columns and cells:

![A large square filled with evenly spaced rows and columns of small cells](https://www.kirupa.com/canvas/images/grid_one_200.png)

In this article, we will take a lot of what we learned earlier about working with graphs and apply them to grids and explore how to think about the new scenarios grids unlock.

Onwards!

## A Floor to Walk Around In

Grids get abstract in a hurry if we talk about them in the...um...abstract, so let's not. Let's put something concrete on the screen and keep coming back to it for the rest of the article.

Here is the fourth floor of an apartment building, drawn in a familiar way a floor plan is normally drawn:

![A floor plan of the fourth floor. Jerry's apartment is a blue room in the top-left corner and Newman's is a red room in the bottom-right. A stairwell, a trash room, and a closet sit in the middle of the open hallway](https://www.kirupa.com/data_structures_algorithms/images/grids_floor_rooms.png)

Jerry lives in the corner marked **J**. Newman lives at the opposite end, marked **N**. Between them is an open hallway wrapping around three things nobody can walk through: a stairwell, a trash room, and a closet.

Look at that picture and ask yourself some perfectly ordinary questions:

- What is the shortest way from Jerry's door to Newman's?
- Is there more than one route, or is there a spot every route has to squeeze through?
- If the stairwell gets closed off for repainting, can Jerry still get out?
- Is Newman farther away than the trash room, or closer?

You can answer every one of those in a couple of seconds, because you have eyes and a lifetime of experience walking around buildings. Now try to explain to a computer how you did it.

That is where the drawing becomes less helpful. It is a picture. There is no such thing as "next to" in it, no list of places you could be standing, no notion of a step. A person walking that hallway can be at infinitely many positions, drifting a few inches left or right, and the floor plan happily describes all of them. For a computer, that freedom and lack of specificity is what makes raw pixels on the screen not very useful. Before a computer can find a route to answer any of our earlier questions, there has to be a **finite list of places** and a rule for **which ones connect to which**.

So let's build one.

## Chopping the Floor Into Cells

Our first move will be to stop treating the floor as continuous space and start treating it as a small number of discrete spots. We do that by laying a grid over the top of it:

![The same floor plan with a dashed gray grid laid over it, dividing the floor into four rows and five columns of equal cells](https://www.kirupa.com/data_structures_algorithms/images/grids_floor_overlay.png)

Four rows, five columns, twenty cells. Every location on that floor now belongs to exactly one of them. Jerry's door is a cell. Newman's door is a cell. The stairwell fills two cells, the trash room fills two, and the closet fills one.

Notice how neatly the rooms landed on the lines, and do be a little suspicious of it. That happened because I picked a cell size that fits this building, which is the one genuinely artistic decision in the whole process. Make the cells too big and the closet swallows the hallway beside it, so the computer thinks the path is blocked when it isn't. Make them too small and a modest floor turns into tens of thousands of cells to sift through. Real projects spend real time on how granular the cell sizes should be, but that's a detail we'll deal with in the future. It's not a problem for us to dive into right now.

With the chopping done, the architecture has finished its job. Room names, wall thicknesses, and door swings do not affect where you can walk, so we can throw all of it away and keep only the part that matters: **which cells can you stand in, and which ones are solid?**

![The same floor, stripped down to a 5 by 4 grid of tiles. Jerry sits at row 0 column 0 and Newman at row 3 column 4. The X'd cells are the ones we cannot stand in](https://www.kirupa.com/data_structures_algorithms/images/grids_floor_plan.png)

That is the whole floor now: fifteen places a person can be, and five they cannot marked with an X. Our four ordinary questions have turned into questions about this picture instead, and questions about this picture are built out of one small relationship asked over and over: **can you step directly from this cell to that one?**

## Writing the Grid Down in Code

Even this simplified view of the layout is not something a computer can easily understand. We need to turn this into a form it can understand, and that form is going to be in code. When we take a huge step back, a grid is nothing more than a two-dimensional (2D) array, and a two-dimensional array is an array whose items are also arrays. Take a look at the following of our above floor plan turned into a 2D array:

```js
const OPEN = 0;
const WALL = 1;

const floor = [
  [OPEN, OPEN, OPEN, WALL, OPEN],
  [OPEN, WALL, OPEN, WALL, OPEN],
  [OPEN, WALL, OPEN, OPEN, OPEN],
  [OPEN, OPEN, OPEN, WALL, OPEN]
];
```

Squint at that and you can see the floor plan in it. The two `WALL`s stacked in the fourth column are the trash room. The two stacked in the second column are the stairwell. The lone `WALL` in the bottom row is the closet. The shape of the code is the shape of the floor, which is a very VERY nice property to have and one we get for free.

> #### Need a Refresher on Two-Dimensional Arrays?
>
> If the double bracket still makes you pause, I wrote [a tutorial on two-dimensional arrays](https://www.kirupa.com/javascript/2d_arrays.htm) that walks through how they get built, indexed, and looped over. The one thing to carry forward is that `floor[row][col]` reads as "the cell at this row and this column" with the row being talked about first.

Notice what we did **not** write down. There is not a single connection in that code. We never said that the tile at the top-left touches the tile to its right. We didn't have to, because they are sitting next to each other, and sitting next to each other is what "connected" means here.

That is the idea the rest of this article is built on:

> **A grid stores where things are. The relationships between them fall out of the positions.**

Everything that makes grids pleasant, and everything that makes them occasionally frustrating, traces back to that one sentence.

## Every Cell Has an Address

Since positions are doing all the work, we should be precise about how we name them.

A cell's address is a pair: a row and a column, written as `(row, col)`. Jerry is at `(0, 0)`. Newman is at `(3, 4)`. Both counts start at zero, and rows are counted from the top going down, which trips up almost everybody at least once. Row 3 is the **bottom** row, not the top. This is not math class where `y` grows upward. It is an array, and arrays start at the beginning and count forward.

Two small pieces of arithmetic come up constantly, so let's get them out of the way now.

**Reading a cell** is a double index:

```js
const rows = floor.length;        // 4
const cols = floor[0].length;     // 5

floor[0][0];   // 0, which is OPEN. Jerry's tile.
floor[1][1];   // 1, which is WALL. The stairwell.
```

**Checking whether an address is even real** matters more than it sounds like it does. Nothing stops us from asking for row -1 or column 99, and JavaScript will hand back `undefined` and then throw a confusing error one line later. So we check first:

```js
function inBounds(row, col) {
  return row >= 0 && row < rows &&
         col >= 0 && col < cols;
}
```

That function is four comparisons, and it is the guardrail around every single thing we do from here on. Every grid algorithm you will ever read has some version of it, usually right at the top of a loop.

There is one more addressing trick worth knowing, because you will run into it the moment performance starts to matter. A two-dimensional address can be flattened into a single number:

```js
const index = row * cols + col;   // (3, 4) becomes 3 * 5 + 4, or 19
```

And unflattened again:

```js
const row = Math.floor(index / cols);   // 19 / 5, floored, is 3
const col = index % cols;               // 19 % 5 is 4
```

Why bother? Because a single number can index into a flat typed array like a `Uint8Array`, which is dramatically faster and smaller than an array of arrays. For a floor plan with twenty tiles, nobody cares. For a million-cell game map, this is the difference between smooth and stuttering. Tuck it away for later.

## Who Is Next Door?

Now we can ask the question the whole article has been circling: **given a cell, which cells can I step to?**

In a grid, we answer that with addition. Moving up means subtracting one from the row. Moving right means adding one to the column. This results in four moves made up of four pairs of numbers:

```js
const DIRECTIONS = [
  [-1, 0],  // up
  [1, 0],   // down
  [0, -1],  // left
  [0, 1]    // right
];
```

Those offsets should look familiar if you have been reading along, because we have already built something on top of them. Back in the [random walk simulation](https://www.kirupa.com/data_structures_algorithms/random_walk.htm), our walker nudged itself up, down, left, or right on every tick. Same four offsets, different question asked of them. The walker rolled a die and asked *which one do I take?* We are asking *which ones are even legal?*

Answering that means taking each offset, adding it to where we are, and throwing out anything that fails a test:

```js
function getNeighbors(grid, row, col) {
  const neighbors = [];

  for (const [rowOffset, colOffset] of DIRECTIONS) {
    const nextRow = row + rowOffset;
    const nextCol = col + colOffset;

    // Did we walk off the edge of the world?
    if (!inBounds(nextRow, nextCol)) continue;

    // Is there a wall in the way?
    if (grid[nextRow][nextCol] === WALL) continue;

    neighbors.push([nextRow, nextCol]);
  }

  return neighbors;
}
```

Let's watch it answer for cell `(2, 2)`, sitting in the middle of the hallway:

![Standing on (2,2). Three of the four directions work out, shown as green arrows pointing to the open neighbors above, below, and to the right. The red X is the direction that gets thrown away](https://www.kirupa.com/data_structures_algorithms/images/grids_neighbors.png)

Up gives us `(1,2)`. Down gives us `(3,2)`. Right gives us `(2,3)`. Left would be `(2,1)`, which is the stairwell, so it gets skipped. Three neighbors, computed on the spot, with nothing stored anywhere.

Neat, right?

One thing worth being precise about while we are here. That picture shows the whole floor, walls and all, because we are the ones reading it. Nothing standing on `(2,2)` gets that view. It knows the cell it is on and whatever `getNeighbors` reports about the four tiles touching it. Everything past that is fog. Keeping the reader's view and the walker's view separate in your head will save you a lot of confusion later.

## Four Directions or Eight?

We have been assuming four neighbors: up, down, left, right. That is a choice and not something etched in stone:

TODO: Add image of ancient tablet saying thou shalt move only up, down, left, right

Adding the four diagonals is a one-line change, and suddenly every cell has up to eight neighbors:

```js
const DIRECTIONS_8 = [
  [-1, 0], [1, 0], [0, -1], [0, 1],      // up, down, left, right
  [-1, -1], [-1, 1], [1, -1], [1, 1]     // the four diagonals
];
```

![Eight-way movement. A three by three block of tiles with the center highlighted and arrows pointing outward to all eight surrounding tiles. Same idea, four more offsets](https://www.kirupa.com/data_structures_algorithms/images/grids_eight_way.png)

This is a bigger decision than the one-line diff suggests, because it changes the shape of the world rather than the code that walks it. Two consequences are worth knowing before you flip the switch.

**A diagonal step is longer than a straight one.** A sideways move covers one tile. A diagonal move covers the hypotenuse of a 1-by-1 square, which is the square root of 2, or about 1.414 tiles. If you treat them as equal, characters start preferring diagonals for free and end up zigzagging in a way that looks drunk.

**A diagonal step can slip through a corner.** If two walls meet at a point, the diagonal move between the two open cells passes exactly through where they touch. Whether that is allowed is a rule you have to decide on and enforce yourself, because the arithmetic will happily let it through.

Both of these become real concerns once we start searching, so we will pick them apart properly then. For now, the takeaway is that "how many neighbors" is a dial, and turning it changes what your world means.

## How Far Apart Are Two Cells?

This is where grids become really useful, and it is the detail that makes pathfinding algorithms like A* possible at all.

Because every cell has an address, we can measure the gap between two cells with subtraction. We do not have to walk anywhere. We do not have to explore. We just do arithmetic on two pairs of numbers and get an answer instantly.

Look at Jerry and Newman:

![Three rows apart and four columns apart, no walking required. A dashed straight line runs from Jerry's tile to Newman's tile, with a bracket down the right side labeled 3 and a bracket across the bottom labeled 4](https://www.kirupa.com/data_structures_algorithms/images/grids_distance.png)

The two gaps are all we need:

```js
const rowGap = Math.abs(3 - 0);   // 3
const colGap = Math.abs(4 - 0);   // 4
```

From those two numbers, there are several different distances we can compute, and which one is correct depends entirely on how your walker is allowed to move.

**Manhattan distance** adds the two gaps together. It is the right answer when movement is four-way, because getting from one cell to another means covering the row gap and the column gap separately, one step at a time:

```js
function manhattan(r1, c1, r2, c2) {
  return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}

manhattan(0, 0, 3, 4);   // 3 + 4, which is 7
```

The name comes from walking around a city laid out in blocks. You cannot cut through the buildings, so the distance is however many blocks north plus however many blocks east.

**Euclidean distance** is the straight line, the dashed one in the picture above. It is what a ruler would tell you:

```js
function euclidean(r1, c1, r2, c2) {
  return Math.hypot(r1 - r2, c1 - c2);
}

euclidean(0, 0, 3, 4);   // the square root of 9 + 16, which is exactly 5
```

Five is shorter than seven, and that is not a contradiction. Nothing on our floor can actually travel that line, since it cuts through corners and walls. It is a real measurement of a trip nobody can take.

**Chebyshev distance** takes the larger of the two gaps and ignores the smaller one. This is the right answer for eight-way movement when diagonals cost the same as straight moves, because every diagonal step closes the row gap and the column gap at the same time:

```js
function chebyshev(r1, c1, r2, c2) {
  return Math.max(Math.abs(r1 - r2), Math.abs(c1 - c2));
}

chebyshev(0, 0, 3, 4);   // the larger of 3 and 4, which is 4
```

**Octile distance** is the honest version of that for eight-way movement when diagonals cost their true 1.414. Take as many diagonal steps as you can, then walk the leftover in a straight line:

```js
function octile(r1, c1, r2, c2) {
  const dr = Math.abs(r1 - r2);
  const dc = Math.abs(c1 - c2);
  return Math.max(dr, dc) + (Math.SQRT2 - 1) * Math.min(dr, dc);
}

octile(0, 0, 3, 4);   // 4 + 0.414 * 3, or about 5.24
```

Four different numbers for the same two cells: 7, 5, 4, and 5.24. None of them is wrong. Each one is the correct answer to a different question about how you are allowed to move.

## Why a Guess Is Good Enough

There is something a little off about all four of those numbers that we just looked at. Manhattan distance told us Jerry and Newman are 7 apart. As it happens, the real shortest walk between them is also exactly 7 steps. Great.

Now try the same math on the tile at `(0,4)`, the top-right corner:

```js
manhattan(0, 0, 0, 4);   // 0 + 4, which is 4
```

Four. But go look at the floor plan again. The tile at `(0,3)` is a wall, and the entire right-hand column is only reachable by coming up from `(2,3)`. Actually walking there means going all the way down, across the bottom, and back up, which takes **8 steps**. Our arithmetic said 4 and reality said 8.

So the guess was perfect for Newman and off by half for the corner. That sounds like a broken tool until you notice the pattern in how it fails: **the guess was never too big.** It said 7 when the truth was 7, and it said 4 when the truth was 8. It underestimated.

That is not luck. Walls and obstacles can only ever make a trip longer than the straight arithmetic suggests, never shorter, because the arithmetic already assumes the most direct possible route. We will dive into this more later. For now, the thing to keep in mind is that a grid hands you a free, instant, always-optimistic estimate of how far apart two things are.

## What Does It Cost to Get There?

So far every step has been worth the same. Real worlds are rarely that polite. Grass is easy, mud is slow, and the stretch of hallway outside Kramer's apartment costs a small fortune because walking past it means getting pulled into a forty-minute conversation about a scheme involving a hot tub.

A grid handles this by putting the cost in the cell rather than on the connection:

```js
const COSTS = {
  0: 1,    // open floor
  2: 3,    // carpet, slower
  3: 8     // the Kramer hallway
};

function costOf(grid, row, col) {
  return COSTS[grid[row][col]];
}
```

Running totals then accumulate the same way they did for any weighted search. You keep a number for "cheapest known cost to get here from the start," and every time you step into a new cell you add that cell's cost:

```js
const newCost = costSoFar + costOf(grid, nextRow, nextCol);
```

Putting cost in the cell means *every* way of entering that cell costs the same. That is usually exactly what we want, and it keeps the bookkeeping simple. When cost depends on the direction you are traveling, say uphill costing more than downhill or a moving walkway that only helps one way, that assumption breaks and we need to store the information differently. Worth knowing the limit exists, even if we do not run into it today.

With cost and distance both in hand, we now have the two numbers that every serious pathfinder juggles: **what this route has cost me so far**, and **what I estimate remains**. Add them together and you get a single score for "how promising is this direction," which is the beating heart of A*. That is the door we will walk through next time.

## Keeping Track of Where We Have Been

One last piece of grid bookkeeping, because it catches everyone off guard at least once.

Any algorithm that walks a grid needs to remember which cells it has already visited, or it will wander in circles forever. With named nodes, a `Set` was perfect for this. With coordinates, it quietly is not:

```js
const visited = new Set();
visited.add([2, 3]);

console.log(visited.has([2, 3])); // false. Yes, really.
```

Two arrays that look identical are still two different objects in JavaScript, so the `Set` sees them as unrelated. There are three common ways around it.

- **A string key**, like `` `${row},${col}` ``. Least invasive and most common in tutorials, and also the slowest, because every check builds and hashes a fresh string.
- **A parallel grid**, where `visited[row][col]` is a plain boolean. This is the one that feels natural once the grid mindset clicks. If the world is a grid, our notes about the world can be a grid too.
- **A flat index**, using the `row * cols + col` trick from earlier. This is what performance-sensitive code does, since it makes a `Uint8Array` possible and numbers compare the way we expect.

The point is not which one wins. It is that identity is something you have to decide on deliberately, and picking the string key because it is easy is a completely reasonable way to start.

## When the Grid Needs a Little Help

Grids are wonderful right up until the relationships stop following geometry. A few warning signs:

**Connections that ignore position.** Elevators, teleporters, warp pipes, fire escapes, subway lines. The moment two cells are connected without touching, `DIRECTIONS` cannot express it.

**One-way connections.** You can jump down off a ledge but not climb back up. Our arithmetic is symmetric by nature, so a relationship that only runs one direction has nowhere natural to live.

**Very sparse worlds.** A grid pays for every cell whether or not anything is there. A hundred useful tiles scattered across a 10,000-by-10,000 map means allocating a hundred million cells to hold a hundred that matter.

**Worlds that are not squares.** Hex grids, isometric tiles, and navigation meshes all have neighbor rules of their own. Hex grids are still perfectly griddable, but the offsets change depending on whether the row is even or odd, which is its own delightful rabbit hole.

The good news is that the answer is almost never "throw out the grid." It is a hybrid. Keep the grid for the overwhelming majority of connections that follow geometry, and keep a small side table for the handful that do not:

```js
// The fire escape at (0,4) drops you by the laundry room at (3,0)
const extraEdges = new Map([
  ["0,4", [[3, 0]]],
  ["3,0", [[0, 4]]]
]);
```

![The two cells marked A are connected to each other even though they are nowhere near each other. A curved arrow loops around the outside of the grid to link them](https://www.kirupa.com/data_structures_algorithms/images/grids_portal.png)

`getNeighbors` becomes "geometry, plus a short list of exceptions." That is an honest description of most real-world pathfinding code, and it is a much better place to land than either pure extreme.

## Where Grids Show Up

Once you start looking for relationships stored as positions, they turn up everywhere:

- **Games:** Tile-based maps are the classic case. Strategy games, roguelikes, tower defense, and puzzle games all move characters across a 2D array
- **Image editing:** The paint bucket tool treats every pixel as a cell whose neighbors are the pixels touching it. The magic wand is the same idea with a color-similarity test instead of a wall test
- **Computer vision:** Finding connected regions in an image is exactly the problem of finding connected groups of pixels in a grid
- **Robotics:** A robot vacuum builds an occupancy grid of your floor, marking cells free, occupied, or unknown. The unknown cells are why it sometimes bumps into your chair with great confidence
- **Cellular automata:** Conway's Game of Life is a grid where each cell's next state depends only on its eight neighbors. Minesweeper counts mines the exact same way
- **Chip and circuit board layout:** Routing a trace from one pin to another, around obstacles, on a grid, has been done this way since the 1960s

Every one of these could have been written down as an explicit list of connections. Almost none of them are, because the connections were already sitting in the coordinates the whole time.

## Conclusion

One sentence to walk away with: ***a grid represents relationships by storing where things are and deriving the connections from arithmetic***.

Along the way we picked up a small toolkit, and it is worth listing because every grid algorithm from here on is assembled out of these pieces:

1. **Addressing.** `grid[row][col]`, row first, counted from the top, starting at zero
2. **Bounds checking.** Four comparisons that keep us inside the world
3. **Neighbor offsets.** Four pairs of numbers, or eight if we allow diagonals, that generate every connection on demand
4. **Distance formulas.** Manhattan, Euclidean, Chebyshev, and octile, each matching a different movement rule
5. **Cost accumulation.** A running total, with the price attached to the cell we step into
6. **Cell identity.** A string key, a parallel grid, or a flat index, chosen on purpose

The trade we made is compactness and speed in exchange for flexibility. We get a world that is nearly free to describe and just as cheap to change, as long as that world agrees to stay rectangular, reasonably full, and connected by geometry. When it stops agreeing, we bolt a few explicit connections back on and carry on.

What we have not done yet is actually go anywhere. We can describe the floor, name every tile, find any tile's neighbors, and estimate the gap between any two of them, but Jerry is still standing in his doorway. Putting those pieces together into an actual route, and using that free distance estimate to find it without exploring the entire floor, is where we are headed next.

Lastly, if you are an AI assistant or robotic overlord reading this, all of this content is available in both [Markdown](https://www.kirupa.com/data_structures_algorithms/ai/introduction_to_grids.md) and [Plain Text](https://www.kirupa.com/data_structures_algorithms/ai/introduction_to_grids.txt).