-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Tools for working with regular grids (graphs, lattices).
--
-- Provides tools for working with regular arrangements of tiles, such as
-- might be used in a board game or some other type of grid map.
-- Currently supports triangular, square, and hexagonal tiles, with
-- various 2D and toroidal layouts. 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.
--
-- 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.
@package grid
@version 6.1
-- | A module containing private Grid internals. Most developers
-- should use Grid instead. This module is subject to change
-- without notice.
module Math.Geometry.GridInternal
-- | A regular arrangement of tiles. Minimal complete definition:
-- Index, Direction, indices,
-- distance, directionTo.
class Grid g where type family Index g type family Direction g minDistance = defaultMinDistance neighbours = defaultNeighbours neighbour = defaultNeighbour numNeighbours g = length . neighbours g contains g a = a `elem` indices g tileCount = length . indices null g = tileCount g ≡ 0 nonNull = not . null edges = defaultEdges viewpoint g p = map f (indices g) where f a = (a, distance g p a) isAdjacent = defaultIsAdjacent adjacentTilesToward = defaultAdjacentTilesToward minimalPaths = defaultMinimalPaths defaultMinDistance g xs a = minimum . map (distance g a) $ xs defaultNeighbours g a = filter (\ b -> distance g a b ≡ 1) $ indices g defaultNeighbour g a d = head . filter (\ b -> [d] ≡ directionTo g a b) . neighbours g $ a defaultTileCount = length . indices defaultEdges g = nubBy sameEdge $ concatMap (`adjacentEdges` g) $ indices g defaultIsAdjacent g a b = distance g a b ≡ 1 defaultAdjacentTilesToward g a b = filter f $ neighbours g a where f c = distance g c b ≡ distance g a b - 1 defaultMinimalPaths g a b | a ≡ b = [[a]] | distance g a b ≡ 1 = [[a, b]] | otherwise = map (a :) xs where xs = concatMap (\ c -> minimalPaths g c b) ys ys = adjacentTilesToward g a b
indices :: Grid g => g -> [Index g]
distance :: Grid g => g -> Index g -> Index g -> Int
minDistance :: Grid g => g -> [Index g] -> Index g -> Int
neighbours :: Grid g => g -> Index g -> [Index g]
neighbour :: (Grid g, Eq (Direction g)) => g -> Index g -> Direction g -> Index g
numNeighbours :: Grid g => g -> Index g -> Int
contains :: (Grid g, Eq (Index g)) => g -> Index g -> Bool
tileCount :: Grid g => g -> Int
null :: Grid g => g -> Bool
nonNull :: Grid g => g -> Bool
edges :: (Grid g, Eq (Index g)) => g -> [(Index g, Index g)]
viewpoint :: Grid g => g -> Index g -> [(Index g, Int)]
isAdjacent :: Grid g => g -> Index g -> Index g -> Bool
adjacentTilesToward :: Grid g => g -> Index g -> Index g -> [Index g]
minimalPaths :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> [[Index g]]
directionTo :: Grid g => g -> Index g -> Index g -> [Direction g]
defaultMinDistance :: Grid g => g -> [Index g] -> Index g -> Int
defaultNeighbours :: Grid g => g -> Index g -> [Index g]
defaultNeighbour :: (Grid g, Eq (Direction g)) => g -> Index g -> Direction g -> Index g
defaultTileCount :: Grid g => g -> Int
defaultEdges :: (Grid g, Eq (Index g)) => g -> [(Index g, Index g)]
defaultIsAdjacent :: Grid g => g -> Index g -> Index g -> Bool
defaultAdjacentTilesToward :: Grid g => g -> Index g -> Index g -> [Index g]
defaultMinimalPaths :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> [[Index g]]
sameEdge :: Eq t => (t, t) -> (t, t) -> Bool
adjacentEdges :: Grid g => Index g -> g -> [(Index g, Index g)]
cartesianIndices :: (Enum r, Enum c, Num r, Num c, Ord r, Ord c) => (r, c) -> [(c, r)]
cartesianCentre :: (Int, Int) -> [(Int, Int)]
cartesianMidpoints :: Int -> [Int]
-- | A regular arrangement of tiles where the number of tiles is finite.
-- Minimal complete definition: size.
class Grid g => FiniteGrid g where type family Size s
size :: FiniteGrid g => g -> Size g
-- | A regular arrangement of tiles with an edge. Minimal complete
-- definition: tileSideCount.
class Grid g => BoundedGrid g where boundary g = map fst . filter f $ xds where xds = map (\ b -> (b, numNeighbours g b)) $ indices g f (_, n) = n < tileSideCount g isBoundary g a = a `elem` boundary g centre g = map fst . last . groupBy ((≡) `on` snd) . sortBy (comparing snd) $ xds where xds = map (\ b -> (b, minDistance g bs b)) $ indices g bs = boundary g isCentre g a = a `elem` centre g
tileSideCount :: BoundedGrid g => g -> Int
boundary :: BoundedGrid g => g -> [Index g]
isBoundary :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool
centre :: BoundedGrid g => g -> [Index g]
isCentre :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool
-- | A regular arrangement of tiles where the boundaries are joined.
-- Minimal complete definition: normalise.
class Grid g => WrappedGrid g
normalise :: WrappedGrid g => g -> Index g -> Index g
denormalise :: WrappedGrid g => g -> Index g -> [Index g]
neighboursBasedOn :: (Eq (Index u), Grid g, Grid u, Index g ~ Index u) => u -> g -> Index g -> [Index g]
distanceBasedOn :: (Eq (Index g), Grid g, Grid u, Index g ~ Index u) => u -> g -> Index g -> Index g -> Int
directionToBasedOn :: (Eq (Index g), Eq (Direction g), Grid g, Grid u, Index g ~ Index u, Direction g ~ Direction u) => u -> g -> Index g -> Index g -> [Direction g]
neighboursWrappedBasedOn :: (Eq (Index g), WrappedGrid g, Grid u, Index g ~ Index u) => u -> g -> Index g -> [Index g]
neighbourWrappedBasedOn :: (Eq (Index g), Eq (Direction g), WrappedGrid g, Grid u, Index g ~ Index u, Direction g ~ Direction u) => u -> g -> Index g -> Direction g -> Index g
distanceWrappedBasedOn :: (Eq (Index g), WrappedGrid g, Grid u, Index g ~ Index u) => u -> g -> Index g -> Index g -> Int
directionToWrappedBasedOn :: (Eq (Index g), Eq (Direction g), WrappedGrid g, Grid u, Index g ~ Index u, Direction g ~ Direction u) => u -> g -> Index g -> Index g -> [Direction g]
-- | A module containing private TriGrid internals. Most
-- developers should use TriGrid instead. This module is subject
-- to change without notice.
module Math.Geometry.Grid.TriangularInternal
data TriDirection
South :: TriDirection
Northwest :: TriDirection
Northeast :: TriDirection
North :: TriDirection
Southeast :: TriDirection
Southwest :: TriDirection
-- | An unbounded grid with triangular tiles. The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedTriGrid
UnboundedTriGrid :: UnboundedTriGrid
-- | For triangular tiles, it is convenient to define a third component z.
triZ :: Int -> Int -> Int
-- | 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.
data TriTriGrid
TriTriGrid :: Int -> [(Int, Int)] -> TriTriGrid
inTriTriGrid :: (Int, Int) -> Int -> Bool
-- | 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.
triTriGrid :: Int -> TriTriGrid
-- | 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.
data ParaTriGrid
ParaTriGrid :: (Int, Int) -> [(Int, Int)] -> ParaTriGrid
-- | 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.
paraTriGrid :: Int -> Int -> ParaTriGrid
-- | 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.
data RectTriGrid
RectTriGrid :: (Int, Int) -> [(Int, Int)] -> RectTriGrid
-- | 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.
rectTriGrid :: Int -> Int -> RectTriGrid
-- | 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.
data TorTriGrid
TorTriGrid :: (Int, Int) -> [(Int, Int)] -> TorTriGrid
-- | torTriGrid r c returns a toroidal grid with r
-- rows and c columns, using triangular tiles. The indexing
-- method is the same as for ParaTriGrid. 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.
torTriGrid :: Int -> Int -> TorTriGrid
-- | A cylindrical grid with triangular tiles, where the cylinder is along
-- the y-axis. The grid and its indexing scheme are illustrated in the
-- user guide, available at https://github.com/mhwombat/grid/wiki.
data YCylTriGrid
YCylTriGrid :: (Int, Int) -> [(Int, Int)] -> YCylTriGrid
-- | yCylTriGrid r c returns a cylindrical grid with
-- r rows and c columns, using triangular tiles, where
-- the cylinder is along the y-axis. The indexing method is the same as
-- for ParaTriGrid. 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.
yCylTriGrid :: Int -> Int -> YCylTriGrid
instance Show TriDirection
instance Eq TriDirection
instance Show UnboundedTriGrid
instance Eq TriTriGrid
instance Eq ParaTriGrid
instance Eq RectTriGrid
instance Eq TorTriGrid
instance Eq YCylTriGrid
instance WrappedGrid YCylTriGrid
instance FiniteGrid YCylTriGrid
instance Grid YCylTriGrid
instance Show YCylTriGrid
instance WrappedGrid TorTriGrid
instance FiniteGrid TorTriGrid
instance Grid TorTriGrid
instance Show TorTriGrid
instance BoundedGrid RectTriGrid
instance FiniteGrid RectTriGrid
instance Grid RectTriGrid
instance Show RectTriGrid
instance BoundedGrid ParaTriGrid
instance FiniteGrid ParaTriGrid
instance Grid ParaTriGrid
instance Show ParaTriGrid
instance BoundedGrid TriTriGrid
instance FiniteGrid TriTriGrid
instance Grid TriTriGrid
instance Show TriTriGrid
instance Grid UnboundedTriGrid
-- | A regular arrangement of triangular tiles. The userguide, with
-- illustrations, is available at
-- https://github.com/mhwombat/grid/wiki. Also see
-- Math.Geometry.Grid for examples of how to use this class.
module Math.Geometry.Grid.Triangular
-- | An unbounded grid with triangular tiles. The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedTriGrid
-- | 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.
data TriTriGrid
-- | 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.
triTriGrid :: Int -> TriTriGrid
-- | 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.
data ParaTriGrid
-- | 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.
paraTriGrid :: Int -> Int -> ParaTriGrid
-- | 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.
data RectTriGrid
-- | 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.
rectTriGrid :: Int -> Int -> RectTriGrid
-- | 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.
data TorTriGrid
-- | torTriGrid r c returns a toroidal grid with r
-- rows and c columns, using triangular tiles. The indexing
-- method is the same as for ParaTriGrid. 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.
torTriGrid :: Int -> Int -> TorTriGrid
-- | A module containing private SquareGrid internals. Most
-- developers should use SquareGrid instead. This module is
-- subject to change without notice.
module Math.Geometry.Grid.SquareInternal
data SquareDirection
North :: SquareDirection
East :: SquareDirection
South :: SquareDirection
West :: SquareDirection
-- | An unbounded grid with square tiles. The grid and its indexing scheme
-- are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedSquareGrid
UnboundedSquareGrid :: UnboundedSquareGrid
-- | 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.
data RectSquareGrid
RectSquareGrid :: (Int, Int) -> [(Int, Int)] -> RectSquareGrid
-- | 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.
rectSquareGrid :: Int -> Int -> RectSquareGrid
-- | 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.
data TorSquareGrid
TorSquareGrid :: (Int, Int) -> [(Int, Int)] -> TorSquareGrid
-- | 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.
torSquareGrid :: Int -> Int -> TorSquareGrid
instance Show SquareDirection
instance Eq SquareDirection
instance Show UnboundedSquareGrid
instance Eq RectSquareGrid
instance Eq TorSquareGrid
instance WrappedGrid TorSquareGrid
instance FiniteGrid TorSquareGrid
instance Grid TorSquareGrid
instance Show TorSquareGrid
instance BoundedGrid RectSquareGrid
instance FiniteGrid RectSquareGrid
instance Grid RectSquareGrid
instance Show RectSquareGrid
instance Grid UnboundedSquareGrid
-- | A regular arrangement of square tiles. The userguide, with
-- illustrations, is available at
-- https://github.com/mhwombat/grid/wiki. Also see
-- Math.Geometry.Grid for examples of how to use this class.
module Math.Geometry.Grid.Square
-- | An unbounded grid with square tiles. The grid and its indexing scheme
-- are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedSquareGrid
-- | 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.
data RectSquareGrid
-- | 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.
rectSquareGrid :: Int -> Int -> RectSquareGrid
-- | 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.
data TorSquareGrid
-- | 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.
torSquareGrid :: Int -> Int -> TorSquareGrid
-- | A module containing private HexGrid internals. Most
-- developers should use HexGrid instead. This module is subject
-- to change without notice.
module Math.Geometry.Grid.HexagonalInternal
data HexDirection
West :: HexDirection
Northwest :: HexDirection
Northeast :: HexDirection
East :: HexDirection
Southeast :: HexDirection
Southwest :: HexDirection
-- | An unbounded grid with hexagonal tiles The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedHexGrid
UnboundedHexGrid :: UnboundedHexGrid
-- | 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.
data HexHexGrid
HexHexGrid :: Int -> [(Int, Int)] -> HexHexGrid
-- | 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.
hexHexGrid :: Int -> HexHexGrid
-- | 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.
data ParaHexGrid
ParaHexGrid :: (Int, Int) -> [(Int, Int)] -> ParaHexGrid
-- | 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.
paraHexGrid :: Int -> Int -> ParaHexGrid
instance Show HexDirection
instance Eq HexDirection
instance Show UnboundedHexGrid
instance Eq HexHexGrid
instance Eq ParaHexGrid
instance BoundedGrid ParaHexGrid
instance FiniteGrid ParaHexGrid
instance Grid ParaHexGrid
instance Show ParaHexGrid
instance BoundedGrid HexHexGrid
instance FiniteGrid HexHexGrid
instance Grid HexHexGrid
instance Show HexHexGrid
instance Grid UnboundedHexGrid
-- | A regular arrangement of hexagonal tiles. The userguide, with
-- illustrations, is available at
-- https://github.com/mhwombat/grid/wiki. Also see
-- Math.Geometry.Grid for examples of how to use this class.
module Math.Geometry.Grid.Hexagonal
-- | An unbounded grid with hexagonal tiles The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedHexGrid
-- | 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.
data HexHexGrid
-- | 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.
hexHexGrid :: Int -> HexHexGrid
-- | 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.
data ParaHexGrid
-- | 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.
paraHexGrid :: Int -> Int -> ParaHexGrid
-- | A module containing private OctGrid internals. Most
-- developers should use OctGrid instead. This module is subject
-- to change without notice.
module Math.Geometry.Grid.OctagonalInternal
data OctDirection
West :: OctDirection
Northwest :: OctDirection
North :: OctDirection
Northeast :: OctDirection
East :: OctDirection
Southeast :: OctDirection
South :: OctDirection
Southwest :: OctDirection
-- | An unbounded grid with octagonal tiles. The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedOctGrid
UnboundedOctGrid :: UnboundedOctGrid
-- | A rectangular grid with octagonal tiles. The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data RectOctGrid
RectOctGrid :: (Int, Int) -> [(Int, Int)] -> RectOctGrid
-- | rectOctGrid r c produces a rectangular grid with
-- r rows and c columns, using octagonal 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.
rectOctGrid :: Int -> Int -> RectOctGrid
-- | A toroidal grid with octagonal tiles. The grid and its indexing scheme
-- are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data TorOctGrid
TorOctGrid :: (Int, Int) -> [(Int, Int)] -> TorOctGrid
-- | torOctGrid r c returns a toroidal grid with r
-- rows and c columns, using octagonal 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.
torOctGrid :: Int -> Int -> TorOctGrid
instance Show OctDirection
instance Eq OctDirection
instance Show UnboundedOctGrid
instance Eq RectOctGrid
instance Eq TorOctGrid
instance WrappedGrid TorOctGrid
instance FiniteGrid TorOctGrid
instance Grid TorOctGrid
instance Show TorOctGrid
instance BoundedGrid RectOctGrid
instance FiniteGrid RectOctGrid
instance Grid RectOctGrid
instance Show RectOctGrid
instance Grid UnboundedOctGrid
-- | A regular arrangement of octagonal tiles. Octagons won't tile a
-- regular plane (there will be diamond-shaped gaps between the tiles),
-- but they will tile a hyperbolic plane. (Alternatively, you can
-- think of these as squares on a board game where diagonal moves are
-- allowed.) The userguide, with illustrations, is available at
-- https://github.com/mhwombat/grid/wiki. Also see
-- Math.Geometry.Grid for examples of how to use this class.
module Math.Geometry.Grid.Octagonal
-- | An unbounded grid with octagonal tiles. The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data UnboundedOctGrid
-- | A rectangular grid with octagonal tiles. The grid and its indexing
-- scheme are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data RectOctGrid
-- | rectOctGrid r c produces a rectangular grid with
-- r rows and c columns, using octagonal 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.
rectOctGrid :: Int -> Int -> RectOctGrid
-- | A toroidal grid with octagonal tiles. The grid and its indexing scheme
-- are illustrated in the user guide, available at
-- https://github.com/mhwombat/grid/wiki.
data TorOctGrid
-- | torOctGrid r c returns a toroidal grid with r
-- rows and c columns, using octagonal 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.
torOctGrid :: Int -> Int -> TorOctGrid
-- | 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.
module Math.Geometry.Grid
-- | A regular arrangement of tiles. Minimal complete definition:
-- Index, Direction, indices,
-- distance, directionTo.
class Grid g where type family Index g type family Direction g minDistance = defaultMinDistance neighbours = defaultNeighbours neighbour = defaultNeighbour numNeighbours g = length . neighbours g contains g a = a `elem` indices g tileCount = length . indices null g = tileCount g ≡ 0 nonNull = not . null edges = defaultEdges viewpoint g p = map f (indices g) where f a = (a, distance g p a) isAdjacent = defaultIsAdjacent adjacentTilesToward = defaultAdjacentTilesToward minimalPaths = defaultMinimalPaths defaultMinDistance g xs a = minimum . map (distance g a) $ xs defaultNeighbours g a = filter (\ b -> distance g a b ≡ 1) $ indices g defaultNeighbour g a d = head . filter (\ b -> [d] ≡ directionTo g a b) . neighbours g $ a defaultTileCount = length . indices defaultEdges g = nubBy sameEdge $ concatMap (`adjacentEdges` g) $ indices g defaultIsAdjacent g a b = distance g a b ≡ 1 defaultAdjacentTilesToward g a b = filter f $ neighbours g a where f c = distance g c b ≡ distance g a b - 1 defaultMinimalPaths g a b | a ≡ b = [[a]] | distance g a b ≡ 1 = [[a, b]] | otherwise = map (a :) xs where xs = concatMap (\ c -> minimalPaths g c b) ys ys = adjacentTilesToward g a b
indices :: Grid g => g -> [Index g]
distance :: Grid g => g -> Index g -> Index g -> Int
minDistance :: Grid g => g -> [Index g] -> Index g -> Int
neighbours :: Grid g => g -> Index g -> [Index g]
neighbour :: (Grid g, Eq (Direction g)) => g -> Index g -> Direction g -> Index g
contains :: (Grid g, Eq (Index g)) => g -> Index g -> Bool
tileCount :: Grid g => g -> Int
null :: Grid g => g -> Bool
nonNull :: Grid g => g -> Bool
edges :: (Grid g, Eq (Index g)) => g -> [(Index g, Index g)]
viewpoint :: Grid g => g -> Index g -> [(Index g, Int)]
isAdjacent :: Grid g => g -> Index g -> Index g -> Bool
adjacentTilesToward :: Grid g => g -> Index g -> Index g -> [Index g]
minimalPaths :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> [[Index g]]
directionTo :: Grid g => g -> Index g -> Index g -> [Direction g]
-- | A regular arrangement of tiles where the number of tiles is finite.
-- Minimal complete definition: size.
class Grid g => FiniteGrid g where type family Size s
size :: FiniteGrid g => g -> Size g
-- | A regular arrangement of tiles with an edge. Minimal complete
-- definition: tileSideCount.
class Grid g => BoundedGrid g where boundary g = map fst . filter f $ xds where xds = map (\ b -> (b, numNeighbours g b)) $ indices g f (_, n) = n < tileSideCount g isBoundary g a = a `elem` boundary g centre g = map fst . last . groupBy ((≡) `on` snd) . sortBy (comparing snd) $ xds where xds = map (\ b -> (b, minDistance g bs b)) $ indices g bs = boundary g isCentre g a = a `elem` centre g
tileSideCount :: BoundedGrid g => g -> Int
boundary :: BoundedGrid g => g -> [Index g]
isBoundary :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool
centre :: BoundedGrid g => g -> [Index g]
isCentre :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool
-- | Ordered maps from tiles on a grid to values. This module is a wrapper
-- around Grid and Map, in order to
-- combine the functionality of grids and maps into a single type.
module Math.Geometry.GridMap
-- | A regular arrangement of tiles, having a value associated with each
-- tile. Minimal complete definition: toMap, toGrid,
-- adjustWithKey, mapWithKey.
--
-- Note: Some of the methods have an Ord constraint on the grid
-- index. This is purely to make it easier to write implementations.
-- While tile positions can be ordered (e.g., (1,2) < (2,1)),
-- the ordering may not be particularly meaningful. (Comparisons such as
-- east of or south of may be more sensible.) However, it
-- is convenient to write implementations of this class using
-- Data.Map, with the grid indices as keys. Many of the
-- functions in Data.Map impose the Ord constraint on
-- map keys, so we'll live with it. In summary, to use some methods in
-- this class, your grid indices must be orderable.
class (Grid (BaseGrid gm v), Foldable gm) => GridMap (gm :: * -> *) v where type family BaseGrid gm v ! gm k = toMap gm ! k toList = toList . toMap lookup k = lookup k . toMap adjust f = adjustWithKey (\ _ v -> f v) findWithDefault v k = findWithDefault v k . toMap elems = elems . toMap map f = mapWithKey (\ _ v -> f v)
(!) :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => gm v -> k -> v
toMap :: (GridMap gm v, k ~ (Index (BaseGrid gm v))) => gm v -> Map k v
toGrid :: GridMap gm v => gm v -> BaseGrid gm v
toList :: (GridMap gm v, k ~ (Index (BaseGrid gm v))) => gm v -> [(k, v)]
lookup :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => k -> gm v -> Maybe v
adjust :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => (v -> v) -> k -> gm v -> gm v
adjustWithKey :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => (k -> v -> v) -> k -> gm v -> gm v
findWithDefault :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => v -> k -> gm v -> v
elems :: GridMap gm v => gm v -> [v]
map :: (GridMap gm v, GridMap gm v2, Index (BaseGrid gm v) ~ Index (BaseGrid gm v2)) => (v -> v2) -> gm v -> gm v2
mapWithKey :: (GridMap gm v, k ~ Index (BaseGrid gm v), k ~ Index (BaseGrid gm v2), GridMap gm v2) => (k -> v -> v2) -> gm v -> gm v2
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . elems.
--
-- For example,
--
--
-- elems map = foldr (:) [] map
--
--
--
-- let f a len = len + (length a)
-- foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldr :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . elems.
--
-- For example,
--
--
-- elems = reverse . foldl (flip (:)) []
--
--
--
-- let f len a = len + (length a)
-- foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldl :: (a -> b -> a) -> a -> Map k b -> a
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> Map k b -> a
-- | Ordered maps from tiles on a grid to values. This module is a wrapper
-- around Grid and Map, in order to
-- combine the functionality of grids and maps into a single type.
module Math.Geometry.GridMap.Lazy
-- | A map from tile positions in a grid to values.
data LGridMap g v
-- | Construct a grid map which is strict in the keys (tile positions), but
-- lazy in the values.
lazyGridMap :: (Ord (Index g), Grid g) => g -> [v] -> LGridMap g v
instance (Show g, Show v) => Show (LGridMap g v)
instance (Eq g, Eq (Index g), Eq v) => Eq (LGridMap g v)
instance Grid g => GridMap (LGridMap g) v
instance FiniteGrid g => FiniteGrid (LGridMap g v)
instance Grid g => Grid (LGridMap g v)
instance Foldable (LGridMap g)
instance (Grid g, Ord (Index g)) => Functor (LGridMap g)