Copyright | (c) Amy de Buitléir 2012-2015 |
---|---|

License | BSD-style |

Maintainer | amy@nualeargais.ie |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell98 |

A regular arrangement of tiles. Grids have a variety of uses, including games and self-organising maps. The userguide is available at https://github.com/mhwombat/grid/wiki.

In this package, tiles are called "triangular", "square", etc.,
based on the number of *neighbours* they have.
For example, a square tile has four neighbours, and a hexagonal
tile has six.
There are only three regular polygons that can tile a plane:
triangles, squares, and hexagons.
Of course, other plane tilings are possible if you use irregular
polygons, or curved shapes, or if you combine tiles of different
shapes.

When you tile other surfaces, things get very interesting.
Octagons will tile a *hyperbolic* plane.
(Alternatively, you can think of these as squares on a board game
where diagonal moves are allowed.)

For a board game, you probably want to choose the grid type based
on the number of *directions* a player can move, rather than the
number of sides the tile will have when you display it.
For example, for a game that uses square tiles and allows the user
to move diagonally as well as horizontally and vertically,
consider using one of the grids with *octagonal* tiles to model the
board.
You can still *display* the tiles as squares, but for internal
calculations they are octagons.

NOTE: Version 6.0 moved the various grid flavours to sub-modules.

NOTE: Version 4.0 uses associated (type) synonyms instead of multi-parameter type classes.

NOTE: Version 3.0 changed the order of parameters for many functions. This makes it easier for the user to write mapping and folding operations.

- class Grid g where
- type Index g
- type Direction g
- indices :: g -> [Index g]
- distance :: g -> Index g -> Index g -> Int
- minDistance :: g -> [Index g] -> Index g -> Int
- neighbours :: Eq (Index g) => g -> Index g -> [Index g]
- neighbour :: (Eq (Index g), Eq (Direction g)) => g -> Index g -> Direction g -> Maybe (Index g)
- contains :: Eq (Index g) => g -> Index g -> Bool
- tileCount :: g -> Int
- null :: g -> Bool
- nonNull :: g -> Bool
- edges :: Eq (Index g) => g -> [(Index g, Index g)]
- viewpoint :: g -> Index g -> [(Index g, Int)]
- isAdjacent :: g -> Index g -> Index g -> Bool
- adjacentTilesToward :: Eq (Index g) => g -> Index g -> Index g -> [Index g]
- minimalPaths :: Eq (Index g) => g -> Index g -> Index g -> [[Index g]]
- directionTo :: g -> Index g -> Index g -> [Direction g]

- class Grid g => FiniteGrid g where
- type Size g
- size :: g -> Size g
- maxPossibleDistance :: g -> Int

- class Grid g => BoundedGrid g where
- tileSideCount :: g -> Int
- boundary :: Eq (Index g) => g -> [Index g]
- isBoundary :: Eq (Index g) => g -> Index g -> Bool
- centre :: Eq (Index g) => g -> [Index g]
- isCentre :: Eq (Index g) => g -> Index g -> Bool
- defaultBoundary :: Eq (Index g) => g -> [Index g]
- defaultIsBoundary :: Eq (Index g) => g -> Index g -> Bool
- defaultCentre :: Eq (Index g) => g -> [Index g]
- defaultIsCentre :: Eq (Index g) => g -> Index g -> Bool

# Example

Create a grid.

ghci> let g = hexHexGrid 3 ghci> indices g [(-2,0),(-2,1),(-2,2),(-1,-1),(-1,0),(-1,1),(-1,2),(0,-2),(0,-1),(0,0),(0,1),(0,2),(1,-2),(1,-1),(1,0),(1,1),(2,-2),(2,-1),(2,0)]

Find out if the specified index is contained within the grid.

ghci> g `contains` (0,-2) True ghci> g `contains` (99,99) False

Find out the minimum number of moves to go from one tile in a grid to another tile, moving between adjacent tiles at each step.

ghci> distance g (0,-2) (0,2) 4

Find out the minimum number of moves to go from one tile in a grid to any other tile, moving between adjacent tiles at each step.

ghci> viewpoint g (1,-2) [((-2,0),3),((-2,1),3),((-2,2),4),((-1,-1),2),((-1,0),2),((-1,1),3),((-1,2),4),((0,-2),1),((0,-1),1),((0,0),2),((0,1),3),((0,2),4),((1,-2),0),((1,-1),1),((1,0),2),((1,1),3),((2,-2),1),((2,-1),2),((2,0),3)]

Find out which tiles are adjacent to a particular tile.

ghci> neighbours g (-1,1) [(-2,1),(-2,2),(-1,2),(0,1),(0,0),(-1,0)]

Find how many tiles are adjacent to a particular tile. (Note that the result is consistent with the result from the previous step.)

ghci> numNeighbours g (-1,1) 6

Find out if an index is valid for the grid.

ghci> g `contains` (0,0) True ghci> g `contains` (0,12) False

Find out the physical dimensions of the grid.

ghci> size g 3

Get the list of boundary tiles for a grid.

ghci> boundary g [(-2,2),(-1,2),(0,2),(1,1),(2,0),(2,-1),(2,-2),(1,-2),(0,-2),(-1,-1),(-2,0),(-2,1)]

Find out the number of tiles in the grid.

ghci> tileCount g 19

Check if a grid is null (contains no tiles).

ghci> null g False ghci> nonNull g True

Find the central tile(s) (the tile(s) furthest from the boundary).

ghci> centre g [(0,0)]

Find all of the minimal paths between two points.

ghci> let g = hexHexGrid 3 ghci> minimalPaths g (0,0) (2,-1) [[(0,0),(1,0),(2,-1)],[(0,0),(1,-1),(2,-1)]]

Find all of the pairs of tiles that are adjacent.

ghci> edges g [((-2,0),(-2,1)),((-2,0),(-1,0)),((-2,0),(-1,-1)),((-2,1),(-2,2)),((-2,1),(-1,1)),((-2,1),(-1,0)),((-2,2),(-1,2)),((-2,2),(-1,1)),((-1,-1),(-1,0)),((-1,-1),(0,-1)),((-1,-1),(0,-2)),((-1,0),(-1,1)),((-1,0),(0,0)),((-1,0),(0,-1)),((-1,1),(-1,2)),((-1,1),(0,1)),((-1,1),(0,0)),((-1,2),(0,2)),((-1,2),(0,1)),((0,-2),(0,-1)),((0,-2),(1,-2)),((0,-1),(0,0)),((0,-1),(1,-1)),((0,-1),(1,-2)),((0,0),(0,1)),((0,0),(1,0)),((0,0),(1,-1)),((0,1),(0,2)),((0,1),(1,1)),((0,1),(1,0)),((0,2),(1,1)),((1,-2),(1,-1)),((1,-2),(2,-2)),((1,-1),(1,0)),((1,-1),(2,-1)),((1,-1),(2,-2)),((1,0),(1,1)),((1,0),(2,0)),((1,0),(2,-1)),((1,1),(2,0)),((2,-2),(2,-1)),((2,-1),(2,0))]

Find out if two tiles are adjacent.

ghci> isAdjacent g (-2,0) (-2,1) True ghci> isAdjacent g (-2,0) (0,1) False

# Grids

A regular arrangement of tiles.
Minimal complete definition:

, `Index`

, `Direction`

,
`indices`

, `distance`

.`directionTo`

indices :: g -> [Index g] Source

Returns the indices of all tiles in a grid.

distance :: g -> Index g -> Index g -> Int Source

returns the minimum number of moves required
to get from the tile at index `distance`

g a b`a`

to the tile at index `b`

in
grid `g`

, moving between adjacent tiles at each step. (Two tiles
are adjacent if they share an edge.) If `a`

or `b`

are not
contained within `g`

, the result is undefined.

minDistance :: g -> [Index g] -> Index g -> Int Source

returns the minimum number of moves
required to get from any of the tiles at indices `minDistance`

g bs a`bs`

to the tile
at index `a`

in grid `g`

, moving between adjacent tiles at each
step. (Two tiles are adjacent if they share an edge.) If `a`

or
any of `bs`

are not contained within `g`

, the result is
undefined.

neighbours :: Eq (Index g) => g -> Index g -> [Index g] Source

returns the indices of the tiles in the grid
`neighbours`

g a`g`

which are adjacent to the tile with index `a`

.

neighbour :: (Eq (Index g), Eq (Direction g)) => g -> Index g -> Direction g -> Maybe (Index g) Source

returns the indices of the tile in the grid
`neighbour`

g d a`g`

which is adjacent to the tile with index `a`

, in the
direction `d`

.

contains :: Eq (Index g) => g -> Index g -> Bool Source

`g ``

returns `contains'`

a`True`

if the index `a`

is contained
within the grid `g`

, otherwise it returns false.

Returns the number of tiles in a grid. Compare with

.`size`

Returns `True`

if the number of tiles in a grid is zero, `False`

otherwise.

Returns `False`

if the number of tiles in a grid is zero, `True`

otherwise.

edges :: Eq (Index g) => g -> [(Index g, Index g)] Source

A list of all edges in a grid, where the edges are represented by a pair of indices of adjacent tiles.

viewpoint :: g -> Index g -> [(Index g, Int)] Source

returns a list of pairs associating the index
of each tile in `viewpoint`

g a`g`

with its distance to the tile with index `a`

.
If `a`

is not contained within `g`

, the result is undefined.

isAdjacent :: g -> Index g -> Index g -> Bool Source

returns `isAdjacent`

g a b`True`

if the tile at index `a`

is
adjacent to the tile at index `b`

in `g`

. (Two tiles are adjacent
if they share an edge.) If `a`

or `b`

are not contained within
`g`

, the result is undefined.

adjacentTilesToward :: Eq (Index g) => g -> Index g -> Index g -> [Index g] Source

returns the indices of all tiles
which are neighbours of the tile at index `adjacentTilesToward`

g a b`a`

, and which are
closer to the tile at `b`

than `a`

is. In other words, it returns
the possible next steps on a minimal path from `a`

to `b`

. If `a`

or `b`

are not contained within `g`

, or if there is no path from
`a`

to `b`

(e.g., a disconnected grid), the result is undefined.

minimalPaths :: Eq (Index g) => g -> Index g -> Index g -> [[Index g]] Source

returns a list of all minimal paths from
the tile at index `minimalPaths`

g a b`a`

to the tile at index `b`

in grid `g`

. A
path is a sequence of tiles where each tile in the sequence is
adjacent to the previous one. (Two tiles are adjacent if they
share an edge.) If `a`

or `b`

are not contained within `g`

, the
result is undefined.

Tip: The default implementation of this function calls

. If you want to use a custom algorithm,
consider modifying `adjacentTilesToward`

instead of
`adjacentTilesToward`

.`minimalPaths`

directionTo :: g -> Index g -> Index g -> [Direction g] Source

returns the direction(s) of the next
tile(s) in a `directionTo`

g a b*minimal* path from the tile at index `a`

to the
tile at index `b`

in grid `g`

.

# Finite grids

class Grid g => FiniteGrid g where Source

A regular arrangement of tiles where the number of tiles is finite.
Minimal complete definition:

, `size`

.`maxPossibleDistance`

Returns the dimensions of the grid.
For example, if `g`

is a 4x3 rectangular grid,

would
return `size`

g`(4, 3)`

, while

would return `tileCount`

g`12`

.

maxPossibleDistance :: g -> Int Source

Returns the largest possible distance between two tiles in the grid.

# Bounded grids

class Grid g => BoundedGrid g where Source

A regular arrangement of tiles with an edge.
Minimal complete definition:

.`tileSideCount`

tileSideCount :: g -> Int Source

Returns the number of sides a tile has

boundary :: Eq (Index g) => g -> [Index g] Source

Returns a the indices of all the tiles at the boundary of a grid.

isBoundary :: Eq (Index g) => g -> Index g -> Bool Source

' returns `isBoundary`

g a`True`

if the tile with index `a`

is
on a boundary of `g`

, `False`

otherwise. (Corner tiles are also
boundary tiles.)

centre :: Eq (Index g) => g -> [Index g] Source

Returns the index of the tile(s) that require the maximum number of moves to reach the nearest boundary tile. A grid may have more than one central tile (e.g., a rectangular grid with an even number of rows and columns will have four central tiles).

isCentre :: Eq (Index g) => g -> Index g -> Bool Source

' returns `isCentre`

g a`True`

if the tile with index `a`

is
a centre tile of `g`

, `False`

otherwise.

defaultBoundary :: Eq (Index g) => g -> [Index g] Source

defaultIsBoundary :: Eq (Index g) => g -> Index g -> Bool Source

defaultCentre :: Eq (Index g) => g -> [Index g] Source

defaultIsCentre :: Eq (Index g) => g -> Index g -> Bool Source