Bestimmte Fläche anklicken - Wie elegant lösen?

[Meldanor]

Hallo Leute,

ich habe aus Jux und Tollerei angefangen, Risiko zu programmieren. Ja, dieses Thema findet sich bei der Suche sehr häufig und auch ich weiß, dass es nichts großes ist. Ich für meinen Teil will das jedoch durchziehen als auch einen Multiplayer einbauen.

Ich bin noch in der "Gedankenphase" und überlege mir, welche Probleme auftauchen und wie man diese lösen kann.

Ein Problem ist:

Wie kann ich erkennen, dass eine bestimmte Fläche angeklickt wurde?
Bei einer quadratischen oder kreisförmigen Fläche würde ich das rausbekommen.
Doch wie sieht dies bei .... "Fleck"-Förmige Fläche aus?
Wenn wir uns z.B. Deutschland als Grundriss vorstellen, wie kann ich "elegant" lösen, dass nun Deutschland angeklickt wurde?
Elegant wird hier betont, denn eine "naja" Lösung hätte ich, nämlich Deutschland in mehrere Quadrate teilen und somit die "Fleck"-Fläche mit Quadraten füllen, um so rauszubekomen, ob der Mausklick in Deutschland erfolgt.
Gibt es jedoch eine elegante Lösung, sodass ich nicht alle "Hilfsquadrate" überprüfen muss als auch wirklich die "ganze" Fläche abdecke?

Ich hab mir auch schon überlegt, ob ich mir die Begrenzungslinie als Punktmenge vorstelle und dies irgendwie speicher und dann über irgendeinen Algorithmus herausfinden, ob der Mausklick innerhalb liegt, jedoch fehlt mir hierfür ein mathematisches Verständis oder gar ein Stück realistisches Denken?

Eine Idee, die mir gerade beim schreiben gekommen ist:
Ein 2D Array mit im Hintergrund, wo jedes Element ein "Punkt" der gesamt Karte darstellt und wenn man das Spiel lädt, füllt er das Array mit Zahlen, welche z.B. symbolisieren "Das ist Deutschland".
So müsste man "ja nur" im Array nachschauen, ob der Mausklick in Deutschland erfolgt oder nicht.
Hier jedoch müsste man ja irgendwie speichern, wo Deutschland intern liegt. Also beim Laden des Programmes müsste dieses Array dann gefüllt werden. Hier würde es interessant sein, denn ich will ja nicht das Array serialisieren oder so, sondern Datensparend speichern ^^
Hierfür könnte man ja in der Länder Datei speichern den jeweils linken Punkt und dann den jeweils rechten Punkt der Begrenzungslinie, sodass ich Zeilenweise von links nach rechts das Array fülle.
Mmm...die Idee gefällt mir, doch gibt es wie gesagt eine elegantere Lösung?

Mfg
Mel

PS: Danke für das eventuelle Durchlesen und das Beantworten

 

[Steev]

Hmm, eine Elegante lösung währe vieleicht eine eigene Shape-Klasse bei der du eine "contains"-Methode implementierst, die du dann bei einem Mausklick einfach abfragen kannst.
Die contains-Methode würde ich anhand er Umlaufsummer der Punkte berechnen. Diese Lößung funktioniert zwar nicht für alle beliebigen Formen, aber dafür für die meisten Formen. Hier mal eine Shape-Klasse, wo die Methode schon ausprogrammiert wurde.

SourceForge.net Repository - [rpgenesis] Index of /trunk/src/RPGenesis/com/rpgenesis/geom

Viel Spaß damit und Gruß
Steev

 

[Steev]

PS: Es ist die Methode "contains" in der Klasse "RPGCollider"

 

[André Uhres]

Wiese nimmst du nicht einfach die Klasse java.awt.Polygon?

 

[Steev]

Ich nehme nicht java.awt.Polygon weil ich pro Translationsinstanz ein Polygon bräuchte, mit meiner Klasse brauche ich dafür nur eine Transformation-Instanz und kann immer dasselbe Polygon verwenden, dem nur verschiedene Transformationsattribute übergeben werden. Die Klasse ist ja teil einer Engine, wo es durchaus größere Polygone gegben kann... An sich hast du aber Recht, für diesen konkreten Fall währe java.awt.Polygon tatsächlich ausreichend.

 

[Quaxli]

Meine Wahl würde bei so einem Problem mit relativ kleiner Auswahl auf eine sog. "Schattenkarte" fallen: Du erstellst Dir vom Spielplan ein 2. Bild in dem jedes Land eindeutig eingefärbt ist: Nordeuropa blau, Ukraine grün, usw. - dabei wirst du aber für ein Riskio schon mit Farbschattierungen arbeiten müssen.
Für das Spiel werden beide Bilder geladen. Der eigentliche Spielplan wird angezeigt, die Schattenkart nur in den Speicher geladen und "vorgehalten".
Wenn jetzt jemand auf die eigentliche Karte klickt (schön bunt, Schriften, Farbverläufe, Sondergrafiken etc.), fragst Du im Hintergrund ab, welche Farbe der Pixel auf der Schattenkarte hat und kannst so relativ einfach das entsprechende Land über den Farbcode ermitteln.
Der Vorteil bei dieser Methode ist, daß Du für selbst bei einem Land, daß in ein anderes hinein ragt, noch für das letzte Pixel bequem das richtige Land ermitteln kannst, während Du bei einem Polygon meiner Ansicht nach Abstriche beim Detailgrad machen müßtest.

 

[Steev]

Das ist für das konkrete Problem meiner Meinung nach auch vertretbar. Für größere Sachen ist es halt immer so, dass eine "Schattenkarte" viel mehr Heapspeicher verbraucht als ein Polygon, weshalb ich daher immer Polygone verwende.

 

[Grey_M]

So ne Schattenkarte kann man ja ziemlich klein halten. Muss ja kein Bitmap sein, ein Vectorgrafik reicht ja auch.

Und "viel mehr" ist auch immer so relativ. Ob nun 1kb oder 2kb ist ja eigentlich egal.

 

[Steev]

*Räusper*
Dir ist klar, dass jedes Bild in ungepacktem Format im Heap liegt und java imho keine Vektorgrafiken unterstützt?

 

[Tomate_Salat]

imho keine Vektorgrafiken unterstützt?

Ah ok gut, dachte schon ich hätte was verpasst :rtfm:

Hab mir mal Polygone angeschaut und finde die eigentl. nicht verkehrt. Kann Java eigentl. automatisch Pfade finden? Also ich mein: man lädt ein Transparentes Bild und sucht die Struktur von dem Bild und lässt sich daraus ein Polygon erzeugen? Wenn das so gehen würde, könnte man ja einen Editor schreiben, der einfach ein Bild in ein Polygon konvertiert und dieses dann Abspeichert, welches man im Spiel verwenden kann.

MFG

Tomate_Salat

 

[Steev]

Soweit ich weis, gibt es da in Java keine Möglichkeit, Bilder automatisch in Vektoren zu wandeln.
Ich habe da mal einen Algorithmus geschrieben, der die Odd-Parity-Regel verwendet hatte. Das Problem dabei ist, dass man relativ schwer komplexe zusammenhängende Flächen erkennen kann. Ich würde einfach einen Inkscape-Importer schreiben, oder irgendetwas in der Art machen.

 

[Tomate_Salat]

Ja dachte ich mir schon, bin schon die ganze Zeit am überlegen, wie man komplexere oder mehrere Gebilde erkennen könnte

 

[Steev]

Na ja, ich wüsste da schon was.
Ich würde durch ein Bild rastern und prüfen, ob ein Pixel einen Alphawert kleiner 255 oder gleich 255 hat. Wenn sich der Alphawert vom Vorpixel (X-Achse) unterscheidet, so wird der Punkt (X, Y) in einer LinkedList abgespeichert. Auserdem wird die Nummer des Punktes pro Zeile abgespeichert. Der erste Punkt der gefunden wird bekommt die 0, der zweite Punkt die 1 usw. Die Nummerierung fängt pro Zeile neu an.
Am Ende hast du dann alle Punkte eines Übergangs gespeichert.
Jetzt iterierst du vorwärts durch die Liste und verbindest alle Punkte mit dem Index 0 miteinander, dann iterierst du rückwärst durch die Liste und verbindest alle Punkte mit dem Index 1 miteinander, dann iterierst du vorwärts durch die Liste und verbindest alle Punkte mit dem Index 2 miteinander usw.
Am Ende verbindest du den letzten 0-Punkt mit dem letzen 1-Punkt, den ersten 1-Punkt mit dem ersten 2-Punkt usw. Der letzte Punkt überhaupt wird dann mit dem ersten Punkt überhaupt verbunden.
Jetzt hast du ein zusammenhängenden Polygonzug. Jetzt müssen alle Punkte entfernt werden, die zu oft vorkommen. Dazu iterierst du durch deinen Polygonzug und überprüfst, ob sich ein Punkt von seinem Vorgänger und Nachfolger unterscheidet. Ist dies nicht der Fall, so wird er gelöscht.

Das ist ein ganz rudimentärer Ansatz, um nicht-konkave Formen erkennen zu können.

Gruß
Steev

 

[Tomate_Salat]

Klingt interessant, ich glaube ich werde das iwann mal umsetzen


Und wie würde ich folgendes Szenario behandeln:
ich habe ein haus
das haus hat transparente fenster...

ich glaube, wenn ich jemals an mein erstes Spiel gehe, werde ich erstmal alles idealisieren Oo

 

[Meldanor]

Nach einigem Hin- und herprobieren und Überlegen habe ich mich für die Methode von Quaxli entschieden, auch wenn die anderen sich interessant anhören.
Jedoch habe ich die Schattenkarte reduziert auf ein Array im Hintergrund, wo jedes Element aus einer Zahl von 0 bis n besteht. Wenn nun der User klickt, schau ich im Array nach, wo der Klick erfolgte und fertig. Die Schattenkarte zeichne ich dann einmal und lasse sie per mini Programm in das Array umwandeln und gleich abspeichern. Vorteil zum Bild: Ich habe ja nur eine zahl und nicht 4-Tupel an Zahlen(Alpha, Rot, Grün, Blau).
Es ist zwar Speicheraufwendiger als wenn ich per Berechnung das rausbekomme, aber ich schätze, wenn ich einen kleinen Datentyp nehme(wie short), dass ich dann den Speicherverbrauch minimiere.
Auf jeden Fall klappt das schon ganz gut.
Und nochmals vielen Dank für die sehr vielfältigen und guten Antworten . Danke