Isometrie: Welche Kachel wurde angeklickt?

[TheAn00bis]

Hallo!

Ich arbeite im Moment an einem kleinen Spiel mit isometrischer Grafik bzw. an dem Framework.
Das Zeichnen von Sprites usw. funktioniert so weit, nur stehe ich jetzt seit einiger Zeit vor dem Problem, wie ich herausfinde, welches Tile angeklickt wird.

Siehe angehängte Grafik!

Die Welt wird größer als der Bildschirm sein, deshalb muss der Benutzer scrolen. Man kann sich das dann wie in meiner Grafik so vorstellen, dass der Bildschirm einen Ausschnitt der ganzen Welt darstellt. Dafür habe ich wirklich eine Klasse Screen geschrieben, die die Eigenschaften x und y hat, welche angeben, wo sich der Bildschirm gerade in der Welt befindet.
Ich bin jetzt auf der Suche nach einer Funktion, der ich die Mauskoordinaten übergebe, an denen geklickt wurde und die mir zurückgibt, welches Tile sich an dieser Position befindet.
Würde der Benutzer beispielsweise an der Stelle des grünen Punktes klicken, so sollte die Funktion "3;5" zurückgeben.

Meine Frage an euch ist jetzt: Wie ist das am einfachsten zu lösen?

Ich bin bisher folgendem Ansatz nachgegangen:

Ich bestimme eine Gerade durch den Punkt(+Screen.x bzw. y), die parallel zur isometrischen Achse ist (Steigung arctan(0,5) bzw. -arctan(0,5)) [in Grafik grün makiert] und berechne ihren Schnittpunkt mit der ganz linken bzw. ganz rechten Achse (orange makiert), dann dividere ich die Koordinaten durch die Seitenlänge.
Müsste theoretisch funktionieren, praktisch habe ich da bisher nur Müll raus, obwohl ich mich daran schon länger versuche.

Also, was würdet ihr vorschlagen, wie das am besten zu machen ist?

Ich hab das Gefühl, dass das eigentlich super einfach ist, ich einfach nur nicht die richtige Idee habe.

[dizzy]

Erheblich einfacher wird das ganze, wenn du deine Kacheln als Polygone ansiehst. Dann hast du ja schon das Offset deiner Welt zur Anzeige, und die angeklickten Koordinaten der Anzeige hast du auch. Folglich ist der angeklickte Punkt in Weltkoordinaten ScreenOffset + GeklickteKoordinate, und mit diesen kannst du dann einfach einen Point-In-Poly Test machen (gibts einige Threads in der DP zu).

Damit du nun aber nicht alle Teile deiner (größtenteils nicht sichtbaren) Welt abtesten musst, kannst du den Bereich vorher eingrenzen. Es reicht schon vorher zu testen, ob ein Rechteck im sichtbaren lieget. Das sind pro Kachel ein bis vier Vergleiche die noch dazu kommen, aber in den meisten fällen den aufwendigeren Polygontest umschiffen, nämlich dann, wenn die Kachel eh nicht sichtbar ist. *)

Das Verfahren hat den Vorteil, dass du frei bist was die Kachelform angeht, wenn du z.B. mal auf Sechsecke umstellen/erweitern willst. Paul Bourkes Seiten sind immer meine Anlaufstelle Nr.1 wenn es um Geometrie geht, und auf der verlinkten sind gleich eine Reihe von sehr einfachen C Snippets für den Test. Ob sich der für Rauten nochmal optimieren lässt, habe ich noch nicht geschaut. Aber der Aufwand hält sich so schon in Grenzen denke ich.



*) Die Vorauswahl setzt voraus, dass du zu jeder Kachel die 4 Eckpunkte kennst. Ich nenne sie mal T(op), B(ottom), L(eft) und R(right), dann könnte ein Pseudocode etwa so aussehen:

Delphi-Quellcode:

for i := 0 to AnzahlKacheln-1 do
begin
  if (Kachel[i].R > 0) and (Kachel[i].B > 0) then
    if (Kachel[i].L < Screen.Width) and (Kachel[i].T < Screen.Height) then
      if PointInPoly(Kachel[i], ClickedPoint) then Kachel[i].Selected := true; // oder was auch immer dann passieren soll
end;

Die if-Abfrage funktioniert genauso gut wenn sie am Stück geschrieben steht, so fand ich nur übersichtlicher.

Bei der Vorauswahl musst du zwangläufig die Anzeigekoodinaten der Kacheln nehmen, beim Polygon-Test geht prinzipiell beides. Du musst dich nur auf eines festlegen, und jeweils den Punkt oder die Kachel um dein Offset vorm Test verschieben.
Da du aber eh schon die Anzeigekoords berechnen musstest (Kachel um Offset verschoben), empfiehlt es sich diese nochmals zu nehmen, zumal man dann für den geklickten Punkt die vom OnClick gelieferten Koordinaten 1:1 benutzen kann.


Kommt komplett ohne Trigonometrie aus, also auch ohne Float-Arithmetik. Dürfte vom Speed her okay sein.

Gruss,
Fabian

[TheAn00bis]

Darauf, das so Bruteforce-mäßig zu machen bin ich gar nicht gekommen.

Danke schonmal!

Wenn nur wenige Tiles zu sehen sind, also nah herangezoomt wurde ist das sicherlich wirklich der beste Weg. Ich bin mir nur unsicher, ob das auch schnell genug geht, wenn man weit herausgezoomt hat und vielleicht tausend Tiles sieht. Ich werde es ausprobieren und berichten.
Allerdings denke ich schon, dass das kein Problem sein wird, da der Benutzer ja nur ab und zu mal klickt und die Methode nicht bei jedem Bildaufbau aufgerufen wird.

[Sidorion]

Ich hab das bei meiner Hexmap so gelöst: Ich suche alle Mittelpunkte der Kacheln, die innerhalb eines bestimmten Radiuses um den geklickten Punkt liegen (das sind bei Dir bis zu vier Mittelpunkte). Hier empfiehlt sich die halbe Diagonale. Jetzt berechne ich den Abstand des geklickten Punktes zu all diesen Mittelpunkten. Derjenige, der am nächsten liegt, ist die gesuchte Kachel. Dieses Verfahren ist zudem unabhängig von der Rotation.
Um viele Berechnungen zu vermeiden, kannst Du auch den Mittelpunkt suchen, der als erster die Bedingung 'Im Kreis' erfüllt. Die anderen drei sind dann sein rechter und unterer Nachbar und der diagonale rechts unten.

[ibp]

Zitat von TheAn00bis:

...Ich bestimme eine Gerade durch den Punkt(+Screen.x bzw. y), die parallel zur isometrischen Achse ist (Steigung arctan(0,5) bzw. -arctan(0,5)) [in Grafik grün makiert] und berechne ihren Schnittpunkt mit der ganz linken bzw. ganz rechten Achse (orange makiert), dann dividere ich die Koordinaten durch die Seitenlänge.
Müsste theoretisch funktionieren, praktisch habe ich da bisher nur Müll raus, obwohl ich mich daran schon länger versuche....

ist doch ein guter Ansatz, was dir Fehlt ist imho der offset deines Spielkoordinaten-nullpunktes zum globalen nullpunkt! da du ja einen bestimmten bildschirmapschnitt betrachtest, musst du auch die verschiebung beachten!

hab die mal grün im bild markiert...

mit den koordinaten Xmap und Ymap kannst du dann dein Tile berechnen!

[nachtrag]

mit den formeln der koordinatentransformation kannst du dann weiterrechnen...

X = xmap*cos(winkel) + ymap*sin(winkel)
Y = -xmap*sin(winkel) + ymap*cos(winkel)

quadrat ist dann tile[(X div xtile)+1 ; (Y div ytile)+1]

[TheAn00bis]

Danke, für die Antworten.

Ich weiß nicht genau, ob dizzys oder Sidorion Verfahren schneller ist, dizzys Verfahren hat mehr Vergleiche, bei Sidirion hingegen müssen Mittelpunkte gefunden werden, Abstände berechnet werden und hinterher noch der kleinste gesucht werden.
Ich mach es im Moment so, wie von Dizzy vorgeschlagen und das funktioniert ganz gut.

ibp, dieses Offset ist gleich Null, weil die Nullpunkte von Bildschirm und Welt übereinander liegen. Die Grafik gibt den Bildschrim nämlich nicht bei 0,0 wieder. Hätte ich schreiben müssen, sorry.
Ich versuche vielleicht später nochmal, einen rechnerischen Weg zu implementieren. Erstmal lasse ich es bei der Bruteforce-Methode, die für den Zweck ausreichend ist. (Bin im Moment zu faul, um mich weiter damit rumzuplagen. )

Edit: Also ich fand das Thema war in "Programmieren allgemein" besser aufgehoben, meine Frage ist ja rein algorithmischer Natur und hat nichts mit Delphi zu tun, ich schreibe das ganze übrigens auch in Java.