Jump and Run Game -- Kollisionsabfrage

[DarKestSun]

Tag, ich und 3 andere arbeiten an einem Jump and Run Game, die Maps dafür soll man im Paint zeichnen können.
Unser System funktioniert so:
* Eine Schwarz - Weiß Map wird gezeichnet, der Spieler kann schwarze Pixel nicht berühren (Boden, Wand...)alle anderen werden ignoriert
* Eine frabige Map wird am Bildschirm dargestellt, die Schwarz -Weiß Map ist nicht sichtbar

Die Pixel der Map werden in ein Array gelesen, true für eine schwarzes Pixel, false für irgend ein anderes.
Später prüft man ob der spieler ein schwarzes pixel berührt, falls es so ist, darf er nicht weitergehen.

wir prüfen das so ab:

for - schleife testet 10 pixel rechts des spielers ab (nur wenn er nach rechts geht)
for - schleife testet 10 pixel unterhalb des spielers ab, wenn er nach unten fällt. wird ein schwarzes pixel festgestellt, endet der fall.

das ganze baut auf threads auf.

unser problem ist (die collision funktioniert schon), dass das ganze sehr systemauslastend ist. vielleicht gibt es ja eine einfachere möglichkeit für eine Kollisionsabfrage?

Danke für jede Antwort

 

[Sky]

Die Ursache liegt in Zeile 249.

Nein, jetzt mal im Ernst: Ohne konkrete Quellen kann man zu einem Performance-Problem (was hier ja anscheinend vorliegt...) nichts konkretes sagen.

Allgemein läßt sich sagen, dass die Ursache in
* inperformanter Thread-Programmierung
* Zu häufiger Aufruf von repaint() (evtl. für die Map!?)
* noch 1000 weiteren Details
liegen kann.

 

[0xdeadbeef]

Wozu denn genau die For-Schleife?
In aller Regel sollte es doch ausreichen, den Spieler für Kollisionen als Rechteck zu betrachten. Je nach Bewegungsrichtung muß man dann halt die linke oder rechte Seite des Rechtecks prüfen. Wenn es keine komplexen Hindernisse gibt, muß dann nur einen einzigen Pixel prüfen, bevor man den Spieler z.B. nach rechts bewegt usw.

 

[DarKestSun]

tu ich ja.
ich prüfe in einer for - schleife den zielbereich, kleine skizze:

||| *
||| *

die | symbolisieren den spieler, * ist das ziel pixel.
der spieler ist ca. 50 pixel hoch, das macht 50 pixel die ich prüfen muss.

der quellcode ist ziemlich viel, ich frage ja nur um ein prinzip, wie die collision funzt.

mit einem pixelgrabber lses ich die map in ein array ein mit x - y - koordinaten. später prüfe ich ob
array[player.x+20][player.y] true ist, dann ist dort ein schwarzes pixel.
weil der spieler 50 pixel hoch ist, prüfe ich das ganzemit 50 verschiedenen y - werten.

bei 50 fps ist das anscheinend zu aufwändig.

 

[TRunKX]

||||||||||||||*
||||||||||||||
||||||||||||||
||||||||||||||
||||||||||||||
||||||||||||||*
||||||||||||||
||||||||||||||
||||||||||||||
||||||||||||||
||||||||||||||*


So ssagen wir der Soieler will nach Rechts dann sind das alle FElder die du abfragen musst nicht 50 sondern nur die 3.
oder mach von mir aus 10 fals es spitze "schwarze kanten gibt" Aber versuch die menge der Abfragen so gering wie möglich zu halten .... achja tu sowas immer itterativ!


kannste ja mal ne Demo eures Games hochstellen!

 

[DarKestSun]

Danke mal für deine Mühe...
aber ich suche ein anderes System, es sei denn die guten Spiele machen das auch so.
Es wird eh nur jedes 3. Pixel geprüft, das Problem ist, dass ich pro Schritt 5 Pixel weit nach rechts gehe, damit ich nicht 5*3 Pixel prüfen muss, prüfe ich nur die ZielSpalte.

Das Problem ist, dieses System funktioniert bei >50 fps nicht mehr einwandfrei.
verschieden verbesserungen wurden schon gemacht, darum frag ich ob es eine ANDERE, BESSERE Variante gibt, vielleicht irgendwie mit grafischen Befehlen oder weiß der Geier was, hauptsache besser als 50 mal pro sekunde eine for-schleife durchlaufen zu lassen.

ich stell bald mal ne demo hier rein, brauch aber zuerst noch das einverständnis meiner kollegen

 

[Jockel]

Hab den Thread jetzt nur überflogen, aber vielleicht hilft dir ja folgendes: http://www.joachimrohde.com/v4.0/Nehe/ogltut30d.php
Ist zwar für OpenGL + C geschrieben, aber die Theorie ändert sich ja nicht.

 

[Hansdampf]

bei 50 fps ist das anscheinend zu aufwändig

kann nicht sein.
Bei meinem Spiel wird JEDER Pixel von JEDER Grafik in einer for-Schleife gesetzt, dabei wird jedesmal getestet, ob der Pixel transparent ist.
Ich würde erstmal das mit den Threads knicken und mit nem Profiler schauen woran es liegt.

 

[EgonOlsen]

Ich würde erstmal das mit den Threads knicken...

Was ganz generell ein sehr guter Tipp ist. Threads für: IO (Netzwerk, evtl. HD u.ä.) und von mir aus für die KI in einem Schachspiel oder ähnlichem. Aber nicht für die Spiellogik oder das Rendern in einem Jump-n-Run. Es wirkt auf den ersten Blick sexy...das kenne ich, weil ich das selber mal gedacht habe. Aber es ist es nicht und spätestens auf Multiprozessor- oder auch HT-Maschinen bekommt man plötzlich Ergebnisse, die man so nicht haben wollte...

 

[DarKestSun]

und jetz?
ohne threats rendern, wie denn?
man muss ja irgendwie synchronisieren und in n- Zeitabständen arbeiten.

 

[0xdeadbeef]

Schreib Dir 'nen eigenen Scheduler. Die Zeitsychronisation kannst Du auch machen, indem Du die Zeit mißt die von einem Schleifendurchlauf des Schedulers zum nächsten vergangen ist.

Und nochmal zum Abtesten der Pixel zwecks Kollisionserkennung: pixelgenaue Kollisionserkennung mag man in gewissen Situation brauchen. Bei einem Jump & Run halte ich es aber für übertrieben, wenn es nur um Hindernisse geht. Dann sollten in der Tat ein einziger Punkt in Bewegungsrichtung oder halt mehrere bei komplexeren Hindernissen reichen.

 

[Reality]

Tach!
Wenn der Spieler bespielsweise 20 Pixel breit ist und 30 hoch, dann ist die Breite des Spielsfelds beispielsweise 20 * 200 = 4000 Pixels und die Höhe 30 * 30 = 600 Pixel.

Kollisionsabfrage: Spielfeldbreite / Spielerbreite

LG
Reality

 

[DarKestSun]

Boahh jetz lässt du mich schlecht dastehen...
lerne java noch...

scheduler, is das was besonderes oder meinst du einfach das ich zeit pro schleifendurchlauf mitzähle, ganz simpel eben.

ach ja und kollisionserkennung is leider doch mit mehr pixeln nötig.
unser jump'n run game wird in paint gezeichnet, es gibt runde objekte und schiefe ebene usw.
worauf wir besonders stolz sind ist, dass man berge rauflaufen kann, ab einem gewissen steigungsgrad geht dann nix mehr.

 

[dronus]

das beste ist, einfach das ganze bild einmal "abzutasten", und in eine byte[][]- array einzufüllen, und zwar ein byte pro pixel. ist zwar speicherverschwendung, aber der pixelgrabber ist so weit ich ihn kenne seehr langsam. ein byte-array ist so schnell, das du problemlos einige tausend pixel prüfen kannst.

 

[DarKestSun]

ja das hab ich ja gemacht
array[xpos][ypos], schon getan

das spiel soll eine art soldat-kopie sein, falls das jemand kennt.
man soll mit schusswaffen rumballern usw.
und die kugeln müssen einschlagen, bei einem maschinengwehr sind das viele kuglen und das heißt viel collision.

rumlaufen und springen geht schon, aber mit kugeln wird das bisherige system zu aufwändig, die laufbahn kann 200 pixel lang sein oder länger, daher ist das jetzige system ziemlich aufwändig.

es funzt halt net so gut

 

[dronus]

Wenn du die Kugeln wirklich 200 Pixel weit schiesst und dabei sogar ein 1-pixel-breites hinderniss treffen willst ist das recht schwierig...
da schlagt ich dir eine "Quadtree"-Technik vor... recht anspruchsvoll, aber von der Performance kaum zu schlagen..
Such mal im netz nach Quadtree oder Octree (das selbe für 3d)

 

[Hansdampf]

was soll denn da bitteschön ein Quadtree bringen, er checkt doch die Hindernisse in einem int [][] (ich hoffe mal, dass es int[][] ist und kein byte[][]... besser wäre übrigens ein int[], da kannst du mit [x+y*breite] den betreffenden Pixel(x,y) holen, bekommst du mit .getRaster().getDataBuffer().getData()).
Zu den Schüssen: Richtung ausrechnen, normalisieren und dann halt die Richtung abtasten, Pixel für Pixel. Sollte keine Geschwindigkeitsprobleme geben, ausser du hast 50000 Kugel auf einmal.

 

[0xdeadbeef]

Man könnte sich aber schon intelligentere Algorithmen vorstellen als die "brute force" Methode mit dem großen int-Array.

Beispiel "Schuß trifft Spieler?": legt man um die Spieler und die Schüsse jeweils Rechtecke, die alle Pixel des Objekts umschließen, kann man zunächst die schnelle Rechteckprüfung machen: liegt Rechteck Schuß (teilweise) in Rechteck Spieler? Falls nicht, lohnt sich eine pixelgenaue Prüfung nicht. Falls das Schuß-Rechteck auch nur teilweise im Spieler-Rechteck liegt, kann man dann für den Bereich der Überschneidung pixelgenau prüfen.

Um so kleiner die zu prüfenden Objekte sind, um so kleiner ist natürlich der Vorteil der Rechteckmethode, was die reine Kollisionsprüfung angeht. Man darf aber nicht vergessen, daß man für die Kollisionsprüfung per Rechteck überhaupt keine Updates einer Kollisionsmaske (int-Array) machen muß. Und der Aufwand dafür dürfte nicht unerheblich sein.

Für die Kollisionsprüfung der Spieler und Kugeln mit dem Hintergund bietet sich die Idee mit dem int-Array schon eher an, denn hier muß der int-Array nur einmalig erzeugt werden - vorausgesetzt der Level ist statisch.
Falls der Level sich ändern kann, hat man natürlich auch wieder das Problem, das man die Kollisionsmaske bei jeder Veränderung des Levels (Bombe sprengt Teil des Bodens weg o.ä.) neu berechnen muß.

In diesem Fall würde es sich dann wohl anbieten, die gesamte Grafik zuerst in einen int-Array zu "malen" - wobei man mit dem selben Array-Index, mit dem man einen Pixel mal, auch die Kollision prüfen kann. Diesen Int-Array kann man dann ja per MemoryImageSource in ein Image verwandeln und darstellen. Das dürfte alles in allem noch die performanteste Methode sein, pixelgenaue Kollisionen per "brute force" zu testen.

 

[Hansdampf]

Stimmt alles, bis auf den letzten Absatz (hoffentlich verquatsche ich mich jetzt nicht).
Mit MemoryImageSource ist es viiiieeel langsamer als mit einem int[] durch.getRaster()...
Der Vorteil mit dem Raster ist, dass man durch Veränderungen im int[] gleich das Image Object mit verändert, man kann das Image dann einfach mit g.drawImage() zeichnen.
Fängt man damit erst einmal an, folgt ein ganzer Rattenschwanz von Sachen, die man selber erledigen muss, z.B vom einfachen setPixel() über drawCircle() bis zu semitransparentem putMyImage(int[]). Vorteil: man hat die volle Kontrolle über jeden Pixel und lernt jede Menge. Nachteil: in derselben Zeit kann man eine andere api lernen (z.B. jlwgl) und damit 3 Spiele schreiben, die man geschwindigkeits- und qualitätstechnisch nie mit Pixeloperationen bzw. java2d erreichen kann.
Ups, da fällt mir gerade ein: die ganzen Sachen (setPixel() usw) muss man gar nicht selber schreiben, man kann ja auch das Graphics-Object des Image nehmen. (Hab ich nicht dran gedacht, hab schon immer alles in int[]'s gemacht)

 

[0xdeadbeef]

Ok, die MemoryImageSource-Methode sollte man natürlich nur benutzen, wenn man keine komplexeren Grafikoperationen macht, sondern hauptsächlich/ausschließlich "Sprites" verwendet, zumindest was den Teil angeht, der Kollisionsprüfung braucht. Punktezahl usw. kann man dann ja über das Image reinschreiben.
Transparenz sollte kein Problem sein, ebensowenig das Zeichnen einfacher Pixel - gerade das reduziert sich ja auf den Array-Zugriff. Sobald man natürlich komplexere Sachen braucht (Alpha-Blending, komplexe Zeichenoperationen mit Kollisionsprüfung o.ä.) wird das ganze unhandlich.

Hast aber natürlich Recht, daß man auch per WritableRaster pixelgenau zeichnen (und dann in int-Array entsprechend die Kollision prüfen) kann. Vermutlich ist die WritableRaster-Methode schneller, wenn man relativ wenig zeichnet und die MemoryImageSource-Methode ist schneller, wenn sich große Teile des Bildes ändern (Overhead durch Funktionsaufrufe usw.). Müßte man mal ausmessen, hab's nie wirklich ausprobiert

Der große Nachteil beider Ansätze ist halt, daß man durch pixelweises Zeichnen in jedem Fall sehr viel Performance einbüßt. Müßte aber auch bei setPixel/WritableRaster so sein. Das Einfügen eines Images per drawImage wird ansonsten ja an tiefere Schichten weitergereicht und zumindest unter Windows üblicherweise von der Grafikhartware ausgeführt.

 

[dronus]

@Hansdampf
ein Quadtree bringt "nur" eine Verminderung der Komplexität von linear zu etwa log(Streckenlänge) das sollte auf jedenfall was bringen. Natürlich ist es für den Kollisionstest einzellner Pixel sinnlos, da die ja im Array stehen. Wenn er aber eine gaanze Gerade (die Schusslinie) gegen die Hindernisspixel testet, kann man mit Quadtree in log(Schusslänge) den ersten Treffer finden, und solange die "Kugel steckenbleibt" reicht der ja auch. Wenn er über 1000 Pixel weit schiesst, kommt der Quadtree grad mal mit 10 Box/Linie-Tests aus... statt mit bis zu 1000 Pixel-tests ohne Quadtree, falls der Schuss ins Leere geht.
Oder hab ich mich jetzt irgendwo verdacht?

 

[0xdeadbeef]

Hm, das würde aber nur für Kollisionen mit unbewegten Objekten funktionieren bzw. mit unendlich schnell schießenden Waffen. Normalerweise will man ja nicht beim Abschuß der Kugel wissen, was jetzt 200 Pixel entfernt los ist, sondern man möchte das wissen, wenn sie dort angekommen ist. Zudem können ja andere Spieler unvorhergesehen in die Schußbahn laufen usw.

 

[Hansdampf]

Wenn er über 1000 Pixel weit schiesst, kommt der Quadtree grad mal mit 10 Box/Linie-Tests aus... statt mit bis zu 1000 Pixel-tests ohne Quadtree, falls der Schuss ins Leere geht.

troz übelsten Kater werde ich mal versuchen ganz frech zu antworten.

Bei unendlich schnellen Schüssen wären das 1000 mal log anzahlObjekte* Box/Linie-Tests vs (1000 Pixel Tests plus anzahlObjekte Box Tests +1 mal pixelgenauer Test) (bei statischem Hintergrund bzw jedes Frame geupdatetem Kollisions int[]). Die n Box Tests kann man dann durch einen Quadtree auf log n reduzieren. Wobei ich jedoch bezweifle, dass der Threadersteller sich mit Quadtrees auseinandersetzen will :wink:

edit: habe natürlich Schwachsinn geschrieben(teilweise)

 

[dronus]

hm. wenn ich die zu treffende pixel-map in einen quadtree packe (wobei ich NUR KONTUREN reintun muss) dann kann ich eine linie egal wie lang gegen die boxen testen, von der schussstelle an vorwärts. zumeist wird der schuss wohl in der ersten box wo er abgefeuert wurde treffen, von da an geht es im quadtree schnell abwärts (solange der schuss nicht in die nähe von kanten kommt, die er dann doch nicht trifft.) solange er jedoch "recht fern" von zielen ist (bis auf das was er dann auch trifft) gehts jeden schritt eine etage tiefer im tree und damit ziemlich bald zum ende. schlecht ist nur, wenn man knapp an eine "wand entlang" feuert, hier würde man häufig tief in den baum steigen und dann doch verfehlen..

Wobei ich jedoch bezweifle, dass der Threadersteller sich mit Quadtrees auseinandersetzen will icon_wink.gif

da allerdings stimme ich dir voll und ganz zu *g* würd ich ja nichmal selbst wollen...

 

[DarKestSun]

Ich hab schon angst wenn ich jetz nach quadtrees suche...

mit single - shots funktioniert jetz alles mit pixel-für-pixel prüfung, ev. gibts noch schwierigkeiten, wenn man mehrere gleichzeitig feuert, oder schnell hintereinander, weil die in eine ArrayList (o.ä.) gespeichert werden müssen.

hab ein byte[][] array, inhalt is eine nummer für die "farbe" des hintergrunds (0=schwarz,...)
warum soll ich int nehmen? is ja verschwendung für die 10 zahlen

funktionieren diese quadtrees wirklich um so vieles besser? das es jetz nich ruckelt heißt nichts, das ganze ist wie am anfang gesagt ein multiplayer spiel, und wir wollen so viele spieler wie möglich schaffen

 

[Guest]

hab mein passwort vergessen
Ints sind schneller weil intern sowieso von Byte nach Int konvertiert wird (auch von Boolean anch Int obwohl Booleans eigentlich nut 1 Bit groß sind). Du benutzt wohl ein indexedArray oder sowas, nimm einfach Ints, schau dir mal die API an und such nach BufferedImage und .getRaster(). MemoryImagesource ist seit 1.2 veraltet.

 

[0xdeadbeef]

MemoryImagesource ist seit 1.2 veraltet.

Hö? Ist weder als depricated markiert noch sonstwas. Ob die Performance für Spiele geeignet ist, sei mal dahingestellt, aber einfach zu behaupten, das sei "veraltet" ist schon ein bisserl strange.

 

[Hansdampf]

Hm. Da ist ja einer sehr politisch korrekt.

liebe(r) Oxdeadbeef,
ich habe nicht gesagt, es sei depricated. Ist aber VERALTET. Genauso wie andere Dinge in Java, die inzwischen durch bessere Konzepte ersetzt wurden.
anstatt nun einen kleinen Vergleichstest zu schreiben bemühte ich kurz Google.

Old style offscreen image + opaque images
20fps@16bit
15fps@32bit

MemoryImage 1 + copyarray
11fps@16bit
10fps@32bit

MemoryImage 2 + copyarray
2.29fps@16bit
13fps@32bit

BufferedImage + drawImage
55fps@16bit
30fps@32bit

BufferedImage + copyarray
58fps@16bit
33fps@32bit

Buffered + copyarray 16bit 300 tiles( 1 layer ) 142fps

hier der link
http://www.gamedev.net/community/forums/topic.asp?topic_id=32258
ist zwar von Nov 2000, aber genug.
Ich hab früher übrigens immer einen ImageProducer benutzt, war auch schneller als MemImageSource.
Ich bleib mal bei meiner "Behauptung"

 

[0xdeadbeef]

Ich hab früher übrigens immer einen ImageProducer benutzt, war auch schneller als MemImageSource.
Ich bleib mal bei meiner "Behauptung"

MemoryImageSource ist ein ImageProducer ("implements"). Aber lassen wir's.

 

[Hansdampf]

ok, politisch korrekt: ich habe einen ImageProducer implementiert, der nicht so lahm wie MemoryImageSource ist.
Frieden

 

[DarKestSun]

k thx mal für die ganzen antworten.
also wie ihr schon sagtet, an der kollision kanns net liegen, und es liegt auch nicht daran.

ich glaub mein problem liegt bei den Threads.
vl. sollte man Thread.yield() und Thread.sleep() nicht mischen?

oda kann man generell auf Threads verzichten? (wenns so is bitte sagen wie, was ein scheduler is ähh :?: )