# SnippetQTree

#### Infinitegde

##### O.O
QTree v1.1
Uses: vJass
Testmap uses: T32
How to Import:
1)Create trigger called Qtree.
2)Convert to custom code.
3)Paste the code from here.​

Description:
The Qtree is a way to index points by location. When you add a node it adds it to the tree. if you have more than n-leaves, it splits the tree into 4 quadrants and adds the nodes to the quadrants they belong in. Similarly, if anymore than 4 nodes are added to any of those quadrants it splits again and so on and so on.

Why do you want to do this?
If your doing collision detection, you don't want to have to check EVERY node whether its nearby, (big O notation of n^2). With QTree's you can check it against the nodes in its quadrant which is (usually) at most 4. Which takes the complexity down to O(1). Insertion into the QTree is O(log(n)/log(leaves)), where n is number of nodes on the tree and leaves is the number of leaves per quadrant you specify.
Removal is also the same(It has to recur to root to decrease size.)

Qtree's are very good with POINTS. If you have a unit of collisionsize 1000 you probably dont want to be using Qtrees. However, you can still use it for this purpose. You can increase the scope of your search so it goes to a higher node on the root and gets all the nodes.

How to Use:
First thing you need is a struct that extends QT_node (a struct implemented in my snippet). node has the fields, real x, real y, node next, node prev, and node root. Do not touch next, prev, or root.
There are also a bunch of methods that you should be familiar with.

Self explanatory. Adds "this" node to a Qtree. Add it to the root to ensure it ends up in the right place. returns true if its added, false if its not.

update() returns true if its not within the bounds of the tree anymore (its removed), false otherwise.
It moves the node to its correct quadrant based on its x and y.
The update method is pretty quick, but call it only after you change the nodes x and y values.
This does have a textmacro!

removeFromQtree() is self explanatory. Removes it from the entire tree. make sure you call this before you destroy the node. it is very important.

getNodesRadius(integer radius)-this gets nodes in the a certain radius. THIS IS VERY COARSE. It might return units 1000 units away, if there still in the same quadrant. check the distances.
getQtreeScope(integer depth)-still your best friend. depth is how far back you want to go.
*same as above.

Qtree is a struct also implemented.
call Qtree.create(left,top,right,bottom,depth)
left - x of left side of rect, top- y of top side of rect, right - x of..., bottom - y of...,
depth - maximum depth of the qtree. (how many times it can be split.) Its not always good to have the depth be very high. Ill explain more later.

Qtree.getChildren() returns a nodeList which contains all the descendants (indirect included) of the qtree.

QT_nodes acts like an array. nodeList[x] returns the xth value of list.
QT_nodes.size returns size of list. Don't change the size of the list.
If you need to typecast an element of nodeList[x] you need to use this format.
Code:
``MYSTRUCT(QT_nodes[x].n).member``

Okay, so you want to choose a depth such that the width and height of the maximum bounds /2^depth is not very very small.
At least I think its 2^depth. What happens when you do it, it causes the width and height of the rects to get really small which can
cause bugs.

Code:
``````//Qtree
//By Infinitegde
//============================================================
//Description:
//Data structure for holding nodes that have X,Y coordinates.
//Indexes them in such a way so that, when you need to compare
//the nodes to eachother and check the nodes nearest you can call a function
//that will return nodes close to the node your looking at.
//That way, instead of a O(n^2) algorithm, you can minimize
//the comparisons. It goes from O(n^2) to kind of O(n)
//By kind of O(n), your checking a maximum(kind of again) of
//leaves^depth your searching. Where leaves is the max leaves
//on the tree. And depth is the depth your searching the tree.
//The reason for this kind of is because if your at the max
//depth the tree wont split anymore it will just add it to that
//part of the tree. That means you could be checking for more
//leaves^depth.
//=============================================================
//Stats:
//Let n be number of nodes on the tree
//Insertion: log(base MAXLEAVES)n
//Removal: log(base MAXLEAVES)n
//=============================================================
// HOW TO USE:
/*
//First thing you need is a struct that extends QT_node (a struct implemented in my snippet). node has the fields, real x, real y, node next, node prev, and node root. Do not touch next, prev, or root.
//There are also a bunch of methods that you should be familiar with.

//Self explanatory. Adds "this" node to a Qtree. Add it to the root to ensure it ends up in the right place. returns true if its added, false if its not.

//update() returns true if its not within the bounds of the tree anymore (its removed), false otherwise.
//It moves the node to its correct quadrant based on its x and y.
//The update method is pretty quick, but call it only after you change the nodes x and y values.
//This does have a textmacro!

//removeFromQtree() is self explanatory. Removes it from the entire tree. make sure you call this before you destroy the node. it is very important.

//getNodesRadius(integer radius)-this gets nodes in the a certain radius. THIS IS VERY COARSE. It might return units 1000 units away, if there still in the same quadrant. check the distances.
// *data is stored in static QT_nodes. Look on to learn more.
//getQtreeScope(integer depth)-still your best friend. depth is how far back you want to go.
// *same as above.

//Qtree is a struct also implemented.
//call Qtree.create(left,top,right,bottom,depth)
//left - x of left side of rect, top- y of top side of rect, right - x of..., bottom - y of...,
//depth - maximum depth of the qtree. (how many times it can be split.) Its not always good to have the depth be very high. Ill explain more later.

//Qtree.getChildren() returns a nodeList which contains all the descendants (indirect included) of the qtree.

//QT_nodes acts like an array. nodeList[x] returns the xth value of list.
//QT_nodes.size returns size of list. Don't change the size of the list.
//If you need to typecast an element of nodeList[x] you need to use this format.

MYSTRUCT(QT_nodes[x].n).member
*/
// Look at the Test trigger to see how it works...
//=================================================================
//Okay, so you want to choose a depth such that the width and height of the maximum bounds /2^depth is not very very small.
//At least I think its 2^depth. What happens when you do it, it causes the width and height of the rects to get really small which can
//cause bugs.
library QT
globals
public constant integer MAXLEAVES=4
endglobals
public struct node
real x=0
real y=0
node prev=-1
node next=-1
Qtree root=-1
local Qtree qt =.root
loop
exitwhen qt.root==-1
exitwhen true
endif
set qt=qt.root
endloop
return qt.getChildren(this)
endmethod
method getQtreeScope takes integer depth returns integer
local Qtree tmp = .root
loop
set depth=depth-1
exitwhen depth<=0 or tmp.root==-1
set tmp=tmp.root
endloop
return tmp.getChildren(this)
endmethod
method addToQtree takes Qtree root returns boolean
local Qtree tmp
if(not root.contains(.x,.y))then
return false
endif
loop
exitwhen root==-1
set root.size=root.size+1
if(root.child==-1 or root.child.getType()!=Qtree.typeid)then
set tmp=root
set .root=tmp
if(tmp.child==-1)then
set tmp.child=this
set tmp.tail=this
debug set .prev=-1
debug set .next=-1
else
set tmp.child.prev=this
set .next=tmp.child
debug set .prev=-1
set tmp.child=this
endif
if(tmp.depth>0 and tmp.size>MAXLEAVES)then
call tmp.split()
endif
return true
endif
set tmp=Qtree(root.child)
loop
if(tmp==-1)then
return false
endif
if(tmp.contains(.x,.y))then
set root=tmp
exitwhen true
endif
set tmp=tmp.next
endloop
endloop
return false
endmethod
method removeFromQtree takes nothing returns nothing
local Qtree qt=.root
local Qtree tmp=.root
if(.root==-1)then
return
endif
call .root.removeNode(this)
loop
set qt=qt.root
exitwhen not(qt.child.getType()==Qtree.typeid and qt.size<MAXLEAVES)
call qt.collapse()
set tmp =qt
endloop
set qt=tmp
loop
exitwhen qt==-1
set qt.size=qt.size-1
set qt=qt.root
endloop
endmethod
method update takes nothing returns boolean
local Qtree qt=.root
local Qtree tmp=.root
if(qt!=-1 and qt.contains(this.x,this.y))then
return false
endif
debug if(.root==-1)then
debug return false
debug endif
call .root.removeNode(this)
loop
set qt=qt.root
exitwhen not(qt.child.getType()==Qtree.typeid and qt.size<MAXLEAVES)
call qt.collapse()
set tmp =qt
endloop
set qt=tmp
loop
exitwhen qt==-1
set qt.size=qt.size-1
set qt=qt.root
endloop
if(qt==-1)then
return true
endif
return false
endmethod
endstruct
public struct nodes extends array
delegate node n
static integer size
/*static method operator[] takes integer i returns node
return nodes(i).n
endmethod*/
endstruct
struct Qtree extends node
real r=0
real b=0
node child=-1
node tail=-1
node cursor=-1
integer depth=0
integer size=0
static method create takes real x, real y, real r, real b, integer d returns Qtree
local Qtree qt = Qtree.allocate()
set qt.x=x
set qt.y=y
set qt.r=r
set qt.b=b
set qt.depth=d
set qt.size=0
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)
set lt.next=rt
set rt.next=lb
set lb.next=rb
set rb.prev=lb
set lb.prev=rt
set rt.prev=lt
set lt.root=this
set rt.root=this
set lb.root=this
set rb.root=this
set .tail=rb
loop
exitwhen .child==-1  or .child==.tail
set temp=.child
set .child=.child.next
debug call BJDebugMsg("Qtree:Make sure you call update when you change x and y!")
//call temp.update()
endif
endloop
set .child=lt
endmethod
method removeNode takes node n returns nothing
if(.child==n)then
set .child=n.next
else
set n.prev.next=n.next
endif
if(.tail==n)then
set .tail=n.prev
else
set n.next.prev=n.prev
endif
set n.next=-1
set n.prev=-1
set n.root=-1
endmethod
method collapse takes nothing returns nothing
local node temp=-1
local node tempLower
local Qtree tempQtree
set .tail=-1
loop
exitwhen .child==-1 or .child==.tail
set tempQtree= Qtree(.child)
if(tempQtree.child!=-1)then
if(.tail==-1)then
set .tail=tempQtree.tail
endif
set tempLower=tempQtree.child
loop
exitwhen tempLower==-1
set tempLower.root=this
set tempLower=tempLower.next
endloop
set tempQtree.tail.next=temp
set temp.prev=tempQtree.tail
set temp=tempQtree.child
endif
set .child=.child.next
call tempQtree.destroy()
endloop
set .child=temp
endmethod
private method sureAdd takes node n returns boolean
if(not .contains(n.x,n.y))then
return false
endif
set .size=.size+1
if(.child==-1)then
set .child=n
set .tail=n
set n.prev=-1
set n.next=-1
else
set .child.prev=n
set n.next=.child
set n.prev=-1
set .child=n
endif
set n.root=this
return true
endmethod
method getChildren takes  node n returns integer
local Qtree temp= this
local integer i=0
set .cursor=.child
loop
if(temp.cursor==-1)then
if(temp==this)then
//call BJDebugMsg("End!")
exitwhen true
endif
set temp=temp.root
set temp.cursor=temp.cursor.next
endif
if(temp.cursor.getType()==Qtree.typeid)then
set temp=temp.cursor
set temp.cursor=temp.child
elseif(temp.cursor!=n)then
set nodes(i).n=temp.cursor
set i=i+1
set temp.cursor=temp.cursor.next
else
set temp.cursor=temp.cursor.next
endif
endloop
set nodes.size=i
return i
endmethod
endstruct

function checkQtree takes Qtree qt returns integer
local integer size=0
local node temp =qt.child
local integer typeCheck = temp.getType()
loop
exitwhen temp==-1
if(temp.getType()!=typeCheck)then
call BJDebugMsg("Qtrees and nodes are in the same tree")
endif
if(temp.getType()==Qtree.typeid)then
set size=size+checkQtree(temp)
else
set size=size+1
endif
if(temp.root!=qt)then
call BJDebugMsg("Root is not set correctly")
endif
if(temp==qt.child)then
if(temp.prev!=-1)then
call BJDebugMsg("Bug- Child Prev!=-1")
endif
endif
if(temp==qt.tail)then
if(temp.next!=-1)then
call BJDebugMsg("Bug- Tail Next!=-1")
endif
elseif(temp.next.prev!=temp)then
call BJDebugMsg("Bug- Prev not set correctly2")
endif
if(temp.next==-1)then
if(temp!=qt.tail)then
call BJDebugMsg("Bug- Abrupt next==-1")
endif
elseif(temp.next.prev!=temp)then
call BJDebugMsg("Bug- Prev not set correctly1")
endif
if(temp.prev==-1)then
if(temp!=qt.child)then
call BJDebugMsg("Bug- Abrupt prev==-1")
endif
endif
set temp=temp.next
endloop
if(qt.size!=size)then
call BJDebugMsg("Size is out of sync! Actual:"+I2S(size)+","+I2S(qt.size))
endif
return size
endfunction
endlibrary``````

Notes:
Ironically,I forgot to follow my own instructions. This is VERY VERY important. MAKE SURE YOU CALL .update() WHENEVER you change the x and y values of the nodes.

If you find a bug try to determine whats causing it and post it here I'll try and fix it.
Also, there aren't that many helper functions yet because I want to make sure logistics are right, feel free to give me your idea for a helper function.
Also if anyone can help me with implementation so I can make it modular rather than needing it to extend the struct?
Wish vJass allowed you to have private members in a struct with the scope being a library or a scope rather than just the struct. =]
is this a snippet or a system...?

TestMap:
Things you can mess around with:
numberUnits. self explanatory
whichUnit, which unit to create
testDepth, 0 is for O(n^2) like algorithm. 5-10 will give you a nice O(nlogn) representation.
Just a good way to see the capabilities. MAKE SURE YOU RUN IT IN DEBUG MODE FIRST!
There are a few differences between debug and not debug mode in this test map.
If you run it in debug mode, it will create units you can see. If you disable the QTree trigger and leave Marked QTree trigger enabled you will see the bounds of each Qtree rect as there created and destroyed. The units will gravitate towards the gryphon. Also whenever a unit hits another one of the unit "gets a kill." When that unit dies it spawns as many kills as it gets and only one kill is transferred to the killing unit. You can also specify the type of unit you want. If you choose hpea you will see the phoenix missile model which shows you the trail. opeo is just regular peons.

If you dont run it in debug mode, none of this fun stuff happens. It just emulates everything behind the scenes. When a unit collides with another it creates another one immediately somewhere on the map, so the amount of units remains constant.
Another note: Its a lot of fun to watch peons die =]

#### Attachments

• Qtree.w3x
35.9 KB · Views: 435
• Qtree1.1.w3x
65.5 KB · Views: 485
Okay, I feel unloved because no ones posting any comments =[
But here are some stats that might make people happy =]
With my newest ver(which I haven't posted yet because I'm still looking for improvements),

This is with no units being created, everything is emulated by the code.
O(n^2) Algorithm
* this is with a LITTLE overhead from the system.
(Although my machine is a little too powerful for WC3 so if someone else would like to test this out for me?
If you set testDepth in the test trigger to 0, enable the Qtree trigger and disable marked Qtree, and disable debug mode, you will have the exact case I tested mine under... of course this is after i upload the new version)
Code:
``````50 units 35-50 fps
75 units 2-5 fps``````

O(n*logn) Algorithm, testDepth set to 10
Code:
``````50 units 64 fps
100 units 64 fps
150 units 64 fps
200 units 64 fps
300 units 20-30 fps retest 50 fps
350 units 40 fps
400 units ~10 fps retest 10-20 fps retest #2 ~10 fps``````
A playable 300 units O(n*logn) at 50 fps vs a playable 50 units O(n^2).

Not only that. But the test case I MYSELF chose. (All units are attracted to one point.) is possibly one of the worst cases for a tree. when all the units are evenly distributed around the map, qtrees would be even more efficient.
(why is it worse when there all clumped up? it forces the qtree to stop splitting and causes the nodes to be added on to one node which basically causes a n^2 algorithm again.)

Since the main deal with this is how much more efficient it is for enumerating over close units, you should work at maximizing its efficiency.

Like this should be a struct that extends an array ;P
[ljass]struct nodeList[/ljass]

Also, that should be NodeList ;P.

Also, this should pretty much be a B- Tree shouldn't it? That'd have the same functionality as this w/ more possibilities.

There's also a special tree that's made to specifically deal with spacial coordinates called a kd-tree

http://en.wikipedia.org/wiki/Kd-tree

If you really want to work at doing some great enum stuff, check that stuff out and see how you can improve it.

Further improvements is shortening your variable names to like single and double chars as well as moving them out of the structs and into globals blocks. It really does make a big dif in the stress tests =).

Yeah I haven't done much with struct arrays, but ill check it out.
Yeah its basically a b-tree the only difference being that leaves can stack if necessary but nodes that point to other qtrees have a max of 4 children. Why?
because it makes the split method easy =] but also because I don't see the point in specifying exactly how many trees the root splits into. larger numbers cause a bit of overhead because i have to loop through the children to find where its contained. At a certain point it becomes more efficient to just find the right child mathematically. But because its a linked list, theres no Random access which means i still have to loop through it. Which led me to keeping it at a smaller number, 2 would cause a large number of trees to be created so i made it 4.

The thing with kd tree is that its almost exactly this except you can have k-dimensions. hence kd. However, how often will a collision system in wc3 need to check z height at O(nlogn) efficiency.(plus alot of projectiles would have to share the same xy-space for the efficiency to not be O(nlogn)) the other difference is that kd-trees are also binary in that they split the space by a plane. if there was really a dire need i would consider making it. but it would be very similar to this so may as well perfect this then see whats next =]

Yeah. I've removed all recursive functions in my upcoming release. Are there any other efficiency improvements? algorithmically though lol. shortening variable names is the last thing on my list bc id like to know what my variables mean while im still coding haha.

Thanks for the input though =]

Are you saying syntactically it should be an "extends array" or that making it "extends array" would be better?
Because its not a syntactic error. nodeList defines a start and size so a unique nodeList acts as an array but only allows for it to access values in its range.

I'm saying that [ljass]extends array[/ljass] would be better, and rather than extending off of the struct, you just use a delegate or w/e.

having what extends array would be better? and where do i use a delegate?

Thanks for the info guys.

Ver 1.1 is here!
This is a major/minor update. Its major in that its a big leap from ver 1. But minor in that there are still a lot of improvements I plan on making.
Changes-
• Broke backwards compatability but I don't think thats a big deal because no one uses this... yet =]
• Removed ALL recursive functions(except one that I use for debug purposes.)
• Turned nodeList into nodes and made it extend array.
• Test map has been changed again.
• Some text macros you can use to inline things. (Very minor right now, dont need to use yet. Making more and going to add documentation for them.)
• Ill put up some stats for the next version. Feel free to post FPS's that you get when running this under different stresses.

Infinitedge has not been on in quite awhile, so I'm deeming this as inactive in development.

Please format the post a lot more. It's a mess right now.

Also, please put the code in
JASS:
`````` tags.

Graveyarded.``````

General chit-chat
Help Users
• No one is chatting at the moment.