Infinitegde
O.O
- Reaction score
- 86
Hellooo. Making a Qtree implementation. And I canNOT figure out what is wrong with the implementation. unfortunately its really annoying to debug so I was wondering if anyone can spot whats wrong with it? It gets buggy when it collapses. Although, there could be other bugs in it.
This code displays messages whenever the size of a Qtree changes and it also creates footmen and destroys them at the corners of the bounds.
It also displays when it splits and when it should collapse. I commented out the collapse function to see if that was causing it to bug. but there is still a bug for some reason.
In case you dont know what a qtree is it basically defines a rectangle. When you add nodes it splits the bounds into 4 spaces so that the nodes are added to those 4 spaces. This lets you check for nodes in the general area rather than check EVERY node in the bounds.
Implemented it using a doubly linked list for children of Qtree.
Insertion: logn/log4 I think?
Removal: logn/log4 I think? (needs to traverse to root of tree and decrease size)
OH and if you want to test out the code it uses T32
This code displays messages whenever the size of a Qtree changes and it also creates footmen and destroys them at the corners of the bounds.
It also displays when it splits and when it should collapse. I commented out the collapse function to see if that was causing it to bug. but there is still a bug for some reason.
In case you dont know what a qtree is it basically defines a rectangle. When you add nodes it splits the bounds into 4 spaces so that the nodes are added to those 4 spaces. This lets you check for nodes in the general area rather than check EVERY node in the bounds.
Implemented it using a doubly linked list for children of Qtree.
Insertion: logn/log4 I think?
Removal: logn/log4 I think? (needs to traverse to root of tree and decrease size)
OH and if you want to test out the code it uses T32
Code:
library Qtree initializer init
globals
integer MAXDEPTH=3
integer MAXLEAVES=4
endglobals
struct node
real x=0
real y=0
node prev=-1
node next=-1
Qtree root=-1
method remove takes nothing returns nothing
local Qtree qt=.root
debug if(.root==-1)then
debug call BJDebugMsg("Node not added!")
debug return
debug endif
call .root.removeNode(this)
loop
set qt=qt.root
exitwhen qt==-1
set qt.size=qt.size-1
if(qt.child.getType()==Qtree.typeid and qt.size<MAXLEAVES)then
call BJDebugMsg("Should collapse")
//call qt.collapse()
endif
endloop
endmethod
method update takes nothing returns boolean
local Qtree qt=.root
if(qt!=-1 and not .root.contains(.x,.y))then
call .root.removeNode(this)
loop
set qt=qt.root
exitwhen qt==-1
set qt.size=qt.size-1
call BJDebugMsg("SIZE "+I2S(qt.size))
exitwhen qt.add(this)
if(qt.child.getType()==Qtree.typeid and qt.size<MAXLEAVES)then
call qt.collapse()
endif
endloop
if(qt==-1)then
return true
endif
endif
return false
endmethod
endstruct
struct Qtree extends node
real r=0
real b=0
node child=-1
integer depth=0
integer size=0
debug unit c1
debug unit c2
debug unit c3
debug unit c4
static method create takes real x, real y, real r, real b, integer d returns Qtree
local Qtree qt = Qtree.allocate()
debug set qt.c1= CreateUnit(Player(0),'hfoo',x,y,0)
debug set qt.c2= CreateUnit(Player(0),'hfoo',x,b,0)
debug set qt.c3= CreateUnit(Player(0),'hfoo',r,y,0)
debug set qt.c4= CreateUnit(Player(0),'hfoo',r,b,0)
set qt.x=x
set qt.y=y
set qt.r=r
set qt.b=b
set qt.depth=d
return qt
endmethod
method contains takes real x, real y returns boolean
return .x<x and .r>=x and .y<y and .b>=y
endmethod
method split takes nothing returns nothing
local real mx=(.x+.r)/2
local real my=(.y+.b)/2
local integer newdepth=.depth+1
local node temp
local Qtree lt=Qtree.create(.x,.y,mx,my,newdepth)
local Qtree rt=Qtree.create(mx,.y,.r,my,newdepth)
local Qtree lb=Qtree.create(.x,my,mx,.b,newdepth)
local Qtree rb=Qtree.create(mx,my,.r,.b,newdepth)
call BJDebugMsg("SPLIT AT "+I2S(.depth+1))
set lt.next=rt
set rt.next=lb
set lb.next=rb
set lt.root=this
set rt.root=this
set lb.root=this
set rb.root=this
loop
exitwhen .child==-1
set temp=.child
set .child=.child.next
if(not (lt.add(temp) or rt.add(temp) or lb.add(temp) or rb.add(temp)))then
debug call BJDebugMsg("QTREE:FAILED TO ADD NODE")
endif
endloop
set .child=lt
endmethod
method removeNode takes node n returns nothing
if(not .contains(n.x,n.y))then
//call BJDebugMsg("Remove Node")
set .size=.size-1
call BJDebugMsg("SIZE "+I2S(.size))
set n.next.prev=n.prev
set n.prev.next=n.next
set n.next=-1
set n.prev=-1
set n.root=-1
endif
endmethod
method collapse takes nothing returns nothing
local node temp=-1
local node tempLower
local Qtree tempQtree
call BJDebugMsg("Collapse at "+I2S(.depth+1))
loop
exitwhen .child==-1
set tempQtree= Qtree(.child)
loop
exitwhen tempQtree.child==-1
set tempLower=tempQtree.child
set tempQtree.child=tempQtree.child.next
set tempLower.next=temp
if(temp!=-1)then
set temp.prev = tempLower
endif
set temp =tempLower
set temp.root=this
endloop
set .child=.child.next
call tempQtree.destroy()
endloop
set .child=temp
endmethod
method add takes node n returns boolean
local node temp
if(not .contains(n.x,n.y))then
return false
endif
set .size=.size+1
call BJDebugMsg("SIZE "+I2S(.size))
if(.child.getType()==Qtree.typeid)then
set temp = .child
loop
exitwhen temp==-1 or Qtree(temp).add(n)
set temp=temp.next
if(temp==-1)then
set .size=.size-1
call BJDebugMsg("QTREE:THIS SHOULD NEVER HAPPEN")
endif
endloop
return true
endif
//debug call BJDebugMsg("ADDED TO "+I2S(.depth))
set .child.prev=n
set n.next=.child
set .child=n
set n.root=this
if(.depth<MAXDEPTH and .size>MAXLEAVES)then
call .split()
endif
return true
endmethod
debug method onDestroy takes nothing returns nothing
debug call RemoveUnit(.c1)
debug call RemoveUnit(.c2)
debug call RemoveUnit(.c3)
debug call RemoveUnit(.c4)
debug endmethod
endstruct
struct unitCapture extends node
unit u
Qtree top
method periodic takes nothing returns nothing
set .x=GetUnitX(.u)
set .y=GetUnitY(.u)
if(not .root.contains(.x,.y))then
call .remove()
call .top.add(this)
endif
endmethod
implement T32x
endstruct
function init takes nothing returns nothing
local Qtree qt =Qtree.create(-2000,-2000,2000,2000,0)
local integer i=0
local unitCapture uc
local real x
local real y
local node n
loop
exitwhen i>4
set x= GetRandomReal(-2000,2000)
set y= GetRandomReal(-2000,2000)
set uc= unitCapture.create()
set uc.u=CreateUnit(Player(0),'hgry',x,y,0)
set uc.x=x
set uc.y=y
set uc.top=qt
call uc.startPeriodic()
call qt.add(uc)
set i =i+1
endloop
endfunction
endlibrary
