Isometrische Karte | event handler

[TheBenji]

Hallo,

ich komme gerade irgendwie nicht so ganz weiter...
...ich habe eine ganz normale isometrische map und möchte sobald der mauszeiger über einem tile ist "irgendwas machen".

Sprich ich habe MouseX und MouseY und muss damit herausfinden ob ich über einem tile bin: Da diese aber rautenförmig sind weiß ich grad nicht wie ich das am besten mache.
Also bei einer "normalen" Karte würde man ja einfach

Code: Alles auswählen

if(MouseX > tilePositionX && MouseX < tilePositionX+tileSize && MouseY > tilePositionY && MouseY < tilePositionY+tileSize)

machen.
Aber das funktioniert hier ja nicht.

Könnt ihr mir weiterhelfen?

[joggel]

Evtl. durch einen einfachen Intersection-Test...
Position der Maus mit einem (sehr) weit enfernten Punkt verbinden (der zweite Punkt sollte aber so gewählt werden, das er auf keinen Fall mehr in dem Tile ist). Es ensteht eine Linie.
Testen ob es eine Überschneidung mit der Linie und den Kanten gibt.
Also, mit jeder Kanten testen.
Sollte die Anzahl der Überschneidungen gerade (1) sein, ist der Punkt im Tile, sollte er ungerade sein (0 oder 2) ist er auserhalb...

Aber das ist ne ziemlich rechenintensive Methode... sprich, wenn du die Maus bewegst, müsste jedesmal so ein Test ausgeführt werden.

[Krishty]

Aber das ist ne ziemlich rechenintensive Methode... sprich, wenn du die Maus bewegst, müsste jedesmal so ein Test ausgeführt werden.

Suboptimal sicher, aber „rechenintensiv“? Ich bin mir sicher, dass meine CPU von 2D-Streckenschnittberechnungen pro Sekunde eine neunstellige Zahl hinbekäme. Falls mein Handy eine Maus hätte, wäre die Zahl immernoch sechsstellig.

Ich würde übrigens die vier Geradengleichungen der Rautenkanten aufstellen und prüfen, ob die Zeigerposition über den unteren beiden und unter den oberen beiden liegt.

[TheBenji]

Ich würde übrigens die vier Geradengleichungen der Rautenkanten aufstellen und prüfen, ob die Zeigerposition über den unteren beiden und unter den oberen beiden liegt.

So ungefähr hatte ich mir das auch gedacht...aber ich dachte vllt. gibts ja so nen coolen Algo der das ganze noch vereinfacht/optimiert - es haben sich ja in der Vergangenheit schon viele schlaue Menschen mit vielen Problemen beschäftigt :)

Aber dann werde ich wohl die geradengleichungen aufstellen...

[Alexander Kornrumpf]

Ich hab auch noch eine Idee. Alle Tilegrenzen haben eine von zwei Steigungen. Gegeben x,y und Steigung kannst du den Ordinatenabschnitt zweier jeweils zu den Gitterdimensionen paralleler Gerade bestimmen auf der der Punkt liegt. Das ist billig. y = mx+b => b= y - mx mit, x, y, m bekannt. Dann machst du deinen Vergleich aus der "normalen Karte" mit den (bekannten) Ordinatenabschnitten der Tilegrenzen. Ich bin sicher dass man mit relativ wenig Arithmetik von tilePositionX und tilePositionY zu den gefragten Ordinatenabschnitten kommen kann.

(Das ist so eine Frage bei der ich das Gefühl habe, gleich kommt TGGC und erklärt uns wie man es richtig macht)

[Krishty]

Falls bei dir die jeweils gegenüberliegenden Kanten parallel sind, ist das ja schon eine ziemliche Vereinfachung …

Nachtrag: Ja, Alexander war schneller. Du bestimmst die Koordinaten im Koordinatensystem der Raute, indem du die Zeigerposition auf die beiden maßgebenden Geraden umrechnest. Dann prüfst du wie gehabt, ob die Koordinaten innerhalb der Grenzen liegen.

[Alexander Kornrumpf]

Ja hatte ich angenommen dass es sich um ein relativ zum Koordinatensystem gedrehtes Gitter handelt. Da müsste auch was mit projektion drin sein, oder? Also im Koordinatensystem des Gitters den Test machen den er eh machen wollte. Wer von euch kann das eben aus dem ärmel schütteln?

[dot]

Der vektor u zeige in Richtung der einen Koordinatenachse, v in Richtung der anderen und o seien die Koordinaten des Ursprungs. Dann transformiert die Matrix

Code: Alles auswählen

| u_x  u_y  -dot(u, o) |
| v_x  v_y  -dot(v, o) | * p = p'
|  0    0        1     |

von Pixelkoordinaten p in Koordinaten in deinem isometrischen Gitter p', wenn ich nicht irre.

[Chromanoid]

Ja genau, es sollte einfacher sein die Klick-Koordinate in Indizes des Map-Arrays umzurechnen... Ein ganz netter Thread auf JGO dazu: [SOLVED] Drawing isometric tiles inside a screen ??

[TheBenji]

Mir fehlen hier wohl stellenweiße noch einige Mathematische Grundkenntnisse :D
..merke ich daran das ich den Beitrag von dot nicht so ganz verstehe *hust*

Und auch sonst: so wirklich funktionieren tut das alles nicht recht.
Der letzte Versuch war einfach den Mauszeiger (die Position von dem Mauszeiger) ebenfalls "rotieren" zu lassen - halt theoretisch genau entegegen der karte.
Mit dem Gedanken das dieser pseudopunkt des Mauszeigers ja dann genau auf der "normalen" Karte liegen müsste.
Nur irgendwie bin ich zu doof da entsprechend die korrekten Zahlen aneinander zu klatschen...-.-

Werde mich dann aber heute abend noch mal hinsetzen müssen und mal schauen was zum teufel ich da mache und wieso :D

[dot]

Der letzte Versuch war einfach den Mauszeiger (die Position von dem Mauszeiger) ebenfalls "rotieren" zu lassen - halt theoretisch genau entegegen der karte.
Mit dem Gedanken das dieser pseudopunkt des Mauszeigers ja dann genau auf der "normalen" Karte liegen müsste.

Genau das tut meine Matrix ;)
Ich schreibs dir einfach mal aus:

Code: Alles auswählen

x' = u_x * p_x + u_y * p_y - u_x * o_x - u_y * o_y
y' = v_x * p_x + v_y * p_y - v_x * o_x - v_y * o_y

Wobei x und y die Mauskoordinaten x' und y' die Koordinaten des "Pseudopunktes" auf der Karte sind. u und v sind Vektoren, die in Richtung der Pseudokoordinatenachsen deines Spielbretts zeigen und o ist der Urpsrung des Pseudokoordinatensystems.

[TheBenji]

Wenn mich nicht alles täuscht möchte ich ja das hier machen:



Wobei der grüne Punkt ja quasi mein Mauszeiger ist.
Das rote ist ja das "noramle" (bekannte) Koordinatensystem in dem ich überprüfen kann ob ich in dem feld bin oder nicht.
Das schwarze ist ja meine ISO-map (hoffe ich :D)

Bin ich denn soweit nicht schon total falsch unterwegs?

Und den Mauszeiger jetzt so zu verschieben hilft deine Matrix? Mag mir dann mal jemand aufzeigen wo da jetzt was welcher wert wäre? Blicke da leider immer noch nicht so ganz durch :(

[dot]

u und v in meiner Matrix sind genau die schwarzen Richtungen da oben und o ist der Punkt wo sie sich treffen ;)

[TheBenji]

Also um das jetzt mal ein beispiel zu nehmen für ganz doofe wie mich:

Wenn wir davon ausgehen das o der Punkt 0|0 ist und mein Mauszeiger an der Position 0| 100 (was so grob der zeichnung entsprechen dürfte wenn wir davon ausgehen das eine Seite von so nem tile 128px lang ist und wir die sehr genaue zeichnung mal schön reden) würden die variablen jetzt wie genau (ungefähr genau) aussehen?

o_x und o_y dürften ja dann wohl 0 sein, oder?
p_x unter dieser annahme auch 0 und p_y entsprechend 100?!
So, und mit den Vektoren tu ich mir schwer weil ich die nur durch Wikipedia kenne - also ich mein es ist grundlegend klar das Vektoren nur so ne Verschiebung sind und alles in allem nicht sonderlich aufregend aber mir fällt es gerade schwer das auf diesen Anwendungsfall zu projezieren...
Wäre u_x dann der Punkt an dem der Mauszeiger ist gemessen an dem "schwarzen" Koordinatensystem oder was? Oo
Also quasi 100? Und u_y ebenfalls?
Falls ja (ich weiß ja das das nicht sein kann aber egal), wo ist der unterschied zu v_x/v_y?

Ich hoffe ich habe mich jetzt nicht alzusehr blamiert :)

[Chromanoid]

Schau dir sonst mal den JGO Link an :).

[BeRsErKeR]

Könnte man die Raute nicht einfach als 4 rechtwinklige Dreiecke betrachten und kurz prüfen in welchem umschließenden Rechteck dieser Dreiecke die Maus liegen könnte? Das wäre ja recht simpel. Und wenn man ein mögliches umschließendes Rechteck gefunden hat, kann man ja einfach (anhand der Steigung der Hypothenuse) prüfen ob der Punkt im Teildreieck, welches zur Raute gehört, liegt. Keine Ahnung wie schnell und effektiv das wäre. Man kann aber relativ schnell alle Mauspositionen ausschließen, die außerhalb des Rechtecks liegen, welches die Raute umschließt.

Will man rausfinden, welche Raute angeklickt wurde muss man prinzipiell nur 2 mögliche Rauten prüfen. Bzw nach obigem Test, wenn die Maus eben im Teildreieck liegt, welches nicht zur Raute gehört, kann man leicht feststellen, welche Raute tatsächlich unterm Cursor liegt, nämlich die angrenzende in der jeweiligen Richtung (je nach Teildreieck 1-4).

[LONy]

Ich stand ja bei mir genau vor dem gleichen Problem. Da ich mein Problem allerdings nicht so schön mit Vektoren usw. gelöst habe (hab das nicht ganz verstanden, bzw. war das beispiel das ich gefunden hab nur für eine diamond map geeigent) hab ich erstmal nichts dazu gesagt^^
Ich nutze bei mir eine Straggered Map... der Unterschied zur Diamond Map liegt nur darin, wie die koordinaten angeordnet sind:
http://www.pst.ifi.lmu.de/DA_Fopra/iso.gif (mit google gefunden)
Wobei ich meine Map noch etwas anders durchnummeriert habe (so wie auf dem Bild wäre sie dann doppelt so breit wie hoch). Ich denke meine Lösung ist ähnlich bzw. so wie es BeRsErKeR vorgeschlagen hat:

Ich teile die geraden Tile-Reihen (die die nicht eingerückt sind) einfach in Rechtecke auf. Jedes Rechteck teil ich nochmal in 4 Teile. Diese Teile halbier ich durch eine Gerade von Ecke zu Ecke (was meiner Tilekannte entspricht) und prüfe dann ob ich mich oberhalb oder unterhalb dieser schrägen gerade befinde. Entsprechend ob ich mich oberhalb oder unterhalb befinde, bin ich auf dem Haupttile, das von dem großen Rechteck eingeschlossen ist oder auf einem Nachbartile und korregiere dann entsprechend die berechneten Koordinaten.

Es gibt sicherlich bessere Lösungen, aber so funktionierts bei mir gut und es gibt dinge die sehr viel zeitaufwendiger sind als die Mauskoordinaten (so umständlich) von Pixelkoordinaten in Tilekoordinaten umzurechnen ;)

EDIT:
Ich hab mich für eine Straggered Map entschieden, um nicht unnötig Tiles außerhalb des Sichtbereichs rendern zu müssen. Der große Nachteil ist allerdings, dass die Koordinaten recht durcheinander sind im vergleich zur Diamond Map. In dem Forum vom ersten link hab ich gesehn, dass genau dieses Problem diskutiert wurde mit dem sichtbaren Bereich rendern.
Vielleicht steig ich auch noch irgendwann auf eine Diamond Map um, aber noch mehr Zeit will ich da erstmal nicht investieren und mal schaun wie weit ich mit meiner Straggered Map komm :D

[dot]

o_x und o_y dürften ja dann wohl 0 sein, oder?

ja

p_x unter dieser annahme auch 0 und p_y entsprechend 100?!

ja

So, und mit den Vektoren tu ich mir schwer weil ich die nur durch Wikipedia kenne - also ich mein es ist grundlegend klar das Vektoren nur so ne Verschiebung sind und alles in allem nicht sonderlich aufregend aber mir fällt es gerade schwer das auf diesen Anwendungsfall zu projezieren...

Stell dir einen Vektor vor als Richtung im Raum. Das ist mathematisch zwar nicht wirklich korrekt, aber das ignorieren wir mal. Ich kann dir nur sehr sehr empfehlen, dass du dich zumindest mit Vektoren mal eingehend auseinandersetzt. Imo gibt es absolut keine wichtigere mathematische Grundlage für Spieleprogrammierung als Vektoren. Vektoren sind wirklich nicht schwer zu verstehen, aber wenn du sie mal verstanden hast, dann wird sooo vieles, plötzlich sooo viel einfacher, das glaubst du gar nicht ;)

Wäre u_x dann der Punkt an dem der Mauszeiger ist gemessen an dem "schwarzen" Koordinatensystem oder was? Oo
Also quasi 100? Und u_y ebenfalls?
Falls ja (ich weiß ja das das nicht sein kann aber egal), wo ist der unterschied zu v_x/v_y?

Wie gesagt, u und v sind die Richtungen der x- und y-Achse deines Koordinatensystem. Wenn wir davon ausgehen, dass die linke schwarze Linie die y-Achse und die rechte die x-Achse ist, dann hätten u und v eben die Koordinaten:

Code: Alles auswählen

u_x = 1 / sqrt(2)
u_y = 1 / sqrt(2)

v_x =-1 / sqrt(2)
v_y = 1 / sqrt(2)

Wenn du die Werte nun in meine vorhin gepostete Formel einsetzt, wirst du sehen, dass genau das richtige rauskommt ;)

[joeydee]

Zur allgemeinen Verwirrung hier noch mein Lösungsweg ;-) ist im Prinzip das was dot sagt, aber vielleicht verstehst du's mit anderen Worten nochmal besser:
- du kennst den Ursprung deiner Tile-Landschaft auf dem Bildschirm (ox,oy), also da wo die erste Ecke des Tiles aus der Map (0/0) abgebildet wird.
- du kennst die X-Kante eines Tiles in Bildschirmpixeln (ux,uy) d.h. z.B. von ox/oy aus geht man ux Pixel nach rechts und uy Pixel nach unten, dann ist man am Ursprng des 2. Tiles (entspricht dem 2. Tile horizontal in der Map, also map_x=1)
- ebenso kennst du die Y-Kante auf dem Bildschirm (vx,vy) d.h. von ox/oy gehts vx Pixel nach rechts und vy nach unten, dann steht man am 2. Tile vertikal in der Map (map_y=1)

Also kannst du jederzeit Map-Koordinaten (s,t) in Bildschirm-Koordinaten umrechnen:
screen=s*u+t*v+o (u, v und o sind die oben genannten Vektoren, s und t sind Skalare, Ergebnis ist ein Vektor)
Oder in Komponenten, da dir Vektoren ja noch nicht so geläufig sind:

Code: Alles auswählen

//MapToScreen (s,t)
screenX=s*ux+t*vx+ox
screenY=s*uy+t*vy+oy

Mit diesem Wissen kannst du auch umgekehrt Screen- in Mapkoordinaten umrechnen: du hast ein Gleichungssystem mit 2 Unbekannten und musst nach s und t auflösen.

Code: Alles auswählen

//ScreenToMap (sx,sy)
s=(vx*sy-vy*sx+vy*ox-vx*oy)/(vx*uy-vy*ux);
t=(sx-s*ux-ox)/vx;

Abgerundet ergibt das dein Tile, die Nachkommastellen geben dir die relative Position im Tile.

(ob die Rechnung im Prinzip oben genannter Matrix von dot entspricht habe ich nicht überprüft; wenn aber die Ergebnisse von dot stimmen, müsste sich das 1:1 überführen lassen)

Das funktioniert übrigens für alle isometrischen Tiles, egal wie sie gestaucht, gedreht oder relativ zur Ansicht verschoben (gescrollt) sind. o, u und v definieren dabei deine aktuelle Ansicht.

Edit: noch ein Bildchen dazu gemalt.

[dot]

Nimm die Lösung von joeydee. In meiner Lösung ging ich davon aus, dass u und v normal aufeinander stehen, fällt mir grad auf...

[Chromanoid]

Hier das ganze noch mal illustriert wie im JGO Thread. Sind glaube ich im Grunde die gleichen Formeln wie von joeydee, nur eben als Spezialfall.




Hier dann noch mal wie man das ganze benutzt um nur die Tiles, die auf dem Screen sind zu rendern.
http://www.java-gaming.org/topics/drawi ... #msg212862

[TheBenji]

Vielen vielen dank für eure ausführlichen erklärungen :)

Damit lies sich mein Problem wirklich leicht lösen und ich habe jetzt (glaube ich :D) auch schon mal die grundzüge der vektoren verstanden.

Danke das ihr euch so ne Mühe gegeben habt und es so ausführlich beschrieben habt!

[joeydee]

Hier noch die Ergänzung für alle die das evtl. mal nachschlagen und auf Vektorarithmetik bauen möchten:
Man baue sich eine 3x3-Matrix, in welcher die Screeninformationen stecken. Dann kann man durch einfache Multiplikation Map- in Screenkoordinaten umrechnen, bzw. mit der Inversen der Matrix von Screen- auf Mapkoordinaten.

Code: Alles auswählen

m=[
ux vx ox
uy vy oy
0   0   1
]

vScreen=vMap*m
vMap=vScreen*(m^-1)
(v in der Form [x y 1])