Finding all entities within a radius

Blitz3D Forums/Blitz3D Programming/Finding all entities within a radius

Swifty

(Posted 2008) [#1]

Is there a better way to find all the entities in a radius around a central entity other than checking entitydistance of each entity in turn?

Doing it that way , I would end up having to check a LOT of entities.

Stevie G

(Posted 2008) [#2]

Not really but you could speed it up ( probably not by much ) by doing a few broad phase checks for each entity ... e.g...

   if abs( entityx( Player ) - entityx( check ) ) < Radius
      if abs( entityz( Player ) - entityz( check ) ) < Radius
        if abs( entityy( Player ) - entityy( check ) ) , Radius
          if EntityDistance( Player, check ) < radius
               ;within radius
          endif
       endif
    endif
  endif

chwaga

(Posted 2008) [#3]

that would definitely speed it up, but I don't see any other ways to speed it up.

Beaker

(Posted 2008) [#4]

I seriously doubt that would be faster on modern hardware. You might get a little more speed by checking for the unsquared distance, but even that would probably be negligable if written in Blitz itself.

Andy	(Posted 2008) [#5]

>Doing it that way , I would end up having to check a LOT of entities.

I generally check one each frame and then add it to an 'inside radius' list or to an 'outside radius' list. Then I have other functions do various things to either list.

Stevie G

(Posted 2008) [#6]

I did a quick check on the 3 methods for 20,000 entities. It's negligible on my machine :

Test1 = 1327ms
Test2 = 1322ms
Test3 = 1321ms

Graphics3D 800,600,32,1

Global PLAYER = CreatePivot()
Global CHECKpivot = CreatePivot()
Const Radius = 50
Const Radius2 = Radius * Radius
Const Number = 20000


For l = 1 To Number
	tmp = CreatePivot( CHECKpivot )
	PositionEntity tmp, Rand(-1000,1000 ), 0 , Rand(-1000,1000 )
Next

;test1
Test1 = MilliSecs()
For l = 1 To Number
	CHECK = GetChild( CHECKpivot, l )
	If Abs( EntityX( PLAYER ) - EntityX( CHECK ) ) < Radius
      If Abs( EntityY( PLAYER ) - EntityY( CHECK ) ) < Radius
        If Abs( EntityZ( PLAYER ) - EntityZ( CHECK ) ) < Radius
          If EntityDistance( PLAYER, CHECK ) < radius
               ;do nothing
          EndIf
       EndIf
    EndIf
  EndIf
Next
Test1 = MilliSecs() - Test1

;test2
Test2 = MilliSecs()
For l = 1 To Number
	CHECK = GetChild( CHECKpivot, l )
    If EntityDistance( PLAYER, CHECK ) < radius
	    ;do nothing
    EndIf
Next
Test2 = MilliSecs() - Test2

;test3
Test3 = MilliSecs()
For l = 1 To Number
	CHECK = GetChild( CHECKpivot, l )
	Dx# = EntityX( PLAYER ) - EntityX( CHECK )
	Dy# = EntityY( PLAYER ) - EntityY( CHECK )
	Dz# = EntityZ( PLAYER ) - EntityZ( CHECK )
	If ( Dx * Dx + Dy * Dy + Dz * Dz ) < Radius2 
	    ;do nothing
    EndIf
Next
Test3 = MilliSecs() - Test3


RenderWorld()

Text 0,10,"Test1 : "+Test1
Text 0,20,"Test2 : "+Test2
Text 0,30,"Test3 : "+Test3

Flip

WaitKey()
End

Jasu	(Posted 2008) [#7]

Usually Octree is used in these situations. I have failed to understand how to implement it so I have figured out a system of my own. For each object in space, I make a list of objects close to it. Depending on the speed of which the object moves I determine the frequency how often this list is recreated. All the calculations (like distance in your case) are done only between objects that are on the list. To prevent double calculation (object A having object B on its list and B having A), you can do a check like Handle(A) > Handle(B) in your calculation.

This is not as fast as Octree would be I think, but it comes so close that I never found the need to really learn to implement Octree.

Swifty

(Posted 2008) [#8]

Thanks for the help guys

Ross C

(Posted 2008) [#9]

Yeah, distance check is pretty dam fast!