michi's log

Recently I am very interested in creating a small game for Android. Since every game needs a proper working gameloop and a underlying drawing mechanism I started to look at some examples from the internet. My first attempt in searching a good example lead me to the Android Developers page. There is a good description on how to get started with 2D graphics. I decided to take the threaded aproach as described there. This means that there is a thread that draws everything into the view as fast as possible while not blocking the UI thread.

Some further poking on the Android Developers page lead me to the Lunar Lander example which looked right what I wanted to do. I installed it on my HTC and played around with it a bit when I suddenly received this error message:

What happened? To put it simple, there is a bug in Google’s Lunar Lander example. Let’s look at the implemenation of the thread that draws the game in LunarView.java and how it’s started:

1
2
3
4

public void surfaceCreated(SurfaceHolder holder) {
	thread.setRunning(true);
	thread.start();
}

The method surfaceCreated() is a callback method from the SurfaceHolder class. It is called whenever the Surface we want to draw on is created, for example when the application starts or when we return from a pause. Respectivly the method surfaceDestroyed() is called whenever the surface is destroyed, for example when the application terminates or another application gets the focus.

1
2
3
4
5
6
7
8
9
10
11

public void surfaceDestroyed(SurfaceHolder holder) {
	boolean retry = true;
	thread.setRunning(false);
	while (retry) {
		try {
			thread.join();
			retry = false;
		} catch (InterruptedException e) {
		}
	}
}

In the Lunar Lander implemention the drawing thread is terminated on the first time the surface is destroyed. If we then try to come back to the application, for example with a long click on the home button, the application throws this exception:

java.lang.IllegalThreadStateException: Thread already started.

We reached an illegal state because a thread is only allowed to be started a single time!

To fix this issue I don’t stop the drawing thread in my application if the app looses focus. Instead I just stop drawing and let the thread sleep for a while (and thus save the CPU resources etc). When the app gets focus again, the drawing starts over. In the example below this behaviour is controlled by the paused variable, running is the variable that is set to true when the game starts and is set to false when the app is terminated and the thread really needs to stop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

@Override
public void run() {
	while (running) {
		while (paused) {
			try {
				Thread.sleep(50L);
			} catch (InterruptedException ignore) {
			}
		}
 
		Canvas canvas = null;
		try {
			canvas = holder.lockCanvas(null);
			draw(canvas);
		} finally {
			if (canvas != null) {
				holder.unlockCanvasAndPost(canvas);
			}
		}
	}
}

I’ve implemented this gameloop in a small example that displays Conway’s Game of Life:

Of course my implementation has a fixed timestep as suggested by the famous article Fix Your Timestep!

Download my example sourcecode here: android-gameloop-example-v1.zip
App in the Android Market: Gameloop Tutorial

In my current project I make heavy use of logging. To be able to customize logging I am using log4j. Unfortunately LWJGL doesn’t use a log framework of any kind and just outputs on the console via System.out.println(). To add these outputs to the logfile or a log4j console appender one has to reroute the output through log4j. Luckily there is a pretty easy way, I found it in a stackoverflow posting. So how does it work? There is a Java API that allows to set a new PrintStream for System.out and System.err:

1
2

System.setOut(PrintStream stream);
System.setErr(PrintStream stream);

So we simply have to add our own PrintStream implementation that calls the logger and we are done:

1
2
3
4
5

new PrintStream(realPrintStream) {
    public void print(final String message) {
        LOG.info(message);
    }
}

LOG would be our log4j Logger.

In Eclipse there is this wonderful little helper for adding Javadoc links while you’re typing a class name. It looks like this:

It suggests not just to put the classes name there but also use a @link tag so one can navigate the Javadoc sources later on. The finished comment:

Unfortunately this functionality is not available in JetBrains’ IntelliJ Idea. There is (of course) auto completion for classnames in Idea but it simply doesn’t put them in a @link tag. A simple trick saves the day: simply create a live template with context ‘Java comment’ like here:

EDIT: The screenshot is missing the word ‘link’. The complete template should be: ‘{@link $LINK$} ‘.

Don’t forget to click on ‘Edit variables’ and fill in ‘complete()’ as Expression. This activates the auto completion for classnames.

Now everytime a @link in the Javadocs is needed we invoke the Live Templates with Alt + J and enter a classname. The @link tag will be build around that name. It’s not as simple as with Eclipse, but works pretty well.

“Immediate mode rendering is dead” is the title of a topic on the Javagaming Forums I’ve been following the last two days. It is a really insightfull discussion about the use of Vertex Buffer Objects versus Vertex Arrays and the Immediate Mode.
One says the internet doesn’t forget and that is especially true for tutorials concerning OpenGL which have been around for a very long time now. Most of them start by showing how to draw simple geometry using the Immediate Mode and most people posting in the mentioned topic agree that this is the wrong thing to start learning with, at least nowadays.
The topic also includes some example code and benchmarking what methods and ways seem to be the fastest. The contributers just started comparing benchmarks and didn’t go very deep, but I really hope that there will be deeper insights revealed.
The whole discussion actually started here: Sprite!, where princec (from Puppygames) is writing about his sprite-engine. Also a very interesting read!

It has been a while since I last used Vertex Buffer Objects (VBO) with LWJGL. It seemed as if they had changed some of the method signatures since I used them last time. I couldn’t even get the simplest example running. After experimenting for a while I finally figured it out. Have a look at the signature of the VertexPointer method:

static void glVertexPointer(int size, int type, int stride, long pointer_buffer_offset);

With the last offset one can specify where the vertex information starts in the buffer given to the VBO management. Well, I could/should have guessed that this offset has to be in bytes since I am dealing with a buffer here but instead I used the number of floats.. So next time I see an operation dealing with buffers that takes a long argument I’ll try the byte-count from the beginning..

Shaderprogrammierung in GLSL, der Shadersprache unter OpenGL, war bisher ein Buch mit sieben Siegeln für mich. Aber da man ja alles lernen kann habe ich mich auf die Suche nach Tutorials gemacht und auch einige sehr gute entdeckt. Die Einführung von Lighthouse3d ist zum Beispiel sehr zu empfehlen. Hier wird wirklich mit den Grundlagen angefangen und erstmal eine Beschreibung geliefert wie die Pipeline der Grafikkarten aufgebaut sind und wo genau die verschiedenen Shader zum Einsatz kommen.

Natürlich muss man die geschriebenen (oder abgetippten) Shader auch irgendwie ausprobieren. Hier fand ich das Programm ShaderDesigner von Typhoon Labs ganz brauchbar. Leider scheint es die Firma nicht mehr zu geben, aber sowohl ShaderDesigner als auch ein ebenfalls super geschriebenes Tutorial für Shader lassen sich nach wie vor von der Seite runterladen.

Schließlich habe ich mich daran gemacht, die Shader auch in einem wirklichen Programm einzusetzen. Hierfür verwende ich die “Light Weight Java Games Library” (LWJGL), meinem Lieblingsbinding von OpenGL an Java. Es stellte sich heraus, dass wenn man mal einen funktionierenden Shader hat, diesen wirklich einfach in ein Programm einbinden kann. Wirklich geholfen hat mir der entsprechende Wikieintrag im LWJGL Wiki. Am besten speichert man Vertex- und Fragmentshader in einer Textdatei und legt sie irgendwo im Projektverzeichnis ab. Im Programm werden die Dateien dann mit ganz gewöhnlichen Hausmitteln erstmal geöffnet und in einem Bytearray gespeichert. Dies muss natürlich sowohl für Vertex- als auch für Fragmentshader passieren:

1
2
3
4
5
6
7
8
9
10
11

ClassLoader loader = ShaderTest.class.getClassLoader();
InputStream is = loader.getResourceAsStream(shadername);
byte[] shadercode = null;
try {
    DataInputStream dis = new DataInputStream(is);
    dis.readFully(shadercode = new byte[is.available()]);
    dis.close();
    is.close();
} catch (IOException e) {
    System.out.println(e.getMessage());
}

Anschließend werden die Bytearrays in einen ByteBuffer kopiert, den LWJGL lieber mag:

1
2
3

ByteBuffer shader = BufferUtils.createByteBuffer(shadercode.length);
shader.put(shadercode);
shader.flip();

Nicht vergessen die Buffer zu flippen!
Anschließend teilen wir OpenGL mit, dass wir zwei neue Shaderobjekte brauchen. Dies funktioniert genau wie wenn man eine Textur anlegt: Man teilt OpenGL mit, was man haben will und bekommt ein int zurück, mit dem man das neue Objekt referenzieren kann:

1
2
3
4

int vertexShaderID = ARBShaderObjects.glCreateShaderObjectARB(
ARBVertexShader.GL_VERTEX_SHADER_ARB);
int pixelShaderID = ARBShaderObjects.glCreateShaderObjectARB(
ARBFragmentShader.GL_FRAGMENT_SHADER_ARB);

Nachdem die entsprechenden Objekte nun OpenGL bekannt gemacht wurden müssen wir OpenGL nun mitteilen was die Shader genau machen sollen, sprich deren Quellcode übergeben. Danach werden die Shader kompiliert:

1
2
3
4
5

ARBShaderObjects.glShaderSourceARB(vertexShaderID, vertexShader);
ARBShaderObjects.glCompileShaderARB(vertexShaderID);
 
ARBShaderObjects.glShaderSourceARB(pixelShaderID, pixelShader);
ARBShaderObjects.glCompileShaderARB(pixelShaderID);

vertexShader und pixelShader sind die Variablen, die auf die ByteBuffer zeigen und den eingelesenen Quelltext enthalten.
Die beiden Shader werden nun zu einem Programm zusammengebunden. Ein Programm wird dabei ebenso wie ein Shaderobjekt erstellt: bei einem Methodenaufruf erhalten wir ein int mit dem wir das Programm in Zukunft referenzieren. Hat man nur einen Vertex- oder nur einen Fragmentshader zur Hand wird der jeweils andere Teil von OpenGL durch eine Standartimplementierung ersetzt. Zum Schluß werden die Teile ähnlich einem C Programm zusammengebunden.

1
2
3
4

int shaderProgramID = ARBShaderObjects.glCreateProgramObjectARB();
ARBShaderObjects.glAttachObjectARB(shaderProgramID, vertexShaderID);
ARBShaderObjects.glAttachObjectARB(shaderProgramID, pixelShaderID);
ARBShaderObjects.glLinkProgramARB(shaderProgramID);

Jetzt sind wir fertig und können den Shader beim Rendern benutzen. Hierzu ruft man im Renderloop bevor das Objekt das den Shader erhalten soll gezeichnet wird die folgende Methode auf

1

ARBShaderObjects.glUseProgramObjectARB(shaderProgramID);

Wird anstatt einem Shaderprogramm “0″ übergeben benutzt OpenGL die Standarteinstellungen (fixed Pipeline) zum Rendern.

Ein kleiner Test mit einem Toon-Shader aus dem Lighthouse Tutorial sieht dann zum Beispiel so aus:

Die Veränderung der Farbe des 3d Modells hängt nicht mit dem Licht zusammen sondern wird im Fragmentshader verursacht. Hierzu wird eine Variable vom Javaprogramm aus an den Shader übergeben, die die Zeit seit dem Beginn der Anwendung übergibt. Im Fragmentshader ist die Variable so definiert:

1

uniform float TIME_SINCE_INIT;

Bei jedem Durchlauf des Renderloops wird diese Variable vom Javaprogramm neu geschrieben. Um den Schreibvorgang durchzuführen wird vorher die Location der Variable bestimmt. Dazu wird OpenGL der mit 0 terminierte Name der Variablen übergeben. Existiert diese, dann liefert OpenGL eine Location in Form eines Integers zurück und man kann mit einem glUniform1fARB-Aufruf den Wert übergeben.

1
2
3
4
5
6
7
8

ByteBuffer buff = BufferUtils.createByteBuffer(
    "TIME_SINCE_INIT".length()+1);
buff.put( "TIME_SINCE_INIT".getBytes() );
buff.put((byte)0);
buff.flip();
int location = ARBShaderObjects.glGetUniformLocationARB(
    shaderProgramID, buff);
ARBShaderObjects.glUniform1fARB(location, gameLogicTimer.getTime());

Beim Stöbern durch die Bibliotheken von ACM bin ich auf folgenden Artikel gestoßen: Computer games as motivation for design patterns. Paul V. Gestwicki beschreibt darin wie er mit Hilfe eines Computerspiels seine Studenten motiviert sich mit Design Patterns zu beschäftigen. Obwohl man ja gerade bei Spielen oft darauf aus ist noch die letzten FPS aus dem Code herauszuquetschen lohnt es sich doch nicht allen Code auf Performance auszulegen, sondern einen strukturierten Ansatz zu verfolgen. Die Vorteile liegen auf der Hand: Der Code wird lesbarer, leichter wartbar und besser erweiterbar.

Das erste Design Pattern in seinem Paper ist das State Pattern. Anhand einer Sprite Klasse, die zuständig für das Aussehen, die Größe und Position des Spielers ist, erläutert er das Pattern. Der Spieler kann sich in mehreren Zuständen(=States) befinden und das Verhalten der Sprite Klasse ändert sich mit jedem Zustand. Eine naive Implementation würde jedem Zustand einen int-Wert geben und dann in einer update() Methode später einen großen switch-Block durchlaufen in dem jedes Verhalten in jedem Zustand beschrieben ist.

Im Buch Design Patterns von Gamma et. al. wird jedoch genau dies als Grundlage der Anwendbarkeit des State Pattern angegeben:

• An object’s behavior depends on its state, and it must change its behavior at run-time depending on that state
• Operations hve large, multipart conditional statements that depend on the object’s state. This state is usually represented by one or more enumerated constants.

Wie sieht nun so ein State Pattern aus? Zu allererst brauchen wir ein Interface, dass einen Zustand beschreibt:

1
2
3
4
5
6

public interface State {
public void install();
public void uninstall();
public void draw();
public void update();
}

Die Spieler Klasse muss nun eine Variable vom Typ State besitzen mit der angegeben wird in welchem Zustand der Spieler sich gerade befindet. Außerdem müssen alle Aufrufe die den Zustand des Spielers betreffen an die State-Implementation deligiert werden. Skizzenhaft sieht der Spieler dann so aus:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Spieler{
State aktuellerZustand;
 
...
 
public void update(){
aktuellerZustand.update();
}
 
public void draw(){
aktuellerZustand.draw();
}
 
...
}

Was nun noch fehlt sind tatsächliche Implementationen des State-Interfaces. Hier hat man mehrere Möglichkeiten. Zum einen kann man innere anonyme Klassen verwenden:

1
2
3
4
5
6
7
8

//Konstruktor
public Spieler(){
aktuellerZustand = new State(){
public void install(){...};
public void uninstall(){...};
public void update(){...};
public void draw(){...};
}

oder man verwendet einfache innere Klassen, d.h. in der Spieler Klasse werden weitere Klassen definiert die jeweils das State Interface implementieren. Beides hat den Vorteil, dass man die Logik und das Verhalten des Spielers sehr nahe am Spieler selbst hat. Die inneren Klassen können auf Variablen der äußeren Zugreifen und so mit dem Spieler interagieren. Weiterhin verbirgt man die konkreten Zustände vor der Außenwelt.

Das Spieler Objekt könnte nun selbst entscheiden wann es welchen Zustand braucht, einfacher und manchmal auch schöner ist es jedoch die Zustände selbst entscheiden zu lassen. Hierfür gibt es die Methoden install() und uninstall(), die einen Übergang von einem zum anderen Zustand erlauben indem sie einfach die State Variable des Spielers neu setzen. Denkbar ist natürlich auch, dass in diesen Methoden spezielle Animationen für die Übergänge ausgelöst werden usw.

Im Moment arbeite ich an einem kleinen Spiel und hier sind die ersten Screenshots:

Geplant ist ein 2D Spiel mit 3D Grafiken. Auf den Bildern kann man leider nicht sehen, dass die Asteroiden sich drehen und das kleine Raumschiff von ihnen abprallt. Das Asteroidenfeld ist prinzipiell unendlich groß.. jedesmal wenn man einen Teil verlässt wird ein gerade unsichtbarer Teil in Flugrichtung kopiert, sodass der Eindruck entsteht es würde nie aufhören. Tatsächlich besteht es aus nur 650 Asteroiden.
Sobald ich die Steuerung fertiggestellt habe gibt es ein Video..
Als Engine benutze ich die java MonkeyEngine jME mit Physikerweiterung.

In meinem letzten Blog Eintrag habe ich ein einfaches Beispiel eines Quadtrees gezeigt und wie er generell aufgebaut ist. Diesesmal will ich eine einfache Quadtree Implementation vorstellen. Zu Anfang muss aber gesagt werden, dass es Quadtrees wie Sand am mehr gibt und jeder ein wenig anders ist als die Anderen. Bei Quadtrees gibt es nur eine grobe Vorstellung wie er auszusehen hat und nicht “den einen” Quadtree aus dem Lehrbuch.

Je nach Anwendung wird der Quadtree einfacher oder komplizierter ausfallen. Zum Beispiel ist ein Quadtree der eine statische Landschaft unterteilt damit schnell entschieden werden kann welche Teile wirklich gezeichnet werden müssen relativ simpel. Es braucht nicht unbedingt eine Methode die neue Objekte einfügt oder eine andere die Objekte löscht. Schwieriger wird es wenn der Quadtree eine Szene repräsentiert in der sich Objekte bewegen können. Hier kann es schnell vorkommen, dass ein Objekt einen der Knoten verlässt und zu einem anderen hinzugefügt werden muss. Genau diesen Fall, also eine dynamische Szene von Objekten, möchte ich hier vorstellen. Man kann sich natürlich streiten ob sich ein Quadtree für solche nicht-statischen Szenen eignet, aber ich denke ein Versuch ist es wert.

Angefangen habe ich mit einer einfachen Klasse, die lediglich eine Box repräsentiert in der alle Objekte eines Knotens liegen sollen:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

public class BBox {
    /** 4 edges in counterclockwise order, beginning top right */
    public float [][] bounds;
    public float width;
    public float height;
    public float centerX;
    public float centerY;
 
    public BBox(float [][] bounds) {
        this.bounds = bounds;
 
        this.width = bounds[0][0] - bounds[1][0];
        this.height = bounds[1][1] - bounds[2][1];
        this.centerX = bounds[1][0] + width/2f;
        this.centerY = bounds[2][0] + height/2f;
    }
 
    public BBox(float centerX, float centerY, float width, float height){
        bounds = new float[4][2];
        bounds[0][0] = centerX + width/2f;
        bounds[0][1] = centerY + height/2f;
        bounds[1][0] = centerX - width/2f;
        bounds[1][1] = centerY + height/2f;
        bounds[2][0] = centerX - width/2f;
        bounds[2][1] = centerY - height/2f;
        bounds[3][0] = centerX + width/2f;
        bounds[3][1] = centerY - height/2f;
 
        this.centerX = centerX;
        this.centerY = centerY;
        this.width = width;
        this.height = height;
    }
 
    /**
     * Check if two BBoxes overlap
     * @param bbox1 first BBox
     * @param bbox2 second BBox
     * @return  1 if bbox2 is completly inside bbox 1
     *          0 if the boxes overlap
     *          -1 if the boxes don't overlap
     */
    public static int overlap(BBox bbox1, BBox bbox2){
        boolean overlapX = false;
        boolean overlapY = false;
        boolean insideX = false;
        boolean insideY = false;
 
        //check if bbox2.left is overlapping with bbox1 (in x dimension)
        if( isInside(bbox1.bounds[1][0], bbox1.bounds[0][0], bbox2.bounds[1][0])){
            overlapX = true;
            //check if bbox2.right is overlapping with bbox1 (in x dimension)
            if( isInside(bbox1.bounds[1][0], bbox1.bounds[0][0], bbox2.bounds[0][0]) ){
                //since left and right bbox2 is inside, the whole bbox2 is inside bbox1
                insideX = true;
            }
        }else{
            if( isInside(bbox1.bounds[1][0], bbox1.bounds[0][0], bbox2.bounds[0][0]) ){
                overlapX = true;
            }
        }
 
        //if overlapX is still false, we can return that the boxes dont overlap
        if(!overlapX) return -1;
 
        //do the same as above for y dimension
        //check if bbox2.up is overlapping with bbox1 (in y dimension)
        if( isInside(bbox1.bounds[2][1], bbox1.bounds[1][1], bbox2.bounds[1][1])){
            overlapY = true;
            //check if bbox2.down is overlapping with bbox1 (in y dimension)
            if( isInside(bbox1.bounds[2][1], bbox1.bounds[1][1], bbox2.bounds[2][1]) ){
                //since up and down bbox2 is inside, the whole bbox2 is inside bbox1
                insideY = true;
            }
        }else{
            if( isInside(bbox1.bounds[2][1], bbox1.bounds[1][1], bbox2.bounds[2][1]) ){
                overlapY = true;
            }
        }
 
        if(!overlapY) return -1;
 
        if(insideX && insideY) return 1;
        else return 0;
    }
 
    /** just a little helper */
    private static boolean isInside(float left, float right, float test){
        if(test < right && test >= left) return true;
        else return false;
    }
 
}

Hier passiert keine Magie, das Array bounds enthält einfach die vier Eckpunkte der Box und es gibt einen Konstruktor der die Box Objekte initialisiert. Die Methode overlap ist statisch und wird benötigt um festzustellen ob sich zwei Boxen überschneiden, eine in der anderen enthalten ist oder ob sich beide nicht berühren. Später werden genau damit die Tests durchgeführt ob ein Objekt noch in einem Knoten des Quadtrees ist oder ihn schon verlassen hat. Die Methode ist in keiner Weise optimiert und implementiert nur den ersten Gedanken den ich zu dieser Box “Kollisionserkennung” hatte.

Als nächstes folgt die Klasse Quadtree in der ich alle Schnittstellen festlege, die ich brauche um mit meinem Quadtree zu arbeiten.

1
2

private QuadtreeElement root;
private ArrayList elements;

Zuallererst definiere ich mir ein Wurzelknoten an dem alle weiteren Knoten des Quadtrees hängen. Ich habe die Knoten des Baumes hier QuadtreeElement genannt, aber das spielt im Endeffekt keine Rolle. Eigentlich könnte man auch die ganze Quadtreeklasse weglassen und einfach die Schnittstellen der QuadtreeElements benutzen, aber ich fand es schöner das nochmal zu kapseln. In Zeile zwei halte ich noch ein ArrayList mit allen QuadtreeElements die im Baum vorkommen. Das ist eigentlich auch nicht nötig, erspart einem aber manchmal unnötige Sucherei auf dem Baum. Der Nachteil ist natürlich, dass jede Änderung am Baum auch in dieser Liste vollzogen werden muss.
Um vernünftig mit dem Quadtree arbeiten zu können fehlen noch ein paar Methoden:

1
2
3
4

public void addObject(Testobject o){
     root.addObject(o);
     root.update();
}

addObject fügt unserem Quadtree ein neues Objekt hinzu. In diesem Fall rufen wir nur die Methode addObject des Wurzelelements und danach update. Diese beiden Methoden sorgen dafür, dass das Objekt erst einmal im Wurzelknoten gespeichert wird. Update prüft dann im zweiten Schritt ob es möglich ist dieses Objekt in tiefere Schichten des Baumes einzusortieren. Wie das genau funktioniert sehen wir später.

Da die Szene von Objekten dynamisch sein soll brauchen wir eine Möglichkeit festzustellen wann wir überprüfen müssen ob auch alle Objekte noch in den QuadtreeElementen sind in denen sie sein sollten. Sprich wir müssen Testen ob sich die Objekte bewegt haben seit dem letzten Methodenaufruf. Die Methode update macht genau dies.

1
2
3
4
5
6
7
8
9
10
11
12
13

     public void update(){
        //go through all QuadtreeElement and check if their objects have changed
        for(int j = 0; j < elements.size(); j++){
            QuadtreeElement n = elements.get(j);
            for(int i = 0; i < n.payload.size(); i++){
                if(n.payload.get(i).hasMoved()){
                    n.markDirty();
                    break;
                }
            }
        }
        root.update();
    }

Diese Methode macht von der eingangs erwähnten Liste von QuadtreeElements gebrauch indem sie einfach alle Elemente durchgeht und jedes gespeicherte Objekt in dem Element fragt ob es sich bewegt hat. An dieser Stelle gibt es auch einen Knackpunkt im Design mit dem ich nicht glücklich bin: Jedesmal bevor das nächste Bild gezeichnet werden kann gehe ich hier alle Elemente durch und überprüfe ob sie ein update brauchen oder nicht. Eigentlich wäre es schöner wenn die Objekte die ich im Baum verwalte von selbst mitteilen würden wenn und ob sie sich bewegt haben, doch dann müsste jedes Objekt wiederum den Quadtree kennen, was ich eigentlich vermeiden wollte. Falls jemand eine gute Idee hat: nur her damit.
Falls ein Objekt gefunden wird, dass sich seit dem letzten mal bewegt hat müssen wir auf alle Fälle prüfen ob es sich noch im richtigen QuadtreeElement befindet, oder ob es dies verlassen hat. Wir prüfen das später in der update Methode der QuadtreeElemente. Um jedoch zu vermeiden, dass wir ein Update an jedem Element aufrufen markieren wir die Elemente die tatsächlich ein update brauchen. Das geschieht mit der Methode markDirty. In der letzten Zeile der obige update Methode wird der tatsächliche Updatevorgang eingeleitet in dem wir wiederum Update am Wurzelelement aufrufen. Wie wir später sehen ruft das Wurzelelement dann rekursiv alle update Methoden der Kinderelemente auf die als dirty markiert sind.

Das waren die wichtigsten Methoden die wir brauchen um einen Quadtree aufzubauen. Nun kommen wir zu den eigentlichen Baumelementen, den QuadtreeElements:

1
2
3
4
5
6
7
8
9
10
11

private QuadtreeElement parent;
private QuadtreeElement[] childs;
private BBox bbox;
public  ArrayList payload;
private int depth;
private boolean dirty;
private Quadtree tree;
 
private static final int MAX_OBJECT_NUM = 2;
private static final int MIN_OBJECT_NUM = 1;
private static final int MAX_DEPTH = 5;

Zu Beginn definieren wir einige Konstanten die wir brauchen um das Verhalten des Baumes zu steuern. MAX- und MIN_OBJECT_NUM gibt an wie viele Objekte in einem QuadtreeElement sein dürfen bevor es in vier kleinere Teile aufgesplittet wird bzw. was die minimale Anzahl an Objekten ist bevor ein QuadtreeElement gelöscht wird und die Objekte eine Ebene nach oben verschoben werden. Weiterhin haben wir Referenzen auf die Elemente über und unter dem aktuellen Element und auf eine Box die die Grenzen des Elements angibt. payload ist schliesslich eine ArrayList die die eigentlichen Objekte enthält die wir im Baum verwalten wollen. TestObject ist eine Klasse die das Interface QuadtreeConnector implementiert. Dieses Interface wiederum hat nur eine Methode: hasMoved. Wie oben beschrieben brauchen wir genau diese Methode um festzustellen ob ein Objekt im Baum (und damit natürlich das entsprechende QuadtreeElement) ein Update benötigt.

Es gibt fünf wichtige Methoden in einem QuadtreeElement: addObject, update, markDirty, pushup und pushdown.

Zum einfachen Verständnis nehmen wir einfach mal an, wir wollen ein Testobject dem Quadtree hinzufügen. Wir wissen schon dass die addObject Methode des Quadtrees addObject des Wurzelelements aufruft und danach update. AddObject der QuadtreeElements sieht so aus:

1
2
3
4
5

public void addObject(Testobject o) {
    //add the new object to the payload and mark the quadtreeElement as dirty
   payload.add(o);
   markDirty();
}

Wir fügen das Testobject einfach dem Wurzelelement hinzu indem wir es an die payload Arrayliste anhängen. Danach wird dieses Element als dirty markiert und der nächste Aufruf von update wird entscheiden ob das Testobjekt weiter nach unten im Baum verschoben wird.

markDirty ist eine recht einfache rekursive Funktion, die einfach alle QuadtreeElemente vom eigenen an bis zum rootElement als dirty markiert:

1
2
3
4
5

public void markDirty(){
    this.dirty = true;
    if(parent != null && parent.dirty == false)
        parent.markDirty();
}

Als nächstes wird die Update Methode aufgerufen:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

    public void update(){
        //if this quadtreeElement is not dirty, none of its successors is, so return
        if(!dirty) return;
        //update recursivly all nodes with a dirty flag
        if(childs != null){
            for(int i = 0; i = 0; i--){
            int res = BBox.overlap(bbox, payload.get(i).box);
            if( res == 0 || res == -1){
                //the object overlaps or is completly outside the node -> push it up
                pushup(payload.remove(i));
            }
        }
 
        //all objects that are overlaping or outside the quadtreeElement boundaries are now
        //in the parent quadtreeElement, so time for a pushdown of those that can get deeper
        pushdown();
 
        //if we abandoned a subtree we remove it
        if(getChildObjectCount() == 0 && childs != null){
            tree.removeNode(childs[0]);
            tree.removeNode(childs[1]);
            tree.removeNode(childs[2]);
            tree.removeNode(childs[3]);
            childs = null;
        }
 
        //if the subtree and current quadtreeElement contain less or equal than MAX_OBJECT_NUM
        //put all objects into the actual quadtreeElement and delete the subnodes
        if(payload.size() + getChildObjectCount() = 1 && childs != null){
            for(int i = 0; i < 4; i++){
                for(int j = 0; j  MAX_OBJECT_NUM && depth < MAX_DEPTH && childs == null){
        childs = new QuadtreeElement[4];
        BBox b1 = new BBox(bbox.centerX + bbox.width/4f, bbox.centerY + bbox.height/4f, bbox.width/2f, bbox.height/2f);
        BBox b2 = new BBox(bbox.centerX - bbox.width/4f, bbox.centerY + bbox.height/4f, bbox.width/2f, bbox.height/2f);
        BBox b3 = new BBox(bbox.centerX - bbox.width/4f, bbox.centerY - bbox.height/4f, bbox.width/2f, bbox.height/2f);
        BBox b4 = new BBox(bbox.centerX + bbox.width/4f, bbox.centerY - bbox.height/4f, bbox.width/2f, bbox.height/2f);
 
        childs[0] = tree.getNewNode();
        childs[0].depth = depth + 1;
        childs[0].bbox = b1;
        childs[0].parent = this;
 
        childs[1] = tree.getNewNode();
        childs[1].depth = depth + 1;
        childs[1].bbox = b2;
        childs[1].parent = this;
 
        childs[2] = tree.getNewNode();
        childs[2].depth = depth + 1;
        childs[2].bbox = b3;
        childs[2].parent = this;
 
        childs[3] = tree.getNewNode();
        childs[3].depth = depth + 1;
        childs[3].bbox = b4;
        childs[3].parent = this;
 
    }
    //if we are at the maximum depth or there are not enough objects, do nothing
    if(childs == null) return;
    //now we try to put the objects into the child nodes
    for(int j = 0; j = 0; i--){
            if(BBox.overlap(childs[j].bbox, payload.get(i).box) == 1){
                //the object is completely inside the child, add it to the child
                Testobject o = payload.remove(i);
                childs[j].payload.add(o);
            }
        }
        //every node that fits is now in the child node j, try to push them
        //even deeper with a recursive pushdown()
        childs[j].pushdown();
    }
}

Pushdown überprüft ob es überhaupt Kindelemente gibt in die man ein Testobject verschieben könnte. Falls dies nicht zutrifft und es besteht Bedarf(da es mehr Objekte gibt als MAX_OBJECT_NUM zuläßt) werden vier Kindelemente erzeugt und mit entsprechenden Boxen versehen. Danach wird für jedes Objekt in der Payloadliste überprüft ob es komplett in eines der Teilelemente hineinpasst und daraufhin eventuell dort hineinverschoben.

Dies waren die wichtigsten Funktionen und Klassen. Ich werde in den nächsten Tagen den Sourcecode hier veröffentlichen, damit man sich ein komplettes Bild machen kann.
Da dies nur ein Test ist ob man überhaupt bewegte Objekte in einem Quadtree vernünftig verwalten kann müssen noch einige Tests gemacht werden. Die Mechanik des Baumes funktioniert jedenfalls schon zuverlässig wie die kleine Demo im letzten Blogposting gezeigt hat. Es bleibt nur die Frage ob es in einem Spiel ebenfalls funktionieren würde. Ich hoffe ich finde in den nächsten Tagen Zeit dies zu testen. Über Feedback würde ich mich freuen!

Quadtrees tauchen in der Computergrafik immer dann auf wenn es darum geht zwei dimensionale Daten hierarchisch zu ordnen. In Computerspielen kann man einen Quadtree beispielsweise dazu verwenden die Kollisionsabfrage zwischen Spielobjekten zu vereinfachen. Theoretisch müsste man jedes Objekt im Spiel zu jeder Zeit gegen jedes andere Objekt auf eine Kollision testen. Dies ist jedoch sehr ineffizient, da Objekte die weit auseinander liegen ja garnicht kollidieren können.

Man sortiert also die Objekte in eine Baumstruktur ein. Jeder Baumknoten kann dabei vier Kinder haben und repräsentiert je ein Viertel des darüberliegenden Knotens. Der Wurzelknoten repräsentiert die gesamte Szene. Im ersten Bild ist dies dargestellt: der rote Rahmen gibt die Grenze der Szene an und das kleine rote Kästchen ist ein Objekt der Szene:

Fügt man nun weitere Objekte hinzu wird der Wurzelknoten sich teilen, vier Teilknoten bilden und die Kinder in die Teilknoten verteilen. In Bild 2 ist dies dargestellt. Der rote Wurzelknoten ist natürlich noch da, er wird nur von den Kinderknoten überzeichnet.

Die Objekte haben nun die Farbe der Teilknoten um anzuzeigen auf welcher Ebene des Baumes sie sich befinden. Würde jetzt eine Kollisionserkennung durchgeführt, müsste man eigentlich nichts testen, denn alle Objekte befinden sich in anderen Teilknoten und sind somit weit genug voneinander entfernt. Wenn nun noch mehr Objekte dazugefügt werden, zum Beispiel in den unteren rechten Knoten, dann wird dieser sich weiter unterteilen:

Genau wie die Schwelle wann sich ein Knoten in vier Kinderknoten aufteilt kann man auch festlegen bis in welche Tiefe der Baum wachsen kann bis keine weiteren Unterteilungen mehr vorgenommen werden. Dies ist von der Anwendung abhängig die realisiert werden soll.

Es gibt noch einen Sonderfall bei dem es sich lohnt genauer hinzuschauen: Da in diesem Beispiel die Objekte eine räumliche Ausdehnung haben und nicht nur punktförmig sind, kann es passieren, dass ein Objekt genau auf der Grenze zwischen zwei Knoten liegenbleibt. In diesem Fall ordnet man dieses Objekt dem Elternknoten zu. Allerdings muss man nun beachten, dass die Kollisionserkennung dieses Objekt mitberechnet. Man muss also alle Objekte in einem Knoten testen plus alle Objekte die in den Elternknoten liegen. Um auch hier möglichste effizient zu bleiben wird schon beim Aufbau des Baumes darauf geachtet, dass man Objekte immer so tief wie möglich im Baum ansiedelt, sodass die Objekte die nicht in Blattknoten liegen möglichst wenige sind.

Ein interaktives Beispiel kann hier ausprobiert werden: quadtree test

Man kann mit der + Taste neue Objekte hinzufügen und das zuletzt hinzugefügte Objekt mit w a s d bewegen.