Performance At Scale

{
  "name": "performance-at-scale",
  "description": "Spatial indexing and world streaming for Three.js building games with thousands of pieces. Use when optimizing building games, implementing spatial queries, chunk loading, or profiling performance.",
  "tags": [
    "3d",
    "three.js",
    "optimization"
  ],
  "sub_skills": [],
  "source": "claude-user",
  "type": "template",
  "depends_on": [],
  "enhances": [
    "multiplayer-building",
    "structural-physics",
    "3d-building-advanced"
  ],
  "last_reviewed_at": null,
  "review_score": null,
  "relevance_tier": null
}

/**
 * ChunkManager - World streaming for large-scale building systems
 * 
 * Divides the world into chunks that load/unload based on player proximity.
 * Enables effectively infinite worlds while keeping memory bounded.
 * 
 * Based on: Minecraft's 16x16x256 chunk system, Rust's streaming architecture
 * 
 * Usage:
 *   const chunkManager = new ChunkManager({ chunkSize: 64, loadDistance: 3 });
 *   chunkManager.onChunkLoad = async (chunkKey) => loadChunkData(chunkKey);
 *   chunkManager.onChunkUnload = (chunkKey, chunk) => saveChunkData(chunkKey, chunk);
 *   // In game loop:
 *   chunkManager.update(playerPosition);
 */

import * as THREE from 'three';
import { Octree } from './octree.js';

export class Chunk {
  constructor(key, bounds, chunkSize) {
    this.key = key;
    this.bounds = bounds;
    this.chunkSize = chunkSize;
    this.objects = new Map(); // objectId -> object
    this.spatialIndex = new Octree(bounds, { maxDepth: 4, maxObjects: 16 });
    this.meshGroup = new THREE.Group();
    this.meshGroup.name = `Chunk_${key}`;
    
    this.state = 'unloaded'; // unloaded, loading, loaded, unloading
    this.lastAccess = Date.now();
    this.isDirty = false;
    this.metadata = {};
  }

  /**
   * Add object to chunk
   */
  addObject(id, object, position) {
    this.objects.set(id, { object, position: position.clone() });
    this.spatialIndex.insert(object, position);
    
    if (object.mesh) {
      this.meshGroup.add(object.mesh);
    } else if (object instanceof THREE.Object3D) {
      this.meshGroup.add(object);
    }
    
    this.isDirty = true;
    this.lastAccess = Date.now();
  }

  /**
   * Remove object from chunk
   */
  removeObject(id) {
    const entry = this.objects.get(id);
    if (!entry) return false;

    this.spatialIndex.remove(entry.object);
    
    if (entry.object.mesh) {
      this.meshGroup.remove(entry.object.mesh);
    } else if (entry.object instanceof THREE.Object3D) {
      this.meshGroup.remove(entry.object);
    }

    this.objects.delete(id);
    this.isDirty = true;
    this.lastAccess = Date.now();
    return true;
  }

  /**
   * Query objects within radius
   */
  queryRadius(position, radius) {
    this.lastAccess = Date.now();
    return this.spatialIndex.queryRadius(position, radius);
  }

  /**
   * Get all objects in chunk
   */
  getAllObjects() {
    return Array.from(this.objects.values());
  }

  /**
   * Get object count
   */
  get objectCount() {
    return this.objects.size;
  }

  /**
   * Serialize chunk data for saving
   */
  serialize() {
    const objects = [];
    for (const [id, { object, position }] of this.objects) {
      objects.push({
        id,
        type: object.type || object.constructor.name,
        position: { x: position.x, y: position.y, z: position.z },
        data: object.serialize ? object.serialize() : {}
      });
    }
    return {
      key: this.key,
      metadata: this.metadata,
      objects
    };
  }

  /**
   * Clear chunk data
   */
  clear() {
    this.objects.clear();
    this.spatialIndex.clear();
    this.meshGroup.clear();
    this.isDirty = false;
  }
}

export class ChunkManager {
  constructor(options = {}) {
    this.chunkSize = options.chunkSize ?? 64;
    this.loadDistance = options.loadDistance ?? 3;
    this.unloadDistance = options.unloadDistance ?? this.loadDistance + 2;
    this.maxLoadedChunks = options.maxLoadedChunks ?? 100;
    this.loadBatchSize = options.loadBatchSize ?? 2; // Chunks to load per frame
    this.worldHeight = options.worldHeight ?? 256;

    this.chunks = new Map(); // chunkKey -> Chunk
    this.loadQueue = [];
    this.unloadQueue = [];
    this.scene = options.scene || null;

    // Callbacks
    this.onChunkLoad = options.onChunkLoad || null;   // async (chunkKey) => chunkData
    this.onChunkUnload = options.onChunkUnload || null; // (chunkKey, chunk) => void
    this.onChunkCreate = options.onChunkCreate || null; // (chunk) => void

    // Stats
    this.stats = {
      loadedChunks: 0,
      loadingChunks: 0,
      queuedLoads: 0,
      totalObjects: 0
    };

    // Internal state
    this._lastPlayerChunk = null;
    this._isProcessing = false;
  }

  /**
   * Convert world position to chunk key
   */
  worldToChunkKey(position) {
    const cx = Math.floor(position.x / this.chunkSize);
    const cz = Math.floor(position.z / this.chunkSize);
    return `${cx},${cz}`;
  }

  /**
   * Parse chunk key to chunk coordinates
   */
  parseChunkKey(key) {
    const [x, z] = key.split(',').map(Number);
    return { x, z };
  }

  /**
   * Get chunk bounds from key
   */
  getChunkBounds(key) {
    const { x, z } = this.parseChunkKey(key);
    return {
      min: new THREE.Vector3(
        x * this.chunkSize,
        0,
        z * this.chunkSize
      ),
      max: new THREE.Vector3(
        (x + 1) * this.chunkSize,
        this.worldHeight,
        (z + 1) * this.chunkSize
      )
    };
  }

  /**
   * Main update - call every frame with player position
   */
  async update(playerPosition) {
    const playerChunkKey = this.worldToChunkKey(playerPosition);
    const playerChunk = this.parseChunkKey(playerChunkKey);

    // Only recalculate if player moved to new chunk
    if (this._lastPlayerChunk !== playerChunkKey) {
      this._lastPlayerChunk = playerChunkKey;
      this._updateChunkQueues(playerChunk);
    }

    // Process queues
    await this._processLoadQueue();
    this._processUnloadQueue();
    this._updateStats();
  }

  /**
   * Determine which chunks to load/unload
   */
  _updateChunkQueues(playerChunk) {
    const chunksToLoad = new Set();
    const chunksToKeep = new Set();

    // Determine chunks that should be loaded
    for (let dx = -this.loadDistance; dx <= this.loadDistance; dx++) {
      for (let dz = -this.loadDistance; dz <= this.loadDistance; dz++) {
        const key = `${playerChunk.x + dx},${playerChunk.z + dz}`;
        chunksToKeep.add(key);
        
        if (!this.chunks.has(key)) {
          chunksToLoad.add(key);
        }
      }
    }

    // Sort load queue by distance (closest first)
    this.loadQueue = Array.from(chunksToLoad).sort((a, b) => {
      const aCoords = this.parseChunkKey(a);
      const bCoords = this.parseChunkKey(b);
      const aDist = Math.abs(aCoords.x - playerChunk.x) + Math.abs(aCoords.z - playerChunk.z);
      const bDist = Math.abs(bCoords.x - playerChunk.x) + Math.abs(bCoords.z - playerChunk.z);
      return aDist - bDist;
    });

    // Determine chunks to unload
    for (const [key, chunk] of this.chunks) {
      if (chunk.state === 'loaded' || chunk.state === 'loading') {
        const coords = this.parseChunkKey(key);
        const dist = Math.max(
          Math.abs(coords.x - playerChunk.x),
          Math.abs(coords.z - playerChunk.z)
        );
        
        if (dist > this.unloadDistance) {
          this.unloadQueue.push(key);
        }
      }
    }
  }

  /**
   * Process chunk load queue
   */
  async _processLoadQueue() {
    if (this._isProcessing) return;
    this._isProcessing = true;

    const toLoad = this.loadQueue.splice(0, this.loadBatchSize);
    
    for (const key of toLoad) {
      if (this.chunks.has(key)) continue;

      // Create chunk
      const bounds = this.getChunkBounds(key);
      const chunk = new Chunk(key, bounds, this.chunkSize);
      chunk.state = 'loading';
      this.chunks.set(key, chunk);

      // Add to scene
      if (this.scene) {
        this.scene.add(chunk.meshGroup);
      }

      // Load data
      try {
        if (this.onChunkLoad) {
          const data = await this.onChunkLoad(key);
          if (data) {
            this._populateChunk(chunk, data);
          }
        }
        chunk.state = 'loaded';
        
        if (this.onChunkCreate) {
          this.onChunkCreate(chunk);
        }
      } catch (error) {
        console.error(`Failed to load chunk ${key}:`, error);
        chunk.state = 'loaded'; // Mark as loaded even if empty
      }
    }

    this._isProcessing = false;
  }

  /**
   * Process chunk unload queue
   */
  _processUnloadQueue() {
    // Limit unloads per frame
    const toUnload = this.unloadQueue.splice(0, 1);
    
    for (const key of toUnload) {
      const chunk = this.chunks.get(key);
      if (!chunk) continue;

      chunk.state = 'unloading';

      // Save if dirty
      if (this.onChunkUnload && chunk.isDirty) {
        this.onChunkUnload(key, chunk);
      }

      // Remove from scene
      if (this.scene) {
        this.scene.remove(chunk.meshGroup);
      }

      // Dispose resources
      chunk.clear();
      this.chunks.delete(key);
    }

    // Force unload if over limit
    if (this.chunks.size > this.maxLoadedChunks) {
      this._forceTrimChunks();
    }
  }

  /**
   * Populate chunk with loaded data
   */
  _populateChunk(chunk, data) {
    if (data.metadata) {
      chunk.metadata = data.metadata;
    }

    if (data.objects && Array.isArray(data.objects)) {
      for (const objData of data.objects) {
        // Objects need to be created by the game - we just store position data
        const position = new THREE.Vector3(
          objData.position.x,
          objData.position.y,
          objData.position.z
        );
        
        // Store raw data for later object creation
        chunk.objects.set(objData.id, {
          object: objData,
          position
        });
      }
    }
  }

  /**
   * Force trim chunks when over limit
   */
  _forceTrimChunks() {
    const sortedChunks = Array.from(this.chunks.entries())
      .filter(([_, chunk]) => chunk.state === 'loaded')
      .sort((a, b) => a[1].lastAccess - b[1].lastAccess);

    const toRemove = sortedChunks.slice(0, this.chunks.size - this.maxLoadedChunks);
    
    for (const [key] of toRemove) {
      if (!this.unloadQueue.includes(key)) {
        this.unloadQueue.push(key);
      }
    }
  }

  /**
   * Update stats
   */
  _updateStats() {
    let loaded = 0;
    let loading = 0;
    let totalObjects = 0;

    for (const chunk of this.chunks.values()) {
      if (chunk.state === 'loaded') loaded++;
      if (chunk.state === 'loading') loading++;
      totalObjects += chunk.objectCount;
    }

    this.stats = {
      loadedChunks: loaded,
      loadingChunks: loading,
      queuedLoads: this.loadQueue.length,
      totalObjects
    };
  }

  /**
   * Get chunk at position (creates if needed)
   */
  getChunkAt(position) {
    const key = this.worldToChunkKey(position);
    return this.chunks.get(key);
  }

  /**
   * Get or create chunk at position
   */
  getOrCreateChunk(position) {
    const key = this.worldToChunkKey(position);
    let chunk = this.chunks.get(key);
    
    if (!chunk) {
      const bounds = this.getChunkBounds(key);
      chunk = new Chunk(key, bounds, this.chunkSize);
      chunk.state = 'loaded';
      this.chunks.set(key, chunk);
      
      if (this.scene) {
        this.scene.add(chunk.meshGroup);
      }
    }
    
    return chunk;
  }

  /**
   * Add object to appropriate chunk
   */
  addObject(id, object, position) {
    const chunk = this.getOrCreateChunk(position);
    chunk.addObject(id, object, position);
    return chunk;
  }

  /**
   * Remove object from its chunk
   */
  removeObject(id, position) {
    const chunk = this.getChunkAt(position);
    if (chunk) {
      return chunk.removeObject(id);
    }
    return false;
  }

  /**
   * Query objects near position across chunks
   */
  queryRadius(position, radius) {
    const results = [];
    const chunkRadius = Math.ceil(radius / this.chunkSize) + 1;
    const centerChunk = this.parseChunkKey(this.worldToChunkKey(position));

    for (let dx = -chunkRadius; dx <= chunkRadius; dx++) {
      for (let dz = -chunkRadius; dz <= chunkRadius; dz++) {
        const key = `${centerChunk.x + dx},${centerChunk.z + dz}`;
        const chunk = this.chunks.get(key);
        
        if (chunk && chunk.state === 'loaded') {
          const chunkResults = chunk.queryRadius(position, radius);
          results.push(...chunkResults);
        }
      }
    }

    return results;
  }

  /**
   * Force load a specific chunk
   */
  async forceLoadChunk(key) {
    if (this.chunks.has(key)) {
      return this.chunks.get(key);
    }

    const bounds = this.getChunkBounds(key);
    const chunk = new Chunk(key, bounds, this.chunkSize);
    chunk.state = 'loading';
    this.chunks.set(key, chunk);

    if (this.scene) {
      this.scene.add(chunk.meshGroup);
    }

    if (this.onChunkLoad) {
      const data = await this.onChunkLoad(key);
      if (data) {
        this._populateChunk(chunk, data);
      }
    }

    chunk.state = 'loaded';
    return chunk;
  }

  /**
   * Mark chunk as dirty (needs saving)
   */
  markDirty(position) {
    const chunk = this.getChunkAt(position);
    if (chunk) {
      chunk.isDirty = true;
    }
  }

  /**
   * Save all dirty chunks
   */
  saveAllDirty() {
    const saved = [];
    
    for (const [key, chunk] of this.chunks) {
      if (chunk.isDirty && this.onChunkUnload) {
        this.onChunkUnload(key, chunk);
        chunk.isDirty = false;
        saved.push(key);
      }
    }
    
    return saved;
  }

  /**
   * Get chunk grid for debug rendering
   */
  createDebugGrid(scene, color = 0x4444ff) {
    const group = new THREE.Group();
    group.name = 'ChunkDebugGrid';

    const material = new THREE.LineBasicMaterial({ color, transparent: true, opacity: 0.3 });

    for (const [key] of this.chunks) {
      const bounds = this.getChunkBounds(key);
      const geometry = new THREE.BoxGeometry(
        this.chunkSize,
        this.worldHeight,
        this.chunkSize
      );
      const edges = new THREE.EdgesGeometry(geometry);
      const line = new THREE.LineSegments(edges, material);
      
      line.position.set(
        (bounds.min.x + bounds.max.x) / 2,
        this.worldHeight / 2,
        (bounds.min.z + bounds.max.z) / 2
      );
      
      group.add(line);
    }

    scene.add(group);
    return group;
  }

  /**
   * Clear all chunks
   */
  clear() {
    for (const [key, chunk] of this.chunks) {
      if (this.scene) {
        this.scene.remove(chunk.meshGroup);
      }
      chunk.clear();
    }
    
    this.chunks.clear();
    this.loadQueue = [];
    this.unloadQueue = [];
    this._lastPlayerChunk = null;
  }
}

export default ChunkManager;

/**
 * Octree - Adaptive spatial partitioning for building systems
 * 
 * Best for: Non-uniform object distribution, true 3D queries, 5000-10000+ components
 * Automatically subdivides dense regions while keeping sparse regions as large nodes
 * 
 * Usage:
 *   const bounds = { min: new THREE.Vector3(-500, 0, -500), max: new THREE.Vector3(500, 100, 500) };
 *   const octree = new Octree(bounds);
 *   octree.insert(buildingPiece, piece.position);
 *   const nearby = octree.queryRadius(position, 15);
 */

import * as THREE from 'three';

export class OctreeNode {
  constructor(bounds, depth = 0, config = {}) {
    this.bounds = bounds; // { min: Vector3, max: Vector3 }
    this.depth = depth;
    this.maxDepth = config.maxDepth ?? 8;
    this.maxObjects = config.maxObjects ?? 8;
    this.minSize = config.minSize ?? 1;
    
    this.objects = [];
    this.children = null;
    this.objectCount = 0;
  }

  /**
   * Get center point of this node
   */
  get center() {
    return new THREE.Vector3()
      .addVectors(this.bounds.min, this.bounds.max)
      .multiplyScalar(0.5);
  }

  /**
   * Get size of this node
   */
  get size() {
    return new THREE.Vector3()
      .subVectors(this.bounds.max, this.bounds.min);
  }

  /**
   * Check if point is within bounds
   */
  containsPoint(point) {
    return (
      point.x >= this.bounds.min.x && point.x <= this.bounds.max.x &&
      point.y >= this.bounds.min.y && point.y <= this.bounds.max.y &&
      point.z >= this.bounds.min.z && point.z <= this.bounds.max.z
    );
  }

  /**
   * Check if bounds intersect a sphere
   */
  intersectsSphere(center, radius) {
    const closest = new THREE.Vector3(
      Math.max(this.bounds.min.x, Math.min(center.x, this.bounds.max.x)),
      Math.max(this.bounds.min.y, Math.min(center.y, this.bounds.max.y)),
      Math.max(this.bounds.min.z, Math.min(center.z, this.bounds.max.z))
    );
    return closest.distanceToSquared(center) <= radius * radius;
  }

  /**
   * Check if bounds intersect another AABB
   */
  intersectsBounds(other) {
    return (
      this.bounds.min.x <= other.max.x && this.bounds.max.x >= other.min.x &&
      this.bounds.min.y <= other.max.y && this.bounds.max.y >= other.min.y &&
      this.bounds.min.z <= other.max.z && this.bounds.max.z >= other.min.z
    );
  }

  /**
   * Insert object at position
   */
  insert(object, position) {
    if (!this.containsPoint(position)) {
      return false;
    }

    // If subdivided, insert into appropriate child
    if (this.children) {
      for (const child of this.children) {
        if (child.insert(object, position)) {
          this.objectCount++;
          return true;
        }
      }
      return false;
    }

    // Add to this node
    this.objects.push({ object, position: position.clone() });
    this.objectCount++;

    // Check if we should subdivide
    const nodeSize = this.size;
    const canSubdivide = (
      this.objects.length > this.maxObjects &&
      this.depth < this.maxDepth &&
      nodeSize.x > this.minSize &&
      nodeSize.y > this.minSize &&
      nodeSize.z > this.minSize
    );

    if (canSubdivide) {
      this._subdivide();
    }

    return true;
  }

  /**
   * Insert object with bounding box (may span multiple nodes)
   */
  insertWithBounds(object, objectBounds) {
    if (!this.intersectsBounds(objectBounds)) {
      return false;
    }

    // If subdivided, try children first
    if (this.children) {
      let inserted = false;
      for (const child of this.children) {
        if (child.insertWithBounds(object, objectBounds)) {
          inserted = true;
        }
      }
      if (inserted) {
        this.objectCount++;
        return true;
      }
    }

    // Store at this level if bounds span multiple children or we're a leaf
    this.objects.push({ 
      object, 
      position: new THREE.Vector3()
        .addVectors(objectBounds.min, objectBounds.max)
        .multiplyScalar(0.5),
      bounds: objectBounds 
    });
    this.objectCount++;
    return true;
  }

  /**
   * Remove object from octree
   */
  remove(object) {
    // Check this node's objects
    const index = this.objects.findIndex(entry => entry.object === object);
    if (index !== -1) {
      this.objects.splice(index, 1);
      this.objectCount--;
      this._tryCollapse();
      return true;
    }

    // Check children
    if (this.children) {
      for (const child of this.children) {
        if (child.remove(object)) {
          this.objectCount--;
          this._tryCollapse();
          return true;
        }
      }
    }

    return false;
  }

  /**
   * Update object position
   */
  update(object, newPosition) {
    if (this.remove(object)) {
      return this.insert(object, newPosition);
    }
    return false;
  }

  /**
   * Query objects within radius of position
   */
  queryRadius(center, radius, results = []) {
    if (!this.intersectsSphere(center, radius)) {
      return results;
    }

    const radiusSq = radius * radius;

    // Check objects at this level
    for (const { object, position } of this.objects) {
      if (position.distanceToSquared(center) <= radiusSq) {
        results.push(object);
      }
    }

    // Check children
    if (this.children) {
      for (const child of this.children) {
        child.queryRadius(center, radius, results);
      }
    }

    return results;
  }

  /**
   * Query objects within AABB bounds
   */
  queryBounds(queryBounds, results = []) {
    if (!this.intersectsBounds(queryBounds)) {
      return results;
    }

    // Check objects at this level
    for (const { object, position } of this.objects) {
      if (
        position.x >= queryBounds.min.x && position.x <= queryBounds.max.x &&
        position.y >= queryBounds.min.y && position.y <= queryBounds.max.y &&
        position.z >= queryBounds.min.z && position.z <= queryBounds.max.z
      ) {
        results.push(object);
      }
    }

    // Check children
    if (this.children) {
      for (const child of this.children) {
        child.queryBounds(queryBounds, results);
      }
    }

    return results;
  }

  /**
   * Find all objects along a ray
   */
  queryRay(ray, maxDistance = Infinity, results = []) {
    // Quick rejection test using ray-box intersection
    const invDir = new THREE.Vector3(
      1 / ray.direction.x,
      1 / ray.direction.y,
      1 / ray.direction.z
    );

    const t1 = (this.bounds.min.x - ray.origin.x) * invDir.x;
    const t2 = (this.bounds.max.x - ray.origin.x) * invDir.x;
    const t3 = (this.bounds.min.y - ray.origin.y) * invDir.y;
    const t4 = (this.bounds.max.y - ray.origin.y) * invDir.y;
    const t5 = (this.bounds.min.z - ray.origin.z) * invDir.z;
    const t6 = (this.bounds.max.z - ray.origin.z) * invDir.z;

    const tmin = Math.max(Math.min(t1, t2), Math.min(t3, t4), Math.min(t5, t6));
    const tmax = Math.min(Math.max(t1, t2), Math.max(t3, t4), Math.max(t5, t6));

    if (tmax < 0 || tmin > tmax || tmin > maxDistance) {
      return results;
    }

    // Check objects at this level
    for (const { object, position } of this.objects) {
      const closestPoint = new THREE.Vector3();
      ray.closestPointToPoint(position, closestPoint);
      const dist = position.distanceTo(closestPoint);
      const rayDist = ray.origin.distanceTo(closestPoint);
      
      if (dist < 1 && rayDist <= maxDistance) { // 1 unit tolerance
        results.push({ object, distance: rayDist });
      }
    }

    // Check children
    if (this.children) {
      for (const child of this.children) {
        child.queryRay(ray, maxDistance, results);
      }
    }

    return results;
  }

  /**
   * Find nearest object to position
   */
  findNearest(position, maxDistance = Infinity) {
    let nearest = null;
    let nearestDistSq = maxDistance * maxDistance;

    const search = (node) => {
      // Check objects at this level
      for (const { object, position: objPos } of node.objects) {
        const distSq = objPos.distanceToSquared(position);
        if (distSq < nearestDistSq) {
          nearestDistSq = distSq;
          nearest = object;
        }
      }

      // Check children, prioritizing by distance to bounds
      if (node.children) {
        const sortedChildren = [...node.children].sort((a, b) => {
          const distA = this._distToBounds(position, a.bounds);
          const distB = this._distToBounds(position, b.bounds);
          return distA - distB;
        });

        for (const child of sortedChildren) {
          // Skip if closest possible point is farther than current best
          const minDist = this._distToBounds(position, child.bounds);
          if (minDist * minDist >= nearestDistSq) continue;
          
          search(child);
        }
      }
    };

    search(this);
    return nearest;
  }

  /**
   * Get all objects in octree
   */
  getAllObjects(results = []) {
    for (const { object } of this.objects) {
      results.push(object);
    }

    if (this.children) {
      for (const child of this.children) {
        child.getAllObjects(results);
      }
    }

    return results;
  }

  /**
   * Subdivide this node into 8 children
   */
  _subdivide() {
    const { min, max } = this.bounds;
    const mid = this.center;
    
    this.children = [];
    
    // Create 8 children for each octant
    const octants = [
      { min: new THREE.Vector3(min.x, min.y, min.z), max: new THREE.Vector3(mid.x, mid.y, mid.z) },
      { min: new THREE.Vector3(mid.x, min.y, min.z), max: new THREE.Vector3(max.x, mid.y, mid.z) },
      { min: new THREE.Vector3(min.x, mid.y, min.z), max: new THREE.Vector3(mid.x, max.y, mid.z) },
      { min: new THREE.Vector3(mid.x, mid.y, min.z), max: new THREE.Vector3(max.x, max.y, mid.z) },
      { min: new THREE.Vector3(min.x, min.y, mid.z), max: new THREE.Vector3(mid.x, mid.y, max.z) },
      { min: new THREE.Vector3(mid.x, min.y, mid.z), max: new THREE.Vector3(max.x, mid.y, max.z) },
      { min: new THREE.Vector3(min.x, mid.y, mid.z), max: new THREE.Vector3(mid.x, max.y, max.z) },
      { min: new THREE.Vector3(mid.x, mid.y, mid.z), max: new THREE.Vector3(max.x, max.y, max.z) }
    ];

    for (const octant of octants) {
      this.children.push(new OctreeNode(octant, this.depth + 1, {
        maxDepth: this.maxDepth,
        maxObjects: this.maxObjects,
        minSize: this.minSize
      }));
    }

    // Redistribute objects to children
    const objectsToRedistribute = this.objects;
    this.objects = [];

    for (const { object, position } of objectsToRedistribute) {
      let inserted = false;
      for (const child of this.children) {
        if (child.containsPoint(position)) {
          child.objects.push({ object, position });
          child.objectCount++;
          inserted = true;
          break;
        }
      }
      // Keep objects that don't fit in children (edge cases)
      if (!inserted) {
        this.objects.push({ object, position });
      }
    }
  }

  /**
   * Try to collapse children back into this node
   */
  _tryCollapse() {
    if (!this.children) return;

    // Check if we should collapse
    let totalObjects = this.objects.length;
    for (const child of this.children) {
      if (child.children) return; // Don't collapse if any child is subdivided
      totalObjects += child.objects.length;
    }

    if (totalObjects <= this.maxObjects / 2) {
      // Collect all objects from children
      for (const child of this.children) {
        this.objects.push(...child.objects);
      }
      this.children = null;
    }
  }

  /**
   * Distance from point to bounds
   */
  _distToBounds(point, bounds) {
    const closest = new THREE.Vector3(
      Math.max(bounds.min.x, Math.min(point.x, bounds.max.x)),
      Math.max(bounds.min.y, Math.min(point.y, bounds.max.y)),
      Math.max(bounds.min.z, Math.min(point.z, bounds.max.z))
    );
    return point.distanceTo(closest);
  }

  /**
   * Get statistics about octree structure
   */
  getStats() {
    let nodeCount = 1;
    let leafCount = 0;
    let maxDepthReached = this.depth;
    let objectsInLeaves = 0;
    let objectsInBranches = this.objects.length;

    const traverse = (node) => {
      if (node.children) {
        objectsInBranches += node.objects.length;
        for (const child of node.children) {
          nodeCount++;
          maxDepthReached = Math.max(maxDepthReached, child.depth);
          traverse(child);
        }
      } else {
        leafCount++;
        objectsInLeaves += node.objects.length;
      }
    };

    if (this.children) {
      for (const child of this.children) {
        nodeCount++;
        maxDepthReached = Math.max(maxDepthReached, child.depth);
        traverse(child);
      }
    } else {
      leafCount = 1;
      objectsInLeaves = this.objects.length;
      objectsInBranches = 0;
    }

    return {
      nodeCount,
      leafCount,
      maxDepth: maxDepthReached,
      totalObjects: this.objectCount,
      objectsInLeaves,
      objectsInBranches,
      avgObjectsPerLeaf: leafCount > 0 ? objectsInLeaves / leafCount : 0
    };
  }

  /**
   * Clear all data
   */
  clear() {
    this.objects = [];
    this.children = null;
    this.objectCount = 0;
  }

  /**
   * Create debug visualization
   */
  createDebugMesh(scene, options = {}) {
    const {
      showEmpty = false,
      leafColor = 0x00ff00,
      branchColor = 0x0088ff,
      opacity = 0.2
    } = options;

    const group = new THREE.Group();
    group.name = 'OctreeDebug';

    const traverse = (node) => {
      const hasObjects = node.objects.length > 0;
      const isLeaf = !node.children;

      if (hasObjects || showEmpty) {
        const size = node.size;
        const geometry = new THREE.BoxGeometry(size.x, size.y, size.z);
        const edges = new THREE.EdgesGeometry(geometry);
        const material = new THREE.LineBasicMaterial({
          color: isLeaf ? leafColor : branchColor,
          transparent: true,
          opacity: hasObjects ? opacity : opacity * 0.3
        });
        const line = new THREE.LineSegments(edges, material);
        line.position.copy(node.center);
        group.add(line);
      }

      if (node.children) {
        for (const child of node.children) {
          traverse(child);
        }
      }
    };

    traverse(this);
    scene.add(group);
    return group;
  }
}

/**
 * Convenience wrapper with common configuration
 */
export class Octree extends OctreeNode {
  constructor(bounds, config = {}) {
    super(bounds, 0, {
      maxDepth: config.maxDepth ?? 8,
      maxObjects: config.maxObjects ?? 8,
      minSize: config.minSize ?? 1
    });
  }

  /**
   * Create octree with automatic bounds from objects
   */
  static fromObjects(objects, getPosition, padding = 10) {
    if (objects.length === 0) {
      return new Octree({
        min: new THREE.Vector3(-100, -100, -100),
        max: new THREE.Vector3(100, 100, 100)
      });
    }

    const min = new THREE.Vector3(Infinity, Infinity, Infinity);
    const max = new THREE.Vector3(-Infinity, -Infinity, -Infinity);

    for (const obj of objects) {
      const pos = getPosition(obj);
      min.min(pos);
      max.max(pos);
    }

    min.subScalar(padding);
    max.addScalar(padding);

    const octree = new Octree({ min, max });
    
    for (const obj of objects) {
      octree.insert(obj, getPosition(obj));
    }

    return octree;
  }
}

export default Octree;

/**
 * PerformanceProfiler - Benchmarking utilities for building systems
 * 
 * Measures frame time, spatial query performance, memory usage,
 * and helps identify bottlenecks in building mechanics.
 * 
 * Usage:
 *   const profiler = new PerformanceProfiler();
 *   profiler.startFrame();
 *   // ... game logic ...
 *   profiler.endFrame();
 *   console.log(profiler.getReport());
 */

export class PerformanceProfiler {
  constructor(options = {}) {
    this.historySize = options.historySize ?? 120; // ~2 seconds at 60fps
    this.warnThresholds = {
      frameTime: options.frameTimeWarn ?? 16.67, // 60fps
      queryTime: options.queryTimeWarn ?? 1,      // 1ms per query
      memoryMB: options.memoryWarn ?? 500         // 500MB
    };

    this.frameHistory = [];
    this.queryHistory = [];
    this.customTimers = new Map();
    this.counters = new Map();
    
    this._frameStart = 0;
    this._currentFrame = null;
    this._enabled = true;
  }

  /**
   * Enable/disable profiling
   */
  setEnabled(enabled) {
    this._enabled = enabled;
  }

  /**
   * Start frame measurement
   */
  startFrame() {
    if (!this._enabled) return;
    
    this._frameStart = performance.now();
    this._currentFrame = {
      startTime: this._frameStart,
      sections: {},
      queries: []
    };
  }

  /**
   * End frame measurement
   */
  endFrame() {
    if (!this._enabled || !this._currentFrame) return;

    const frameTime = performance.now() - this._frameStart;
    this._currentFrame.totalTime = frameTime;

    this.frameHistory.push(this._currentFrame);
    if (this.frameHistory.length > this.historySize) {
      this.frameHistory.shift();
    }

    this._currentFrame = null;
    return frameTime;
  }

  /**
   * Start timing a named section
   */
  startSection(name) {
    if (!this._enabled || !this._currentFrame) return;
    
    this._currentFrame.sections[name] = {
      start: performance.now(),
      end: null
    };
  }

  /**
   * End timing a named section
   */
  endSection(name) {
    if (!this._enabled || !this._currentFrame) return;
    
    const section = this._currentFrame.sections[name];
    if (section) {
      section.end = performance.now();
      section.duration = section.end - section.start;
    }
  }

  /**
   * Time a function execution
   */
  time(name, fn) {
    if (!this._enabled) return fn();

    const start = performance.now();
    const result = fn();
    const duration = performance.now() - start;

    if (this._currentFrame) {
      this._currentFrame.sections[name] = { duration };
    }

    return result;
  }

  /**
   * Time an async function execution
   */
  async timeAsync(name, fn) {
    if (!this._enabled) return fn();

    const start = performance.now();
    const result = await fn();
    const duration = performance.now() - start;

    if (this._currentFrame) {
      this._currentFrame.sections[name] = { duration };
    }

    return result;
  }

  /**
   * Record a spatial query for analysis
   */
  recordQuery(type, candidateCount, resultCount, timeMs) {
    if (!this._enabled) return;

    const query = { type, candidateCount, resultCount, timeMs };
    
    if (this._currentFrame) {
      this._currentFrame.queries.push(query);
    }

    this.queryHistory.push(query);
    if (this.queryHistory.length > this.historySize * 10) {
      this.queryHistory.shift();
    }
  }

  /**
   * Increment a counter
   */
  count(name, amount = 1) {
    if (!this._enabled) return;
    
    const current = this.counters.get(name) || 0;
    this.counters.set(name, current + amount);
  }

  /**
   * Reset a counter
   */
  resetCount(name) {
    this.counters.set(name, 0);
  }

  /**
   * Get average frame time
   */
  getAverageFrameTime() {
    if (this.frameHistory.length === 0) return 0;
    
    const sum = this.frameHistory.reduce((acc, f) => acc + f.totalTime, 0);
    return sum / this.frameHistory.length;
  }

  /**
   * Get current FPS estimate
   */
  getFPS() {
    const avgFrameTime = this.getAverageFrameTime();
    return avgFrameTime > 0 ? 1000 / avgFrameTime : 0;
  }

  /**
   * Get section timing statistics
   */
  getSectionStats(sectionName) {
    const times = this.frameHistory
      .map(f => f.sections[sectionName]?.duration)
      .filter(t => t !== undefined);

    if (times.length === 0) {
      return { avg: 0, min: 0, max: 0, count: 0 };
    }

    return {
      avg: times.reduce((a, b) => a + b, 0) / times.length,
      min: Math.min(...times),
      max: Math.max(...times),
      count: times.length
    };
  }

  /**
   * Get query statistics
   */
  getQueryStats() {
    if (this.queryHistory.length === 0) {
      return { avgTime: 0, avgCandidates: 0, avgResults: 0, count: 0 };
    }

    const stats = {
      avgTime: 0,
      avgCandidates: 0,
      avgResults: 0,
      count: this.queryHistory.length,
      byType: {}
    };

    for (const q of this.queryHistory) {
      stats.avgTime += q.timeMs;
      stats.avgCandidates += q.candidateCount;
      stats.avgResults += q.resultCount;

      if (!stats.byType[q.type]) {
        stats.byType[q.type] = { time: 0, count: 0 };
      }
      stats.byType[q.type].time += q.timeMs;
      stats.byType[q.type].count++;
    }

    stats.avgTime /= stats.count;
    stats.avgCandidates /= stats.count;
    stats.avgResults /= stats.count;

    for (const type in stats.byType) {
      stats.byType[type].avgTime = stats.byType[type].time / stats.byType[type].count;
    }

    return stats;
  }

  /**
   * Get memory usage (if available)
   */
  getMemoryUsage() {
    if (performance.memory) {
      return {
        usedHeapMB: performance.memory.usedJSHeapSize / 1024 / 1024,
        totalHeapMB: performance.memory.totalJSHeapSize / 1024 / 1024,
        limitMB: performance.memory.jsHeapSizeLimit / 1024 / 1024
      };
    }
    return null;
  }

  /**
   * Get comprehensive report
   */
  getReport() {
    const avgFrameTime = this.getAverageFrameTime();
    const fps = this.getFPS();
    const memory = this.getMemoryUsage();
    const queryStats = this.getQueryStats();

    // Gather all section names
    const sectionNames = new Set();
    for (const frame of this.frameHistory) {
      for (const name of Object.keys(frame.sections)) {
        sectionNames.add(name);
      }
    }

    const sections = {};
    for (const name of sectionNames) {
      sections[name] = this.getSectionStats(name);
    }

    // Warnings
    const warnings = [];
    if (avgFrameTime > this.warnThresholds.frameTime) {
      warnings.push(`Frame time ${avgFrameTime.toFixed(2)}ms exceeds ${this.warnThresholds.frameTime}ms threshold`);
    }
    if (queryStats.avgTime > this.warnThresholds.queryTime) {
      warnings.push(`Query time ${queryStats.avgTime.toFixed(2)}ms exceeds ${this.warnThresholds.queryTime}ms threshold`);
    }
    if (memory && memory.usedHeapMB > this.warnThresholds.memoryMB) {
      warnings.push(`Memory usage ${memory.usedHeapMB.toFixed(0)}MB exceeds ${this.warnThresholds.memoryMB}MB threshold`);
    }

    return {
      fps: Math.round(fps),
      frameTime: {
        avg: avgFrameTime,
        min: Math.min(...this.frameHistory.map(f => f.totalTime)),
        max: Math.max(...this.frameHistory.map(f => f.totalTime))
      },
      sections,
      queries: queryStats,
      memory,
      counters: Object.fromEntries(this.counters),
      warnings,
      frameCount: this.frameHistory.length
    };
  }

  /**
   * Format report as string for console
   */
  formatReport() {
    const report = this.getReport();
    const lines = [
      `=== Performance Report ===`,
      `FPS: ${report.fps} (${report.frameTime.avg.toFixed(2)}ms avg)`,
      `Frame Range: ${report.frameTime.min.toFixed(2)}ms - ${report.frameTime.max.toFixed(2)}ms`,
      ``
    ];

    if (Object.keys(report.sections).length > 0) {
      lines.push(`Sections:`);
      for (const [name, stats] of Object.entries(report.sections)) {
        lines.push(`  ${name}: ${stats.avg.toFixed(2)}ms avg (${stats.min.toFixed(2)}-${stats.max.toFixed(2)})`);
      }
      lines.push(``);
    }

    if (report.queries.count > 0) {
      lines.push(`Queries: ${report.queries.count} total`);
      lines.push(`  Avg Time: ${report.queries.avgTime.toFixed(3)}ms`);
      lines.push(`  Avg Candidates: ${report.queries.avgCandidates.toFixed(0)}`);
      lines.push(`  Avg Results: ${report.queries.avgResults.toFixed(0)}`);
      lines.push(``);
    }

    if (report.memory) {
      lines.push(`Memory: ${report.memory.usedHeapMB.toFixed(0)}MB / ${report.memory.limitMB.toFixed(0)}MB`);
      lines.push(``);
    }

    if (Object.keys(report.counters).length > 0) {
      lines.push(`Counters:`);
      for (const [name, value] of Object.entries(report.counters)) {
        lines.push(`  ${name}: ${value}`);
      }
      lines.push(``);
    }

    if (report.warnings.length > 0) {
      lines.push(`⚠️ Warnings:`);
      for (const warning of report.warnings) {
        lines.push(`  - ${warning}`);
      }
    }

    return lines.join('\n');
  }

  /**
   * Reset all data
   */
  reset() {
    this.frameHistory = [];
    this.queryHistory = [];
    this.counters.clear();
    this._currentFrame = null;
  }

  /**
   * Create on-screen debug display
   */
  createOverlay(container = document.body) {
    const overlay = document.createElement('div');
    overlay.id = 'perf-overlay';
    overlay.style.cssText = `
      position: fixed;
      top: 10px;
      left: 10px;
      background: rgba(0, 0, 0, 0.8);
      color: #0f0;
      font-family: monospace;
      font-size: 12px;
      padding: 10px;
      border-radius: 4px;
      z-index: 10000;
      pointer-events: none;
      white-space: pre;
    `;
    container.appendChild(overlay);

    const update = () => {
      if (!this._enabled) {
        overlay.style.display = 'none';
        return;
      }
      overlay.style.display = 'block';

      const report = this.getReport();
      const fpsColor = report.fps >= 55 ? '#0f0' : report.fps >= 30 ? '#ff0' : '#f00';
      
      overlay.innerHTML = `
<span style="color: ${fpsColor}">FPS: ${report.fps}</span>
Frame: ${report.frameTime.avg.toFixed(1)}ms
${report.memory ? `Mem: ${report.memory.usedHeapMB.toFixed(0)}MB` : ''}
${report.queries.count > 0 ? `Queries: ${report.queries.avgTime.toFixed(2)}ms avg` : ''}
${report.warnings.length > 0 ? `<span style="color: #f00">⚠ ${report.warnings.length} warnings</span>` : ''}
      `.trim();
    };

    // Update every 100ms
    const intervalId = setInterval(update, 100);

    return {
      element: overlay,
      destroy: () => {
        clearInterval(intervalId);
        overlay.remove();
      }
    };
  }
}

/**
 * Benchmark utility for comparing implementations
 */
export class Benchmark {
  constructor(name) {
    this.name = name;
    this.results = [];
  }

  /**
   * Run a function multiple times and record results
   */
  run(fn, iterations = 1000, warmup = 100) {
    // Warmup
    for (let i = 0; i < warmup; i++) {
      fn();
    }

    // Actual benchmark
    const times = [];
    for (let i = 0; i < iterations; i++) {
      const start = performance.now();
      fn();
      times.push(performance.now() - start);
    }

    const result = {
      iterations,
      total: times.reduce((a, b) => a + b, 0),
      avg: times.reduce((a, b) => a + b, 0) / times.length,
      min: Math.min(...times),
      max: Math.max(...times),
      median: this._median(times),
      p95: this._percentile(times, 95),
      p99: this._percentile(times, 99)
    };

    this.results.push(result);
    return result;
  }

  /**
   * Compare multiple implementations
   */
  static compare(benchmarks) {
    const results = [];
    
    for (const { name, fn, iterations } of benchmarks) {
      const bench = new Benchmark(name);
      const result = bench.run(fn, iterations);
      results.push({ name, ...result });
    }

    // Sort by avg time
    results.sort((a, b) => a.avg - b.avg);

    // Calculate relative performance
    const baseline = results[0].avg;
    for (const result of results) {
      result.relative = result.avg / baseline;
    }

    return results;
  }

  /**
   * Format comparison results
   */
  static formatComparison(results) {
    const lines = ['=== Benchmark Comparison ===', ''];
    
    for (const r of results) {
      lines.push(`${r.name}:`);
      lines.push(`  Avg: ${r.avg.toFixed(4)}ms (${r.relative.toFixed(2)}x)`);
      lines.push(`  Min: ${r.min.toFixed(4)}ms, Max: ${r.max.toFixed(4)}ms`);
      lines.push(`  P95: ${r.p95.toFixed(4)}ms, P99: ${r.p99.toFixed(4)}ms`);
      lines.push('');
    }

    return lines.join('\n');
  }

  _median(arr) {
    const sorted = [...arr].sort((a, b) => a - b);
    const mid = Math.floor(sorted.length / 2);
    return sorted.length % 2 ? sorted[mid] : (sorted[mid - 1] + sorted[mid]) / 2;
  }

  _percentile(arr, p) {
    const sorted = [...arr].sort((a, b) => a - b);
    const index = Math.ceil((p / 100) * sorted.length) - 1;
    return sorted[Math.max(0, index)];
  }
}

/**
 * Wrapper to profile spatial structure operations
 */
export function profileSpatialStructure(structure, profiler) {
  return {
    insert: (object, position) => {
      profiler.startSection('insert');
      const result = structure.insert(object, position);
      profiler.endSection('insert');
      return result;
    },

    remove: (object) => {
      profiler.startSection('remove');
      const result = structure.remove(object);
      profiler.endSection('remove');
      return result;
    },

    queryRadius: (position, radius) => {
      const start = performance.now();
      profiler.startSection('queryRadius');
      const results = structure.queryRadius(position, radius);
      profiler.endSection('queryRadius');
      
      const timeMs = performance.now() - start;
      profiler.recordQuery('radius', structure.objectCount || 0, results.length, timeMs);
      
      return results;
    },

    queryBounds: (bounds) => {
      const start = performance.now();
      profiler.startSection('queryBounds');
      const results = structure.queryBounds(bounds);
      profiler.endSection('queryBounds');
      
      const timeMs = performance.now() - start;
      profiler.recordQuery('bounds', structure.objectCount || 0, results.length, timeMs);
      
      return results;
    }
  };
}

export default PerformanceProfiler;

/**
 * SpatialHashGrid - Uniform spatial partitioning for building systems
 * 
 * Best for: Uniform object distribution, 2D/2.5D games, <5000 components
 * Time complexity: O(1) cell lookup + O(k) objects per cell
 * 
 * Usage:
 *   const grid = new SpatialHashGrid(10); // 10-unit cells
 *   grid.insert(buildingPiece, piece.position);
 *   const nearby = grid.queryRadius(position, 15);
 */

import * as THREE from 'three';

export class SpatialHashGrid {
  constructor(cellSize = 10) {
    this.cellSize = cellSize;
    this.cells = new Map();
    this.objectCells = new Map(); // object -> Set of cell keys (for objects spanning cells)
    this.objectCount = 0;
  }

  /**
   * Generate cell key from world coordinates
   */
  _hash(x, y, z) {
    const cx = Math.floor(x / this.cellSize);
    const cy = Math.floor(y / this.cellSize);
    const cz = Math.floor(z / this.cellSize);
    return `${cx},${cy},${cz}`;
  }

  /**
   * Parse cell key back to cell coordinates
   */
  _parseKey(key) {
    const [x, y, z] = key.split(',').map(Number);
    return { x, y, z };
  }

  /**
   * Get cell world bounds from key
   */
  _getCellBounds(key) {
    const { x, y, z } = this._parseKey(key);
    return {
      min: new THREE.Vector3(
        x * this.cellSize,
        y * this.cellSize,
        z * this.cellSize
      ),
      max: new THREE.Vector3(
        (x + 1) * this.cellSize,
        (y + 1) * this.cellSize,
        (z + 1) * this.cellSize
      )
    };
  }

  /**
   * Insert object at position (point-based)
   */
  insert(object, position) {
    const key = this._hash(position.x, position.y, position.z);
    
    if (!this.cells.has(key)) {
      this.cells.set(key, new Set());
    }
    this.cells.get(key).add(object);
    
    // Track which cells contain this object
    if (!this.objectCells.has(object)) {
      this.objectCells.set(object, new Set());
      this.objectCount++;
    }
    this.objectCells.get(object).add(key);
    
    return key;
  }

  /**
   * Insert object with bounding box (spans multiple cells)
   */
  insertWithBounds(object, bounds) {
    const minCell = {
      x: Math.floor(bounds.min.x / this.cellSize),
      y: Math.floor(bounds.min.y / this.cellSize),
      z: Math.floor(bounds.min.z / this.cellSize)
    };
    const maxCell = {
      x: Math.floor(bounds.max.x / this.cellSize),
      y: Math.floor(bounds.max.y / this.cellSize),
      z: Math.floor(bounds.max.z / this.cellSize)
    };

    if (!this.objectCells.has(object)) {
      this.objectCells.set(object, new Set());
      this.objectCount++;
    }

    for (let x = minCell.x; x <= maxCell.x; x++) {
      for (let y = minCell.y; y <= maxCell.y; y++) {
        for (let z = minCell.z; z <= maxCell.z; z++) {
          const key = `${x},${y},${z}`;
          if (!this.cells.has(key)) {
            this.cells.set(key, new Set());
          }
          this.cells.get(key).add(object);
          this.objectCells.get(object).add(key);
        }
      }
    }
  }

  /**
   * Remove object from grid
   */
  remove(object) {
    const cellKeys = this.objectCells.get(object);
    if (!cellKeys) return false;

    for (const key of cellKeys) {
      const cell = this.cells.get(key);
      if (cell) {
        cell.delete(object);
        if (cell.size === 0) {
          this.cells.delete(key);
        }
      }
    }

    this.objectCells.delete(object);
    this.objectCount--;
    return true;
  }

  /**
   * Update object position (remove and re-insert)
   */
  update(object, newPosition) {
    this.remove(object);
    return this.insert(object, newPosition);
  }

  /**
   * Update object with new bounds
   */
  updateWithBounds(object, newBounds) {
    this.remove(object);
    this.insertWithBounds(object, newBounds);
  }

  /**
   * Query all objects within radius of position
   */
  queryRadius(position, radius) {
    const results = new Set();
    const cellRadius = Math.ceil(radius / this.cellSize);
    const centerCell = {
      x: Math.floor(position.x / this.cellSize),
      y: Math.floor(position.y / this.cellSize),
      z: Math.floor(position.z / this.cellSize)
    };

    const radiusSq = radius * radius;

    for (let dx = -cellRadius; dx <= cellRadius; dx++) {
      for (let dy = -cellRadius; dy <= cellRadius; dy++) {
        for (let dz = -cellRadius; dz <= cellRadius; dz++) {
          const key = `${centerCell.x + dx},${centerCell.y + dy},${centerCell.z + dz}`;
          const cell = this.cells.get(key);
          
          if (cell) {
            for (const object of cell) {
              // Get object position for distance check
              const objPos = object.position || object;
              if (objPos.distanceToSquared) {
                if (objPos.distanceToSquared(position) <= radiusSq) {
                  results.add(object);
                }
              } else {
                results.add(object);
              }
            }
          }
        }
      }
    }

    return Array.from(results);
  }

  /**
   * Query all objects within AABB bounds
   */
  queryBounds(bounds) {
    const results = new Set();
    const minCell = {
      x: Math.floor(bounds.min.x / this.cellSize),
      y: Math.floor(bounds.min.y / this.cellSize),
      z: Math.floor(bounds.min.z / this.cellSize)
    };
    const maxCell = {
      x: Math.floor(bounds.max.x / this.cellSize),
      y: Math.floor(bounds.max.y / this.cellSize),
      z: Math.floor(bounds.max.z / this.cellSize)
    };

    for (let x = minCell.x; x <= maxCell.x; x++) {
      for (let y = minCell.y; y <= maxCell.y; y++) {
        for (let z = minCell.z; z <= maxCell.z; z++) {
          const key = `${x},${y},${z}`;
          const cell = this.cells.get(key);
          if (cell) {
            for (const object of cell) {
              results.add(object);
            }
          }
        }
      }
    }

    return Array.from(results);
  }

  /**
   * Query single cell by position
   */
  queryCell(position) {
    const key = this._hash(position.x, position.y, position.z);
    const cell = this.cells.get(key);
    return cell ? Array.from(cell) : [];
  }

  /**
   * Find nearest object to position
   */
  findNearest(position, maxRadius = Infinity) {
    let nearest = null;
    let nearestDistSq = maxRadius * maxRadius;

    // Expand search outward from center cell
    let searchRadius = 0;
    const centerCell = {
      x: Math.floor(position.x / this.cellSize),
      y: Math.floor(position.y / this.cellSize),
      z: Math.floor(position.z / this.cellSize)
    };

    while (searchRadius * this.cellSize <= maxRadius || searchRadius === 0) {
      for (let dx = -searchRadius; dx <= searchRadius; dx++) {
        for (let dy = -searchRadius; dy <= searchRadius; dy++) {
          for (let dz = -searchRadius; dz <= searchRadius; dz++) {
            // Only check shell of current radius
            if (Math.abs(dx) !== searchRadius && 
                Math.abs(dy) !== searchRadius && 
                Math.abs(dz) !== searchRadius) {
              continue;
            }

            const key = `${centerCell.x + dx},${centerCell.y + dy},${centerCell.z + dz}`;
            const cell = this.cells.get(key);
            
            if (cell) {
              for (const object of cell) {
                const objPos = object.position || object;
                if (objPos.distanceToSquared) {
                  const distSq = objPos.distanceToSquared(position);
                  if (distSq < nearestDistSq) {
                    nearestDistSq = distSq;
                    nearest = object;
                  }
                }
              }
            }
          }
        }
      }

      // If we found something and searched far enough to be sure
      if (nearest && (searchRadius + 1) * this.cellSize > Math.sqrt(nearestDistSq)) {
        break;
      }
      searchRadius++;
    }

    return nearest;
  }

  /**
   * Raycast through grid cells
   */
  raycast(origin, direction, maxDistance = 1000) {
    const results = [];
    const ray = new THREE.Ray(origin, direction.normalize());
    
    // Simple approach: collect all cells the ray passes through
    const step = this.cellSize / 2;
    const steps = Math.ceil(maxDistance / step);
    const checkedCells = new Set();
    const point = origin.clone();

    for (let i = 0; i <= steps; i++) {
      const key = this._hash(point.x, point.y, point.z);
      
      if (!checkedCells.has(key)) {
        checkedCells.add(key);
        const cell = this.cells.get(key);
        
        if (cell) {
          for (const object of cell) {
            if (!results.includes(object)) {
              results.push(object);
            }
          }
        }
      }
      
      point.addScaledVector(direction, step);
    }

    return results;
  }

  /**
   * Get statistics about grid usage
   */
  getStats() {
    let totalObjects = 0;
    let maxPerCell = 0;
    let minPerCell = Infinity;
    let emptyCells = 0;

    for (const cell of this.cells.values()) {
      const count = cell.size;
      totalObjects += count;
      maxPerCell = Math.max(maxPerCell, count);
      minPerCell = Math.min(minPerCell, count);
      if (count === 0) emptyCells++;
    }

    return {
      cellCount: this.cells.size,
      objectCount: this.objectCount,
      cellSize: this.cellSize,
      maxObjectsPerCell: maxPerCell,
      minObjectsPerCell: minPerCell === Infinity ? 0 : minPerCell,
      avgObjectsPerCell: this.cells.size > 0 ? totalObjects / this.cells.size : 0,
      emptyCells,
      memoryEstimate: this.cells.size * 100 + this.objectCount * 50 // rough bytes
    };
  }

  /**
   * Clear all data
   */
  clear() {
    this.cells.clear();
    this.objectCells.clear();
    this.objectCount = 0;
  }

  /**
   * Visualize grid (debug)
   */
  createDebugMesh(scene, color = 0x00ff00) {
    const material = new THREE.LineBasicMaterial({ color, transparent: true, opacity: 0.3 });
    const group = new THREE.Group();
    group.name = 'SpatialGridDebug';

    for (const key of this.cells.keys()) {
      const bounds = this._getCellBounds(key);
      const geometry = new THREE.BoxGeometry(
        this.cellSize,
        this.cellSize,
        this.cellSize
      );
      const edges = new THREE.EdgesGeometry(geometry);
      const line = new THREE.LineSegments(edges, material);
      
      line.position.set(
        (bounds.min.x + bounds.max.x) / 2,
        (bounds.min.y + bounds.max.y) / 2,
        (bounds.min.z + bounds.max.z) / 2
      );
      
      group.add(line);
    }

    scene.add(group);
    return group;
  }
}

/**
 * 2D variant for terrain-based games (ignores Y axis)
 */
export class SpatialHashGrid2D {
  constructor(cellSize = 10) {
    this.cellSize = cellSize;
    this.cells = new Map();
    this.objectCells = new Map();
    this.objectCount = 0;
  }

  _hash(x, z) {
    const cx = Math.floor(x / this.cellSize);
    const cz = Math.floor(z / this.cellSize);
    return `${cx},${cz}`;
  }

  insert(object, position) {
    const key = this._hash(position.x, position.z);
    
    if (!this.cells.has(key)) {
      this.cells.set(key, new Set());
    }
    this.cells.get(key).add(object);
    
    if (!this.objectCells.has(object)) {
      this.objectCells.set(object, new Set());
      this.objectCount++;
    }
    this.objectCells.get(object).add(key);
    
    return key;
  }

  remove(object) {
    const cellKeys = this.objectCells.get(object);
    if (!cellKeys) return false;

    for (const key of cellKeys) {
      const cell = this.cells.get(key);
      if (cell) {
        cell.delete(object);
        if (cell.size === 0) {
          this.cells.delete(key);
        }
      }
    }

    this.objectCells.delete(object);
    this.objectCount--;
    return true;
  }

  queryRadius(position, radius) {
    const results = new Set();
    const cellRadius = Math.ceil(radius / this.cellSize);
    const centerX = Math.floor(position.x / this.cellSize);
    const centerZ = Math.floor(position.z / this.cellSize);
    const radiusSq = radius * radius;

    for (let dx = -cellRadius; dx <= cellRadius; dx++) {
      for (let dz = -cellRadius; dz <= cellRadius; dz++) {
        const key = `${centerX + dx},${centerZ + dz}`;
        const cell = this.cells.get(key);
        
        if (cell) {
          for (const object of cell) {
            const objPos = object.position || object;
            const distSq = (objPos.x - position.x) ** 2 + (objPos.z - position.z) ** 2;
            if (distSq <= radiusSq) {
              results.add(object);
            }
          }
        }
      }
    }

    return Array.from(results);
  }

  clear() {
    this.cells.clear();
    this.objectCells.clear();
    this.objectCount = 0;
  }
}

export default SpatialHashGrid;