Infinitegde
O.O
- 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.
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).memberAbout 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
endlibraryNotes:
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 =]
