Kollisionserkennung

[neoexpert]

Guten Abend.
Was ist die effizienteste Methode für Kollisionserkennung für Objekte in einem Raum?
Man kann ja z.B. jedes Objekt mit jedem auf Kollision prüfen. Es wäre ziemlich rechenintensiv bei vielen Objekten die sich bewegen (O(n^2)).
Dann habe ich überlegt den Raum zu "verpixeln" (vervoxeln) also grobe Kollisionserkennung zu machen, die man verfeinern kann wenn Objekte näher zu einander kommen. Stellt euch mal vor die Objekte bewegen sich in einem "Integer-Raum" und sind zunächst Würfel mit Kantenlänge 1.
Man kann dann mit

HashMap<Point,Object> objects;

Direkt und schnell auf jeden Objekt zugreifen der im RaumVoxel P liegt.
So könnte man schnell checken ob unser würfel in einen belegtten RaumVoxel fliegt und damit kollidiert. Das wäre O(n) aber grob. Was meint Ihr dazu?

 

[InfectedBytes]

Kommt auf den Raum an...
2D/3D, Art der Räume, Art der Objekte, typische Verteilung, etc.
Standardansätze wären z.b. kd-tree, quad/octree, etc.

 

[neoexpert]

import java.util.*;
import Main.*;
import java.util.Map.*;

public class Main
{

    private int w=20;

    private int h=20;
    public class PointF{
        public float x;
        public float y;
    }
    public class Point
    {
        public float x;
        public float y;
        public Point(Point p){
            this.x=p.x;
            this.y=p.y;
           
        }
        public Point(float x, float y)
        {
            this.x = x;
            this.y = y;
           
        }

        public void add(Main.Point dir)
        {
            x += dir.x;
            y += dir.y;
           
        }

        @Override
        public boolean equals(Object p)
        {
            return Math.round(((Point)p).x) == Math.round(x) &&Math.round( ((Point)p).y) == Math.round(y);
        }
        @Override
        public int hashCode()
        {
            int result = Math.round(x);
            result = 31 * result + Math.round(y);
            return result;
        }

    }
    public class MObject
    {
        public Point pos;
        public Point dir;
        public MObject(Point pos, Point dir,char me)
        {
            this.pos = pos;
            this.dir = dir;
            this.me=me;
        }

        public void moveBack()
        {
            pos.add(new Point(-dir.x,-dir.y));
        }

        public void collide()
        {
            dir.x *= -1;
            dir.y *= -1;
        }


        public void move()
        {
            pos.add(dir);
            dir.x*=0.99;
            dir.y*=0.99;
        }
        private char me='o';
        @Override
        public String toString()
        {
            //return String.valueOf(me)+"("+pos.x+")";
            return String.valueOf(me);
        }
       
    }
    Main()
    {
        os = new HashMap<Point,MObject>();
        for(int i=0;i<10;i++){
            MObject o=new MObject(new Point(new Random().nextInt(w),new Random().nextInt(h) ), new Point(new Random().nextFloat()*2.0f-1.0f,new Random().nextFloat()*2.0f-1.0f),(""+i).charAt(0));
            os.put(new Point(o.pos),o);
        }
    }
    HashMap<Point,MObject> os;
    public static void main(String[] args)
    {
        Main m=new Main();

        while (true)
        {
            m.move();
            m.print();
            try
            {
                Thread.sleep(100);
            }
            catch (InterruptedException e)
            {}
        }
    }

    private void print()
    {
        for (int x=0;x <= w;x++)
        {
            System.out.print("#");
            for (int y=0;y <= h;y++)
            {
                if(x==0||x==20){
                    System.out.print("#");
                    continue;
                }
                MObject o= os.get(new Point(x, y));
                if (o == null)
                    System.out.print(" ");
                else
                    System.out.print(o);

            }
            System.out.print("#\n");
        }

    }
    public void move()
    {
       
        Iterator<Main.MObject> it= os.values().iterator();
        //while (it.hasNext())
        {
        //    Main.MObject o=it.next();
           
        }
        HashMap<Main.Point, Main.MObject> newMap= new HashMap<Point,MObject>();
        it= os.values().iterator();
        while (it.hasNext())
        {
            Main.MObject o=it.next();
            check(o);
            o.move();
            if(newMap.get(o.pos)==null)
                newMap.put(new Point(o.pos),o);
            else{
                o.moveBack();
                newMap.put(new Point(o.pos),o);
            }
        }
       
       
        os=newMap;
       
    }

    private void check(MObject o)
    {
        Point p=new Point(o.pos);
        p.add(o.dir);
        if (p.x <= 0 || p.x >= w)
            o.dir.x*=-1;
        if(p.y <= 0 || p.y >= h)
            o.dir.y*=-1;
       
        if (os.get(p) != null)
        {
            Point dir=new Point(o.dir);
            o.dir=new Point(os.get(p).dir);
            os.get(p).dir=dir;
        }
    }
}

 

[InfectedBytes]

ernsthaft? Nur Code? Kein Text? Und dann nichtmals in CodeTags...

 

[neoexpert]

In dem selben Moment bearbeitet...

 

[InfectedBytes]

Und was sollen wir nun damit? Wäre schon sinnvoll wenn du schreibst was du überhaupt mit dem Code willst