QUADTREES!!!!!
Or... I dunno what you'd call them. N-trees. Something along those lines. The idea of quadtrees is that you have a plane, and you divide that plane into fourths, and then those sections into fourths, and then the subsections, etc. until you have every object in its own subsection.
What you would be doing would be similar. Here's an example I have of a quatree:
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
ang as float
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
sync on
sync rate 0
do
cls
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
add_unit(normPoint()*30+mousex(),normPoint()*30+mousey(),rgb(rnd(255),rnd(255),rnd(255)))
next n
endif
for a=1 to unitnum
unit(a).ang=wrapvalue(unit(a).ang+rnd(100)/25.0-2.0)
moveObj(a,unit(a).p.x+cos(unit(a).ang),unit(a).p.y+sin(unit(a).ang))
next
if mouseclick()=0 then mouse=0
print "contains(M.m)="+str$(contains(M.m))
print screen fps()
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
if unit(obj).p.x<M.tl.x then unit(obj).p.x=M.br.x `wraparound
if unit(obj).p.x>M.br.x then unit(obj).p.x=M.tl.x
if unit(obj).p.y<M.tl.y then unit(obj).p.y=M.br.y `wraparound
if unit(obj).p.y>M.br.y then unit(obj).p.y=M.tl.y
Q_handle_move(obj)
endfunction
function Q_handle_move(obj as integer)
`this function will handle unit obj moving from position unit(obj).lp to unit(obj).p, 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
exitfunction
endif
`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,unit(obj).p.x,unit(obj).p.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*sign(n)
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.
r=contains(nodeAddress)
for n=0 to 3
cleanNode(peek dword(nodeAddress+n*4))
NEXT
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 goto skip
next n
skip:
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
You'll need IanM's matrix dlls (I use the memory allocation and deallocation commands), and the d3dfunc dll (It draws a lot of lines, and barely runs about 9 fps for 100 objects with native commands, but 100 fps with 2000 objects with d3d_lines).
Now... I used memory allocation and deallocation so I could quickly change the structure of the tree. However, you could use an array, it doesnt really matter.
The idea is that you have a data structure that points to data structures like itself, or nothing. Thats why almost all my code is recursive (a recursive function calls itself), because every quadtree node is a quadtree (and every one of its nodes, and so on and so forth).
O'course, that might be all unnecessary complicated. You could just create 3 separate arrays of 10 towns, 100 houses, and 1000 rooms, and call it a day! I would think the best way would be to have town 0 point to houses 0-9, house 1 point to rooms 10-19, etc.
If you want to dynamically change the number of rooms/houses... You could either just create all the arrays the max size allowed, and then just have a list of excluded rooms/houses/buildings. Otherwise, your best bet is just the weird poking and prodding akin to the quadtree codez.
