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
[pbcode]
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
next n
te=timer()
print te-ts
Print "Closest Object Number:"+str$(Nearest)
print ""
` -----------------------------------------------------------------------
` Test 4
` -----------------------------------------------------------------------
`
` This one uses a min/max range to screen out seriously checking all the
` objects if they are within range. It should be noted that if no objects
` are within the MIN range, then the NEAREST object offset will equal 0
`
` The code is longer yes, but faster also since were only checking distance
` when the DX or DZ falls with the MIN range.
` -----------------------------------------------------------------------
ts=timer()
Nearest=0
MaxDistance=5000
MinDistance=500
for n=1 to NumberOfObjects
dx=abs(ObjectX(n)-PlayerX)
dz=abs(ObjectZ(n)-PlayerZ)
if Dx=>dZ
if Dx<=MinDistance
if sqrt((dx*dx)+(dz*dz)) < MaxDistance
MaxDistance=sqrt((dx*dx)+(dz*dz))
Nearest=n
endif
endif
else
if Dz<=MinDistance
if sqrt((dx*dx)+(dz*dz)) < MaxDistance
MaxDistance=sqrt((dx*dx)+(dz*dz))
Nearest=n
endif
endif
endif
next n
te=timer()
print te-ts
if Nearest=0
Print "Closest Object Number: Nothing within Min range"
else
Print "Closest Object Number:"+str$(Nearest)
endif
print ""
` -----------------------------------------------------------------------
` Test 5
` -----------------------------------------------------------------------
`
` This one uses a min/max range also but avoids the square roots. It's
` ironic really, while a square root is slower than regular math operations
` it's not that bad in terms speed in DB. This is bound to change in DBpro
` however so via not using a square root your going for the max speed.
`
` -----------------------------------------------------------------------
ts=timer()
Nearest=0
MaxDistance=10000
MaxDistanceSquared=MaxDistance*MaxDistance
MinDistance=500
for n=1 to NumberOfObjects
dx=abs(ObjectX(n)-PlayerX)
dz=abs(ObjectZ(n)-PlayerZ)
if Dx=>dZ
if Dx<=MinDistance
if (dx*dx)+(dz*dz) < MaxDistanceSquared
MaxDistanceSquared=(dz*dz)+(dx*dx)
Nearest=n
endif
endif
else
if Dz<=MinDistance
if (dx*dx)+(dz*dz) < MaxDistanceSquared
MaxDistanceSquared=(dx*dx)+((ObjectZ(n)-PlayerZ)^2)
Nearest=n
endif
endif
endif
next n
te=timer()
print te-ts
if Nearest=0
Print "Closest Object Number: Nothing within Min range"
else
Print "Closest Object Number:"+str$(Nearest)
endif
print ""
sync
loop
[/pbcode]