Projekt: Zelda Clon programmieren

[finalmagic]

Hallo meine Lieben!

So ich programmiere seit einigen Jahren jetzt schon in Java und wollte mich an ein größeres Projekt wagen, als Minesweeper und Asteroid-Shooter

Wie ihr im Betreff lesen könnt, handelt es sich um einen Zelda Clon.

Hier zu meinem Konzept:

1. Level:

Das Level besteht wies auch nicht anders zu erwarten ist aus einer Tilemap xD

In ihr wird die Karte anhand eines 2 dimensionalen Arrays gespeichert.

int levelMap[][] = new int[mapWidth][mapHeight]

2. Input:

Gesteuert wird der Proband mit WASD. ENTER zum schlagen. Mehr erst mal nicht

3. Mobs:

Wie in jedem 2D Zeldaspiel gibt es natürlich auch Mobs(Gegner). Sie sollen zufällig in der Map durchlaufen und ggf. den Probenden verfolgen, sollte dieser in Sichtweite kommen.

4. Animation:

Jaaa, dass ist mein größtes Problem. Das Schwertschlagen, Steine heben etc. Ich hab noch keine Ahnung wie ich das umsetzen soll Aber das soll natürlich auch ins Spiel xD

5. Kollision:

Kollision mit der Map soll abgefangen werden, genau wie Kollision mit den Mobs und den Gegenständen. Mein soll ja nicht durch Mauern laufen können

6. Darstellung:

Und natürlich soll auch alles schön auf das JPanel gezeichnet werden. Aber das ist das kleinste Problem. Spielschleife und Funktionen stehen schon.

So wie ihr seht, soll am Schluss ein fertiges ZeldaSpiel entstanden sein. So nun kommt ihr! Wer hat schon Erfahrung mit der Programmierung eines Adventures? Wer kann mir hilfreiche Tipps und Denkanstöße geben. Zum Anfang geht es nur um

!!PUNKT 1!!

Ich möchte einen Mapeditor schreiben, der mir die TileMap als level1.map ausspuckt. Ich werde in den nächsten Tagen das erste Konzept online stellen. Bis dahin bin ich über jeden Tip dankbar

Vielen Dank und postet alles was euch dazu einfällt

Liebe Grüße,

final

[flashpixx]

Ich will hier nur kurz einmal den Verweis auf die Computergraphik geben, Kollisionsberechnung von unregelmäßigen Körpern ist nicht ganz trivial.

Eigne Dir zunächst einmal die Grundlagen der Linearen Algebra an, damit Deine Algorithmen auch effizient werden. Ich würde BV Hierarchy bzw BV Boxes verwenden

[finalmagic]

@ flashpixx: Vielen Dank für die schnelle Antwort!

Also ich muss ehrlich gestehen, dass ich bisher Kollisionen nur zwischen Rechtecken abgefangen. (und Kreisen xD)

Hab auch einige Kollisionsfunktionen geschrieben! Hier meine Funktion um Kollision en mit Rechtecken abzufangen:

public static boolean checkCollusion(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {

	if(x2 >= x3 && x4 >= x1 && y2 >= y3 && y4 >= y1) return true;

	return false;

}

Der Funktion übergeb ich die linkere obere Ecke und die rechte untere Ecke zweier Sprites und krieg dann raus, ob die beiden sich treffen. Recht simpel ich weiß, aber hat bisher gereicht.

Kannst du mir eine Website nennen, wo ich mir das mal ansehen kann?

[flashpixx]

Kannst du mir eine Website nennen, wo ich mir das mal ansehen kann?

Bounding volume - Wikipedia, the free encyclopedia

Das ganze funktioniert analog auch in 2D.

Dein Algorithmus wird aber schon nicht mehr korrekt funktionieren, wenn sich genau 2 Ecken 2er unterschiedlicher Polygone treffen. Außerdem kannst Du nicht um jeden Körper eine einzelne Hitbox legen, denn damit würden sich nur rechteckige Körper formen lassen, was z.B. schon bei der Spielfigur problematisch ist.

Mache API wie DirectX oder auch OpenGL unterstützen Bounding Hierarchien (Octree / kd-Tree), so dass Du damit auch diese Methoden implementieren kannst. Für eine 2D Ansicht wäre dann entsprechend der Viewpoint zu setzen.

Ich halt aber Dein Vorhaben für nicht praktikabel, da Dir aktuell Grundlagen dafür fehlen und diese man sich auch nicht mal eben schnell durch ein Tutorial aneignen kann

[finalmagic]

Naja du musst bedenken, dass das Spiel komplett in 2D gehalten ist und alle Sprites auch rechteckig sind.

Ich gebe dir aber vollkommen Recht! Ein solches Verfahren, werd ich mir kaum in einer Woche aneignen können aber ich kann mich mal reinlesen. Hab einige Erfahrung in Spieleprogrammierung und hab einige Handygames geproggt.

Auch schon Spiele mit der Top-Down Perspektive und natürlich mit Viewpoint!

Ich bin mir eigentlich sicher, dass das Projektziel nicht unerreichbar ist! Aber ich bin mir auch sicher, dass ich auf einige Hänger treffen werde, bei denen ich sicher Hilfe brauche!

Ich schweife ab

Wenn ich mir die Wikiseite zu Bounding Volume ansehe, seh ich gar nicht so einen großen Unterschied zu meiner Funktion. Ich berechne auch eine Kollision mit 4 Punkten. Vieleicht steh ich auch grad auf dem Schlauch! (Steh ich häufiger )

Kannst du mir mal ein beispiel Zeigen? Wie eine solche Kollisionserkennen dann aussehen könnte?

Vielen Dank nochmal für die Hilfe! Bin echt überrascht! Hab gedacht ich werd zerfetzt hier im Forum

[flashpixx]

Naja du musst bedenken, dass das Spiel komplett in 2D gehalten ist und alle Sprites auch rechteckig sind.

Meines Wissen wird nicht für jedes Sprite ein einzelnes Rechteck verwendet, sondern eben Bounding Boxes, d.h. mehrere, eben je nach Auflösung. Wobei Du dann direkt die Frage hast wie viele BV's nimmst Du, um eine gute Approximation des Sprites zu erhalten.

Einfaches Bsp: Ein Kreis, der von einem Rechteck eingeschlossen wird, deckt nicht gut ab.

Hab einige Erfahrung in Spieleprogrammierung und hab einige Handygames geproggt.

Ich gehe davon aus, dass das eher ein Trial 'n' Error war. Denn gerade dabei kommt es auf effiziente Algorithmen an, die sicher nicht mal so eben implementiert werden.

Wenn ich mir die Wikiseite zu Bounding Volume ansehe, seh ich gar nicht so einen großen Unterschied zu meiner Funktion. Ich berechne auch eine Kollision mit 4 Punkten.

Als Beispiel überprüfst Du bei Dir immer alle 4 Ecken, das sind 4 Vergleiche.

Wenn Du in Deiner Szene 5 Gegner, 3 Steine hast und Deine Spielfigur, sind das 9 Figuren * 4 Vergleiche = 36 Operationen, die Du bei jeder Veränderung der Gegner bzw Deiner Spielfigur durchführen musst (mal abgesehen davon, dass die Gegner ja auch mit den Steinen kollidieren können). Da sich ja Deine Gegner auf Deine Figur zu bewegen musst Du auch die Kollisionen zwischen den Gegner selbst berechnen.

Spieleprogrammierung hat etwas mit sehr effizienten Algorithmen, sowie den dazu schnellen Datenstrukturen und sehr guter Approximation zu tun.

[finalmagic]

Ok ich verstehe. Ich habe es bisher immer so gemacht, dass ich zuerst überprüft habe, ob die zu überprüfenden Sprites im sichtbaren Bereich liegen, also auf dem Screen, anschließend, ob mit ihnen, oder untereinander eine Kollision besteht.

Ich dachte mir die Kollision im ZeldaClon folgendermaßen:

Per Viewpoint wird des aktuell sichtbare Screen ermittelt. Alle Sprites innerhalb dieses Screens sind "Rechtecke" und werden durch die Kollisionserkennung gejagt und entsprechend wird eine Aktion durchgeführt.

Das klappt auf Handy eigentlich ganz gut und nein es waren keine Trial'n'Errors bitte nichts behaupten, kannst mich auch einfach fragen =) Dann schick ich dir ein Beispiel sobald ich zuhause bin.

Jetzt stellt sich mir eine Frage, wie kann man das noch verschnellern? Weil die Kollision muss doch so oder so bei allen durchgeführt werden. Oder hab ich es bisher umständlich gemacht?

[flashpixx]

Das klappt auf Handy eigentlich ganz gut und nein es waren keine Trial'n'Errors bitte nichts behaupten, kannst mich auch einfach fragen =) Dann schick ich dir ein Beispiel sobald ich zuhause bin.

Mach das ganze bitte einmal mit 100 oder 1000 Objekten.

Außerdem werde ich sicherlich keine Programme von irgendwem auf meinem Handy installieren, um mir irgendetwas anzuschauen. Nur, wenn Du das alles wüsstest, dann wären die entsprechende Algorithmen bekannt und Du hättest sie schon umgesetzt

Jetzt stellt sich mir eine Frage, wie kann man das noch verschnellern? Weil die Kollision muss doch so oder so bei allen durchgeführt werden. Oder hab ich es bisher umständlich gemacht?

Nein muss man nicht. z.B. ein naiver Ansatz ist, eine Kollision kann nur dann stattfinden, wenn die Distanz zwischen ihnen kleiner gleich der Summe der beiden halben Durchmesser (beim Kreis wäre es der Radius) ist.

Man muss eben schauen, wie effizient man einen entsprechenden Algorithmus wählt.

Außerdem reicht ja bei Deinem Verfahren die Aussage "isCollision::bool" nicht aus, sondern Du musst auch wissen, wo die Kollision auftritt (oben, unten, rechts, links), weil Du ja die Richtung der Figur verändern musst.

[finalmagic]

Ok also muss meine Kollision folgende Struktur haben:

1. Überprüfe ob die Distanz zwischen 2 Sprites einen bestimmten wert hat

2. Überprüfe ob eine Kollision zwischen den Sprites stattfindet

3. Überprüfe an welcher Seite die Kollision stattfindet und gib die Seite zurück

if(distanz(Sprite1, Sprite2) < 0) {

	if(kollision(Sprite1, Sprite2)) {

		if(kollisionTop(Sprite1, Sprite2) return TOP;

		if(kollisionDown(Sprite1, Sprite2) return DOWN;

		if(kollisionLeft(Sprite1, Sprite2) return LEFT;

		if(kollisionRight(Sprite1, Sprite2) return RIGHT;

	}

}

Im besten Fall hab ich dann nur eine if-Abfrage und im schlimmsten sechs. Aber so ist das ganze doch gemeint, oder? Sieht auf jeden Fall plausibel aus. und selbst bei 1000 Sprites müsste das relativ schnell sein. Korrigier mich bitte.

[flashpixx]

Im besten Fall hab ich dann nur eine if-Abfrage und im schlimmsten sechs. Aber so ist das ganze doch gemeint, oder? Sieht auf jeden Fall plausibel aus. und selbst bei 1000 Sprites müsste das relativ schnell sein. Korrigier mich bitte.

Du denkst naiv. Ich hatte ja geschrieben, dass es mehrere Möglichkeiten gibt. Warum willst Du Sprite für Sprite prüfen? Wenn ich z.B. schon meine Datenstruktur so wählen kann, dass ich sie als Baum ablege und die Sprites darin so einhänge, dass sie nach der Distanz schon sortiert sind, d.h. ich kenne pro Knoten schon die Distanz und muss nicht mehr alle Sprites prüfen.

k-d-Baum ? Wikipedia

Quadtree ? Wikipedia

Gridfile ? Wikipedia

Kollisionserkennung (Algorithmische Geometrie) ? Wikipedia

[finalmagic]

Stimmt! An Datenstrukturen hab ich noch gar nicht gedacht. Man Teilt die Sprites in verschiedene Bereiche und überprüft nur die Kollision innerhalb dieser Bereiche. Das verbindet man einfach mit der Kollisionserkennung von oben und voila! Schon geht das alles schneller =)

Werd ich heute Abend sofort ausprobieren wenn ich zu Hause bin. Dachte da an das k-d-Baum-Modell. Eignen sich aber alle für das Spielchen.

So hab mir grad Gedanken um die Map gemacht. Folgende Kriterien muss sie erfüllen:

- Es gibt verschiedene Terrains. Also müssen verschiedene TileSets verwendet werden. Diese werden Zentral in eine Klasse gespeichert.

- Es gibt einen Untergrund (Gras, Boden, etc.), eine Landschaft (Bäume, Blumen, etc.) und Objekte (NPCs, Gegenstände, etc.)

- Die Karte soll einen Namen haben.

- Es gibt Teile der Landschaft, die man nicht betreten darf.

Unter Beachtung der oben genannten Punkte ergab sich folgende Klasse:

class Map {

	byte tileSet;

	byte[][][] map;

	String mapName;

	byte[] colTiles;

}

Wenn einem noch was einfällt, immer her damit

[flashpixx]

Schon geht das alles schneller =)

Werd ich heute Abend sofort ausprobieren wenn ich zu Hause bin. Dachte da an das k-d-Baum-Modell.

Auch hier der Hinweis, was in 3D effizient ist, muss nicht ebenso in 2D effizient sein

Kollisionserkennung (Algorithmische Geometrie) ? Wikipedia

Computersimulation und -animation kann im 2D-Raum oder im 3D-Raum ablaufen. Die meisten Kollisionserkennungsmethoden, die für den dreidimensionalen Raum erstellt wurden, können zwar auch zur Lösung des zweidimensionalen Problems verwendet werden, was aber im Allgemeinen nicht zu einer ebenso effizienten Lösung führen muss.