You are looking at historical revision 29361 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:

- Create a vector representing a hexagonal grid, and access and modify its members (cells), indexing them by column and row coordinates, possibly with wrap-around semantics in the horizontal and/or vertical direction.
- Find the cell adjacent to a given one in a chosen direction, or all of them.
- Convert grid <column>,<row> indices and world/screen coordinates, and vice versa. Determine within which hexagon is a point given in world/screen coordinates.
- Various other useful hexagon grid metrics, to facilitate drawing them on screen.
- Calculate 'hexagon distance' between two cells, possibly with wrap around semantics in the horizontal and/or vertical direction.

### Requirements

### Usage

The best usage example is probably visualize.scm in the tests (see the usage for _that_ in the doc at the top of the file itself):

https://github.com/euccastro/hexgrid/blob/master/tests/visualize.scm

#### Data representation

The grid is stored transparently as a flat vector, where the 0,0 cell is at the lowest left corner and width-1,height-1 is at the upper right. The grid represents a roughly rectangular region in world/screen space. For example, (make-grid-vector '(3 4)) would return a representation of the following grid:

0,3 1,3 2,3

0,2 1,2 2,2

0,1 1,1 2,1

(0,0) 1,0 2,0

Where indices may optionally wrap around horizontally or vertically, so coords -1,4 in the above grid would refer to the same cell as 2,0. Thus, the above grid also represents the following map (where an instance of the original grid has been highlighted):

...

... 1,1 2,1 0,1 1,1 2,1 0,1 1,1 ...

... 1,0 2,0 0,0 1,0 2,0 0,0 1,0 ... +-----------------+ ... 1,3 2,3 / 0,3 1,3 2,3 / 0,3 1,3 ... / / ... 1,2 2,2 | 0,2 1,2 2,2 | 0,2 1,2 ... \ \ ... 1,1 2,1 | 0,1 1,1 2,1 | 0,1 1,1 ... / / ... 1,0 2,0 /(0,0) 1,0 2,0 / 0,0 1,0 ... +-----------------+ ... 1,3 2,3 0,3 1,3 2,3 0,3 1,3 ...

... 1,2 2,2 0,2 1,2 2,2 0,2 1,2 ...

...

If this wrapping doesn't make sense for your application, just don't use the wrapper functions and check indices at the appropriate places with `((within-bounds? grid-size) cell)`.

**Warning:** if you want your grid to wrap around vertically, make sure it has an even height (number of rows).

We store grid cells in a flat vector, where the order is determined by cell coordinates, first x and then y, both ascending. Thus, the grid described above would be represented as

#(0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2)

Where `i,j` are the contents at cell in row `j` and column `i`. You can set these to whatever makes sense for your application. This module initializes them to `#f` and doesn't otherwise bother itself with them.

Functions normally take and return *lists of size two* to represent cell coordinates or points in world/screen space. This is done so they compose more seamlessly.

Functions that take data that will typically not change much during a program come *curried* like this: `((fn permanent args) varying args)`, to make it more convenient to avoid clutter and verbosity.

#### Tutorial

(use hexgrid) ; Width (columns). (definegrid-width 5) ; Height (rows). ; IMPORTANT: have an even number of rows if you want to wrap around vertically! (definegrid-height 6) ; For composability, the functions below take and return sequences of length 2 ; to represent horizontal and vertical components of two-dimensional values. (definesize (list grid-width grid-height)) ; Create a grid like this. (definev (make-grid-vector size)) ; v is a regular, flat vector. (assert (vector? v)) (assert (= (vector-length v) (* grid-width grid-height))) ; Convenience, checks bounds. (defineindex (indexer size)) (definecell '(2 3)) (vector-set! v (index cell) 'my-cell-data) (assert (eq? 'my-cell-data (vector-ref v (index cell)))) (defineout-of-bounds-cell '(-1 -1)) ; Would trigger an assertion failure. ; (index out-of-bounds-cell) ; Cells are initialized to #f by default. (definedifferent-cell '(1 1)) (assert (not (vector-ref v (index different-cell)))) ; Convenience: wraps around in horizontal direction. (definehwrap (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. (definevwrap (vertical-wrapper grid-height)) (assert (equal? (vwrap out-of-bounds-cell) (list -1 grid-height))) ; Wrappers compose with each other and with index. (definewrap (compose hwrap vwrap)) (definewrapindex (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. (defineinside? (within-bounds? gsize)) ; If we will always use wrapping logic, we might just as well... (define(wrap-direction direction) (compose wrap direction)) (defineeast-wrap (wrap-direction east)) (definenortheast-wrap (wrap-direction northeast)) ; ... (definewrapped-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)) (defineeast-checked (check-direction east)) (definenortheast-checked (check-direction northeast)) ; ... (definechecked-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. (definescreen-size '(800 600)) (definehex-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. (defineorigin (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. (definew->g (world->grid origin hex-radius)) (defineg->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! (definehv (hex-verts origin hex-radius)) (definecell-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

Wherever type `cell` is indicated, a list of two integers `(<column> <row>)` is expected or returned. Where `grid-size` is indicated, a list of two integers `(<columns> <rows>)` is expected or returned. Where type `origin` or `point` are indicated, a list of two numbers `(<x> <y>)` is expected or returned. Where `world-size` is indicated, a list of two numbers `(<width> <height>)` is expected or returned. Where type is `hex-radius`, a number is expected. In the case of `*-size` and `hex-radius`, positive numbers are expected or returned.

*[procedure]*

`(make-grid grid-size) => vector`

Return a vector representing an hexagonal grid of `grid-size` columns and rows.

*[procedure]*

`((indexer grid-size) cell) => integer`

Return the index corresponding to the given `cell` in the vector returned by `make-grid`. Bounds will be checked.

(Note: curried.)

*[procedure]*

`((horizontal-wrapper width) cell) => cell`

Return the position equivalent to `cell` with the horizontal coordinate wrapped at `width`.

(Note: curried.)

*[procedure]*

`((vertical-wrapper height) cell) => cell`

Return the position equivalent to `cell` with the vertical coordinate wrapped at `height`.

(Note: curried.)

*[procedure]*

`((within-bounds? grid-size) cell) => boolean`

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

(Note: curried.)

*[procedure]*

`(east cell) => cell`

*[procedure]*

`(northeast cell) => cell`

*[procedure]*

`(northwest cell) => cell`

*[procedure]*

`(west cell) => cell`

*[procedure]*

`(southwest cell) => cell`

*[procedure]*

`(southeast cell) => cell`

Return the cell adjacent to `cell` 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.

*[constant]*

`directions`

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) => point`

Return the world/screen coordinates of the center of `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]*

`((world->grid origin hex-radius) point) => cell`

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.)

*[constant]*

`normalized-hex-verts`

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) => (6 points)`

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) => integer`

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 in the respective position otherwise. For example `((distance '(5 #f)) '(1 2) '(3 4))` will wrap horizontally assuming the grid has width 5, and it will not wrap vertically at all. Bounds are not checked in any case. Use `within-bounds?` if you want that.

(Note: curried.)

*[procedure]*

`(distance-nowrap cell1 cell2) => integer`

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

*[procedure]*

`(grid-world-size grid-size hex-radius) => world-size`

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) => hex-radius`

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) => origin`

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.

*[constant]*

`row-height`

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.

*[constant]*

`inner-radius`

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.3
- first release where egg and tests actually install