Safe Haskell | None |
---|---|
Language | Haskell2010 |
This toolkit allows one to create and manipulate 2D Binary Space Partition trees. They can be used to split a rectangular region into non overlapping sub-regions.
- data BSP = BSP {}
- type BSPCallback = BSP -> IO Bool
- bspNew :: IO BSP
- bspNewWithSize :: Int -> Int -> Int -> Int -> IO BSP
- bspDelete :: BSP -> IO ()
- bspLeft :: BSP -> IO (Maybe BSP)
- bspRight :: BSP -> IO (Maybe BSP)
- bspFather :: BSP -> IO (Maybe BSP)
- bspIsLeaf :: BSP -> IO Bool
- bspTraversePreOrder :: BSP -> BSPCallback -> IO Bool
- bspTraverseInOrder :: BSP -> BSPCallback -> IO Bool
- bspTraversePostOrder :: BSP -> BSPCallback -> IO Bool
- bspTraverseLevelOrder :: BSP -> BSPCallback -> IO Bool
- bspTraverseInvertedLevelOrder :: BSP -> BSPCallback -> IO Bool
- bspContains :: BSP -> Int -> Int -> IO Bool
- bspFindNode :: BSP -> Int -> Int -> IO (Maybe BSP)
- bspResize :: BSP -> Int -> Int -> Int -> Int -> IO ()
- bspSplitOnce :: BSP -> Bool -> Int -> IO ()
- bspSplitRecursive :: BSP -> TCODRandom -> Int -> Int -> Int -> Float -> Float -> IO ()
- bspRemoveSons :: BSP -> IO ()
Documentation
Data for BSP of map
Creating the root node
First, you have to create the root node of the tree. This node encompasses the whole rectangular region.
:: Int | x Top left corner position and size of the rectangular region covered by the BSP tree. |
-> Int | y |
-> Int | w |
-> Int | h |
-> IO BSP |
Creating the root node
First, you have to create the root node of the tree. This node encompasses the whole rectangular region.
bspIsLeaf :: BSP -> IO Bool Source #
You can know if a node is a leaf (not split, no sons) with this function
:: BSP | node |
-> BSPCallback | |
-> IO Bool |
Traversing the tree
You can scan all the nodes of the tree and have a custom function called back for each node. Each traversal function returns false if the traversal has been interrupted (a callback returned false).
Pre-order : the callback is called for the current node, then for the left son, then for the right son.
:: BSP | node |
-> BSPCallback | |
-> IO Bool |
Traversing the tree
You can scan all the nodes of the tree and have a custom function called back for each node. Each traversal function returns false if the traversal has been interrupted (a callback returned false).
In-order : the callback is called for the left son, then for current node, then for the right son.
:: BSP | node |
-> BSPCallback | |
-> IO Bool |
Traversing the tree
You can scan all the nodes of the tree and have a custom function called back for each node. Each traversal function returns false if the traversal has been interrupted (a callback returned false).
Post-order : the callback is called for the left son, then for the right son, then for the current node.
bspTraverseLevelOrder Source #
:: BSP | node |
-> BSPCallback | |
-> IO Bool |
Traversing the tree
You can scan all the nodes of the tree and have a custom function called back for each node. Each traversal function returns false if the traversal has been interrupted (a callback returned false).
Level-order : the callback is called for the nodes level by level, from left to right.
bspTraverseInvertedLevelOrder Source #
:: BSP | node |
-> BSPCallback | |
-> IO Bool |
Traversing the tree
You can scan all the nodes of the tree and have a custom function called back for each node. Each traversal function returns false if the traversal has been interrupted (a callback returned false).
Inverted level-order : the callback is called in the exact inverse order as Level-order.
This operation resets the size of the tree nodes without changing the splitting data (orientation/position). It should be called with the initial region size or a bigger size, else some splitting position may be out of the region.
You can use it if you changed the nodes size and position while using the BSP tree, which happens typically when you use the tree to build a dungeon. You create rooms inside the tree leafs, then shrink the leaf to fit the room size. Calling resize on the root node with the original region size allows you to reset all nodes to their original size.
Splitting a node once
Once you have the root node, you can split it into two smaller non-overlapping nodes.
:: BSP | |
-> TCODRandom | randomize algorithm |
-> Int | Number of recursion levels. |
-> Int | min h size. Minimum values of w and h for a node. A node is split only if the resulting sub-nodes are bigger than minHSize x minVSize |
-> Int | min v size |
-> Float | max h ratio. Maximum values of wh and hw for a node. If a node does not conform, the splitting orientation is forced to reduce either the wh or the hw ratio. Use values near 1.0 to promote square nodes. |
-> Float | max v ratio |
-> IO () |
Recursively splitting a node
You can also recursively split the bsp. At each step, a random orientation (horizontal/vertical) and position are chosen
bspRemoveSons :: BSP -> IO () Source #
Deleting a part of the tree
You can delete a part of the tree, releasing resources for all sub nodes with