Folgendes Schema beabsichtige ich:
- 1. Phase: via Quadtree werden alle benachbarten Objekte gesucht. Im Quadtree sollen die Objekte enthalten sein, so dass ich anhand der zugehörigen Quadrate (btw achsenparallel) entscheiden kann, welche Objekte kollisionsverdächtig sind und welche nicht. Quasi ein "Aussieben".
- 2. Phase: Alle Objekte, deren Quadrat sich mit dem Quadrat des primären Objektes (das, für das ich Kollisionen suche) schneiden, werden bezüglich der Kreise überprüft. Dabei fallen ggf. wieder ein paar Objekte raus.
- 3. Phase: Schließlich wird polygonbasierte gesuch, d.h. ich gehe z.B. das Polygon Strecke für Strecke durch und suche Schnitte oder Berührungen. Das ist sehr rechenintensiv, so dass es in der dritten und letzten Phase erst soweit kommen soll.
Für "Programmprototypen" finde ich die Verwendung von Python absolut unschlagbar 
Ich habe ein kleines Skript geschrieben, was so einen Quadtree implementiert und die Suche mit einer linearen Liste vergleicht. Nur habe ich keine Ahnung, ob meine Quadtree-Implementierung so "richtig" bzw. vollständig ist, oder worauf ich noch achten sollte. :K Hier ist das Skript - ich hoffe es ist nicht zu verworren:
Code: Alles auswählen
#!/usr/bin/python
# -*- coding: utf8 -*-
import math
# gewöhnlicher Kreis
class Circle:
def __init__(self, x, y, r):
self.x = x # x Koordinate Mittelpunkt
self.y = y # y Koordinate Mittelpunkt
self.r = r # Radius
def __str__(self):
return '<{0},{1}:{2}>'.format(self.x, self.y, self.r)
# Eukldischer Abstand zweier Punkte
def distance(self, x, y):
return math.sqrt((self.x - x)**2 + (self.y - y)**2)
# Kollision Kreis-Punkt
def collide(self, x, y):
return (self.distance(x, y) <= self.r)
# Kollision Kreis-Kreis
def intersect(self, circ):
if (self.distance(circ.x, circ.y) <= self.r + circ.r):
# hier sollte dann die polygonbasierte Kollisionsprüfung folgen
#print 'Abstand: {0}, Radiensumme: {1}'.format(self.distance(circ.x, circ.y), self.r+circ.r)
return True
else:
return False
# Quadrat (achsenparallel) erzeugen, dessen Inkreis dieser Kreis ist
def getRect(self):
return Rect(self.x - self.r, self.y - self.r, 2 * self.r, 2 * self.r)
# Achsenparalleles Rechteck
class Rect:
def __init__(self, x, y, w, h):
self.x = x # x Koordinate "oben links"
self.y = y # y Koordinate "oben links"
self.w = w # Breite
self.h = h # Höhe
# Kollision Rechteck-Punkt
def collide(self, x, y):
return ((self.x <= x <= self.x + self.w) and
(self.y <= y <= self.y + self.h))
# Kollision Rechteck-Rechteck
def intersect(self, rect):
return ((self.x < rect.x + rect.w) and (rect.x < self.x + self.w) and
(self.y < rect.y + rect.h) and (rect.y < self.y + self.h))
def __str__(self):
return '<{0},{1};{2},{3}>'.format(self.x, self.y, self.w, self.h)
class Quadtree:
def __init__(self, depth, rect):
self.rect = rect
self.depth = depth
self.ne = None
self.se = None
self.sw = None
self.nw = None
self.objs = list()
if (depth > 1):
w = self.rect.w / 2
h = self.rect.h / 2
x = self.rect.x + w
y = self.rect.y
self.ne = Quadtree(depth-1, Rect(x, y, w, h))
w = self.rect.w / 2
h = self.rect.h / 2
x = self.rect.x + w
y = self.rect.y + h
self.se = Quadtree(depth-1, Rect(x, y, w, h))
w = self.rect.w / 2
h = self.rect.h / 2
x = self.rect.x
y = self.rect.y + h
self.sw = Quadtree(depth-1, Rect(x, y, w, h))
w = self.rect.w / 2
h = self.rect.h / 2
x = self.rect.x
y = self.rect.y
self.nw = Quadtree(depth-1, Rect(x, y, w, h))
def insert(self, obj):
if (not self.rect.intersect(obj.getRect())):
return
if (self.depth == 1):
self.objs.append(obj)
else:
self.ne.insert(obj)
self.se.insert(obj)
self.sw.insert(obj)
self.nw.insert(obj)
def query(self, obj):
inRange = list()
if (not self.rect.intersect(obj.getRect())):
return inRange
if (self.depth == 1):
for o in self.objs:
if (obj.intersect(o)):
inRange.append(o)
else:
inRange.extend(self.ne.query(obj))
inRange.extend(self.se.query(obj))
inRange.extend(self.sw.query(obj))
inRange.extend(self.nw.query(obj))
return inRange
if __name__ == '__main__':
import time, random
size = 600
depth = 5
qtree = Quadtree(depth, Rect(0, 0, size, size))
linear = list()
for i in range(size):
x = random.randint(0, size * 10) / 10.0
y = random.randint(0, size * 10) / 10.0
r = random.randint(0, size * 10) / 20.0
c = Circle(x, y, r)
qtree.insert(c)
linear.append(c)
print 'Strukturen (Liste und Quadtree der Tiefe {0}) mit {1} Objekten wurden erstellt.\n'.format(depth, size)
prim = Circle(1.5, 1.5, 0.1)
print 'Kreis {0} (mit Quadrat {1}) Kollisionen:'.format(prim, prim.getRect())
s = time.time()
objs = qtree.query(prim)
e = time.time()
#for o in objs:
# print o
print '\t\t--> {0} Objekte gefunden'.format(len(objs))
print 'Zeit Quadtree:\t\t{0}\n'.format(e-s)
print 'Kreis {0} (mit Quadrat {1}) Kollisionen:'.format(prim, prim.getRect())
s = time.time()
objs = list()
for o in linear:
if prim.intersect(o):
objs.append(o)
e = time.time()
#for o in objs:
# print o
print '\t\t--> {0} Objekte gefunden'.format(len(objs))
print 'Zeit lineare Liste:\t{0}'.format(e-s)
Code: Alles auswählen
Strukturen (Liste und Quadtree der Tiefe 4) mit 5000 Objekten wurden binnen 2.72023701668s erstellt.
Kreis <1.5,1.5:0.1> (mit Quadrat <1.4,1.4;0.2,0.2>) Kollisionen:
--> 321 Objekte gefunden
Zeit Quadtree: 0.00606107711792
Kreis <1.5,1.5:0.1> (mit Quadrat <1.4,1.4;0.2,0.2>) Kollisionen:
--> 321 Objekte gefunden
Zeit lineare Liste: 0.0397760868073LG Glocke
PS: falls ich im falschen Unterforum gelandet bin, dann verschiebt mich einfach ^^
Schau dir mal den PEP 8 an.
Quasi dynamisches Erweitern und Kürzen. Wird nachgeholt