--- a/rust/landgen/Cargo.toml Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/Cargo.toml Sat Jan 18 16:57:26 2025 +0100
@@ -8,8 +8,9 @@
integral-geometry = { path = "../integral-geometry" }
land2d = { path = "../land2d" }
vec2d = { path = "../vec2d" }
-itertools = "0.13"
+itertools = "0.14"
png = "0.17"
+rand = "0.8"
[dev-dependencies]
criterion = "0.5"
--- a/rust/landgen/benches/benchmark.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/benches/benchmark.rs Sat Jan 18 16:57:26 2025 +0100
@@ -1,57 +1,53 @@
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use integral_geometry::{Point, Rect, Size};
use landgen;
-use landgen::{LandGenerationParameters, LandGenerator};
use landgen::outline_template_based::outline_template::OutlineTemplate;
use landgen::outline_template_based::template_based::TemplatedLandGenerator;
+use landgen::{LandGenerationParameters, LandGenerator};
pub fn generate_outline(c: &mut Criterion) {
let template = OutlineTemplate {
- islands: vec![
- vec![
- Rect::from_box(273, 273, 2048, 2048),
- Rect::from_box(683, 683, 32, 63),
- Rect::from_box(1092, 1092, 2048, 2048),
- ],
- vec![
- Rect::from_box(1638, 1638, 2048, 2048),
- Rect::from_box(2048, 2048, 32, 63),
- Rect::from_box(2458, 2458, 2048, 2048),
- ],
- vec![
- Rect::from_box(3004, 3004, 2048, 2048),
- Rect::from_box(3413, 3413, 32, 63),
- Rect::from_box(3823, 3823, 2048, 2048),
+ islands: vec![
+ vec![
+ Rect::from_box(273, 273, 2048, 2048),
+ Rect::from_box(683, 683, 32, 63),
+ Rect::from_box(1092, 1092, 2048, 2048),
+ ],
+ vec![
+ Rect::from_box(1638, 1638, 2048, 2048),
+ Rect::from_box(2048, 2048, 32, 63),
+ Rect::from_box(2458, 2458, 2048, 2048),
+ ],
+ vec![
+ Rect::from_box(3004, 3004, 2048, 2048),
+ Rect::from_box(3413, 3413, 32, 63),
+ Rect::from_box(3823, 3823, 2048, 2048),
+ ],
],
- ],
- walls: vec![],
- fill_points: vec![Point::new(1, 0)],
- size: Size {
- width: 4096,
- height: 2048,
- },
- can_flip: false,
- can_invert: false,
- can_mirror: false,
- is_negative: false,
-};
+ walls: vec![],
+ fill_points: vec![Point::new(1, 0)],
+ size: Size {
+ width: 4096,
+ height: 2048,
+ },
+ can_flip: false,
+ can_invert: false,
+ can_mirror: false,
+ is_negative: false,
+ };
- let parameters = LandGenerationParameters::new(
- 0u16,
- 32768u16,
- 10,
- false,
- false
- );
+ let parameters = LandGenerationParameters::new(0u16, 32768u16, 10, false, false);
- c.bench_function("outline_generation", |b| b.iter(|| {
- fn prng() -> impl Iterator<Item = u32> {
- (0..).map(|i| (i as u64 * 31_234_773 % 2_017_234_567) as u32)
- }
+ c.bench_function("outline_generation", |b| {
+ b.iter(|| {
+ fn prng() -> impl Iterator<Item = u32> {
+ (0..).map(|i| (i as u64 * 31_234_773 % 2_017_234_567) as u32)
+ }
- let gen = TemplatedLandGenerator::new(black_box(template.clone()));
- gen.generate_land(black_box(¶meters), &mut prng())
- }));
+ let gen = TemplatedLandGenerator::new(black_box(template.clone()));
+ gen.generate_land(black_box(¶meters), &mut prng())
+ })
+ });
}
criterion_group!(benches, generate_outline);
--- a/rust/landgen/src/lib.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/src/lib.rs Sat Jan 18 16:57:26 2025 +0100
@@ -1,3 +1,5 @@
+use rand::Rng;
+
pub mod maze;
pub mod outline_template_based;
pub mod wavefront_collapse;
@@ -38,9 +40,9 @@
}
pub trait LandGenerator {
- fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
+ fn generate_land<T: Copy + PartialEq + Default>(
&self,
parameters: &LandGenerationParameters<T>,
- random_numbers: &mut I,
+ prng: &mut impl Rng,
) -> land2d::Land2D<T>;
}
--- a/rust/landgen/src/maze.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/src/maze.rs Sat Jan 18 16:57:26 2025 +0100
@@ -2,6 +2,7 @@
use crate::{LandGenerationParameters, LandGenerator};
use integral_geometry::{Point, Polygon, Rect, Size};
use land2d::Land2D;
+use rand::Rng;
#[derive(Clone)]
pub struct MazeTemplate {
@@ -77,13 +78,13 @@
}
impl Maze {
- pub fn new<I: Iterator<Item = u32>>(
+ pub fn new(
size: &Size,
cell_size: usize,
num_steps: usize,
inverted: bool,
braidness: u32,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> Self {
let num_cells = Size::new(
prev_odd(size.width / cell_size),
@@ -102,11 +103,10 @@
let edge_list = vec![vec![vec![false; num_cells.width]; num_cells.height]; 2];
for current_step in 0..num_steps {
- let x = random_numbers.next().unwrap_or_default() as usize % (seen_cells.width - 1)
- / num_steps;
+ let x = random_numbers.gen_range(0..seen_cells.width - 1) / num_steps;
last_cell[current_step] = Point::new(
(x + current_step * seen_cells.width / num_steps) as i32,
- random_numbers.next().unwrap_or_default() as i32 % seen_cells.height as i32,
+ random_numbers.gen_range(0..seen_cells.height) as i32,
);
}
@@ -130,18 +130,18 @@
}
}
- fn see_cell<I: Iterator<Item = u32>>(
+ fn see_cell(
&mut self,
current_step: usize,
start_dir: Direction,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> bool {
let mut dir = start_dir;
loop {
let p = self.last_cell[current_step];
self.seen_list[p.y as usize][p.x as usize] = Some(current_step);
- let next_dir_clockwise = random_numbers.next().unwrap_or_default() % 2 == 0;
+ let next_dir_clockwise = random_numbers.gen();
for _ in 0..5 {
let sp = p + dir.0;
@@ -158,9 +158,7 @@
match when_seen {
Some(a) if a == current_step => {
// try another direction
- if !self.inverted
- && random_numbers.next().unwrap_or_default() % self.braidness == 0
- {
+ if !self.inverted && random_numbers.gen_range(0..self.braidness) == 0 {
if dir.0.x == -1 && p.x > 0 {
self.walls[dir.orientation()][p.y as usize][p.x as usize - 1] =
false;
@@ -386,12 +384,12 @@
Self { maze_template }
}
- fn generate_outline<I: Iterator<Item = u32>>(
+ fn generate_outline(
&self,
size: &Size,
play_box: Rect,
intersections_box: Rect,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> OutlinePoints {
let num_steps = if self.maze_template.inverted { 3 } else { 1 };
let mut step_done = vec![false; num_steps];
@@ -411,7 +409,7 @@
for current_step in 0..num_steps {
if !step_done[current_step] {
- let dir = Direction::new(random_numbers.next().unwrap_or_default() as usize);
+ let dir = Direction::new(random_numbers.gen());
step_done[current_step] = maze.see_cell(current_step, dir, random_numbers);
done = false;
}
@@ -432,10 +430,10 @@
}
impl LandGenerator for MazeLandGenerator {
- fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
+ fn generate_land<T: Copy + PartialEq + Default>(
&self,
parameters: &LandGenerationParameters<T>,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> Land2D<T> {
let do_invert = self.maze_template.inverted;
let (basic, zero) = if do_invert {
--- a/rust/landgen/src/outline_template_based/outline.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/src/outline_template_based/outline.rs Sat Jan 18 16:57:26 2025 +0100
@@ -1,10 +1,9 @@
-use itertools::Itertools;
use std::cmp::min;
+use super::outline_template::OutlineTemplate;
use integral_geometry::{Line, Point, Polygon, Ray, Rect, Size};
use land2d::Land2D;
-
-use super::outline_template::OutlineTemplate;
+use rand::Rng;
pub struct OutlinePoints {
pub islands: Vec<Polygon>,
@@ -16,41 +15,32 @@
}
impl OutlinePoints {
- pub fn from_outline_template<I: Iterator<Item = u32>>(
+ pub fn from_outline_template(
outline_template: &OutlineTemplate,
play_box: Rect,
size: Size,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> Self {
- Self {
- play_box,
- size,
- islands: outline_template
- .islands
+ let mut fix_polygons = |polygons: &[Vec<Rect>]| -> Vec<Polygon> {
+ polygons
.iter()
.map(|i| {
i.iter()
- .zip(random_numbers.tuples())
- .map(|(rect, (rnd_a, rnd_b))| {
- play_box.top_left() + rect.quotient(rnd_a as usize, rnd_b as usize)
+ .map(|rect| {
+ let (rnd_a, rnd_b) = random_numbers.gen();
+ play_box.top_left() + rect.quotient(rnd_a, rnd_b)
})
.collect::<Vec<_>>()
.into()
})
- .collect(),
- walls: outline_template
- .walls
- .iter()
- .map(|i| {
- i.iter()
- .zip(random_numbers.tuples())
- .map(|(rect, (rnd_a, rnd_b))| {
- play_box.top_left() + rect.quotient(rnd_a as usize, rnd_b as usize)
- })
- .collect::<Vec<_>>()
- .into()
- })
- .collect(),
+ .collect()
+ };
+
+ Self {
+ play_box,
+ size,
+ islands: fix_polygons(&outline_template.islands),
+ walls: fix_polygons(&outline_template.walls),
fill_points: outline_template.fill_points.clone(),
intersections_box: Rect::at_origin(size)
.with_margin(size.to_square().width as i32 * -2),
@@ -77,12 +67,12 @@
.chain(self.fill_points.iter_mut())
}
- fn divide_edge<I: Iterator<Item = u32>>(
+ fn divide_edge(
&self,
segment: Line,
distance_divisor: u32,
distortion_limiting_factor: u32,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> Option<Point> {
#[inline]
fn intersects(ray: &Ray, edge: &Line) -> bool {
@@ -251,20 +241,18 @@
Some(mid_point)
} else {
// select distance within [-dist_right; dist_left], keeping min_distance in mind
- let d = -(dist_right as i32)
- + min_distance
- + random_numbers.next().unwrap() as i32
- % (dist_right as i32 + dist_left as i32 - min_distance * 2);
+ let d = random_numbers
+ .gen_range(-(dist_right as i32) + min_distance..=dist_left as i32 - min_distance);
Some(mid_point + normal * d / normal_len as i32)
}
}
- fn divide_edges<I: Iterator<Item = u32>>(
+ fn divide_edges(
&mut self,
distance_divisor: u32,
distortion_limiting_factor: u32,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) {
for is in 0..self.islands.len() {
let mut i = 0;
@@ -291,11 +279,11 @@
}
}
- pub fn distort<I: Iterator<Item = u32>>(
+ pub fn distort(
&mut self,
distance_divisor: u32,
distortion_limiting_factor: u32,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) {
loop {
let old_len = self.total_len();
@@ -314,9 +302,7 @@
}
fn visible_segments_iter<'a>(&'a self) -> impl Iterator<Item = Line> + 'a {
- self.islands
- .iter()
- .flat_map(|p| p.iter_edges())
+ self.islands.iter().flat_map(|p| p.iter_edges())
}
fn segments_iter<'a>(&'a self) -> impl Iterator<Item = Line> + 'a {
--- a/rust/landgen/src/outline_template_based/template_based.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/src/outline_template_based/template_based.rs Sat Jan 18 16:57:26 2025 +0100
@@ -1,6 +1,7 @@
use super::{outline::OutlinePoints, outline_template::OutlineTemplate};
use crate::{LandGenerationParameters, LandGenerator};
use land2d::Land2D;
+use rand::Rng;
pub struct TemplatedLandGenerator {
outline_template: OutlineTemplate,
@@ -13,13 +14,13 @@
}
impl LandGenerator for TemplatedLandGenerator {
- fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
+ fn generate_land<T: Copy + PartialEq + Default>(
&self,
parameters: &LandGenerationParameters<T>,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> Land2D<T> {
let do_invert = self.outline_template.is_negative
- && (!self.outline_template.can_invert || random_numbers.next().unwrap() & 1 == 0);
+ && (!self.outline_template.can_invert || random_numbers.gen());
let (basic, zero) = if do_invert {
(parameters.zero, parameters.basic)
} else {
@@ -36,25 +37,17 @@
);
// mirror
- if self.outline_template.can_mirror {
- if let Some(b) = random_numbers.next() {
- if b & 1 != 0 {
- points.mirror();
- }
- }
+ if self.outline_template.can_mirror && random_numbers.gen() {
+ points.mirror();
}
// flip
- if self.outline_template.can_flip {
- if let Some(b) = random_numbers.next() {
- if b & 1 != 0 {
- points.flip();
- }
- }
+ if self.outline_template.can_flip && random_numbers.gen() {
+ points.flip();
}
if !parameters.skip_distort {
- let distortion_limiting_factor = 100 + random_numbers.next().unwrap() % 8 * 10;
+ let distortion_limiting_factor = 100 + random_numbers.gen_range(0..8) * 10;
points.distort(
parameters.distance_divisor,
--- a/rust/landgen/src/wavefront_collapse/generator.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/src/wavefront_collapse/generator.rs Sat Jan 18 16:57:26 2025 +0100
@@ -3,6 +3,7 @@
use crate::{LandGenerationParameters, LandGenerator};
use integral_geometry::Size;
use png::Decoder;
+use rand::Rng;
use std::collections::HashSet;
use std::fs::File;
use std::io::{BufReader, Result};
@@ -179,6 +180,7 @@
pub fn build_rules<T: Copy + PartialEq + Default>(
&self,
tiles: &[TileImage<T, String>],
+ probability_distribution_factor: i32,
) -> Vec<CollapseRule> {
let [grid_top_edge, grid_right_edge, grid_bottom_edge, grid_left_edge]: [Option<
Edge<String>,
@@ -263,7 +265,12 @@
}
}
+ let weight = (probability_distribution_factor * 2 * i as i32 / (tiles.len() - 1) as i32
+ + 100
+ - probability_distribution_factor) as u32;
+
rules.push(CollapseRule {
+ weight,
tile: Tile::Numbered(i),
top,
right,
@@ -277,13 +284,17 @@
}
impl LandGenerator for WavefrontCollapseLandGenerator {
- fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
+ fn generate_land<T: Copy + PartialEq + Default>(
&self,
parameters: &LandGenerationParameters<T>,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) -> land2d::Land2D<T> {
+ assert!(parameters.distance_divisor >= 1);
+ assert!(parameters.distance_divisor <= 25);
+
let tiles = self.load_template(parameters);
- let rules = self.build_rules(&tiles);
+ let distribution_factor = (parameters.distance_divisor - 1) as i32 * 8 - 96;
+ let rules = self.build_rules(&tiles, distribution_factor);
let mut wfc = WavefrontCollapse::new(self.template.wrap);
wfc.set_rules(rules);
--- a/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs Sat Jan 18 16:57:26 2025 +0100
@@ -1,4 +1,7 @@
use integral_geometry::Size;
+use rand::distributions::Distribution;
+use rand::distributions::WeightedIndex;
+use rand::Rng;
use std::collections::HashSet;
use vec2d::Vec2D;
@@ -17,6 +20,7 @@
#[derive(Debug)]
pub struct CollapseRule {
+ pub weight: u32,
pub tile: Tile,
pub right: HashSet<Tile>,
pub bottom: HashSet<Tile>,
@@ -49,11 +53,11 @@
}
}
- pub fn generate_map<I: Iterator<Item = u32>, F: FnOnce(&mut Vec2D<Tile>)>(
+ pub fn generate_map<F: FnOnce(&mut Vec2D<Tile>)>(
&mut self,
map_size: &Size,
seed_fn: F,
- random_numbers: &mut I,
+ random_numbers: &mut impl Rng,
) {
self.grid = Vec2D::new(map_size, Tile::Empty);
@@ -82,7 +86,7 @@
self.grid.get(y, x).copied().unwrap_or_default()
}
- fn collapse_step<I: Iterator<Item = u32>>(&mut self, random_numbers: &mut I) -> bool {
+ fn collapse_step(&mut self, random_numbers: &mut impl Rng) -> bool {
let mut tiles_to_collapse = (usize::max_value(), Vec::new());
// Iterate through the tiles in the land
@@ -97,7 +101,7 @@
let left_tile = self.get_tile(y, x.wrapping_sub(1));
let top_tile = self.get_tile(y.wrapping_sub(1), x);
- let possibilities: Vec<Tile> = self
+ let possibilities: Vec<(u32, Tile)> = self
.rules
.iter()
.filter_map(|rule| {
@@ -106,7 +110,7 @@
&& rule.left.contains(&left_tile)
&& rule.top.contains(&top_tile)
{
- Some(rule.tile)
+ Some((rule.weight, rule.tile))
} else {
None
}
@@ -116,12 +120,10 @@
let entropy = possibilities.len();
if entropy > 0 {
if entropy <= tiles_to_collapse.0 {
- let entry = (
- y,
- x,
- possibilities
- [random_numbers.next().unwrap_or_default() as usize % entropy],
- );
+ let weights = possibilities.iter().map(|(weight, _)| *weight);
+ let distribution = WeightedIndex::new(weights).unwrap();
+
+ let entry = (y, x, possibilities[distribution.sample(random_numbers)]);
if entropy < tiles_to_collapse.0 {
tiles_to_collapse = (entropy, vec![entry])
@@ -147,8 +149,10 @@
let possibilities_number = tiles_to_collapse.len();
if possibilities_number > 0 {
- let (y, x, tile) = tiles_to_collapse
- [random_numbers.next().unwrap_or_default() as usize % possibilities_number];
+ let weights = tiles_to_collapse.iter().map(|(_, _, (weight, _))| *weight);
+ let distribution = WeightedIndex::new(weights).unwrap();
+
+ let (y, x, (_, tile)) = tiles_to_collapse[distribution.sample(random_numbers)];
*self
.grid
--- a/rust/lib-hwengine-future/src/lib.rs Sat Jan 18 16:55:04 2025 +0100
+++ b/rust/lib-hwengine-future/src/lib.rs Sat Jan 18 16:57:26 2025 +0100
@@ -108,8 +108,7 @@
let mut map_gen = MapGenerator::<WfcTemplate>::new(data_path);
map_gen.import_yaml_templates(&yaml_templates);
- let distance_divisor = feature_size.pow(2) / 8 + 10;
- let params = LandGenerationParameters::new(0u16, 0x8000u16, distance_divisor, false, false);
+ let params = LandGenerationParameters::new(0u16, 0x8000u16, feature_size, false, false);
let template = map_gen
.get_template(template_type, &mut random_numbers_gen)
.expect("Error reading wfc templates file")