Kollisionserkennung

N

neoexpert

Gast
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
Java:
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

Top Contributor
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.
 
N

neoexpert

Gast
Java:
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;
        }
    }
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Kollisionserkennung und -behandlung Spiele- und Multimedia-Programmierung 3
BraunBerry Java Game verbesserte Kollisionserkennung Spiele- und Multimedia-Programmierung 18
Cromewell JavaFX Kollisionserkennung Spiele- und Multimedia-Programmierung 6
S Jump 'n' Run-Spiel Kollisionserkennung Spiele- und Multimedia-Programmierung 3
S Kollisionserkennung in Slick2D... Mal wieder Spiele- und Multimedia-Programmierung 4
C Java Kollisionserkennung Spiele- und Multimedia-Programmierung 4
Androbin Pixel-genaue Kollisionserkennung Spiele- und Multimedia-Programmierung 5
Kenan89 Kollisionserkennung - Idee Spiele- und Multimedia-Programmierung 5
T Kollisionserkennung mit AABBs und Spielerobjekt Spiele- und Multimedia-Programmierung 4
P Kollisionserkennung Spiele- und Multimedia-Programmierung 6
R Java3D Kollisionserkennung und Schwerkraft Spiele- und Multimedia-Programmierung 17
Apo Kollisionserkennung bei Jump'n'Run Spiele- und Multimedia-Programmierung 69
B Kollisionserkennung bei gezeichneten Objekten Spiele- und Multimedia-Programmierung 2
M Kollisionserkennung optimieren Spiele- und Multimedia-Programmierung 7
M Kollisionserkennung Spiele- und Multimedia-Programmierung 4
E Probleme mit Kollisionserkennung ! Spiele- und Multimedia-Programmierung 2
P Kollisionserkennung Spiele- und Multimedia-Programmierung 3
R Kollisionserkennung funktioniert nicht Spiele- und Multimedia-Programmierung 3
C Kollisionserkennung Spiele- und Multimedia-Programmierung 3

Ähnliche Java Themen

Neue Themen


Oben