src/ai/crowd.js

// No direct THREE.js import needed

/**
 * Crowd Simulation with Collision Avoidance for Villagers
 * 
 * This implementation uses a combination of steering behaviors and spatial partitioning
 * to efficiently manage crowd simulation with collision avoidance for multiple villagers.
 */

class CrowdManager {
    constructor() {
        this.villagers = [];
        this.spatialGrid = new SpatialGrid(100, 100, 5); // 100x100 grid with 5 unit cells
    }

    /**
     * Add a villager to the crowd simulation
     * @param {Villager} villager - The villager to add
     */
    addVillager(villager) {
        this.villagers.push(villager);
        this.spatialGrid.insert(villager);
    }

    /**
     * Update all villagers in the crowd simulation
     * @param {number} deltaTime - Time since last frame
     */
    update(deltaTime) {
        // Update spatial grid
        this.spatialGrid.clear();
        for (const villager of this.villagers) {
            this.spatialGrid.insert(villager);
        }

        // Update each villager
        for (const villager of this.villagers) {
            // Get nearby villagers for collision avoidance
            const nearby = this.spatialGrid.query(villager.position, 10);

            // Calculate steering forces
            const avoidanceForce = this.calculateAvoidanceForce(villager, nearby);
            const steeringForce = this.calculateSteeringForce(villager);

            // Apply forces to velocity (using arrays)
            this.addScaledVector(villager.velocity, avoidanceForce, deltaTime);
            this.addScaledVector(villager.velocity, steeringForce, deltaTime);

            // Limit velocity
            const speed = this.calculateVectorLength(villager.velocity);
            if (speed > villager.maxSpeed) {
                this.normalizeVector(villager.velocity);
                this.scaleVectorInPlace(villager.velocity, villager.maxSpeed);
            }

            // Update position
            const moveVector = this.scaleVector(villager.velocity, deltaTime);
            this.addVectors(villager.position, moveVector);
        }
    }

    /**
     * Calculate avoidance force to prevent collisions
     * @param {Villager} villager - The villager to calculate for
     * @param {Array<Villager>} nearby - Nearby villagers
     * @returns {Array} Avoidance force as [x, y, z]
     */
    calculateAvoidanceForce(villager, nearby) {
        const force = [0, 0, 0];

        for (const neighbor of nearby) {
            if (neighbor === villager) continue;

            const distance = this.calculateDistance(villager.position, neighbor.position);
            if (distance < villager.avoidanceRadius && distance > 0) {
                // Calculate avoidance direction (away from neighbor)
                const direction = this.subtractVectors(villager.position, neighbor.position);
                this.normalizeVector(direction);

                // Scale force by inverse of distance (stronger when closer)
                const strength = (villager.avoidanceRadius - distance) / villager.avoidanceRadius;
                this.addScaledVector(force, direction, strength);
            }
        }

        return this.scaleVector(force, villager.avoidanceWeight);
    }

    /**
     * Calculate distance between two positions
     */
    calculateDistance(pos1, pos2) {
        const dx = pos1[0] - pos2[0];
        const dy = pos1[1] - pos2[1];
        const dz = pos1[2] - pos2[2];
        return Math.sqrt(dx * dx + dy * dy + dz * dz);
    }

    /**
     * Subtract two vectors
     */
    subtractVectors(vec1, vec2) {
        return [
            vec1[0] - vec2[0],
            vec1[1] - vec2[1],
            vec1[2] - vec2[2]
        ];
    }

    /**
     * Normalize a vector
     */
    normalizeVector(vec) {
        const length = Math.sqrt(vec[0] * vec[0] + vec[1] * vec[1] + vec[2] * vec[2]);
        if (length > 0) {
            vec[0] /= length;
            vec[1] /= length;
            vec[2] /= length;
        }
    }

    /**
     * Add scaled vector to another vector
     */
    addScaledVector(target, source, scale) {
        target[0] += source[0] * scale;
        target[1] += source[1] * scale;
        target[2] += source[2] * scale;
    }

    /**
     * Scale a vector
     */
    scaleVector(vec, scale) {
        return [
            vec[0] * scale,
            vec[1] * scale,
            vec[2] * scale
        ];
    }

    /**
     * Calculate vector length
     */
    calculateVectorLength(vec) {
        return Math.sqrt(vec[0] * vec[0] + vec[1] * vec[1] + vec[2] * vec[2]);
    }

    /**
     * Scale vector in place
     */
    scaleVectorInPlace(vec, scale) {
        vec[0] *= scale;
        vec[1] *= scale;
        vec[2] *= scale;
    }

    /**
     * Add two vectors
     */
    addVectors(target, source) {
        target[0] += source[0];
        target[1] += source[1];
        target[2] += source[2];
    }

    /**
     * Calculate steering force to follow path
     * @param {Villager} villager - The villager to calculate for
     * @returns {Array} Steering force as [x, y, z]
     */
    calculateSteeringForce(villager) {
        if (villager.path.length === 0) return [0, 0, 0];

        const target = villager.path[0];
        const direction = this.subtractVectors(target, villager.position);
        this.normalizeVector(direction);
        const desired = this.scaleVector(direction, villager.maxSpeed);
        const steer = this.subtractVectors(desired, villager.velocity);

        return this.scaleVector(steer, villager.steeringWeight);
    }
}

/**
 * Spatial Grid for efficient neighbor queries
 */
class SpatialGrid {
    constructor(width, height, cellSize) {
        this.width = width;
        this.height = height;
        this.cellSize = cellSize;
        this.grid = [];
        
        // Initialize grid
        const cols = Math.ceil(width / cellSize);
        const rows = Math.ceil(height / cellSize);
        for (let i = 0; i < cols * rows; i++) {
            this.grid.push([]);
        }
    }

    /**
     * Get cell index for a position
     * @param {Array} position - Position to get cell for [x, y, z]
     * @returns {number} Cell index
     */
    getCellIndex(position) {
        const col = Math.floor(position[0] / this.cellSize);
        const row = Math.floor(position[2] / this.cellSize);
        return row * Math.ceil(this.width / this.cellSize) + col;
    }

    /**
     * Insert an object into the grid
     * @param {Object} obj - Object to insert
     */
    insert(obj) {
        const index = this.getCellIndex(obj.position);
        if (index >= 0 && index < this.grid.length) {
            this.grid[index].push(obj);
        }
    }

    /**
     * Clear the grid
     */
    clear() {
        for (let i = 0; i < this.grid.length; i++) {
            this.grid[i] = [];
        }
    }

    /**
     * Query objects within a radius
     * @param {Array} position - Center position [x, y, z]
     * @param {number} radius - Query radius
     * @returns {Array<Object>} Objects within radius
     */
    query(position, radius) {
        const results = [];
        const col = Math.floor(position[0] / this.cellSize);
        const row = Math.floor(position[2] / this.cellSize);
        const radiusCells = Math.ceil(radius / this.cellSize);
        
        const cols = Math.ceil(this.width / this.cellSize);
        const rows = Math.ceil(this.height / this.cellSize);
        
        // Check surrounding cells
        for (let r = Math.max(0, row - radiusCells); r <= Math.min(rows - 1, row + radiusCells); r++) {
            for (let c = Math.max(0, col - radiusCells); c <= Math.min(cols - 1, col + radiusCells); c++) {
                const index = r * cols + c;
                if (index >= 0 && index < this.grid.length) {
                    results.push(...this.grid[index]);
                }
            }
        }
        
        return results;
    }
}

export default CrowdManager;