Nearest Neighbor Algo

Community Forums/General Help/Nearest Neighbor Algo

RifRaf

(Posted 2009) [#1]

Anyone know much about this algo. I need to create a function that can take a list of entities and report the x closest entities to the source entity.

the ent fields represent Blitz3D entities.
Example :

Type FieldObjects
field ent
End type

Type ReportedObjects
Field ent
end type

Function NearestEnt(sourceent,num_objects)
;algo here creates new ReportedObject type for each
;reported object, up to num_objects of them using the list
;of Fieldobjects as possible candidates
end function

I have looked at a few artciles about nearest neighbor algo, but the ones ive read so far i couldnt get my head around. I need the "Nearest Neighbor algo for dummies" version of the arcticle :)

GfK	(Posted 2009) [#2]

You could iterate through all entities and work out the relative distance for each:

dist = ((x2-x1) * (x2-x1)) + ((y2-y1) * (y2-y1)) + ((z2-z1) * (z2-z1))

If you just want to know which is nearest, you don't need to waste time calculating the square root (which would give the actual distance). Use the above algo, and the one with the smallest result, is the nearest.

RifRaf

(Posted 2009) [#3]

thanks for the input.. heres what ive come up with, feel free to improve on it and share :) Its not the speedy algo I was trying to learn, i gave up on that :)



;multi dx light system for tiny tanks. build 1.0

Type dxlightpos
Field x#,y#,z#
Field r,g,b
Field range
Field dist#
Field followent ;not used yet
End Type


;using 7 lights, one is reserverd for sunlight
Dim dxlight(7)

Function initlights()
;called between maps, remove lightpositions
Delete Each dxlightpos
For i=1 To 7
	If dxlight(i)=0 Then dxlight(i)=CreateLight(2)
	PositionEntity dxlight(i),9000,-9000,9000
	LightRange dxlight(i),1
Next
End Function 


Function removelights()
;called on game exit remove all
Delete Each dxlightpos
For i=1 To 7
	If dxlight(i)<>0 Then 
		FreeEntity dxlight(i)
		dxlight(i)=0
 	EndIf
Next
End Function 




;have not speed tested this yet, but I see no reason to call it every frame, once every 300ms should be smooth enough
Function UpdateLights(source,numberof=7)

For dxl.dxlightpos=Each dxlightpos
    dxl\dist#=distance(dxl\x,dxl\y,dxl\z,EntityX(source,1),EntityY(source,1),EntityZ(source,1))
Next

bestdist#=99999999
Sorted=0
While Sorted=0
	amlower=0
	For dxl.dxlightpos =Each dxlightpos
		If dxl\dist<bestdist Then 
			amlower=1
			Insert dxl.dxlightpos Before First dxlightpos
    	    bestdist=dxl\dist
            Exit
		EndIf
    Next 		
    If amlower=0 Then sorted=1
Wend		

i=0
For dxl.dxlightpos=Each dxlightpos
	i=i+1
	LightColor dxlight(i),dxl\r,dxl\g,dxl\b
    LightRange dxlight(i),dxl\range
    PositionEntity dxlight(i),dxl\x,dxl\y,dxl\z
    If i=numberof Then Exit
Next

End Function

GfK	(Posted 2009) [#4]

Where's your Distance() function?

Assuming that's all in order, just time the function over a million or so iterations to work out how fast it is. 8 loops per call probably won't even register 1ms so I think you'll be safe at that.

RifRaf

(Posted 2009) [#5]

sorry, take your pick

Function Distance#( x#, y#, z#, x2#, y2#, z2# )
	value#=Sqr((x#-x2#)*(x#-x2#)+(y#-y2#)*(y#-y2#)+(z#-z2#)*(z#-z2#))
	Return value#
End Function
Function DistanceF#( x#, y#, z#, x2#, y2#, z2# )
	value#=(x#-x2#)*(x#-x2#)+(y#-y2#)*(y#-y2#)+(z#-z2#)*(z#-z2#)
	Return value#
End Function

The actual number of light positions to check is unlimited, its only 7 active at any one time. Proper light placement vs lightrange should be able to create a well lit scene i think.

edit: somthing is not quite right, i can see visually that im closer to certain lights but they dont activate until im much close than I should be.

GfK	(Posted 2009) [#6]

You might have to Abs() each subtraction cos it might screw up if any negative values are in there?

value#=Abs((x#-x2#)*(x#-x2#))+Abs((y#-y2#)*(y#-y2#))+Abs((z#-z2#)*(z#-z2#))

Another possibility is that the float the result is stored in, is overflowing. Depends on your game scale.

If you only need to know which light is nearest, regardless of how far away it is, use your second function.

If you also need to know the distance, use the first.

RifRaf

(Posted 2009) [#7]

thanks, i didnt catch the abs() however with that correction neither distance call is correcting the glitch. The test map is only 1200 blitz units across. centered at 0,0,0. Perhaps i misunderstood how insert works. Does it move the list object , and are there errors in doing this in a loop of the same list.

GfK	(Posted 2009) [#8]

Can't help with that one, I'm afraid. Blitz3D is all a bit alien to me these days.

RifRaf

(Posted 2009) [#9]

thats ok, thanks for the help anyway. I got it sorted. Punting the lower distance to the front was just the wrong way to go about it, caused some that should be near the front not to make it simply because the distance was higher than the one that previously made it to front. However moving the larger distance lights to the back seems to work fine. here it is


;multi dx light system for tiny tanks. build 1.0

Type dxlightpos
Field x#,y#,z#
Field r,g,b
Field range
Field dist#
Field followent ;not used yet
End Type


;using 7 lights, one is reserverd for sunlight
Dim dxlight(7)

Function initlights()
;called between maps, remove lightpositions
Delete Each dxlightpos
For i=1 To 7
	If dxlight(i)=0 Then dxlight(i)=CreateLight(2)
	PositionEntity dxlight(i),9000,-9000,9000
	LightRange dxlight(i),0
Next
End Function 


Function removelights()
;called on game exit remove all
Delete Each dxlightpos
For i=1 To 7
	If dxlight(i)<>0 Then 
		FreeEntity dxlight(i)
		dxlight(i)=0
 	EndIf
Next
End Function 

;have not speed tested this yet, but I see no reason to call it every frame, once every 300ms should be smooth enough
Function UpdateLights(source,numberof=7)
For dxl.dxlightpos=Each dxlightpos
    dxl\dist#=Abs(distancef(dxl\x,dxl\y,dxl\z,EntityX(source,1),EntityY(source,1),EntityZ(source,1)))
Next
bestdist#=0
Sorted=0
While sorted=0
	amhigher=0
	For dxl.dxlightpos =Each dxlightpos
		If dxl\dist>bestdist Then 
			amhigher=1
			Insert dxl.dxlightpos After Last dxlightpos
		    bestdist=dxl\dist
        EndIf
    Next 		
    If amhigher=0 Then sorted=1
Wend



i=0
For dxl.dxlightpos=Each dxlightpos
	i=i+1
	LightColor dxlight(i),dxl\r,dxl\g,dxl\b
    LightRange dxlight(i),dxl\range
    PositionEntity dxlight(i),dxl\x,dxl\y,dxl\z
    If i=numberof Then Exit
Next
End Function

if anyone uses this you will need the distance functions I posted above

Nate the Great

(Posted 2009) [#10]

hmm, I did some test out of curiosity...

Graphics 640,480,0,2

b = MilliSecs()
For i = 0 To 1000000
	distance(123,234,243,654,5645,534)
Next
Print MilliSecs()-b

b = MilliSecs()
For i = 0 To 1000000
	distancef(123,234,243,654,5645,534)
Next
Print MilliSecs()-b

b = MilliSecs()
For i = 0 To 1000000
	quickdistance(123,234,243,654,5645,534)
Next
Print MilliSecs()-b

Function Distance#( x#, y#, z#, x2#, y2#, z2# )
	value#=Sqr((x#-x2#)*(x#-x2#)+(y#-y2#)*(y#-y2#)+(z#-z2#)*(z#-z2#))
	Return value#
End Function
Function DistanceF#( x#, y#, z#, x2#, y2#, z2# )
	value#=(x#-x2#)*(x#-x2#)+(y#-y2#)*(y#-y2#)+(z#-z2#)*(z#-z2#)
	Return value#
End Function

Function quickdistance(x#,y#,z#,xx#,yy#,zz#)
	Local dx# = x-xx
	Local dy# = y-yy
	Local dz# = z-zz
	Return (dx*dx + dy*dy + dz*dz)
End Function

WaitKey()

I consistently get

130,100,100 respectively in b3d which makes sense but here is the odd part... taking out the graphics command, using the same code in bmax, I get 40,28, and 83

I dont see why the latter function is less efficient in bmax, it should be more efficient taking away 3 subtractions for each loop ... odd isnt it?

Ross C

(Posted 2009) [#11]

Insert is pig slow. Insert will basically redirect the pointers from and the pointers to that object, from the one before and after. You can Insert BEFORE and insert AFTER. I'll have a lookie when i get home though. I've recently done stuff like this in my waypoint editor, so it's still fairly fresh in my mind.

ubergeek

(Posted 2009) [#12]

Totally off topic, but is it just me or are the times messed up?

...
Gfk: 1 hour ago
RifRaf: 1 hour ago
Gfk: 32 minutes ago
RifRaf: 29 minutes ago
Nate the Great: 43 minutes ago
Ross C: 6 hours ago

_Skully

(Posted 2009) [#13]

Yup.. might explain the whole "active topics" going completely blank frequently too

TaskMaster

(Posted 2009) [#14]

Happens on the first day of every month...

ubergeek

(Posted 2009) [#15]

Ah, that explains it. I forgot about that little "feature" of these forums. ;)

Looks like it's fixed now.

_Skully

(Posted 2009) [#16]

Why doesn't it just filter for messages posted in the last 48 hours or something?

Shagwana

(Posted 2009) [#17]

This old code arc post from me may be of intrest in speeding this up.

It has distance aproximation functions that are faster then the ones you have posted.

Adam Novagen

(Posted 2009) [#18]

Am I missing something here, or has everyone COMPLETELY forgotten the EntityDistance() function... ? O.o

Jerome Squalor

(Posted 2009) [#19]

here you go, i asked for this a few years back also

Function NearestBall(refferenceEntity)

Local ball.tBall
Local nearestBall.tBall
Local nearestDist#

;Assume first tBall instance is the nearest
nearestBall = First tBall
nearestDistance = EntityDistance(bat,nearestBall\entity)

For ball = Each tBall
If ball <> nearestBall
dist = EntityDistance(refferenceEntity,ball\entity)
If dist < nearestDist
nearestBall = ball
nearestDist = dist
End If
End If
Next

Return nearestBall\entity
End Function

if u need help with it let me know