Hello, fellow Rustaceans,
I'm reaching out to explore insights and advice on enhancing the performance of platform systems, particularly in the context of pathfinding algorithms like A* (A Star) and BFS (Breadth-First Search). I'm currently working with a platform system (link provided below), which operates efficiently under conventional search parameters. However, the performance drops significantly when I employ pathfinding algorithms, and I find myself in need of a more optimized solution.
To address this, I experimented with the R* algorithm, but unfortunately, it didn't offer any improvement over my existing setup. Given the voluminous data managed by this system, an efficient implementation is crucial, especially for cell management and dynamic resizing.
I've also considered integrating an octree approach, yet I'm struggling with its proper implementation and remain uncertain about its potential benefits for my case.
Could anyone share their experiences or suggestions on how to tackle these challenges? I'm particularly interested in any advice on implementing these algorithms more effectively or any alternative strategies that could enhance the system's performance for pathfinding tasks.
#![allow(dead_code, unused_imports)]
use {
ahash::AHashMap,
deepsize::{Context, DeepSizeOf},
std::{
fs::File,
io::{self, BufReader, Read},
path::Path,
time::Instant
}
};
#[derive(Copy, Clone, Debug, Hash, Eq, PartialEq)]
struct Point3D {
x: i32,
y: i32,
z: i32
}
impl DeepSizeOf for Point3D {
fn deep_size_of_children(&self, _context: &mut Context) -> usize {
}
}
#[derive(Debug, Clone, Hash, Eq, PartialEq)]
struct Platform {
minx: i32,
maxx: i32,
miny: i32,
maxy: i32,
minz: i32,
maxz: i32,
name: String
}
impl DeepSizeOf for Platform {
fn deep_size_of_children(&self, context: &mut Context) -> usize {
self.name.deep_size_of_children(context)
}
}
struct SpatialHashMap {
grid: AHashMap<Point3D, Vec<Platform>>,
cell_size: i32
}
impl SpatialHashMap {
fn add_platform(&mut self, platform: Platform) {
let start_cell_x = platform.minx / self.cell_size;
let end_cell_x = platform.maxx / self.cell_size;
let start_cell_y = platform.miny / self.cell_size;
let end_cell_y = platform.maxy / self.cell_size;
let start_cell_z = platform.minz / self.cell_size;
let end_cell_z = platform.maxz / self.cell_size;
for x in start_cell_x..=end_cell_x {
for y in start_cell_y..=end_cell_y {
for z in start_cell_z..=end_cell_z {
let cell_key = Point3D { x, y, z };
self
.grid
.entry(cell_key)
.or_default()
.push(platform.clone());
}
}
}
}
fn remove_platform(
&mut self,
minx: i32,
maxx: i32,
miny: i32,
maxy: i32,
minz: i32,
maxz: i32,
name: String
) {
let start_cell_x = minx / self.cell_size;
let end_cell_x = maxx / self.cell_size;
let start_cell_y = miny / self.cell_size;
let end_cell_y = maxy / self.cell_size;
let start_cell_z = minz / self.cell_size;
let end_cell_z = maxz / self.cell_size;
for x in start_cell_x..=end_cell_x {
for y in start_cell_y..=end_cell_y {
for z in start_cell_z..=end_cell_z {
let cell_key = Point3D { x, y, z };
if let Some(platforms) = self.grid.get_mut(&cell_key) {
platforms.retain(|platform| {
// Check if the platform matches the one to be removed
platform.minx != minx
|| platform.maxx != maxx
|| platform.miny != miny
|| platform.maxy != maxy
|| platform.minz != minz
|| platform.maxz != maxz
|| platform.name != name
});
if platforms.is_empty() {
self.grid.remove(&cell_key);
}
}
}
}
}
}
fn find_latest_platform_at(&self, point: Point3D) -> Option<&Platform> {
let cell_key = Point3D {
x: point.x / self.cell_size,
y: point.y / self.cell_size,
z: point.z / self.cell_size
};
if let Some(platforms) = self.grid.get(&cell_key) {
for platform in platforms.iter().rev() {
if point.x >= platform.minx
&& point.x <= platform.maxx
&& point.y >= platform.miny
&& point.y <= platform.maxy
&& point.z >= platform.minz
&& point.z <= platform.maxz
{
return Some(platform);
}
}
}
None
}
fn new(cell_size: i32) -> Self {
Self {
grid: AHashMap::new(),
cell_size
}
}
}
fn load_map_from_file(file_path: &str) -> io::Result<SpatialHashMap> {
let path = Path::new(file_path);
let file = File::open(path)?;
let mut reader = BufReader::new(file);
let mut spatial_hashmap = SpatialHashMap::new(90);
let mut content = String::new();
reader.read_to_string(&mut content)?;
let lines = content.split('\r').collect::<Vec<_>>();
for line in lines {
if line.starts_with("tile:") {
let parts: Vec<&str> = line["tile:".len()..].split(':').collect();
if parts.len() == 7 {
let minx = parts[0].parse::<i32>().unwrap();
let maxx = parts[1].parse::<i32>().unwrap();
let miny = parts[2].parse::<i32>().unwrap();
let maxy = parts[3].parse::<i32>().unwrap();
let minz = parts[4].parse::<i32>().unwrap();
let maxz = parts[5].parse::<i32>().unwrap();
let name = parts[6].to_string();
spatial_hashmap.add_platform(Platform {
minx,
maxx,
miny,
maxy,
minz,
maxz,
name
});
}
}
}
Ok(spatial_hashmap)
}
fn main() {
let spatial_hashmap = load_map_from_file("main.map").expect("Failed to load map");
let size_in_bytes = spatial_hashmap.grid.deep_size_of();
println!(
"Ve\u{13e}kos\u{165} mapy je pribli\u{17e}ne {} kilobajtov",
size_in_bytes / 1024
);
let loop_count = 3000000;
let point = Point3D { x: 0, y: 112, z: 0 };
//let mut found_platforms = Vec::new();
let start = Instant::now();
for _ in 0..loop_count {
if let Some(_platform) = spatial_hashmap.find_latest_platform_at(point) {
//if !found_platforms.contains(&platform.name) {
//found_platforms.push(platform.name.clone());
//}
}
}
let duration = start.elapsed();
println!("Vyh\u{13e}ad\u{e1}vanie na (0, 0, 0) {loop_count}-kr\u{e1}t trvalo: {duration:?}");
//println!("N\u{e1}jden\u{e9} platformy: {found_platforms:?}");
}