Kollisionerkennung von Strichen

[TimeIsTheKey]

Hallo

Ich bräuchte ein paar Lösungsansätze. Hoffe ihr könnt mir helfen.
Ich möchte ein Stickman-Spiel programmieren und dazu müsste ich eine effiziente Lösung haben um zu erkennen, ob und wo sich Striche berühren.

Wenn ich es schaffe möchte ich ein normales Jump- and Run programmieren, während im Hintergrund alles mit Strich-Figuren abläuft (gezeichnet werden aber normale Bilder). Genauere Kollision mit einer halbwegs normaler Performance.

Im Prinzip geht es mir nur darum 2 transparente Bilder miteinander zu vergleichen. Sobald sich etwas überkreuzt muss ich herausfinden an welcher Stelle. Der banalste und einfachste Lösungsansatz wäre natürlich jedes Pixel einzeln durchzugehen, aber da gibt es sicher bessere Ansätze/Methoden.

Möchte nicht mehr die 2D-Figuren in Java verwenden (z.B. Rectangle).

Danke im Voraus für jegliche Hilfe!!

Bilderklärung: Ich habe mal ein Bild erstellt um euch mal zu zeigen was ich meine. Findet ihr im Anhang. Bild 1 ist der einfachste Fall. 2 Striche kreuzen sich. Beim Schnittpunkt sollte eine Kollision festgestellt werden. Bei Bild 2 trifft der Kreis den Strich gleich zwei mal. Bedeutet 2 Kollisionen. Und bei Bild 3 sind die nur farbig markiert. Dadurch könnte ich herausfinden welche Stelle sich treffen. Ist nur eine Idee. Bei Bild 4 sieht man wozu die Farben gebraucht werden könnten.
Ich müsste dann jeweils auch immer Wissen an welcher Stelle die sich durchkreuzen.

MfG

 

[Marco13]

Klingt irgendwie widersprüchlich. Einerseits geht es um Linien, was erstmal mathematisch und verktoriell klingt, dann doch um transparente Bilder, was nach Pixelgenauer Kollisionserkennung klingt und jeden vektoriellen Ansatz ad absurdum führen würde... und dann noch die Aussage, dass du Dinge wie Rectangle2D und Line2D nicht verwenden willst, die einem das Leben doch sooo viel einfacher machen würden. Wenn's low-level sein soll: Auf Geometric Tools gibt's jede Menge C-Code, der leicht nach Java portiert werden kann...

 

[TimeIsTheKey]

Klingt irgendwie widersprüchlich. Einerseits geht es um Linien, was erstmal mathematisch und verktoriell klingt, dann doch um transparente Bilder, was nach Pixelgenauer Kollisionserkennung klingt und jeden vektoriellen Ansatz ad absurdum führen würde... und dann noch die Aussage, dass du Dinge wie Rectangle2D und Line2D nicht verwenden willst, die einem das Leben doch sooo viel einfacher machen würden. Wenn's low-level sein soll: Auf Geometric Tools gibt's jede Menge C-Code, der leicht nach Java portiert werden kann...

Danke erstmal für deinen Beitrag.

Ich habe die Idee von einem anderen Spiel, aber ich weiss leider nicht mehr wie es heisst. In der Alpha-Phase wurde es im Debug-Mode gezeigt und dort konnte man sehr gut sehen, dass im Hintergrund alles so abläuft. Das Spiel gibt es auf der PS3 und war ein grosser Erfolg.

Ich hatte schon mit Rectangle und Line gearbeitet, aber mir geht es eigentlich nur darum, diesen Lösungsansatz umzusetzen. Vielleicht war's ein bisschen blöd erklärt. Also:
Ich habe pro sichtbares Objekt 2 Grafiken auf denen alles drauf ist. Das erste Bild sind die normalen Bilder die man dann beim Spielen sehen wird. Auf dem zweiten Bild sind nur die Bereiche mit Striche eingezeichnet, die auf Kollision abgeprüft werden soll. Der Hintergrund der Bilder ist transparent.
Jedes Objekt wird während beim Durchlauf mit allen anderen (später unterteile ich das in Bereiche um Performance zu sparen) Objekten geprüft. Dazu würde ich jeweils 2 Objekte in ein Bild einsetzen und dann schauen ob die sich irgendwo überlagern. Falls ja müsste ich sehen wo.

Ist das einigermassen verständlich? Hoffe ich mal.
Ich habe ein Beispiel-Bild gemacht (im Anhang). Dort siehst du zuerst das normale Bild, dass der Spieler vor sich haben wird und dann im Hintergrund der Bereich der auf die Kollision abgeprüft wird. Könnte natürlich dicker sein. Hab das jetzt einfach mal so schnell ich konnte gezeichnet also erwarte keine Qualität. Beide Bilder wären dann auf 2 verschiedenen Bildern und jedes normale Bild hätte im zweiten Bild an der gleichen Stelle ein Strich-Männchen.

Würde dann einfach mit diesen Strichmännchen auf Kollision überprüfen und beim Zeichnen die echten Bildern nehmen.

Gruss

 

[Marco13]

Hmja... so ganz kapier' ich's noch nicht: Warum erwartest du dir einen Geschwindigkeitsvorteil, wenn du statt eines Bildes mit der Figur ein Bild mit (eventuell sogar noch dickeren) Linien für die Kollisionserkennung verwendest? Wenn das mit den Linien wirklich ein Bild sein soll (was es bei diesem PS3-Spiel mit ziemlicher Sicherheit nicht war) bleibt einem ja doch wieder nichts anderes übrig, als alle Pixel durchzugehen, nachzusehen, ob sie schwarz sind, und zu schauen, ob ein anderes Bild an dieser Stelle auch einen schwarzen Pixel hat... da kann man ja gleich noch auf Rot, Grün und Blau (bzw. auf "Nicht-Durchsichtig") testen und gleich das richtige Bild verwenden...?! :bahnhof:

 

[TimeIsTheKey]

Hmja... so ganz kapier' ich's noch nicht: Warum erwartest du dir einen Geschwindigkeitsvorteil, wenn du statt eines Bildes mit der Figur ein Bild mit (eventuell sogar noch dickeren) Linien für die Kollisionserkennung verwendest? Wenn das mit den Linien wirklich ein Bild sein soll (was es bei diesem PS3-Spiel mit ziemlicher Sicherheit nicht war) bleibt einem ja doch wieder nichts anderes übrig, als alle Pixel durchzugehen, nachzusehen, ob sie schwarz sind, und zu schauen, ob ein anderes Bild an dieser Stelle auch einen schwarzen Pixel hat... da kann man ja gleich noch auf Rot, Grün und Blau (bzw. auf "Nicht-Durchsichtig") testen und gleich das richtige Bild verwenden...?! :bahnhof:

Stimmt, beim PS3-Spiel war es sicher nicht diese Methode. Allerdings war es eine ausgereifte Physik-Engine und am Körper selbst wurden verschiedene 2D-Elemente verwendet die zusammen verknüpft waren. Da ich allerdings noch weit entfernt bin sowas zu schreiben, dachte ich mir, es sei einfacher mit vorgezeichneten Strichen vorzudefinieren. Einen Geschwindigkeitsvorteil erhoffe ich mir nur, wenn jemand dafür einen guten Lösungsansatz hätte. Alles einzeln abzuklappern wäre die primitivste Lösung.
Ansonsten müsste ich allen Bildern einzeln Striche und Körper zuweisen.

 

[Marco13]

Ja... sorry, ich sehe jetzt nicht, wo man da irgendwas mit Strichzeichnungen gewinnbringend einsetzen könnte. Vielleicht hat ja jemand anderes eine Idee... Quaxli oder Apo oder so...!?

 

[Quaxli]

...Da ich allerdings noch weit entfernt bin sowas zu schreiben...

Klingt für mich nach dem Schlüsselsatz und ist auf keinen Fall böse gemeint
Ich würde zunächst mal ein normales kleines Spiel schreiben und nur die sichtbaren Grafiken/Sprites auf Kollision prüfen. Einfach zur Erfahrungssammlung.

Die oben erklärte Vorgehensweise mit den Strichen ist mir auch neu. Hast Du da ggf. mal einen Link? Wenn ich einem Objekt/Sprite weitere Objekte/Sprites zuweisen wollte würde ich mir eine entsprechende Klasse schreiben, die mir das ganze verwaltet. Allerdings würde ich immer noch die Vordergrund-Grafiken abgleichen - aus den von Marco13 oben dargelegten Gründen.

Vielleicht könnte man sich etwas basteln, daß die Vordergrundgrafik in Striche "übersetzt", aber ob das performant und eindeutig ist? :bahnhof:

Vielleicht hat ja sonst jemand eine Idee?

 

[Opi3]

Ich habe in as3 mal eine 'kleine' Physik-Engine geschrieben und könnte mir vorstellen,
das einfach jede Figur ein 'strichskelet' hat.
Zumindest bestanden in meiner Engine alle Körper nur aus strecken (kreise gab es nicht wie gesagt 'klein' )
Die Striche werden jetzt nicht 'Pixel für Pixel' auf Kollision geprüft sondern man rechtet sich einfach aus wo und ob sich zwei der strecken schneiden.

Das man die strecken nachher sieht war bestimmt nur eine Debugger-funktion.

^^Vermutung über Vermutung

Opi3