Grid parts and relationships

from Red Blob Games
Jan 2006, then May 2021
faceedgevertex

This guide will show coordinate systems for tiles (faces), vertices (corners), and edges for square, hexagon, and triangle[1] grids. There are algorithms for going from a tile to its corners, an edge to its tiles, and many others. For a more detailed guide to hexagons, see my guide to hexagonal grids. For more on square grids, see my pages on edges, line-drawing, and circle fills.

Part A (black)Part B (red)
FaceEdgeVertex
FaceNeighbors:
Neighbors of a square
Borders:
Borders of a square
Corners:
Corners of a square
EdgeJoins:
Joins of an edge
Continues:
Continuation of an edge
Endpoints:
Endpoints of an edge
VertexTouches:
Vertex touching
Protrudes:
Vertex protrusion
Adjacent:
Adjacent vertices

The names and definitions here are arbitrary. This page isn't about the way to set up relationships, but one way to set up relationships. You'll want to adapt these for your own project. For example, you might choose to have neighbors and adjacent include diagonals. You might choose continues to include edges that aren't colinear. You might choose additional relationships. I hope this page gives you ideas for designing your own system for your project.

This page is an updated version of my 2006 guide to grid parts[2].

 1  Square grids#

Square grids are common. In both 2D and 3D graphics systems, we have to transform “world” coordinates into “screen” coordinates and back. With grids, we also have to transform “grid” coordinates into “world” coordinates and back. The world↔screen transform will be different for a top-down or side or isometric view, but the grid↔world transform works the same. This page covers the grid coordinates only and not the transforms.

 1.1. Coordinates

PartDiagramNotes
Tile0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,21,1;Square tiles are the default choice because they're easy to work with. I'm using "y down" on this page but everything works the same if you use "y up".
Vertex,,,,,,,,1,1; 0,0,0,1,1,1,1,0,0,2,1,2,0,3,1,3,2,1,2,0,2,2,2,3,3,1,3,0,3,2,3,3Each square has 4 vertices. We can choose 1 vertex that is each shared with 4 tiles. Here, I've picked the northwest vertex, but any of them will do.
Edge,,,,,,,,1,1; 0,0,N,0,0,W,0,1,N,1,0,W,0,1,W,0,2,N,1,1,W,0,2,W,0,3,N,1,2,W,1,0,N,1,1,N,2,0,W,1,2,N,2,1,W,1,3,N,2,2,W,2,0,N,2,1,N,3,0,W,2,2,N,3,1,W,2,3,N,3,2,WThere are four edges per square. You can either keep them separate or share them with adjacent squares. Here I'm using the west edge shared with the east edge of the adjacent tile, and the north edge shared with the south edge of the adjacent tile.

 1.2. Relationships

Each of these 9 relationships can be expressed as taking an input and generating a list of outputs. For some types of input there is a different rule for each s value.

RelationshipDiagramFormula
Neighbors
q,rq,r-1q-1,rq,r+1q+1,rq,r
q,r-1
q-1,r
q,r+1
q+1,r
Borders
q,rq,r,Nq,r,Wq,r+1,Nq+1,r,Wq,r
q,r,N
q,r,W
q,r+1,N
q+1,r,W
Corners
q,rq,rq,r+1q+1,r+1q+1,rq,r
q,r
q,r+1
q+1,r+1
q+1,r
Joins
W
q,rq-1,rq,r,Wq,r,W
q,r
q-1,r
Joins
N
q,r-1q,rq,r,Nq,r,N
q,r-1
q,r
Continues
W
q,r-1,Wq,r+1,Wq,r,Wq,r,W
q,r-1,W
q,r+1,W
Continues
N
q-1,r,Nq+1,r,Nq,r,Nq,r,N
q-1,r,N
q+1,r,N
Endpoints
W
q,rq,r+1q,r,Wq,r,W
q,r
q,r+1
Endpoints
N
q+1,rq,rq,r,Nq,r,N
q+1,r
q,r
Touches
q,rq,r-1q-1,r-1q-1,rq,rq,r
q,r
q,r-1
q-1,r-1
q-1,r
Protrudes
q,r,Wq,r,Nq,r-1,Wq-1,r,Nq,rq,r
q,r,W
q,r,N
q,r-1,W
q-1,r,N
Adjacent
q,r+1q+1,rq,r-1q-1,rq,rq,r
q,r+1
q+1,r
q,r-1
q-1,r

 2  Hexagon Grids#

In this article, I use pointy-topped hexagons, but the math works the same if you want flat-topped hexagons. To construct hexagon coordinates, we can start with a square grid and morph it into a hexagon grid:


This is the "axial" coordinate system from my comprehensive hexagonal grid guide[3]. That page has more coordinate systems and many more algorithms.

 2.1. Coordinates

PartDiagramNotes
Tile0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,21,1;There are many coordinate systems for hexagonal grids. This one is the "axial" system. See my hexagonal grid guide for more.
Vertex,,,,,,,,1,1; 0,0,N,0,-1,S,-1,1,N,0,0,S,0,1,N,1,-1,S,-1,2,N,0,1,S,0,2,N,1,0,S,-1,3,N,0,2,S,0,3,N,1,1,S,1,0,N,1,1,N,2,-1,S,1,2,N,2,0,S,1,2,S,1,3,N,2,1,S,2,0,N,2,1,N,3,-1,S,2,2,N,3,0,S,2,2,S,2,3,N,3,1,SEach hexagon has 6 vertices. We can choose 2 vertices that are each shared with 3 tiles. Here, I've picked the north and south vertices, but there are many ways to do this.
Edge,,,,,,,,1,1; 0,0,NE,0,0,NW,0,0,W,-1,1,NE,0,1,NW,1,0,W,0,1,NE,0,1,W,-1,2,NE,0,2,NW,1,1,W,0,2,NE,0,2,W,-1,3,NE,0,3,NW,1,2,W,1,0,NE,1,0,NW,1,1,NW,2,0,W,1,1,NE,1,2,NW,2,1,W,1,2,NE,0,3,NE,1,3,NW,2,2,W,2,0,NE,2,0,NW,2,1,NW,3,0,W,2,1,NE,2,2,NW,3,1,W,2,2,NE,1,3,NE,2,3,NW,3,2,WThere are six edges per hexagon. You can either keep them separate or share them with adjacent hexagons. Here they are shared.

 2.2. Relationships

RelationshipDiagramFormula
Neighbors
q,rq,r+1q+1,rq+1,r-1q,r-1q-1,rq-1,r+1q,r
q,r+1
q+1,r
q+1,r-1
q,r-1
q-1,r
q-1,r+1
Borders
q,rq,r,NEq,r,NWq,r,Wq-1,r+1,NEq,r+1,NWq+1,r,Wq,r
q,r,NE
q,r,NW
q,r,W
q-1,r+1,NE
q,r+1,NW
q+1,r,W
Corners
q,rq,r,Nq,r-1,Sq-1,r+1,Nq,r,Sq,r+1,Nq+1,r-1,Sq,r
q,r,N
q,r-1,S
q-1,r+1,N
q,r,S
q,r+1,N
q+1,r-1,S
Joins
NE
q+1,r-1q,rq,r,NEq,r,NE
q+1,r-1
q,r
Joins
NW
q,rq,r-1q,r,NWq,r,NW
q,r
q,r-1
Joins
W
q,rq-1,rq,r,Wq,r,W
q,r
q-1,r
Endpoints
NE
q+1,r-1,Sq,r,Nq,r,NEq,r,NE
q+1,r-1,S
q,r,N
Endpoints
NW
q,r,Nq,r-1,Sq,r,NWq,r,NW
q,r,N
q,r-1,S
Endpoints
W
q,r-1,Sq-1,r+1,Nq,r,Wq,r,W
q,r-1,S
q-1,r+1,N
Touches
N
q+1,r-1q,rq,r-1q,r,Nq,r,N
q+1,r-1
q,r
q,r-1
Touches
S
q,rq,r+1q-1,r+1q,r,Sq,r,S
q,r
q,r+1
q-1,r+1
Protrudes
N
q,r,NEq+1,r-1,Wq,r,NWq,r,Nq,r,N
q,r,NE
q+1,r-1,W
q,r,NW
Protrudes
S
q,r+1,NWq-1,r+1,NEq,r+1,Wq,r,Sq,r,S
q,r+1,NW
q-1,r+1,NE
q,r+1,W
Adjacent
N
q+1,r-2,Sq,r-1,Sq+1,r-1,Sq,r,Nq,r,N
q+1,r-2,S
q,r-1,S
q+1,r-1,S
Adjacent
S
q-1,r+1,Nq-1,r+2,Nq,r+1,Nq,r,Sq,r,S
q-1,r+1,N
q-1,r+2,N
q,r+1,N

For squares and triangles, I defined the Continues relation for collinear edges, but with hexes there aren't any. It would be reasonable to define them to be non-collinear edges. Don't take the relations here as the way to define the relations; they're one way to define them. Adapt the rules here to match the needs of your project.

 3  Triangle Grids#

Triangles are common in 3d graphics but are less commonly used for game maps. In this article I use triangles pointed up and down, but the math works the same if your triangles point left and right.


Other variants:

 3.1. Coordinates

PartDiagramNotes
Tile0,0,L,0,0,R,0,1,L,0,1,R,0,2,L,0,2,R,1,0,L,1,0,R,1,1,L,1,1,R,1,2,L,1,2,R,2,0,L,2,0,R,2,1,L,2,1,R,2,2,L,2,2,R1,1,L,1,1,R;To define triangle grid coordinates we can start with square grid coordinates, shear the squares, then split the rhombuses into two triangles. This means each square face coordinate needs to be two triangle face coordinates. I chose to label them L and R.
Vertex,,,,,,,,,,,,,,,,,1,1,L,1,1,R; 0,1,1,0,0,0,1,1,0,2,1,2,0,3,1,3,2,0,2,1,2,2,2,3,3,0,3,1,3,2,3,3Triangles are the "dual" of hexagons. Triangle tiles are similar to hexagon vertices; triangle vertices are similar to hexagon tiles. The extra triangle face does not create any additional vertices, so the vertex labeling is the same as the square grid labeling.
Edge,,,,,,,,,,,,,,,,,1,1,L,1,1,R; 0,0,E,0,0,N,0,0,W,0,1,N,1,0,W,0,1,E,0,1,W,0,2,N,1,1,W,0,2,E,0,2,W,0,3,N,1,2,W,1,0,E,1,0,N,1,1,N,2,0,W,1,1,E,1,2,N,2,1,W,1,2,E,1,3,N,2,2,W,2,0,E,2,0,N,2,1,N,3,0,W,2,1,E,2,2,N,3,1,W,2,2,E,2,3,N,3,2,WTriangle tiles are up or down facing, and that makes the edge assignment trickier. The edges are the same as those for squares (W and N), except we have one additional edge from the splitting of the face in two, and I've labeled that E.

To convert triangle vertices from grid coordinates to world coordinates, multiply by the axis vectors i and j:

  ⎛ x ⎞     ⎡ i.x j.x ⎤ ⎛ u ⎞
  ⎝ y ⎠  =  ⎣ i.y j.y ⎦ ⎝ v ⎠

Expanded out, that's

  x = i.x * u + j.x * v
  y = i.y * u + j.y * v

To convert triangle face coordinates to world coordinates involves an adjustment. For face (q, r, L/R) first calculate the world coordinates of the lower left vertex, (q, r). Then for an L face, add (1/2 * i, 1/3 * j) to the upper left vertex location. For an R face, add (i, 2/3 * j) to the upper left vertex location. The result will be the center of the face.

To convert from world coordinates to triangle vertices, first find the upper left corner of the rhombus (q, r) using algebra, or by inverting the i.x,j.x,i.y,j.y matrix. The rhombus contains two triangle faces. To determine which face the point is in, look at the edge that divides the two triangles inside each rhombus. If frac(q) + frac(r) < 1.0, the point is on the left of the line, and is therefore in the L face; otherwise it is in the R face.

When working with triangles, treat vertices as primary, and face centers as secondary. This is the opposite of how we treat hexagons.

Distance on a triangle grid is something I explore here[9]. I haven't worked much with triangle grids and don't know if this is the best way to approach it. This article from symbo1ics[10] has more math for triangle grids.

 3.2. Relationships

RelationshipDiagramFormula
Neighbors
L
q,r,Lq,r,Rq,r-1,Rq-1,r,Rq,r,L
q,r,R
q,r-1,R
q-1,r,R
Neighbors
R
q,r,Rq,r+1,Lq+1,r,Lq,r,Lq,r,R
q,r+1,L
q+1,r,L
q,r,L
Borders
L
q,r,Lq,r,Eq,r,Nq,r,Wq,r,L
q,r,E
q,r,N
q,r,W
Borders
R
q,r,Rq,r+1,Nq+1,r,Wq,r,Eq,r,R
q,r+1,N
q+1,r,W
q,r,E
Corners
L
q,r,Lq,r+1q+1,rq,rq,r,L
q,r+1
q+1,r
q,r
Corners
R
q,r,Rq+1,r+1q+1,rq,r+1q,r,R
q+1,r+1
q+1,r
q,r+1
Joins
E
q,r,Rq,r,Lq,r,Eq,r,E
q,r,R
q,r,L
Joins
N
q,r,Lq,r-1,Rq,r,Nq,r,N
q,r,L
q,r-1,R
Joins
W
q,r,Lq-1,r,Rq,r,Wq,r,W
q,r,L
q-1,r,R
Continues
E
q+1,r-1,Eq-1,r+1,Eq,r,Eq,r,E
q+1,r-1,E
q-1,r+1,E
Continues
N
q+1,r,Nq-1,r,Nq,r,Nq,r,N
q+1,r,N
q-1,r,N
Continues
W
q,r+1,Wq,r-1,Wq,r,Wq,r,W
q,r+1,W
q,r-1,W
Endpoints
E
q+1,rq,r+1q,r,Eq,r,E
q+1,r
q,r+1
Endpoints
N
q+1,rq,rq,r,Nq,r,N
q+1,r
q,r
Endpoints
W
q,r+1q,rq,r,Wq,r,W
q,r+1
q,r
Touches
q-1,r,Rq,r,Lq,r-1,Rq,r-1,Lq-1,r-1,Rq-1,r,Lq,rq,r
q-1,r,R
q,r,L
q,r-1,R
q,r-1,L
q-1,r-1,R
q-1,r,L
Protrudes
q,r,Wq,r,Nq,r-1,Eq,r-1,Wq-1,r,Nq-1,r,Eq,rq,r
q,r,W
q,r,N
q,r-1,E
q,r-1,W
q-1,r,N
q-1,r,E
Adjacent
q,r+1q+1,rq+1,r-1q,r-1q-1,rq-1,r+1q,rq,r
q,r+1
q+1,r
q+1,r-1
q,r-1
q-1,r
q-1,r+1

 4  More#

For implementation of the Tile, Edge, Vertex data structures, I usually use a struct with public fields, q and r being integers and s being a symbol (:L in Ruby, 'L in Lisp) or a character ('L' in C or C++ or Java or Rust) or a one-character string ('L' in Python). Each of the relationship algorithms is a function that takes a part as input and returns a list of parts as output. Parts that have s variants can be handled using switch or pattern matching. I made a JavaScript implementation to implement the diagrams on this page.

What else would you like to see me include in this document? Was anything confusing? Incomplete? Incorrect? Let me know.

There are some things I didn't find a place for, but might be of interest. Mathematicians have found five types of grids in 2D space[11]: squares, triangles, hexagons[12], rectangles, and parallelograms. However only squares, triangles, and hexagons are regular polygons. Spiral Honeycomb Mosaic[13] is an interesting way to assign numbers to hexagons in a hexagonal grid. It results in bizarre properties.

Email me , or tweet @redblobgames, or comment: