Add dungeon level generation

Add a dungeon level generator, which:

1. generates an infinite sequence of rectangular rooms within the
   dimensions of the level
2. removes any duplicates from that sequence
3. Generates a graph from the delaunay triangulation of the centerpoints
   of those rooms
4. Generates the minimum-spanning-tree of that delaunay triangulation,
   with weights given by line length in points
5. Adds back a subset (default 10-15%) of edges from the delaunay
   triangulation to the graph
6. Uses the resulting graph to draw corridors between the rooms, using a
   random point on the near edge of each room to pick the points of the
   corridors

3 files changed, 71 insertions, 4 deletions

diff --git a/test/Spec.hs b/test/Spec.hs
index 73b965bdb6ca..8141b83e9771 100644
--- a/test/Spec.hs
+++ b/test/Spec.hs
@@ -9,6 +9,7 @@ import qualified Xanthous.Generators.UtilSpec
 import qualified Xanthous.MessageSpec
 import qualified Xanthous.OrphansSpec
 import qualified Xanthous.Util.GraphicsSpec
+import qualified Xanthous.Util.GraphSpec
 import qualified Xanthous.Util.InflectionSpec
 import qualified Xanthous.UtilSpec
 
@@ -28,5 +29,6 @@ test = testGroup "Xanthous"
   , Xanthous.DataSpec.test
   , Xanthous.UtilSpec.test
   , Xanthous.Util.GraphicsSpec.test
+  , Xanthous.Util.GraphSpec.test
   , Xanthous.Util.InflectionSpec.test
   ]
diff --git a/test/Xanthous/DataSpec.hs b/test/Xanthous/DataSpec.hs
index 6fad88681acb..bd02c0f36fe5 100644
--- a/test/Xanthous/DataSpec.hs
+++ b/test/Xanthous/DataSpec.hs
@@ -1,10 +1,10 @@
--- |
-
+--------------------------------------------------------------------------------
 module Xanthous.DataSpec (main, test) where
-
+--------------------------------------------------------------------------------
 import Test.Prelude hiding (Right, Left, Down)
 import Xanthous.Data
 import Data.Group
+--------------------------------------------------------------------------------
 
 main :: IO ()
 main = defaultMain test
@@ -35,11 +35,12 @@ test = testGroup "Xanthous.Data"
           (not . isUnit) (Position @Int 1 13) @? "isUnit $ Position 1 13"
       ]
     ]
+
   , testGroup "Direction"
     [ testProperty "opposite is involutive" $ \(dir :: Direction) ->
         opposite (opposite dir) == dir
     , testProperty "opposite provides inverse" $ \dir ->
-        invert (asPosition dir) == asPosition (opposite dir)
+        invert (asPosition dir) === asPosition (opposite dir)
     , testProperty "asPosition isUnit" $ \dir ->
         dir /= Here ==> isUnit (asPosition dir)
     , testGroup "Move"
@@ -53,4 +54,29 @@ test = testGroup "Xanthous.Data"
       , testCase "DownRight" $ move DownRight mempty @?= Position 1 1
       ]
     ]
+
+  , testGroup "Corner"
+    [ testGroup "instance Opposite"
+      [ testProperty "involutive" $ \corner ->
+          opposite (opposite corner) === corner
+      ]
+    ]
+
+  , testGroup "Edge"
+    [ testGroup "instance Opposite"
+      [ testProperty "involutive" $ \edge ->
+          opposite (opposite edge) === edge
+      ]
+    ]
+
+  , testGroup "Box"
+    [ testGroup "boxIntersects"
+      [ testProperty "True" $ \dims ->
+          boxIntersects (Box @Word (V2 1 1) (V2 2 2))
+                        (Box (V2 2 2) dims)
+      , testProperty "False" $ \dims ->
+          not $ boxIntersects (Box @Word (V2 1 1) (V2 2 2))
+                            (Box (V2 4 2) dims)
+      ]
+    ]
   ]
diff --git a/test/Xanthous/Util/GraphSpec.hs b/test/Xanthous/Util/GraphSpec.hs
new file mode 100644
index 000000000000..35ff090b28b9
--- /dev/null
+++ b/test/Xanthous/Util/GraphSpec.hs
@@ -0,0 +1,39 @@
+module Xanthous.Util.GraphSpec (main, test) where
+--------------------------------------------------------------------------------
+import Test.Prelude
+--------------------------------------------------------------------------------
+import Xanthous.Util.Graph
+import Data.Graph.Inductive.Basic
+import Data.Graph.Inductive.Graph (labNodes, size, order)
+import Data.Graph.Inductive.PatriciaTree
+import Data.Graph.Inductive.Arbitrary
+--------------------------------------------------------------------------------
+
+main :: IO ()
+main = defaultMain test
+
+test :: TestTree
+test = testGroup "Xanthous.Util.Graph"
+  [ testGroup "mstSubGraph"
+    [ testProperty "always produces a subgraph"
+        $ \(CG _ (graph :: Gr Int Int)) ->
+          let msg = mstSubGraph $ undir graph
+          in counterexample (show msg)
+            $ msg `isSubGraphOf` undir graph
+    , testProperty "returns a graph with the same nodes"
+        $ \(CG _ (graph :: Gr Int Int)) ->
+          let msg = mstSubGraph graph
+          in counterexample (show msg)
+            $ labNodes msg === labNodes graph
+    , testProperty "has nodes - 1 edges"
+        $ \(CG _ (graph :: Gr Int Int)) ->
+          order graph > 1 ==>
+          let msg = mstSubGraph graph
+          in counterexample (show msg)
+            $ size msg === order graph - 1
+    , testProperty "always produces a simple graph"
+        $ \(CG _ (graph :: Gr Int Int)) ->
+          let msg = mstSubGraph graph
+          in counterexample (show msg) $ isSimple msg
+    ]
+  ]