using System.Collections.Generic;
using Godot;

namespace WorldSim;

/// <summary>
/// A coarse spatial hash over NPC positions so proximity queries stop being
/// O(n²). Rebuilt once per tick from the live NPC list; queries return only
/// the buckets within range. At ~80 NPCs this turns every soul-pressure,
/// neighbor, and teacher scan from "look at everyone" into "look at the few
/// nearby" — the difference between a live view that stutters and one that
/// doesn't.
/// </summary>
public class SpatialGrid
{
    private readonly float _cell;
    private readonly Dictionary<(int, int), List<Npc>> _buckets = new();

    public SpatialGrid(float cellSize) => _cell = cellSize;

    private (int, int) Key(Vector2 p) =>
        (Mathf.FloorToInt(p.X / _cell), Mathf.FloorToInt(p.Y / _cell));

    public void Rebuild(IReadOnlyList<Npc> npcs)
    {
        foreach (var list in _buckets.Values) list.Clear();
        foreach (var npc in npcs)
        {
            var key = Key(npc.Position);
            if (!_buckets.TryGetValue(key, out var list))
                _buckets[key] = list = new List<Npc>();
            list.Add(npc);
        }
    }

    /// <summary>
    /// Invoke <paramref name="action"/> for every NPC within <paramref
    /// name="radius"/> of <paramref name="center"/> (excluding none — caller
    /// filters). Scans only the buckets the radius touches.
    /// </summary>
    public void ForEachNear(Vector2 center, float radius, System.Action<Npc> action)
    {
        int reach = Mathf.CeilToInt(radius / _cell);
        int cols = Mathf.CeilToInt(Toroidal.Size / _cell);   // buckets per axis
        var (cx, cy) = Key(center);
        // Wrap bucket coordinates so a search near the seam also scans the
        // buckets on the far edge — the world is a torus.
        for (int dx = -reach; dx <= reach; dx++)
        for (int dy = -reach; dy <= reach; dy++)
        {
            int gx = ((cx + dx) % cols + cols) % cols;
            int gy = ((cy + dy) % cols + cols) % cols;
            if (_buckets.TryGetValue((gx, gy), out var list))
                foreach (var npc in list) action(npc);
        }
    }
}