Portability	portable
Stability	experimental
Maintainer	amy@nualeargais.ie
Safe Haskell	Safe-Inferred

Math.Geometry.Grid

Contents

The Grid class
Grids with triangular tiles
Grids with square tiles
Grids with hexagonal tiles
Example

Description

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.

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

Synopsis

The Grid class

class Grid g whereSource

A regular arrangement of tiles. Minimal complete definition: indices and distance.

Associated Types

type Index g Source

Methods

indices :: g -> [Index g]Source

Returns the indices of all tiles in a grid.

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

distance g a b returns the minimum number of moves required to get from the tile at index 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

minDistance g bs a returns the minimum number of moves required to get from any of the tiles at indices 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 :: g -> Index g -> [Index g]Source

neighbours g x returns the indices of the tiles in the grid g which are adjacent to the tile with index x.

numNeighbours :: g -> Index g -> Int Source

numNeighbours g x returns the number of tiles in the grid g which are adjacent to the tile with index x.

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

g `'contains'` x returns True if the index x is contained within the grid g, otherwise it returns false.

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

viewpoint g x returns a list of pairs associating the index of each tile in g with its distance to the tile with index x. If x is not contained within g, the result is undefined.

tileCount :: g -> Int Source

Returns the number of tiles in a grid. Compare with size.

null :: g -> Bool Source

Returns True if the number of tiles in a grid is zero, False otherwise.

nonNull :: g -> Bool Source

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.

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

isAdjacent g a b returns 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 :: g -> Index g -> Index g -> [Index g]Source

adjacentTilesToward g a b returns the indices of all tiles which are neighbours of the tile at index 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

minimalPaths g a b returns a list of all minimal paths from the tile at index 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 adjacentTilesToward. If you want to use a custom algorithm, consider modifying adjacentTilesToward instead of minimalPaths.

class Grid g => FiniteGrid g whereSource

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

Associated Types

type Size s Source

Methods

size :: g -> Size gSource

Returns the dimensions of the grid. For example, if g is a 4x3 rectangular grid, size g would return (4, 3), while tileCount g would return 12.

Instances

FiniteGrid ParaHexGrid
FiniteGrid HexHexGrid
FiniteGrid TorSquareGrid
FiniteGrid RectSquareGrid
FiniteGrid TorTriGrid
FiniteGrid RectTriGrid
FiniteGrid ParaTriGrid
FiniteGrid TriTriGrid
FiniteGrid g => FiniteGrid (LGridMap g v)

class Grid g => BoundedGrid g whereSource

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

Methods

tileSideCount :: g -> Int Source

Returns the number of sides a tile has

boundary :: 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

isBoundary g x' returns True if the tile with index x is on a boundary of g, False otherwise. (Corner tiles are also boundary tiles.)

centre :: 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

isCentre g x' returns True if the tile with index x is a centre tile of g, False otherwise.

Instances

BoundedGrid ParaHexGrid
BoundedGrid HexHexGrid
BoundedGrid RectSquareGrid
BoundedGrid RectTriGrid
BoundedGrid ParaTriGrid
BoundedGrid TriTriGrid

Grids with triangular tiles

data UnboundedTriGrid Source

Instances

Show UnboundedTriGrid
Grid UnboundedTriGrid

data TriTriGrid Source

A triangular grid with triangular tiles. The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq TriTriGrid
Show TriTriGrid
BoundedGrid TriTriGrid
FiniteGrid TriTriGrid
Grid TriTriGrid

triTriGrid :: Int -> TriTriGrid Source

triTriGrid s returns a triangular grid with sides of length s, using triangular tiles. If s is nonnegative, the resulting grid will have s^2 tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

data ParaTriGrid Source

A Parallelogrammatical grid with triangular tiles. The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq ParaTriGrid
Show ParaTriGrid
BoundedGrid ParaTriGrid
FiniteGrid ParaTriGrid
Grid ParaTriGrid

paraTriGrid :: Int -> Int -> ParaTriGrid Source

paraTriGrid r c returns a grid in the shape of a parallelogram with r rows and c columns, using triangular tiles. If r and c are both nonnegative, the resulting grid will have 2*r*c tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

data RectTriGrid Source

A rectangular grid with triangular tiles. The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq RectTriGrid
Show RectTriGrid
BoundedGrid RectTriGrid
FiniteGrid RectTriGrid
Grid RectTriGrid

rectTriGrid :: Int -> Int -> RectTriGrid Source

rectTriGrid r c returns a grid in the shape of a rectangle (with jagged edges) that has r rows and c columns, using triangular tiles. If r and c are both nonnegative, the resulting grid will have 2*r*c tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

data TorTriGrid Source

A toroidal grid with triangular tiles. The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq TorTriGrid
Show TorTriGrid
WrappedGrid TorTriGrid
FiniteGrid TorTriGrid
Grid TorTriGrid

torTriGrid :: Int -> Int -> TorTriGrid Source

torTriGrid r c returns a toroidal grid with r rows and c columns, using triangular tiles. If r is odd, the result is undefined because the grid edges would overlap. If r and c are both nonnegative, the resulting grid will have 2*r*c tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

Grids with square tiles

data UnboundedSquareGrid Source

Instances

Show UnboundedSquareGrid
Grid UnboundedSquareGrid

data RectSquareGrid Source

A rectangular grid with square tiles. The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq RectSquareGrid
Show RectSquareGrid
BoundedGrid RectSquareGrid
FiniteGrid RectSquareGrid
Grid RectSquareGrid

rectSquareGrid :: Int -> Int -> RectSquareGrid Source

rectSquareGrid r c produces a rectangular grid with r rows and c columns, using square tiles. If r and c are both nonnegative, the resulting grid will have r*c tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

data TorSquareGrid Source

A toroidal grid with square tiles. The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq TorSquareGrid
Show TorSquareGrid
WrappedGrid TorSquareGrid
FiniteGrid TorSquareGrid
Grid TorSquareGrid

torSquareGrid :: Int -> Int -> TorSquareGrid Source

torSquareGrid r c returns a toroidal grid with r rows and c columns, using square tiles. If r and c are both nonnegative, the resulting grid will have r*c tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

Grids with hexagonal tiles

data UnboundedHexGrid Source

Instances

Show UnboundedHexGrid
Grid UnboundedHexGrid

data HexHexGrid Source

A hexagonal grid with hexagonal tiles The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq HexHexGrid
Show HexHexGrid
BoundedGrid HexHexGrid
FiniteGrid HexHexGrid
Grid HexHexGrid

hexHexGrid :: Int -> HexHexGrid Source

hexHexGrid s returns a grid of hexagonal shape, with sides of length s, using hexagonal tiles. If s is nonnegative, the resulting grid will have 3*s*(s-1) + 1 tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

data ParaHexGrid Source

A parallelogramatical grid with hexagonal tiles The grid and its indexing scheme are illustrated in the user guide, available at https://github.com/mhwombat/grid/wiki.

Instances

Eq ParaHexGrid
Show ParaHexGrid
BoundedGrid ParaHexGrid
FiniteGrid ParaHexGrid
Grid ParaHexGrid

paraHexGrid :: Int -> Int -> ParaHexGrid Source

paraHexGrid r c returns a grid in the shape of a parallelogram with r rows and c columns, using hexagonal tiles. If r and c are both nonnegative, the resulting grid will have r*c tiles. Otherwise, the resulting grid will be null and the list of indices will be null.

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