Snippet QTree

Reaction score
86
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.

addToQtree(Qtree)-
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.
Code:
MYSTRUCT(QT_nodes[x].n).member

About the Depth:
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.

//addToQtree(Qtree)-
//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...
//=================================================================
//About the Depth:
//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
        method getNodesRadius takes integer radius returns integer
            local Qtree qt =.root
            loop
            exitwhen qt.root==-1
                if(radius<qt.r-qt.x and radius<qt.b-qt.y)then
                    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
                debug call BJDebugMsg("Qtree:Node not added!")
                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 call BJDebugMsg("Node not added!")
                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
                exitwhen this.addToQtree(qt)
                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
                if(not (lt.sureAdd(temp) or rt.sureAdd(temp) or lb.sureAdd(temp) or rb.sureAdd(temp)))then
                    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.
 
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.

      The Helper Discord

      Staff online

      Members online

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top