Binary Space Partition in Rust

Generating maps for rogelikes requires placing some rooms sometimes. Generally, these rooms shouldn’t overlap. A simple way to generate these rooms is to start with the complete area, then split it into different rooms, until you are left with rooms that you like.

A generic algorithm to do this space partitioning could be configured by passing higher order functions. In Haskell, this would look like this:

    type Split a = a -> [a]
    type Final a = a -> bool
    binary_space_partition :: a -> Split a -> Final a -> [a]

In Rust, generics are a bit more compilicated. Additionally, in Rust you’d generally use Iterators instead of lists or Vecs. When using Iterators, the algorithm can be implemented with less heap allocations.

I’d like to write the following Rust signature:

    fn binary_space_partition<A>(
        area: A,
        split: impl FnMut(A) -> impl Iterator<Item = A>,
        is_final: impl FnMut(a: &A) -> bool 
    ) -> impl Iterator<Item = A>
    {
        todo!()
    }

But you can’t write impl return types in argument positions, so you have to add another generic parameter.

The Implementation is quite simple. You save all areas in a to-be-split stack. Then you return the topmost area if it is final, otherwise you split it and push all splits back onto the stack.

Here is the final imlementation:

    fn binary_space_partition<A, As: Iterator<Item = A>>(
        area: A,
        split: impl FnMut(A) -> As,
        is_final: impl FnMut(a: &A) -> bool
    ) -> impl Iterator<Item = A>
    {
        let mut stack = vec![];
        std::iter::from_fn(move || loop {
            let a = stack.pop()?;
            if is_final(&a) {
                return a;
            } else {
                for next in split(a) {
                    stack.push(next);
                }
            }
        })
    }

With the new const-generics feature you could even make the algorithm completely allocation free. Instead of having a stack Vec, you could pass a const: L: usize and store the stack in an array with length L.

The push and pop methods require the possibility for absence of values, so the stack type would probably have to be [Option<a>; L].

A 2D Area could have the following layout:

    #[derive(Debug, Clone, Copy)]
    struct Point { x: u32, y: u32 };    

    #[derive(Debug, Clone, Copy)]
    struct Area {
        pos: Point,
        dimensions: Point,
    }

    impl Area {
        fn split_horizontal(&self) -> (Self, Self) { todo!() }
        fn split_vertical(&self) -> (Self, Self) { todo!() }
        fn surface_area(&self) -> u32 { todo!() }
    }

To use this algorithm, you have to provide apropriate split and final implementations.

    fn split_area(a: Area) -> impl Iterator<Item = Area> {
        let (a1, a2) = if area.dimensions.x > area.dimensions.y {
            split_vertical(&a)
        } else {
            split_horizontal(&a);
        };
        use std::iter::once;
        once(a1).chain(once(a2))
    }

    fn partition_area(base: Area, target: u32) -> Vec<Area> {
        binary_space_partition(
            base,
            split_area,
            |&a| a.surface_area() > target
        ).collect()
    }