Honeycomb

⚠️ This is an experimental version and the API ~~is likely to~~ may change. I encourage anyone to try it out and open an issues if you have any suggestions or questions ⚠️

A hexagon grid library made in ~~JavaScript~~TypeScript, heavily inspired by Red Blob Games' blog posts and code samples.

Honeycomb works in modern browsers and Node (>=16). It's recommended to use Honeycomb with TypeScript, but not required.

Installation

NPM:

npm i honeycomb-grid@alpha

Yarn:

yarn add honeycomb-grid@alpha

Or download the distribution from unpkg.com.

Basic example

Create a rectangular grid of 10 by 10 hexes and log each hex:

import { createHexPrototype, Grid, rectangle } from 'honeycomb-grid'

// 1. Create a hex prototype. All hexes will have this object as their prototype:
const hexPrototype = createHexPrototype({ dimensions: 30 })

// 2. Create a grid by passing the prototype and a "traverser" for a rectangular-shaped grid:
const grid = new Grid(hexPrototype, rectangle({ width: 10, height: 10 }))

// 3. Iterate over the grid to log each hex:
grid.forEach(console.log)

Rendering

Honeycomb comes without the ability to render hexes to screen. Fortunately, it isn't very hard. Especially if you use a dedicated rendering library.

Using SVG.js:

import { SVG } from '@svgdotjs/svg.js'
import { Hex } from 'honeycomb-grid'

const draw = SVG().addTo('body').size('100%', '100%')

function renderSVG(hex: Hex) {
  const polygon = draw
    // create a polygon from a hex's corner points
    .polygon(hex.corners.map(({ x, y }) => `${x},${y}`))
    .fill('none')
    .stroke({ width: 1, color: '#999' })

  return draw.group().add(polygon)
}

Using PixiJS:

import * as PIXI from 'pixi.js';
import { Hex } from 'honeycomb-grid'

const app = new PIXI.Application({ backgroundAlpha: 0 })
const graphics = new PIXI.Graphics()

document.body.appendChild(app.view)
graphics.lineStyle(1, 0x999999)

function renderCanvas(hex: Hex) {
  const [firstCorner, ...otherCorners] = hex.corners

  // move the "pen" to the first corner
  graphics.moveTo(firstCorner.x, firstCorner.y)
  // draw lines to the other corners
  otherCorners.forEach(({ x, y }) => graphics.lineTo(x, y))
  // finish at the first corner
  graphics.lineTo(firstCorner.x, firstCorner.y)

  app.stage.addChild(graphics)
}

Either render() function can be used like so:

import { createHexPrototype, Grid, rectangle } from 'honeycomb-grid'

// You may want the origin to be the top left corner of a hex's bounding box instead of its center (which is the default)
const hexPrototype = createHexPrototype({ dimensions: 30, origin: 'topLeft' })

new Grid(hexPrototype, rectangle({ width: 10, height: 10 }))
  .forEach(renderSVG) // or: .forEach(renderCanvas)

Coordinate system

There are four types of coordinates:

1. Offset coordinates, e.g.: { col: 1, row: 2 }
2. Axial coordinates, e.g.: { q: 1, r: 2 }
3. Cube coordinates, e.g.: { q: 1, r: 2, s: -3 } (the sum of all three coordinates must always be 0)
4. Tuple coordinates, e.g.: [1, 2] or [1, 2, -3] which is an array of length 2 (axial coordinates) or 3 (cube coordinates)

Most functions/methods that accept coordinates accept HexCoordinates, which is a union type of these four coordinate types.

You may also find points (e.g.: { x: 1, r: 2 }) in the library. For example, a hex's corners property returns an array of the hex's six corner points.

There are some functions for converting between types of coordinates:

import { assertCubeCoordinates, hexToOffset, hexToPoint, offsetToCube, pointToCube, tupleToCube } from 'honeycomb-grid'

offsetToCube(HexPrototype, OffsetCoordinates): CubeCoordinates
pointToCube(HexPrototype, Point): CubeCoordinates
tupleToCube(TupleCoordinates): CubeCoordinates

hexToOffset(Hex): OffsetCoordinates
hexToPoint(Hex): Point

// HexCoordinates could be any of the four types, use this to convert them to CubeCoordinates
assertCubeCoordinates(HexPrototype, HexCoordinates): CubeCoordinates

Odd or even hex offsets

In a grid with pointy hexes, each row is offsetted half a hex relative to the previous row. In grids with flat hexes, this applies to the columns. Redblobgames.com has a visual example.

Set the offset property to 1 or -1 (default) to control whether the even or odd rows/columns are offsetted.

Pixel → Hex

Translating a screen pixel to the corresponding hex in a grid is possible with Grid.pointToHex(). It also works with irregularly shaped hexes.

import { createHexPrototype, Grid, rectangle } from 'honeycomb-grid'

const hexPrototype = createHexPrototype({
  dimensions: { xRadius: 50, yRadius: 30 }, // wide hexes
  origin: 'topLeft'
})
const grid = new Grid(hexPrototype, rectangle({ start: [0, 0], width: 10, height: 10 }))

document.addEventListener('click', ({ offsetX, offsetY }) => {
  const hex = grid.pointToHex({ x: offsetX, y: offsetY })
  console.log(hex)
})

Traversing

In Honeycomb it's possible to traverse a grid: iterating over hexes in a specific order. You can then use other iterating methods like each(), filter() and takeWhile() to do whatever you want with those hexes.

Built-in traversers include: rectangle(), ring(), spiral(), add() and line().

// A traverser can be passed as the 2nd argument to the Grid constructor:
const grid = new Grid(hexPrototype, rectangle({ start: [0, 0], width: 4, height: 4 }))

// or to the traverse() method:
grid.traverse(spiral({ start: [5, 5], radius: 3 }))

Traversers can be chained by wrapping them in an array. Each consecutive traverser receives the last traversed hex (cursor) of the previous traverser.

// This traverses over a grid following a triangular path:
grid
  .traverse([
    // Start at the hex with coordinates { q: 0, r: 0 } and move 4 hexes East
    line({ start: [0, 0], direction: Compass.E, length: 4 }),
    // then move 4 hexes Southwest
    line({ direction: Compass.SW, length: 4 }),
    // finally move 3 hexes Northwest to close the triangle
    line({ direction: Compass.NW, length: 3 }),
  ])
  .each((hex) => console.log(hex))
  .run() // logs: Hex {q: 0, r: 0}, Hex {q: 1, r: 0}, Hex {q: 2, r: 0}, …

In order to prevent the same hexes are traversed multiple times, traversers never traverse the cursor they receive from the previous traverser. This means that when you call a traverser, the first hex will be missing (by default):

// This produces a 10x10 grid with the hex in the top left corner missing ⚠️
// (so actually a 9x10 grid)
const grid = new Grid(hexPrototype, rectangle({ width: 10, height: 10 }))

This can be fixed by passing the start option that should be the hex coordinates the traverser should…well, start:

// This produces a 10x10 grid as you might expect 😌
const grid = new Grid(hexPrototype, rectangle({ start: [0, 0], width: 10, height: 10 }))

Most traversers accept this start option as well as an at option. at behaves the same as start but doesn't include the hex at those coordinates. It should be used to make a traverser start at coordinates that aren't the cursor's.

TL;DR In most cases: only use start when creating a grid or for the first traverser in an array of traversers.

Finally, you can also supply a custom traverser. It's called with:

1. cursor: the hex where the previous traverser left off
2. getHex: a function that either returns a hex from the grid's store (if present) or creates a new hex

It must return an iterable (usually an array) of hexes:

grid.traverse((cursor, getHex) => [getHex(cursor)]) // (this traverser isn't very useful 😬)

// Because a traverser must return an iterable of hexes, generators can be traversers too:
grid.traverse(function*(cursor, getHex) {
  yield getHex([0, 0])
  yield getHex([1, 0])
  yield getHex([0, 1])
})

Stateful and stateless grids

import { Grid, rectangle } from 'honeycomb-grid'

// When a grid is created with a traverser…
const statefulGrid = new Grid(hexPrototype, rectangle({ width: 2, height: 2 }))
// …all hexes produced by the traverser are added to a store (a JS Map):
statefulGrid.store  // Map(4) {"0,0" => Hex, "1,0" => Hex, "0,1" => Hex, "1,1" => Hex}
// A grid with a store is a stateful grid and it can be iterated:
statefulGrid
  .filter((hex) => hex.q === 1)
  .each((hex) => console.log(hex))
  .run()  // logs: Hex {q: 1, r: 0}, Hex {q: 1, r: 1}

// If you don't need state and/or want a performance gain, create a stateless grid:
const statelessGrid = new Grid(hexPrototype) // don't pass a 2nd argument
statelessGrid.store // Map(0) {}
// This grid can't be iterated (what hexes and in what order?)
statelessGrid.each((hex) => console.log(hex)).run() // logs nothing
// However, stateless grids can always be traversed:
statelessGrid
  .traverse(add([1, 1])) // traverse a single hex
  .each((hex) => console.log(hex))
  .run()  // logs: Hex {q: 1, r: 1}

// To update a grid's store (add/remove/change hexes), you could do this manually:
const hexToAdd = statefulGrid.getHex([2, 2])
statefulGrid.store.set(hexToAdd.toString(), hexToAdd)
// But this mutates the grid (possibly introducing bugs). Use update() instead:
const anotherHex = statefulGrid.getHex([3, 3])
const updatedGrid = statefulGrid.update((grid) => {
  // grid is a clone of the source grid (statefulGrid), so you can mutate it in-place
  grid.store.set(anotherHex.toString(), anotherHex)
  // you don't have to return the grid
})
statefulGrid.store.get(anotherHex.toString()) // undefined
updatedGrid.store.get(anotherHex.toString()) // Hex {q: 3, r: 3}

Controlling how hexes are created

Whenever Honeycomb creates or clones a hex, the clone() method on the hex prototype is called. So by implementing your own version you can control how hexes are created:

import { cloneHex, createHexPrototype, Grid } from 'honeycomb-grid'

const hexPrototype = createHexPrototype({
  // `newProps` can be undefined(!), coordinates (offset, axial or cube) or a hex
  clone(newProps) {
    // you can run side-effects here for example
    console.log('Hi there 👋')
    // `this` is set to the hex that's being cloned
    return cloneHex(this, newProps)
  }
})
const grid = new Grid(hexPrototype)

// the following creates a new hex and then calls its clone() method
const hex = grid.getHex([1, 2]) // logs: Hi there 👋

If you want to update hexes in a grid, use Grid's map() method:

import { add, createHexPrototype, Grid } from 'honeycomb-grid'

const hexPrototype = createHexPrototype(/* ... */)
const grid = new Grid(hexPrototype, add([1, 2])) // create a grid with a single hex
const mappedGrid = grid
  .map((hex) => {
    // hex is already cloned, so you can mutate it in-place
    hex.custom = 'custom'
    // you don't even have to return the hex (the cloned hex is used)
  })
  .run()

// the hex in the original grid is unaffected:
grid.getHex([1, 2])       // Hex {q: 1, r: 2}
mappedGrid.getHex([1, 2]) // Hex {q: 1, r: 2, custom: 'custom'}

Playground

The project contains a playground to play around with Honeycomb on your machine. I use this myself to test out new functionality. To use it follow these steps:

1. git clone [email protected]:flauwekeul/honeycomb.git
2. git switch next
3. npm run dev (this starts a server that automatically rebuilds the project to /dist when anything in /src changes)
4. npm run playground (this starts a parcel server running at http://localhost:1234 with /playground/index.html as its entrypoint)
5. Play around with the files in /playground (mainly /playground/index.ts)

The playground contains render.ts to render individual hexes as SVGs and benchmark.ts for running comparative performance tests.

Documentation

I'm planning on writing documentation once the API is (more or less) stable.

4.0 Backlog

Features that are crossed out are not going to be added. Checked features are implemented (or not applicable). The rest will probably be implemented.

General

• [ ] Add a helper to manage grid state better (and remove the "need" to override a global variable to keep track of the grid state). It's probably better to remove the store for now, leave that to the user. Something like this: ```typescript // this helper is supplied by Honeycomb: const getGrid = (initialGrid: Grid) => { let grid = initialGrid || new Grid(); // action must have this signature: (grid: Grid) => Grid return (...actions) => actions.reduce((grid, action) => action(grid), grid) }

  const updateGrid = getGrid()
  
  document.querySelector('#grid').addEventListener('click', (event) => {
    const updatedGrid = updateGrid(
      traverse(/* traversers */),
      filter(/* some filter */),
      map(/* some mapper */),
    )
    // the updated grid can then be used:
    doSomething(updatedGrid)
  });
  ```

• [ ] Rename each() to peak() or tap(), because each suggests that it returns nothing.

• [ ] Replace compass class with util functions:

  • [ ] vector(): accepts start coordinates, a direction and length and returns coordinates (length can also be a function?)
  • [ ] turn(): accepts start coordinates, a direction and an amount to turn (in degrees or "compass steps"?)
  • [ ] functions to convert between degrees and compass directions

• [ ] Functions/methods should also accept strings for compass directions.

• [ ] Directions should also be given in degrees (in steps of 30°)?

• [x] ~~Do something with this: https://www.redblobgames.com/grids/hexagons/#map-storage?~~ A Map works fine

• [x] There should be a way to loop over hexes in a grid with transducers? Experimented with this and I couldn't get it to work when a grid was traversed multiple times before being run (triggering the transducer). Surprisingly, it had a significant performance drop (more than 50%). Don't know what caused it though, probably the combination of transducers and traversers that don't fit well together. Might investigate more in the future.

• [ ] Add an abstraction for the grid store (currently a plain Map). So that instead of doing this: grid.store.set(someHex.toString(), someHex), one can do this: grid.store.set(someHex). Or maybe even separate methods for adding hexes (that throws when the hex is already present), updating hexes (that throws when the hex isn't present) and setting hexes (that doesn't throw when the hex is already present).

• [ ] Add functionality related to edges

• [x] ~~Do something with matrices?~~ Nah, no need

• [x] ~~Add some generic rendering helpers (a "pen" that "draws" hex edges (for canvas) or a single hex (for SVG))~~ No need: one only needs to map a hex's corners to render a hex. Nearly all code is specific to the render lib.

• [ ] Make sure the lib can be imported as a module (e.g.: <script type="module" src="https://unpkg.com/honeycomb-grid/dist/honeycomb.mjs"></script>). Probably use microbundle or snowpack.

• [ ] Switch to np for publishing releases

Functions and methods

These methods exist in v3 and they need to be considered for v4.

• [ ] hex functions (apply to a single hex):
  • [ ] ? add
  • [x] ~~cartesian~~ replaced with row and col props
  • [x] ~~cartesianToCube (alias: toCube)~~ replaced with offsetToAxial()
  • [x] center
  • [x] ~~coordinates (returns cube by default?)~~ considered obsolete
  • [x] corners
  • [x] ~~cube~~ considered obsolete
  • [x] ~~cubeToCartesian (alias: toCartesian)~~ replaced with hexToOffset()
  • [x] equals
  • [x] fromPoint: pointToCube()
  • [x] height
  • [x] isFlat
  • [x] isPointy
  • [x] lerp (not public)
  • [x] nudge (not public)
  • [x] round
  • [ ] ? set
  • [ ] ? subtract
  • [ ] thirdCoordinate
  • [x] toString
  • [x] width
• [ ] grid functions (these should apply to multiple hexes):
  • [x] distance
  • [x] hexToPoint
  • [x] pointToHex
  • [x] get
  • [x] hexesBetween: see line() traverser
  • [ ] hexesInRange:
    • [x] ring() traverser (always 1 hex thick)
    • [x] spiral() traverser (uses ring() internally and offers an API to skip to the next ring)?
    • [ ] rays() traverser (produces hexes in straight lines from the start hex)
  • [x] line: line() traverser ~~(aliased to move())~~
  • [x] ~~neighborsOf~~ replaced with neighborOf() (singular)
  • [ ] pointHeight
  • [ ] pointWidth
  • [ ] ? set
  • [ ] parallelogram
  • [ ] triangle
  • [ ] hexagon
  • [x] rectangle
  • [x] ring
  • [x] spiral

Grid

Terminology

• grid instance: an iterable object that represents hexes in a plane (possibly with infinite dimensions). ~~The order of iteration is not important?~~

• stateful grid: a grid with a non-empty store. The store can be filled when the grid is created by either passing a store or a traverser as the 2nd argument.

• stateless grid: a grid with an empty store. Create a stateless grid by only passing a hex prototype to the constructor.

• concrete grid: a grid instance with finite hexes stored as a concrete data type (array, object, string, etc)

• grid-like: an iterable that can be converted to a grid instance

• traverser: a ~~generator~~ (generators are not performant, so the built-in traversers are regular array-producing functions, but a traverser can still be a generator) function that determines how a grid instance is traversed. It produces hexes in a certain order.

  The result of a traversal is always a new grid (the traversed grid isn't mutated, the hexes in it can be mutated though), this can be added/subtracted/intersected/differenced, mapped/reduced or just ignored (in case of side-effects).

• iterator method: a grid method that iterates over the hexes in the grid (if any). A traverser is also an iterator. Stateful grids can always be iterated (using the store), stateless grids can only be iterated when traversed at least once.

API

• [x] Creation:
  • [x] new Grid<T extends Hex>(hexPrototype: T, traverserOrStore?: Traverser<T> | Map<string, T>): ~~can be traversed indefinitely, determine default traverser (spiral?) the default traverser doesn't emit hexes~~ A grid without hexes isn't very helpful, so it makes sense to pass a traverser or store (Map) to the constructor.
  • [x] ~~Grid.of<T extends Hex>(/* same args as constructor */)~~
  • [x] Grid.from<T extends Hex>(iterable: Iterable<T>)
• [ ] Traversal:
  • [x] grid.rectangle(options)
  • [x] ~~grid.hexagon(options)~~ see: the spiral() traverser
  • [x] ~~grid.parallelogram(options)~~ add if requested
  • [x] ~~grid.triangle(options)~~ add if requested
  • [x] grid.spiral(options) (grid.ring(options) would be a spiral that stops)
  • [x] ~~grid.line(options)~~ see the line() traverser
  • [x] ~~grid.zigzag(options)?~~ add if requested
  • [ ] something that uses path finding algorithms like A*?
  • [x] ~~grid.createTraverser(function* customTraverser(options) {})(options)~~
  • [x] 👉 Make traversers even more fine-grained (~~seems very complex~~ it is, but worth it!)
• [ ] Combination:
  • [ ] grid.add(otherGrid) / grid.union(otherGrid)
  • [ ] grid.subtract(otherGrid)
  • [ ] grid.intersect(otherGrid)
  • [ ] grid.difference(otherGrid)
  • [x] ~~grid.mergeMap() / grid.zip()~~ these ~~seem~~ are useless
• [ ] Assertion:
  • [ ] ? grid.some() whether any hex passes predicate
  • [ ] ? grid.every() whether all hexes pass predicate
• [ ] Mutation/reduction:
  • [x] grid.update((grid) => void)

    // the passed grid is already a clone, similar to Immer
    grid.update((grid) => {
      // grid.hexes() returns the hexes since the last run() call
      grid.store = new Map(grid.hexes().map((hex) => [hex.toString(), hex]))
    })

  • [ ] grid.reduce<R>((R, hex, grid) => R, R): R
  • [x] ~~grid.toArray(): T[]~~ see grid's hexes() method
  • [x] ~~grid.toJSON()~~
  • [x] ~~grid.toString() / grid.serialize()~~
  • [x] ~~grid.toLinkedList()~~
  • [x] ~~grid.toRecord()~~
  • [x] ~~grid.toMap()~~ (just use grid.store)
  • [x] ~~grid.toSet()~~

Coordinates

• [x] Also accept tuples (e.g. [1, 2]). These correspond to ~~offset~~ axial coordinates (e.g. { q: 1, r: 2 }).
• [ ] Also accept strings? These strings should be the same as what hex.toString() produces (by default separated by a comma 1,2). But if user overrides toString() (and using a different separator, e.g. a pipe: 1|2), then user is responsible for using the correct separator when they use strings as coordinates.
• [x] Store coordinates as ~~"tuples" (arrays)~~ simple 3D objects. ~~Investigate whether arrays or objects (without prototype?) (maybe even strings, ArrayBuffer?) are more performant.~~
• [x] Take Amit's advice and use axial coordinates by default.
  • [x] ~~Use x, y and z for cube coordinates?~~
  • [x] ~~Rename cartesian to offset?~~
  • [ ] Also use doubled coordinates?
• [x] Problem: how to differentiate between 2D hex coordinate and 2D "pixel" coordinate? Solution: CartesianCoordinates is an alias of Point. A "coordinate" is a point in a grid, a "point" is any 2D/3D point in any system (e.g. a grid).
• [x] ~~Offer Point() function (with add() etc methods)? And/or a way to convert tuples to points/coordinates?~~ Converting from/to tuples is outside this lib's scope.

✅ Hex

• [x] Hexes only have axial coordinates (most methods require axial coordinates anyway).
• [x] Make default origin the center of the hex (currently is top left corner)? Can't remember why it's not already the center.
  • [ ] Add boundingBox (with topLeft, topRight, etc)
  • [x] Origin should also be able to set with a function that's called with the hex prototype (?) so that width, height or corners can be used to determine origin
• [x] ~~Make it possible to use own createHex() functions (this also means hex prototypes aren't set by Honeycomb)?~~ Every time a new hex is created (in Grid for example), the clone() method is called. This way users can control how hexes are created.
• [ ] Different groups of functions:
  1. Functions that require both a hex prototype and a hex (e.g. toPoint())
  2. Functions that require a hex prototype and optionally a hex (e.g. corners() with just a hex prototype returns the relative corners of any hex, corners() with both a hex prototype and a hex returns the absolute corners of the hex)
  3. Functions that require only a hex prototype (e.g. width())
  4. Functions that require only a hex (e.g. equals())
  • [x] What to do when group 1 is only called with a hex prototype? ~~Return a function that accepts a hex.~~ Todo: Log a warning
  • [x] (Naming) conventions for these groups?
    • group 1: ~~offer higher order function that accepts a hex prototype (prefixed with create, e.g. createToPoint()?) and returns a function that accepts a hex. This can be used to create hex prototype methods using partial application (i.e. hex.toPoint()).~~ When used as a static method: name start with hex (e.g. hexToPoint()) and accepts a hex. When used as a prototype method: accepts no arguments (works on instance).
    • group 2: 1st parameter is the hex prototype, 2nd optional parameter the hex. The return value depends on whether the 2nd parameter was passed. This can also be used as a static method on Hex or a prototype method (then the function is partially applied with the hex prototype).
    • group 3: are both available as a static and prototype method.
    • group 4: available as a static method and a partially applied prototype method.
• [x] By default hexes only have coordinates as state. Should be possible for users to add state:

  interface CustomHex {
    customProp: string
    customMethod(): void
  }
  // the properties of CustomHex are available to all hexes (because they're added to the prototype)
  const hexPrototype = createHexPrototype<CustomHex>({ size: 20, customProp: 'custom', customMethod() {} })

  • [x] how can you type functions that accept hexes? RxJS operators seem to be able to fix this.
• [x] ~~Maybe either have pointy or flat hexes and leave it to rendering if they're pointy or flat?~~ All the if statements that check whether hexes are pointy or flat may be resolved by having separate functions for pointy and flat hexes and using those in the Hex prototype. This doesn't seem to improve performance.
• [x] ~~Investigate if memoization helps~~ It doesn't