pub mod interactors;
mod jostler;
pub use crate::autoplacer::jostler::Jostler;
use std::ops::ControlFlow;
use derive_getters::Getters;
use rand::RngExt;
use rand_distr::{Distribution, Normal};
use undoredo::{ApplyDelta, Delta, ExtendDelta, FlushDelta, ResetDelta};
use crate::{
board::{Board, BoardHalfDelta},
layout::{Layout, compounds::ComponentId},
orientation::Orientation,
selections::ComponentSelection,
vector::Vector2,
};
#[derive(Clone, Copy)]
pub struct AutoplacerSchedule {
pub initial_temperature: f64,
pub temperature_common_ratio: f64,
pub initial_std_dev: f64,
pub std_dev_common_ratio: f64,
pub max_steps: u64,
}
#[derive(Clone)]
pub struct AutoplacerStepParams {
component_temperatures: Vec<f64>,
std_dev: f64,
}
#[derive(Clone, Getters)]
pub struct Autoplacer {
origin_delta: Delta<BoardHalfDelta>,
components: Vec<ComponentId>,
component_temperatures: Vec<f64>,
acceptance_rates: Vec<f64>,
schedule: AutoplacerSchedule,
step_counter: u64,
curr_component_index: usize,
}
impl Autoplacer {
pub fn new(board: &Board, selection: ComponentSelection, schedule: AutoplacerSchedule) -> Self {
let components: Vec<ComponentId> = board.resolve_components(selection).collect();
Self {
origin_delta: Delta::new(),
component_temperatures: std::iter::repeat_n(
schedule.initial_temperature,
components.len(),
)
.collect(),
acceptance_rates: std::iter::repeat_n(0.5, components.len()).collect(),
components,
schedule,
step_counter: 0,
curr_component_index: 0,
}
}
#[inline]
pub fn step(&mut self, board: &mut Board) -> ControlFlow<()> {
crate::profile_function!();
if self.step_counter < self.schedule.max_steps {
let control_flow = self.step_with_params(
board,
&AutoplacerStepParams {
component_temperatures: self.component_temperatures.clone(),
std_dev: self.schedule.initial_std_dev
* self
.schedule
.std_dev_common_ratio
.powf(self.step_counter as f64),
},
);
self.step_counter += 1;
control_flow
} else {
board.extend_delta(self.origin_delta.clone());
ControlFlow::Break(())
}
}
pub fn abort(&mut self, board: &mut Board) {
board.apply_delta(self.origin_delta.clone().reverse());
}
#[inline]
fn step_with_params(
&mut self,
board: &mut Board,
params: &AutoplacerStepParams,
) -> ControlFlow<()> {
crate::profile_function!();
if self.curr_component_index < self.components.len() {
self.step_component(board, self.curr_component_index, params);
self.curr_component_index = (self.curr_component_index + 1) % self.components.len();
}
ControlFlow::Continue(())
}
#[inline]
fn step_component(
&mut self,
board: &mut Board,
component_index: usize,
params: &AutoplacerStepParams,
) {
crate::profile_function!();
let component_id = self.components[self.curr_component_index];
let last_cost = self.component_cost(board, component_id);
let translation = self.sample_move(params);
board.move_resolved_components_by(&[component_id], translation);
let new_cost = self.component_cost(board, component_id);
let delta_cost = new_cost - last_cost;
if delta_cost < 0.0
|| rand::rng().random::<f64>()
< f64::exp(-delta_cost / params.component_temperatures[component_index])
{
self.accept_move(board, component_index);
} else {
self.reject_move(board, component_index);
}
}
#[inline]
fn sample_move(&self, params: &AutoplacerStepParams) -> Vector2<i64> {
crate::profile_function!();
let dx_gaussian = Normal::new(0.0, params.std_dev).unwrap();
let dy_gaussian = Normal::new(0.0, params.std_dev).unwrap();
Vector2::new(
dx_gaussian.sample(&mut rand::rng()) as i64,
dy_gaussian.sample(&mut rand::rng()) as i64,
)
}
#[inline]
fn accept_move(&mut self, board: &mut Board, component_index: usize) {
crate::profile_function!();
self.origin_delta = self.origin_delta.clone().merge_deltas(board.flush_delta());
self.component_temperatures[component_index] *= self.schedule.temperature_common_ratio;
self.acceptance_rates[component_index] =
0.998 * self.acceptance_rates[component_index] + 0.002;
}
#[inline]
fn reject_move(&mut self, board: &mut Board, component_index: usize) {
crate::profile_function!();
board.reset_delta();
self.component_temperatures[component_index] *= self.schedule.temperature_common_ratio;
self.acceptance_rates[component_index] = 0.998 * self.acceptance_rates[component_index];
}
pub fn component_cost(&self, board: &Board, component: ComponentId) -> f64 {
crate::profile_function!();
let layout = board.layout();
let repulsion_cost = self.component_repulsion_cost(layout, component);
let attraction_cost = self.component_attraction_cost(layout, component);
let retention_cost = self.component_retention_cost(layout, component);
repulsion_cost + attraction_cost + retention_cost
}
pub fn component_repulsion_cost(&self, layout: &Layout, component: ComponentId) -> f64 {
crate::profile_function!();
layout
.locate_component_repulsions(component, Orientation::Oblique)
.map(|vector| 1000 * (vector.x.abs() + vector.y.abs()))
.sum::<i64>() as f64
}
pub fn component_attraction_cost(&self, layout: &Layout, component: ComponentId) -> f64 {
crate::profile_function!();
layout
.component_attractions(component)
.map(|vector| {
(vector.x.abs().pow(2) as f64 + vector.y.abs().pow(2) as f64)
.sqrt()
.powf(0.5)
})
.sum::<f64>()
}
pub fn component_retention_cost(&self, layout: &Layout, component: ComponentId) -> f64 {
crate::profile_function!();
layout
.component_retentions(component)
.map(|vector| 1000 * (vector.x.abs() + vector.y.abs()))
.sum::<i64>() as f64
}
}