Structure container improvements, cursor cross

Cursor cross

I added a cursor cross to make it easier to align Structures. This is especially handy when placing Belts.

Structure container improvements

Over the past weeks I applied several improvements to how Structures are tracked.

Deduplicate code

Initially both the Blueprint and Planet kept track of their Structures individually.
While there was a shared container type both were using, the Planet tracked more data as part of various optimizations.
I moved all that into StructContainer so Blueprint could also benefit from existing and future optimizations.

Quad tree for find and visibility

I previously optimized the rendering to only consider visibile Structures. This was a great improvement, but still had to iterate all Structures:

for (id, element) in self.planet.elements().iter().enumerate() {
    if Self::is_visible(self.module_store, &current_area, &element) {
        //render here

With a QuadTree as member of the StructContainer it’s now possible to query it for Structures in an area:

impl StructContainer {
    ...
    pub fn for_all_in<F>(&self, area: &Area, f: &mut F)
    where
        F: FnMut(&PosElement),
    {
        ...
        self.pos_tree.borrow().for_all_in(area, f);
    }
    ...
}

Which can then be used during rendering:

self.planet
    .structs()
    .for_all_in(&current_area, &mut |x: &PosElement| {
        //render here

It’s now also used to find Structures by position:

impl StructContainer {
    ...
    pub fn get_id(&self, ms: &dyn MS, pos: &Pos<i64>) -> Option<StructureID> {
        ...
        self.pos_tree
            .borrow()
            .find(pos.x as f64, pos.y as f64)
            .map(|e| e.id)
    }
    ...
}

Position storage

Before using the QuadTree as described above, the positions were stored in a map:

pub struct StructContainer {
    positions: BTreeMap<Pos<i64>, StructureID>,
    ...
}

Since all lookups now happen via the tree, there’s no need to store the positions separately anymore, since Structures are already stored with their positions attached:

pub struct ContainerElement {
    pub pos: PosAnchor<i64>,
    pub rot: Rot,
    pub sm: StructureModule,
}
...
pub struct StructContainer {
    elements: Vec<ContainerElement>,
    ...
}

Dedicated visibility tree

The above approach still had one major flaw:
Structures that are not inside the current view aren’t rendered. This sounds like the expected result, but some Structures have a greater visual impact than their size. For example the Influence has only a size of 1x1, but has a large visual indicator for the Influence area.
To keep track of that I extended Structures with:

fn visibility_range(&self, ms: &dyn MS) -> u32;

And am using an AABB-Tree (axis aligned bounding box) to keep track of of the visibilities:

pub struct VisibilityElement {
    pub pos: Pos<i64>,
    pub range: u32,
    pub id: StructureID,
}
...
pub struct StructContainer {
    ...
    vis_tree: RefCell<AABBTree2D<VisibilityElement>>,
    ...
}

which is now used for the visibility check during rendering instead of the QuadTree.

Dirty flags

I also introduced dirty flags for all the search structures to avoid unnecessary recalculation of those.

pub struct StructContainer {
    ...
    vis_tree_dirty: RefCell<bool>,
    ...
}
...
impl StructContainer {
    ...
    pub fn add(&mut self, ms: &dyn MS, element: ContainerElement) -> AddResult {
        ...
        *self.vis_tree_dirty.borrow_mut() = true;

        Ok(())
    }
    ...
    pub fn for_all_visible_in<F>(&self, ms: &dyn MS, area: &Area, f: &mut F)
    where
        F: FnMut(&VisibilityElement),
    {
        self.update_search_trees(ms);
        ...
        self.vis_tree.borrow().for_each_collision_candidate(&bb, f)
    }
    ...
    fn update_search_trees(&self, ms: &dyn MS) {
        ...
        if *self.vis_tree_dirty.borrow() {
            ...
            *self.vis_tree_dirty.borrow_mut() = false;
        }
    }
}