Finding all entities within a radius

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.

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

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

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.

>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.

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

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.

Thanks for the help guys

Yeah, distance check is pretty dam fast!