You are looking at historical revision 29358 of this page. It may differ significantly from its current revision.

Hexgrid

Functions to work with hexagonal grids, like those used in old-school board wargames.

Description

Functionality is provided to:

Requirements

bindings

Usage

A fairly detailed tutorial:

(use hexgrid)

; Width (columns).
(define grid-width 5)

; Height (rows).
; IMPORTANT: have an even number of rows if you want to wrap around vertically!
(define grid-height 6)

; For composability, the functions below take and return sequences of length 2
; to represent horizontal and vertical components of two-dimensional values.
(define size (list grid-width grid-height))

; Create a grid like this.
(define v (make-grid-vector size))

; v is a regular, flat vector.
(assert (vector? v))
(assert (= (vector-length v) (* grid-width grid-height)))

; Convenience, checks bounds.
(define index (indexer size))
(define cell '(2 3))
(vector-set! v (index cell) 'my-cell-data)
(assert (eq? 'my-cell-data (vector-ref v (index cell))))

(define out-of-bounds-cell '(-1 -1))

; Would trigger an assertion failure.
; (index out-of-bounds-cell)

; Cells are initialized to #f by default.
(define different-cell '(1 1))
(assert (not (vector-ref v (index different-cell))))

; Convenience: wraps around in horizontal direction.
(define hwrap (horizontal-wrapper grid-width))
(assert (equal? (hwrap out-of-bounds-cell) (list grid-width -1)))

; The vertical wrapper checks that you have an even number of rows.  There is
; no good way to wrap around vertically otherwise.
(define vwrap (vertical-wrapper grid-height))
(assert (equal? (vwrap out-of-bounds-cell) (list -1 grid-height)))

; Wrappers compose with each other and with index.
(define wrap (compose hwrap vwrap))
(define wrapindex (compose index wrap))
(assert (eq? 'my-cell-data (vector-ref v (wrapindex (list (+ 2 gwidth) 3)))))
(assert (eq? 'my-cell-data (vector-ref v (wrapindex (list (- 2 gwidth) 3)))))

; Get neighboring cells.
(assert (equal? '(3 3) (east cell)))
(assert (equal? '(2 4) (northwest cell)))

; Get all adjacencies, from east counterclockwise.
(assert (equal? '((3 3) (3 4) (2 4) (1 3) (2 2) (1 2))
                (map (lambda (direction) (direction cell))
                     directions)))

; Direction functions don't wrap by default, nor do they check bounds.
(assert (equal? (southwest '(0 0)) '(-1 -1)))

; We can use the wrapping function that we built above.
(assert (equal? (wrap (southwest '(0 0)))
                (list (- gwidth 1) (- gheight 1))))

; Or we can check bounds ourselves with
(assert (not ((within-bounds? gsize) (southwest '(0 0)))))

; within-bounds? has that particular shape because we will most often
; specialize it to our grid size.
(define inside? (within-bounds? gsize))

; If we will always use wrapping logic, we might just as well...
(define (wrap-direction direction) (compose wrap direction))
(define east-wrap (wrap-direction east))
(define northeast-wrap (wrap-direction northeast))
; ...
(define wrapped-directions (map wrap-direction directions))

; Or, if we will always check.
(define ((check-direction direction) cell)
  (let ((other-cell (direction cell)))
    (assert ((within-bounds? gsize) other-cell))
    other-cell))
(define east-checked (check-direction east))
(define northeast-checked (check-direction northeast))
; ...
(define checked-directions (map check-direction directions))

; To convert between world/screen and grid coordinates we need to provide the
; following, in world/screen coordinates:
;
; - hexagon radius: the distance from the center of the hexagon to any of its
;   vertices, which is the same as the length of one hexagon side.
;
; There is a function that will calculate a radius to fit in a given screen/
; world rectangle, with some margin.
(define screen-size '(800 600))
(define hex-radius (radius-to-fit gsize screen-size 100))

; - origin: the position of the center of the 0,0 hexagon.
;
; There is a utility function to center the grid in its container.

(define origin (origin-to-center gsize hex-radius screen-size))

; Having those, we can now find the screen/world coordinates of the center of
; a given hexagon, and which hexagon contains a given point.

(assert (equal? cell ((world->grid origin radius)
                      ((grid->world origin radius) cell))))

; Notice the slightly peculiar syntax?  This is another case where typically
; you'll want to save a specialization of the procedures.

(define w->g (world->grid origin hex-radius))
(define g->w (grid->world origin hex-radius))

; So the above example looks less cluttered:

(assert (equal? cell (w->g (g->w cell))))

; Once you have the center and radius of your hexagons, you have all you need
; in order to display them.
;
; One option is to position and scale them using, for example, OpenGL or cairo
; transforms, and then just draw `normalized-hex-verts`:
;
;   (apply gl:Translatef (append (g->w cell) '(0)))
;   (gl:Scalef hex-radius hex-radius 0)
;   (gl:Begin gl:LINE_LOOP)
;   (for-each
;     (lambda (v)
;       (apply gl:Vertex2f v))
;     normalized-hex-verts)
;   (gl:End)
;
; Another option is to obtain the transformed coordinates (for example, to
; paint them directly or to build a vertex buffer with them).

; More chicken curry for ya!
(define hv (hex-verts origin hex-radius))

(define cell-verts (hv cell))

; cell-verts are in screen/world coordinates and can be plotted without
; further transformations.

; You can find out how far apart two hexes are, in hexes.
(assert (= (distance-nowrap '(0 1) '(1 1)) 1))

; Optionally, you can find distance by allowing wrapping around the
; horizontal and/or vertical borders.
(assert (= ((distance '(100 200)) '(0 0) '(99 199)) 1))


; And that's all.  For use cases not covered here you may get some ideas from
; the sources.
;
; Enjoy!

Interface

Where type `cell` or `grid-size` is indicated, a list of two integers is expected. Where type `origin`, `point` or `world-size` is indicated, a list of two numbers is expected. Where type is `radius`, a number is expected. In the case of `*-size` and `radius` arguments, positive numbers are expected.

[procedure] (make-grid grid-size)

Return a vector representing an hexagonal grid of the given size.

[procedure] ((indexer grid-size) cell)

Return the index corresponding to the given `cell`. Bounds will be checked.

(Note: curried.)

[procedure] ((horizontal-wrapper width) cell)

Return the given cell, with the horizontal coordinate wrapped at `width`.

(Note: curried.)

[procedure] ((vertical-wrapper height) cell)

Return the given cell, with the vertical coordinate wrapped at `height`.

(Note: curried.)

[procedure] ((within-bounds? grid-size) cell)

Return #t if `cell` is within the bounds expressed in `grid-size`, #f otherwise.

(Note: curried.)

[procedure] (east cell)
[procedure] (northeast cell)
[procedure] (northwest cell)
[procedure] (west cell)
[procedure] (southwest cell)
[procedure] (southeast cell)

Return the cell adjacent to the given one in the corresponding direction. Bounds are not checked not wrapped around; compose `horizontal-wrapper`, `vertical-wrapper` and/or `within-bounds?` with these, if you want wrapping and/or checking versions.

<data>directions</data>

A list with (east northeast northwest west southwest southeast), to make it convenient to collect the adjacencies of a cell.

[procedure] ((grid->world origin hex-radius) cell)

Return the world/screen coordinates of the center of the given `cell`.

`origin` is the position, in world/screen coordinates, of the cell at row 0, column 0. `hex-radius` is the distance, in world/screen coordinates, between the center of a hexagon and any of its vertices (which is the same as the length of one hexagon side).

No bounds wrap-around or checking is done. See `horizontal-wrapper`, `vertical-wrapper` or `within-bounds?` for that.

(Note: curried.)

[procedure] ((grid->world origin hex-radius) point)

Return the grid coordinates of the hexagon that contains the world/screen `point`.

`origin` is the position, in world/screen coordinates, of the cell at row 0, column 0. `hex-radius` is the distance, in world/screen coordinates, between the center of a hexagon and any of its vertices (which is the same as the length of one hexagon side).

No bounds wrap-around or checking is done. See `horizontal-wrapper`, `vertical-wrapper` or `within-bounds?` for that.

(Note: curried.)

<data>normalized-hex-verts</data>

A list containing the world/screen coordinates of six points corresponding to the vertices of a hexagon centered at 0,0 with radius 1.

[procedure] ((hex-verts origin hex-radius) cell)

A list containing the world/screen coordinates of six points corresponding to the vertices of a hexagon at `cell` with radius `hex-radius`.

`origin` is the position, in world/screen coordinates, of the cell at row 0, column 0. `hex-radius` is the distance, in world/screen coordinates, between the center of a hexagon and any of its vertices (which is the same as the length of one hexagon side).

No bounds wrap-around or checking is done. See `horizontal-wrapper`, `vertical-wrapper` or `within-bounds?` for that.

(Note: curried.)

[procedure] ((distance grid-size) cell1 cell2)

Return how many steps does it take to go from `cell1` to `cell2`, where a step means moving to an adjacent cell. Provide a valid width and/or height in `grid-size` if you want to allow wrapping around that direction, or #f otherwise. Bounds are not checked in any case. Use `within-bounds?` if you want that.

(Note: curried.)

[procedure] (distance-nowrap cell1 cell2)

Same as (distance '(#f #f)), that is, straight distance with no wrap around.

[procedure] (grid-world-size grid-size hex-radius)

Return the size, in screen/world units, of a grid of `grid-size` columns and rows if the distance from hexagon centers to their vertices (or, equivalently, the length of hexagon sides) is `hex-radius`.

[procedure] (radius-to-fit grid-size container-size margin)

Return the longest hexagon radius (or, equivalently, hexagon side length) such that a grid of `grid-size` columns and rows will fit in `container-size` world/screen units, with `margin` world/screen units left at both sides in the most constrained direction.

[procedure] (origin-to-center grid-size hex-radius container-size)

Return the position, in world/screen coordinates, for the center of the hexagon at column 0 and row 0, so a grid with `grid-size` columns and rows where each hexagon has `hex-radius` distance from center to vertices (or, equivalently, side length) will be centered in a container of `container-size` width and height in world/screen coordinates.

<data>row-height</data>

The vertical distance between centers of hexagons in successive rows, if the hexagon radius (that is, the distance between the hexagon center and any of its vertices) or, equivalently, the length of the hexagon sides, is 1.

<data>inner-radius</data>

The distance between the center of a hexagon and the midpoint of any of its sides. This is also the horizontal distance between the centers of adjacent hexagons in different rows, or half the distance between the centers of adjacent hexagons in the same row.

License

BSD

Author

Estevo U. C. Castro <euccastro@gmail.com>

History
0.1
initial release