Polygonbasierte Kollisionsabfrage [TopDown Engine]

  • GM 8

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Polygonbasierte Kollisionsabfrage [TopDown Engine]

    Abend Community,

    seit einigen Tagen arbeite ich an einer neuen TopDown Engine. Bis jetzt lief alles mehr oder minder gut, doch irgendwann kommt ja immer der Punkt wo man stundenlang im selben Code rumrührt und nichts mehr gebacken kriegt :thumbsup:
    Nach dem fünften Tage Dauerprogrammieren mit jeweils großzügigen 6 Stunden Schlaf scheint mein Hirn die Konsistenz eines Smoothies erlangt zu haben, denn klare Gedanken zu fassen gestaltet sich mitunter als schwierig und selbst das Verfassen dieses Textes gleicht eines mentalen Marathons, daher entschuldigt, falls ich mich im weiteren Verlauf unglücklich artikulieren sollte.

    Um langsam zur Sache zu kommen, bis jetzt habe ich eine N-Gon basierte Lichtengine so wie Kollisionsengine geschrieben. Beide laufen Hand in Hand miteinander und beziehen als Rohdaten die Eckpunkte eines Polygons (N-Gons) für alle weiteren Berechnungen. Hier wird zwichen statischen und dynamischen Objekten unterschieden. Die Eckpunkte (von nun an "casts") werden für die dynamischen in Echtzeit berechnet (dies geschieht zur Optimierung nur wenn benötigt, etwa wenn im Einflussbereich eines Lichtkegels oder bei "Kollision" (simples place_meeting() )mit dem Spieler). Bei bspw. einem rotierenden Würfel werden die casts also nicht neuberechnet, wenn diese momentan keine Bedeutung haben.

    Alle N-Gone haben Grundlegend folgende Attribute :
    Eine Variable cast_points, diese hält die Anzahl (n) an casts(Eckpunkten).
    Ein Array cast_x_raw[n] sowie cast_y_raw[n], diese halten die casts als offsets relativ zu x,y des Objekts.
    Als Grundlage habe ich 2 Objekt-templates erstellt, ein Rechteck :: und ein Dreieck .:
    Da diese die casts als sprite_xoffset/sprite_yoffset enthalten, können diese im roomeditor beliebig transformiert werden.
    Die Engine kann allerdings mit -n casts umgehen, es können also komplexere zusammenhängende Strukturen modelliert werden.
    Die oben gelisteten Arrays halten die Offsets für die untransformierte Figur, nach Erstellen der Instanz werden mindestens einmal die casts geupdated und in zwei neue Arrays cast_x[n] und cast_y[n] geschrieben.

    Rechteck:
    Spoiler anzeigen

    GML-Quellcode

    1. ///caster_init(static, solid)
    2. cast_points = 4;
    3. cast_x_raw[0] = -sprite_xoffset;
    4. cast_y_raw[0] = -sprite_yoffset;
    5. cast_x_raw[1] = -sprite_xoffset+sprite_width;
    6. cast_y_raw[1] = -sprite_yoffset;
    7. cast_x_raw[2] = -sprite_xoffset+sprite_width;
    8. cast_y_raw[2] = -sprite_yoffset+sprite_height;
    9. cast_x_raw[3] = -sprite_xoffset;
    10. cast_y_raw[3] = -sprite_yoffset+sprite_height;
    11. static = argument0;
    12. is_solid = argument1;
    13. if (!static) {
    14. global.dynamic_casts += 1;
    15. }
    16. caster_update(image_angle);
    Alles anzeigen



    Bis jetzt alles super, caster_update() wird hier also einmal ausgeführt und berechnet die transformierten casts.
    Beim Licht ist auch alles in Ordnung, alle casts werden richtig berechnet.

    Nun kommen wir jedoch zum Problem, der Kollisionsabgrage :
    Hier habe ich mir "perfect collsions" mit sliding als Ziel gesetzt, was sogar annähernd funktioniert.
    Wichtig ist, dass der Spieler auch in Beweglichen Objekten niemals hängen bleibt, wir also eine Art softbody-collision haben, daher auch der Ansatz mit den Polys.
    Beim herkömmlichen Collision-Event des Spielers mit dem Parent wird mein Kollisionsscript aufgerufen.
    Hier durchlaufen wir eine Schlaufe n-mal (n=other.cast_points) und verbinden die casts zu Linien (cast_x[0]/cast_y[0] zu cast_x[1]/cast_y[1]...)
    Der nächste Punkt lässt sich also mit [n+1] finden. Wir müssen fragen ob [n+1] == cast_points entspricht, ist dies der Fall gibt es keinen Punkt [n+1], wir müssen also zum ersten Punkt [0] verbinden. Somit haben wir individuelle collision_lines welche wir auf Kollision testen können. Trifft nun eine Seite zu, berechnen wir den Normalenvektor dieser (dies bin ich vorher weit komplizierter angegangen, ich bin mir sicher dies ist der Knackpunkt, da ich nun einfach die point_direction um 90Grad drehe, allerdings finde ich keinen passenden Ansatz). Zuletzt bewegen wir den Spieler in Richtung des Normalenvektors, bis keine Kollision mehr zutrifft.

    Hier müsste noch ein weiterer Faktor einspielen um zu bestimmen, ob der Spieler in Richtung der Normalen hin oder von ihr weg bewegt werden muss.
    Da ich auf keine gescheite Lösung komme, mir aber denke dass dieses Problem relativ simpel zu lösen ist, möchte ich euch um Rat bitten.

    Die Problematik äußert sich in sofern, als dass der Spieler an Ecken bzw. sehr dünnen Objekten(allerdings nur von einer Seite) in die falsche Richtung "teleportiert" wird, da er womöglich mit gegenüberliegenden Seiten kollidiert (?) und so in die Falsche Richtung bewegt wird.

    Eventuell könnte man den Mittelpunkt der Figur errechnen und dann mit den Koordinaten des Spielers vergleichen um die Richtung zu bestimmen.
    Hier bin ich nun auf helle Köpfe angewiesen, denn Mathe war nie meine Stärke und mit Trigonometrie wurde sich auch im Matheunterricht leider nie wirklich beschäftigt.
    Ich habe in den letzten Tagen bestimmt öfters sinus/cosinus verwendet als vorher jemals in meinem Leben, mir fehlt defacto das Verständnis mathematischer Funktionen dieses Gebiets und die Leichtigkeit diese anzuwenden.

    Anbei das jetzige Kollisionsscript(Aufgerufen im Collision-Event des Spielers mit dem Parent) :
    Spoiler anzeigen

    GML-Quellcode

    1. ///player_collision(resolution)
    2. var resolution;
    3. resolution = argument0;
    4. if (other.is_solid) {
    5. for (i = 0; i < other.cast_points; i++) {
    6. var ii;
    7. if (i+1 = other.cast_points) {ii = 0;}
    8. else {ii = i+1;}
    9. if (collision_line(other.x + other.cast_x[i],other.y + other.cast_y[i],other.x + other.cast_x[ii],other.y + other.cast_y[ii], id, true, false) != noone) {
    10. var x1,y1,x2,y2,dir;
    11. x1 = other.x + other.cast_x[i];
    12. y1 = other.y + other.cast_y[i];
    13. x2 = other.x + other.cast_x[ii];
    14. y2 = other.y + other.cast_y[ii];
    15. dir = point_direction(x1,y1,x2,y2)-90;
    16. while (place_meeting(x, y, other.id)) {
    17. //playerHSpeed = 0;
    18. //playerVSpeed = 0;
    19. x = x+lengthdir_x(-resolution,dir);
    20. y = y+lengthdir_y(-resolution,dir);
    21. }
    22. x = round(x);
    23. y = round(y);
    24. }
    25. }
    26. }
    Alles anzeigen



    Hier habe ich euch noch eine kleine Demo zusammengeschmissen an der praktisch alle Fehler repliziert werden können :

    Steuerung : W A S D, Maus
    F- Taschenlampe an/aus
    Enter- Debug Overlay, malt casts, Mittelpunkte der collision-lines sowie center of mass. Schaltet weitere Funktionen frei(siehe unten).
    (wenn Debug Overlay an):
    K- Zerstört letztes Licht
    N- Zerstört letzten dynamischen Caster
    V- VSync an/aus
    X- Antialiasing 0,2,4,8
    Y- aktiviert/deaktiviert alle Lichter
    Mausrad-Helligkeit der Umgebung

    DOWNLOAD DEMO

    Zuletzt noch was fürs Auge, Screenshots sind von "alt" nach neu.

    Danke für jegliche Hilfe/Einwände/Tipps etc !

    -Rhazul
    Bilder
    • pic1.png

      295,23 kB, 1.366×768, 619 mal angesehen
    • pic2.png

      641,54 kB, 1.366×768, 620 mal angesehen
    • pic3.png

      451,82 kB, 1.366×768, 612 mal angesehen
    132 little bugs in the code. 132 little bugs. Fix a few, set the compiler to stew, 172 little bugs in the code... :vogel:
  • Wow das ist echt cool und das Licht ist dir auch sehr gelungen.
    Ich würde auch gerne so eine Licht engine machen aber weis nicht wie man die macht :(.
    Aber die Engine ist super!!
    Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
    Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

    Willst du mit mir auf Discord Chatten/Quatschen?
    Meine Husi's Tutorial Reihe
  • Woooow echt super! Würde mich echt freuen, wenn da ein Spiel draus werden würde!!!! Allerdings hab ich irgendwie das Gefühl, dass alles ein bisschen flüssiger laufen könnte. Dass der Rechner also grad so an seine Grenze kommt. Vielleicht ist das aber auch nur die Steuerung die das vermittelt!? (Kenn mich leider nicht aus wie ich das nachprüfen könnte)
  • Also bei mir läuft das super so über die 100 fps. Ich glaube dein Rechner ist nicht so ganz schnell.

    PS: Du kannst ja mal ein tut darüber machen. Aber man merkt schon kaum das es überhaupt eine Frage ist :D
    So wie du alles aufgebaut hast sieht das aus als wenn du ein Spiel veröffentlichst. Sehr viel Text und informativ.
    Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
    Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

    Willst du mit mir auf Discord Chatten/Quatschen?
    Meine Husi's Tutorial Reihe
  • Also ich kann nur soviel sagen, mein Laptop aufdem ich imo. progge ist fast 5 jahre alt, die Demo läuft mit ca 120 Fps. Wenn ich die Lichter deaktiviere, komme ich auf 300-400 Fps. Ich habe sogar schon zu testzwecken ein Horrorgame erstellt welches ca 50MB fasst.B Das habe ich auf Android geportet und es lief mit 50 Fps.
    Daher kann es nur an deiner Hardware liegen :----S

    Der Fehler mit der Kollision besteht übrigens immernoch und ich wäre froh, wenn jemand mit helfen könnte :huh:
    132 little bugs in the code. 132 little bugs. Fix a few, set the compiler to stew, 172 little bugs in the code... :vogel:
  • Vorweg: Mein Wissen ist recht begrenzt, was den GameMaker und GML angeht, aber ich kann ja meinen Senf bzw. meine Gedanken dazu dazugeben. Vielleicht bringt es dich ja auf den richtigen Gedanken.

    Also; was wir wissen ist, dass der Spieler nur dann über das Objekt "springt", wenn er mit einer dünnen Seite eines Objekts kollidiert (falls dir mal langweilig wird kannst du ja mal gucken wie dünn so ein Objekt, in Pixel, sein muss, damit es "übersprungen" wird. Vielleicht findet sich dieser Wert dann auch im Code wieder). Diese Seite des Objekts muss aus der Verbindun der ersten und letzten Casts bestehen. Demnach müsste irgendwo zwischen diesen beiden Casts der Fehler liegen.
    Beim Überfliegen des Collision-Scripts ist mein Blick an "round()" hängen geblieben. Da round() anders rundet, als man(oder ich zumindest) es aus der Schule kennt, könnte sich dort der Fehler eingeschlichen haben - so mein erster Gedanke dazu. Wenn man weiter überlegt, müsste dies den Fehler dann auch an allen Seiten hervorrufen können. Tut es aber nicht. Meh.
    Dann bin ich in der kurzen Zeit (Freistunde! Bin gleich wieder in der Schule) nicht dahinter gekommen, was es mit der Variable "resolution" auf sich hat. Allerdings kann dise Variable auch gut für den "sprung" verantwortlich sein. Ich würde versuchen die maximale Distanz zu limitieren. Wenn die Distanz aber zu klein wird, und der Spieler dadurch nicht über das Objekt "springen" kann, steckt er fest. Also muss er in die andere Richtung gehen. Also müsste etwas mit der Richtungsangabe bei der Kollision des Spielers mit einem Objekt an der erster-Cast letzter-Cast Seite nicht stimmen.

    So, dass ist jetzt vielleicht nicht ganz das, was du gehofft hast, und auch ziemlich ungeordnet, aber ich gucke mal, ob ich später auf etwas sinnvolles kommen kann. Ansonsten könntest du versuchen ein Script extra für die fehlerhafte Seite zu schreiben.

    Das ist dann alles, was mir momentan und auf die Schnelle dazu eingefallen ist.


    Skotchy~
    "Ich sollte schlafen gehen"

    ~Pika-Pika~
  • Hey, danke für deine Mitüberlegungen!
    Um direkt mal ein paar Sachen aufzuklärenn : das round x/y wird erst nach der for Schleife angewand. Die x,y Position des Spielers wird hier einfach nur auf ganze Werte gerundet sobald keine Kollsion mehr auftritt. Dies verhindert Ruckeln in den Grafiken/dem view, da der Spieler sich ansonsten zwichen zwei pixeln befinden könnte (zB x 3.124, y 13.3445 wird zu x 3, y 13. Wenn durch diese Rundung eine Kollision hervorgerufen würde, liefe das ganze wieder von vorne ab und der Spieler würde wieder aus dem kollidierenden Objekt gedrückt. Da die maximale Rundung immer kleiner 1 ist, kann hier der Fehler nicht liegen. Zur resolution, diese wird dem script als Parameter übergeben und beträgt in der Demo 0.1; das heißt, das der Spieler jeden Schleifendurchlauf maximal 0.1 pixel auf x und y verschoben wird.

    Dass das Problem nur bei dünnen Figuren besteht kann ich nicht komplett bestätigen, auch bei größeren Rechtecken gibt es mindestens eine Seite/Ecke welche Probleme bereitet.

    Zeile9-11 meines Kollisionsscripts stellen den wrapper dar, welcher den letzten mit dem ersten Punkt verbindet. Meinen Tests zufolge, dem Debugoverlay (welches abgewandelten code hiervon zum drawen der Verbingungen benutzt) und meinen Gedankengängen zufolge ist hier nichts verkehrt.

    Ich bin mir sicher, dass in Zeile 21 angesetzt werden muss. Die Richtungsbestimmung erfordert einen Komplexeren Ansatz.

    Für jede weitere Hilfe wäre ich sehr dankbar.
    132 little bugs in the code. 132 little bugs. Fix a few, set the compiler to stew, 172 little bugs in the code... :vogel:
  • Dazu ein weiteres Gedankenpacket:
    Auch wenn das round() nach der Schleife angewandt wird, so kann es das Objekt theoretisch wieder in eine neue Kollision runden (Beispiel: <2.1 = Kollision, round(2.2) = 2, 2<2.1, => Kollision). Zum ruckeln; da habe ich nach einem etwas ausführlicherem Test einen weiteren Fehler gefunden, der mit dem gesamten Problem zusammenhängen könnte: Geht man in/an die weiß markierten Stellen(wie im Bild zu sehen), springt der Spieler ein Stück zurück. (Habe eben auchnoch herausgefunden, dass dieser Fehler auch and der kurzen Seite des großen rotierenden Dreiecks im "Norden" auftritt)
    Bei dem Problem mit dünnen Figuren kann ich dir zustimmen: sie sind nicht die einzigen Übeltäter. Der Fehler kann an jeder Ecke reproduziert werden, allerdings nicht von jeder Richtung, wie es scheint.
    Für die Richtungsbestimmung denke ich mir morgen einen Ansatz aus und bastle etwas herum (Wenn dann noch Bedarf besteht ;) ). Um zu gucken, ob auch wirklich die Richtungsbestimmung fehlerhaft ist, könntest du versuchen sie zu visualisieren oder dir den Wert anzeigen lassen.
    Zu kompliziert sollte man dabei allerdings auch nicht denken.


    Skotchy~
    Bilder
    • Test.png

      811,73 kB, 965×648, 529 mal angesehen
    "Ich sollte schlafen gehen"

    ~Pika-Pika~
  • Durch ändern des Vorzeichens der -90 bei "dir" lässt sich das ganze Umdrehen, nun sind die Kollisionen von den jeweiligen 2 anderen Seiten Perfekt.
    Es liegt also aufjedenfall daran, wie ich vermutet hatte. Das ruckeln, welches du zuvor erwähntest, ist mir auchschon aufgefallen. Ich denke es ergibt sich durch das Zusammenspiel der falschen Richtungen für x/y Achse, der SPieler wird desshalb immer hin und her geworfen.

    Wir müssen jetzt nurnoch herausfinden, wie wir "dir" richtig berechnen.
    132 little bugs in the code. 132 little bugs. Fix a few, set the compiler to stew, 172 little bugs in the code... :vogel:
  • Ich habe nun ein wenig herumprobiert und bin zu folgendem Ergebnis gekommen:
    Das Problem ist sehr wahrscheinlich, dass der Spieler die gegenüberliegende Wand berührt, und dadurch ein weiteres Kollisions-Event auslöst, welches zu dem Fehler führt. Die Berechnung für "dir" müsste richtig sein.
    Versuche mal folgendes:
    Bewege den Spieler nicht aus der Wand, sondern zur Wand, indem du "x/yprevious" benutzt, um auf die Position des letzten Steps zu kommen damit der Spieler die Wand nicht berührt, und "dir" um 180 erhöhst/verringerst oder "resolution" positiv benutzt, um auf die Wand zuzusteuern.


    Skotchy~
    "Ich sollte schlafen gehen"

    ~Pika-Pika~