Nevermind I got it to work:
1 cup of coffee is all it took. I was drowsy while I coded this(I'm taking meds for allergies that makes me drowsy) and missed the fact that non-leaf <> root.
*my wife is gonna get pissed I drank coffee. :*(
'' binary tree
''http://www.blackpawn.com/texts/lightmaps/default.html
'#define DEBUG
enum
E_ROOT = 0
E_LEAF
E_NON_LEAF
end enum
type Trect
x1 as integer
y1 as integer
x2 as integer
y2 as integer
end type
type Timage
x as integer
y as integer
wid as integer
hei as integer
col as integer
end type
type Tnode
public:
declare constructor()
declare destructor()
declare function insert(byref img as Timage) as Tnode ptr
declare function is_leaf() as integer
child(0 to 1) as Tnode ptr
rect as Trect
imageID as integer '' sprite index (0 = subdivided else terminator)
nodeID as integer
private:
end type
'' tests if b could fit inside a
'' 0 = smaller
'' 1 = fits
'' 2 = one axis larger
function rec_fits(byval A as Trect, byval B as Trect) as integer
'' a.x1 = b.x1
'' a.y1 = b.y1
dim as integer a_wid = (a.x2 - a.x1) + 1
dim as integer a_hei = (a.y2 - a.y1) + 1
dim as integer b_wid = (b.x2 - b.x1) + 1
dim as integer b_hei = (b.y2 - b.y1) + 1
if (b_wid > a_wid) or (b_hei > a_hei) then
return 2
endif
if (b_wid < a_wid) or (b_hei < a_hei) then
return 0
endif
return 1
end function
constructor Tnode()
child(0) = 0
child(1) = 0
imageID = 0
nodeID = E_LEAF
end constructor
destructor Tnode()
if child(0) then delete child(0)
if child(1) then delete child(1)
end destructor
function Tnode.is_leaf() as integer
return ((child(0)=0) and (child(1)=0))
end function
function Tnode.insert(byref img as Timage) as Tnode ptr
'' non leaf
if (not is_leaf()) then 'we're not a leaf then
''print "root"
''sleep
'''(try inserting into first child)
dim as Tnode ptr newNode = child(0)->insert( img )
if (newNode <> 0) then
#ifdef DEBUG
print "inserted at child(0) of root"
#endif
return newNode
endif
''(no room, insert into second)
#ifdef DEBUG
print "inserted at child(1) off root"
#endif
return child(1)->insert( img )
else '' leaf
''print "leaf"
''sleep
''(if there's already a lightmap here, return)
if (imageID <> 0) then
#ifdef DEBUG
print "has image"
#endif
return 0
endif
dim as Trect b
b.x1 = rect.x1
b.y1 = rect.y1
b.x2 = (rect.x1 + img.wid)-1
b.y2 = (rect.y1 + img.hei)-1
'' check fit value
dim as integer result = rec_fits(rect, b)
#ifdef DEBUG
print result
#endif
''(if we're too small, return)
'' one of the image axis is bigger than rect
if (result = 2) then ''img doesn't fit in pnode->rect
#ifdef DEBUG
print "image too big"
#endif
return 0
end if
''(if we're just right, accept)
if (result = 1) then ''img fits perfectly in pnode->rect
#ifdef DEBUG
print "fits"
#endif
return @this
end if
''(otherwise, gotta split this node and create some kids)
'' ie: we are smaller so split the node
child(0) = new Tnode
child(1) = new Tnode
''(decide which way to split)
dim as integer rw = (rect.x2 - rect.x1)+1
dim as integer rh = (rect.y2 - rect.y1)+1
dim as integer dw = rw - img.wid
dim as integer dh = rh - img.hei
'' child 0 rect = image rect dimensions
if (dw > dh) then
child(0)->rect.x1 = rect.x1
child(0)->rect.y1 = rect.y1
child(0)->rect.x2 = rect.x1 + (img.wid - 1)
child(0)->rect.y2 = rect.y2
child(1)->rect.x1 = rect.x1 + (img.wid)
child(1)->rect.y1 = rect.y1
child(1)->rect.x2 = rect.x2
child(1)->rect.y2 = rect.y2
else
child(0)->rect.x1 = rect.x1
child(0)->rect.y1 = rect.y1
child(0)->rect.x2 = rect.x2
child(0)->rect.y2 = rect.y1 + (img.hei - 1)
child(1)->rect.x1 = rect.x1
child(1)->rect.y1 = rect.y1 + (img.hei)
child(1)->rect.x2 = rect.x2
child(1)->rect.y2 = rect.y2
end if
#ifdef DEBUG
print "child(0)dimensions:"; child(0)->rect.x1,child(0)->rect.y1,child(0)->rect.x2,child(0)->rect.y2
print "child(1)dimensions:"; child(1)->rect.x1,child(1)->rect.y1,child(1)->rect.x2,child(1)->rect.y2
#endif
'' return first child since it would fit perfectly
'' ie. we have just calculated the bounding box that
'' can hold the image perfectly
''child(0)->nodeID = E_NON_LEAF
return child(0)->insert(img)
end if
return 0
end function
function insert_images(byval m_root as Tnode ptr, byref img as Timage) as integer
static as integer id = 1
dim as Tnode ptr pnode = m_root->insert(img)
if (pnode <> 0) then
''copy pixels over from img into pnode->rc part of texture
line(pnode->rect.x1,pnode->rect.y1)-(pnode->rect.x2,pnode->rect.y2), img.col, bf
pnode->imageID = id
#ifdef DEBUG
print "yay!! ImageID = "; id
print "dimensions:"; pnode->rect.x1,pnode->rect.y1,pnode->rect.x2,pnode->rect.y2
#endif
id += 1
return 0
else
return 1
endif
end function
randomize timer
'' 640 * 480, 8 bit
#ifndef DEBUG
screen 18,8,1
#endif
dim as Timage image(0 to 15)
dim as Tnode tree
tree.child(0) = new Tnode
tree.child(1) = new Tnode
tree.nodeID = E_ROOT
tree.rect.x1 = 0
tree.rect.y1 = 0
tree.rect.x2 = 255
tree.rect.y2 = 255
tree.child(0)->rect.x1 = 0
tree.child(0)->rect.y1 = 0
tree.child(0)->rect.x2 = 255
tree.child(0)->rect.y2 = 255
'tree.child(1)->rect.x1 = 0
'tree.child(1)->rect.y1 = 0
'tree.child(1)->rect.x2 = 255
'tree.child(1)->rect.y2 = 255
for i as integer = 0 to 15
image(i).x = 0
image(i).y = 0
image(i).wid = 16 + int(rnd*11)
image(i).hei = 16 + int(rnd*11)
image(i).col = 1 + int(rnd*15)
next
for i as integer = 0 to 15
insert_images(@tree, image(i))
next i
for i as integer = 0 to 5
dim as integer x1=image(i).x
next i
sleep
