Inledning
Ett Quad Tree kan ses som en blandning av en algoritm och ett sätt att lagra data. Quad Tree används ofta i spel men kan även användas när man vill indexera två egenskaper.
Vi kommer att presentera en komplett implementation som kan användas i XNA samt ett Windows Forms testprogram. Men först måste vi beskriva det problem som ett Quad Tree attackerar.
Prestandaproblem
Tänk er att vi har 10 objekt i ett 2D-spel som skall undersökas för eventuell kollision varje frame. För att säkerställa kollisionshanteringen så måste första objektet jämföras med de 9 andra. Nästa objekt måste jämföras med 8 andra osv. Totalt ger detta oss (10*9)/2=45 jämförelser.
Endast 10 objekt är inte så roligt. Vi kanske har 50 fiender plus lite projektiler som flyger omkring. Totalt ca 100st objekt som måste undersökas för kollision. Denna gång blir det (100*99)/2=4950 jämförelser varje frame. Fortfarande inget större problem.
Nu vill vi ha ännu fler fiender på banan med ännu fler projektiler samt lite power-ups och liknande som skall kunna plockas upp. Totalt har vi nu 1000 objekt som skall jämföras. Det blir nu (1000*999)/2 = 499500 jämförelser och vi har ett problem! Nu tar kollisionshanteringen ca 100ms att göra på en laptop och vårt spel körs nu i ca 10 fps, nära helt ospelbart.
Vi måste hitta ett smartare sätt att snabbt finna de objekt som ligger så pass nära att vi eventuellt kan kollidera med dem. Det måste finnas ett bättre sätt - Quad Tree.
Fyra delar
Om vi tar spel som ett exempel och åller oss till detta så är det objektens position i x- och y-led som vi ska indexera. Med "indexera" menas att vi ska kunna hitta objekt med ett visst krav på position snabbt.
Ett Quad Tree börjar med en rektangel som inramar det område som är aktuellt. I vårt exempel får det symbolisera banans område. Varje rektangel är en "Quad Tree node", en nod ett ett blivande träd. Varje nod har en lista över de objekt som befinners sig inom rektangeln.
Efter hand som det läggs in fler objekt i trädet så nås en gräns när trädet vill dela på sig i fyra lika stora delar. Därav namnet Quad (=fyra) tree. När trädet delar på sig så sorteras de objekt som befinner sig i rektangeln in i någon av de fyra underliggande noderna som skapas. En nod i trädet kan alltså ha fyra undernoder, varje undernod i sin tur kan ha ytterligare fyra undernoder osv. Se videon nedan.
Gränsen för när trädet ska delas och skapa nya noder är i videon lika med 1. När gränsen överskrids så skapas nya undernoder.
Ett specialfall inträffar då objektet ligger på gränsen mellan två rektanglar och kan inte entydigt läggas in i någon undernod. I detta fall så kommer objektet att ligga kvar i noden och inte läggas in i någon undernod. Se bild nedan.
Trädet
Nu när vi vet lite teori för hur ett Quad Tree fungerar så är det dags att presnetera en implementation. Vi börjar med klassen QuadTree som kommer att bli vår lagringsklass.
Vi kommer att skapa QuadTree som en generisk klass liknande dem som beskrivs i aritkeln Samlingsklasser . Det betyder att vi kommer att kunna lagra vilka sorters objekt vi vill med ett villkor. Objekten som ska lagras måste ha en Rectangle definierad så att vi kan avgöra hur stor plats objektet tar och vart det ska in i trädet. Vi behöver ett interface som vi kallar IHasRectangle.
namespace QuadTreeLib
{
public interface IHasRectangleF
{
RectangleF Rectangle { get; }
}
}
Strukturen RectangleF definierar vi också själva. Anledningen till detta är att XNA inte har en rektangel-klass som använder float. RectangleF bör ha samma egenskaper och metoder som man kan tänka sig en rektangel-klass behöver, bredd, höjd etc. samt metoder för att avgöra överlappning etc.
namespace QuadTreeLib
{
public struct RectangleF
{
float _x;
float _y;
float _width;
float _height;
float _x2;
float _y2;
public RectangleF(float pX, float pY, float pWidth, float pHeight)
{
_x = pX;
_y = pY;
_width = pWidth;
_height = pHeight;
_x2 = pX + pWidth;
_y2 = pY + pHeight;
}
public static RectangleF Empty { get { return new RectangleF(0, 0, 0, 0);} }
public bool IsEmpty
{
get { return _width == 0.0f && _height == 0.0f; }
}
public float X
{
get { return _x; }
set
{
_x = value;
_x2 = _x + _width;
}
}
public float Y
{
get { return _y; }
set
{
_y = value;
_y2 = _y + _height;
}
}
public float Width
{
get { return _width; }
set
{
_width = value;
_x2 = _x + _width;
}
}
public float Height
{
get { return _height; }
set
{
_height = value;
_y2 = _y + _height;
}
}
public float X2
{
get { return _x2; }
}
public float Y2
{
get { return _y2; }
}
public bool Contains(RectangleF rect)
{
return (rect.X >= this.X && rect.Y >= this.Y &&
rect.X2 <= this.X2 && rect.Y2 <= this.Y2);
}
public bool IntersectsWith(RectangleF rect)
{
return (this.X + this.Width >= rect.X && this.Y + this.Height >= rect.Y &&
this.X <= rect.X + rect.Width && this.Y <= rect.Y + rect.Height);
}
}
}
Det är främst metoderna Contains samt IntersectsWith i RectangleF som vi kommer att använda.
Klassen för vårt Quad Tree blir inte så stor. Den mesta logiken kommer att ligga i klassen för noder, QuadTreeNode.
using System;
using System.Collections.Generic;
namespace QuadTreeLib
{
public class QuadTree<T> where T : IHasRectangleF
{
private readonly QuadTreeNode<T> _root;
public QuadTree(RectangleF rectangle, float maxLevels, int splitSize)
{
_root = new QuadTreeNode<T>(rectangle, maxLevels, splitSize);
}
public QuadTree(int x, int y, int width, int height, float maxLevels, int splitSize)
: this(new RectangleF(x, y, width, height), maxLevels, splitSize)
{
}
public int Count { get { return _root.Count; } }
public void Insert(T item)
{
_root.Insert(item);
}
public List<T> FindIntersecting(RectangleF area)
{
List<T> results = new List<T>();
return _root.FindIntersecting(area, results);
}
public List<T> Find(RectangleF area)
{
List<T> results = new List<T>();
return _root.Find(area, results);
}
public void ForEach(Action<QuadTreeNode<T>> action)
{
_root.ForEach(action);
}
}
}
Med nyckelordet where på rad 6 begränsar vi vilken typ av objekt som vi kan lagra. Endast klasser som implementerar IHasRectangle accepteras. Det betyder att alla objekt som lagras kommer att ha egenskapen Rectangle.
När ett QuadTree skapas så måste dels rektangeln anges som beskriver gränserna men också gränsen för hur många objekt som skall lagras innan trädet delar på sig samt hur många nivåer (=levels) som trädet max kan delas i.
Metoder för att lägga till, Insert samt för att hitta objekt inom ett visst område Find behövs. Skillnaden mellan Find och FindIntersecting är att Find returnerar alla objekt som enligt trädet kan kollidera med det givna området medan FindIntersecting utför själva kollisionsdetekteringen också och returnerar endast de objekt som verkligen kolliderar.
Det kan vara som så att vi faktiskt tänker använda oss av en annan metod för kollisionhantering än bara med rektanglar. Då kan det vara onödigt att först göra ett rektangel-test och sedan ytterligare ett test på varje objekt. I vårt exempel kan vi använda Find och FindIntersecting för att visualisera vilka objekt som vi testar (vit färg) och vilka objekt som faktiskt kolliderar (lila färg) med ett visst område (gulmarkerat) . Se bild nedan.
Noden
using System;
using System.Collections.Generic;
namespace QuadTreeLib
{
public class QuadTreeNode<T> where T : IHasRectangleF
{
public RectangleF Bounds { get; private set; }
public List<T> Contents { get; private set; }
protected List<QuadTreeNode<T>> Nodes = new List<QuadTreeNode<T>>(4);
protected int LevelsLeft;
protected int SplitSize;
private bool _hasSplit = false;
public QuadTreeNode(RectangleF bounds, int levelsLeft, int splitSize)
{
_hasSplit = levelsLeft <= 0;
LevelsLeft = levelsLeft;
SplitSize = splitSize;
Contents = new List<T>();
Bounds = bounds;
}
public bool IsEmpty { get { return Bounds.IsEmpty || (Nodes.Count == 0 && Contents.Count == 0); } }
public int Count
{
get
{
int count = 0;
foreach (QuadTreeNode<T> node in Nodes)
count += node.Count;
count += this.Contents.Count;
return count;
}
}
internal void AddSubTreeContents(List<T> results)
{
foreach (QuadTreeNode<T> node in Nodes)
node.AddSubTreeContents(results);
results.AddRange(this.Contents);
}
internal List<T> Find(RectangleF queryArea, List<T> results)
{
results.AddRange(Contents);
foreach (QuadTreeNode<T> node in Nodes)
{
if (node.IsEmpty)
continue;
if (node.Bounds.Contains(queryArea))
{
node.Find(queryArea, results);
break;
}
if (queryArea.Contains(node.Bounds))
{
node.AddSubTreeContents(results);
continue;
}
if (node.Bounds.IntersectsWith(queryArea))
{
node.Find(queryArea, results);
}
}
return results;
}
internal List<T> FindIntersecting(RectangleF queryArea, List<T> results)
{
foreach (T item in this.Contents)
{
if (queryArea.IntersectsWith(item.Rectangle))
results.Add(item);
}
foreach (QuadTreeNode<T> node in Nodes)
{
if (node.IsEmpty)
continue;
// Fall 1
if (node.Bounds.Contains(queryArea))
{
node.FindIntersecting(queryArea, results);
break;
}
// Fall 2
if (queryArea.Contains(node.Bounds))
{
node.AddSubTreeContents(results);
continue;
}
// Fall 3
if (node.Bounds.IntersectsWith(queryArea))
{
node.FindIntersecting(queryArea, results);
}
}
return results;
}
public void Insert(T item)
{
if (!Bounds.Contains(item.Rectangle))
return;
if (!_hasSplit)
{
if (Contents.Count < SplitSize)
{
Contents.Add(item);
return;
}
else
{
// Kommentar 1
CreateSubNodes();
var tmpArray = Contents.ToArray();
Contents.Clear();
foreach (var i in tmpArray)
this.Insert(i);
}
}
// Kommerntar 2
foreach (QuadTreeNode<T> node in Nodes)
{
if (node.Bounds.Contains(item.Rectangle))
{
node.Insert(item);
return;
}
}
// Kommentar 3
this.Contents.Add(item);
}
public void ForEach(Action<QuadTreeNode<T>> action)
{
action(this);
// draw the child quads
foreach (var node in this.Nodes)
node.ForEach(action);
}
private void CreateSubNodes()
{
_hasSplit = true;
if (LevelsLeft <= 0)
return;
float halfWidth = (Bounds.Width / 2f);
float halfHeight = (Bounds.Height / 2f);
Nodes.Add(new QuadTreeNode<T>(new RectangleF(Bounds.X, Bounds.Y, halfWidth, halfHeight), LevelsLeft - 1, SplitSize));
Nodes.Add(new QuadTreeNode<T>(new RectangleF(Bounds.X, Bounds.Y + halfHeight, halfWidth, halfHeight), LevelsLeft - 1, SplitSize));
Nodes.Add(new QuadTreeNode<T>(new RectangleF(Bounds.X + halfWidth, Bounds.Y, halfWidth, halfHeight), LevelsLeft - 1, SplitSize));
Nodes.Add(new QuadTreeNode<T>(new RectangleF(Bounds.X + halfWidth, Bounds.Y + halfHeight, halfWidth, halfHeight), LevelsLeft - 1, SplitSize));
}
}
}
Noden skapas med ett angivet område, en indikation på hur många nivåer det är kvar samt en nivå som bestämmer när noden skall delas upp. Det är inte säkert att det ska skapas några nya noder, det beror helt på om det finns några nivåer kvar att skapa. Därför sätts _hasSplit redan som nivåerna kvar är 0 eller under. I detta fall kommer noden att vara delad men sakna undernoder.
Om noden inte har delats (_hasSplit) så läggs objekten bara i Contents-listan (rad 124).
Kommentar 1: Skulle man nått gränsen för när det är dags att dela noden så anropas CreateSubNodes. Nu måste alla objekt i noden sorteras in igen, detta görs genom att rekursivt anropa Insert. Noden kommer nu att vara delad och insättningen fortsätter.
Kommentar 2: Om vi hittar en subnod som rymmer objektet så lägger vi till i denna subnod och återvänder.
Kommentar 3: Hit kan vi komma av två anledningar. Först att ingen subnod rymmer objektet helt, dvs. objektet överlappar två eller fler subnoder. Den andra anledningen är att det inte finns några subnoder. Vi har nått lägsta nivån i trädet. Oavsett anledning så läggs objektet in i Content-listan för noden.
Om vi instället tittar på FindIntersecting som fungerar ungefär som Find så börjar vi med att jämföra alla objekt som finns i nodens lista på rad 80. Objekt som kolliderar med sökområdet läggs i den lista för resultat som har skickats med sedan rot-noden i QuadTree. Utöver detta så finns det 3 fall för varje subnod som måste undersökas.
Fall 1: Sökområdet ryms helt i en subnod. Anropa subnodens FindIntersecting och avbryt sedan loop'en genast.
Fall 2: Subnoden ryms helt i sökområdet. Alltså det motsatta till fall 1. Nu måste alla objekt i subnoden läggas till resultatet.
Fall 3: Om sökområdet delvis skär en subnod så måste sökningen fortsätta i subnoden. Loop'en måste också fortsätta då sökområdet kan skära fler subnoder i noden.
Prestanda
Tester gjorda med exempelprogrammet ger att kollisionsdetektering med 1000 objekt itererat över en vanlig lista tar ca 95ms att genomföra. Använder vi Quad Tree så tar samma operation endast 9ms. En faktor 10 bättre! Då användes ett träd med djupet 5, alltså MaxLevels = 5.
Ökar vi till 10000 objekt så får vi en tid på hela 7236ms vilket inte riktigt är en faktor 100 sämre jämfört med 95ms men följer ungefär det förväntade ordo, O(n 2 ). Motsvarande för Quad Tree gav 330ms men än en faktor 20 bättre!
Enligt litteraturen så ska ett Quad Tree prestera enligt O(n*log2 n) i bästa fall. Med bästa fall menas att objekten är jämt fördelade samt inte ligger mellan några rektanglar. Enligt denna modell borde vi fått ca 2ms på 1000 objekt, en faktor 50 bättre och med 10000 objekt skulle det blivit en faktor 370 bättre. Alltså ligger vi inte i närheten av bästa fallet.
Samtidigt skall vi inte glömma att sämsta fallet för Quad Tree är identiskt med O( n2 ). Vi hamnar någonstans mittemellan av flera orsaker. Vi har många objekt som ligger tätt samt gränsar över flera rektanglar. Samtidigt kan vi inte heller utesluta att vi gjort någon prestandamiss i vår implementation. Ökar vi avståndet mellan
Avslutning
Vi avslutar enkelt med att önska lycka till och hoppas att du kanske får nytta av ett Quad Tree någon gång. Koden samt exempelprogrammet hittar du nedan. Använd högerknappen på musen för att markera ett område.
Ordet spatiell, vad hade det med saken att göra? Jo ordet betyder "rum" och hur ett objekt förhåller sig till ett annat rent "rumsligt", t.ex. avståndsmässigt.