Sidescroller - vernünftige Collision Detection mit dynamischer Oberfläche

[LilaQ]

Hallo zusammen,

ich hoffe der Titel ist aussagekräftig genug

Also, ich habe ein Spiel, bei dem eine Figur über eine dynamisch generierte Oberfläche läuft & hüpft. Eine Gravitation habe ich drin, die Figur springt und fällt schon ganz ok soweit. Durch eine Hittest Abfrage mit der Oberfläche, landet die Figur soweit auch immer auf der Oberfläche.

Durch die Gravitation, ging das Bergab Laufen von Anfang an problemlos. Dann gab es natürlich das Problem dass ich beim Bergauf Laufen, durch die Map gelaufen bin, anstatt auf der Map weiter nach oben.

Für den Anfang hatte ich das so gelöst, dass der oberste Y-Punkt der Map gefunden wird wenn die Figur sich bewegt hat, und habe dann der Figur diesen Y-Punkt zugewiesen. So läuft sie komplett die Karte entlang.

Moment passt mir noch nicht dass:

(1) die Figur auch sehr steile Ansteigungen hochläuft (das ist ja leicht abzufangen durch den Vergleich der neuen Y-Position und der aktuellen Y-Position)
Allerdings hätte ich gerne dass die Figur den Anstieg dann herunterrutscht, wenn sie versucht dort hochzulaufen, dazu habe ich aber keine passende Idee zur Realisierung

(2) die momentane Lösung mit der Y-Koordinate birgt 2 Probleme:

- wenn ich eine 'Klippe' herunter laufe, fällt der Spieler nicht, sondern er wird wieder auf den 'höchsten' Punkt der Karte gesetzt (in diesem Fall halt weit unter dem vorherigen Punkt, wie gesagt, ohne zu Fallen)

- ich kann den Spieler nicht durch 'Höhlen' laufen lassen, da bei diesen der höchste Punkt der Map natürlich AUF der Höhle ist.


Die Map soll definitiv dynamisch generiert werden und ist auch nur als Sprite / Bitmap verfügbar, da ich mit der Map noch einige graphische Spielereien veranstalte die dieses brauchen.

Wenn mir bei diesen Problemen jemand irgendwie weiterhelfen kann, wäre ich sehr dankbar.

Freu' mich schon auf eure Antworten.

Beste Grüße,
LilaQ

[[RK]]

Wie funktioniert das Hit-Testen?
Wie wird deine Karte erstellt?

Wenn du beispielsweise tilebased arbeitest, könntest du jeweils das Tile unter der Spielfigur abprüfen und fragen welche Art Tile es ist und gegebenenfalls entsprechende Hit-Tests ausführen. Ist es beispielsweise Wasser verwendest du andere Mechanismen als wenn du eine Schräge hast oder einfach nur eine gerade Fläche. So sparst du Performance und bist flexibler mit Features. (Ein Pane-System lässt sich in tilebased Spielen auch gut implementieren)

[LilaQ]

Tilebased kommt leider nicht in Frage, da die Map komplett dynamisch gezeichnet wird. Es wird ein Punkt unten links, ausserhalb der Stage gesucht bei dem gestartet wird. Dann wird entlang einer Sinus-Kurve (mit zufälliger Amplitude, Streckung und Verschiebung) mit etwas "Rauschen" nach oben und nach unten, alle paar Pixel ein neuer Punkt mit curveTo angezeichnet.

So habe ich am Ende eine komplett zufällig gezeichnete Landschaft. Diese Landschaft wird in ein Bitmap gedrawt, welches dann auch dargestellt wird. Über den BitmapData.Hittest() wird die Fall-Kollisionsabfrage gemacht.

Würde mich freuen, wenn noch ein paar Ideen kommen

Mfg
LilaQ

[[RK]]

OK, fast vermutet das es gezeichnet wird. War mir nur nicht sicher weil du meintest es kommt nur Sprite / Bitmap in Frage. Da war ich etwas verwirrt.

Naja, was ich auch mal gemacht habe war die Hittests per getPixel() zu lösen. Also ich hatte meine Map gezeichnet und simultan dazu eine Hitmap bei der die jeweiligen Pixelfarben gekennzeichnet haben um was es sich handelt. (Ist allerdings nicht so der Wahnsinn @ Speicher :P)

Ist in deinem Fall allerdings wohl weniger hilfreich. Ich schätze bei dir wäre noch das passenste einfach die Steigung zwischen 2 Pixeln zu berrechnen. Wenn deine Berrechnung der Map allerdings schon so streng mathematisch abläuft wärs natürlich interessant ob du nicht vll sogar einfach die 1.Ableitung davon hernehmen könntest.

Wobei sich nun die Frage stellt wie genau dein Bitmap gezeichnet wird. Bzw. wie wird berrechnet was der "höchste Punkt ist"? Kann man diese Berechnung nicht vom Charakter aus ausführen anstatt von y:0? (um Höhlen etc. zu ermöglichen)

[LilaQ]

Zitat von [RK]

...
Wenn deine Berrechnung der Map allerdings schon so streng mathematisch abläuft wärs natürlich interessant ob du nicht vll sogar einfach die 1.Ableitung davon hernehmen könntest.

An sich eine Idee, allerdings ist meine Karte "zerstörbar", will sagen, es werden teilweise Stellen von der Karte entfernt (deswegen auch die Darstellung als Bitmap).

Zitat von [RK]

...
Wobei sich nun die Frage stellt wie genau dein Bitmap gezeichnet wird. Bzw. wie wird berrechnet was der "höchste Punkt ist"? Kann man diese Berechnung nicht vom Charakter aus ausführen anstatt von y:0? (um Höhlen etc. zu ermöglichen)

Genau das war die Idee, die ich in den letzten 2 Tagen im Kopf hatte. Momentan prüfe ich einfach von der X-Koordinate, auf die der Spieler laufen will, im Bitmap per getPixel() von y:0 (wie du schon sagtest) solange weiter nach unten, bis die Farbe des Pixels nicht mehr transparent ist - also die Map 'gefunden' wurde.
Wenn ich das vom Y des Spielers aus mache, sollte es ja für die Höhlen funktionieren und zusätzlich sogar weniger Berechnungen in Anspruch nehmen.

Ich denke so werde ich auch gleich mal versuchen das Ganze umzusetzen.



Jetzt fehlt mir dann allerdings noch die mathematische / physikalische Beschreibung des Rutschens. Diese sollte sich am besten generell auswirken, und nicht nur beim Besteigen eines zu steilen Hügels. Will sagen, dass wenn der Spieler mal auf einen Abhang fällt, er auch dann runterrutschen kann.
(Halt im Endeffekt eine generelle physikalische Beschreibung, so wie es mit der Gravitation ja auch funktioniert)

Besten Dank schonmal

Mfg
LilaQ

[[RK]]

Lässt sich ja über die Steigung zwischen zwei Pixeln lösen.

Du testest wie bisher den ersten Bodenpixel von deinem Charakter aus (y, solange runtergehen bis alpha != 0), nur das du das ganze simultan auch an der Position xpos + 1 (Charakter sieht/geht nach rechts) oder xpos - 1 (links) machst.

Die Höhendifferenz der 2 errechneten Koordinaten ist gleich deine Steigung und entsprechend hast du einen Vektor (musst darauf achten das er immer nach unten zeigt) in dessen Richtung du den Charakter "schupsen" kannst und die Länge gibt auch gleich die Stärke an mit der der Charakter runterkugeln soll. - jeweils pro Rendertick (Frame) wiederholen und sofern ich mir das jetzt nicht zu einfach mache sollte es das auch schon gewesen sein.

@Bodentesten.
Die Worms-Reihe macht das genauso (wie die Physik lösen weis ich nicht). Zur Optimierung lassen sie soweit ich weis allerdings sogar Pixel aus, da in den meisten Fällen es nicht auf 1nen Pixel genau ankommt. Kann mich aber nicht erinnern ob das bin zum Ende so drin blieb, oder Probleme verursacht hat. Aber kann man ja recht schnell ausprobieren. Vielleicht passt es ja für dein Spiel besser.

[LilaQ]

Hi,

ja das klingt doch schonmal nach nem sehr schönen Ansatz.
Habe auch gestern noch den Test umgeschrieben, dass jetzt "nach oben" gesucht wird bis eine Mapgrenze erreicht wurde. Leider ist das ganze manchmal noch ein bisschen buggy und die Figuren "zittern" hoch und runter... aber das muss sich irgendwie noch lösen lassen. Hab eben auch nochmal testweise auf die alte Lösung umgestellt, da hatte ich die Probleme merkwürdigerweise nicht.

Achja, hast es übrigens genau getroffen, das Spiel wird ein Worms Clone Soll sogar ziemlich umfassend werden. Hab den Tag über schon an den Schussfunktionen gearbeitet, Explosionen und wegsprengen von der Map klappt auch schon.

Das ganze ist eine Hausarbeit für's Studium, hab noch bis Ende September Zeit

Werde das mit dem Rutschen dann direkt mal probieren, sobald der Rest der Bewegungen / Höhlen Betreten / etc. problemlos funktioniert ... Immer nur an einer Baustelle arbeiten, hab ich auch bei diesem Projekt wieder gemerkt ;>

Mfg
LilaQ

[[RK]]

Wieso testest du aufeinmal von unten nach oben? Das machts ja kein bisschen besser. Von oben nach unten ist ja schon ok, nur ignorier einfach alle Werte solang deren y > des y deines Wurms ist. (wenn du schon nicht erst ab da starten kannst :X)

[LilaQ]

Wenn ich von oben teste, würde ich ja wieder nur auf die oberste Ebene der Map treffen.

Hab's glaub ich nicht gut genug beschrieben, also ich teste jetzt vom aktuellen Y meines Wurms, und von da aus nach oben (wenn der Wurm IN der Map steht, der Wurm also eine Steigung hochläuft), und korrigiere dann auf diesen Punkt. So komme ich ja immer auf die aktuelle Ebene auf der der Wurm läuft.

Ich hoffe es ist verständlich wie ich das meine ^^ Sonst mach ich nachher nochmal ne Zeichnung.

Mfg
LilaQ

[joeydee]

Also die Funktion wie du den nächten Boden in der Map von einem bestimmten Punkt aus gesehen findest, dürftest du ja jetzt haben wenn ich richtig verstehe. Mach daraus eine eigene Funktion, etwa so:

function findNextGround(px:int,py:int){
    var gy:int;
    while(gy!=py && py>0 && py<550){
        gy=py;
        if(!level.hitTestPoint(px,py+1,true))py++;
        if(level.hitTestPoint(px,py,true))py--;
    }
    return py;
} 

In jedem Frame: Finde das nächste Boden-Y für die aktuellen Wurmkoordinaten, aber setze ihn nicht gleich dorthin.

a) Wenn der Wurm nach oben muss, setze ihn direkt dorthin (Wurm war im Boden versunken).

b) Wenn er nach unten muss, lass ihn nach unten fallen (Wert hinzuaddieren).

c) Wenn er weder nach oben noch nach unten muss, sitzt er auf Grund. Berechne nun die Steigung:
Finde das nächste Boden-Y jeweils ein paar Pixel links und rechts von der Wurmkoordinate. Aus dem Höhenunterschied und dem horizontalen Abstand der beiden Messpunkte kannst du eine Steigung (slope) errechnen (Mathe Mittelstufe lässt grüßen: DeltaY/DeltaX):

var rad:int=5;
var y1=findNextGround(wurm.x-rad,wurm.y);
var y2=findNextGround(wurm.x+rad,wurm.y);
var slope:Number=(y2-y1)/(rad*2); 

Nun kannst du entscheiden was passiert: über/untersteigt der slope einen bestimmten Grenzwert, bewege den Wurm in die entsprechende x-Richtung (jeweils hangabwärts) und verbiete das Bewegen in die andere Richtung (hangaufwärts). Du musst dich hier übrigens nur um die Seitwärtsbewegung kümmern, auf/ab wird schon unter a und b erledigt.

[LilaQ]

So, leider seh' ich momentan vor lauter Bäumen den Wald nicht mehr. Bin seit 1,5 Tagen dran, und verbau mir hier glaub ich grade einiges.

Von daher nochmal kurz auf Anfang.

1. Wie mache ich am besten die Kollisionserkennung von meinem Bitmap (die Landschaft, die im Laufe des Spiels weiter zerstört wird) und meinem Wurm (MovieClip)? BitmapData.hitTest()? Wenn ja, mit Point, Rectangle, oder DisplayObject?

2. Wie suche ich mir dann am besten(!) den Anfang der Map?
Momentan mache ich das mit getPixel() und vergleiche mit 0. Ist aber auch doof, weil sobald schwarz auf der Map erscheint, glaubt die Funktion den Mapanfang gefunden zu haben.

Ich weiß, ist alles wieder 2 Schritte zurück, aber irgendwo hapert es grade und ich kommt nicht dahinter. (Mal werden die Würmer immer wieder in den Himmel gesetzt beim Bodenkontakt, mal zittern sie nur hoch und runter, mal laufen sie nur waagerecht und bergab) - also ich hab grad irgendwo den Wurm drin, beim denken oder beim Programmieren.

Ich hoffe ihr könnt mir da nochmal hilfreich in die Seite treten, bevor ich mir hier zuviel Klumpatsch reinschreibe und nachher nicht mehr durchblicke

[shin10]

hi,

also wie versprochen hab ich nochmal geschaut. wie gesagt hab ich gerade einiges um die ohren. drum hab ich dir nur nen kleinen prototypen hingeschludert (also so richtig schludrig). was du brauchst sind zwei mcs: level und player
schau es dir einfach mal durch. ich denke als kleine inspiration wirds schon was taugen.

PHP-Code:

const TASTE_HOCH:uint = 38;
const TASTE_RUNTER:uint = 40;
const TASTE_LINKS:uint = 37;
const TASTE_RECHTS:uint = 39;

const g:Number = 9.81 * 2 / stage.frameRate;
const steigungMax = 3;

player.speed = 2;
player.speedX = 0;
player.speedY = 0;
player.sprungkraft = 10;
player.bodenKontakt = level.hitTestPoint(player.x,player.y,true);


var keys:Array = new Array(256);
for (var i:uint=0; i<keys.length; i++)
{
    keys[i] = false;
}

function kdh(e:KeyboardEvent):void
{
    keys[e.keyCode] = true;
}
function kuh(e:KeyboardEvent):void
{
    keys[e.keyCode] = false;
}
function efh(e:Event):void
{
    playerInput();
    physics(player);
    info.text = "" + player.bodenKontakt.toString() + "\n" + clippingOben(player) + "\n" + clippingUnten(player);
}

function playerInput():void
{
    if (keys[TASTE_LINKS] == true && keys[TASTE_RECHTS] == false)
    {
        player.speedX =  -  player.speed;
    }
    else if (keys[TASTE_LINKS]==false && keys[TASTE_RECHTS]==true)
    {
        player.speedX = player.speed;
    }
    else
    {
        player.speedX = 0;
    }

    if (keys[TASTE_HOCH] == true && player.bodenKontakt == true)
    {
        player.speedY =  -  g * player.sprungkraft;
    }
}
function physics(obj:MovieClip):void
{
    obj.speedY += g;
    if(obj.bodenKontakt){
        //kontollverlust >> rutschen
        if(abrutschen(obj)){
            return;
        }
    }
    schwerkraft(obj);
    clippingUnten2(obj);
    gehen(obj);
}
function abrutschen(obj:MovieClip):Boolean{
    if(level.hitTestPoint(obj.x-1, obj.y-(steigungMax+1), true) && level.hitTestPoint(obj.x+1, obj.y+(steigungMax+1), true) == false){
        obj.x ++;
        return true;
    }else if(level.hitTestPoint(obj.x+1, obj.y-(steigungMax+1), true) && level.hitTestPoint(obj.x-1, obj.y+(steigungMax+1), true) == false){
        obj.x --;
        return true;
    }
    
    return false;
}

function gehen(obj:MovieClip):void
{
    var vX:int = obj.speedX/(Math.abs(obj.speedX));
    for (var i = Math.abs(obj.speedX); i>0; i--)
    {
        if (level.hitTestPoint(obj.x + vX, obj.y - steigungMax, true) == false)
        {
            obj.x +=  vX;
        }
    }
    clippingUnten(obj);
}
function schwerkraft(obj:MovieClip):void
{
    var vY:int = obj.speedY/(Math.abs(obj.speedY));
    for (var i = 0; i<Math.abs(obj.speedY); i++)
    {
        if ((clippingUnten2(obj) == false || obj.bodenKontakt) && (clippingOben(obj)==false))
        {
            obj.y +=  vY;
        }
        else
        {
            return;
        }
    }
}
function clippingUnten2(obj:MovieClip):Boolean
{
    obj.bodenKontakt = level.hitTestPoint(obj.x,obj.y + 1,true);
    if (level.hitTestPoint(obj.x,obj.y,true) == false)
    {
        return false;
    }
    while (level.hitTestPoint(obj.x, obj.y, true))
    {
        obj.y--;
    }
    obj.speedY = 0;
    obj.bodenKontakt = true;
    return true;
}
function clippingUnten(obj:MovieClip):Boolean
{
    if (level.hitTestPoint(obj.x,obj.y,true) == false)
    {
        return false;
    }
    while (level.hitTestPoint(obj.x, obj.y, true))
    {
        obj.y--;
    }
    return true;
}
function clippingOben(obj:MovieClip):Boolean
{
    if (level.hitTestPoint(obj.x,obj.y - 1,true) == false)
    {
        return false;
    }
    while (level.hitTestPoint(obj.x, obj.y-1, true))
    {
        obj.y++;
    }
    obj.speedY = 0;
    return true;
}

stage.addEventListener(Event.ENTER_FRAME, efh);
stage.addEventListener(KeyboardEvent.KEY_DOWN, kdh);
stage.addEventListener(KeyboardEvent.KEY_UP, kuh); 


mfg

sx

[LilaQ]

Hey shin10,

danke dafür

Habe zwar einiges hinbekommen in der Nacht noch, aber besonders das Rutschen und das ClippingOben werd ich mir für das Spiel nochmal näher ranziehen von deinem Code.

Hilft schon sehr wenn man betriebsblind geworden ist vor dem vielen Coden und dann mal eine passende Lösung sieht

Hab direkt mal einen Screenshot von dem momentanen Stand gemacht, damit ihr auch mal seht worum es hier geht :>



Mfg
LilaQ

[shin10]

oha,

sieht ja schon recht fein aus. bin gespannt, wann wir das mal so richtig online auschecken können.

was das clippingOben angeht. da wollte ich noch was zu sagen. also erstmal braucht es sowas ja natürlich, dass man nicht von unten in eine wand reinspringen kann. ich hab jetzt all die funktionen mit nem einfachen hitTestPoint gelöst, wie du gesehen hast. es würde sich allerdings für dein spiel dennoch weiterhin der bitmap hittest anbieten weil so ein wurm ja nicht nur 3 oder 4 pixel hoch ist. das andere ist, dass die würmer ja auch aufeinander stehen können und sich gegenseitig behindern. daher würde ich das ganze mit einer art hitbox angehen. also ein stark abstrahierter wurm, der animationsunabhängig sowohl zum prüfen als auch als hindernis dient ...

vom prinzip her bleibt es sich aber ja dennoch recht gleich.
halt uns auf dem laufenden

mfg

sx

[LilaQ]

So, stehe leider momentan wieder vor einem größeren Problem.

Bis gestern konnten die Würmer beim Springen (ein Sprung geht nach oben und zur Seite, je nachdem in welche Richtung der Wurm schaut) immer noch in Objekte der Map "reinspringen". Durch das reinspringen werden sie im nächsten Berechnungszyklus auf den nächsthöheren Punkt gesetzt.

So lassen sich auch dünne Wände etc. einfach durchspringen. So sollte das ganze natürlich nicht sein.

Versuche jetzt seit knapp 10 Stunden eine Lösung für das Problem zu finden.
Wenn der Wurm von unten gegen eine Decke springt, soll er natürlich wieder nach unten abprallen.

Daher dachte ich mir, dass ich erst einmal eine Funktion schreibe, die die Pixel zwischen dem aktuellen Punkt und dem nächsten Punkt im Sprung überprüft (da diese ja beim Sprung mehr oder weniger übergangen werden).

Bin grad schon wieder leicht am verzweifeln und mir fällt auch einfach nichts mehr ein, was ich noch probieren könnte.

Daher werde ich auch nicht mehr viel erklären, sondern jetzt mal ein paar Ausschnitte aus meinem Quelltext posten, vielleicht kann mir da nochmal jemand auf die Sprünge helfen, sonst verlier ich hier bald noch Haare

private function gravityHandler(e:Event)		:void
		{
			//	Wenn der Wurm auf der Map steht
			if((wormHitTest(new Point(Worm(e.target).x, Worm(e.target).y)))&&(wormHitTest(new Point(Worm(e.target).x, Worm(e.target).y-1))))
			{
				Worm(e.target).VelocityY = 0;
				Worm(e.target).y = YcoordFromMap(Worm(e.target)) + 2;
				Worm(e.target).isFalling = false;
				
				//	Wenn der Wurm sich seitlich bewegen soll:
				if(Worm(e.target).VelocityX != 0)
					//	Steigung wird berücksichtigt
					//	Ist es zu steil, geht der Wurm nicht weiter
					if(!wormHitTest(new Point((Worm(e.target).x + Worm(e.target).VelocityX), (Worm(e.target).y - MAX_STEIGUNG)))) 
					{
						Worm(e.target).x += Worm(e.target).VelocityX;
						Worm(e.target).y = YcoordFromMap(Worm(e.target)) + 2;
						Worm(e.target).VelocityX = 0;
					}
			}
			
			//	Wurm fällt oder springt
			else 
			{
				Worm(e.target).VelocityY 	+= _curSettings.GRAVITY;
				Worm(e.target).y 			+= Worm(e.target).VelocityY;
				Worm(e.target).x 			+= Worm(e.target).VelocityX;
			} 
		}

Hab noch einiges rausgenommen um es übersichtlicher zu halten.

wormHitTest() prüft nur den übergebenen Punkt mit der Map und ob eine Kollision damit stattfindent

YcoordFromMap() findet nur den nächsthöheren Y-Punkt heraus für den übergebenen Wurm

Die Funktion die ich vorhin ansprach um die Punkte zwischen 2-Sprung-Stadien zu überprüfen habe ich so geschrieben (momentan nicht implementiert im gravityHandler):

private function kollisionZwischenPunkten(srcX:uint, srcY:uint, destX:uint, destY:uint)	:Array
		{
			var dx: uint = Math.abs(destX - srcX);
			var dy: uint = Math.abs(destY - srcY);
			var y: uint = srcY;
			var returnArray:Array = new Array();
			var step:Number = dy / dx;
			for (var i : int = srcX;i < destX;i++) 
			{
				if(wormHitTest(new Point(i, y)))
				{
					returnArray[0] = "true";
					returnArray[1] = i;	// X-Wert bei Kollision
					returnArray[2] = y; // Y-Wert bei Kollision
					return returnArray;
				}
				y += step;
			}
			returnArray[0] = "false";
			return returnArray;
		}

So, und im Endeffekt möchte ich eigentlich nur dass die Würmer nicht mehr durch Wände / Decken springen können, sondern davon abprallen -.-

Wäre wirklich ausserordentlich dankbar wenn mir da nochmal jemand mit helfen kann.

Danke euch im Voraus.

Mfg
LilaQ