Ah, I see.
Anyways, I'm not *really* looking for something to find the n closest neighbors, I just wanted to do that to test out my quad tree. I'm not even sure how to get a couple adjacent neighbors :\
Also, have the quadtree thing up and running for the most part. Code got all muddled, so i just scrapped it and restarted.
code:
type vec2
x as float
y as float
endtype
type masterNode
tl as vec2
br as vec2
m as dword
endtype
type unit
p as vec2 `position
lp as vec2 `last position
d as vec2 `direction
c as dword `color
node as dword `address of the current node
endtype
d3d_init
global ret as vec2
global dim unit(0) as unit
global unitnum as dword
global dim off(1,1) as vec2
off(0,0).x=-1 `0
off(0,0).y=-1
off(0,1).x= 1 `4
off(0,1).y=-1
off(1,0).x=-1 `8
off(1,0).y= 1
off(1,1).x= 1 `12
off(1,1).y= 1
Global M as masterNode `master node
M.tl.x=40
M.tl.y=20
M.br.x=screen width()-100
M.br.y=screen height()-100
create_Mnode()
`fill_subnodes(M.m)
`fill_subnodes(peek dword(M.m+4))
`fill_subnodes(peek dword(peek dword(M.m+4)+8))
`fill_subnodes(peek dword(peek dword(peek dword(M.m+4)+8)+12))
mouse=0
do
cls
text 0,0,str$(contains(M.m))
d3d_batch_set_line2d 100000
d3d_batch_set_dot2d 100000
if mouseclick()=1 and mouse=0
add_unit(mousex(),mousey(),rgb(rnd(255),rnd(255),rnd(255)))
mouse=1
ENDIF
if mouseclick()=2 and mouse=0
mouse=1
q as dword
q=getNode(M.m,mousex(),mousey())
if q>0 and q<>M.m then cleanNode(peek dword(q+16))
endif
if spacekey()=1
for n=0 to 3
fill_subnodes(getNode(M.m,normPoint()*30+mousex(),normPoint()*30+mousey()))
next n
endif
if mouseclick()=0 then mouse=0
draw_all()
d3d_batch_draw_line2d 1
d3d_batch_draw_dot2d 1
sync
LOOP
function draw_all()
color as dword
color=rgb(0,0,255)
d3d_batch_add_line2d M.br.x,M.tl.y,M.br.x,M.br.y,color
d3d_batch_add_line2d M.tl.x,M.br.y,M.br.x,M.br.y,color
d3d_batch_add_line2d M.tl.x,M.tl.y,M.tl.x,M.br.y,color
d3d_batch_add_line2d M.tl.x,M.tl.y,M.br.x,M.tl.y,color
draw_node(M.m,color)
ENDFUNCTION
function moveObj(obj as integer,x as float, y as float)
unit(obj).lp=unit(obj).p
unit(obj).p.x=x
unit(obj).p.y=y
Q_handle_move(obj)
endfunction
function Q_handle_move(obj as integer)
`this function will handle unit obj moving from position unit(obj).p to unit(obj).lp, assuming
`that the object is in the node it was in at unit(obj).lp
if unit(obj).node=M.m then exitfunction `don't mess with teh master!!!
if isInNode(unit(obj).node,unit(obj).p.x,unit(obj).p.y)=1 then exitfunction
`Alright, Here, we have an obj that has moved from its node (gasp!), time to remove its info
`from its last node, and add its info to the new one.
poke dword unit(obj).node+20,0
cleanNode(peek dword(unit(obj).node+16)) `may leave its super all BLAGH.
unit(obj).node=0 `out with the old.
add_unit_to_quadnode(getNode(M.m,x,y),obj) `in with the new.
endfunction
function isInNode(nodeAddress as dword, x as float, y as float) `check if x and y are bounded by node nodeAddress
if nodeAddress>0
qx#=peek float(nodeAddress+24)
qy#=peek float(nodeAddress+28)
w#=peek float(nodeAddress+32)
h#=peek float(nodeAddress+36)
if absolute(x-qx#)<=w# and absolute(y-qy#)<=h# then exitfunction 1
endif
endfunction 0
function absolute(n as float)
a#=n and (not 1<<31)
endfunction a#
function draw_node(nodeAddress as dword,color as dword) `draws a node and all of its subnodes
if nodeAddress>0 `is a valid node
if peek dword(nodeAddress)>0 `has subnodes
x#=peek float(nodeAddress+24)
y#=peek float(nodeAddress+28)
w#=peek float(nodeAddress+32)
h#=peek float(nodeAddress+36)
d3d_batch_add_line2d x#,y#-h#,x#,y#+h#,color
d3d_batch_add_line2d x#-w#,y#,x#+w#,y#,color
for n=0 to 3
draw_node(peek dword(nodeAddress+n*4),color)
NEXT
else
o as dword
o =peek dword(nodeAddress+20)
if o>0 then d3d_batch_add_dot2d unit(o).p.x,unit(o).p.y,unit(o).c
endif
ENDIF
endfunction
function getNode(nodeAddress as dword, x as float, y as float) `returns the highest order subnode at (x,y)
if peek dword(nodeAddress)>0
centx as float
centy as float
centx=peek float(nodeAddress+24)
centy=peek float(nodeAddress+28)
x2=sign(x-centx)
y2=sign(y-centy)
if x2=0 then x2=1
if y2=0 then y2=1
if x2=-1 then x2=0
if y2=-1 then y2=0
exitfunction getNode(peek dword(nodeAddress+x2*8+y2*4),x,y)
else
exitfunction nodeAddress
endif
endfunction 0
function add_unit(x as float, y as float, color as dword) `add a unit to the array and the quadtree
array insert at bottom unit()
inc unitnum,1
unit(unitnum).p.x=x
unit(unitnum).p.y=y
unit(unitnum).lp=unit(unitnum).p
unit(unitnum).d.x=0
unit(unitnum).d.y=1
unit(unitnum).c=color
add_unit_to_quadnode(getNode(M.m,x,y),unitnum)
endfunction
function cleanNode(nodeAddress as dword)
if nodeAddress>0 and peek dword(nodeAddress)>0 `if it's not a node, ignore it. If it has no subnodes, ignore it. An empty node is a clean node.
for n=0 to 3
cleanNode(peek dword(nodeAddress+n*4))
NEXT
r=contains(nodeAddress)
if r=0 `no objects? Then the subnodes are doing NOTHING! LAZY SUBNODES WTF GTFO
delete_subnodes(nodeAddress)
exitfunction
endif
if r=1 `if there's one object... kill teh clutter, and bump that sucker up from its node.
obj as dword
for n=0 to 3
obj=peek dword(peek dword(nodeAddress+n*4)+20)
if obj>0 then break
next n
print obj
wait key
delete_subnodes(nodeAddress)
add_unit_to_quadnode(nodeAddress,obj)
exitfunction
endif
`more than one object? That's OK, because all the subnodes have been cleaned (at the top o' teh function).
endif
ENDFUNCTION
function contains(nodeAddress as dword) ` return the number of objects contained in the node and its subnodes.
ret as dword
if peek dword(nodeAddress)>0
ret=0
for n=0 to 3
ret=ret+contains(peek dword(nodeAddress+n*4))
NEXT
exitfunction ret
else
ret=peek dword(nodeAddress+20)
if ret>0 then exitfunction 1
exitfunction 0
endif
ENDFUNCTION 0
function add_unit_to_quadnode(nodeAddress as dword, obj as dword) `add a unit to the node.
`handles if multiple objs are in the same node. Passing in nodeAddress might be a bit of a pain,
`but it allows one to pinpoint a node, instead of going aaall the way down from the master node
`every single recursive step. call with M.m in nodeAddress if you just want to add it to the quadtree.
if nodeAddress>0 and obj>0
if peek dword(nodeAddress+20)>0
obj2=peek dword(nodeAddress+20)
if unit(obj).p.x=unit(obj2).p.x and unit(obj).p.y=unit(obj2).p.y then exitfunction `if they're in the same position, forget it.
poke dword nodeAddress+20,0
fill_subnodes(nodeAddress)
add_unit_to_quadnode(getNode(nodeAddress,unit(obj2).p.x,unit(obj2).p.y),obj2)
add_unit_to_quadnode(getNode(nodeAddress,unit(obj).p.x,unit(obj).p.y),obj)
else
poke dword nodeAddress+20,obj
unit(obj).node=nodeAddress
endif
ENDIF
endfunction
function create_Mnode()
M.m=alloc zeroed(44)
poke float M.m+24,(M.tl.x+M.br.x)/2.0
poke float M.m+28,(M.tl.y+M.br.y)/2.0
poke float M.m+32,(M.br.x-M.tl.x)/2.0
poke float M.m+36,(M.br.y-M.tl.y)/2.0
endfunction
function create_node(super as dword, index as dword)
`index goes from 0 to 3
`four dwords for subnodes - 0 - 4 - 8 - 12
`one dword for supernodes - 16
`one dword for stored info - 20
`center position x - 24
`center position y - 28
`half the width of the cell - 32
`half the height - 36
`node depth level - 40
mem as dword
mem=alloc zeroed(44)
poke dword super+4*index,mem
poke dword mem+16,super
w#=peek float(super+32)/2
h#=peek float(super+36)/2
poke float mem+24,peek float(super+24)+w#*off(index).x
poke float mem+28,peek float(super+28)+h#*off(index).y
poke float mem+32,w#
poke float mem+36,h#
poke dword mem+40,peek dword(super+40)+1 `IE : |3|3|_2|_2|_2|_______1| <-bintree w/ depth level, 0 would be the whole thing.
endfunction
function delete_subnodes(nodeAddress as dword)
if nodeAddress>0 and peek dword(nodeAddress)>0
for n=0 to 3
delete_subnodes(peek dword(nodeAddress+n*4))
free peek dword(nodeAddress+n*4)
poke dword nodeAddress+n*4,0 `dissociate pointers
next
endif
endfunction
function fill_subnodes(nodeAddress as dword)
g as dword
g=peek dword(nodeAddress+20)
poke dword nodeAddress+20,0
for n=0 to 3
create_node(nodeAddress,n)
NEXT
if g>0
add_unit_to_quadnode(getNode(nodeAddress,unit(g).p.x,unit(g).p.y),g)
endif
ENDFUNCTION
`MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTHHHHHHHHHHHH
function hi_word(n as dword)
b as word
b=(n>>16)
endfunction b
function lo_word(n as dword)
b as word
b=n and %00000000000000001111111111111111
endfunction b
function hi_byte(n as word)
b as byte
b=(n>>8)
endfunction b
function lo_byte(n as word)
b as byte
b=n and %0000000011111111
endfunction b
function lo_bit(n as byte)
b as byte
b=n and %00000001
endfunction b
function hi_bit(n as byte)
b as byte
b=(n and %00000010)>>1
endfunction b
function sign(a as float)
if a=0 then exitfunction 0
if a<0 then exitfunction -1
endfunction 1
function maximum(a as integer, b as integer)
if a>b then exitfunction a
endfunction b
function minimum(a,b)
if a<b then exitfunction a
endfunction b
function normPoint()
`returns a value whose probability of being between any two values is the same as the area under the normal distribution inbetween those two values.
p#=(rnd(999997)+1)/999999.0
r#=SNormInv(p#)
endfunction r#
Function SNormInv(p as float) `estimates the inverse of the sum of the normal distribution. Fun!
q as float
r as float
A1 as float
A2 as float
A3 as float
A4 as float
A5 as float
A6 as float
B1 as float
B2 as float
B3 as float
B4 as float
B5 as float
C1 as float
C2 as float
C3 as float
C4 as float
C5 as float
C6 as float
D1 as float
D2 as float
D3 as float
D4 as float
P_LOW as float
P_HIGH as float
`Coefficients in rational approximations.
A1= -39.69683
A2= 220.9461
A3= -275.9285
A4= 138.3578
A5= -30.66480
A6= 2.506628
B1= -54.47610
B2= 161.5858
B3= -155.6990
B4= 66.80131
B5= -13.28068
C1= -0.007785
C2= -0.322396
C3= -2.400758
C4= -2.549733
C5= 4.374664
C6= 2.938164
D1= 0.007784696
D2= 0.3224671
D3= 2.445134
D4= 3.754409
P_LOW= 0.02425
P_HIGH=1-P_LOW
if p>0 and p<P_LOW
`Rational approximation for lower region.
q = Sqrt(-2*Log(p))
ret#=(((((C1*q+C2)*q+C3)*q+C4)*q+C5)*q+C6)/((((D1*q+D2)*q+D3)*q+D4)*q+1)
exitfunction ret#
endif
If p>=P_LOW and p<=P_HIGH
`Rational approximation for central region.
q=p-0.5
r=q*q
ret#=(((((A1*r+A2)*r+A3)*r+A4)*r+A5)*r+A6)*q/(((((B1*r+B2)*r+B3)*r+B4)*r+B5)*r+1)
exitfunction ret#
endif
if p> _HIGH and p<1
`Rational approximation for upper region.
q = Sqrt(-2*Log(1-p))
ret#=-(((((C1*q+C2)*q+C3)*q+C4)*q+C5)*q+C6)/((((D1*q+D2)*q+D3)*q+D4)*q+1)
exitfunction ret#
endif
endfunction 0.0
Runs pretty well, but I was stuck for a while on a stupid mistake I made where the width of everything was negative, giving really weird patterns where I added nodes (one was actually a diagonal sierpinski triangle... no clue why/how X_X). The error I have now is that the cleanNode function sometimes deletes objects. I guess that when cleanNode calls itself, there can be a node that has subnodes that have subnodes etc. that has an object (instead of four terminating subnodes), and then that gets deleted. Every time you right click, and a "0" pops up, an object dies
It's 3 am though so I'll get it done tomorrow XD
