snuvi-engine/src/me/hammerle/snuviengine/game/BoxList.java

package me.hammerle.snuviengine.game;

import java.util.LinkedList;
import java.util.List;

public class BoxList
{
    private static final double MAX_SIZE = 0.5;
    
    public static class Node
    {
        private Node next;
        private Node previous;
        private Entity ent;
        private int x;
        private int y;
    }
    
    private final double boxMinX;
    private final double boxMinY;
    private final double boxMaxX;
    private final double boxMaxY;
    
    private final double size;
    
    private final Node[][] nodes;
    
    private Node freeNodes = null;
    
    private final int partionX;
    private final int partionY;
    
    public int amount = 0;
        
    public BoxList(double x1, double y1, double x2, double y2, double size)
    {
        this.size = size;
        
        boxMinX = Math.min(x1, x2);
        boxMinY = Math.min(y1, y2);
        
        partionX = (int) Math.ceil((Math.max(x1, x2) - boxMinX) / size);
        partionY = (int) Math.ceil((Math.max(y1, y2) - boxMinX) / size);
        
        boxMaxX = partionX * size;
        boxMaxY = partionY * size;
        
        System.out.println(boxMinX + " " + boxMaxX);
        System.out.println(boxMinY + " " + boxMaxY);
        System.out.println(partionX + " " + partionY);
        
        nodes = new Node[partionX][partionY];
        
        for(int i = 0; i < 132000; i++)
        {
            Node n = new Node();
            n.next = freeNodes;
            freeNodes = n;
        }
    }
    
    public Node add(Entity ent)
    {
        int x = Math.max(Math.min((int) (((ent.xPos + ent.width / 2) + boxMinX) / size), partionX - 1), 0);
        int y = Math.max(Math.min((int) (((ent.yPos + ent.height / 2) + boxMinY) / size), partionY - 1), 0);
        
        amount++;
        
        Node n = freeNodes;
        freeNodes = n.next;
        n.next = null;
        
        n.ent = ent;
        n.x = x;
        n.y = y;
        
        if(nodes[x][y] == null)
        {
            nodes[x][y] = n;
        }
        else
        {
            n.next = nodes[x][y];
            nodes[x][y].previous = n;
            nodes[x][y] = n;
        }
        return n;
    }
    
    public void remove(Node n)
    {
        if(n.previous != null)
        {
            n.previous.next = n.next;
        }
        else
        {
            nodes[n.x][n.y] = n.next;
        }
        
        if(n.next != null)
        {
            n.next.previous = n.previous;
        }
        
        n.previous = null;
        n.ent = null;
        
        n.next = freeNodes;
        freeNodes = n;
        
        amount--;
    }
    
    public List<Entity> getAllEntitiesAt(Entity not, double minX, double minY, double maxX, double maxY)
    {
        int sx = Math.max(Math.min((int) ((minX + boxMinX - MAX_SIZE) / size), partionX - 1), 0);
        int sy = Math.max(Math.min((int) ((minY + boxMinY - MAX_SIZE) / size), partionY - 1), 0);
        int ex = Math.max(Math.min((int) ((maxX + boxMinX + MAX_SIZE) / size), partionX - 1), 0);
        int ey = Math.max(Math.min((int) ((maxY + boxMinY + MAX_SIZE) / size), partionY - 1), 0);
        
        List<Entity> list = new LinkedList<>();
        
        for(int x = sx; x <= ex; x++)
        {
            for(int y = sy; y <= ey; y++)
            {
                Node n = nodes[x][y];
                while(n != null)
                {
                    if(not != n.ent && n.ent.isColliding(minX, minY, maxX, maxY))
                    {
                        list.add(n.ent);
                    }
                    n = n.next;
                }
            }
        }
        
        return list;
    } 
}