let it leave me like a long breath

data BSPControl f a n e = BSPControl
  { minSize :: a
  , maxGeneration :: Integer
  , splitRange :: (Float, Float)
  , divideControl :: Maybe (f a -> f a -> Integer -> Bool)
  , includeSmallOverlaps :: Bool
  , rebuild :: f a -> f a -> n
  , reconnect :: f (TouchState a) -> e
  }

delve :: (Graph gr, RandomGen g, Random a, Integral a, Ord a, Num (f a), Applicative f, Metric f, Traversable f) => BSPControl f a n e -> f a -> Rand g (gr n e)
delve c size = liftM (construct c) $ bsp c size

so this is dimension-agnostic binary-space-partitioning code, which is nice, but wow are those a lot of type constraints. for a while i had both Integral a and Floating a constraints, which basically meant that there was no possible type that could work with the code. i'd still like to get rid of that Integral requirement, since it only comes up once in the entire set of functions, and there it's just because i need something i can cast to and from a floating-point value.

(the f values are expected to be V* values from Linear)

the bit that was most confusing at first (how exactly do i determine if n-dimensional axis-aligned prisms are touching) ended up being radically simplified due to Applicatives:

touching :: (Applicative f, Foldable f, Ord a, Num a) => BSPRoom (f a) -> BSPRoom (f a) -> f (TouchState a)
touching (BSPRoom pos size _) (BSPRoom pos' size' _) =
  test <$> pos <*> size <*> pos' <*> size'
  where
    test :: (Ord a, Num a) => a -> a -> a -> a -> TouchState a
    test start1 length1 start2 length2 = if start2 < start1
      then test start2 length2 start1 length1
      else case min length2 (start1 + length1 - start2) of
        x | x < 0 -> NoContact
          | x == 0 -> Touching start2
          | otherwise -> Overlapping start2 x

since of course if you have axis-aligned prisms you can decompose each of the dimensionality tests, so what this ends up doing is generating a vector that contains contact information for each dimension, and it turns out there are pretty simple rules for figuring out just when a contact vector is "really" touching, which i will LEAVE DETERMINING AS AN EXERCISE FOR THE READER. (hint: all dimensions being Touching means the two things touch on a single point; all dimensions being Overlapping means the two things contain a full overlapping subprism.) sadly i haven't really figured out a way to type-agnostically transform that into something useful (e.g., planes or lines) but whatever, the type variables have gotta run out sometime.