#1 04.08.2005 06:33:22

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Kollision 2 Rectangles für 2D Sprites

Hallo,

folgendes Problem: Bei Bodenmissionen (schräg von oben gesehen, 2D) brauche ich eine eigene Kollisions-Erkennung für Bewegungen. Ein hoher Baum z.B. soll nicht über sein ganzes Image kollidieren, sondern nur über den 'Fuß' wo er steht, also meinetwegen das untere Drittel.

Also weder Pixel-Kollision noch normale Rectangle-Kollision über das ganze Image kommt in Frage.

Meine Idee:

An jedes Sprite ein benutzerdefiniertes Rectangle, hier setze ich einfach den Bereich, der kollidieren soll. Und jetzt wenn mein Mann oder ein Monster geht, müssen alles Sprites durchlaufen werden, und jedes Rectangle verglichen werden, ob eins im Bereich liegt.

1) Ist das eine gute Idee?

2) Wie vergleiche ich sehr schnell 2 Rectangles oder mein spezielles mit allen anderen?

Danke,
Firle

Offline

 

#2 04.08.2005 07:56:08

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

[Edit: Topic verschoben.]

Zitat:

An jedes Sprite ein benutzerdefiniertes Rectangle, hier setze ich einfach den Bereich, der kollidieren soll.

Das ist für 2D-Kollisionen üblich. Du könntest auch für jedes Objekt eine extra Kollisionsmap benutzen. Je nachdem wie genau die Kollision sein muss, kannst du dann die Auflösung der zusätzlichen Textur verändern. Die Rechtecke haben nämlich den Nachteil, das eine "runde" Kollision nicht möglich ist.

Zitat:

müssen alles Sprites durchlaufen werden

Das ist nicht so gut, wenn du mehr als ca. 100 Objekte hast (denk ich mal) solltest du versuchen deine Objekte in einem Baum anzuordnen. Mit einem Baum (Quadtree) würdest du dann statt 100 (theoretisch) nur noch log_4 (100) = (ln 100 / ln 4)  = 3,32.. ~ 4 Tests brauchen und die Objekte in der Umgebung des Spielers zu finden. Die gefunden Objekte musst du dann natürlich noch einzeln testen.

Theoretisch heißt wenn die Objekte optimal verteilt sind, das man denBaum optimal aufbauen kann. In der Praxis würde man das vermutlich einfacher angehen:
Angenommen dein Spielfeld ist 8192^2 Pixel groß. Jetzt würdest du deine Spielfläche z.B.  in 64x64 große Stückchen unterteilen. Für jedes Stückchen speicherst du die Objekte die sich darauf befinden. Um jetzt die Stückchen zu finden reicht ein Baum der Höhe 7 !
Berechnet sich so:
8192 / 64 = 128 => 128 x 128 = 16384 Stückchen
log_4(16384) = ln 16384 / ln 4 = 7

D.h. du bräuchtest nur 7+1 = 8 Tests um alle Objekte zufinden die sich in einer 192x192 großen Umgebung um den Spieler befinden. (das Stückchen auf dem der Spieler steht und alle Nachbarn)

Ich hoffe ich habe dich jetzt vom enormen Vorteil des Logarithmischen Aufwands überzeugt wink
Wenn du jetzt noch wissen willst wie du das effizient implementierst, dann schau dir mein http://www-users.rwth-aachen.de/Martin. … aytree.pdf an.


Coolcat


My software never has bugs. It just develops random features.

Offline

 

#3 04.08.2005 08:59:15

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

OMG!

Gut zu hören, dass ich schonmal auf dem richtigen Weg bin.  big_smile

Das hört sich toll an, aber ich bin doch so schlecht in Mathe.  :rock:
Muss ich mal reingugn und drüber nachdenken.

Wie würdest du den Vergleich zweier Rectangles am einfachsten machen?

Firle

Offline

 

#4 04.08.2005 09:14:27

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

So 2 Rectangles vergleichen:

X1 linker Punkt, X2 rechter Punkt, Y1 oben, Y2 unten

If ((Rect2.X1)>(Rect1.X1) and (Rect2.X1)<(Rect1.X2)
or ((Rect2.X2)>(Rect1.X1) and (Rect2.X2)<(Rect1.X2))
and ((Rect2.Y1)>(Rect1.Y1) and (Rect2.Y1)<(Rect1.Y2)
or ((Rect2.Y2)>(Rect1.Y1) and (Rect2.Y2)<(Rect1.Y2))
then collision:=true

oder wie geht das besser und schneller?

Firle

Offline

 

#5 04.08.2005 09:17:42

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Zitat:

Das hört sich toll an, aber ich bin doch so schlecht in Mathe.

Sowas wirst du in Mathe nicht lernen, zumindest nicht in der Schule. Eher schon in Informatik... wink

Zwei Rechtecke vergleichen:
Solange die beiden Rechtecke AxisAligned sind, dürfte der Test ja kein Problem sein. Einfach die Koordinaten vergleichen, fertig. (Edit:  ^^ jep, das geht nich besser, glaub ich)
Wenn die Rechtecke gedreht sind, wirds komplizierter, es sollte sich aber im Internet Quellcode dazufinden lassen...

Coolcat

Edit2: Doch geht wohl besser, Code such*


My software never has bugs. It just develops random features.

Offline

 

#6 04.08.2005 09:24:25

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Nö, da wird nix gedreht. Gedrehte Mauern z. B. haben ein eigenes sprite, dem würde ich eine eigenes Rectangle setzen.

Einfach nur wie oben beschrieben, dann wäre das so okay, ja? Dann müsste ich nur noch versuchen, Die Test-Anzahl irgendwie zu beschränken...

Firle

Offline

 

#7 04.08.2005 09:33:01

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Vorraussetzung:
x1 bzw. y1 sind bei beiden Rechtecken kleiner als x2 bzw. y2 !

Code: delphi

if ( ( max(rect1.x1, rect2.x1) < min(rect1.x2, rect2.x2) ) and
     ( max(rect1.y1, rect2.y1) < min(rect1.y2, rect2.y2) )  ) then 
 collision := true;



Das spart dir zwei Vergleiche und eine Menge and bzw. or's.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#8 04.08.2005 09:41:25

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Kollision 2 Rectangles für 2D Sprites

gääÄÄÄÄÄhn.... steht ihr früh auf!
Firle´s Rechteck-Algo sieht schon ziemlich gut aus, ich hätt´s auch so gemacht.
Wenn du 100 Objekte mit 100 Objekten vergleichen mußt, dann kannst Du das noch straight-forward machen, also:
for obj1:=1 to 99 do
..for obj2:=obj1+1 to 100 do
....if collided(obj1,obj2) then boom;

Ist zwar ne Menge Arbeit, aber die CPU ist schnell und deine Collision Det. ja ziemlich einfach.

Wenn das klappt und du Zeit hast, würd ich aber zu Coolcat´s Variante wechseln, ist eleganter.

Muß ich wohl auch noch machen, bei mir sind die ColDets sehr viel komplizierter. Naja.

Peer

Offline

 

#9 04.08.2005 09:48:33

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Aaaah, das schmerzt den Informatikstudenten im innersten wink Quadratischer Aufwand, igitt...

Für meinen Algo brauchst du nur einen Aufwand von O(n * log n), mit dem Baum von oben also durchschnittlich 8 (schnelle!) Tests pro Objekt um das "Stückchen" zu finden und dann vielleicht noch ein oder zwei echte Tests, je nahc dem wie dicht deine Objekte sind.
Du kommst also "über den Daumen gepeitl" auf insgesamt etwa 1000 Vergleiche, nicht 10000 wie bei DerPeer...
Bevor du am Test selbst optimierst, optimiere also lieber den Algorithmus, damit du gar nicht erst testen musst!

Wenn es jetzt nämlich 1000 Objekte wären, hätten wir ein verhältnis von 10000 : 1 Mio big_smile

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#10 04.08.2005 10:07:29

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Kollision 2 Rectangles für 2D Sprites

Moment, es sind nicht 10000 bei mir, sondern nur 5000.
Aber ja, Coolcat´s Methode ist viel besser und schneller und Coolcat selbst ist ja auch der beste  big_smile
Aber zu Testzwecken würde ich immer erst sowas implementieren, bei den Baumgeschichten kann man sich als Anfänger ganz schön verstricken.

Peer

Offline

 

#11 04.08.2005 10:15:47

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Zitat:

sondern nur 5000.

oh, stimmt,  :doof:

Zitat:

Coolcat selbst ist ja auch der beste big_smile

haha, ich bin harmlos, ihr kennt die Freaks nich die bei uns an der Uni rumlaufen...

[Offtopic]
Gestern hatte da einer wieder sowas gebastelt:

Code: delphi

(...) 
x := 0;
magischefunktion(a,b,c);
x := 1;
ausgeben(x);



Die magischeFunktion sorgt dafür das nicht 1 sondern 0 ausgegeben wird!
[/Offtopic]

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#12 04.08.2005 10:41:33

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Hi!

Zitat:

if ( ( max(Rect1.x1, Rect2.x1) < min(Rect1.x2, Rect2.x2) ) and
     ( max(Rect1.y1, Rect2.y1) < min(Rect1.y2, Rect2.y2) )  ) then
collision := true;

Dafür sorgen ich schon, dass x1<x2 und y1<y2, das hatte ich ja am Anfang extra mit reingeschrieben. *Drüber nachdenk*

Ja, das sieht noch eleganter und schneller aus, gut. Danke!

Na dann habe ich ja erstmal was zu tun (heute abend)  wink

:thx:

Firle

Offline

 

#13 05.08.2005 04:24:34

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Das klappt so nicht, irgendwo stimmt was nicht.

Aus Debug:
Box 1: links 410, rechts 450
Box 2: links 884, rechts 924

kollidieren niemals, ist klar. Aber bei mir tun sie es.

Max(410,884)<min(450,924) : 884<450 false, darf nicht true sein!

Trotzdem gibt er True zurück:

Meine Routine:

Code: delphi

function tcommandoform.rect_collide(rect_temp: trect;x,y:single): boolean;
var i: integer;
begin
  for i:=0 to xensprite.count-1 do begin
    if (( max(rect_temp.left+x,xensprite.items[i].rectcol.left+xensprite.items[i].x) < min(rect_temp.right+x, xensprite.items[i].rectcol.right+xensprite.items[i].x)) and
   (max(rect_temp.top+y, xensprite.items[i].rectcol.top+xensprite.items[i].y) < min(rect_temp.bottom+y, xensprite.items[i].rectcol.bottom+xensprite.items[i].y) ) ) then begin
     result:=true;
     exit;
   end;  
  end;
  result:=false;
end;



Alle Werte für dieses True (X siehe oben):
Y Box 1: 540;580
Y Box 2: 188;213

Also die darf weder X noch Y kollidieren. *GugKlammerungan*

Komisch das.

Firle

Offline

 

#14 05.08.2005 05:20:21

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Okay, ich glaube der Debugger lügt und es gibt nur ein True, weil das Sprite mit sich selbst kollidiert. Komich nur, dass der Debugger ein True bei obigen Werten zurückgab. Komisch das.

Firle

Offline

 

#15 05.08.2005 07:35:25

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Funzt es den nun oder nich?

Ich glaube nich das der Debugger da true geliefert hat. (Allerdings hatte ich auch schon die merkwürdigsten erlebnise mit Debuggern....)

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#16 05.08.2005 08:11:53

firlefanz
GodlikeMember
Ort: Olpe in NRW
Registriert: 31.01.2005
Beiträge: 1035
Web-Seite

Re: Kollision 2 Rectangles für 2D Sprites

Doch, das hat er! Aber ich glaube, der Fehler liegt daran, dass das Sprite sich selber findet und ein True liefert. Es gibt leider keinen Public Index. Bin aber mittlerweile auf der Arbeit, muss das heute abend mal testen.

Firle

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson