grid-7.8.12: Tools for working with regular grids (graphs, lattices).

Copyright (c) Amy de Buitléir 2012-2017 BSD-style amy@nualeargais.ie experimental portable Safe Haskell2010

Math.Geometry.Grid

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.

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.

Synopsis

# 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
False

# Grids

class Grid g where Source #

A regular arrangement of tiles. Minimal complete definition: Index, Direction, indices, distance, directionTo.

Minimal complete definition

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 :: Eq (Index g) => g -> Index g -> [Index g] Source #

neighbours g a returns the indices of the tiles in the grid 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 #

neighbour g d a returns the indices of the tile in the grid g which is adjacent to the tile with index a, in the direction d.

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

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

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.

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

viewpoint g a returns a list of pairs associating the index of each tile in 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 #

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 :: Eq (Index g) => 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.

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

directionTo g a b returns the direction(s) of the next tile(s) in a minimal path from the tile at index a to the tile at index b in grid g.

Instances
 Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Associated Types Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Associated Types Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Associated Types Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Associated Types Grid g => Grid (LGridMap g v) Source # Instance detailsDefined in Math.Geometry.GridMap.Lazy Associated Typestype Index (LGridMap g v) :: Type Source #type Direction (LGridMap g v) :: Type Source # Methodsindices :: LGridMap g v -> [Index (LGridMap g v)] Source #distance :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> Int Source #minDistance :: LGridMap g v -> [Index (LGridMap g v)] -> Index (LGridMap g v) -> Int Source #neighbours :: LGridMap g v -> Index (LGridMap g v) -> [Index (LGridMap g v)] Source #neighboursOfSet :: LGridMap g v -> [Index (LGridMap g v)] -> [Index (LGridMap g v)] Source #neighbour :: LGridMap g v -> Index (LGridMap g v) -> Direction (LGridMap g v) -> Maybe (Index (LGridMap g v)) Source #numNeighbours :: LGridMap g v -> Index (LGridMap g v) -> Int Source #contains :: LGridMap g v -> Index (LGridMap g v) -> Bool Source #tileCount :: LGridMap g v -> Int Source #null :: LGridMap g v -> Bool Source #nonNull :: LGridMap g v -> Bool Source #edges :: LGridMap g v -> [(Index (LGridMap g v), Index (LGridMap g v))] Source #viewpoint :: LGridMap g v -> Index (LGridMap g v) -> [(Index (LGridMap g v), Int)] Source #isAdjacent :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> Bool Source #adjacentTilesToward :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> [Index (LGridMap g v)] Source #minimalPaths :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> [[Index (LGridMap g v)]] Source #directionTo :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> [Direction (LGridMap g v)] Source #defaultMinDistance :: LGridMap g v -> [Index (LGridMap g v)] -> Index (LGridMap g v) -> Int Source #defaultNeighbours :: LGridMap g v -> Index (LGridMap g v) -> [Index (LGridMap g v)] Source #defaultNeighboursOfSet :: LGridMap g v -> [Index (LGridMap g v)] -> [Index (LGridMap g v)] Source #defaultNeighbour :: LGridMap g v -> Index (LGridMap g v) -> Direction (LGridMap g v) -> Maybe (Index (LGridMap g v)) Source #defaultEdges :: LGridMap g v -> [(Index (LGridMap g v), Index (LGridMap g v))] Source #defaultIsAdjacent :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> Bool Source #defaultAdjacentTilesToward :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> [Index (LGridMap g v)] Source #defaultMinimalPaths :: LGridMap g v -> Index (LGridMap g v) -> Index (LGridMap g v) -> [[Index (LGridMap g v)]] Source #

type family Index g Source #

Instances
 type Index XCylTriGrid Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index XCylTriGrid = (Int, Int) type Index YCylTriGrid Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index YCylTriGrid = (Int, Int) type Index TorTriGrid Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index TorTriGrid = (Int, Int) type Index RectTriGrid Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index RectTriGrid = (Int, Int) type Index ParaTriGrid Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index ParaTriGrid = (Int, Int) type Index TriTriGrid Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index TriTriGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal type Index UnboundedTriGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal type Index TorSquareGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal type Index RectSquareGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal type Index UnboundedSquareGrid = (Int, Int) type Index TorOctGrid Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal type Index TorOctGrid = (Int, Int) type Index RectOctGrid Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal type Index RectOctGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal type Index UnboundedOctGrid = (Int, Int) type Index RectHexGrid Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 type Index RectHexGrid = (Int, Int) type Index HexHexGrid Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 type Index HexHexGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 type Index UnboundedHexGrid = (Int, Int) type Index ParaHexGrid Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal type Index ParaHexGrid = (Int, Int) type Index HexHexGrid Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal type Index HexHexGrid = (Int, Int) Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal type Index UnboundedHexGrid = (Int, Int) type Index (LGridMap g v) Source # Instance detailsDefined in Math.Geometry.GridMap.Lazy type Index (LGridMap g v) = Index g

type family Direction g Source #

Instances
 Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal type Direction (LGridMap g v) Source # Instance detailsDefined in Math.Geometry.GridMap.Lazy type Direction (LGridMap g v) = Direction 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.

Associated Types

type Size g Source #

Methods

size :: g -> Size g Source #

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.

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

Instances
 Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Associated Types Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Associated Types Methods FiniteGrid g => FiniteGrid (LGridMap g v) Source # Instance detailsDefined in Math.Geometry.GridMap.Lazy Associated Typestype Size (LGridMap g v) :: Type Source # Methodssize :: LGridMap g v -> Size (LGridMap g v) Source #

# Bounded grids

class Grid g => BoundedGrid g where Source #

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

Minimal complete definition

tileSideCount

Methods

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 #

isBoundary g a' returns 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 #

isCentre g a' returns 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 #

Instances
 Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Methods Source # Instance detailsDefined in Math.Geometry.Grid.TriangularInternal Methods Source # Instance detailsDefined in Math.Geometry.Grid.SquareInternal Methods Source # Instance detailsDefined in Math.Geometry.Grid.OctagonalInternal Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal2 Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Methods Source # Instance detailsDefined in Math.Geometry.Grid.HexagonalInternal Methods BoundedGrid g => BoundedGrid (LGridMap g v) Source # Instance detailsDefined in Math.Geometry.GridMap.Lazy MethodstileSideCount :: LGridMap g v -> Int Source #boundary :: LGridMap g v -> [Index (LGridMap g v)] Source #isBoundary :: LGridMap g v -> Index (LGridMap g v) -> Bool Source #centre :: LGridMap g v -> [Index (LGridMap g v)] Source #isCentre :: LGridMap g v -> Index (LGridMap g v) -> Bool Source #defaultBoundary :: LGridMap g v -> [Index (LGridMap g v)] Source #defaultIsBoundary :: LGridMap g v -> Index (LGridMap g v) -> Bool Source #defaultCentre :: LGridMap g v -> [Index (LGridMap g v)] Source #defaultIsCentre :: LGridMap g v -> Index (LGridMap g v) -> Bool Source #