Kollisionserkennung beschleunigen/verbessern? :)

[Volvagia]

Hi, ich habe eine Collisionserkennung, mit dem ich versuche festzustellen, wie weit sich ein 2-px-großes Objekt, was am Rand eines 16-px-großen Objektes anfängt bewegen kann, bis es zu einer Kollision kommt. Die Methode wird in einem Thread mit 10 millisekunden Verzögerung aufgerufen, trotzdem schnellt die Prozessorauslastung auf 100% hoch. Hat jemand vielleicht eine Idee, wie ich das ganze optimieren könnte? (Oder auch ganz ersetzen.)

private void checkCollision()
{
	Room parent = getParentRoom();
	
	Rectangle rectangle = new Rectangle(getX() + 16, getY() + 7, 2, 2); //Erste Position
	int startX = rectangle.x; //x-position, wo es anfängt.
	for(boolean collisionFound = false; !collisionFound;) //Schleife, bis es zu einer Kollision kommt.
	{
		if(parent.collisionWithEntilitie(rectangle) || rectangle.x > 640) //Kommt es zu einer Kollision oder ist x außerhalb des sichtbaren Bereichs.
		{
			lock(); //Speeren.
			x = startX; //Positionen in Felder setzen.
			y = rectangle.y;
			width = rectangle.x - getX();
			height = 2;
			unlock(); //Entspeeren
			collisionFound = true; //Boolean setzen
		}
		rectangle.x = rectangle.x + 1; //Einen Pixel nach rechts.
	
	}
}

public boolean collisionWithEntilitie(Rectangle rectangle)
{
	boolean b = false; //Returnwert
	
	listLock.lock(); //Listenzugriff speeren
	try
	{
		for(int i = list.size() - 1; i >= 0 && !b; i--) //Schleife rückwärts durchlaufen, bis der letzte (erste) index erreicht ist oder b true ist.
			b = rectangle.intersects(list.get(i).getBounds()); //Prüfen, ob das Rectangle mit etwas kollidiert.
	}
	finally
	{
		listLock.unlock(); //Listenzugriff entspeeren
	}
	return(b); //Und zurück mit der boolean.
}

Edit: Mir ist gerade eine Idee gekommen: Ich könnte mit einen Rectangle mit fixer Länge, z. B. 30 px anfangen. Wenn es dabei zu einer Kollision kommt, halbiere ich die Länge auf 15, und teste noch mal. Wenn nicht, verdoppel ich die Länge. Wenn ein Punkt, der kollidiert und nicht kollidiert gefunden wurde, wird so lange mit dem Durchschnitt der beiden getestet, bis ((max - 1) == min) ist. Ich weiß nur nicht, ob das Geschwindigkeitsvor- oder -nachteile bringen würde. Könnt ihr mir bitte etwas dazu sagen?

 

[Marco13]

Sieht chaotisch aus. Beschreib' ggf. nochmal genauer, was der Code machen soll. Wenn es nur darum geht, Rechtecke zu bewegen, deren Position und Abmessungen man kennt, könnte man die Lösung vielleicht einfach ausrechnen...

 

[Volvagia]

Ich versuche, einen Laser zu basteln, der durch ein anderes Objekt blockiert werden kann. Manche von ihnen können auch verschoben werden. Deshalb wollte ich die Distanz zwischen dem Objekt, welches dem Laser abfeuert und dem ersten Objekt, mit dem es kollidiert regelmäßig herausfinden, um ihm dazustellen.

 

[Marco13]

Hm. Je nachdem wieviele Objekte es in der Liste gibt, und wie weit die voneinander entfernt sind, kann das (soweit ich es jetzt nachvollziehen konnte) ja schon lange dauern: Er mach einen überschneidungstest, bewegt das objekt einen Pixel, macht noch einen überschneidungstest...

Vielleicht würde eine Methode helfen, die den Abstand (in x-Richtung) von zwei Rectangles berechnet?

 

[Volvagia]

Ich weiß aber nicht, wie man feststellt, mit welchen Objekt/Rectangle der Laser kollidiert, was die Hauptaufgabe der Methode ist.

Ich könnte aber z. B. alle Objekte auslassen, deren y + height > laserstartobjekt.y und y < laserstartobjekt.y + laserstartobjekt.height ist. Aber da sich manche Objekte auch bewegen können, müsste ich wohl bei jedem Durchlauf eine Collection anlegen/leeren, sie von der original Liste übertragen, und dann durchgehen. Ich bezweifel aber, dass das schneller als meine jetzige Methode geht.

 

[Marco13]

*seufz* Aaaalso, da ist irgendwo ein Laserstrahl. Der fängt bei der Position (Lx,Ly) an. geht er immer senkrecht oder waagerecht? Geht er durch Objekte durch? Sollen ALLE Objekte gestestet werden? Es gibt Objekte, die sich bewegen. Bewegen die sich nur senkrecht oder waagerecht? Mit wie großen Schritten? .... *nochmalseufz*

 

[Volvagia]

Oh, tut mir leid. Ja, er bewegt sich nur waagrecht/senkrecht. Ich will später noch Objekte einbauen, die spiegeln und ihm so umlenken können, aber dabei will ich einen neuen Laser in die jeweilige Reihe erzeugen. Er soll auch durch Objekte durchgehen, deshalb müssen nur ca. 10 von derzeit 55 Objekttypen getestet werden, diese sind aber deutlich in der Mehrheit. Derzeit ist es so aufgebaut, dass es nur einen TimerTask gibt, der alle Objekte in einer Liste durchgeht und eine Methode aufruft. Die Objekte, die sich hauptsächlich bewegen sich 2 px pro Aufruf (insgesamt 16 px pro Schritt), der Task läuft alle 10 ms durch. Dabei werden die meisten Objekte vom Spieler geschoben (ziehen geht nicht), ruft bei der Berührung einen byte um, und leitet so die eigene Bewegung ein. Dem Task habe ich genommen, damit alles syncron läuft.

 

[Marco13]

Und warum werden bei einem Schnitt Strahl-Rechteck zwei Rechtecke verwendet? Soll das sowas werden die ApoPrizm !?

 

[Volvagia]

Im Prinzip schon. Also der Laser soll von dem erstbesten Objekt auf das er trifft blockiert werden, und wenn er etwas trifft, wird eine Methode des Objektes aufgerufen, in der jeweils HP abgezogen werden (manche Objekte sollen dem Laser nur kurze Zeit stand halten können). Ich denke, das Projekt ist Game of ROBOT, ROBOT-Spiele von TOM Productions, Robot Junior, Robot 1, Robot 2, Robot 3, Robot 4 am ähnlichsten, auch wenn es dort so einen Laser nicht gibt.

 

[Marco13]

Sorry, mir ist das jetzt zu zäh. Du willst irgendein tolles Spiel schreiben, und weißt nicht, wie es geht. Wenn du die Frage nicht runterkondensieren kannst auf "Wie schneidet man ein Rechteck mit einem Strahl?" oder sowas, kann diese Nachfragerei hier noch Tage dauern.

 

[JohannisderKaeufer]

Ein paar Bilder sagen vielleicht mehr als 1000 Worte. Wie wäre es mit einer kleinen Skizze?

 

[Volvagia]

Na ja, ich wollte ja eigendlich nur wissen, wie ich die Kollisionserkennung beschleunigen kann.

Ich habe einfach einen Laser, der solange geht, bis er von etwas blockiert wird.

 

[Marco13]

int laserStartX = ...
int laserStartY = ...
int laserEndY = laserStartY;
int laserEndY = berechne(allRectangles);

int berechne(List<Rectangle> allRectangles)
{
    int result = Integer.MAX_VALUE;
    for (Rectangle r : allRectangles)
    {
        if (laserStartY > r.y && laserStartY < r.y+r.height)
        {
            result = Math.min(result, r.x);
        }
    }
    return result;
}

!?

 

[Volvagia]

Wow, vielen dank. Manchmal übersehe ich sogar die einfachsten Lösungen.

 

[Marco13]

Die Lösung ist nur so lange einfach, wie es nur um horizontale (oder vertikale) Laser und Rechtecke geht. Ansonsten kann das komplizierter werden, und nennt sich in seiner ausgefeiltesten Form dann "Raytracing"