Nahestes Entity Finden...

Übersicht

BlitzBasic

Blitz3D

	AnniXa Betreff: Nahestes Entity Finden...	Mi, Apr 01, 2009 9:48 Antworten mit Zitat
Gibt es eine elegante und schnelle möglichkeit das "naheste entity" zu finden? Derzeit mache ich das so: ich hab viele entity-handles in einem type organisiert. es gibt 2 arten von entitys A und B. Alle entitys von typ A suchen nun immer nach dem nahesten von Typ B Dafür läuft eine for-each schleife alle A´s durch und für jeden durchlauf werden wiederum alle B´s durchgelaufen und das für welches der geringsten "EntityDistance" wert ermittelt wurde wird übergeben. klar das dies bei vielen entitys natürlich nicht sehr flott geht, daher meine frage: Gibt es eine bessere schnellere und effizientere möglichkeit das naheste entity zu finden?

AnniXa

Betreff: Nahestes Entity Finden...

Mi, Apr 01, 2009 9:48
Antworten mit Zitat

Gibt es eine elegante und schnelle möglichkeit das "naheste entity" zu finden?

Derzeit mache ich das so:
ich hab viele entity-handles in einem type organisiert.
es gibt 2 arten von entitys A und B.
Alle entitys von typ A suchen nun immer nach dem nahesten von Typ B
Dafür läuft eine for-each schleife alle A´s durch und für jeden durchlauf werden wiederum alle B´s durchgelaufen und das für welches der geringsten "EntityDistance" wert ermittelt wurde wird übergeben.

klar das dies bei vielen entitys natürlich nicht sehr flott geht, daher meine frage:

Gibt es eine bessere schnellere und effizientere möglichkeit das naheste entity zu finden?

	Xaymar ehemals "Cgamer"	Mi, Apr 01, 2009 12:04 Antworten mit Zitat
Die Daten z.b. Cachen. und dann nur für veränderte entities neuüberprüfen. Das sollte es eigentlich sehr verschnellern
Warbseite

Xaymar

ehemals "Cgamer"

Mi, Apr 01, 2009 12:04
Antworten mit Zitat

Die Daten z.b. Cachen. und dann nur für veränderte entities neuüberprüfen. Das sollte es eigentlich sehr verschnellern

Warbseite

	Mr.Keks	Mi, Apr 01, 2009 12:22 Antworten mit Zitat
Hi, ja, ich würde auch erstmal versuchen, nicht mehr jedes Frame alle Abstände zu berechnen. Sollte dies aber tatsächlich notwendig sein, kommst du wohl um eine Aufteilung des Raums nicht herum. Diese Aufteilung könnte zum Beispiel so aussehen, dass du den Raum, in dem sich deine Entities bewegen in 16x16x16 (Zahl ist jetzt beliebig) Quader aufteilst. (Fortgeschrittene würden hier evtl. auch komplexere Raumaufteilungen wählen...) Bevor du jetzt die Abstände berechnest, ordnest du die Entities den Quadern zu und erstellst für jeden Quader eine Liste der sich darin befindenden Entities (linearer Aufwand). Jetzt beginnst du die ganzen A-Entities durchzugehen. Gibt es B-Entities im selben Quader? Ansonsten nimm die Entities aus den umliegenden Quadern hinzu, sodass du einen noch größeren Quader erhälst! Nun schaue, welches der in dem Bereich liegenden B-Entities den geringsten Abstand zu dem ausgewählten A hat. Dieses ist mit ziemlich hoher Wahrscheinlichkeit das nächste an dem A. Allerdings nur, wenn es innerhalb des Abstands des A-Entities von der nächsten Wand des großen Quaders liegt. Ansonsten könnte es sein, dass kurz jenseits der entsprechenden Wand ein noch näheres B liegt. Um das zu umgehen, vergrößere den Suchquadranten so, dass alle Entities, die denselben Abstand haben wie das B darin liegen müssen und überprüfe die B-Entities in den neu hinzugekommenen Quadern auch noch auf ihren Abstand zum A-Entity. Das ganze klingt jetzt vielleicht etwas umständlicher als nur zwei verschachtelte Schleifen, sollte aber auf jeden Fall in einer niedrigeren Aufwandsklasse liegen und ist jetzt auch so ziemlich der verständlichste/simpelste Algo, der mir dazu einfällt . Viel Spaß bei der Umsetzung!
MrKeks.net

Mr.Keks

Mi, Apr 01, 2009 12:22
Antworten mit Zitat

Hi, ja, ich würde auch erstmal versuchen, nicht mehr jedes Frame alle Abstände zu berechnen. Sollte dies aber tatsächlich notwendig sein, kommst du wohl um eine Aufteilung des Raums nicht herum.

Diese Aufteilung könnte zum Beispiel so aussehen, dass du den Raum, in dem sich deine Entities bewegen in 16x16x16 (Zahl ist jetzt beliebig) Quader aufteilst. (Fortgeschrittene würden hier evtl. auch komplexere Raumaufteilungen wählen...) Bevor du jetzt die Abstände berechnest, ordnest du die Entities den Quadern zu und erstellst für jeden Quader eine Liste der sich darin befindenden Entities (linearer Aufwand).
Jetzt beginnst du die ganzen A-Entities durchzugehen. Gibt es B-Entities im selben Quader? Ansonsten nimm die Entities aus den umliegenden Quadern hinzu, sodass du einen noch größeren Quader erhälst! Nun schaue, welches der in dem Bereich liegenden B-Entities den geringsten Abstand zu dem ausgewählten A hat. Dieses ist mit ziemlich hoher Wahrscheinlichkeit das nächste an dem A. Allerdings nur, wenn es innerhalb des Abstands des A-Entities von der nächsten Wand des großen Quaders liegt. Ansonsten könnte es sein, dass kurz jenseits der entsprechenden Wand ein noch näheres B liegt. Um das zu umgehen, vergrößere den Suchquadranten so, dass alle Entities, die denselben Abstand haben wie das B darin liegen müssen und überprüfe die B-Entities in den neu hinzugekommenen Quadern auch noch auf ihren Abstand zum A-Entity.

Das ganze klingt jetzt vielleicht etwas umständlicher als nur zwei verschachtelte Schleifen, sollte aber auf jeden Fall in einer niedrigeren Aufwandsklasse liegen und ist jetzt auch so ziemlich der verständlichste/simpelste Algo, der mir dazu einfällt . Viel Spaß bei der Umsetzung!

MrKeks.net

	AnniXa	Mi, Apr 01, 2009 13:03 Antworten mit Zitat
Zitat: Die Daten z.b. Cachen. und dann nur für veränderte entities neuüberprüfen. Das sollte es eigentlich sehr verschnellern Die idee von mr.keks klingt sehr vielversprechend, hierzu hätte ich eine frage: Zitat: Bevor du jetzt die Abstände berechnest, ordnest du die Entities den Quadern zu und erstellst für jeden Quader eine Liste der sich darin befindenden Entities ich würde nun die quader selbst auch als type´s anlegen, wie kann ich dann eine liste innerhalb eines types machen? kann man types in types verpacken?

AnniXa

Mi, Apr 01, 2009 13:03
Antworten mit Zitat

Zitat:

Die Daten z.b. Cachen. und dann nur für veränderte entities neuüberprüfen. Das sollte es eigentlich sehr verschnellern

Die idee von mr.keks klingt sehr vielversprechend, hierzu hätte ich eine frage:
Zitat:

Bevor du jetzt die Abstände berechnest, ordnest du die Entities den Quadern zu und erstellst für jeden Quader eine Liste der sich darin befindenden Entities

ich würde nun die quader selbst auch als type´s anlegen, wie kann ich dann eine liste innerhalb eines types machen?
kann man types in types verpacken?

	peacemaker	Mi, Apr 01, 2009 13:06 Antworten mit Zitat
Das geht, ist aber etwas unbequem, weil ja alle Types miteinder verknüpft sind. Dann musst du entweder nen Type für die einzelnen Verbindungen machen, oder im Entity-Type die Instanz des nächsten speichern... Code: [AUSKLAPPEN] [EINKLAPPEN] Type Quader field entity.Entity End type Type Entity field nextEntity.Entity End Type
~Tehadon~ www.tehadon.de http://www.blitzforum.de/worklogs/14/

peacemaker

Mi, Apr 01, 2009 13:06
Antworten mit Zitat

Das geht, ist aber etwas unbequem, weil ja alle Types miteinder verknüpft sind. Dann musst du entweder nen Type für die einzelnen Verbindungen machen, oder im Entity-Type die Instanz des nächsten speichern...

Code: [AUSKLAPPEN]

Type Quader
field entity.Entity
End type

Type Entity
field nextEntity.Entity
End Type

~Tehadon~
www.tehadon.de
http://www.blitzforum.de/worklogs/14/

	Noobody	Mi, Apr 01, 2009 13:15 Antworten mit Zitat
Du kannst die Types natürlich auch in Blitzarrays stecken: Code: [AUSKLAPPEN] [EINKLAPPEN] Type TCube Field EntityCount Field Entities.TEntity[ 64 ] End Type Type TEntity Field X#, Y#, Z# End Type Function AddEntityToCube( Cube.TCube, Entity.TEntity ) Cube\Entities[ Cube\EntityCount ] = Entity Cube\EntityCount = Cube\EntityCount + 1 End Function Function DoSomething( Cube.TCube ) For i = 0 to Cube\EntityCount - 1 Print Cube\Entities[ i ]\X# + " " + Cube\Entities[ i ]\Y# + " " + Cube\Entities[ i ]\Z# Next End Function
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

Mi, Apr 01, 2009 13:15
Antworten mit Zitat

Du kannst die Types natürlich auch in Blitzarrays stecken: Code: [AUSKLAPPEN]

Type TCube
Field EntityCount
Field Entities.TEntity[ 64 ]
End Type

Type TEntity
Field X#, Y#, Z#
End Type

Function AddEntityToCube( Cube.TCube, Entity.TEntity )
Cube\Entities[ Cube\EntityCount ] = Entity
Cube\EntityCount = Cube\EntityCount + 1
End Function

Function DoSomething( Cube.TCube )
For i = 0 to Cube\EntityCount - 1
Print Cube\Entities[ i ]\X# + " " + Cube\Entities[ i ]\Y# + " " + Cube\Entities[ i ]\Z#
Next
End Function

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	AnniXa Betreff: okay	Mi, Apr 01, 2009 17:43 Antworten mit Zitat
danke für die tips, ich probiere das mal auszuknobeln.

AnniXa

Betreff: okay

Mi, Apr 01, 2009 17:43
Antworten mit Zitat

danke für die tips, ich probiere das mal auszuknobeln.

	Krischan	Do, Apr 02, 2009 15:30 Antworten mit Zitat
Versuch es mal hiermit, sorry ist nicht gut kommentiert (habs noch etwas auf das Wesentliche reduziert), war auch nur ein Test für einen minimalen Spannbaum. Es werden 1000 Sterne zufällig im Raum plaziert und mittels der Funktion Calcnearest der nächstliegende Stern ermittelt (kannst auch 10.000, 100.000 nehmen nur dann fliegt Dir die 3D-Anzeige mit den Linien um die Ohren, die Suche nach dem nächsten Stern dauert hingegen nur unwesentlich länger). Der Raum wird dabei in immer kleinere Teile zerteilt und das kommt alles ohne Entitydistance aus (in 1 ms). Vielleicht kommst Du damit ja weiter. Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics3D 800,600,32,2 ; Zeitmessung starten ms=MilliSecs() movespeed#=0.1 ; Geschwindigkeit Kamera sterne%=1000 ; Anzahl Sterne range#=50.0 ; Sektorgrösse (-range,range) in alle Dimensionen viewrange#=1000.0 ; Sichtbarkeit Sterne textrange#=10.0 ; Reichweite der Textanzeige sun=0 ; Flag für erste Sonne d#=0.0 ; Hilfsvariable Punktverbindung Type point Field entity% Field x#,y#,z# Field connections% End Type ; Kamera cam=CreateCamera() CameraRange cam,0.1,1000 PositionEntity cam,0,0,-2 ; Pivots wiref_piv = CreatePivot() solid_piv = CreatePivot() dummy = CreatePivot() ; Sternvorlage star=CreateSphere(8) ScaleEntity star,0.1,0.1,0.1 EntityFX star,1 EntityColor star,255,128,0 ; Mesh Verbindungslinien lines=CreateMesh(wiref_piv) surf=CreateSurface(lines) EntityFX lines,1+2+16+32 ; Sterne generieren For stars=1 To sterne newrange#=range;range(stars1.0/sterne) point.point = New point point\x=Rnd(-newrange,newrange) point\y=Rnd(-newrange,newrange) point\z=Rnd(-newrange,newrange) ; erste Sonne in die Mitte bei 0,0,0 If sun=0 Then point\x=0 : point\y=0 : point\z=0 : sun=1 point\entity=CopyEntity(star) PositionEntity point\entity,point\x,point\y,point\z EntityAutoFade point\entity,viewrange/2.0,viewrange NameEntity point\entity,stars Next ; Nachbarpunkt für jeden Punkt herausfinden For loop.point = Each point d0# = 100000000.0 np.point = Null ; alle Punkte durchgehen For point.point = Each point ; aber nicht mit sich selbst messen If point\entity<>loop\entity Then ; X d=(point\x-loop\x)(point\x-loop\x) If d<d0 Then ; Y d=d+((point\y-loop\y)(point\y-loop\y)) If d<d0 Then ; Z d=d+((point\z-loop\z)(point\z-loop\z)) If d<d0 Then d0=d : np=point : lastentity = point\entity End If End If EndIf Next ; Linie ziehen lines=Line3D(lines,loop\x,loop\y,loop\z,np\x,np\y,np\z,64,128,255,0.5) linien=linien+1 loop\connections=loop\connections+1 Next ; Maus in die Mitte MoveMouse GraphicsWidth()/2,GraphicsHeight()/2 Color 0,255,0 ; Zeitmessung beenden zeit=MilliSecs()-ms ; Hauptloop While Not KeyHit(1) ; FPS messung FPS_C=FPS_C+1 If ms<MilliSecs() ms=MilliSecs()+1000 FPS=FPS_C FPS_C=0 EndIf ; Frame tweening Tween#=Float(MilliSecs()-FrameTime)/Float(20.0) : FrameTime=MilliSecs() ; Maussteuerung mxs#=MouseXSpeed() : mys#=MouseYSpeed() : pitch#=EntityPitch(cam)+(mys#/5) If pitch>89 Then pitch=89 Else If pitch<-89 Then pitch=-89 RotateEntity cam,pitch,EntityYaw(cam)-(mxs#/5),0 MoveMouse GraphicsWidth()/2,GraphicsHeight()/2 ; Tastatursteuerung If KeyDown(200) Then MoveEntity cam,0,0,movespeedtween If KeyDown(208) Then MoveEntity cam,0,0,-movespeedtween If KeyDown(205) Then MoveEntity cam,movespeedtween,0,0 If KeyDown(203) Then MoveEntity cam,-movespeedtween,0,0 If KeyHit(57) Then wf=1-wf ; Render wireframe objects. WireFrame 1 : ShowEntity wiref_piv : HideEntity solid_piv CameraClsMode cam,1,1 : RenderWorld ; Render solid objects. WireFrame wf : HideEntity wiref_piv : ShowEntity solid_piv CameraClsMode cam,0,0 : RenderWorld ; Textausgabe Text 0, 0,"FPS..............: "+FPS Text 0,15,"Sterne gesamt....: "+sterne Text 0,30,"Nächster Stern...: "+close+" ["+name+"]" Text 0,45,"Zeit für Aufbau..: "+zeit+"ms" Text 0,60,"Zeit pro Schleife: "+loops+"ms" Text 0,75,"Linien gezeichnet: "+linien ; nächsten Stern suchen und Name einblenden msloops=MilliSecs() close=CalcNearest(EntityX(cam),EntityY(cam),EntityZ(cam)) If close Then name=EntityName(close) CameraProject cam,EntityX(close),EntityY(close),EntityZ(close) px%=ProjectedX() py%=ProjectedY() Text px,py,name EndIf loops=MilliSecs()-msloops Flip 0 Wend End ; 3D-Linie zwischen zwei Punkten zeichnen Function Line3D(mesh,x0#,y0#,z0#,x1#,y1#,z1#,r%=255,g%=255,b%=255,a#=1.0) If mesh=0 Then mesh=CreateMesh() surf=CreateSurface(mesh) EntityFX mesh,1+2+16 Else last_surf=CountSurfaces(mesh) surf=GetSurface(mesh,last_surf) If CountVertices(surf)>30000 Then surf=CreateSurface(mesh) End If v0=AddVertex(surf,x1,y1,z1) v1=AddVertex(surf,x0,y0,z0) AddTriangle surf,v0,v0,v1 VertexColor surf,v0,r,g,b,a VertexColor surf,v1,r,g,b,a Return mesh End Function Function CalcNearest(x#,y#,z#) Local d# Local d0# = 100000000.0 np.point = Null ; alle Punkte durchgehen For point.point = Each point ; X d=(point\x-x)(point\x-x) If d<d0 Then ; Y d=d+((point\y-y)(point\y-y)) If d<d0 Then ; Z d=d+((point\z-z)(point\z-z)) If d<d0 Then d0=d : np=point End If End If Next Return np\entity End Function

Krischan

Do, Apr 02, 2009 15:30
Antworten mit Zitat

Versuch es mal hiermit, sorry ist nicht gut kommentiert (habs noch etwas auf das Wesentliche reduziert), war auch nur ein Test für einen minimalen Spannbaum. Es werden 1000 Sterne zufällig im Raum plaziert und mittels der Funktion Calcnearest der nächstliegende Stern ermittelt (kannst auch 10.000, 100.000 nehmen nur dann fliegt Dir die 3D-Anzeige mit den Linien um die Ohren, die Suche nach dem nächsten Stern dauert hingegen nur unwesentlich länger). Der Raum wird dabei in immer kleinere Teile zerteilt und das kommt alles ohne Entitydistance aus (in 1 ms). Vielleicht kommst Du damit ja weiter.

Code: [AUSKLAPPEN]

Graphics3D 800,600,32,2

; Zeitmessung starten
ms=MilliSecs()

movespeed#=0.1 ; Geschwindigkeit Kamera
sterne%=1000 ; Anzahl Sterne
range#=50.0 ; Sektorgrösse (-range,range) in alle Dimensionen
viewrange#=1000.0 ; Sichtbarkeit Sterne
textrange#=10.0 ; Reichweite der Textanzeige
sun=0 ; Flag für erste Sonne
d#=0.0 ; Hilfsvariable Punktverbindung

Type point
Field entity%
Field x#,y#,z#
Field connections%
End Type

; Kamera
cam=CreateCamera()
CameraRange cam,0.1,1000
PositionEntity cam,0,0,-2

; Pivots
wiref_piv = CreatePivot()
solid_piv = CreatePivot()
dummy = CreatePivot()

; Sternvorlage
star=CreateSphere(8)
ScaleEntity star,0.1,0.1,0.1
EntityFX star,1
EntityColor star,255,128,0

; Mesh Verbindungslinien
lines=CreateMesh(wiref_piv)
surf=CreateSurface(lines)
EntityFX lines,1+2+16+32

; Sterne generieren
For stars=1 To sterne

newrange#=range;range*(stars*1.0/sterne)

point.point = New point

point\x=Rnd(-newrange,newrange)
point\y=Rnd(-newrange,newrange)
point\z=Rnd(-newrange,newrange)

; erste Sonne in die Mitte bei 0,0,0
If sun=0 Then point\x=0 : point\y=0 : point\z=0 : sun=1

point\entity=CopyEntity(star)
PositionEntity point\entity,point\x,point\y,point\z

EntityAutoFade point\entity,viewrange/2.0,viewrange

NameEntity point\entity,stars

Next

; Nachbarpunkt für jeden Punkt herausfinden
For loop.point = Each point

d0# = 100000000.0
np.point = Null

; alle Punkte durchgehen
For point.point = Each point

   ; aber nicht mit sich selbst messen
If point\entity<>loop\entity Then

; X
d=(point\x-loop\x)*(point\x-loop\x)

If d<d0 Then

; Y
d=d+((point\y-loop\y)*(point\y-loop\y))

If d<d0 Then

; Z
d=d+((point\z-loop\z)*(point\z-loop\z))
If d<d0 Then d0=d : np=point : lastentity = point\entity

End If

End If

EndIf

Next

; Linie ziehen
lines=Line3D(lines,loop\x,loop\y,loop\z,np\x,np\y,np\z,64,128,255,0.5)

linien=linien+1

loop\connections=loop\connections+1

Next

; Maus in die Mitte
MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

Color 0,255,0

; Zeitmessung beenden
zeit=MilliSecs()-ms

; Hauptloop
While Not KeyHit(1)

; FPS messung
FPS_C=FPS_C+1
If ms<MilliSecs()
ms=MilliSecs()+1000
FPS=FPS_C
FPS_C=0
EndIf

; Frame tweening
Tween#=Float(MilliSecs()-FrameTime)/Float(20.0) : FrameTime=MilliSecs()

; Maussteuerung
mxs#=MouseXSpeed() : mys#=MouseYSpeed() : pitch#=EntityPitch(cam)+(mys#/5)
If pitch>89 Then pitch=89 Else If pitch<-89 Then pitch=-89
RotateEntity cam,pitch,EntityYaw(cam)-(mxs#/5),0
MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

; Tastatursteuerung
If KeyDown(200) Then MoveEntity cam,0,0,movespeed*tween
If KeyDown(208) Then MoveEntity cam,0,0,-movespeed*tween
If KeyDown(205) Then MoveEntity cam,movespeed*tween,0,0
If KeyDown(203) Then MoveEntity cam,-movespeed*tween,0,0
If KeyHit(57) Then wf=1-wf

; Render wireframe objects.
WireFrame 1 : ShowEntity wiref_piv : HideEntity solid_piv
CameraClsMode cam,1,1 : RenderWorld

; Render solid objects.
WireFrame wf : HideEntity wiref_piv : ShowEntity solid_piv
CameraClsMode cam,0,0 : RenderWorld

; Textausgabe
Text 0, 0,"FPS..............: "+FPS
Text 0,15,"Sterne gesamt....: "+sterne
Text 0,30,"Nächster Stern...: "+close+" ["+name+"]"
Text 0,45,"Zeit für Aufbau..: "+zeit+"ms"
Text 0,60,"Zeit pro Schleife: "+loops+"ms"
Text 0,75,"Linien gezeichnet: "+linien

; nächsten Stern suchen und Name einblenden
msloops=MilliSecs()
close=CalcNearest(EntityX(cam),EntityY(cam),EntityZ(cam))
If close Then
   name=EntityName(close)
   CameraProject cam,EntityX(close),EntityY(close),EntityZ(close)
   px%=ProjectedX()
   py%=ProjectedY()
   Text px,py,name
EndIf

loops=MilliSecs()-msloops

Flip 0

Wend

End

; 3D-Linie zwischen zwei Punkten zeichnen
Function Line3D(mesh,x0#,y0#,z0#,x1#,y1#,z1#,r%=255,g%=255,b%=255,a#=1.0)

If mesh=0 Then
   mesh=CreateMesh()
   surf=CreateSurface(mesh)
   EntityFX mesh,1+2+16
Else
   last_surf=CountSurfaces(mesh)
   surf=GetSurface(mesh,last_surf)
   If CountVertices(surf)>30000 Then surf=CreateSurface(mesh)
End If

v0=AddVertex(surf,x1,y1,z1)
v1=AddVertex(surf,x0,y0,z0)
AddTriangle surf,v0,v0,v1

VertexColor surf,v0,r,g,b,a
VertexColor surf,v1,r,g,b,a

Return mesh

End Function

Function CalcNearest(x#,y#,z#)

Local d#
Local d0# = 100000000.0
np.point = Null

; alle Punkte durchgehen
For point.point = Each point

; X
d=(point\x-x)*(point\x-x)

If d<d0 Then

; Y
d=d+((point\y-y)*(point\y-y))

If d<d0 Then

; Z
d=d+((point\z-z)*(point\z-z))
If d<d0 Then d0=d : np=point

End If

End If

Next

Return np\entity

End Function

	Krischan	Do, Apr 02, 2009 16:48 Antworten mit Zitat
Hier nochmal etwas reduziert, mit Vergleichsmöglichkeit: 1. Beispiel: 3D, 100.000 Cubes, mit SPACE kann die Methode gewechselt werden: Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics3D 800,600,32,2 ; Zeitmessung starten ms=MilliSecs() movespeed#=0.1 ; Geschwindigkeit Kamera sterne%=100000 ; Anzahl Sterne range#=50.0 ; Sektorgrösse (-range,range) in alle Dimensionen sun=0 ; Flag für erste Sonne d#=0.0 ; Hilfsvariable Punktverbindung Type point Field entity% Field x#,y#,z# End Type ; Kamera cam=CreateCamera() CameraRange cam,0.1,range/5 PositionEntity cam,0,0,-2 ; Pivot dummy=CreatePivot() ; Sternvorlage star=CreateCube() ScaleEntity star,0.01,0.01,0.01 EntityFX star,1 EntityColor star,255,128,0 ; Sterne generieren For stars=1 To sterne newrange#=range point.point = New point point\x=Rnd(-newrange,newrange) point\y=Rnd(-newrange,newrange) point\z=Rnd(-newrange,newrange) ; erste Sonne in die Mitte bei 0,0,0 If sun=0 Then point\x=0 : point\y=0 : point\z=0 : sun=1 point\entity=CopyEntity(star) PositionEntity point\entity,point\x,point\y,point\z EntityAutoFade point\entity,range/10,range/5 NameEntity point\entity,stars Next ; Maus in die Mitte MoveMouse GraphicsWidth()/2,GraphicsHeight()/2 Color 0,255,0 ; Zeitmessung beenden zeit=MilliSecs()-ms ; Hauptloop While Not KeyHit(1) ; FPS messung FPS_C=FPS_C+1 If ms<MilliSecs() ms=MilliSecs()+1000 FPS=FPS_C FPS_C=0 EndIf ; Frame tweening Tween#=Float(MilliSecs()-FrameTime)/Float(20.0) : FrameTime=MilliSecs() ; Maussteuerung mxs#=MouseXSpeed() : mys#=MouseYSpeed() : pitch#=EntityPitch(cam)+(mys#/5) If pitch>89 Then pitch=89 Else If pitch<-89 Then pitch=-89 RotateEntity cam,pitch,EntityYaw(cam)-(mxs#/5),0 MoveMouse GraphicsWidth()/2,GraphicsHeight()/2 ; Tastatursteuerung If KeyDown(200) Then MoveEntity cam,0,0,movespeedtween If KeyDown(208) Then MoveEntity cam,0,0,-movespeedtween If KeyDown(205) Then MoveEntity cam,movespeedtween,0,0 If KeyDown(203) Then MoveEntity cam,-movespeedtween,0,0 If KeyHit(57) Then method=1-method If method=0 Then methodstring$="Krischan's Algorithm" Else methodstring="Distance Sort" ; Render solid objects. RenderWorld ; Textausgabe Text 0, 0,"Zeit für Aufbau..: "+zeit+"ms" Text 0,15,"FPS..............: "+FPS Text 0,30,"Sterne gesamt....: "+sterne Text 0,45,"Nächster Stern...: "+close+" ["+name+"]" Text 0,60,"Methode verwendet: "+methodstring Text 0,75,"Zeit Pro Schleife: "+loops+"ms" ; nächsten Stern suchen und Name einblenden msloops=MilliSecs() If method=0 Then close=CalcNearest(EntityX(cam),EntityY(cam),EntityZ(cam)) Else close=FindNearest(EntityX(cam),EntityY(cam),EntityZ(cam)) EndIf If close Then PositionEntity dummy,EntityX(close),EntityY(close),EntityZ(close) If EntityInView(dummy,cam) Then name=EntityName(close) CameraProject cam,EntityX(close),EntityY(close),EntityZ(close) px%=ProjectedX() py%=ProjectedY() If px>=0 And px<799 And py>=0 And py<=599 Then Text px,py,name EndIf EndIf loops=MilliSecs()-msloops Flip 0 Wend End Function FindNearest(x#,y#,z#) min#=100000000.0 For point.point = Each point d#=Distance(x,y,z,point\x,point\y,point\z) If d<min Then min=d : current%=point\entity Next Return current End Function Function Distance#(x1#,y1#,z1#,x2#,y2#,z2#) Return Sqr((x1-x2)(x1-x2)+(y1-y2)(y1-y2)+(z1-z2)(z1-z2)) End Function Function CalcNearest(x#,y#,z#) Local d# Local d0# = 100000000.0 np.point = Null ; alle Punkte durchgehen For point.point = Each point ; X d=(point\x-x)(point\x-x) If d<d0 Then ; Y d=d+((point\y-y)(point\y-y)) If d<d0 Then ; Z d=d+((point\z-z)(point\z-z)) If d<d0 Then d0=d : np=point End If End If Next Return np\entity End Function 2. Beispiel: OHNE 3D, reiner Performancetest mit diesmal 10.000.000 Punkten: Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics 800,600,32,2 ; Zeitmessung starten ms=MilliSecs() movespeed#=0.1 ; Geschwindigkeit Kamera sterne%=10000000 ; Anzahl Sterne range#=50.0 ; Sektorgrösse (-range,range) in alle Dimensionen sun=0 ; Flag für erste Sonne d#=0.0 ; Hilfsvariable Punktverbindung Type point Field x#,y#,z# Field entity End Type ; Sterne generieren For stars=1 To sterne newrange#=range point.point = New point point\x=Rnd(-newrange,newrange) point\y=Rnd(-newrange,newrange) point\z=Rnd(-newrange,newrange) ; erste Sonne in die Mitte bei 0,0,0 If sun=0 Then point\x=0 : point\y=0 : point\z=0 : sun=1 point\entity=stars Next Color 0,255,0 ; Zeitmessung beenden zeit=MilliSecs()-ms ; Hauptloop While Not KeyHit(1) Cls ; FPS messung FPS_C=FPS_C+1 If ms<MilliSecs() ms=MilliSecs()+1000 FPS=FPS_C FPS_C=0 EndIf If KeyHit(57) Then method=1-method If method=0 Then methodstring$="Krischan's Algorithm" Else methodstring="Distance Sort" ; Textausgabe Text 0, 0,"Zeit für Aufbau..: "+zeit+"ms" Text 0,15,"FPS..............: "+FPS Text 0,30,"Sterne gesamt....: "+sterne Text 0,45,"Nächster Stern...: "+close Text 0,60,"Methode verwendet: "+methodstring Text 0,75,"Zeit Pro Schleife: "+loops+"ms" ; nächsten Stern suchen und Name einblenden msloops=MilliSecs() If method=0 Then close=CalcNearest(0,0,0) Else close=FindNearest(0,0,0) EndIf loops=MilliSecs()-msloops Flip 0 Wend End Function FindNearest(x#,y#,z#) min#=100000000.0 For point.point = Each point d#=Distance(x,y,z,point\x,point\y,point\z) If d<min Then min=d : current%=point\entity Next Return current End Function Function Distance#(x1#,y1#,z1#,x2#,y2#,z2#) Return Sqr((x1-x2)(x1-x2)+(y1-y2)(y1-y2)+(z1-z2)(z1-z2)) End Function Function CalcNearest(x#,y#,z#) Local d# Local d0# = 100000000.0 np.point = Null ; alle Punkte durchgehen For point.point = Each point ; X d=(point\x-x)(point\x-x) If d<d0 Then ; Y d=d+((point\y-y)(point\y-y)) If d<d0 Then ; Z d=d+((point\z-z)(point\z-z)) If d<d0 Then d0=d : np=point End If End If Next Return np\entity End Function Meine Methode ist etwa doppelt so schnell wie die billigste Entitydistance-Sortiermethode (wobei ich hier noch nicht mal Entitydistance verwende, sondern eine schnellere DIstanzberechnung, das wäre etwa 4x langsamer).

Krischan

Do, Apr 02, 2009 16:48
Antworten mit Zitat

Hier nochmal etwas reduziert, mit Vergleichsmöglichkeit:

1. Beispiel: 3D, 100.000 Cubes, mit SPACE kann die Methode gewechselt werden:
Code: [AUSKLAPPEN]

Graphics3D 800,600,32,2

; Zeitmessung starten
ms=MilliSecs()

movespeed#=0.1 ; Geschwindigkeit Kamera
sterne%=100000 ; Anzahl Sterne
range#=50.0 ; Sektorgrösse (-range,range) in alle Dimensionen
sun=0 ; Flag für erste Sonne
d#=0.0 ; Hilfsvariable Punktverbindung

Type point
Field entity%
Field x#,y#,z#
End Type

; Kamera
cam=CreateCamera()
CameraRange cam,0.1,range/5
PositionEntity cam,0,0,-2

; Pivot
dummy=CreatePivot()

; Sternvorlage
star=CreateCube()
ScaleEntity star,0.01,0.01,0.01
EntityFX star,1
EntityColor star,255,128,0

; Sterne generieren
For stars=1 To sterne

newrange#=range

point.point = New point

point\x=Rnd(-newrange,newrange)
point\y=Rnd(-newrange,newrange)
point\z=Rnd(-newrange,newrange)

; erste Sonne in die Mitte bei 0,0,0
If sun=0 Then point\x=0 : point\y=0 : point\z=0 : sun=1

point\entity=CopyEntity(star)
PositionEntity point\entity,point\x,point\y,point\z

EntityAutoFade point\entity,range/10,range/5

NameEntity point\entity,stars

Next

; Maus in die Mitte
MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

Color 0,255,0

; Zeitmessung beenden
zeit=MilliSecs()-ms

; Hauptloop
While Not KeyHit(1)

; FPS messung
FPS_C=FPS_C+1
If ms<MilliSecs()
ms=MilliSecs()+1000
FPS=FPS_C
FPS_C=0
EndIf

; Frame tweening
Tween#=Float(MilliSecs()-FrameTime)/Float(20.0) : FrameTime=MilliSecs()

; Maussteuerung
mxs#=MouseXSpeed() : mys#=MouseYSpeed() : pitch#=EntityPitch(cam)+(mys#/5)
If pitch>89 Then pitch=89 Else If pitch<-89 Then pitch=-89
RotateEntity cam,pitch,EntityYaw(cam)-(mxs#/5),0
MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

; Tastatursteuerung
If KeyDown(200) Then MoveEntity cam,0,0,movespeed*tween
If KeyDown(208) Then MoveEntity cam,0,0,-movespeed*tween
If KeyDown(205) Then MoveEntity cam,movespeed*tween,0,0
If KeyDown(203) Then MoveEntity cam,-movespeed*tween,0,0
If KeyHit(57) Then method=1-method

If method=0 Then methodstring$="Krischan's Algorithm" Else methodstring="Distance Sort"

; Render solid objects.
RenderWorld

; Textausgabe
Text 0, 0,"Zeit für Aufbau..: "+zeit+"ms"
Text 0,15,"FPS..............: "+FPS
Text 0,30,"Sterne gesamt....: "+sterne
Text 0,45,"Nächster Stern...: "+close+" ["+name+"]"
Text 0,60,"Methode verwendet: "+methodstring
Text 0,75,"Zeit Pro Schleife: "+loops+"ms"

; nächsten Stern suchen und Name einblenden
msloops=MilliSecs()

If method=0 Then

   close=CalcNearest(EntityX(cam),EntityY(cam),EntityZ(cam))

Else

   close=FindNearest(EntityX(cam),EntityY(cam),EntityZ(cam))

EndIf

If close Then

   PositionEntity dummy,EntityX(close),EntityY(close),EntityZ(close)

   If EntityInView(dummy,cam) Then

      name=EntityName(close)
      CameraProject cam,EntityX(close),EntityY(close),EntityZ(close)

      px%=ProjectedX()
      py%=ProjectedY()

      If px>=0 And px<799 And py>=0 And py<=599 Then Text px,py,name

   EndIf

EndIf

loops=MilliSecs()-msloops

Flip 0

Wend

End

Function FindNearest(x#,y#,z#)

min#=100000000.0

For point.point = Each point

   d#=Distance(x,y,z,point\x,point\y,point\z)
   If d<min Then min=d : current%=point\entity

Next

Return current

End Function

Function Distance#(x1#,y1#,z1#,x2#,y2#,z2#)

Return Sqr((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))

End Function

Function CalcNearest(x#,y#,z#)

Local d#
Local d0# = 100000000.0
np.point = Null

; alle Punkte durchgehen
For point.point = Each point

; X
d=(point\x-x)*(point\x-x)

If d<d0 Then

; Y
d=d+((point\y-y)*(point\y-y))

If d<d0 Then

; Z
d=d+((point\z-z)*(point\z-z))
If d<d0 Then d0=d : np=point

End If

End If

Next

Return np\entity

End Function

2. Beispiel: OHNE 3D, reiner Performancetest mit diesmal 10.000.000 Punkten:
Code: [AUSKLAPPEN]

Graphics 800,600,32,2

; Zeitmessung starten
ms=MilliSecs()

movespeed#=0.1 ; Geschwindigkeit Kamera
sterne%=10000000 ; Anzahl Sterne
range#=50.0 ; Sektorgrösse (-range,range) in alle Dimensionen
sun=0 ; Flag für erste Sonne
d#=0.0 ; Hilfsvariable Punktverbindung

Type point
Field x#,y#,z#
Field entity
End Type

; Sterne generieren
For stars=1 To sterne

newrange#=range

point.point = New point

point\x=Rnd(-newrange,newrange)
point\y=Rnd(-newrange,newrange)
point\z=Rnd(-newrange,newrange)

; erste Sonne in die Mitte bei 0,0,0
If sun=0 Then point\x=0 : point\y=0 : point\z=0 : sun=1

point\entity=stars

Next

Color 0,255,0

; Zeitmessung beenden
zeit=MilliSecs()-ms

; Hauptloop
While Not KeyHit(1)

Cls

; FPS messung
FPS_C=FPS_C+1
If ms<MilliSecs()
ms=MilliSecs()+1000
FPS=FPS_C
FPS_C=0
EndIf

If KeyHit(57) Then method=1-method

If method=0 Then methodstring$="Krischan's Algorithm" Else methodstring="Distance Sort"

; Textausgabe
Text 0, 0,"Zeit für Aufbau..: "+zeit+"ms"
Text 0,15,"FPS..............: "+FPS
Text 0,30,"Sterne gesamt....: "+sterne
Text 0,45,"Nächster Stern...: "+close
Text 0,60,"Methode verwendet: "+methodstring
Text 0,75,"Zeit Pro Schleife: "+loops+"ms"

; nächsten Stern suchen und Name einblenden
msloops=MilliSecs()

If method=0 Then

   close=CalcNearest(0,0,0)

Else

   close=FindNearest(0,0,0)

EndIf

loops=MilliSecs()-msloops

Flip 0

Wend

End

Function FindNearest(x#,y#,z#)

min#=100000000.0

For point.point = Each point

   d#=Distance(x,y,z,point\x,point\y,point\z)
   If d<min Then min=d : current%=point\entity

Next

Return current

End Function

Function Distance#(x1#,y1#,z1#,x2#,y2#,z2#)

Return Sqr((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))

End Function

Function CalcNearest(x#,y#,z#)

Local d#
Local d0# = 100000000.0
np.point = Null

; alle Punkte durchgehen
For point.point = Each point

; X
d=(point\x-x)*(point\x-x)

If d<d0 Then

; Y
d=d+((point\y-y)*(point\y-y))

If d<d0 Then

; Z
d=d+((point\z-z)*(point\z-z))
If d<d0 Then d0=d : np=point

End If

End If

Next

Return np\entity

End Function

Meine Methode ist etwa doppelt so schnell wie die billigste Entitydistance-Sortiermethode (wobei ich hier noch nicht mal Entitydistance verwende, sondern eine schnellere DIstanzberechnung, das wäre etwa 4x langsamer).

	Mr.Keks	Fr, Apr 03, 2009 9:40 Antworten mit Zitat
Duhu, Krischan, deine Abstandberechnung is zwar kleverer als EntityDistance, aber du bist damit nur um einen konstanten Faktor schneller, liegst also noch in derselben Aufwandsklasse. Du musst immer noch 1000 * 1000 = 1000000 Abstandsprüfungen durchführen. Bei mir brauchen deine 1000 Sterne über 100 Millisekunden, um ihre Nachbarn zu finden. Mit dem von mir beschriebenen System sollte das in Echtzeit updatebar sein, also nicht mehr als 5 ms brauchen, denke ich. Es hat auf jeden Fall weniger Prüfungen als du, außer im halbwegs unwahrscheinlichen WorstCase, dass alle verglichenen Punkte an derselben Stelle liegen.
MrKeks.net

Mr.Keks

Fr, Apr 03, 2009 9:40
Antworten mit Zitat

Duhu, Krischan, deine Abstandberechnung is zwar kleverer als EntityDistance, aber du bist damit nur um einen konstanten Faktor schneller, liegst also noch in derselben Aufwandsklasse. Du musst immer noch 1000 * 1000 = 1000000 Abstandsprüfungen durchführen. Bei mir brauchen deine 1000 Sterne über 100 Millisekunden, um ihre Nachbarn zu finden.

Mit dem von mir beschriebenen System sollte das in Echtzeit updatebar sein, also nicht mehr als 5 ms brauchen, denke ich. Es hat auf jeden Fall weniger Prüfungen als du, außer im halbwegs unwahrscheinlichen WorstCase, dass alle verglichenen Punkte an derselben Stelle liegen.

MrKeks.net

	Silver_Knee	Fr, Apr 03, 2009 10:29 Antworten mit Zitat
hmm was ist mit EntityPick oder LinePick? wenn man das vernünftig einsetzt klappts auch

Silver_Knee

Fr, Apr 03, 2009 10:29
Antworten mit Zitat

hmm was ist mit EntityPick oder LinePick? wenn man das vernünftig einsetzt klappts auch

	AnniXa	Fr, Apr 03, 2009 11:20 Antworten mit Zitat
also ich habe grob angefangen diese cubes zu machen (da das ganze nur auf einer fläche abläuft) , sind eigentlich nur X und Z relevant, ich speichere nun das Handle des type feldes von Entity typ B in diese cubes types bzw dem feld das ein blitz array ist, und erhöhe immer den zähler, wenn nun ein entity den cube verläst, veringere ich den zähler und muss auch das handle wieder aus dem blitz array rausholen, um den platz freizugeben wie mach ichn das effiziennt? oder muss ich dann den ganzen blitzarray durchschleifen, vergleichen und wegmachen? wie weis ich dann wenn wieder ein neues in den cube eintritt wo nen platz im array frei ist? bin zu doof :/

AnniXa

Fr, Apr 03, 2009 11:20
Antworten mit Zitat

also ich habe grob angefangen diese cubes zu machen (da das ganze nur auf einer fläche abläuft) , sind eigentlich nur X und Z relevant,

ich speichere nun das Handle des type feldes von Entity typ B in diese cubes types bzw dem feld das ein blitz array ist,
und erhöhe immer den zähler,
wenn nun ein entity den cube verläst,
veringere ich den zähler und muss auch das handle wieder aus dem blitz array rausholen, um den platz freizugeben
wie mach ichn das effiziennt?
oder muss ich dann den ganzen blitzarray durchschleifen, vergleichen und wegmachen?
wie weis ich dann wenn wieder ein neues in den cube eintritt wo nen platz im array frei ist?

bin zu doof :/

	Noobody	Fr, Apr 03, 2009 11:24 Antworten mit Zitat
Wenn du ein Entity entfernst, schiebst du einfach das letzte Element des Arrays an den freien Platz - da die Reihenfolge ja unwichtig ist, erhältst du damit eine durchgängige Liste und kannst neue Entities ganz einfach an das Ende der Liste anhängen. So im Sinne von Code: [AUSKLAPPEN] [EINKLAPPEN] Function RemoveEntity( Cube.TCube, Entity.TEntity ) For i = 0 to Cube\EntityCount - 1 If Cube\Entities[ i ] = Entity then Cube\Entities[ i ] = Cube\Entities[ Cube\EntityCount - 1 ] Cube\Entities[ Cube\EntityCount - 1 ] = Null Cube\EntityCount = Cube\EntityCount - 1 Return EndIf Next End Function
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

Fr, Apr 03, 2009 11:24
Antworten mit Zitat

Wenn du ein Entity entfernst, schiebst du einfach das letzte Element des Arrays an den freien Platz - da die Reihenfolge ja unwichtig ist, erhältst du damit eine durchgängige Liste und kannst neue Entities ganz einfach an das Ende der Liste anhängen.

So im Sinne von Code: [AUSKLAPPEN]

Function RemoveEntity( Cube.TCube, Entity.TEntity )
For i = 0 to Cube\EntityCount - 1
   If Cube\Entities[ i ] = Entity then
      Cube\Entities[ i ] = Cube\Entities[ Cube\EntityCount - 1 ]
      Cube\Entities[ Cube\EntityCount - 1 ] = Null
      Cube\EntityCount = Cube\EntityCount - 1

      Return
   EndIf
Next
End Function

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	Krischan	Fr, Apr 03, 2009 12:42 Antworten mit Zitat
Mr.Keks hat Folgendes geschrieben: Duhu, Krischan, deine Abstandberechnung is zwar kleverer als EntityDistance, aber du bist damit nur um einen konstanten Faktor schneller, liegst also noch in derselben Aufwandsklasse. Du musst immer noch 1000 * 1000 = 1000000 Abstandsprüfungen durchführen. Bei mir brauchen deine 1000 Sterne über 100 Millisekunden, um ihre Nachbarn zu finden. Mit dem von mir beschriebenen System sollte das in Echtzeit updatebar sein, also nicht mehr als 5 ms brauchen, denke ich. Es hat auf jeden Fall weniger Prüfungen als du, außer im halbwegs unwahrscheinlichen WorstCase, dass alle verglichenen Punkte an derselben Stelle liegen. Klar, aber ging es nicht darum, dass man von nur einem Punkt aus den nächsten Punkt aus einer Punktwolke herausfinden muss? Dafür reicht das eigentlich aus und ist auch nicht besonders aufwändig geschrieben. Evt. könnte man sogar einen Octree dafür heranziehen, das müsste dann noch viel schneller sein (aber mit so rekursiven Sachen kenne ich mich nicht so aus), oder Quadtree, wenn 2D ausreicht.

Krischan

Fr, Apr 03, 2009 12:42
Antworten mit Zitat

Mr.Keks hat Folgendes geschrieben:

Klar, aber ging es nicht darum, dass man von nur einem Punkt aus den nächsten Punkt aus einer Punktwolke herausfinden muss? Dafür reicht das eigentlich aus und ist auch nicht besonders aufwändig geschrieben. Evt. könnte man sogar einen Octree dafür heranziehen, das müsste dann noch viel schneller sein (aber mit so rekursiven Sachen kenne ich mich nicht so aus), oder Quadtree, wenn 2D ausreicht.

	Mr.Keks	Fr, Apr 03, 2009 14:08 Antworten mit Zitat
AnniXa hat Folgendes geschrieben: Alle entitys von typ A suchen nun immer nach dem nahesten von Typ B Dafür läuft eine for-each schleife alle A´s durch und für jeden durchlauf werden wiederum alle B´s durchgelaufen und das für welches der geringsten "EntityDistance" wert ermittelt wurde wird übergeben. Wie du siehst, ging es um alle Punkte. Zum Octtree/Quadtree: Das ist es eben, dass man den Raum irgendwie in Volumeneinheiten aufteilen muss, um ihn besser zu beherrschen. Genau das habe ich beschrieben. Allerdings mit gleichgroßen Kuben, da diese einem einiges Kopfzerbrechen ersparen und es auch einfacher zu erklären war . Octtrees machen das ganze nicht viel schneller, aber drastisch unübersichtlicher. Sollte es jedoch so sein, dass AnniXa alle B-Entities an nen paar Stellen im Raum verdammt dicht packt, während der größte Teil des Raums gähnend leer ist, müsste mensch sich tatsächlich möglicherweise den Kopf über nen Quad/Octtree zerbrechen.
MrKeks.net

Mr.Keks

Fr, Apr 03, 2009 14:08
Antworten mit Zitat

AnniXa hat Folgendes geschrieben:

Alle entitys von typ A suchen nun immer nach dem nahesten von Typ B
Dafür läuft eine for-each schleife alle A´s durch und für jeden durchlauf werden wiederum alle B´s durchgelaufen und das für welches der geringsten "EntityDistance" wert ermittelt wurde wird übergeben.

Wie du siehst, ging es um alle Punkte.
Zum Octtree/Quadtree: Das ist es eben, dass man den Raum irgendwie in Volumeneinheiten aufteilen muss, um ihn besser zu beherrschen. Genau das habe ich beschrieben. Allerdings mit gleichgroßen Kuben, da diese einem einiges Kopfzerbrechen ersparen und es auch einfacher zu erklären war Wink

. Octtrees machen das ganze nicht viel schneller, aber drastisch unübersichtlicher. Sollte es jedoch so sein, dass AnniXa alle B-Entities an nen paar Stellen im Raum verdammt dicht packt, während der größte Teil des Raums gähnend leer ist, müsste mensch sich tatsächlich möglicherweise den Kopf über nen Quad/Octtree zerbrechen.

MrKeks.net

	AnniXa	Di, Apr 07, 2009 22:56 Antworten mit Zitat
Nochmals danke an alle hier, leider habe ich es bisher nicht geschaft meine suchfunktion zu verbessern. irgendwelche fehler die ich mir meistens nicht erklären kann stören dann immer, inzwischen ist mein programm schon sehr komplex und wenn ein entity verändert wird bzw muss da viel passieren. für den der interesse hat kann man hier sehen wofür ich das gebraucht habe. Ich werde diese nacht wohl damit verbringen zu versuchen den mr.keks vorschlag nochmal anzugehen, und das krischan programm probiere ich auch aus.

AnniXa

Di, Apr 07, 2009 22:56
Antworten mit Zitat

Nochmals danke an alle hier,
leider habe ich es bisher nicht geschaft meine suchfunktion zu verbessern.
irgendwelche fehler die ich mir meistens nicht erklären kann stören dann immer, inzwischen ist mein programm schon sehr komplex und wenn ein entity verändert wird bzw muss da viel passieren.
für den der interesse hat kann man hier sehen wofür ich das gebraucht habe.
Ich werde diese nacht wohl damit verbringen zu versuchen den mr.keks vorschlag nochmal anzugehen, und das krischan programm probiere ich auch aus.

Übersicht

BlitzBasic

Blitz3D

Nach Oben

BlitzBasic Portal

Nahestes Entity Finden...

Betreff: Nahestes Entity Finden...

Betreff: okay