Series: Procedural Generation
Terrain Generation part 1: Voronoi noise - September 30, 2023
- Terrain Generation part 2: layering noise functions - October 03, 2023
- Terrain Generation part 3: random continents - October 04, 2023
- Terrain Generation part 4: deriving temperature - October 06, 2023
Terrain Generation part 1: Voronoi noise
I have been playing around with terrain generation using noise functions. Subdividing the world on a cylinder map into regions seems useful. Note that all of this was written around 2am and is the equivalent of napkin doodles.
Stage 1
Creating a set of equidistant points.
And then assigning each pixel (tile) in the world to the “region” which is the nearest point to that tile.
Stage 2
A grid looks too natural, so let’s divide that up by taking the inital points and shifting each one slightly.
Then assigning each pixel (tile) in the world to the “region” which is the nearest point to that tile, using manhattan distance. Note that this is a cylinder world so a region is contiguous from one side to the other horizontally.
Or assigning each pixel (tile) in the world to the “region” which is the nearest point to that tile, using actual distance.
Stage 3
An example of how I’d use this information of world map region division is to create a heightmap where I informally say that every region bordering the north and south poles should be of the lowest height. If using height to place oceans and water for everything below sea level, this guarantees a traversable sea around the entire northern and southern side of the world maps.
Code
/// -------- voronoi.rs --------
use noise::NoiseFn;
use rand::RngCore;
pub struct Voronoi {
pub width: usize,
pub height: usize,
pub tiles_x: usize,
pub tiles_y: usize,
pub variance: usize,
use_manhattan_distance: bool,
}
pub const EMPTY_REGION: usize = 50_000;
impl Voronoi {
pub fn new(width: usize, height: usize) -> Self {
Self {
width,
height,
tiles_x: 8,
tiles_y: 8,
variance: 0,
use_manhattan_distance: true,
}
}
pub fn set_variance(self, variance: usize) -> Self {
Self { variance, ..self }
}
pub fn set_tiles(self, tiles_x: usize, tiles_y: usize) -> Self {
Self {
tiles_x,
tiles_y,
..self
}
}
pub fn use_euclidian(self) -> Self {
Self {
use_manhattan_distance: false,
..self
}
}
fn manhattan_distance(&self, x: isize, y: isize, x1: isize, y2: isize) -> usize {
y.abs_diff(y2) + (x1 + self.width as isize).abs_diff(x).min(x1.abs_diff(x))
}
fn euclidian_distance(&self, x: isize, y: isize, x1: isize, y2: isize) -> usize {
let y_diff = y.abs_diff(y2);
let x_diff = (x1 + self.width as isize).abs_diff(x).min(x1.abs_diff(x));
y_diff.pow(2) + x_diff.pow(2)
}
pub fn generate(&self, mut rng: impl RngCore) -> RegionMap {
self.generate_with_max_distance(rng, 50_000_000)
}
pub fn generate_with_max_distance(
&self,
mut rng: impl RngCore,
max_distance: usize,
) -> RegionMap {
let mut points = Vec::with_capacity(self.tiles_x * self.tiles_y);
let spacing_x = self.width as f64 / self.tiles_x as f64;
let spacing_y = self.height as f64 / self.tiles_y as f64;
let variance = self.variance * 2;
for y in 0..self.tiles_y {
for x in 0..self.tiles_x {
if variance == 0 {
let x = (spacing_x * (x as f64 + 0.5)) as usize;
let y = (spacing_y * (y as f64 + 0.5)) as usize;
points.push([x, y]);
} else {
let x = (spacing_x * (x as f64 + 0.5)) as usize
+ x
+ rng.next_u64() as usize % (variance * 2)
- self.variance;
let y = (spacing_y * (y as f64 + 0.5)) as usize
+ y
+ rng.next_u64() as usize % (variance * 2)
- self.variance;
points.push([x, y]);
}
}
}
let mut assignments = Vec::with_capacity(self.width * self.height);
let mut index = 0;
for h in 0..self.height {
for w in 0..self.width {
let mut region_index = 0;
let mut best_region_index = EMPTY_REGION;
let mut best_region_distance = 500000;
for point in &points {
let distance = if self.use_manhattan_distance {
self.manhattan_distance(
point[0] as isize,
point[1] as isize,
w as isize,
h as isize,
)
} else {
self.euclidian_distance(
point[0] as isize,
point[1] as isize,
w as isize,
h as isize,
)
};
if distance < best_region_distance && distance <= max_distance {
best_region_distance = distance;
best_region_index = region_index;
}
region_index = region_index + 1;
}
assignments.push(best_region_index);
index = index + 1;
}
}
RegionMap {
width: self.width,
height: self.height,
regions: self.tiles_x * self.tiles_y,
assignments,
points,
regions_in_group: Vec::new(),
}
}
}
pub struct RegionMap {
pub width: usize,
pub height: usize,
pub regions: usize,
pub points: Vec<[usize; 2]>,
pub assignments: Vec<usize>,
pub regions_in_group: Vec<usize>,
}
impl RegionMap {
pub fn with_region_group(self, group: Vec<usize>) -> Self {
Self {
regions_in_group: group,
..self
}
}
}
/// 2-dimensional "noise"
impl NoiseFn<usize, 2> for RegionMap {
fn get(&self, point: [usize; 2]) -> f64 {
let index = point[1] * self.width + point[0];
if self.assignments.len() <= index {
0.0
} else if self.regions_in_group.contains(&self.assignments[index]) {
1.0
} else {
0.0
}
}
}/// -------- main.rs --------
mod voronoi;
use crate::voronoi::{Voronoi, EMPTY_REGION};
use image::{ImageBuffer, RgbImage};
use noise::{Billow, MultiFractal, NoiseFn, Perlin, ScalePoint};
use rand::SeedableRng;
fn main() {
let colors = vec![
image::Rgb([255, 0, 0]),
image::Rgb([0, 255, 0]),
image::Rgb([0, 0, 255]),
image::Rgb([255, 255, 0]),
image::Rgb([0, 255, 255]),
image::Rgb([255, 0, 255]),
];
terrain_stage_1(&colors);
terrain_stage_1_points();
terrain_stage_2_points();
terrain_stage_2(&colors);
terrain_stage_2_euclidian(&colors);
terrain_stage_3();
stage4_basic_multi_noise();
}
fn terrain_stage_1(colors: &Vec<image::Rgb<u8>>) {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let rng = rand::rngs::StdRng::seed_from_u64(20);
let region_map = Voronoi::new(width as usize, height as usize).generate(rng);
let mut index = 0;
for h in 0..height {
for w in 0..width {
let region = region_map.assignments[index];
if region != EMPTY_REGION {
let color = colors[region % colors.len()];
img.put_pixel(w, h, color);
}
index = index + 1;
}
}
img.save("stage1.png").unwrap();
}
fn terrain_stage_1_points() {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let rng = rand::rngs::StdRng::seed_from_u64(20);
let region_map =
Voronoi::new(width as usize, height as usize).generate_with_max_distance(rng, 3);
let mut index = 0;
for h in 0..height {
for w in 0..width {
let region = region_map.assignments[index];
if region != EMPTY_REGION {
let color = image::Rgb([255, 255, 255]);
img.put_pixel(w, h, color);
}
index = index + 1;
}
}
img.save("stage1_points.png").unwrap();
}
fn terrain_stage_2_points() {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let rng = rand::rngs::StdRng::seed_from_u64(20);
let region_map = Voronoi::new(width as usize, height as usize)
.set_variance(10)
.generate_with_max_distance(rng, 3);
let mut index = 0;
for h in 0..height {
for w in 0..width {
let region = region_map.assignments[index];
if region != EMPTY_REGION {
let color = image::Rgb([255, 255, 255]);
img.put_pixel(w, h, color);
}
index = index + 1;
}
}
img.save("stage2_points.png").unwrap();
}
fn terrain_stage_2(colors: &Vec<image::Rgb<u8>>) {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let rng = rand::rngs::StdRng::seed_from_u64(20);
let region_map = Voronoi::new(width as usize, height as usize)
.set_variance(10)
.generate(rng);
let mut index = 0;
for h in 0..height {
for w in 0..width {
let region = region_map.assignments[index];
if region != EMPTY_REGION {
let color = colors[region % colors.len()];
img.put_pixel(w, h, color);
}
index = index + 1;
}
}
img.save("stage2.png").unwrap();
}
fn terrain_stage_2_euclidian(colors: &Vec<image::Rgb<u8>>) {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let rng = rand::rngs::StdRng::seed_from_u64(20);
let region_map = Voronoi::new(width as usize, height as usize)
.set_variance(8)
.use_euclidian()
.generate(rng);
let mut index = 0;
for h in 0..height {
for w in 0..width {
let region = region_map.assignments[index];
if region != EMPTY_REGION {
let color = colors[region % colors.len()];
img.put_pixel(w, h, color);
}
index = index + 1;
}
}
img.save("stage2_euclidian.png").unwrap();
}
fn terrain_stage_3() {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let rng = rand::rngs::StdRng::seed_from_u64(20);
let voronoi = Voronoi::new(width as usize, height as usize).set_variance(10);
let region_map = voronoi.generate(rng);
let mut regions_in_group = Vec::new();
for t in 0..voronoi.tiles_x {
regions_in_group.push(t);
regions_in_group.push(t + (voronoi.tiles_y - 1) * voronoi.tiles_x);
}
let region_map = region_map.with_region_group(regions_in_group);
for index in 0..(width * height) {
let w = index % width;
let h = index / width;
let noise = region_map.get([w as usize, h as usize]);
let pixel = ((1.0 - noise) * 255.0).clamp(0.0, 255.0) as u8;
img.put_pixel(w, h, image::Rgb([pixel, pixel, pixel]));
}
img.save("stage3.png").unwrap();
}
// Normalize to [0.0, 1.0]
fn get_and_normalize_scale(noise: impl NoiseFn<f64, 2>, width: usize, height: usize) -> Vec<f64> {
let mut max_value = -50.0;
let mut min_value = 50.0;
let mut noise_array: Vec<f64> = Vec::with_capacity(height * width);
for h in 0..height {
for w in 0..width {
let wf = w as f64 / width as f64;
let hf = h as f64 / height as f64;
let noise = noise.get([wf, hf]);
if noise < min_value {
min_value = noise;
}
if noise > max_value {
max_value = noise;
}
noise_array.push(noise);
}
}
let range_values = max_value - min_value;
noise_array
.iter()
.map(|x| (x - min_value) / range_values)
.collect()
}
fn stage4_basic_multi_noise() {
let mut img: RgbImage = ImageBuffer::new(512, 512);
let (width, height) = img.dimensions();
let basic_multi = ScalePoint::new(Billow::<Perlin>::new(20).set_lacunarity(3.0)).set_scale(3.0);
let noise_array = get_and_normalize_scale(basic_multi, width as usize, height as usize);
let mut index = 0;
for noise in noise_array {
let w = index % width;
let h = index / width;
let pixel = (noise * 255.0).clamp(0.0, 255.0) as u8;
// img.put_pixel(w, h, image::Rgb([pixel, pixel, pixel]));
if pixel < 160 {
img.put_pixel(w, h, image::Rgb([0, 0, 255 - pixel]));
} else {
img.put_pixel(w, h, image::Rgb([30, pixel, 30]));
}
index = index + 1;
}
img.save("stage4.png").unwrap();
}[dependencies]
image = "0.24.7"
noise = "0.8.2"
rand = "0.7.3"Series: Procedural Generation
Terrain Generation part 1: Voronoi noise - September 30, 2023
- Terrain Generation part 2: layering noise functions - October 03, 2023
- Terrain Generation part 3: random continents - October 04, 2023
- Terrain Generation part 4: deriving temperature - October 06, 2023