Blacksite/crates/scene/src/navigation.rs

use std::fs;
use std::path::{Path, PathBuf};

use nav_glam::{Mat4, UVec3, Vec2, Vec3, Vec3A};
use polyanya::{Mesh, RecastFullMesh};
use rerecast::{
    Aabb3d, AreaType, ConfigBuilder, ConvexVolume, DetailNavmesh, HeightfieldBuilder, TriMesh,
};
use serde::{Deserialize, Serialize};
use shared::{
    BrushDesc, BrushKind, NavigationAgentProfile, NavigationArea, NavigationBounds, NavigationLink,
    NavigationObstacle, PrefabInstance, PrefabOverrides, PrefabRef, Primitive, PrimitiveShape,
    COMPONENT_BRUSH_DESC, COMPONENT_NAVIGATION_AREA, COMPONENT_NAVIGATION_BOUNDS,
    COMPONENT_NAVIGATION_LINK, COMPONENT_NAVIGATION_OBSTACLE, COMPONENT_PRIMITIVE,
};

use crate::document::{SceneComponentBlob, SceneDocument, SceneEntity};

pub const NAVIGATION_ARTIFACT_SCHEMA_VERSION: u32 = 2;
pub const NAVIGATION_GENERATOR_ID: &str =
    "blacksite-nav-2/rerecast-0.3.2/polyanya-0.16.1/glam-0.30.10";
const MAX_NAVIGATION_GRID_AXIS: u64 = 8_192;
const MAX_NAVIGATION_GRID_CELLS: u64 = 4_194_304;

#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NavigationVolumeInput {
    pub actor_id: String,
    pub center: [f32; 3],
    pub half_extents: [f32; 3],
}

#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NavigationAreaInput {
    pub actor_id: String,
    pub id: String,
    pub center: [f32; 3],
    pub half_extents: [f32; 3],
    pub cost: f32,
    pub walkable: bool,
}

#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NavigationLinkInput {
    pub actor_id: String,
    pub start: [f32; 3],
    pub end: [f32; 3],
    pub bidirectional: bool,
    pub cost: f32,
    pub enabled: bool,
}

#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NavigationGeometryInput {
    pub actor_id: String,
    pub triangles: Vec<[[f32; 3]; 3]>,
}

#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NavigationPathSampleInput {
    pub id: String,
    pub start: [f32; 3],
    pub end: [f32; 3],
    pub enabled: bool,
}

#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NavigationBakeInput {
    pub source_scene: String,
    pub bounds_actor_id: String,
    pub center: [f32; 3],
    pub half_extents: [f32; 3],
    pub agent: NavigationAgentProfile,
    #[serde(default)]
    pub geometry: Vec<NavigationGeometryInput>,
    #[serde(default)]
    pub obstacles: Vec<NavigationVolumeInput>,
    #[serde(default)]
    pub areas: Vec<NavigationAreaInput>,
    #[serde(default)]
    pub links: Vec<NavigationLinkInput>,
    #[serde(default)]
    pub samples: Vec<NavigationPathSampleInput>,
}

#[derive(Debug, Clone, PartialEq)]
pub struct NavigationBakeJob {
    pub artifact_path: String,
    pub input: NavigationBakeInput,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct NavigationBakeArtifact {
    pub schema_version: u32,
    pub generator: String,
    pub source_scene: String,
    pub source_fingerprint: String,
    #[serde(default)]
    pub payload_hash: String,
    pub bounds_actor_id: String,
    pub center: [f32; 3],
    pub half_extents: [f32; 3],
    pub agent: NavigationAgentProfile,
    pub mesh: Mesh,
    pub links: Vec<NavigationLinkInput>,
    pub areas: Vec<NavigationAreaInput>,
    #[serde(default)]
    pub samples: Vec<NavigationPathSampleInput>,
    #[serde(default)]
    pub diagnostics: NavigationBakeDiagnostics,
}

#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct NavigationBakeDiagnostics {
    pub polygon_count: usize,
    pub island_count: usize,
    #[serde(default)]
    pub effective_component_count: usize,
}

impl NavigationBakeArtifact {
    pub fn runtime_mesh(&self) -> Mesh {
        let mut mesh = self.mesh.clone();
        mesh.bake();
        mesh
    }

    pub fn is_stale_for(&self, input: &NavigationBakeInput) -> bool {
        self.schema_version != NAVIGATION_ARTIFACT_SCHEMA_VERSION
            || self.generator != NAVIGATION_GENERATOR_ID
            || self.source_fingerprint != navigation_source_fingerprint(input)
    }
}

pub fn navigation_source_fingerprint(input: &NavigationBakeInput) -> String {
    let bytes = ron::ser::to_string(input)
        .expect("navigation bake input contains only serializable authoring data");
    blake3::hash(bytes.as_bytes()).to_hex().to_string()
}

pub fn navigation_artifact_content_hash(
    artifact: &NavigationBakeArtifact,
) -> Result<String, String> {
    let bytes = ron::ser::to_string(artifact)
        .map_err(|error| format!("failed to serialize navigation artifact for hashing: {error}"))?;
    Ok(blake3::hash(bytes.as_bytes()).to_hex().to_string())
}

pub fn navigation_artifact_payload_hash(
    artifact: &NavigationBakeArtifact,
) -> Result<String, String> {
    let mut payload = artifact.clone();
    payload.payload_hash.clear();
    navigation_artifact_content_hash(&payload)
}

pub fn bake_navigation(input: &NavigationBakeInput) -> Result<NavigationBakeArtifact, String> {
    validate_navigation_input(input)?;

    let center = vec3(input.center);
    let half_extents = vec3(input.half_extents);
    let min = center - half_extents;
    let max = center + half_extents;
    let mut trimesh = TriMesh {
        vertices: Vec::new(),
        indices: Vec::new(),
        area_types: Vec::new(),
    };
    append_geometry(&mut trimesh, &input.geometry);
    let config = ConfigBuilder {
        cell_size_fraction: input.agent.cell_size_fraction,
        cell_height_fraction: input.agent.cell_height_fraction,
        agent_height: input.agent.height,
        agent_radius: input.agent.radius,
        walkable_climb: input.agent.max_climb,
        walkable_slope_angle: input.agent.max_slope_deg.to_radians(),
        min_region_size: input.agent.min_region_size,
        merge_region_size: input.agent.merge_region_size,
        aabb: Aabb3d { min, max },
        ..Default::default()
    }
    .build();

    trimesh.mark_walkable_triangles(config.walkable_slope_angle);
    let mut heightfield = HeightfieldBuilder {
        aabb: config.aabb,
        cell_size: config.cell_size,
        cell_height: config.cell_height,
    }
    .build()
    .map_err(|error| format!("failed to allocate navigation heightfield: {error}"))?;
    heightfield
        .rasterize_triangles(&trimesh, config.walkable_climb)
        .map_err(|error| format!("failed to rasterize navigation geometry: {error}"))?;
    heightfield.filter_low_hanging_walkable_obstacles(config.walkable_climb);
    heightfield.filter_ledge_spans(config.walkable_height, config.walkable_climb);
    heightfield.filter_walkable_low_height_spans(config.walkable_height);

    let mut compact = heightfield
        .into_compact(config.walkable_height, config.walkable_climb)
        .map_err(|error| format!("failed to compact navigation heightfield: {error}"))?;
    compact.erode_walkable_area(config.walkable_radius);
    for obstacle in &input.obstacles {
        compact.mark_convex_poly_area(&unwalkable_volume(obstacle.center, obstacle.half_extents));
    }
    for area in input.areas.iter().filter(|area| !area.walkable) {
        compact.mark_convex_poly_area(&unwalkable_volume(area.center, area.half_extents));
    }

    compact.build_distance_field();
    compact
        .build_regions(
            config.border_size,
            config.min_region_area,
            config.merge_region_area,
        )
        .map_err(|error| format!("failed to partition navigation regions: {error}"))?;
    let contours = compact.build_contours(
        config.max_simplification_error,
        config.max_edge_len,
        config.contour_flags,
    );
    let polygon = contours
        .into_polygon_mesh(config.max_vertices_per_polygon)
        .map_err(|error| format!("failed to build navigation polygons: {error}"))?;
    if polygon.polygon_count() == 0 {
        return Err(
            "navigation bake produced no walkable polygons; enlarge bounds or repair obstacles"
                .into(),
        );
    }
    let detail = DetailNavmesh::new(
        &polygon,
        &compact,
        config.detail_sample_dist,
        config.detail_sample_max_error,
    )
    .map_err(|error| format!("failed to build navigation detail mesh: {error}"))?;

    let mut mesh: Mesh = RecastFullMesh::new(polygon, detail).into();
    let diagnostics = navigation_diagnostics(&mesh, &input.links, input.agent.radius);
    mesh.unbake();
    let mut artifact = NavigationBakeArtifact {
        schema_version: NAVIGATION_ARTIFACT_SCHEMA_VERSION,
        generator: NAVIGATION_GENERATOR_ID.into(),
        source_scene: input.source_scene.clone(),
        source_fingerprint: navigation_source_fingerprint(input),
        payload_hash: String::new(),
        bounds_actor_id: input.bounds_actor_id.clone(),
        center: input.center,
        half_extents: input.half_extents,
        agent: input.agent.clone(),
        mesh,
        links: input.links.clone(),
        areas: input.areas.clone(),
        samples: input.samples.clone(),
        diagnostics,
    };
    artifact.payload_hash = navigation_artifact_payload_hash(&artifact)?;
    Ok(artifact)
}

pub fn write_navigation_artifact(
    path: &Path,
    artifact: &NavigationBakeArtifact,
) -> Result<(), String> {
    if let Some(parent) = path.parent() {
        fs::create_dir_all(parent).map_err(|error| {
            format!("failed to create navigation artifact directory {parent:?}: {error}")
        })?;
    }
    let text = ron::ser::to_string_pretty(artifact, ron::ser::PrettyConfig::default())
        .map_err(|error| format!("failed to serialize navigation artifact: {error}"))?;
    let temporary = temporary_path(path);
    fs::write(&temporary, text)
        .map_err(|error| format!("failed to write navigation artifact {temporary:?}: {error}"))?;
    fs::rename(&temporary, path)
        .map_err(|error| format!("failed to replace navigation artifact {path:?}: {error}"))
}

pub fn read_navigation_artifact(path: &Path) -> Result<NavigationBakeArtifact, String> {
    let text = fs::read_to_string(path)
        .map_err(|error| format!("failed to read navigation artifact {path:?}: {error}"))?;
    let artifact: NavigationBakeArtifact = ron::from_str(&text)
        .map_err(|error| format!("failed to parse navigation artifact {path:?}: {error}"))?;
    if artifact.schema_version != NAVIGATION_ARTIFACT_SCHEMA_VERSION {
        return Err(format!(
            "navigation artifact schema {} is unsupported; rebake with schema {}",
            artifact.schema_version, NAVIGATION_ARTIFACT_SCHEMA_VERSION
        ));
    }
    if artifact.generator != NAVIGATION_GENERATOR_ID {
        return Err(format!(
            "navigation artifact generator `{}` is unsupported; rebake with `{NAVIGATION_GENERATOR_ID}`",
            artifact.generator
        ));
    }
    let actual_hash = navigation_artifact_payload_hash(&artifact)?;
    if artifact.payload_hash != actual_hash {
        return Err(format!(
            "navigation artifact payload hash mismatch (stored `{}`, actual `{actual_hash}`); delete it and rebake",
            artifact.payload_hash
        ));
    }
    Ok(artifact)
}

/// Engine-agnostic runtime query result shared by the editor, validation, and game crates.
#[derive(Debug, Clone, PartialEq)]
pub struct NavigationQueryPath {
    pub points: Vec<[f32; 3]>,
    pub length: f32,
    pub used_link_actor_ids: Vec<String>,
}

impl NavigationQueryPath {
    pub fn used_link_actor_id(&self) -> Option<&str> {
        self.used_link_actor_ids.first().map(String::as_str)
    }
}

/// A baked navigation artifact with Polyanya acceleration data ready for repeated queries.
#[derive(Debug, Clone)]
pub struct NavigationQueryRuntime {
    artifact: NavigationBakeArtifact,
    mesh: Mesh,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NavigationLinkValidationFinding {
    pub actor_id: String,
    pub endpoint: &'static str,
    pub message: String,
}

impl NavigationQueryRuntime {
    pub fn from_artifact(artifact: NavigationBakeArtifact) -> Result<Self, String> {
        if artifact.mesh.layers.is_empty()
            || artifact
                .mesh
                .layers
                .iter()
                .all(|layer| layer.polygons.is_empty())
        {
            return Err("navigation artifact contains no walkable polygons; rebake it".into());
        }
        let mesh = artifact.runtime_mesh();
        Ok(Self { artifact, mesh })
    }

    pub fn load(path: &Path) -> Result<Self, String> {
        Self::from_artifact(read_navigation_artifact(path)?)
    }

    pub fn artifact(&self) -> &NavigationBakeArtifact {
        &self.artifact
    }

    pub fn query(&self, start: [f32; 3], end: [f32; 3]) -> Result<NavigationQueryPath, String> {
        if !finite3(start) || !finite3(end) {
            return Err("navigation query endpoints must be finite".into());
        }

        let mut nodes = vec![vec3(start), vec3(end)];
        let mut link_edges = Vec::new();
        for link in self.artifact.links.iter().filter(|link| {
            link.enabled
                && self.endpoint_is_near_mesh(link.start)
                && self.endpoint_is_near_mesh(link.end)
        }) {
            let start_index = nodes.len();
            nodes.push(vec3(link.start));
            let end_index = nodes.len();
            nodes.push(vec3(link.end));
            link_edges.push(QueryLinkEdge::new(start_index, end_index, link, false));
            if link.bidirectional {
                link_edges.push(QueryLinkEdge::new(end_index, start_index, link, true));
            }
        }

        let mut distance = vec![f32::INFINITY; nodes.len()];
        let mut visited = vec![false; nodes.len()];
        let mut previous: Vec<Option<(usize, QueryRouteSegment)>> = vec![None; nodes.len()];
        let mut mesh_edges: Vec<Vec<Option<QueryRouteSegment>>> =
            vec![vec![None; nodes.len()]; nodes.len()];
        distance[0] = 0.0;

        for _ in 0..nodes.len() {
            let Some(current) = (0..nodes.len())
                .filter(|index| !visited[*index])
                .min_by(|a, b| distance[*a].total_cmp(&distance[*b]))
            else {
                break;
            };
            if !distance[current].is_finite() {
                break;
            }
            if current == 1 {
                break;
            }
            visited[current] = true;

            for next in 0..nodes.len() {
                if next == current || visited[next] {
                    continue;
                }
                if mesh_edges[current][next].is_none() {
                    if let Ok(path) = self.direct_path(nodes[current], nodes[next]) {
                        let forward = QueryRouteSegment::from_path(path);
                        let mut reverse = forward.clone();
                        reverse.points.reverse();
                        mesh_edges[current][next] = Some(forward);
                        mesh_edges[next][current] = Some(reverse);
                    }
                }
                if let Some(segment) = mesh_edges[current][next].clone() {
                    relax_query_route(current, next, segment, &mut distance, &mut previous);
                }
            }

            for edge in link_edges.iter().filter(|edge| edge.from == current) {
                relax_query_route(
                    current,
                    edge.to,
                    edge.segment.clone(),
                    &mut distance,
                    &mut previous,
                );
            }
        }

        if !distance[1].is_finite() {
            return Err(
                "no navigation path connects the requested endpoints; inspect islands or add a link"
                    .into(),
            );
        }
        assemble_query_route(&previous, 1)
    }

    pub fn validate_links(&self) -> Vec<String> {
        self.validate_link_findings()
            .into_iter()
            .map(|finding| finding.message)
            .collect()
    }

    pub fn validate_link_findings(&self) -> Vec<NavigationLinkValidationFinding> {
        let mut findings = Vec::new();
        for link in self.artifact.links.iter().filter(|link| link.enabled) {
            for (label, endpoint) in [("start", link.start), ("end", link.end)] {
                let endpoint = vec3(endpoint);
                let point = Vec2::new(endpoint.x, endpoint.z);
                let Some(closest) = self.mesh.get_closest_point_at_height(point, endpoint.y) else {
                    findings.push(NavigationLinkValidationFinding {
                        actor_id: link.actor_id.clone(),
                        endpoint: label,
                        message: format!(
                            "navigation link {} {label} endpoint is not near a walkable polygon",
                            link.actor_id
                        ),
                    });
                    continue;
                };
                let closest = closest.position_with_height(&self.mesh);
                let closest = Vec3::new(closest.x, closest.y, closest.z);
                if closest.distance(endpoint) > self.artifact.agent.radius * 2.0 {
                    findings.push(NavigationLinkValidationFinding {
                        actor_id: link.actor_id.clone(),
                        endpoint: label,
                        message: format!(
                            "navigation link {} {label} endpoint is farther than two agent radii from the mesh",
                            link.actor_id
                        ),
                    });
                }
            }
        }
        findings
    }

    pub fn validate_samples(&self) -> Vec<String> {
        self.artifact
            .samples
            .iter()
            .filter(|sample| sample.enabled)
            .filter_map(|sample| {
                self.query(sample.start, sample.end).err().map(|error| {
                    format!(
                        "navigation validation sample `{}` failed: {error}",
                        sample.id
                    )
                })
            })
            .collect()
    }

    fn direct_path(&self, start: Vec3, end: Vec3) -> Result<QueryDirectPath, String> {
        let start2 = Vec2::new(start.x, start.z);
        let end2 = Vec2::new(end.x, end.z);
        let start_coord = self
            .mesh
            .get_closest_point_at_height(start2, start.y)
            .ok_or_else(|| "navigation start is outside the mesh".to_string())?;
        let end_coord = self
            .mesh
            .get_closest_point_at_height(end2, end.y)
            .ok_or_else(|| "navigation end is outside the mesh".to_string())?;
        let nav_start = start_coord.position_with_height(&self.mesh);
        let nav_end = end_coord.position_with_height(&self.mesh);
        let nav_start = Vec3::new(nav_start.x, nav_start.y, nav_start.z);
        let nav_end = Vec3::new(nav_end.x, nav_end.y, nav_end.z);
        let maximum_snap = self.artifact.agent.radius * 2.0;
        if nav_start.distance(start) > maximum_snap {
            return Err("navigation start is farther than two agent radii from the mesh".into());
        }
        if nav_end.distance(end) > maximum_snap {
            return Err("navigation end is farther than two agent radii from the mesh".into());
        }
        let path = self.mesh.path(start_coord, end_coord).ok_or_else(|| {
            "navigation endpoints are outside the same reachable mesh island".to_string()
        })?;
        let mut points = vec![nav_start];
        for point in path.path_with_height(nav_start, nav_end, &self.mesh) {
            append_distinct_query_point(&mut points, Vec3::new(point.x, point.y, point.z));
        }
        append_distinct_query_point(&mut points, nav_end);
        let length = query_path_length(&points);
        Ok(QueryDirectPath { points, length })
    }

    fn endpoint_is_near_mesh(&self, endpoint: [f32; 3]) -> bool {
        let endpoint = vec3(endpoint);
        self.mesh
            .get_closest_point_at_height(Vec2::new(endpoint.x, endpoint.z), endpoint.y)
            .is_some_and(|closest| {
                let closest = closest.position_with_height(&self.mesh);
                Vec3::new(closest.x, closest.y, closest.z).distance(endpoint)
                    <= self.artifact.agent.radius * 2.0
            })
    }
}

#[derive(Debug, Clone)]
struct QueryDirectPath {
    points: Vec<Vec3>,
    length: f32,
}

#[derive(Debug, Clone)]
struct QueryRouteSegment {
    points: Vec<Vec3>,
    weighted_cost: f32,
    link_actor_id: Option<String>,
}

impl QueryRouteSegment {
    fn from_path(path: QueryDirectPath) -> Self {
        Self {
            points: path.points,
            weighted_cost: path.length,
            link_actor_id: None,
        }
    }
}

struct QueryLinkEdge {
    from: usize,
    to: usize,
    segment: QueryRouteSegment,
}

impl QueryLinkEdge {
    fn new(from: usize, to: usize, link: &NavigationLinkInput, reverse: bool) -> Self {
        let points = if reverse {
            vec![vec3(link.end), vec3(link.start)]
        } else {
            vec![vec3(link.start), vec3(link.end)]
        };
        let length = query_path_length(&points);
        Self {
            from,
            to,
            segment: QueryRouteSegment {
                points,
                weighted_cost: length * link.cost,
                link_actor_id: Some(link.actor_id.clone()),
            },
        }
    }
}

fn relax_query_route(
    from: usize,
    to: usize,
    segment: QueryRouteSegment,
    distance: &mut [f32],
    previous: &mut [Option<(usize, QueryRouteSegment)>],
) {
    let candidate = distance[from] + segment.weighted_cost;
    if candidate < distance[to] {
        distance[to] = candidate;
        previous[to] = Some((from, segment));
    }
}

fn assemble_query_route(
    previous: &[Option<(usize, QueryRouteSegment)>],
    destination: usize,
) -> Result<NavigationQueryPath, String> {
    let mut segments = Vec::new();
    let mut current = destination;
    while current != 0 {
        let Some((from, segment)) = previous[current].clone() else {
            return Err("navigation route reconstruction failed".into());
        };
        segments.push(segment);
        current = from;
    }
    segments.reverse();

    let mut points = Vec::new();
    let mut used_link_actor_ids = Vec::new();
    for segment in segments {
        for point in segment.points {
            append_distinct_query_point(&mut points, point);
        }
        if let Some(actor_id) = segment.link_actor_id {
            used_link_actor_ids.push(actor_id);
        }
    }
    Ok(NavigationQueryPath {
        length: query_path_length(&points),
        points: points.into_iter().map(|point| point.to_array()).collect(),
        used_link_actor_ids,
    })
}

fn append_distinct_query_point(points: &mut Vec<Vec3>, point: Vec3) {
    if points
        .last()
        .is_none_or(|last| last.distance_squared(point) > 1.0e-8)
    {
        points.push(point);
    }
}

fn query_path_length(points: &[Vec3]) -> f32 {
    points
        .windows(2)
        .map(|edge| edge[0].distance(edge[1]))
        .sum()
}

pub fn query_navigation_artifact(
    artifact: NavigationBakeArtifact,
    start: [f32; 3],
    end: [f32; 3],
) -> Result<NavigationQueryPath, String> {
    NavigationQueryRuntime::from_artifact(artifact)?.query(start, end)
}

pub fn navigation_bake_jobs_from_document(
    document: &SceneDocument,
    source_scene: &str,
) -> Result<Vec<NavigationBakeJob>, String> {
    if !document.entities.iter().any(|entity| {
        entity
            .components
            .iter()
            .any(|component| component.type_name == COMPONENT_NAVIGATION_BOUNDS)
    }) {
        return Ok(Vec::new());
    }
    let poses = document_world_poses(document)?;
    let mut obstacles = Vec::new();
    let mut areas = Vec::new();
    let mut links = Vec::new();
    let mut bounds = Vec::new();
    let mut geometry = Vec::new();

    for entity in &document.entities {
        let bounds_value = component::<NavigationBounds>(entity, COMPONENT_NAVIGATION_BOUNDS)?;
        let obstacle_value =
            component::<NavigationObstacle>(entity, COMPONENT_NAVIGATION_OBSTACLE)?;
        let area_value = component::<NavigationArea>(entity, COMPONENT_NAVIGATION_AREA)?;
        let link_value = component::<NavigationLink>(entity, COMPONENT_NAVIGATION_LINK)?;
        let primitive = component::<Primitive>(entity, COMPONENT_PRIMITIVE)?;
        let brush = component::<BrushDesc>(entity, COMPONENT_BRUSH_DESC)?;
        if bounds_value.is_none()
            && obstacle_value.is_none()
            && area_value.is_none()
            && link_value.is_none()
            && primitive.is_none()
            && brush.is_none()
        {
            continue;
        }
        let actor_id = entity
            .actor_id
            .clone()
            .ok_or_else(|| format!("navigation entity {} requires ActorId", entity.document_id))?;
        let pose = poses
            .get(&actor_id)
            .copied()
            .unwrap_or_else(WorldPose::identity);
        if let Some(value) = bounds_value {
            bounds.push((actor_id.clone(), pose, value));
        }
        if let Some(value) = obstacle_value {
            obstacles.push(NavigationVolumeInput {
                actor_id: actor_id.clone(),
                center: pose.transform_point([0.0; 3]).to_array(),
                half_extents: rotated_aabb_half_extents(pose, value.half_extents.to_array()),
            });
        }
        if let Some(value) = area_value {
            areas.push(NavigationAreaInput {
                actor_id: actor_id.clone(),
                id: value.id,
                center: pose.transform_point([0.0; 3]).to_array(),
                half_extents: rotated_aabb_half_extents(pose, value.half_extents.to_array()),
                cost: value.cost,
                walkable: value.walkable,
            });
        }
        if let Some(value) = link_value {
            links.push(NavigationLinkInput {
                actor_id: actor_id.clone(),
                start: pose.transform_point(value.start.to_array()).to_array(),
                end: pose.transform_point(value.end.to_array()).to_array(),
                bidirectional: value.bidirectional,
                cost: value.cost,
                enabled: value.enabled,
            });
        }
        if let Some(value) = navigation_geometry_from_world_matrix(
            actor_id,
            pose.matrix.to_cols_array_2d(),
            primitive.as_ref(),
            brush.as_ref(),
        ) {
            geometry.push(value);
        }
    }
    obstacles.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
    areas.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
    links.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
    geometry.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
    bounds.sort_by(|a, b| a.0.cmp(&b.0));

    Ok(navigation_jobs_from_sources(
        source_scene,
        bounds,
        &geometry,
        &obstacles,
        &areas,
        &links,
    ))
}

/// Resolves the exact navigation contributors visible from one saved scene.
///
/// `entry_text_override` lets the editor provide its current unsaved authored snapshot while
/// subscenes and prefab sources continue to resolve from project files. Only bounds authored in
/// the entry document produce jobs; visible composed scenes and linked prefabs contribute source
/// geometry, volumes, areas, and links to those jobs.
pub fn resolve_navigation_bake_jobs(
    project_root: &Path,
    entry_path: &Path,
    entry_text_override: Option<&str>,
) -> Result<Vec<NavigationBakeJob>, String> {
    let project_root = project_root.canonicalize().map_err(|error| {
        format!(
            "could not resolve project root {}: {error}",
            project_root.display()
        )
    })?;
    let entry_path = if entry_path.is_absolute() {
        entry_path.to_path_buf()
    } else {
        project_root.join(entry_path)
    };
    let entry_path = entry_path.canonicalize().map_err(|error| {
        format!(
            "could not resolve navigation scene {}: {error}",
            entry_path.display()
        )
    })?;
    if !entry_path.starts_with(&project_root) {
        return Err(format!(
            "navigation scene {} is outside project root {}",
            entry_path.display(),
            project_root.display()
        ));
    }
    let source_scene = entry_path
        .strip_prefix(&project_root)
        .map_err(|_| "navigation scene is outside the project root".to_string())?
        .to_string_lossy()
        .replace('\\', "/");
    let entry_text = match entry_text_override {
        Some(text) => text.to_string(),
        None => fs::read_to_string(&entry_path)
            .map_err(|error| format!("could not read {}: {error}", entry_path.display()))?,
    };
    let document = SceneDocument::from_ron_text(&entry_text)
        .map_err(|error| format!("{}: {error}", entry_path.display()))?;
    if !document.entities.iter().any(|entity| {
        entity
            .components
            .iter()
            .any(|component| component.type_name == COMPONENT_NAVIGATION_BOUNDS)
    }) {
        return Ok(Vec::new());
    }

    let mut sources = ResolvedNavigationSources::default();
    let mut composition_stack = vec![entry_path.clone()];
    let mut prefab_stack = Vec::new();
    let entry_is_prefab = source_scene.starts_with("assets/prefabs/");
    collect_resolved_navigation_document(
        document,
        &entry_path,
        &project_root,
        WorldPose::identity(),
        "",
        !entry_is_prefab,
        entry_is_prefab,
        &[],
        &mut composition_stack,
        &mut prefab_stack,
        &mut sources,
    )?;
    sources.sort();
    Ok(navigation_jobs_from_sources(
        &source_scene,
        sources.bounds,
        &sources.geometry,
        &sources.obstacles,
        &sources.areas,
        &sources.links,
    ))
}

#[derive(Default)]
struct ResolvedNavigationSources {
    bounds: Vec<(String, WorldPose, NavigationBounds)>,
    geometry: Vec<NavigationGeometryInput>,
    obstacles: Vec<NavigationVolumeInput>,
    areas: Vec<NavigationAreaInput>,
    links: Vec<NavigationLinkInput>,
}

impl ResolvedNavigationSources {
    fn sort(&mut self) {
        self.bounds.sort_by(|a, b| a.0.cmp(&b.0));
        self.geometry.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
        self.obstacles.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
        self.areas.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
        self.links.sort_by(|a, b| a.actor_id.cmp(&b.actor_id));
    }
}

#[allow(clippy::too_many_arguments)]
fn collect_resolved_navigation_document(
    mut document: SceneDocument,
    document_path: &Path,
    project_root: &Path,
    base_pose: WorldPose,
    namespace: &str,
    collect_bounds: bool,
    inside_prefab: bool,
    override_layers: &[PrefabOverrides],
    composition_stack: &mut Vec<PathBuf>,
    prefab_stack: &mut Vec<PathBuf>,
    sources: &mut ResolvedNavigationSources,
) -> Result<(), String> {
    apply_navigation_override_layers(&mut document, override_layers, namespace)?;
    let poses = document_world_poses(&document)?;

    for entity in &document.entities {
        let bounds_value = component::<NavigationBounds>(entity, COMPONENT_NAVIGATION_BOUNDS)?;
        let obstacle_value =
            component::<NavigationObstacle>(entity, COMPONENT_NAVIGATION_OBSTACLE)?;
        let area_value = component::<NavigationArea>(entity, COMPONENT_NAVIGATION_AREA)?;
        let link_value = component::<NavigationLink>(entity, COMPONENT_NAVIGATION_LINK)?;
        let primitive = component::<Primitive>(entity, COMPONENT_PRIMITIVE)?;
        let brush = component::<BrushDesc>(entity, COMPONENT_BRUSH_DESC)?;
        let prefab = component::<PrefabInstance>(entity, PREFAB_INSTANCE_COMPONENT)?;
        if bounds_value.is_none()
            && obstacle_value.is_none()
            && area_value.is_none()
            && link_value.is_none()
            && primitive.is_none()
            && brush.is_none()
            && prefab.is_none()
        {
            continue;
        }
        let actor_id = entity.actor_id.clone().ok_or_else(|| {
            format!(
                "navigation contributor {} in {} requires ActorId",
                entity.document_id,
                document_path.display()
            )
        })?;
        let qualified_id = qualify_navigation_actor_id(namespace, &actor_id);
        let local_pose = poses
            .get(&actor_id)
            .copied()
            .unwrap_or_else(WorldPose::identity);
        let pose = base_pose.compose(local_pose);

        if let Some(value) = bounds_value {
            if inside_prefab {
                return Err(format!(
                    "prefab navigation contributor `{qualified_id}` contains Navigation Bounds; bounds must be authored in a level scene and the prefab should contain only geometry, obstacles, areas, or links"
                ));
            }
            if collect_bounds {
                sources.bounds.push((qualified_id.clone(), pose, value));
            }
        }
        if let Some(value) = obstacle_value {
            sources.obstacles.push(NavigationVolumeInput {
                actor_id: qualified_id.clone(),
                center: pose.transform_point([0.0; 3]).to_array(),
                half_extents: rotated_aabb_half_extents(pose, value.half_extents.to_array()),
            });
        }
        if let Some(value) = area_value {
            sources.areas.push(NavigationAreaInput {
                actor_id: qualified_id.clone(),
                id: value.id,
                center: pose.transform_point([0.0; 3]).to_array(),
                half_extents: rotated_aabb_half_extents(pose, value.half_extents.to_array()),
                cost: value.cost,
                walkable: value.walkable,
            });
        }
        if let Some(value) = link_value {
            sources.links.push(NavigationLinkInput {
                actor_id: qualified_id.clone(),
                start: pose.transform_point(value.start.to_array()).to_array(),
                end: pose.transform_point(value.end.to_array()).to_array(),
                bidirectional: value.bidirectional,
                cost: value.cost,
                enabled: value.enabled,
            });
        }
        if let Some(value) = navigation_geometry_from_world_matrix(
            qualified_id.clone(),
            pose.matrix.to_cols_array_2d(),
            primitive.as_ref(),
            brush.as_ref(),
        ) {
            sources.geometry.push(value);
        }

        if let Some(instance) = prefab {
            let target = resolve_project_scene_path(project_root, &instance.source_path)?;
            if let Some(index) = prefab_stack.iter().position(|path| path == &target) {
                let mut cycle = prefab_stack[index..]
                    .iter()
                    .map(|path| project_relative_label(project_root, path))
                    .collect::<Vec<_>>();
                cycle.push(project_relative_label(project_root, &target));
                return Err(format!("cyclic prefab reference: {}", cycle.join(" -> ")));
            }
            let own_overrides = shared::decode_prefab_overrides(&instance).map_err(|error| {
                format!("prefab instance `{qualified_id}` has invalid overrides: {error}")
            })?;
            let mut child_layers = vec![own_overrides];
            child_layers.extend(
                override_layers
                    .iter()
                    .map(|layer| descend_navigation_overrides(layer, &actor_id)),
            );
            let text = fs::read_to_string(&target)
                .map_err(|error| format!("could not read prefab {}: {error}", target.display()))?;
            let child_document = SceneDocument::from_ron_text(&text)
                .map_err(|error| format!("{}: {error}", target.display()))?;
            let child_namespace = if namespace.is_empty() {
                format!("prefab:{actor_id}")
            } else {
                format!("{namespace}/prefab:{actor_id}")
            };
            prefab_stack.push(target.clone());
            collect_resolved_navigation_document(
                child_document,
                &target,
                project_root,
                pose,
                &child_namespace,
                false,
                true,
                &child_layers,
                composition_stack,
                prefab_stack,
                sources,
            )?;
            prefab_stack.pop();
        }
    }

    if !inside_prefab {
        if let Some(composition) = document.composition {
            for reference in composition
                .subscenes
                .into_iter()
                .filter(|reference| reference.visible)
            {
                let target = resolve_project_scene_path(project_root, &reference.path)?;
                if let Some(index) = composition_stack.iter().position(|path| path == &target) {
                    let mut cycle = composition_stack[index..]
                        .iter()
                        .map(|path| project_relative_label(project_root, path))
                        .collect::<Vec<_>>();
                    cycle.push(project_relative_label(project_root, &target));
                    return Err(format!("cyclic subscene reference: {}", cycle.join(" -> ")));
                }
                let text = fs::read_to_string(&target).map_err(|error| {
                    format!("could not read subscene {}: {error}", target.display())
                })?;
                let child_document = SceneDocument::from_ron_text(&text)
                    .map_err(|error| format!("{}: {error}", target.display()))?;
                let child_namespace = if namespace.is_empty() {
                    format!("subscene:{}", reference.id)
                } else {
                    format!("{namespace}/subscene:{}", reference.id)
                };
                composition_stack.push(target.clone());
                collect_resolved_navigation_document(
                    child_document,
                    &target,
                    project_root,
                    base_pose,
                    &child_namespace,
                    false,
                    false,
                    &[],
                    composition_stack,
                    prefab_stack,
                    sources,
                )?;
                composition_stack.pop();
            }
        }
    }
    Ok(())
}

fn qualify_navigation_actor_id(namespace: &str, actor_id: &str) -> String {
    if namespace.is_empty() {
        actor_id.to_string()
    } else {
        format!("{namespace}::{actor_id}")
    }
}

fn resolve_project_scene_path(project_root: &Path, relative: &str) -> Result<PathBuf, String> {
    let relative_path = Path::new(relative);
    if relative.trim().is_empty()
        || relative_path.is_absolute()
        || !relative.replace('\\', "/").ends_with(".scn.ron")
        || relative_path.components().any(|component| {
            matches!(
                component,
                std::path::Component::CurDir
                    | std::path::Component::ParentDir
                    | std::path::Component::RootDir
                    | std::path::Component::Prefix(_)
            )
        })
    {
        return Err(format!(
            "scene dependency path `{relative}` must be a project-relative .scn.ron file"
        ));
    }
    let target = project_root
        .join(relative_path)
        .canonicalize()
        .map_err(|error| {
            format!(
                "missing scene dependency `{relative}` under {}: {error}",
                project_root.display()
            )
        })?;
    if !target.starts_with(project_root) {
        return Err(format!(
            "scene dependency `{relative}` escapes the project root"
        ));
    }
    Ok(target)
}

fn project_relative_label(project_root: &Path, path: &Path) -> String {
    path.strip_prefix(project_root)
        .unwrap_or(path)
        .to_string_lossy()
        .replace('\\', "/")
}

fn apply_navigation_override_layers(
    document: &mut SceneDocument,
    layers: &[PrefabOverrides],
    namespace: &str,
) -> Result<(), String> {
    for layer in layers {
        if !layer.structural.is_empty() {
            return Err(format!(
                "prefab `{namespace}` has structural overrides that can change navigation hierarchy; apply or unpack the prefab before baking"
            ));
        }
        for component in &layer.components {
            if !component.target.instance_chain.is_empty()
                || !navigation_relevant_override_component(&component.component_type)
            {
                continue;
            }
            apply_navigation_component_override(
                document,
                &component.target.actor_id,
                &component.component_type,
                component.value_component_ron.as_deref(),
            )?;
        }
        let properties = layer
            .properties
            .iter()
            .filter(|property| {
                property.target.instance_chain.is_empty()
                    && navigation_relevant_override_component(&property.component_type)
            })
            .collect::<Vec<_>>();
        for property in &properties {
            validate_navigation_property_override_base(document, property)?;
        }
        for property in properties {
            apply_navigation_property_override(document, property)?;
        }
    }
    Ok(())
}

fn navigation_relevant_override_component(component_type: &str) -> bool {
    matches!(
        component_type,
        TRANSFORM_COMPONENT
            | COMPONENT_PRIMITIVE
            | COMPONENT_BRUSH_DESC
            | COMPONENT_NAVIGATION_BOUNDS
            | COMPONENT_NAVIGATION_OBSTACLE
            | COMPONENT_NAVIGATION_AREA
            | COMPONENT_NAVIGATION_LINK
            | PREFAB_INSTANCE_COMPONENT
            | PREFAB_REF_COMPONENT
    )
}

fn apply_navigation_component_override(
    document: &mut SceneDocument,
    actor_id: &str,
    component_type: &str,
    value: Option<&str>,
) -> Result<(), String> {
    let entity = document
        .entities
        .iter_mut()
        .find(|entity| entity.actor_id.as_deref() == Some(actor_id))
        .ok_or_else(|| {
            format!("navigation-relevant prefab override targets missing actor `{actor_id}`")
        })?;
    match value {
        Some(value) => {
            let replacement = SceneComponentBlob::from_ron(component_type, value)?;
            if let Some(component) = entity
                .components
                .iter_mut()
                .find(|component| component.type_name == component_type)
            {
                *component = replacement;
            } else {
                entity.components.push(replacement);
            }
        }
        None => entity
            .components
            .retain(|component| component.type_name != component_type),
    }
    Ok(())
}

fn validate_navigation_property_override_base(
    document: &SceneDocument,
    property: &shared::PrefabPropertyOverride,
) -> Result<(), String> {
    let entity = document
        .entities
        .iter()
        .find(|entity| entity.actor_id.as_deref() == Some(&property.target.actor_id))
        .ok_or_else(|| {
            format!(
                "navigation-relevant prefab override targets missing actor `{}`",
                property.target.actor_id
            )
        })?;
    let component = entity
        .components
        .iter()
        .find(|component| component.type_name == property.component_type)
        .ok_or_else(|| {
            format!(
                "navigation-relevant prefab property override targets missing component `{}` on actor `{}`",
                property.component_type, property.target.actor_id
            )
        })?;
    if !navigation_component_values_equal(
        &property.component_type,
        &component.ron,
        &property.base_component_ron,
    )? {
        return Err(format!(
            "prefab property `{}` on actor `{}` was authored against a different `{}` base; rebase or apply the override before baking navigation",
            property.property_path, property.target.actor_id, property.component_type
        ));
    }
    Ok(())
}

fn apply_navigation_property_override(
    document: &mut SceneDocument,
    property: &shared::PrefabPropertyOverride,
) -> Result<(), String> {
    let entity = document
        .entities
        .iter_mut()
        .find(|entity| entity.actor_id.as_deref() == Some(&property.target.actor_id))
        .ok_or_else(|| {
            format!(
                "navigation-relevant prefab override targets missing actor `{}`",
                property.target.actor_id
            )
        })?;
    let component = entity
        .components
        .iter_mut()
        .find(|component| component.type_name == property.component_type)
        .ok_or_else(|| {
            format!(
                "navigation-relevant prefab property override targets missing component `{}` on actor `{}`",
                property.component_type, property.target.actor_id
            )
        })?;
    let merged = shared::apply_serialized_navigation_property_override(
        &property.component_type,
        &component.ron,
        &property.value_component_ron,
        &property.property_path,
    )?;
    *component = SceneComponentBlob::from_ron(&property.component_type, &merged)?;
    Ok(())
}

fn navigation_component_values_equal(
    component_type: &str,
    current: &str,
    base: &str,
) -> Result<bool, String> {
    fn compare<T>(component_type: &str, current: &str, base: &str) -> Result<bool, String>
    where
        T: for<'de> Deserialize<'de> + PartialEq,
    {
        let current = ron::from_str::<T>(current).map_err(|error| {
            format!("invalid current value for prefab component `{component_type}`: {error}")
        })?;
        let base = ron::from_str::<T>(base).map_err(|error| {
            format!("invalid base value for prefab component `{component_type}`: {error}")
        })?;
        Ok(current == base)
    }

    match component_type {
        TRANSFORM_COMPONENT => compare::<SerializedTransform>(component_type, current, base),
        COMPONENT_PRIMITIVE => compare::<Primitive>(component_type, current, base),
        COMPONENT_BRUSH_DESC => compare::<BrushDesc>(component_type, current, base),
        COMPONENT_NAVIGATION_BOUNDS => compare::<NavigationBounds>(component_type, current, base),
        COMPONENT_NAVIGATION_OBSTACLE => {
            compare::<NavigationObstacle>(component_type, current, base)
        }
        COMPONENT_NAVIGATION_AREA => compare::<NavigationArea>(component_type, current, base),
        COMPONENT_NAVIGATION_LINK => compare::<NavigationLink>(component_type, current, base),
        PREFAB_INSTANCE_COMPONENT => compare::<PrefabInstance>(component_type, current, base),
        PREFAB_REF_COMPONENT => compare::<PrefabRef>(component_type, current, base),
        _ => Err(format!(
            "component `{component_type}` is not part of the navigation override contract"
        )),
    }
}

fn descend_navigation_overrides(
    overrides: &PrefabOverrides,
    nested_actor_id: &str,
) -> PrefabOverrides {
    let components = overrides
        .components
        .iter()
        .filter_map(|component| {
            let mut component = component.clone();
            if component.target.instance_chain.first().map(String::as_str) == Some(nested_actor_id)
            {
                component.target.instance_chain.remove(0);
                Some(component)
            } else {
                None
            }
        })
        .collect();
    let properties = overrides
        .properties
        .iter()
        .filter_map(|property| {
            let mut property = property.clone();
            if property.target.instance_chain.first().map(String::as_str) == Some(nested_actor_id) {
                property.target.instance_chain.remove(0);
                Some(property)
            } else {
                None
            }
        })
        .collect();
    PrefabOverrides {
        format_version: overrides.format_version,
        source_revision: overrides.source_revision.clone(),
        components,
        properties,
        ..Default::default()
    }
}

const PREFAB_INSTANCE_COMPONENT: &str = "shared::components::PrefabInstance";
const PREFAB_REF_COMPONENT: &str = "shared::components::PrefabRef";

fn navigation_jobs_from_sources(
    source_scene: &str,
    bounds: Vec<(String, WorldPose, NavigationBounds)>,
    geometry: &[NavigationGeometryInput],
    obstacles: &[NavigationVolumeInput],
    areas: &[NavigationAreaInput],
    links: &[NavigationLinkInput],
) -> Vec<NavigationBakeJob> {
    bounds
        .into_iter()
        .map(|(actor_id, pose, bounds)| {
            let center = pose.transform_point([0.0; 3]).to_array();
            let half_extents = rotated_aabb_half_extents(pose, bounds.half_extents.to_array());
            let samples = bounds
                .validation_samples
                .iter()
                .map(|sample| NavigationPathSampleInput {
                    id: sample.id.clone(),
                    start: pose.transform_point(sample.start.to_array()).to_array(),
                    end: pose.transform_point(sample.end.to_array()).to_array(),
                    enabled: sample.enabled,
                })
                .collect();
            NavigationBakeJob {
                artifact_path: bounds.artifact_path,
                input: NavigationBakeInput {
                    source_scene: source_scene.to_string(),
                    bounds_actor_id: actor_id,
                    center,
                    half_extents,
                    agent: bounds.agent,
                    geometry: geometry
                        .iter()
                        .filter(|value| geometry_overlaps_bounds(value, center, half_extents))
                        .cloned()
                        .collect(),
                    obstacles: obstacles
                        .iter()
                        .filter(|value| {
                            aabb_overlaps(center, half_extents, value.center, value.half_extents)
                        })
                        .cloned()
                        .collect(),
                    areas: areas
                        .iter()
                        .filter(|value| {
                            aabb_overlaps(center, half_extents, value.center, value.half_extents)
                        })
                        .cloned()
                        .collect(),
                    links: links
                        .iter()
                        .filter(|value| {
                            point_in_aabb(value.start, center, half_extents)
                                || point_in_aabb(value.end, center, half_extents)
                        })
                        .cloned()
                        .collect(),
                    samples,
                },
            }
        })
        .collect()
}

fn validate_navigation_input(input: &NavigationBakeInput) -> Result<(), String> {
    input
        .agent
        .validate()
        .map_err(|error| format!("invalid navigation agent profile: {error}"))?;
    if input.source_scene.trim().is_empty() {
        return Err("navigation bake requires a source scene path".into());
    }
    if input.bounds_actor_id.trim().is_empty() {
        return Err("navigation bounds actor requires a stable ActorId".into());
    }
    validate_half_extents(input.half_extents, "navigation bounds")?;
    validate_grid_budget(input)?;
    if input
        .geometry
        .iter()
        .all(|source| source.triangles.is_empty())
    {
        return Err(format!(
            "navigation bounds {} contains no primitive or additive-brush source geometry; add walkable geometry inside the bounds",
            input.bounds_actor_id
        ));
    }
    for geometry in &input.geometry {
        if geometry.actor_id.trim().is_empty() {
            return Err("navigation geometry requires a stable actor ID".into());
        }
        for triangle in &geometry.triangles {
            if !triangle.iter().copied().all(finite3) {
                return Err(format!(
                    "navigation geometry {} contains a non-finite triangle",
                    geometry.actor_id
                ));
            }
        }
    }
    for obstacle in &input.obstacles {
        validate_half_extents(obstacle.half_extents, "navigation obstacle")?;
    }
    for area in &input.areas {
        validate_half_extents(area.half_extents, "navigation area")?;
        if area.id.trim().is_empty() {
            return Err(format!("navigation area {} has an empty ID", area.actor_id));
        }
        if !area.cost.is_finite() || area.cost <= 0.0 {
            return Err(format!(
                "navigation area {} cost must be finite and greater than zero",
                area.actor_id
            ));
        }
    }
    for link in &input.links {
        if link.enabled && (!finite3(link.start) || !finite3(link.end)) {
            return Err(format!(
                "navigation link {} endpoints must be finite",
                link.actor_id
            ));
        }
        if link.enabled && squared_distance(link.start, link.end) <= f32::EPSILON {
            return Err(format!(
                "navigation link {} endpoints must be distinct",
                link.actor_id
            ));
        }
        if !link.cost.is_finite() || link.cost <= 0.0 {
            return Err(format!(
                "navigation link {} cost must be finite and greater than zero",
                link.actor_id
            ));
        }
    }
    let mut sample_ids = std::collections::HashSet::new();
    for sample in &input.samples {
        let sample_id = sample.id.trim();
        if sample_id.is_empty() {
            return Err(format!(
                "navigation bounds {} has a validation sample with an empty ID",
                input.bounds_actor_id
            ));
        }
        if !sample_ids.insert(sample_id) {
            return Err(format!(
                "navigation bounds {} repeats validation sample ID `{sample_id}`",
                input.bounds_actor_id
            ));
        }
        if !finite3(sample.start) || !finite3(sample.end) {
            return Err(format!(
                "navigation validation sample `{sample_id}` endpoints must be finite"
            ));
        }
        if squared_distance(sample.start, sample.end) <= f32::EPSILON {
            return Err(format!(
                "navigation validation sample `{sample_id}` endpoints must be distinct"
            ));
        }
    }
    Ok(())
}

fn validate_grid_budget(input: &NavigationBakeInput) -> Result<(), String> {
    let cell_size = f64::from(input.agent.radius / input.agent.cell_size_fraction);
    if !cell_size.is_finite() || cell_size <= 0.0 {
        return Err("navigation voxel detail produces an invalid cell size".into());
    }
    let width = (f64::from(input.half_extents[0]) * 2.0 / cell_size).ceil();
    let height = (f64::from(input.half_extents[2]) * 2.0 / cell_size).ceil();
    if width < 1.0 || height < 1.0 {
        return Err(
            "navigation bounds are smaller than one voxel; reduce voxel detail or enlarge bounds"
                .into(),
        );
    }
    if width > MAX_NAVIGATION_GRID_AXIS as f64 || height > MAX_NAVIGATION_GRID_AXIS as f64 {
        return Err(format!(
            "navigation bake requests a {width:.0} x {height:.0} voxel grid; each axis is limited to {MAX_NAVIGATION_GRID_AXIS}. Split the bounds or reduce voxel detail"
        ));
    }
    let cells = width * height;
    if cells > MAX_NAVIGATION_GRID_CELLS as f64 {
        return Err(format!(
            "navigation bake requests {cells:.0} XZ cells ({width:.0} x {height:.0}); the limit is {MAX_NAVIGATION_GRID_CELLS}. Split the bounds or reduce voxel detail"
        ));
    }
    Ok(())
}

fn append_geometry(trimesh: &mut TriMesh, geometry: &[NavigationGeometryInput]) {
    for source in geometry {
        for triangle in &source.triangles {
            let base = trimesh.vertices.len() as u32;
            trimesh
                .vertices
                .extend(triangle.iter().map(|vertex| Vec3A::from_array(*vertex)));
            trimesh.indices.push(UVec3::new(base, base + 1, base + 2));
            trimesh.area_types.push(AreaType::DEFAULT_WALKABLE);
        }
    }
}

fn navigation_diagnostics(
    mesh: &Mesh,
    links: &[NavigationLinkInput],
    agent_radius: f32,
) -> NavigationBakeDiagnostics {
    let polygon_count = mesh.layers.iter().map(|layer| layer.polygons.len()).sum();
    let mut visited: Vec<Vec<bool>> = mesh
        .layers
        .iter()
        .map(|layer| vec![false; layer.polygons.len()])
        .collect();
    let mut island_by_polygon: Vec<Vec<usize>> = mesh
        .layers
        .iter()
        .map(|layer| vec![usize::MAX; layer.polygons.len()])
        .collect();
    let mut island_count = 0;
    for layer_index in 0..mesh.layers.len() {
        for polygon_index in 0..mesh.layers[layer_index].polygons.len() {
            if visited[layer_index][polygon_index] {
                continue;
            }
            let island = island_count;
            island_count += 1;
            let mut pending = vec![(layer_index, polygon_index)];
            while let Some((layer_index, polygon_index)) = pending.pop() {
                if visited[layer_index][polygon_index] {
                    continue;
                }
                visited[layer_index][polygon_index] = true;
                island_by_polygon[layer_index][polygon_index] = island;
                let layer = &mesh.layers[layer_index];
                for vertex_index in &layer.polygons[polygon_index].vertices {
                    for neighbour in &layer.vertices[*vertex_index as usize].polygons {
                        if *neighbour == u32::MAX {
                            continue;
                        }
                        let neighbour_layer = (*neighbour >> 24) as usize;
                        let neighbour_polygon = (*neighbour & 0x00ff_ffff) as usize;
                        if neighbour_layer < visited.len()
                            && neighbour_polygon < visited[neighbour_layer].len()
                            && !visited[neighbour_layer][neighbour_polygon]
                        {
                            pending.push((neighbour_layer, neighbour_polygon));
                        }
                    }
                }
            }
        }
    }

    let mut parents: Vec<usize> = (0..island_count).collect();
    let mut runtime_mesh = mesh.clone();
    runtime_mesh.bake();
    for link in links.iter().filter(|link| link.enabled) {
        let Some(start) =
            endpoint_island(&runtime_mesh, link.start, agent_radius, &island_by_polygon)
        else {
            continue;
        };
        let Some(end) = endpoint_island(&runtime_mesh, link.end, agent_radius, &island_by_polygon)
        else {
            continue;
        };
        union_components(&mut parents, start, end);
    }
    let mut effective_roots = std::collections::BTreeSet::new();
    for island in 0..island_count {
        effective_roots.insert(component_root(&mut parents, island));
    }
    NavigationBakeDiagnostics {
        polygon_count,
        island_count,
        effective_component_count: effective_roots.len(),
    }
}

fn endpoint_island(
    mesh: &Mesh,
    endpoint: [f32; 3],
    agent_radius: f32,
    island_by_polygon: &[Vec<usize>],
) -> Option<usize> {
    let point = Vec2::new(endpoint[0], endpoint[2]);
    let coord = mesh.get_closest_point_at_height(point, endpoint[1])?;
    let closest = coord.position_with_height(mesh);
    if closest.distance(Vec3::from_array(endpoint)) > agent_radius * 2.0 {
        return None;
    }
    let packed_polygon = coord.polygon();
    let layer = coord
        .layer()
        .map(usize::from)
        .unwrap_or((packed_polygon >> 24) as usize);
    let polygon = (packed_polygon & 0x00ff_ffff) as usize;
    island_by_polygon.get(layer)?.get(polygon).copied()
}

fn component_root(parents: &mut [usize], component: usize) -> usize {
    if parents[component] != component {
        parents[component] = component_root(parents, parents[component]);
    }
    parents[component]
}

fn union_components(parents: &mut [usize], a: usize, b: usize) {
    let a = component_root(parents, a);
    let b = component_root(parents, b);
    if a != b {
        parents[b] = a;
    }
}

pub fn navigation_geometry_from_parts(
    actor_id: String,
    translation: [f32; 3],
    rotation: [f32; 4],
    scale: [f32; 3],
    primitive: Option<&Primitive>,
    brush: Option<&BrushDesc>,
) -> Option<NavigationGeometryInput> {
    let matrix = Mat4::from_scale_rotation_translation(
        Vec3::from_array(scale),
        nav_glam::Quat::from_array(rotation).normalize(),
        Vec3::from_array(translation),
    );
    navigation_geometry_from_world_matrix(actor_id, matrix.to_cols_array_2d(), primitive, brush)
}

pub fn navigation_geometry_from_world_matrix(
    actor_id: String,
    world_matrix: [[f32; 4]; 4],
    primitive: Option<&Primitive>,
    brush: Option<&BrushDesc>,
) -> Option<NavigationGeometryInput> {
    let matrix = Mat4::from_cols_array_2d(&world_matrix);
    let local_triangles =
        if let Some(brush) = brush.filter(|brush| brush.kind == BrushKind::Additive) {
            brush_triangles(brush)
        } else if let Some(primitive) = primitive {
            primitive_triangles(primitive)
        } else {
            Vec::new()
        };
    (!local_triangles.is_empty()).then(|| NavigationGeometryInput {
        actor_id,
        triangles: local_triangles
            .into_iter()
            .map(|triangle| {
                triangle.map(|point| matrix.transform_point3(Vec3::from_array(point)).to_array())
            })
            .collect(),
    })
}

fn brush_triangles(brush: &BrushDesc) -> Vec<[[f32; 3]; 3]> {
    let mut triangles = Vec::new();
    for face in &brush.faces {
        let Some(first) = face.vertices.first() else {
            continue;
        };
        for edge in face.vertices[1..].windows(2) {
            triangles.push([first.to_array(), edge[0].to_array(), edge[1].to_array()]);
        }
    }
    triangles
}

fn primitive_triangles(primitive: &Primitive) -> Vec<[[f32; 3]; 3]> {
    let half = primitive.size.abs() * 0.5;
    let vertices = match primitive.shape {
        PrimitiveShape::Box => vec![
            [-half.x, -half.y, -half.z],
            [half.x, -half.y, -half.z],
            [half.x, half.y, -half.z],
            [-half.x, half.y, -half.z],
            [-half.x, -half.y, half.z],
            [half.x, -half.y, half.z],
            [half.x, half.y, half.z],
            [-half.x, half.y, half.z],
        ],
        PrimitiveShape::Ramp => vec![
            [-half.x, -half.y, -half.z],
            [half.x, -half.y, -half.z],
            [half.x, half.y, -half.z],
            [-half.x, half.y, -half.z],
            [-half.x, -half.y, half.z],
            [half.x, -half.y, half.z],
        ],
        PrimitiveShape::Sphere => vec![
            [0.0, half.y, 0.0],
            [half.x, 0.0, 0.0],
            [0.0, 0.0, half.z],
            [-half.x, 0.0, 0.0],
            [0.0, 0.0, -half.z],
            [0.0, -half.y, 0.0],
        ],
    };
    let indices: &[[usize; 3]] = match primitive.shape {
        PrimitiveShape::Box => &[
            [0, 2, 1],
            [0, 3, 2],
            [4, 5, 6],
            [4, 6, 7],
            [0, 1, 5],
            [0, 5, 4],
            [3, 7, 6],
            [3, 6, 2],
            [0, 4, 7],
            [0, 7, 3],
            [1, 2, 6],
            [1, 6, 5],
        ],
        PrimitiveShape::Ramp => &[
            [0, 2, 1],
            [0, 3, 2],
            [0, 1, 5],
            [0, 5, 4],
            [0, 4, 3],
            [1, 2, 5],
            [3, 4, 5],
            [3, 5, 2],
        ],
        PrimitiveShape::Sphere => &[
            [0, 2, 1],
            [0, 3, 2],
            [0, 4, 3],
            [0, 1, 4],
            [5, 1, 2],
            [5, 2, 3],
            [5, 3, 4],
            [5, 4, 1],
        ],
    };
    indices
        .iter()
        .map(|[a, b, c]| [vertices[*a], vertices[*b], vertices[*c]])
        .collect()
}

pub fn aabb_overlaps(
    a_center: [f32; 3],
    a_half: [f32; 3],
    b_center: [f32; 3],
    b_half: [f32; 3],
) -> bool {
    (0..3).all(|axis| (a_center[axis] - b_center[axis]).abs() <= a_half[axis] + b_half[axis])
}

pub fn point_in_aabb(point: [f32; 3], center: [f32; 3], half_extents: [f32; 3]) -> bool {
    (0..3).all(|axis| (point[axis] - center[axis]).abs() <= half_extents[axis])
}

pub fn geometry_overlaps_bounds(
    geometry: &NavigationGeometryInput,
    center: [f32; 3],
    half_extents: [f32; 3],
) -> bool {
    geometry.triangles.iter().any(|triangle| {
        let mut min = triangle[0];
        let mut max = triangle[0];
        for vertex in &triangle[1..] {
            for axis in 0..3 {
                min[axis] = min[axis].min(vertex[axis]);
                max[axis] = max[axis].max(vertex[axis]);
            }
        }
        let geometry_center = std::array::from_fn(|axis| (min[axis] + max[axis]) * 0.5);
        let geometry_half = std::array::from_fn(|axis| (max[axis] - min[axis]) * 0.5);
        aabb_overlaps(center, half_extents, geometry_center, geometry_half)
    })
}

fn unwalkable_volume(center: [f32; 3], half_extents: [f32; 3]) -> ConvexVolume {
    let center = vec3(center);
    let half = vec3(half_extents);
    ConvexVolume {
        vertices: vec![
            Vec2::new(center.x - half.x, center.z - half.z),
            Vec2::new(center.x + half.x, center.z - half.z),
            Vec2::new(center.x + half.x, center.z + half.z),
            Vec2::new(center.x - half.x, center.z + half.z),
        ],
        min_y: center.y - half.y,
        max_y: center.y + half.y,
        area: AreaType::NOT_WALKABLE,
    }
}

fn vec3(value: [f32; 3]) -> Vec3 {
    Vec3::from_array(value)
}

fn finite3(value: [f32; 3]) -> bool {
    value.into_iter().all(f32::is_finite)
}

fn validate_half_extents(value: [f32; 3], label: &str) -> Result<(), String> {
    if !finite3(value) || value.into_iter().any(|axis| axis <= 0.0) {
        return Err(format!(
            "{label} half extents must be finite and greater than zero"
        ));
    }
    Ok(())
}

fn squared_distance(a: [f32; 3], b: [f32; 3]) -> f32 {
    a.into_iter().zip(b).map(|(a, b)| (a - b) * (a - b)).sum()
}

fn temporary_path(path: &Path) -> PathBuf {
    let mut temporary = path.as_os_str().to_os_string();
    temporary.push(".tmp");
    PathBuf::from(temporary)
}

const TRANSFORM_COMPONENT: &str = "bevy_transform::components::transform::Transform";

#[derive(Debug, Clone, Copy, PartialEq, Deserialize)]
struct SerializedTransform {
    translation: [f32; 3],
    rotation: [f32; 4],
    scale: [f32; 3],
}

impl Default for SerializedTransform {
    fn default() -> Self {
        Self {
            translation: [0.0; 3],
            rotation: [0.0, 0.0, 0.0, 1.0],
            scale: [1.0; 3],
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct WorldPose {
    matrix: Mat4,
}

impl WorldPose {
    fn identity() -> Self {
        Self {
            matrix: Mat4::IDENTITY,
        }
    }

    fn from_serialized(value: SerializedTransform) -> Self {
        Self {
            matrix: Mat4::from_scale_rotation_translation(
                Vec3::from_array(value.scale),
                nav_glam::Quat::from_array(value.rotation).normalize(),
                Vec3::from_array(value.translation),
            ),
        }
    }

    fn compose(self, local: Self) -> Self {
        Self {
            matrix: self.matrix * local.matrix,
        }
    }

    fn transform_point(self, point: [f32; 3]) -> Vec3 {
        self.matrix.transform_point3(Vec3::from_array(point))
    }
}

fn document_world_poses(
    document: &SceneDocument,
) -> Result<std::collections::BTreeMap<String, WorldPose>, String> {
    let entities: std::collections::BTreeMap<&str, &SceneEntity> = document
        .entities
        .iter()
        .filter_map(|entity| Some((entity.actor_id.as_deref()?, entity)))
        .collect();
    let mut poses = std::collections::BTreeMap::new();
    let mut visiting = std::collections::BTreeSet::new();
    for actor_id in entities.keys().copied() {
        resolve_document_pose(actor_id, &entities, &mut poses, &mut visiting)?;
    }
    Ok(poses)
}

fn resolve_document_pose(
    actor_id: &str,
    entities: &std::collections::BTreeMap<&str, &SceneEntity>,
    poses: &mut std::collections::BTreeMap<String, WorldPose>,
    visiting: &mut std::collections::BTreeSet<String>,
) -> Result<WorldPose, String> {
    if let Some(pose) = poses.get(actor_id).copied() {
        return Ok(pose);
    }
    if !visiting.insert(actor_id.to_string()) {
        return Err(format!(
            "navigation hierarchy contains a cycle at actor {actor_id}"
        ));
    }
    let entity = entities
        .get(actor_id)
        .ok_or_else(|| format!("navigation actor {actor_id} is missing from the scene document"))?;
    let local = component::<SerializedTransform>(entity, TRANSFORM_COMPONENT)?
        .map(WorldPose::from_serialized)
        .unwrap_or_else(WorldPose::identity);
    let world = match entity.parent_actor_id.as_deref() {
        Some(parent) => resolve_document_pose(parent, entities, poses, visiting)?.compose(local),
        None => local,
    };
    visiting.remove(actor_id);
    poses.insert(actor_id.to_string(), world);
    Ok(world)
}

fn component<T: for<'de> Deserialize<'de>>(
    entity: &SceneEntity,
    type_name: &str,
) -> Result<Option<T>, String> {
    entity
        .components
        .iter()
        .find(|component| component.type_name == type_name)
        .map(|component| {
            ron::from_str(&component.ron).map_err(|error| {
                format!(
                    "actor {} has invalid {type_name}: {error}",
                    entity.document_id
                )
            })
        })
        .transpose()
}

fn rotated_aabb_half_extents(pose: WorldPose, local_half: [f32; 3]) -> [f32; 3] {
    let half = Vec3::from_array(local_half);
    let x = pose.matrix.x_axis.truncate().abs() * half.x;
    let y = pose.matrix.y_axis.truncate().abs() * half.y;
    let z = pose.matrix.z_axis.truncate().abs() * half.z;
    (x + y + z).to_array()
}

#[cfg(test)]
mod tests {
    use nav_glam::Vec2;
    use std::sync::atomic::{AtomicU64, Ordering};

    use super::*;

    static NEXT_PROJECT: AtomicU64 = AtomicU64::new(1);

    fn resolver_project() -> PathBuf {
        let root = std::env::temp_dir().join(format!(
            "blacksite-navigation-resolver-{}-{}",
            std::process::id(),
            NEXT_PROJECT.fetch_add(1, Ordering::Relaxed)
        ));
        std::fs::create_dir_all(root.join("assets/levels")).unwrap();
        std::fs::create_dir_all(root.join("assets/prefabs")).unwrap();
        root
    }

    fn bounds_ron(actor_id: &str) -> String {
        let mut bounds = NavigationBounds::for_actor(actor_id);
        bounds.half_extents = [10.0, 3.0, 10.0].into();
        bounds.agent.min_region_size = 1;
        bounds.agent.merge_region_size = 2;
        ron::to_string(&bounds).unwrap()
    }

    fn floor_geometry(
        actor_id: &str,
        min_x: f32,
        max_x: f32,
        min_z: f32,
        max_z: f32,
        y: f32,
    ) -> NavigationGeometryInput {
        NavigationGeometryInput {
            actor_id: actor_id.into(),
            triangles: vec![
                [[min_x, y, min_z], [max_x, y, max_z], [max_x, y, min_z]],
                [[min_x, y, min_z], [min_x, y, max_z], [max_x, y, max_z]],
            ],
        }
    }

    fn fixture() -> NavigationBakeInput {
        NavigationBakeInput {
            source_scene: "assets/levels/navigation_showcase.scn.ron".into(),
            bounds_actor_id: "bounds".into(),
            center: [0.0, 0.0, 0.0],
            half_extents: [5.0, 2.0, 5.0],
            agent: NavigationAgentProfile {
                min_region_size: 1,
                merge_region_size: 2,
                ..Default::default()
            },
            geometry: vec![floor_geometry("walkable-floor", -5.0, 5.0, -5.0, 5.0, 0.0)],
            obstacles: vec![NavigationVolumeInput {
                actor_id: "center-obstacle".into(),
                center: [0.0, 0.5, 0.0],
                half_extents: [0.75, 1.0, 0.75],
            }],
            areas: Vec::new(),
            links: Vec::new(),
            samples: Vec::new(),
        }
    }

    #[test]
    fn deterministic_bake_routes_around_an_obstacle() {
        let input = fixture();
        let artifact = bake_navigation(&input).unwrap();
        assert_eq!(
            artifact.source_fingerprint,
            navigation_source_fingerprint(&input)
        );
        let mesh = artifact.runtime_mesh();
        let path = mesh.path(Vec2::new(-3.0, 0.0), Vec2::new(3.0, 0.0));
        assert!(path.is_some());
        assert!(path.unwrap().length > 6.0);
    }

    #[test]
    fn empty_bounds_do_not_synthesize_walkable_floor() {
        let mut input = fixture();
        input.geometry.clear();
        let error = bake_navigation(&input).unwrap_err();
        assert!(error.contains("contains no primitive or additive-brush source geometry"));
        assert!(error.contains("bounds"));
    }

    #[test]
    fn excessive_voxel_grid_is_rejected_before_allocation() {
        let mut input = fixture();
        input.half_extents = [10_000.0, 2.0, 10_000.0];
        let error = bake_navigation(&input).unwrap_err();
        assert!(error.contains("voxel grid"));
        assert!(error.contains("Split the bounds or reduce voxel detail"));
    }

    #[test]
    fn separated_authored_surfaces_remain_disconnected() {
        let mut input = fixture();
        input.geometry = vec![
            floor_geometry("left", -5.0, -1.0, -4.0, 4.0, 0.0),
            floor_geometry("right", 1.0, 5.0, -4.0, 4.0, 0.0),
        ];
        input.obstacles.clear();
        let artifact = bake_navigation(&input).unwrap();
        assert!(artifact.diagnostics.island_count >= 2);
        assert!(artifact.diagnostics.effective_component_count >= 2);
        let mesh = artifact.runtime_mesh();
        assert!(mesh
            .path(Vec2::new(-3.0, 0.0), Vec2::new(3.0, 0.0))
            .is_none());
    }

    #[test]
    fn valid_link_unions_disconnected_islands_in_diagnostics() {
        let mut input = fixture();
        input.geometry = vec![
            floor_geometry("left", -5.0, -1.0, -4.0, 4.0, 0.0),
            floor_geometry("right", 1.0, 5.0, -4.0, 4.0, 0.0),
        ];
        input.obstacles.clear();
        input.links.push(NavigationLinkInput {
            actor_id: "bridge".into(),
            start: [-1.5, 0.0, 0.0],
            end: [1.5, 0.0, 0.0],
            bidirectional: true,
            cost: 1.0,
            enabled: true,
        });
        let diagnostics = bake_navigation(&input).unwrap().diagnostics;
        assert!(diagnostics.island_count >= 2);
        assert_eq!(diagnostics.effective_component_count, 1);
    }

    #[test]
    fn invalid_link_is_reported_and_excluded_from_runtime_routes() {
        let mut input = fixture();
        input.geometry = vec![
            floor_geometry("left", -5.0, -1.0, -4.0, 4.0, 0.0),
            floor_geometry("right", 1.0, 5.0, -4.0, 4.0, 0.0),
        ];
        input.obstacles.clear();
        input.links.push(NavigationLinkInput {
            actor_id: "invalid-bridge".into(),
            start: [-100.0, 0.0, 0.0],
            end: [1.5, 0.0, 0.0],
            bidirectional: true,
            cost: 1.0,
            enabled: true,
        });
        let runtime =
            NavigationQueryRuntime::from_artifact(bake_navigation(&input).unwrap()).unwrap();
        assert!(runtime
            .validate_links()
            .iter()
            .any(|finding| finding.contains("invalid-bridge start")));
        assert!(runtime.query([-3.0, 0.0, 0.0], [3.0, 0.0, 0.0]).is_err());
    }

    #[test]
    fn artifact_round_trip_preserves_query_mesh() {
        let mut input = fixture();
        input.samples.push(NavigationPathSampleInput {
            id: "fixture-route".into(),
            start: [-3.0, 0.0, -3.0],
            end: [3.0, 0.0, 3.0],
            enabled: true,
        });
        let artifact = bake_navigation(&input).unwrap();
        let text = ron::ser::to_string(&artifact).unwrap();
        let restored: NavigationBakeArtifact = ron::from_str(&text).unwrap();
        assert_eq!(restored.samples, input.samples);
        assert!(restored
            .runtime_mesh()
            .path(Vec2::new(-3.0, -3.0), Vec2::new(3.0, 3.0))
            .is_some());
        assert!(NavigationQueryRuntime::from_artifact(restored)
            .unwrap()
            .validate_samples()
            .is_empty());
    }

    #[test]
    fn shared_query_runtime_reports_unreachable_authored_sample() {
        let mut input = fixture();
        input.samples.push(NavigationPathSampleInput {
            id: "outside-bounds".into(),
            start: [100.0, 0.0, 100.0],
            end: [101.0, 0.0, 100.0],
            enabled: true,
        });
        let runtime =
            NavigationQueryRuntime::from_artifact(bake_navigation(&input).unwrap()).unwrap();
        let findings = runtime.validate_samples();
        assert_eq!(findings.len(), 1);
        assert!(findings[0].contains("outside-bounds"));
        assert!(findings[0].contains("no navigation path"));
    }

    #[test]
    fn artifact_payload_hash_detects_parseable_tampering() {
        let mut artifact = bake_navigation(&fixture()).unwrap();
        artifact.links.push(NavigationLinkInput {
            actor_id: "tampered-link".into(),
            start: [-1.0, 0.0, 0.0],
            end: [1.0, 0.0, 0.0],
            bidirectional: true,
            cost: 1.0,
            enabled: true,
        });
        let path = std::env::temp_dir().join(format!(
            "blacksite-navigation-tamper-{}.nav.ron",
            std::process::id()
        ));
        write_navigation_artifact(&path, &artifact).unwrap();
        let error = read_navigation_artifact(&path).unwrap_err();
        std::fs::remove_file(path).unwrap();
        assert!(error.contains("payload hash mismatch"));
    }

    #[test]
    fn agent_change_marks_artifact_stale() {
        let input = fixture();
        let artifact = bake_navigation(&input).unwrap();
        let mut changed = input;
        changed.agent.radius += 0.1;
        assert!(artifact.is_stale_for(&changed));
    }

    #[test]
    fn authored_geometry_change_marks_artifact_stale() {
        let mut input = fixture();
        let artifact = bake_navigation(&input).unwrap();
        input.geometry[0].triangles[0][0][0] -= 0.25;
        assert!(artifact.is_stale_for(&input));
    }

    #[test]
    fn bounds_filter_excludes_distant_authoring() {
        assert!(aabb_overlaps(
            [0.0, 0.0, 0.0],
            [2.0, 2.0, 2.0],
            [3.0, 0.0, 0.0],
            [1.0, 1.0, 1.0]
        ));
        assert!(!aabb_overlaps(
            [0.0, 0.0, 0.0],
            [2.0, 2.0, 2.0],
            [3.01, 0.0, 0.0],
            [1.0, 1.0, 1.0]
        ));
    }

    #[test]
    fn resolver_includes_visible_subscene_geometry_with_qualified_identity() {
        let root = resolver_project();
        let child = r#"(schema_version:4,resources:{},entities:{
            1:(components:{
                "shared::components::ActorId":("child-floor"),
                "bevy_transform::components::transform::Transform":(translation:(0.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0)),
                "shared::components::Primitive":(shape:Box,size:(12.0,0.2,12.0)),
            }),
        })"#;
        std::fs::write(root.join("assets/levels/child.scn.ron"), child).unwrap();
        let bounds = bounds_ron("main-bounds");
        let main = format!(
            r#"(schema_version:4,resources:{{
                "shared::components::SceneComposition":(scene_id:"main",subscenes:[(id:"geometry",path:"assets/levels/child.scn.ron",visible:true,locked:true)]),
            }},entities:{{
                1:(components:{{"shared::components::ActorId":("main-bounds"),"shared::navigation::NavigationBounds":{bounds},}}),
            }})"#
        );
        let main_path = root.join("assets/levels/main.scn.ron");
        std::fs::write(&main_path, main).unwrap();

        let job = resolve_navigation_bake_jobs(&root, &main_path, None)
            .unwrap()
            .pop()
            .unwrap();
        assert_eq!(job.input.geometry.len(), 1);
        assert_eq!(
            job.input.geometry[0].actor_id,
            "subscene:geometry::child-floor"
        );
        assert!(bake_navigation(&job.input).is_ok());
        std::fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn resolver_applies_navigation_relevant_prefab_transform_override() {
        let root = resolver_project();
        let prefab = r#"(schema_version:4,resources:{},entities:{
            1:(components:{
                "shared::components::ActorId":("prefab-floor"),
                "bevy_transform::components::transform::Transform":(translation:(1.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0)),
                "shared::components::Primitive":(shape:Box,size:(4.0,0.2,4.0)),
            }),
        })"#;
        std::fs::write(root.join("assets/prefabs/floor.scn.ron"), prefab).unwrap();
        let mut overrides = PrefabOverrides::default();
        overrides.components.push(shared::PrefabComponentOverride {
            target: shared::PrefabActorPath::direct("prefab-floor"),
            component_type: TRANSFORM_COMPONENT.into(),
            base_component_ron: None,
            value_component_ron: Some(
                "(translation:(4.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0))"
                    .into(),
            ),
        });
        let mut instance = PrefabInstance::new("floor-prefab", "assets/prefabs/floor.scn.ron");
        instance.overrides_ron = shared::encode_prefab_overrides(&overrides).unwrap();
        let instance = ron::to_string(&instance).unwrap();
        let bounds = bounds_ron("main-bounds");
        let main = format!(
            r#"(schema_version:4,resources:{{}},entities:{{
                1:(components:{{"shared::components::ActorId":("main-bounds"),"shared::navigation::NavigationBounds":{bounds},}}),
                2:(components:{{
                    "shared::components::ActorId":("floor-instance"),
                    "bevy_transform::components::transform::Transform":(translation:(2.0,0.0,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0)),
                    "shared::components::PrefabInstance":{instance},
                }}),
            }})"#
        );
        let main_path = root.join("assets/levels/main.scn.ron");
        std::fs::write(&main_path, main).unwrap();

        let job = resolve_navigation_bake_jobs(&root, &main_path, None)
            .unwrap()
            .pop()
            .unwrap();
        assert_eq!(job.input.geometry.len(), 1);
        assert_eq!(
            job.input.geometry[0].actor_id,
            "prefab:floor-instance::prefab-floor"
        );
        let x_min = job.input.geometry[0]
            .triangles
            .iter()
            .flatten()
            .map(|vertex| vertex[0])
            .fold(f32::INFINITY, f32::min);
        assert!((x_min - 4.0).abs() < 0.001, "x_min={x_min}");
        std::fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn resolver_applies_multiple_properties_and_blocks_a_drifted_prefab_base() {
        let root = resolver_project();
        let prefab = r#"(schema_version:4,resources:{},entities:{
            1:(components:{
                "shared::components::ActorId":("prefab-floor"),
                "bevy_transform::components::transform::Transform":(translation:(1.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0)),
                "shared::components::Primitive":(shape:Box,size:(4.0,0.2,4.0)),
            }),
        })"#;
        std::fs::write(root.join("assets/prefabs/floor.scn.ron"), prefab).unwrap();
        let mut overrides = PrefabOverrides::default();
        overrides.properties.push(shared::PrefabPropertyOverride {
            target: shared::PrefabActorPath::direct("prefab-floor"),
            component_type: TRANSFORM_COMPONENT.into(),
            property_path: "translation.x".into(),
            base_component_ron: "(translation:(1.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0))".into(),
            value_component_ron: "(translation:(4.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0))".into(),
        });
        overrides.properties.push(shared::PrefabPropertyOverride {
            target: shared::PrefabActorPath::direct("prefab-floor"),
            component_type: TRANSFORM_COMPONENT.into(),
            property_path: "scale.z".into(),
            base_component_ron: "(translation:(1.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0))".into(),
            value_component_ron: "(translation:(1.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,2.0))".into(),
        });
        let mut instance = PrefabInstance::new("floor-prefab", "assets/prefabs/floor.scn.ron");
        instance.overrides_ron = shared::encode_prefab_overrides(&overrides).unwrap();
        let instance = ron::to_string(&instance).unwrap();
        let bounds = bounds_ron("main-bounds");
        let main = format!(
            r#"(schema_version:4,resources:{{}},entities:{{
                1:(components:{{"shared::components::ActorId":("main-bounds"),"shared::navigation::NavigationBounds":{bounds},}}),
                2:(components:{{
                    "shared::components::ActorId":("floor-instance"),
                    "bevy_transform::components::transform::Transform":(translation:(2.0,0.0,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(1.0,1.0,1.0)),
                    "shared::components::PrefabInstance":{instance},
                }}),
            }})"#
        );
        let main_path = root.join("assets/levels/main.scn.ron");
        std::fs::write(&main_path, main).unwrap();

        let job = resolve_navigation_bake_jobs(&root, &main_path, None)
            .unwrap()
            .pop()
            .unwrap();
        let x_min = job.input.geometry[0]
            .triangles
            .iter()
            .flatten()
            .map(|vertex| vertex[0])
            .fold(f32::INFINITY, f32::min);
        assert!((x_min - 4.0).abs() < 0.001, "x_min={x_min}");
        let z_extent = job.input.geometry[0]
            .triangles
            .iter()
            .flatten()
            .map(|vertex| vertex[2])
            .fold((f32::INFINITY, f32::NEG_INFINITY), |(min, max), value| {
                (min.min(value), max.max(value))
            });
        assert!((z_extent.0 + 4.0).abs() < 0.001, "z_min={}", z_extent.0);
        assert!((z_extent.1 - 4.0).abs() < 0.001, "z_max={}", z_extent.1);

        let drifted_prefab = r#"(schema_version:4,resources:{},entities:{
            1:(components:{
                "shared::components::ActorId":("prefab-floor"),
                "bevy_transform::components::transform::Transform":(translation:(1.0,-0.1,0.0),rotation:(0.0,0.0,0.0,1.0),scale:(2.0,1.0,1.0)),
                "shared::components::Primitive":(shape:Box,size:(4.0,0.2,4.0)),
            }),
        })"#;
        std::fs::write(root.join("assets/prefabs/floor.scn.ron"), drifted_prefab).unwrap();
        let error = resolve_navigation_bake_jobs(&root, &main_path, None).unwrap_err();
        assert!(error.contains("translation.x"), "{error}");
        assert!(error.contains("different"), "{error}");
        assert!(error.contains("rebase or apply"), "{error}");
        std::fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn navigation_override_comparison_detects_primitive_shape_drift() {
        assert!(!navigation_component_values_equal(
            COMPONENT_PRIMITIVE,
            "(shape:Sphere,size:(4.0,0.2,4.0))",
            "(shape:Box,size:(4.0,0.2,4.0))",
        )
        .unwrap());
    }

    #[test]
    fn resolver_rejects_structural_prefab_overrides_instead_of_baking_mismatch() {
        let root = resolver_project();
        let prefab = r#"(schema_version:4,resources:{},entities:{
            1:(components:{"shared::components::ActorId":("prefab-floor"),"shared::components::Primitive":(shape:Box,size:(4.0,0.2,4.0)),}),
        })"#;
        std::fs::write(root.join("assets/prefabs/floor.scn.ron"), prefab).unwrap();
        let mut overrides = PrefabOverrides::default();
        overrides
            .structural
            .push(shared::PrefabStructuralOverride::RemoveChild {
                target: shared::PrefabActorPath::direct("prefab-floor"),
                base_subtree_revision: "fixture".into(),
            });
        let mut instance = PrefabInstance::new("floor-prefab", "assets/prefabs/floor.scn.ron");
        instance.overrides_ron = shared::encode_prefab_overrides(&overrides).unwrap();
        let instance = ron::to_string(&instance).unwrap();
        let bounds = bounds_ron("main-bounds");
        let main = format!(
            r#"(schema_version:4,resources:{{}},entities:{{
                1:(components:{{"shared::components::ActorId":("main-bounds"),"shared::navigation::NavigationBounds":{bounds},}}),
                2:(components:{{"shared::components::ActorId":("floor-instance"),"shared::components::PrefabInstance":{instance},}}),
            }})"#
        );
        let main_path = root.join("assets/levels/main.scn.ron");
        std::fs::write(&main_path, main).unwrap();
        let error = resolve_navigation_bake_jobs(&root, &main_path, None).unwrap_err();
        assert!(error.contains("structural overrides"), "{error}");
        assert!(error.contains("prefab:floor-instance"), "{error}");
        std::fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn committed_navigation_fixture_matches_its_bake_artifact() {
        let root = Path::new(env!("CARGO_MANIFEST_DIR")).join("../..");
        let scene_path = root.join("assets/levels/navigation_authoring_showcase.scn.ron");
        let text = std::fs::read_to_string(scene_path).unwrap();
        let document = SceneDocument::from_ron_text(&text).unwrap();
        let job = navigation_bake_jobs_from_document(
            &document,
            "assets/levels/navigation_authoring_showcase.scn.ron",
        )
        .unwrap()
        .pop()
        .unwrap();
        let committed = read_navigation_artifact(&root.join(&job.artifact_path)).unwrap();
        assert!(!committed.is_stale_for(&job.input));
        assert_eq!(committed.bounds_actor_id, "navigation-bounds-main");
        assert_eq!(job.input.geometry.len(), 1);
        assert_eq!(job.input.geometry[0].actor_id, "navigation-floor-geometry");
        assert_eq!(job.input.samples.len(), 1);
        assert!(NavigationQueryRuntime::from_artifact(committed.clone())
            .unwrap()
            .validate_samples()
            .is_empty());
        assert!(committed
            .runtime_mesh()
            .path(Vec2::new(-6.0, 0.0), Vec2::new(6.0, 0.0))
            .is_some());
    }
}