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 Applicative
s:
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.