Kollisionsbeispiel + Minitutorial + N-Dimensionaler-Baum

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

	Firstdeathmaker Betreff: Kollisionsbeispiel + Minitutorial + N-Dimensionaler-Baum	Fr, Sep 18, 2009 14:37 Antworten mit Zitat
Hab einfach mal aus Spaß eine Implementation eines n-dimensionalen Binärbaumes erstellt und dann ein schönes Beispiel dazuprogrammiert. Das Beispiel behandelt Kollisionsprüfung von rechteckigen Objekten... und zwar für richtig viele Objekte. Beispiel Kompiliert für Windows zum anschauen Erklärung funktionsweise Oft hat man in Spielen das Problem, dass man jede Menge Gegenstände und Objekte miteinander kollidieren lassen möchte. Wenn man jetzt einfach jedes Objekt mit jedem über Imagescollide pixelgenau kollidieren lässt, dann ist das zwar für 100 Objekte noch in Ordnung, aber was ist wenn man auf einmal 1000 hat? Genau, man müsste in diesem schlechtesten Fall 1000^2 Kollisionen durchgehen und prüfen. Was kann man also tun um die Aufrufe von Imagescollide zu verringern? Als erstes kann man natürlich erstmal nen Rechteckcheck machen, ob sich die Rechtecke der Bilder sich überhaupt berühren, und erst wenn das der Fall ist Imagescollide aufrufen. Als zweites (und hier kommt der Clou), kann man einen 2-dimensionalen Baum verwenden, um die gegenseitigen Kollisionsprüfungen auf ein Minimum zu beschränken. Und das funktioniert so: Man stelle sich ein leeres Blatt Papier vor, auf das man 10 Punkte zufällig verteilt. Wenn man jetzt jeden Punkt mit allen anderen auf Kollision prüfen möchte, dann müsste man für jeden Punkt alle 9 anderen Punkte überprüfen. Ergibt 109 = 90 Checks = Viel Aufwand = Schlecht. Was aber, wenn man das Blatt einmal in der Mitte faltet, und nur jeweils diejenigen prüft, welche sich innerhalb einer Hälfte befinden? Man kann das ja machen, weil die Punkte aus dem einen Bereich sowieso nicht die Punkte des anderen Bereiches berühren und umgekehrt. Wir nehmen also an, dass wir 5 Punkte auf der einen, und 5 Punkte auf der anderen Seite des Blattes haben. Das Ergibt 2 5 * 4 = 40 Checks = Weniger Aufwand = Besser. Den Faltvorgang kann man nun beliebig wiederholen, bis es einfach keinen Sinn mehr macht. Jetzt kommt bestimmt jemand schlaues daher und sagt: Moment mal, was ist, wenn ich ein Objekt habe, welches genau auf der Trennlinie des Blattes liegt? Naja, in dem Fall muss man es wohl oder übel mit beiden Punktmengen des Blattes überprüfen. Aber genau das macht der hier vorgestellte 2-Dimensionale Baum (und das ist auch auf 3-Dimensionale Kollisionsprüfung anwendbar). Es ist jedenfalls möglich, die Anzahl der detaillierten Kollisionsprüfungen auf ein minimum zu beschränken, sodass man bei 2500 Objekten die sich gleichzeitig über den Bildschirm bewegen, nur etwa 200 Kollisionen tatsächlich zu prüfen hat (Zahlen aus dem Beispielprogramm genommen). Des weiteren könnte man in einem tatsächlichen Spiel die Objekte in Gruppen verteilen, und so weitere Kollisionsprüfungen sparen. Als Beispiel sei hier z.B. ein Spaceshooter genannt, in dem man Raumschiffe und Laserschüsse hat. Natürlich braucht man nicht unbedingt die Laser gegen die Laser zu prüfen, es reicht wenn man Laser gegen Raumschiffe und Raumschiffe gegen Raumschiffe prüft, was eine weitere nicht zu unterschätzende Ersparniss bringen kann. Erklärung zum Beispiel: Wenn man das Beispiel startet, sieht man zunächst einen schwarzen Bildschirm. Drückt man die LEERTASTE, so erstellt man 100 kleine Rechtecke die mit unterschiedlicher Geschwindigkeit über den Bildschirm flitzen, und falls sich zwei berühren, eines davon vernichtet wird. Das vernichten kann man natürlich ausschalten (mit "D"), sodass man das auch für sehr viel mehr Objekte testen kann. Mit den Pfeiltasten RAUF und RUNTER kann man die "Faltung" des Blattes einstellen, also in wie viele kleine Bereiche der große Bereich aufgeteilt werden soll. Im Hintergrund werden die Kästchen und Bereiche angezeigt, welche gerade tatsächlich existieren und benötigt werden (Wenn in einem Bereich keine Objekte sind, dann ist dort auch keine hohe Skalierung nötig und entsprechend große Kästchen sind dann dort zu sehen). Die Anzeigen sollten selbsterklärend sein, bis auf CollTime: CollTime: Zeit,welche für die reine Kollisionsprüfung benötigt wird \| Zeit, welche für das verwalten und bewegen der Objekte benötigt wird, beides in MS. Beispiel Kompiliert für Windows Beispiel Sourcecode (benötigt weiter unten gepostetes Modul) Code: [AUSKLAPPEN] [EINKLAPPEN] superstrict Import fdm.ndimtree Const worldxoffset:Int = 0 Const worldyoffset:Int = 0 Const worldwidth:Int = 800 Const worldheight:Int = 600 Global maxCollisionDepth:Int = 7 Global onCollideDestruction:Int = True Global showCollisionBoxes:Int = True Global showCollisionBarriers:Int = True Graphics 800 , 600 SetBlend alphablend Global objManager:TObjectManager = New TObjectManager Global DEBUG_Collisions:Int Global DEBUG_CollisionObjects:Int Global DEBUG_CollisionManagementTime:Int Global DEBUG_CollisionCheckTime:Int Repeat If KeyHit(KEY_SPACE) For Local i:Int = 0 Until 100 Rem Local r:Float = Rnd(0 , 200) Local d:Float = Rnd(0,360) Local x:Float = rSin(d) + 100 Local y:Float = rCos(d) + 300 End rem Local x:Float = Rand(worldxoffset , worldwidth) Local y:Float = Rand(worldyoffset , worldheight) Local o:T2DObject = T2DObject.Create(x , y , 2 , 2) o.speed[0] = (Rand(0 , 1) * 2 - 1) * Rnd(0.5 , 5) o.speed[1] = (Rand(0,1)2-1)Rnd(0.5,5) objManager.addObject(o) Next EndIf If KeyHit(KEY_UP) maxCollisionDepth:+ 1 If KeyHit(KEY_DOWN) maxCollisionDepth:- 1 If maxCollisionDepth < 0 maxCollisionDepth = 0 EndIf If KeyHit(KEY_D) onCollideDestruction = Not onCollideDestruction If KeyHit(KEY_B) showCollisionBoxes = Not showCollisionBoxes If KeyHit(KEY_N) showCollisionBarriers = Not showCollisionBarriers If KeyHit(KEY_C) objManager.Clear() EndIf objManager.process() Cls objManager.render() SetAlpha 0.9 SetColor 0,0,0 DrawRect 0 , 0 , 230 , 180 SetAlpha 1 SetColor 255,255,255 DrawText "Objects: " + DEBUG_CollisionObjects , 10 , 10 DrawText "Collisions: " + DEBUG_Collisions , 10 , 30 DrawText "CollTime: " + DEBUG_CollisionCheckTime+"\|"+DEBUG_CollisionManagementTime , 10 , 50 DrawText "CollDepth(Arrow Keys): " + maxCollisionDepth , 10 , 80 DrawText "OnHitDestruction(Key D): " + onCollideDestruction , 10 , 100 DrawText "ShowCollBoxes(Key B): " + showCollisionBoxes , 10 , 120 DrawText "ShowCollBarriers(Key N): " + showCollisionBarriers , 10 , 140 DrawText "Clear All Objects(Key C)", 10 , 160 Flip Until KeyHit(KEY_ESCAPE) End Type TObjectManager Field list:TList = New TList Field collManager:TCollisionManager Method New() collManager = New TCollisionManager End Method Method addObject(o:T2DObject) o.setObjectManager(Self , list.addlast(o) ) o.setCollisionManager(collManager) 'collManager.check2DObjectSpace(o) End Method Method process() DEBUG_CollisionManagementTime = MilliSecs() For Local o:T2DObject = EachIn list o.process() Next DEBUG_CollisionManagementTime = MilliSecs()-DEBUG_CollisionManagementTime DEBUG_Collisions = 0 DEBUG_CollisionCheckTime = MilliSecs() For Local o:T2DObject = EachIn list o.collide() Next DEBUG_CollisionCheckTime = MilliSecs()-DEBUG_CollisionCheckTime End Method Method render() collManager.debugRender() For Local o:T2DObject = EachIn list o.render() Next End Method Method clear() For Local o:T2DObject = EachIn list o.remove() Next End Method End Type Type TCollisionManager Field collTree:TNDimTree Method New() collTree = New TNDimTree collTree.setCompareFunction(Compare2DPositions) End Method Method check2DObjectSpace(obj:T2DObject) Local s:T2DSpace = obj.space If s = Null s = T2DSpace(collTree.returnObject(obj) ) obj.setSpace(s , s.addObject(obj) ) Else If Not s.check2DObjectSpace(obj) obj.removeCollisionSpace() s = T2DSpace(collTree.returnObject(obj) ) obj.setSpace(s , s.addObject(obj) ) EndIf EndIf End Method Method check2DObjectCollisions:TList(obj:T2DObject) Local spacesList:TList = New TList Local objectList:TList = New TList obj.space.node._addAllContentToList(spacesList) For Local s:T2DSpace = EachIn spacesList For Local obj2:T2DObject = EachIn s.content If obj2.pos[0] + obj2.size[0] < obj.pos[0] Continue If obj2.pos[0] > obj.pos[0] + obj.size[0] Continue If obj2.pos[1] + obj2.size[1] < obj.pos[1] Continue If obj2.pos[1] > obj.pos[1] + obj.size[1] Continue If obj2 = obj Continue objectList.addlast(obj2) Next Next spacesList = Null Return objectList End Method Method debugRender() Local n:TNDimNode = collTree._rootNode If n = Null Return 'DebugStop() renderBarrier(n,worldxoffset,worldyoffset,worldwidth,worldheight) End Method Method renderBarrier(n:TNDimNode , x:Float , y:Float,width:Float,height:Float) If n = Null Return Local d:Int = n.getDepth() Local s:T2DSpace = T2DSpace(n.getContent() ) If s = Null Return Local barrier:Float = s.barrier If d Mod 2 If showCollisionBarriers DrawRect x , barrier , width , 1 renderBarrier(n.leftnode,x , y , width , height0.5) renderBarrier(n.rightnode , x , barrier , width , height 0.5) Else If showCollisionBarriers DrawRect barrier , y , 1, height renderBarrier(n.leftnode,x , y , width0.5 , height) renderBarrier(n.rightnode , barrier , y , width 0.5 , height) EndIf If showCollisionBoxes SetAlpha 0.01 DrawRect s.pos[0] , s.pos[1] , s.size[0] , s.size[1] SetAlpha 1 EndIf 'DrawText d,x+width0.5,y+height0.5 End Method End Type Function Compare2DPositions:Int(val:Object , node:TNDimNode) Local obj:T2DObject = T2DObject(val) Local space:T2DSpace = T2DSpace(node.getContent() ) Local depth:Int = node.getDepth() If space = Null space = New T2DSpace space.setBarrier(node) node.setContent(space) EndIf If depth >= maxCollisionDepth Return 0 If depth Mod 2 If obj.pos[1] > space.barrier Return 1 If obj.pos[1] + obj.size[1] < space.barrier Return -1 Return 0 Else If obj.pos[0] > space.barrier Return 1 If obj.pos[0] + obj.size[0] < space.barrier Return -1 Return 0 EndIf End Function Type T2DSpace Field content:TList = New TList Field node:TNDimNode Method addObject:TLink(obj:T2DObject) Return content.addlast(obj) End Method Method removedObject() If content.count() > 0 Return'no reason to check. If node.noSuccessors() Local pnode:TNDimNode = node.upperNode node.remove() If pnode T2DSpace(pnode.content).removedObject() EndIf End Method Field barrier:Float Field depth:Int'debug Field direction:Byte Field pos:Float[2] Field size:Float[2] Method setBarrier(node:TNDimNode) Self.depth = node.getDepth() Self.direction = depth Mod 2 Self.node = node Local axis:Byte = depth Mod 2 'axis 0=x-axis, 1=y-axis pos[0] = worldxoffset pos[1] = worldyoffset size[0] = worldwidth size[1] = worldheight If axis barrier = worldyoffset + worldheight / 2^Floor(depth0.5+1) Else barrier = worldxoffset + worldwidth / 2^Floor(depth0.5+1) EndIf If node.upperNode Local parentSpace:T2DSpace = T2DSpace(node.upperNode.content) pos[0] = parentSpace.pos[0] pos[1] = parentSpace.pos[1] If axis size[0] = parentSpace.size[0] * 0.5 size[1] = parentSpace.size[1] Else size[0] = parentSpace.size[0] size[1] = parentSpace.size[1] * 0.5 EndIf If node.direction > 0 If axis pos[0]:+size[0] Else pos[1]:+size[1] EndIf EndIf node = node.upperNode If node.upperNode If node.direction < 0 barrier = T2DSpace(node.upperNode.content).barrier - barrier ElseIf node.direction > 0 barrier = T2DSpace(node.upperNode.content).barrier + barrier EndIf EndIf EndIf End Method Rem bbdoc: Checks if object is still in this space end rem Method check2DObjectSpace:Byte(obj:T2DObject) If obj.pos[0] >= pos[0] And obj.pos[1] >= pos[1] If obj.pos[0] + obj.size[0] <= pos[0] + size[0] And obj.pos[1] + obj.size[1] <= pos[1] + size[1] If depth = maxCollisionDepth Return True 'check if object lays over the middle barrier If obj.pos[direction] <= barrier And obj.pos[direction] + obj.size[direction] >= barrier Return True 'Otherwise it can be sorted deeper into the heap Return False EndIf EndIf End Method End Type Type T2DObject Field pos:Float[2] Field size:Float[2] Field speed:Float[2] Field collisionManager:TCollisionManager Field space:T2DSpace Field spaceLink:TLink Field objectManager:TObjectManager Field objectManagerLink:TLink Method setSpace(space:T2DSpace , spaceLink:TLink) Assert space <> Null , "T2DObject.setSpace() space = NULL" Assert spaceLink <> Null , "T2DObject.setSpace() spaceLink = NULL" Self.space = space Self.spaceLink = spaceLink End Method Method process() Local x:Float = pos[0] + speed[0] Local y:Float = pos[1] + speed[1] processBoundaries(x,y) setPos(x,y) End Method Method collide() If collisionManager Local l:TList = collisionManager.check2DObjectCollisions:TList(Self) If l.isEmpty() Return DEBUG_Collisions:+1 If onCollideDestruction Self.remove() EndIf End Method Method processBoundaries(x:Float Var, y:Float Var) If x < worldxoffset x = worldxoffset; speed[0] = -speed[0] If y < worldyoffset y = worldyoffset; speed[1] = -speed[1] If x + size[0] > worldwidth+worldxOffset x = worldwidth - size[0] ; speed[0] = - speed[0] If y + size[1] > worldheight y = worldheight + worldyoffset - size[1] ; speed[1] = - speed[1] End Method Method setPos(x:Float , y:Float) pos[0] = x pos[1] = y If collisionManager collisionManager.check2DObjectSpace(Self) End Method Method setSize(width:Float , height:Float) size[0] = width size[1] = height End Method Method setObjectManager(m:TObjectManager , managerLink:TLink) Self.objectManager = m objectManagerLink = managerLink End Method Method setCollisionManager(m:TCollisionManager) Self.collisionManager = m End Method Method New() DEBUG_CollisionObjects:+ 1 End Method Method remove() removeObjectManager() DEBUG_CollisionObjects:-1 End Method Method removeObjectManager() If objectManagerLink RemoveLink(objectManagerLink); objectManagerLink=Null objectManager = Null removeCollisionManager() End Method Method removeCollisionManager() collisionManager = Null removeCollisionSpace() End Method Method removeCollisionSpace() If spaceLink RemoveLink(spaceLink) ; spaceLink = Null If space = Null Return space.removedObject() space = Null End Method Method render() DrawRect pos[0] , pos[1] , size[0] , size[1] 'DrawText space.depth,pos[0] , pos[1] End Method Function Create:T2DObject(x:Float , y:Float , width:Float , height:Float) Local o:T2DObject = New T2DObject o.setPos(x , y) o.setSize(width , height) Return o End Function End Type Modul fdm.mod/ndimtree.mod/ndimtree.bmx Code: [AUSKLAPPEN] [EINKLAPPEN] Rem bbdoc: Illusion-Games NDimTree (N - Dimensional Tree) about: For sorting and finding keys or x-dimensional object spaces. Its non-dynamicly, means it will create the full twig down to the exact value. So think before use! If you just want to save small data amount with high differences (like Strings) you should prefer TMap. But if you want to create a 2Dim or 3Dim Collision detection, than this should be your choice. EndRem Module fdm.ndimtree ModuleInfo "Version: 0.0.1" ModuleInfo "Label: Illusion-Games" ModuleInfo "Authors: Christian Geissler" ModuleInfo "Update: 0" SuperStrict Import brl.linkedlist Public Type TNDimTree Rem bbdoc: Get the compareFunction for this TNDimTree object. End Rem Method GetcompareFunction:Int(key:Object, node:TNDimNode) () Return _compareFunction End Method Rem bbdoc: Set the compareFunction for this TBinaryTree object. End Rem Method SetcompareFunction(f:Int(key:Object, node:TNDimNode)) _compareFunction = f End Method Rem bbdoc: insert an object into the n-dim tree using key:Object to find related position. returns: depth of related node end rem Method insertObject:Int(key:Object, obj:Object) Local node:TNDimNode = _getRelatedNode(key) Assert node.content = Null, "TBinaryTree.insertObject() trying to overwrite existing object" node.content = obj Return node.Getdepth() End Method Rem bbdoc: return saved object from the n-dim tree using key:Object to find related position. end rem Method returnObject:Object(key:Object) Local node:TNDimNode = _getRelatedNode(key) Return node.content End Method Rem bbdoc: searches for related node and returns a list of all subcontent objects end rem Method returnSubObjects:TList(key:Object) Local list:TList = New TList Local node:TNDimNode = _getRelatedNode(key) node._addAllContentToList(list) Return list End Method Rem bbdoc: remove saved object from the n-dim tree using key:Object to find related position. abount: object needs to exist already. If you are not shure if it exists, use returnObject() or ReturnAndRemoveObject() end rem Method removeObject(key:Object) Local node:TNDimNode = _getRelatedNode(key) Assert node.content <> Null, "TBinaryTree.removeObject() there is no object that can be removed" node.content = Null End Method Rem bbdoc: removes and returns object specified by key:Object. If object does not exist, it returns null. returns: related object OR NULL if there is no related object. end rem Method ReturnAndRemoveObject:Object(key:Object) Local node:TNDimNode = _getRelatedNode(key) Local obj:Object = node.content node.content = Null Return obj End Method Rem bbdoc: removes all saved values from this NDimTree. end rem Method clear() If _rootNode _rootNode.remove() _rootNode = Null End Method Rem bbdoc: compareFunction is a function that returns -1 if object is lower than value it should be 0 if object matches value 1 if object is higher than value it should be depth starts from 0 to intMax attention: compareFunction finaly has to return 0, otherwise algorithm doesn't work. end rem Field _compareFunction:Int(key:Object, node:TNDimNode) Field _rootNode:TNDimNode Method _getRelatedNode:TNDimNode(key:Object, startNode:TNDimNode = Null) Local currentNode:TNDimNode Local eval:Int Local depth:Int depth = 0 If Not _rootNode _rootNode = TNDimNode.Create(depth) If startNode = Null startNode = _rootNode currentNode = startNode eval = _compareFunction(key, currentNode) While eval <> 0 If eval < 0 If currentNode.leftNode = Null currentNode.leftNode = TNDimNode.Create(depth + 1, currentNode, -1) currentNode = currentNode.leftNode Else If currentNode.rightNode = Null currentNode.rightNode = TNDimNode.Create(depth + 1, currentNode, 1) currentNode = currentNode.rightNode EndIf depth:+1 eval = _compareFunction(key, currentNode) Wend Return currentNode End Method End Type Type TNDimNode Field leftNode:TNDimNode Field rightNode:TNDimNode Field upperNode:TNDimNode Field content:Object Field depth:Int Field direction:Int '-1 for left, 1 for right, 0 for root Method noSuccessors:Byte() Return (leftNode = Null And rightNode = Null) End Method Rem bbdoc: Get the content value in this TNDimNode object. End Rem Method Getcontent:Object() Return content End Method Rem bbdoc: Set the content value for this TNDimNode object. End Rem Method Setcontent(Value:Object) content = Value End Method Rem bbdoc: Get the depth value in this TNDimNode object. End Rem Method Getdepth:Int() Return depth End Method Rem bbdoc: Set the depth value for this TNDimNode object. End Rem Method Setdepth(Value:Int) depth = Value End Method Function Create:TNDimNode(depth:Int, upperNode:TNDimNode = Null, direction:Int = 0) Local n:TNDimNode = New TNDimNode n.Setdepth(depth) n.upperNode = upperNode n.direction = direction Return n End Function Method _addAllContentToList(list:TList) If leftNode leftNode._addAllContentToList(list) If content list.AddLast(content) If rightNode rightNode._addAllContentToList(list) End Method Method remove() If leftNode leftNode.remove() ;leftNode = Null If rightNode rightNode.remove() ;rightNode = Null If upperNode = Null Return If direction < 0 upperNode.leftNode = Null If direction > 0 upperNode.rightNode = Null upperNode = Null End Method End Type
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Betreff: Kollisionsbeispiel + Minitutorial + N-Dimensionaler-Baum

Fr, Sep 18, 2009 14:37
Antworten mit Zitat

Hab einfach mal aus Spaß eine Implementation eines n-dimensionalen Binärbaumes erstellt und dann ein schönes Beispiel dazuprogrammiert. Das Beispiel behandelt Kollisionsprüfung von rechteckigen Objekten... und zwar für richtig viele Objekte.

Beispiel Kompiliert für Windows zum anschauen

Erklärung funktionsweise
Oft hat man in Spielen das Problem, dass man jede Menge Gegenstände und Objekte miteinander kollidieren lassen möchte. Wenn man jetzt einfach jedes Objekt mit jedem über Imagescollide pixelgenau kollidieren lässt, dann ist das zwar für 100 Objekte noch in Ordnung, aber was ist wenn man auf einmal 1000 hat? Genau, man müsste in diesem schlechtesten Fall 1000^2 Kollisionen durchgehen und prüfen.

Was kann man also tun um die Aufrufe von Imagescollide zu verringern?

Als erstes kann man natürlich erstmal nen Rechteckcheck machen, ob sich die Rechtecke der Bilder sich überhaupt berühren, und erst wenn das der Fall ist Imagescollide aufrufen.

Als zweites (und hier kommt der Clou), kann man einen 2-dimensionalen Baum verwenden, um die gegenseitigen Kollisionsprüfungen auf ein Minimum zu beschränken. Und das funktioniert so:

Man stelle sich ein leeres Blatt Papier vor, auf das man 10 Punkte zufällig verteilt. Wenn man jetzt jeden Punkt mit allen anderen auf Kollision prüfen möchte, dann müsste man für jeden Punkt alle 9 anderen Punkte überprüfen. Ergibt 10*9 = 90 Checks = Viel Aufwand = Schlecht.

Was aber, wenn man das Blatt einmal in der Mitte faltet, und nur jeweils diejenigen prüft, welche sich innerhalb einer Hälfte befinden? Man kann das ja machen, weil die Punkte aus dem einen Bereich sowieso nicht die Punkte des anderen Bereiches berühren und umgekehrt.
Wir nehmen also an, dass wir 5 Punkte auf der einen, und 5 Punkte auf der anderen Seite des Blattes haben. Das Ergibt 2 * 5 * 4 = 40 Checks = Weniger Aufwand = Besser.

Den Faltvorgang kann man nun beliebig wiederholen, bis es einfach keinen Sinn mehr macht.

Jetzt kommt bestimmt jemand schlaues daher und sagt: Moment mal, was ist, wenn ich ein Objekt habe, welches genau auf der Trennlinie des Blattes liegt? Naja, in dem Fall muss man es wohl oder übel mit beiden Punktmengen des Blattes überprüfen. Aber genau das macht der hier vorgestellte 2-Dimensionale Baum (und das ist auch auf 3-Dimensionale Kollisionsprüfung anwendbar).

Es ist jedenfalls möglich, die Anzahl der detaillierten Kollisionsprüfungen auf ein minimum zu beschränken, sodass man bei 2500 Objekten die sich gleichzeitig über den Bildschirm bewegen, nur etwa 200 Kollisionen tatsächlich zu prüfen hat (Zahlen aus dem Beispielprogramm genommen).

Des weiteren könnte man in einem tatsächlichen Spiel die Objekte in Gruppen verteilen, und so weitere Kollisionsprüfungen sparen. Als Beispiel sei hier z.B. ein Spaceshooter genannt, in dem man Raumschiffe und Laserschüsse hat. Natürlich braucht man nicht unbedingt die Laser gegen die Laser zu prüfen, es reicht wenn man Laser gegen Raumschiffe und Raumschiffe gegen Raumschiffe prüft, was eine weitere nicht zu unterschätzende Ersparniss bringen kann.

Erklärung zum Beispiel:
Wenn man das Beispiel startet, sieht man zunächst einen schwarzen Bildschirm. Drückt man die LEERTASTE, so erstellt man 100 kleine Rechtecke die mit unterschiedlicher Geschwindigkeit über den Bildschirm flitzen, und falls sich zwei berühren, eines davon vernichtet wird. Das vernichten kann man natürlich ausschalten (mit "D"), sodass man das auch für sehr viel mehr Objekte testen kann. Mit den Pfeiltasten RAUF und RUNTER kann man die "Faltung" des Blattes einstellen, also in wie viele kleine Bereiche der große Bereich aufgeteilt werden soll.
Im Hintergrund werden die Kästchen und Bereiche angezeigt, welche gerade tatsächlich existieren und benötigt werden (Wenn in einem Bereich keine Objekte sind, dann ist dort auch keine hohe Skalierung nötig und entsprechend große Kästchen sind dann dort zu sehen).

Die Anzeigen sollten selbsterklärend sein, bis auf CollTime:

CollTime: Zeit,welche für die reine Kollisionsprüfung benötigt wird | Zeit, welche für das verwalten und bewegen der Objekte benötigt wird, beides in MS.

Beispiel Kompiliert für Windows

Beispiel Sourcecode (benötigt weiter unten gepostetes Modul)
Code: [AUSKLAPPEN]

superstrict

Import fdm.ndimtree

Const worldxoffset:Int = 0
Const worldyoffset:Int = 0
Const worldwidth:Int = 800
Const worldheight:Int = 600
Global maxCollisionDepth:Int = 7
Global onCollideDestruction:Int = True
Global showCollisionBoxes:Int = True
Global showCollisionBarriers:Int = True

Graphics 800 , 600
SetBlend alphablend

Global objManager:TObjectManager = New TObjectManager

Global DEBUG_Collisions:Int
Global DEBUG_CollisionObjects:Int
Global DEBUG_CollisionManagementTime:Int
Global DEBUG_CollisionCheckTime:Int

Repeat
If KeyHit(KEY_SPACE)
   For Local i:Int = 0 Until 100
   Rem
   Local r:Float = Rnd(0 , 200)
   Local d:Float = Rnd(0,360)
   Local x:Float = r*Sin(d) + 100
   Local y:Float = r*Cos(d) + 300
   End rem
   Local x:Float = Rand(worldxoffset , worldwidth)
   Local y:Float = Rand(worldyoffset , worldheight)

   Local o:T2DObject = T2DObject.Create(x , y , 2 , 2)
   o.speed[0] = (Rand(0 , 1) * 2 - 1) * Rnd(0.5 , 5)
   o.speed[1] = (Rand(0,1)*2-1)*Rnd(0.5,5)
   objManager.addObject(o)
   Next
EndIf

If KeyHit(KEY_UP) maxCollisionDepth:+ 1
If KeyHit(KEY_DOWN)
   maxCollisionDepth:- 1
   If maxCollisionDepth < 0 maxCollisionDepth = 0
EndIf
If KeyHit(KEY_D) onCollideDestruction = Not onCollideDestruction
If KeyHit(KEY_B) showCollisionBoxes = Not showCollisionBoxes
If KeyHit(KEY_N) showCollisionBarriers = Not showCollisionBarriers
If KeyHit(KEY_C)
   objManager.Clear()
EndIf

objManager.process()

Cls
   objManager.render()

   SetAlpha 0.9
   SetColor 0,0,0
   DrawRect 0 , 0 , 230 , 180
   SetAlpha 1
   SetColor 255,255,255
   DrawText "Objects: " + DEBUG_CollisionObjects , 10 , 10
   DrawText "Collisions: " + DEBUG_Collisions , 10 , 30
   DrawText "CollTime: " + DEBUG_CollisionCheckTime+"|"+DEBUG_CollisionManagementTime , 10 , 50
   DrawText "CollDepth(Arrow Keys): " + maxCollisionDepth , 10 , 80
   DrawText "OnHitDestruction(Key D): " + onCollideDestruction , 10 , 100
   DrawText "ShowCollBoxes(Key B): " + showCollisionBoxes , 10 , 120
   DrawText "ShowCollBarriers(Key N): " + showCollisionBarriers , 10 , 140
   DrawText "Clear All Objects(Key C)", 10 , 160

Flip
Until KeyHit(KEY_ESCAPE)
End

Type TObjectManager
Field list:TList = New TList
Field collManager:TCollisionManager

Method New()
   collManager = New TCollisionManager
End Method

Method addObject(o:T2DObject)
   o.setObjectManager(Self , list.addlast(o) )
   o.setCollisionManager(collManager)
   'collManager.check2DObjectSpace(o)
End Method

Method process()
   DEBUG_CollisionManagementTime = MilliSecs()
   For Local o:T2DObject = EachIn list
      o.process()
   Next
   DEBUG_CollisionManagementTime = MilliSecs()-DEBUG_CollisionManagementTime
   DEBUG_Collisions = 0
   DEBUG_CollisionCheckTime = MilliSecs()
   For Local o:T2DObject = EachIn list
      o.collide()
   Next
   DEBUG_CollisionCheckTime = MilliSecs()-DEBUG_CollisionCheckTime
End Method

Method render()
   collManager.debugRender()
   For Local o:T2DObject = EachIn list
      o.render()
   Next
End Method

Method clear()
   For Local o:T2DObject = EachIn list
      o.remove()
   Next
End Method
End Type

Type TCollisionManager
Field collTree:TNDimTree

Method New()
   collTree = New TNDimTree
   collTree.setCompareFunction(Compare2DPositions)
End Method

Method check2DObjectSpace(obj:T2DObject)
   Local s:T2DSpace = obj.space
   If s = Null
      s = T2DSpace(collTree.returnObject(obj) )
      obj.setSpace(s , s.addObject(obj) )
   Else
      If Not s.check2DObjectSpace(obj)
         obj.removeCollisionSpace()
         s = T2DSpace(collTree.returnObject(obj) )
         obj.setSpace(s , s.addObject(obj) )
      EndIf
   EndIf
End Method

Method check2DObjectCollisions:TList(obj:T2DObject)
   Local spacesList:TList = New TList
   Local objectList:TList = New TList
   obj.space.node._addAllContentToList(spacesList)
   For Local s:T2DSpace = EachIn spacesList
      For Local obj2:T2DObject = EachIn s.content
         If obj2.pos[0] + obj2.size[0] < obj.pos[0] Continue
         If obj2.pos[0] > obj.pos[0] + obj.size[0] Continue
         If obj2.pos[1] + obj2.size[1] < obj.pos[1] Continue
         If obj2.pos[1] > obj.pos[1] + obj.size[1] Continue
         If obj2 = obj Continue
         objectList.addlast(obj2)
      Next
   Next
   spacesList = Null
   Return objectList
End Method

Method debugRender()
   Local n:TNDimNode = collTree._rootNode
   If n = Null Return

   'DebugStop()
   renderBarrier(n,worldxoffset,worldyoffset,worldwidth,worldheight)
End Method

Method renderBarrier(n:TNDimNode , x:Float , y:Float,width:Float,height:Float)
   If n = Null Return
   Local d:Int = n.getDepth()
   Local s:T2DSpace = T2DSpace(n.getContent() )
   If s = Null Return
   Local barrier:Float = s.barrier

   If d Mod 2
      If showCollisionBarriers DrawRect x , barrier , width , 1
      renderBarrier(n.leftnode,x , y , width , height*0.5)
      renderBarrier(n.rightnode , x , barrier , width , height * 0.5)
   Else
      If showCollisionBarriers DrawRect barrier , y , 1, height
      renderBarrier(n.leftnode,x , y , width*0.5 , height)
      renderBarrier(n.rightnode , barrier , y , width * 0.5 , height)
   EndIf

   If showCollisionBoxes
      SetAlpha 0.01
      DrawRect s.pos[0] , s.pos[1] , s.size[0] , s.size[1]
      SetAlpha 1
   EndIf
   'DrawText d,x+width*0.5,y+height*0.5
End Method
End Type

Function Compare2DPositions:Int(val:Object , node:TNDimNode)
Local obj:T2DObject = T2DObject(val)
Local space:T2DSpace = T2DSpace(node.getContent() )
Local depth:Int = node.getDepth()

If space = Null
   space = New T2DSpace
   space.setBarrier(node)
   node.setContent(space)
EndIf

If depth >= maxCollisionDepth Return 0

If depth Mod 2
   If obj.pos[1] > space.barrier Return 1
   If obj.pos[1] + obj.size[1] < space.barrier Return -1
   Return 0
Else
   If obj.pos[0] > space.barrier Return 1
   If obj.pos[0] + obj.size[0] < space.barrier Return -1
   Return 0
EndIf
End Function

Type T2DSpace
Field content:TList = New TList
Field node:TNDimNode

Method addObject:TLink(obj:T2DObject)
   Return content.addlast(obj)
End Method

Method removedObject()
   If content.count() > 0 Return'no reason to check.
   If node.noSuccessors()
      Local pnode:TNDimNode = node.upperNode
      node.remove()
      If pnode T2DSpace(pnode.content).removedObject()
   EndIf
End Method

Field barrier:Float
Field depth:Int'debug
Field direction:Byte

Field pos:Float[2]
Field size:Float[2]

Method setBarrier(node:TNDimNode)
   Self.depth = node.getDepth()
   Self.direction = depth Mod 2
   Self.node = node
   Local axis:Byte = depth Mod 2 'axis 0=x-axis, 1=y-axis

   pos[0] = worldxoffset
   pos[1] = worldyoffset
   size[0] = worldwidth
   size[1] = worldheight

   If axis
      barrier = worldyoffset + worldheight / 2^Floor(depth*0.5+1)
   Else
      barrier = worldxoffset + worldwidth / 2^Floor(depth*0.5+1)
   EndIf

   If node.upperNode
      Local parentSpace:T2DSpace = T2DSpace(node.upperNode.content)
      pos[0] = parentSpace.pos[0]
      pos[1] = parentSpace.pos[1]

      If axis
         size[0] = parentSpace.size[0] * 0.5
         size[1] = parentSpace.size[1]
      Else
         size[0] = parentSpace.size[0]
         size[1] = parentSpace.size[1] * 0.5
      EndIf

      If node.direction > 0
         If axis
            pos[0]:+size[0]
         Else
            pos[1]:+size[1]
         EndIf
      EndIf

      node = node.upperNode

      If node.upperNode
         If node.direction < 0
            barrier = T2DSpace(node.upperNode.content).barrier - barrier
         ElseIf node.direction > 0
            barrier = T2DSpace(node.upperNode.content).barrier + barrier
         EndIf
      EndIf
   EndIf
End Method

Rem
   bbdoc: Checks if object is still in this space
end rem
Method check2DObjectSpace:Byte(obj:T2DObject)
   If obj.pos[0] >= pos[0] And obj.pos[1] >= pos[1]
   If obj.pos[0] + obj.size[0] <= pos[0] + size[0] And obj.pos[1] + obj.size[1] <= pos[1] + size[1]
      If depth = maxCollisionDepth Return True
      'check if object lays over the middle barrier
      If obj.pos[direction] <= barrier And obj.pos[direction] + obj.size[direction] >= barrier Return True
      'Otherwise it can be sorted deeper into the heap
      Return False
   EndIf
   EndIf
End Method
End Type

Type T2DObject
Field pos:Float[2]
Field size:Float[2]
Field speed:Float[2]

Field collisionManager:TCollisionManager
Field space:T2DSpace
Field spaceLink:TLink

Field objectManager:TObjectManager
Field objectManagerLink:TLink

Method setSpace(space:T2DSpace , spaceLink:TLink)
   Assert space <> Null , "T2DObject.setSpace() space = NULL"
   Assert spaceLink <> Null , "T2DObject.setSpace() spaceLink = NULL"
   Self.space = space
   Self.spaceLink = spaceLink
End Method

Method process()
   Local x:Float = pos[0] + speed[0]
   Local y:Float = pos[1] + speed[1]
   processBoundaries(x,y)
   setPos(x,y)
End Method

Method collide()
   If collisionManager
      Local l:TList = collisionManager.check2DObjectCollisions:TList(Self)
      If l.isEmpty() Return
      DEBUG_Collisions:+1
      If onCollideDestruction Self.remove()
   EndIf
End Method

Method processBoundaries(x:Float Var, y:Float Var)
   If x < worldxoffset x = worldxoffset; speed[0] = -speed[0]
   If y < worldyoffset y = worldyoffset; speed[1] = -speed[1]

   If x + size[0] > worldwidth+worldxOffset x = worldwidth - size[0] ; speed[0] = - speed[0]
   If y + size[1] > worldheight y = worldheight + worldyoffset - size[1] ; speed[1] = - speed[1]
End Method

Method setPos(x:Float , y:Float)
   pos[0] = x
   pos[1] = y
   If collisionManager collisionManager.check2DObjectSpace(Self)
End Method

Method setSize(width:Float , height:Float)
   size[0] = width
   size[1] = height
End Method

Method setObjectManager(m:TObjectManager , managerLink:TLink)
   Self.objectManager = m
   objectManagerLink = managerLink
End Method

Method setCollisionManager(m:TCollisionManager)
   Self.collisionManager = m
End Method

Method New()
   DEBUG_CollisionObjects:+ 1
End Method

Method remove()
   removeObjectManager()
   DEBUG_CollisionObjects:-1
End Method

Method removeObjectManager()
   If objectManagerLink RemoveLink(objectManagerLink); objectManagerLink=Null
   objectManager = Null
   removeCollisionManager()
End Method

Method removeCollisionManager()
   collisionManager = Null
   removeCollisionSpace()
End Method

Method removeCollisionSpace()
   If spaceLink RemoveLink(spaceLink) ; spaceLink = Null
   If space = Null Return
   space.removedObject()
   space = Null
End Method

Method render()
   DrawRect pos[0] , pos[1] , size[0] , size[1]
   'DrawText space.depth,pos[0] , pos[1]
End Method

Function Create:T2DObject(x:Float , y:Float , width:Float , height:Float)
   Local o:T2DObject = New T2DObject
   o.setPos(x , y)
   o.setSize(width , height)
   Return o
End Function
End Type

Modul fdm.mod/ndimtree.mod/ndimtree.bmx
Code: [AUSKLAPPEN]

Rem
bbdoc: Illusion-Games NDimTree (N - Dimensional Tree)
about: For sorting and finding keys or x-dimensional object spaces. Its non-dynamicly, means it will
create the full twig down to the exact value. So think before use! If you just want to save small
data amount with high differences (like Strings) you should prefer TMap. But if you want to create
a 2Dim or 3Dim Collision detection, than this should be your choice.
EndRem

Module fdm.ndimtree
ModuleInfo "Version: 0.0.1"
ModuleInfo "Label: Illusion-Games"
ModuleInfo "Authors: Christian Geissler"

ModuleInfo "Update: 0"

SuperStrict

Import brl.linkedlist

Public

Type TNDimTree
Rem
   bbdoc: Get the compareFunction for this TNDimTree object.
End Rem
Method GetcompareFunction:Int(key:Object, node:TNDimNode) ()
   Return _compareFunction
End Method
Rem
   bbdoc: Set the compareFunction for this TBinaryTree object.
End Rem
Method SetcompareFunction(f:Int(key:Object, node:TNDimNode))
   _compareFunction = f
End Method

Rem
   bbdoc: insert an object into the n-dim tree using key:Object to find related position.
   returns: depth of related node
end rem
Method insertObject:Int(key:Object, obj:Object)
   Local node:TNDimNode = _getRelatedNode(key)
   Assert node.content = Null, "TBinaryTree.insertObject() trying to overwrite existing object"
   node.content = obj
   Return node.Getdepth()
End Method

Rem
   bbdoc: return saved object from the n-dim tree using key:Object to find related position.
end rem
Method returnObject:Object(key:Object)
   Local node:TNDimNode = _getRelatedNode(key)
   Return node.content
End Method

Rem
   bbdoc: searches for related node and returns a list of all subcontent objects
end rem
Method returnSubObjects:TList(key:Object)
   Local list:TList = New TList
   Local node:TNDimNode = _getRelatedNode(key)
   node._addAllContentToList(list)
   Return list
End Method

Rem
   bbdoc: remove saved object from the n-dim tree using key:Object to find related position.
   abount: object needs to exist already. If you are not shure if it exists, use returnObject() or ReturnAndRemoveObject()
end rem
Method removeObject(key:Object)
   Local node:TNDimNode = _getRelatedNode(key)
   Assert node.content <> Null, "TBinaryTree.removeObject() there is no object that can be removed"
   node.content = Null
End Method

Rem
   bbdoc: removes and returns object specified by key:Object. If object does not exist, it returns null.
   returns: related object OR NULL if there is no related object.
end rem
Method ReturnAndRemoveObject:Object(key:Object)
   Local node:TNDimNode = _getRelatedNode(key)
   Local obj:Object = node.content
   node.content = Null
   Return obj
End Method

Rem
   bbdoc: removes all saved values from this NDimTree.
end rem
Method clear()
   If _rootNode _rootNode.remove()
   _rootNode = Null
End Method

Rem
   bbdoc: compareFunction is a function that returns
   -1 if object is lower than value it should be
   0 if object matches value
   1 if object is higher than value it should be

   depth starts from 0 to intMax
   attention: compareFunction finaly has to return 0, otherwise algorithm doesn't work.
end rem
Field _compareFunction:Int(key:Object, node:TNDimNode)
Field _rootNode:TNDimNode

Method _getRelatedNode:TNDimNode(key:Object, startNode:TNDimNode = Null)
   Local currentNode:TNDimNode
   Local eval:Int
   Local depth:Int

   depth = 0
   If Not _rootNode _rootNode = TNDimNode.Create(depth)
   If startNode = Null startNode = _rootNode
   currentNode = startNode

   eval = _compareFunction(key, currentNode)
   While eval <> 0
      If eval < 0
         If currentNode.leftNode = Null currentNode.leftNode = TNDimNode.Create(depth + 1, currentNode, -1)
         currentNode = currentNode.leftNode
      Else
         If currentNode.rightNode = Null currentNode.rightNode = TNDimNode.Create(depth + 1, currentNode, 1)
         currentNode = currentNode.rightNode
      EndIf
      depth:+1
      eval = _compareFunction(key, currentNode)
   Wend
   Return currentNode
End Method
End Type

Type TNDimNode
Field leftNode:TNDimNode
Field rightNode:TNDimNode
Field upperNode:TNDimNode
Field content:Object
Field depth:Int
Field direction:Int '-1 for left, 1 for right, 0 for root

Method noSuccessors:Byte()
   Return (leftNode = Null And rightNode = Null)
End Method

Rem
   bbdoc: Get the content value in this TNDimNode object.
End Rem
Method Getcontent:Object()
   Return content
End Method
Rem
   bbdoc: Set the content value for this TNDimNode object.
End Rem
Method Setcontent(Value:Object)
   content = Value
End Method

Rem
   bbdoc: Get the depth value in this TNDimNode object.
End Rem
Method Getdepth:Int()
   Return depth
End Method
Rem
   bbdoc: Set the depth value for this TNDimNode object.
End Rem
Method Setdepth(Value:Int)
   depth = Value
End Method

Function Create:TNDimNode(depth:Int, upperNode:TNDimNode = Null, direction:Int = 0)
   Local n:TNDimNode = New TNDimNode
   n.Setdepth(depth)
   n.upperNode = upperNode
   n.direction = direction
   Return n
End Function

Method _addAllContentToList(list:TList)
   If leftNode leftNode._addAllContentToList(list)
   If content list.AddLast(content)
   If rightNode rightNode._addAllContentToList(list)
End Method

Method remove()
   If leftNode leftNode.remove() ;leftNode = Null
   If rightNode rightNode.remove() ;rightNode = Null
   If upperNode = Null Return
   If direction < 0 upperNode.leftNode = Null
   If direction > 0 upperNode.rightNode = Null
   upperNode = Null
End Method
End Type

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	ComNik	Fr, Sep 18, 2009 22:28 Antworten mit Zitat
Wunderbar. Echt super. Ich habe an diese Möglichkeit der Kollisionsprüfung in Verbindung mit meiner Physik Engine gedacht, umgesetzt aber noch nicht. Läuft schnell und einwandfrei (: lg ComNik
WIP: Vorx.Engine

ComNik

Fr, Sep 18, 2009 22:28
Antworten mit Zitat

Wunderbar. Echt super.
Ich habe an diese Möglichkeit der Kollisionsprüfung in Verbindung mit meiner Physik Engine gedacht, umgesetzt aber noch nicht.

Läuft schnell und einwandfrei (:

lg
ComNik

WIP: Vorx.Engine

	Firstdeathmaker	Sa, Sep 19, 2009 10:57 Antworten mit Zitat
Naja, das einzige Problem ist halt, dass man empirisch herausfinden muss welche Unterteilungstiefe am sinnvollsten ist. Bei dem Beispiel habe ich festgestellt, dass 7 die beste ist. Der Nachteil einer zu feinen Unterteilung ist ein zu großer Verwaltungsoverhead, weil die Objekte dauernd den Bereich wechseln würden. Man könnte die Geschwindigkeit übrigens noch weiter steigern, wenn man beim Verlassen eines Bereichs nicht einfach komplett neu einsortieren würde, sondern individuell schauen würde wo es hinkommen muss (da der UpperNode und die Children bekannt sind). Das würde den Verwaltuingsoverhead nocheinmal kleiner machen. Aber da dieser derzeit sowieso noch ziemlich klein ist, sah ich das nicht so als Problem.
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Sa, Sep 19, 2009 10:57
Antworten mit Zitat

Naja, das einzige Problem ist halt, dass man empirisch herausfinden muss welche Unterteilungstiefe am sinnvollsten ist. Bei dem Beispiel habe ich festgestellt, dass 7 die beste ist. Der Nachteil einer zu feinen Unterteilung ist ein zu großer Verwaltungsoverhead, weil die Objekte dauernd den Bereich wechseln würden.

Man könnte die Geschwindigkeit übrigens noch weiter steigern, wenn man beim Verlassen eines Bereichs nicht einfach komplett neu einsortieren würde, sondern individuell schauen würde wo es hinkommen muss (da der UpperNode und die Children bekannt sind). Das würde den Verwaltuingsoverhead nocheinmal kleiner machen. Aber da dieser derzeit sowieso noch ziemlich klein ist, sah ich das nicht so als Problem.

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	ComNik	Sa, Sep 19, 2009 12:32 Antworten mit Zitat
Jap das hatte ich auch so vor. Hast du einen guten Artikel zu dem Thema? Ich bin da zwar theoretisch ein bisschen informiert. Aber so richtig ins Detail konnte ich aufgrund anderer Projekte noch nicht gehen. Wär super (: lg ComNik
WIP: Vorx.Engine

ComNik

Sa, Sep 19, 2009 12:32
Antworten mit Zitat

Jap das hatte ich auch so vor. Hast du einen guten Artikel zu dem Thema? Ich bin da zwar theoretisch ein bisschen informiert. Aber so richtig ins Detail konnte ich aufgrund anderer Projekte noch nicht gehen.
Wär super (:

lg
ComNik

WIP: Vorx.Engine

	Firstdeathmaker	Sa, Sep 19, 2009 14:27 Antworten mit Zitat
Naja, Wikipedia hilft da, hab dazu leider keine Unterlagen aus meinem Studium mehr, ist schon 1 Jahr her. Wikipedia KD-Tree (k-Dimensional) Die englische Version ist um Welten besser als der deutsche Artikel. Im Grunde genommen ist es jedoch echt simpel: Im 1-Dimensionalen Funktioniert so ein Baum folgendermaßen: Vorraussetzung: Die Elemente besitzen eine totale Ordnung, d.h. du kannst für jedes Element bestimmen, ob es größer, kleiner oder gleich einem anderen ist, und daraus Schlüsse ziehen wie: Wenn a < b und c < a, dann ist c < b. Das ist z.B. für alle natürlichen Zahlen der Fall. Wenn man diese Zahlen nun in einen 1-Dimensionalen Baum einsortieren möchte, kann man folgendermaßen vorgehen: Wenn eine neue Zahl in den Baum eingefügt werden soll, dann geht man von oben (von der Wurzel) des Baumes los und schaut an jeder Verzweigung (Knoten), ob die gegebene Zahl kleiner oder größer als die im Knoten gespeicherte Zahl ist. Wenn sie kleiner ist, wird nach links weiter gegangen, wenn sie größer ist nach rechts. Wenn dort kein weiterer Knoten ist, wird ein neuer Knoten erstellt und die Zahl dort einsortiert: Beispiel Zahlenmenge: 5,3,8,2,1,4,7 Code: [AUSKLAPPEN] [EINKLAPPEN] 5 5 3 5 3 8 5 3 8 2 5 3 8 2 1 5 3 8 2 4 1 5 3 8 2 4 7 1 Man sieht jetzt schon, dass sich der Baum auch ziemlich schlecht entwickeln kann, je nachdem wie die Zahlenmenge aussieht welche man einsortiert. Wenn man z.B. die Menge: 9,8,7,6,5,4,3,2,1 einsortieren würde, dann werden die immer ganz links einsortiert, und man bekommt eine ganz lange Kette ohne Vereinfachungen für die Suche. Es gibt bestimmte Algorithmen, die sicherstellen können, dass ein solch "unbalancierter" Baum umgestellt wird, sodass er wieder einigermaßen gleich verteilt ist. Mehrdimensionale Bäume funktionieren auf fast die gleiche Art, nur dass die Werte welche einsortiert werden Vektoren sind (also Wertepaare) und man abwechselnd den einen oder den anderen Wert anschaut um festzustellen ob man nach links oder nach rechts einsortiert. Beispiel: Werte: (1,3), (3,5),(2,10),(2,4) * - bezeichnet den neu eingefügten Vektor Code: [AUSKLAPPEN] [EINKLAPPEN] (1,3)* (1,3) // die 3 von (3,5) is größer als die 1, also nach rechts einsortieren. (3,5)* (1,3) // die 2 von (2,10) is größer als die 1, also nach rechts einsortieren. (3,5) // die 10 von (2,10) ist größer als die 5, also nach rechts einsortieren. (2,10)* (1,3) // die 2 von (2,4) is größer als die 1, also nach rechts einsortieren. (3,5) // die 4 von (2,4) ist kleiner als die 5, also nach links einsortieren. (2,4)* (2,10) Bei dem von mir erstellten Beispiel benutze ich den Baum allerdings nicht in dieser Art. Vielmehr lege ich vorher den genauen Bereich fest welchen der Baum abdecken soll. In meinem Falle den ganzen Bildschirm, also x=0, y=0, widht=800, height=600. Und dann wird an jedem Knoten nur danach entschieden ob das Objekt nach links oder rechts einsortiert werden soll, wenn es kleiner oder größer als die in diesem Knoten festgelegte Grenze ist. Das ganze habe ich dann nur noch in der Tiefe begrenzt, damit das nicht unendlich weit in immer kleinere Gebiete unterteilt wird. Falls die maximale Tiefe erreicht ist, wird das angeschaute Objekt einfach dem tiefsten Knoten zugeordnet. Dadurch habe ich für jedes Objekt ein eindeutiges Gebiet. Falls es genau auf der Kante zweier Gebiete liegt, wird es einfach im darüberliegenden, beide umfassende Gebiet gespeichert. Und da sich die ganzen Objekte ja auch bewegen können sollen, muss eine Prüfung erfolgen ob das Objekt noch im richtigen Bereich liegt. Daher hat jedes Gebiet (im Code mit T2DSpace bezeichnet) einen x,y,width und height Wert mit welchem das schnell geprüft werden kann. Falls das Gebiet nicht in der maximalen Tiefe liegt, besitzt es natürlich 2 kleine Teilgebiete welche das Gebiet in 2 Teile Teilen (also z.B. wäre unser normales Gebiet das ganze Blatt Papier, und die beiden untergeordneten Teilgebiete wären die beiden Hälften links und rechts des Knickes welcher das Blatt in 2 gleichgroße Hälften teilt). Sobald das Betrachtete Objekt, welchem im Moment noch unserem großen Gebiet zugeordnet ist, den Knick verlässt, kann es eindeutig einem kleineren Gebiet zugeordnet werden. Andersherum geht das natürlich auch: Wenn das Objekt einem der kleinen Gebiete zugeordnet war, und dieses aber jetzt verlassen hat, kann es solange an größere "parent"-Gebiete weitergereicht werden, bis es wieder in einem Gebiet liegt. Falls du oder jmd anderer noch weitere Fragen hat, dann könnt ihr mir die gerne stellen
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Sa, Sep 19, 2009 14:27
Antworten mit Zitat

Naja, Wikipedia hilft da, hab dazu leider keine Unterlagen aus meinem Studium mehr, ist schon 1 Jahr her.

Wikipedia KD-Tree (k-Dimensional) Die englische Version ist um Welten besser als der deutsche Artikel.

Im Grunde genommen ist es jedoch echt simpel:

Im 1-Dimensionalen Funktioniert so ein Baum folgendermaßen:

Vorraussetzung: Die Elemente besitzen eine totale Ordnung, d.h. du kannst für jedes Element bestimmen, ob es größer, kleiner oder gleich einem anderen ist, und daraus Schlüsse ziehen wie: Wenn a < b und c < a, dann ist c < b. Das ist z.B. für alle natürlichen Zahlen der Fall. Wenn man diese Zahlen nun in einen 1-Dimensionalen Baum einsortieren möchte, kann man folgendermaßen vorgehen: Wenn eine neue Zahl in den Baum eingefügt werden soll, dann geht man von oben (von der Wurzel) des Baumes los und schaut an jeder Verzweigung (Knoten), ob die gegebene Zahl kleiner oder größer als die im Knoten gespeicherte Zahl ist. Wenn sie kleiner ist, wird nach links weiter gegangen, wenn sie größer ist nach rechts. Wenn dort kein weiterer Knoten ist, wird ein neuer Knoten erstellt und die Zahl dort einsortiert:

Beispiel
Zahlenmenge: 5,3,8,2,1,4,7

Code: [AUSKLAPPEN]

5

5
3

5
3 8

5
3 8
2

5
3 8
2
1

5
3 8
2 4
1

5
3 8
2 4 7
1

Man sieht jetzt schon, dass sich der Baum auch ziemlich schlecht entwickeln kann, je nachdem wie die Zahlenmenge aussieht welche man einsortiert. Wenn man z.B. die Menge: 9,8,7,6,5,4,3,2,1 einsortieren würde, dann werden die immer ganz links einsortiert, und man bekommt eine ganz lange Kette ohne Vereinfachungen für die Suche. Es gibt bestimmte Algorithmen, die sicherstellen können, dass ein solch "unbalancierter" Baum umgestellt wird, sodass er wieder einigermaßen gleich verteilt ist.

Mehrdimensionale Bäume funktionieren auf fast die gleiche Art, nur dass die Werte welche einsortiert werden Vektoren sind (also Wertepaare) und man abwechselnd den einen oder den anderen Wert anschaut um festzustellen ob man nach links oder nach rechts einsortiert.

Beispiel:
Werte: (1,3), (3,5),(2,10),(2,4)
* - bezeichnet den neu eingefügten Vektor

Code: [AUSKLAPPEN]

(1,3)*

(1,3) // die 3 von (3,5) is größer als die 1, also nach rechts einsortieren.
(3,5)*

(1,3) // die 2 von (2,10) is größer als die 1, also nach rechts einsortieren.
(3,5) // die 10 von (2,10) ist größer als die 5, also nach rechts einsortieren.
(2,10)*

(1,3) // die 2 von (2,4) is größer als die 1, also nach rechts einsortieren.
(3,5) // die 4 von (2,4) ist kleiner als die 5, also nach links einsortieren.
(2,4)* (2,10)

Bei dem von mir erstellten Beispiel benutze ich den Baum allerdings nicht in dieser Art. Vielmehr lege ich vorher den genauen Bereich fest welchen der Baum abdecken soll. In meinem Falle den ganzen Bildschirm, also x=0, y=0, widht=800, height=600. Und dann wird an jedem Knoten nur danach entschieden ob das Objekt nach links oder rechts einsortiert werden soll, wenn es kleiner oder größer als die in diesem Knoten festgelegte Grenze ist.
Das ganze habe ich dann nur noch in der Tiefe begrenzt, damit das nicht unendlich weit in immer kleinere Gebiete unterteilt wird. Falls die maximale Tiefe erreicht ist, wird das angeschaute Objekt einfach dem tiefsten Knoten zugeordnet.

Dadurch habe ich für jedes Objekt ein eindeutiges Gebiet. Falls es genau auf der Kante zweier Gebiete liegt, wird es einfach im darüberliegenden, beide umfassende Gebiet gespeichert.

Und da sich die ganzen Objekte ja auch bewegen können sollen, muss eine Prüfung erfolgen ob das Objekt noch im richtigen Bereich liegt. Daher hat jedes Gebiet (im Code mit T2DSpace bezeichnet) einen x,y,width und height Wert mit welchem das schnell geprüft werden kann.

Falls das Gebiet nicht in der maximalen Tiefe liegt, besitzt es natürlich 2 kleine Teilgebiete welche das Gebiet in 2 Teile Teilen (also z.B. wäre unser normales Gebiet das ganze Blatt Papier, und die beiden untergeordneten Teilgebiete wären die beiden Hälften links und rechts des Knickes welcher das Blatt in 2 gleichgroße Hälften teilt). Sobald das Betrachtete Objekt, welchem im Moment noch unserem großen Gebiet zugeordnet ist, den Knick verlässt, kann es eindeutig einem kleineren Gebiet zugeordnet werden.

Andersherum geht das natürlich auch: Wenn das Objekt einem der kleinen Gebiete zugeordnet war, und dieses aber jetzt verlassen hat, kann es solange an größere "parent"-Gebiete weitergereicht werden, bis es wieder in einem Gebiet liegt.

Falls du oder jmd anderer noch weitere Fragen hat, dann könnt ihr mir die gerne stellen Wink

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	ComNik	Sa, Sep 19, 2009 14:45 Antworten mit Zitat
Vielen, vielen Dank. Ich wusste da jetzt zwar ein bisschen was aber das ist super erklärt. Ich werde das mal in die Physik Engine einbauen und hoffen das es genauso gut funktionier. Danke nochmal, lg ComNik
WIP: Vorx.Engine

ComNik

Sa, Sep 19, 2009 14:45
Antworten mit Zitat

Vielen, vielen Dank. Ich wusste da jetzt zwar ein bisschen was aber das ist super erklärt. Ich werde das mal in die Physik Engine einbauen und hoffen das es genauso gut funktionier.

Danke nochmal, lg
ComNik

WIP: Vorx.Engine

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

Nach Oben

BlitzBasic Portal

Kollisionsbeispiel + Minitutorial + N-Dimensionaler-Baum

Firstdeathmaker

Betreff: Kollisionsbeispiel + Minitutorial + N-Dimensionaler-Baum

ComNik

Firstdeathmaker

ComNik

Firstdeathmaker

ComNik