Struct GraphAnalysis

Source

pub struct GraphAnalysis {
    pub vertex_count: usize,
    pub edge_count: usize,
    pub is_connected: bool,
    pub component_count: usize,
    pub diameter: f32,
    pub average_clustering: f32,
}

Fields§

§vertex_count: usize§edge_count: usize§is_connected: bool§component_count: usize§diameter: f32§average_clustering: f32

Implementations§

Source §

impl GraphAnalysis

Source

pub fn analyze(graph: &Graph) -> Self

Examples found in repository ?

examples/delaunay_connections.rs (line 66)

11fn main() {
12    println!("=== Delaunay Triangulation Demo ===\n");
13
14    // Step 1: Generate base dungeon with rooms
15    println!("1. Generating Base Dungeon:");
16    let mut grid = Grid::new(40, 30);
17    let bsp = Bsp::default();
18    bsp.generate(&mut grid, 42424);
19
20    let room_count = count_rooms(&grid);
21    println!(
22        "   Generated {}x{} dungeon with ~{} rooms",
23        grid.width(),
24        grid.height(),
25        room_count
26    );
27
28    // Step 2: Find room centers
29    println!("\n2. Identifying Room Centers:");
30    let room_centers = find_room_centers(&grid);
31    println!("   Found {} room centers:", room_centers.len());
32    for (i, center) in room_centers.iter().enumerate() {
33        println!("     Room {}: ({:.1}, {:.1})", i + 1, center.x, center.y);
34    }
35
36    // Step 3: Create Delaunay triangulation
37    println!("\n3. Creating Delaunay Triangulation:");
38    let triangulation = DelaunayTriangulation::new(room_centers.clone());
39
40    println!("   Triangulation results:");
41    println!("     Vertices: {}", triangulation.points.len());
42    println!("     Triangles: {}", triangulation.triangles.len());
43    println!("     Edges: {}", triangulation.edges.len());
44
45    // Step 4: Generate minimum spanning tree
46    println!("\n4. Generating Minimum Spanning Tree:");
47    let mst_edges = triangulation.minimum_spanning_tree();
48
49    println!("   MST results:");
50    println!("     Edges: {}", mst_edges.len());
51    println!(
52        "     Expected for {} rooms: {}",
53        room_centers.len(),
54        room_centers.len().saturating_sub(1)
55    );
56
57    let total_length: f32 = mst_edges
58        .iter()
59        .map(|edge| edge.length(&triangulation.points))
60        .sum();
61    println!("     Total length: {:.1}", total_length);
62
63    // Step 5: Graph analysis
64    println!("\n5. Graph Analysis:");
65    let graph = Graph::new(triangulation.points.clone(), mst_edges.clone());
66    let analysis = GraphAnalysis::analyze(&graph);
67
68    println!("   Connectivity analysis:");
69    println!("     Connected: {}", analysis.is_connected);
70    println!("     Components: {}", analysis.component_count);
71    println!("     Diameter: {:.1}", analysis.diameter);
72    println!("     Avg clustering: {:.3}", analysis.average_clustering);
73
74    // Step 6: Compare with full triangulation
75    println!("\n6. Comparison: MST vs Full Triangulation:");
76    let full_graph = Graph::new(triangulation.points.clone(), triangulation.edges.clone());
77    let full_analysis = GraphAnalysis::analyze(&full_graph);
78
79    println!("   Full triangulation:");
80    println!("     Edges: {}", full_analysis.edge_count);
81    println!("     Diameter: {:.1}", full_analysis.diameter);
82    println!(
83        "     Avg clustering: {:.3}",
84        full_analysis.average_clustering
85    );
86
87    println!("   MST (optimized):");
88    println!("     Edges: {}", analysis.edge_count);
89    println!("     Diameter: {:.1}", analysis.diameter);
90    println!("     Avg clustering: {:.3}", analysis.average_clustering);
91
92    // Step 7: Pathfinding example
93    println!("\n7. Pathfinding Example:");
94    if room_centers.len() >= 2 {
95        let start = 0;
96        let end = room_centers.len() - 1;
97
98        if let Some(path) = graph.shortest_path(start, end) {
99            println!("   Path from room {} to room {}:", start + 1, end + 1);
100            print!("     Route: ");
101            for (i, &room) in path.iter().enumerate() {
102                if i > 0 {
103                    print!(" -> ");
104                }
105                print!("Room {}", room + 1);
106            }
107            println!();
108
109            let mut path_length = 0.0;
110            for i in 0..(path.len() - 1) {
111                path_length += room_centers[path[i]].distance_to(&room_centers[path[i + 1]]);
112            }
113            println!("     Total distance: {:.1}", path_length);
114        } else {
115            println!("   No path found between rooms");
116        }
117    }
118
119    // Step 8: Performance analysis
120    println!("\n8. Performance Analysis:");
121    let start = std::time::Instant::now();
122    let _ = DelaunayTriangulation::new(room_centers.clone());
123    println!("   Triangulation time: {:?}", start.elapsed());
124
125    let start = std::time::Instant::now();
126    let _ = triangulation.minimum_spanning_tree();
127    println!("   MST generation time: {:?}", start.elapsed());
128
129    println!("\n✅ Delaunay triangulation demo complete!");
130    println!("   - Natural room connections via triangulation");
131    println!("   - Optimal corridor networks with MST");
132    println!("   - Graph analysis for connectivity insights");
133}

More examples

Hide additional examples

examples/phase4_workflow.rs (line 81)

14fn main() {
15    println!("=== Phase 4 Complete Workflow Demo ===\n");
16
17    // Step 1: Generate base layout with BSP
18    println!("1. Generating Base Layout:");
19    let mut base_grid = Grid::new(35, 25);
20    let bsp = Bsp::default();
21    bsp.generate(&mut base_grid, 12345);
22
23    let base_floors = base_grid.count(|t| t.is_floor());
24    println!(
25        "   Generated {}x{} base layout with {} floors",
26        base_grid.width(),
27        base_grid.height(),
28        base_floors
29    );
30
31    // Step 2: Learn patterns from base layout
32    println!("\n2. Learning Patterns from Base Layout:");
33    let learned_patterns = WfcPatternExtractor::extract_patterns(&base_grid, 3);
34    println!(
35        "   Extracted {} unique 3x3 patterns",
36        learned_patterns.len()
37    );
38
39    // Step 3: Generate enhanced areas with WFC
40    println!("\n3. Generating Enhanced Areas with Learned Patterns:");
41    let mut wfc_grid = Grid::new(20, 15);
42    let wfc = Wfc::new(WfcConfig {
43        floor_weight: 0.45,
44        pattern_size: 3,
45        enable_backtracking: true,
46    });
47    wfc.generate_with_patterns(&mut wfc_grid, learned_patterns.clone(), 54321);
48
49    let wfc_floors = wfc_grid.count(|t| t.is_floor());
50    println!(
51        "   WFC generated {} floors with learned patterns",
52        wfc_floors
53    );
54
55    // Step 4: Find room centers for connectivity analysis
56    println!("\n4. Analyzing Room Connectivity:");
57    let room_centers = find_room_centers(&base_grid);
58    println!("   Identified {} room centers", room_centers.len());
59
60    // Step 5: Create optimal connections with Delaunay + MST
61    println!("\n5. Creating Optimal Room Connections:");
62    if room_centers.len() >= 3 {
63        let triangulation = DelaunayTriangulation::new(room_centers.clone());
64        let mst_edges = triangulation.minimum_spanning_tree();
65
66        println!("   Delaunay triangulation:");
67        println!("     Triangles: {}", triangulation.triangles.len());
68        println!("     All edges: {}", triangulation.edges.len());
69
70        println!("   Minimum spanning tree:");
71        println!("     Optimal edges: {}", mst_edges.len());
72
73        let total_length: f32 = mst_edges
74            .iter()
75            .map(|edge| edge.length(&triangulation.points))
76            .sum();
77        println!("     Total corridor length: {:.1}", total_length);
78
79        // Graph analysis
80        let graph = Graph::new(triangulation.points.clone(), mst_edges);
81        let analysis = GraphAnalysis::analyze(&graph);
82
83        println!("   Connectivity analysis:");
84        println!("     Connected: {}", analysis.is_connected);
85        println!("     Diameter: {:.1}", analysis.diameter);
86        println!("     Clustering: {:.3}", analysis.average_clustering);
87    } else {
88        println!("   Not enough rooms for connectivity analysis");
89    }
90
91    // Step 6: Create specialized prefab library
92    println!("\n6. Creating Specialized Prefab Library:");
93    let library = create_specialized_library();
94
95    println!(
96        "   Created library with {} prefabs:",
97        library.get_prefabs().len()
98    );
99    for prefab in library.get_prefabs() {
100        println!(
101            "     - {} (weight: {:.1}, tags: {:?})",
102            prefab.name, prefab.weight, prefab.tags
103        );
104    }
105
106    // Step 7: Place special features with advanced prefabs
107    println!("\n7. Placing Special Features:");
108    let mut feature_grid = Grid::new(30, 20);
109
110    // Place boss rooms (rare, large)
111    let boss_config = PrefabConfig {
112        max_prefabs: 1,
113        min_spacing: 8,
114        allow_rotation: false,
115        allow_mirroring: false,
116        weighted_selection: true,
117        placement_mode: terrain_forge::algorithms::PrefabPlacementMode::Overwrite,
118        tags: None,
119    };
120
121    let boss_placer = PrefabPlacer::new(boss_config, library.clone());
122    boss_placer.generate(&mut feature_grid, 98765);
123
124    // Place treasure rooms (medium rarity)
125    let treasure_config = PrefabConfig {
126        max_prefabs: 2,
127        min_spacing: 5,
128        allow_rotation: true,
129        allow_mirroring: true,
130        weighted_selection: true,
131        placement_mode: terrain_forge::algorithms::PrefabPlacementMode::Overwrite,
132        tags: None,
133    };
134
135    let treasure_placer = PrefabPlacer::new(treasure_config, library.clone());
136    treasure_placer.generate(&mut feature_grid, 13579);
137
138    let feature_floors = feature_grid.count(|t| t.is_floor());
139    println!("   Placed special features: {} floor tiles", feature_floors);
140
141    // Step 8: Performance and quality metrics
142    println!("\n8. Performance and Quality Metrics:");
143
144    // WFC performance
145    let start = std::time::Instant::now();
146    let mut perf_grid = Grid::new(25, 20);
147    wfc.generate_with_patterns(&mut perf_grid, learned_patterns.clone(), 24680);
148    let wfc_time = start.elapsed();
149
150    // Prefab performance
151    let start = std::time::Instant::now();
152    let placer = PrefabPlacer::new(PrefabConfig::default(), library.clone());
153    let mut prefab_grid = Grid::new(25, 20);
154    placer.generate(&mut prefab_grid, 24680);
155    let prefab_time = start.elapsed();
156
157    // Delaunay performance
158    let start = std::time::Instant::now();
159    let _ = DelaunayTriangulation::new(room_centers.clone());
160    let delaunay_time = start.elapsed();
161
162    println!("   Performance metrics:");
163    println!("     WFC generation: {:?}", wfc_time);
164    println!("     Prefab placement: {:?}", prefab_time);
165    println!("     Delaunay triangulation: {:?}", delaunay_time);
166
167    // Step 9: Quality comparison
168    println!("\n9. Quality Comparison:");
169
170    // Basic generation
171    let mut basic_grid = Grid::new(25, 20);
172    bsp.generate(&mut basic_grid, 11111);
173    let basic_floors = basic_grid.count(|t| t.is_floor());
174
175    // Enhanced generation (WFC + prefabs)
176    let enhanced_floors = perf_grid.count(|t| t.is_floor()) + prefab_grid.count(|t| t.is_floor());
177
178    println!("   Floor tile comparison:");
179    println!(
180        "     Basic BSP: {} floors ({:.1}%)",
181        basic_floors,
182        100.0 * basic_floors as f32 / (25 * 20) as f32
183    );
184    println!(
185        "     Enhanced (WFC + Prefabs): {} floors ({:.1}%)",
186        enhanced_floors,
187        100.0 * enhanced_floors as f32 / (50 * 20) as f32
188    );
189
190    // Step 10: Save configuration for reuse
191    println!("\n10. Saving Configuration:");
192    match library.save_to_json("phase4_library.json") {
193        Ok(()) => println!("   ✅ Saved prefab library to phase4_library.json"),
194        Err(e) => println!("   ❌ Failed to save library: {}", e),
195    }
196
197    println!("\n✅ Phase 4 complete workflow finished!");
198    println!("   Workflow summary:");
199    println!("   1. Generated base layout with BSP algorithm");
200    println!(
201        "   2. Learned {} patterns for WFC enhancement",
202        learned_patterns.len()
203    );
204    println!(
205        "   3. Analyzed {} room connections with Delaunay triangulation",
206        room_centers.len()
207    );
208    println!("   4. Placed specialized features with weighted prefab selection");
209    println!("   5. Achieved optimal room connectivity with MST");
210    println!("   6. Demonstrated pattern learning and constraint propagation");
211    println!("   \n   Phase 4 features enable:");
212    println!("   - Intelligent pattern-based generation");
213    println!("   - Mathematically optimal room connections");
214    println!("   - Flexible, reusable prefab systems");
215    println!("   - Advanced graph analysis for level design");
216}