Archive for the ‘Development’ Category
Asteroiden soweit das Auge reicht
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.
Quadtree Implementation in Java
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!
Quadtree
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.
ColorGradient
Java hat zwar einige gute GUI-Komponenten, aber sobald man etwas spezielleres braucht hört es auch schon wieder auf. Für mein Partikelsystem möchte ich ein Editor schreiben mit dem man möglichst unkompliziert Farbverläufe für die Partikel erstellen kann. Ein erster Ansatz sieht mal so aus:

Ich habe ein kleines Web Start gebaut mit dem man das mal testen kann. Den Sourcecode, Javadocs und was so alles dazugehört kann man sich hier runterladen: ColorGradient v0.1 zip
Dies ist die erste Version, es kann sich also noch viel ändern und für Tips und Ratschläge diesbezüglich wäre ich sehr dankbar!
ColorGradient erweitert die Java Swing Klasse JComponent und hat ein eigenes ColorGradientModel mit dem eigentlich alle Anderungen durchgeführt werden sollen. Die Bedienung ist simpel: Die Buttons rufen Methoden des DefaulColorGradientModels auf, welche direkt die Farben und Positionen der Marker beeinflussen. Außerdem kann man per Drag and Drop die Marker auch von Hand verschieben. Der akutelle Marker hat einen kleinen Strich an der Unterseite um ihn von den anderen abzuheben.
LWJGL 1.1 erschienen
Gestern war es mal wieder soweit: lwjgl.org, die Macher hinter der Lightweight Java Game Library haben eine neue Version ihrer Java Grafik/Gaming Bibliothek herausgebracht. Im Changelog war nachzulesen, dass die Performance der Vertex Buffer Objekte verbessert wurde und das ist auch tatsächlich der Fall. Ich habe grade eben mein Partikelsystem mit den neuen Bibliotheken rendern lassen und eine Geschwindigkeitsverbesserung von bis zu 25% feststellen können!
Java Web Start Tutorial
Java Web Start ist ein geniales Tool um Anwendungen auf Clientrechner zu starten ohne dass diese vorher eine Installationsdatei herunterladen und installieren mussten. Manchmal kann es jedoch etwas knifflig sein eine Web Start Anwendung zum Laufen zu bringen und deswegen dachte ich es wäre ganz gut hierfür ein deutsches Tutorial zu haben.
Hier gehts zum Java Web Start Tutorial. Viel Spass beim Lesen.
Es gibt ein ähnliches englisches Tutorial und viele andere interessante Dinge zum Thema auf cokeandcode.com
Java Webstart
In den letzten Tagen habe ich mal wieder etwas Zeit gefunden zu programmieren. Diesesmal ists ein kleines Partikelsystem geworden das ich aber noch weiter ausbauen will. Einen ersten Eindruck gibts hier:

Da das aber ziemlich unspektakulär aussieht dachte ich, ich stelle es auch als Webstart zur Verfügung. Webstart ist eine Technologie mit der man Javaprogramme über das Internet runterladen, installieren und ausführen kann. Das tolle daran ist, dass dies für den Benutzer automatisch geschieht und er nur einen Link anklicken muss.
Hier und hier könnt ihr mal klicken um es auszuprobieren. Java 1.5 sollte auf dem Rechner installiert sein. Im Moment funktioniert das ganze nur für Windowsrechner, aber vielleicht liefere ich ja bald die Runtimes für Linux/Mac hinterher.
Folgende Tasten braucht ihr:
a = Partikel starten
s = Partikel stoppen
d = Animation anhalten
f = Animation weiterlaufen lassen
ESCAPE beendet das Programm.
Bitte lasst mich in einem Kommentar wissen ob es funktioniert, oder ob ihr Probleme habt!
CrillionZ XMess
Nur noch wenige Tage, dann erscheint das neue CrillionZ Xmess endlich! Ich schätze das hier

ist das offizielle Werbeplakat :)
Mandelbrot in Matlab
Neulich bin ich beim Stöbern auf den Seiten des Plus Magazins auf einen Artikel über Fraktale gestoßen. Sofort ist eine alte Faszination entflammt und ich dachte es kann nicht so schwer sein das Mandelbrot selbst mal herbeizuzaubern. Gesagt getan, nach ein paar Minuten mit Matlab haben sich schon einige interessante Ergebnisse zusammengefunden:
Das entsprechende M-File habe ich auch mal hochgeladen, allerdings ist die Berechnung damit hoffnungslos langsam, ich habe noch nichts optimiert: click!
CrillionZ Weihnachtsversion
Rechtzeitig zu Weihnachten gibt es eine Weihnachtsversion von Daves CrillionZ. Es wird überarbeitete Grafiken geben, neue Musik und natürlich einen Haufen neuer, kniffliger Level. Soweit mir bekannt ist, ist eigentlich alles soweit fertig und es wird nur noch hochglanzpoliert. Wenn ich mich richtig erinnere ist der Releasetermin der Nikolaustag, sechster Dezember also!
