JLI Spieleprogrammierung

[Asto]

Huhu =)

Ich bastel derweil an einem Jump&Run, bzw an den Grundlagen dafür (Klassen, etc).
Nun Brauche ich für das Jump & Run ja auch eine Kollisionserkennung Levelumgebung vs. Spielfiguren.

Das wollte ich wie folgt realisieren:
Surface mit dem groben Levelaufbau im Hintergrund. Sprich: weisses surface, an den stellen, an denen "boden" is, is das bitmap bild schwarz.
Darüber wird dann quasi das Bild des Levels gelegt. Alles schön in Farbe und so

Nun zum testen lasse ich einfach ein sprite von oben herabfallen, welches stoppen soll, sobald es mit dem mittelpunkt auf die farbe schwarz trifft.

Ich denke mal, das das Prinzip okay ist bzw. ich hoffe es

Nun zum Problem:
Das Sprite fällt und fällt und fällt *gg*
Ich bekomme keine Farbe zurück, wenn ich sie aus dem Surface auslesen will. Zum testen wollte ich, mit dem aktuellen Farbwert des Pixels über dem grad das Sprite steht, einen Text einfärben, aber dieser ist immer unsichtbar, egal ob das sprite über weissen grund ist, oder über schwarzem.

Daher scheint da was mit dem wählen des aktuellen Pixels etwas nicht zu klappen!?

Lange Rede kurzer Sinn: Hilfe *gg*

Anbei die wichtigen Codestellen, evt. ein Hinweis: wird noch in andere Klassen etc. strukturiert, ist momentan meine Spielwiese:

Aus der Spielschleife:

[Maxim]

du willst also ein pixelgenaue kollisionserkennung?
zur laufzeit auf die pixel zugreifen ist sehr langsam, besser beim erstellen des sprites ein feld für die kollisionsdaten erstellen.
hmmm....eigentlich steht es im buch

ich habe auch mal ein tutorial darüber geschrieben
http://newmaxim.ne.funpic.de/create_page.php?file=2d_collision.html&dir=artikel

[Jonathan_Klein]

A8 ist im Gegensatz zu X8 mit Alphakanal.

Allgemein würde ich dir raten, nicht das ganze Level als Bitmap zu nehmen. In fast jeden Spiel ist ein level eine anhäufung von wiederkehrenden Objekten, dass kann man nutzen. Z.B. erst gucken ob das Objekt getroffen wurde (per Boundingbox meinetwegen) und dann, ob es auf den Pixel genau passt. Dabei ist es letztendlich egal, ob du nun Tiles oder richtige Objekte hast.
Theoretisch kann man auch oft, auf Pixelgenaue Kollision verzichten. Wenn man bei Powerups die Toleranz etwas größer und bei Gegnern etwas kleiner macht, ist der Spieler auch schon zufrieden.
_________________
https://jonathank.de/games/

[Asto]

@maxim: ja ich weiss das das im Buch steht (unter JLI Fighter ). aber ich dachte mir, das ich es so machen könnte ^^
Aber danke für deinen link zu deinem tut =)
werde es mal damit probieren (aber: siehe unten ^^)

@jonathan: also den verschiedenen bodenelementen / -abschnitten, so wie den Gegnern und co immer eine boundingbox geben!?

Oder wie meinst du das genau?

Aber: Meine Levels hätte ich jetzt so aufgebaut, das ich 1024x768er Bilder nebeneinander gepackt hätte und entsprechend scrolle.

Wie soll ich es anders machen? Soll ich Vordergrund (boden / wasser) und Hintergrund (himmerl, evt. bäume) trennen?

Und: Boden bekommt ne boundingbox? ich mein: im jump and run is der ja nicht durchgängig auf einer höhe. so müsste ich ja hunderte von boxen nebeneinander setzen oder nicht!?
wäre das nicht für einen ganzen level aufwendiger als obiges verfahren!?
ich müsste auch für jeden levelabschnitt die boxen selber festlegen oder nicht!?
_________________
"A programmer started to cuss, Because getting to sleep was a fuss, As he lay there in bed, Looping 'round in his head, was: while(!asleep()) sheep++;", Unbekannt

[DirectXer]

also ich würde an deiner stelle eher auf eine andere Kollisionserkennung als pixelgenau zurückgreifen, da das wie schon gesagt relativ aufwändig und langsam ist; beispeilsweise mit AABB (axis-aligned bounding box) oder nur bounding boxen. Wenn dein "Boden" dann parallel zum unteren Rand des Fensters ist, bekommst du damit sogar eine fast perfekt emulierte pixelg. Koll.-Det. hin. Noch einfacher, aber durchaus passabel wäre noch, einfach die y-Koordinate des Sprites zu prüfen, bis sie unter den Rand des Bodens kommt. Das aber mal so mit pixelgenauer Koll.Det. zu implementieren, könnte allerdings auch eine sehr gute Übung im Umgang mit Sprites und insb. auf Pixelbasis sein. Ich finde das Tutorial von Maxim dafür ziemlich gut, obwohl es ja auch im Buch detailliert steht.

Gruß DXer

[Asto]

hmm ok dann werf ich mein surface mal weg *g*
und werd mich mit gimp und dem editor ans aufschreiben der pixelkoords machen, für die boundingboxes - so viel arbeit

aber ok, wenn das die sinnvollste methode is

(Boden ist eigentlich nicht parallel zur x-achse geplant, wobei ich das glaub ich vereinfachen werde durch plätten des bodens, wenn ich sonst alle 10-50px ne neue box brauche... )

Oder ich nutze das mit den Arrays, jedoch muss ich das verfahren ja für einen ganzen levelvordergrund (boden, ebenen) auf einmal machen (einige 1024px breite bilder).
ratet ihr davon ab, oder kann man das ruhig machen, in verb. mit einem ladebildschirm oder ähnlichem.

Habt ihr schonmal ne Art Jump&Run gemacht? was würdet ihr empfehlen!?
Mit unebenem Boden er die Array-Variante oder? (spart mir viel arbeit und gibt sie dem pc XD)
wobei ich dann auch immer das array durchlaufen müsste bei jeder bewegung
_________________
"A programmer started to cuss, Because getting to sleep was a fuss, As he lay there in bed, Looping 'round in his head, was: while(!asleep()) sheep++;", Unbekannt

[DirectXer]

also, das mit den AA-Bounding Boxen ist nicht so ne arbeit, das ist eigtl eine der einfachsten Methoden; vllt hast du da was falsch verstanden? Allerdings ist das auch nicht so eine gute Lösung, wenn der Boden schräg ist; es gibt dafür aber eine viel schnellere und bessere Lösung auf Vektorbasis (sogar in 2d ), die auch im JLI-Asteroids-Code benutzt wird. Dieser Ausschnitt dient als Beispiel, und ist direkt von der Buch-CD:

[Asto]

Also wenn ich eine unebene landschaft habe, müsste ich das mit den boundingboxes ja so machen:

das wäre etwas arg aufwendig für einen ganzen level :X
Oder hab ich was falsch verstanden bei den 2D-BBs!?

wie funktioniert denn das von dir erwähnte verfahren!? ich steige da grad nicht so ganz hinter
habe es auch bei meinen 2003er JLI Asteroids dateien lokalisiert, in der Sprite.cpp - aber im Buch wird dazu nichts gesagt und so komm ich da als neuling grad nicht so ganz hinter

Würde des für eine Schräge wie im obigen Bild die Möglichkeit bieten, das man nicht 5 Boxen dafür hat, sondern eine Box, die eine schräge Seite besitzt!? (da vektoren verwendet werden?)
_________________
"A programmer started to cuss, Because getting to sleep was a fuss, As he lay there in bed, Looping 'round in his head, was: while(!asleep()) sheep++;", Unbekannt

[Jonathan_Klein]

Die Idee ist eigentlich, das Level NICHT in einem Malprogramm zu erstellen. Das mag für Worms ok sein, aber für ein J'n'R net. Am allereinfachsten ist es, ein Array zu machen. Hab ich z.B. bei meinem ersten J'N'R gemacht, ist einfach und schnell und für den Anfang sehr gut geeignet.


Auf den Bild sieht man es recht deutlich. Das Level besteht aus Blöcken, die alle gleich groß sind und in einem Array gespeichert werden. Man braucht nur sehr wenige Grafiken und Kollision kann man auch recht schnell testen.


So kann das auch aussehen. Das Tileset (d.h. alle Grafiken zusammen) ist lange nicht so groß, wie der Bildausschnitt, und man kann doch ein komplettes, großes Level relativ schick gestalten.
_________________
https://jonathank.de/games/

[DirectXer]

axo, so eine landschaft meintest du^^ Naja, das ist dann wieder was anderes. Ich dachte du meintest irgendwie eine gerade fläche, schräg oder parallel zu x-Achse wie das eben so in den 0815 Jump'n'Runs wie SuperMario oder so gemacht wird. Bei sowas könnte man gut über eine pixelgenaue landschaft nachdenken... Allerdings gibt es auch da schnelle Alternativen, wie z.B. eine 2d-LS Height Map, also eine Art 2d-Array in dem du jedem x-Pixelwert den entsprechenden y-Pixelwert der Landschaft zuordnest (kann man auch per PC generieren, indem du z.B. bei Initialisierung die Textur durchscanst oder die Werte direkt in einer Datei speicherst), und dann so in der art

[Jonathan_Klein]

hm, 2d heighmap, bzw. ja schon fast 1d ist auch ne lustige Idee. Allerdings ist das Problem, dass man keine Höhlen haben kann und auch keine Blöcke die in der Luft schweben. Die müsste man dann wieder separat behandeln. sollte man auf sowas allerdings verzichten können, ist 2d Heightmap sicherlich rasend schnell, einfach und gut.
_________________
https://jonathank.de/games/

[Asto]

hmm die ideen sind super, ich denke ich werde auf die von dir zurückkommen, jonathan.

habe noch fragen zum detial bzw fragen des verständnisses.

zum bild / beispiel nr1: also positioniert man diese blöcke zum erstellen des levels quasi erstmal per hand auf dem bildschirm und ein block hat dann halt eigenschaften wie mauer oder leiter. des weiteren hat jeder block ne eigene BB. richtig verstanden!? ^^

sollte ich zum üben als erstes entwickeln denke ich ^^

zum 2.: Also man platziert hier keine blöcke in dem sinne, sondern verschiedene elemetne, wie z.b. die höhle in der luft (die auf dem bild zu sehen ist) aus 3 blöcken: boden, dach, wand-links, die jeder ihre BB verwalten!? und so ist auch der rest des levels aufgebaut?

nun eine frage: im beispiel 2 bewegt sich der spieler ja auch über den bildschirmrand hinaus. da kann man am besten alle sprites erstellen, aber immer nur die anzeigen lassen, die auf dem bildschirm wären oder? nur wie handhabt man das?
setzt man z.b. für ein element das am ende des levels ist einen x-wert von 3000 und wenn man sich nun nach rechts bewegt, nimmt der wert ab, bis das sprite ins bild kommt? bzw zeigt es auch erst per .Draw() an, sobald es im bild liegt!?

Edit: ich glaub ich frag zu viele einfache dinge
aber bin halt noch recht unsicher in dem bereich
_________________
"A programmer started to cuss, Because getting to sleep was a fuss, As he lay there in bed, Looping 'round in his head, was: while(!asleep()) sheep++;", Unbekannt

[DirectXer]

[Asto]

Vielen Dank =)
Ich bin sicher, das ich es nun hinbekommen werde =)

Den Ball auf einen Block fallen lassen hat schon funktioniert *g*
Ok war auch net soo schwer nur jetzt erhöhe ich mal nach und nach den schwierigkeitsgrad
_________________
"A programmer started to cuss, Because getting to sleep was a fuss, As he lay there in bed, Looping 'round in his head, was: while(!asleep()) sheep++;", Unbekannt

[GreveN]

Ich möchte nochmal was zur pixelgenauen Kollisionsabfrage anmerken, da hier ja doch ein paar mal darauf hingewiesen wurde, dass diese sehr langsam sei. Das meiste Nachstehende hab ich selbst noch nicht getestet bzw. durch einen Profiler gescheucht und ist daher lediglich als Denkanregung bzw. Diskussionsgrundlage zu sehen.

Prinzipiell muss eine solche Kollisionserkennung nicht langsam sein, ich hab mal ein Weilchen darüber nach gegrübelt, im Prinzip muss man sich nur eine Strategie überlegen, um

1. die Tests so effizient wie möglich zu machen und
2. die Zahl der notwendigen Pixeltests auf ein Minimum zu drücken.


1. ist relativ leicht zu bewerkstelligen. Natürlich sollte man auf keinen Fall on-the-fly irgendwelche Farbwerte aus irgendwelchen Texturen/Surfaces auslesen, sondern mit Masken arbeiten, die man vorher erstellt und irgendwo hinterlegt. Diese Masken sollten natürlich nicht sonstwie gigantisch sein, sondern ein minimales Rechteck darstellen, welches das Sprite gerade noch komplett umfasst. Dann sollte man sich überlegen, wie man einzelne Punkte in den Masken darstellt, eine naive Lösung wäre natürlich einfach die Verwendung einer Bool-Variable pro Pixel, als ist-vorhanden/ist-nicht-vorhanden-Flag. Die Sache ist natürlich die, dass 'bool' immerhin satte 8 Bit groß ist, von welchen 7 redundant sind, das heißt hier könnte man eventuell optimieren, indem man den sich einen eigenen Datentyp definiert (via 'union') und dort jeweils die Bits einzelnen adressiert, dann könnte man auch sehr flott ein logisches Und darauf anwenden und somit in einem Rutsch 8 Pixel testen - ist der Ergebniswert irgendetwas ungleich 0, müssen sich in den Masken 2 Pixel überlagert haben, somit hat eine Kollision stattgefunden.


2. ist schon etwas komlexer, aber auch nicht wirklich schwierig. Zuerst muss man natürlich erstmal die Schnittmenge beider Masken ermitteln, also den Bereich, in dem sich beide Masken überlagern, d.h. man bekommt sozusagen 2 kleinere Masken, die deckungsgleich sind. Natürlich wäre es Dummheit, diese via 'new' (oder anders) physisch zu erzeugen, man merkt sich einfach irgendwo die Offsets, die die Lage der "neuen" Masken auf den alten markieren, damit hat man die Pixel, welche überhaupt getestet werden müssen schonmal ganz beträchtlich gedrückt.

Nun könnte man ganz naiv Pixel für Pixel von links oben bis nach rechts unten testen, aber das ist einfach nur ineffizient. Im Prinzip sind Kollisionen an den äußersten Randbereichen schonmal relativ unwahrscheinlich, da sich da bei den meisten Sprites eh nix befindet und diese nur der rechteckigen Form wegen mitgeschleppt werden.

Nun stellt sich natürlich die Frage wo man denn dann am besten anfängt zu testen und wie man sich systematisch weiter arbeitet.

Da wir es hier effektiv mit einer Art semientscheidbaren Problem zutun haben, wenn irgendwo eine Kollision stattfindet, wollen wir diese so schnell wie möglich finden, wenn nicht, dauert das Testen wahrscheinlich inakzeptabel lange. lässt sich sagen, dass eine relative Gleichverteilung der zu testenden Punkte innerhalb der 2 Masken sinnvoll ist, jetzt müssen wir schauen wie wir das am besten anstellen.

Ein spontaner Ansatz wäre vielleicht die Verwendung von irgendwelchen Zufallszahlen als Koordinaten für die zu testenden Punkte, aber es dürfte plausibel sein, dass das eine eher schlechte Lösung ist, da die Generation alleine schon ein erhebliches Zeitproblem darstellt.

Noch ein netter Gedanke wäre, dass man schlichtweg am besten einfach den mittleren Pixel zuerst testet, ich denke ein Großteil der Kollisionstests könnte nach diesem ersten Test schon abgebrochen werden, wenn nicht, springt man in die 4 Rechtecke, die durch das Kreuz aufgespannt werden, in dessen Zentrum der eben geteste Pixel liegt, dort testet man wieder den zentralsten aller Pixel usw... Dieses Verfahren impliziert einen rekursiven Algorithmus, wobei man einen wunderschönen Quadtree aufbaut, wichtig ist natürlich eine Breitensuche zu implementieren und keine Tiefensuche, um den zu checkenden Bereich möglichst gleichmäßig zu überprüfen und nicht irgendwie sehr "ecklastig" zu verfahren... Diesen Algorithmus ist natürlich nicht zwingend optimal, da sich Objekte z.B. in Spielen ja gerade vom Rand her in einander bewegen, noch dazu hat man eben wieder das Problem, dass das "Drumherum" zu kostenintensiv ist, jeder Breitensuche-Schritt wird sicher länger dauern als eine handvoll Pixel mehr zu testen...

Als der wahrscheinlich effizienteste Ansatz erscheint mir im Moment, sich rasterartig über die Masken zu bewegen, soll heißen, man testet jeden k-ten Pixel einer Zeile und nur jede k-te Zeile überhaupt, hat man so die komplette Fläche abgegrast, verkleinert man k und startet von vorn. Letztendlich ist das mehr oder weniger das Gleiche wie oben genannter Algorithmus (nur das das k da am Anfang sehr groß ist, nämlich die Hälfte der Höhe/Breite der Masken), allerdings deckt man von Anfang an eine größere Fläche ab, indem man mehr Tests in Kauf nimmt, spart dadurch aber eventuell teure Rekursionsschritte. So richtig glücklich bin ich damit aber auch noch nicht, weil man so wieder in einer Ecke anfängt und in der gegenüberliegenden aufhört, das könnte man eventuell optimieren, indem man sich wechselseitig aus allen 4 Ecken auf das Zentrum zu bewegt, aber das müsste man mal austesten...


Egal wie man es macht, man sollte tunlichst vermeiden alle Pixel testen zu müssen (es sei denn, die zu testende Fläche ist sehr klein, was relativ oft der Fall ist), also braucht man eine sinnvolle Endbedingung. Wenn man o.g. Algorithmus verwendet, wäre es z.B. sinnvoll, einfach aufzuhören, wenn das k klein genug wird. Im Prinzip sind das aber Erfahrungswerte und hängen z.B. von der Form und Größe der Sprites ab, sowie dem Kollisionsverhalten (Gleiten die Objekte eher ineinander oder "ploppen" sie ?)... Wenn die zu testende Fläche im Average-Case klein genug ist, kann man sich einen Algorithmus zur "Pixelsuche" wahrscheinlich auch komplett schenken, überlappen sich die Sprites z.B. mit nur 8x5 Pixeln, ist man ja mit obiger Maskendarstellung schon mit 5 logischen Unds beim Ziel...

Sinnvoll wäre es vielleicht, den zu verwendenden Algorithmus nicht statisch zu coden, sondern als Aspekt oder Dergleichen zu übergeben, um flexibel zusein, was verschiedene Gegebenheiten anbelangt.

Achja, last but not least, ist natürlich unbedingt zu empfehlen vor einer etwaigen pixelgenauen Kollisionserkennung Bounding-Box-Tests mit minimalen (also so klein, dass das Objekt gerade noch hinein passt) Boxen durchzuführen und dann nur bei einem positiven Hit nachzutesten.