Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

Hexgrid

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

Outdated egg!
Hexgrid
1. Description
2. Requirements
3. Usage
  1. Data representation
  2. Tutorial
4. Interface
5. License
6. Author
7. History

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.

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

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

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.

0.1.3: first release where egg and tests actually install

Outdated egg!

Hexgrid

Description

Requirements

Usage

Data representation

Tutorial

Interface

License

Author

History