chunkgen 0.2.0

Minecraft world generation library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use std::collections::{BTreeMap, BTreeSet};

use rustc_hash::FxHashMap;

use crate::world::worldgen::feature::PlacedFeature;

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct FeatureData {
    step: usize,
    feature_index: usize,
}

pub struct StepFeatureData {
    pub features: Vec<&'static PlacedFeature>,
    index_mapping: FxHashMap<usize, usize>,
}

impl StepFeatureData {
    fn new(features: Vec<&'static PlacedFeature>) -> Self {
        let index_mapping = features
            .iter()
            .enumerate()
            .map(|(index, feature)| (feature.id, index))
            .collect();
        Self {
            features,
            index_mapping,
        }
    }

    pub fn index_of(&self, feature: &'static PlacedFeature) -> Option<usize> {
        self.index_mapping.get(&feature.id).copied()
    }
}

pub fn build_features_per_step<'f, T>(
    feature_sources: &[T],
    feature_getter: impl Fn(&T) -> &'f [Vec<&'static PlacedFeature>],
) -> Vec<StepFeatureData> {
    let mut feature_index: FxHashMap<usize, usize> = FxHashMap::default();
    let mut features_by_data: FxHashMap<FeatureData, &'static PlacedFeature> = FxHashMap::default();
    let mut next_feature_index = 0;
    let mut edges: BTreeMap<FeatureData, BTreeSet<FeatureData>> = BTreeMap::new();
    let mut max_step = 0;

    for source in feature_sources {
        let mut feature_list = Vec::new();
        let features_for_step = feature_getter(source);
        max_step = max_step.max(features_for_step.len());

        for (step, features) in features_for_step.iter().enumerate() {
            for &feature in features {
                let index = *feature_index.entry(feature.id).or_insert_with(|| {
                    let index = next_feature_index;
                    next_feature_index += 1;
                    index
                });
                let data = FeatureData {
                    step,
                    feature_index: index,
                };
                features_by_data.insert(data, feature);
                feature_list.push(data);
            }
        }

        for index in 0..feature_list.len() {
            let entry = edges.entry(feature_list[index]).or_default();
            if index + 1 < feature_list.len() {
                entry.insert(feature_list[index + 1]);
            }
        }
    }

    let mut discovered: BTreeSet<FeatureData> = BTreeSet::new();
    let mut currently_visiting: BTreeSet<FeatureData> = BTreeSet::new();
    let mut sorted_features: Vec<FeatureData> = Vec::new();

    let keys: Vec<FeatureData> = edges.keys().copied().collect();
    for data in keys {
        if !discovered.contains(&data)
            && depth_first_search(
                &edges,
                &mut discovered,
                &mut currently_visiting,
                &mut sorted_features,
                data,
            )
        {
            panic!("feature order cycle found");
        }
    }

    sorted_features.reverse();

    (0..max_step)
        .map(|step| {
            StepFeatureData::new(
                sorted_features
                    .iter()
                    .filter(|data| data.step == step)
                    .map(|data| features_by_data[data])
                    .collect(),
            )
        })
        .collect()
}

fn depth_first_search(
    edges: &BTreeMap<FeatureData, BTreeSet<FeatureData>>,
    discovered: &mut BTreeSet<FeatureData>,
    currently_visiting: &mut BTreeSet<FeatureData>,
    output: &mut Vec<FeatureData>,
    current: FeatureData,
) -> bool {
    if discovered.contains(&current) {
        return false;
    }
    if !currently_visiting.insert(current) {
        return true;
    }

    if let Some(neighbors) = edges.get(&current) {
        for &neighbor in neighbors {
            if depth_first_search(edges, discovered, currently_visiting, output, neighbor) {
                return true;
            }
        }
    }

    currently_visiting.remove(&current);
    discovered.insert(current);
    output.push(current);
    false
}