Optimzation Ideas - Manually Finding The Closest Object - Learn To Code

[kevin]

 Optimization Ideas - Manually Finding The Closest Object - Learn To Code

  This is quick port of an article I wrote originally in another programming language, however the ideas employed are fairly universal.  The example looks at ways of locating the nearest object out of a list of randomly positioned objects in 2D.  The comparison is made via a  brute force search.  In other words, in runs through all the objects looking for nearest one.  

  I should point out that i've not really made any attempt to PlayBASIC'ize the code.  It's almost identical to the original version.   Which can be found here www.DbCode.UnderwareDesign.com

PlayBASIC Code: [Select]

Rem * Title  : Testing Finding Closest Object
Rem * Author : Kevin Picone
Rem * Date   : 8,July,2002
` *=---------------------------------------------------------------------=*
`
`                        >> 2D Distance Calc Ideas <<
`
`                             7th, July, 2002
`
`                          By Kevin Picone 2002
`
`          (c) copyright 2002 Kevin Picone, All rights reserved
`
` *=---------------------------------------------------------------------=*

`
`  So What does this do ?:
`  =======================
` 
`   This selection of examples just takes a simulated 2D GET DISTANCE
` routine and tests a few opt's that could be made to it.
`
`   These types of routines are often used within collision detection.  The
` idea is to calc the closest object to the players position within the
` world. We can then assume if something is very close it might hit the
` player. 
` 
`   While this is ok, we probably should build a list of the closest objects
` within the pre set range rather than just find the nearest.  Once we have
` list that's within range we can then check if the player has hit one of
` them. Although perhaps it's just best to test 
`

`
`  Release.
`  =======
`
`    Free to use.  May NOT be sold.
`
`
`
`  Cya,
`  Kevin Picone
` *=-------------------------------------------------------------------=* 



NUmberOfobjects=5000

Dim ObjectX(NUmberOfobjects)
Dim ObjectZ(NUmberOfobjects)


 playerX=5000
 playerZ=5000



Do
 cls 0


 if space=0 
    for lp=1 to NumberOfObjects
      ObjectX(lp)=rnd(32000)
      ObjectZ(lp)=rnd(32000)
   next lp
   space=1
 else
   if spacekey()=1 then space=0
 endif


 Print "Press Space to Randomize the Object List"

 Print "Testing Objects:"+Str$(NumberOfObjects)


print ""





` -----------------------------------------------------------------------
` test 1
` -----------------------------------------------------------------------
`
`  A pretty standard looking check distance routine.While it works, it's
` not very quick.
`
` -----------------------------------------------------------------------


 ts=timer()
   Nearest=1
 
   for n=1 to NumberOfObjects
        if sqrt(abs(ObjectX(n)-PlayerX)^2+abs(ObjectZ(n)-PlayerZ)^2) < sqrt(abs(ObjectX(Nearest)-PlayerX)^2+abs(ObjectZ(Nearest)-PlayerZ)^2) then Nearest=n
   next n
 te=timer()
 print te-ts
 Print "Closest Object Number:"+str$(Nearest)
 print ""


` -----------------------------------------------------------------------
` Test 2
` -----------------------------------------------------------------------
`
` First opt is to remove the ABS() statements which give a nice little speed
` up
`
` -----------------------------------------------------------------------


 ts=timer()
   Nearest=1
   for n=1 to NumberOfObjects
        if sqrt((ObjectX(n)-PlayerX)^2+(ObjectZ(n)-PlayerZ)^2) < sqrt((ObjectX(Nearest)-PlayerX)^2+(ObjectZ(Nearest)-PlayerZ)^2) then Nearest=n
   next n
 te=timer()
 print te-ts
 Print "Closest Object Number:"+str$(Nearest)
 print ""



` -----------------------------------------------------------------------
` test 3
` -----------------------------------------------------------------------
`
`  The logical thing to is that rather than compare one calc distance
` with and another distance calc, is to use a variable to hold the MAX
` distance.  IF the object your testing is lower than this value, then
` we set MAX Distance to this value and continue on. This should make
` faster as it's only calc'ing  the MAX distance value when it needs.
`
` -----------------------------------------------------------------------

 ts=timer()
   Nearest=1
   MaxDistance=100000
   for n=1 to NumberOfObjects
        if sqrt((ObjectX(n)-PlayerX)^2+(ObjectZ(n)-PlayerZ)^2) < MaxDistance

         MaxDistance=sqrt((ObjectX(n)-PlayerX)^2+(ObjectZ(n)-PlayerZ)^2)
         Nearest=n
      endif

Login required to view complete source code