Zielauswahl: Cursorbewegung

Hi,

Erstmal vorweg, es handelt sich um eine konzeptionelle Frage und nicht um die Implementierung, ich würde mal behaupten das Problem ist eher mathematischer als technischer Natur, passt hier aber am besten hin denke ich.

Die Problemstellung:
Für mein Kampfsystem (SKS) möchte ich den Cursor zur Auswahl des Ziels einer Technik in alle Richtungen sinnvoll bewegbar haben. Die Monster können sich dabei irgendwo befinden, vielleicht bewegen sie sich auch noch, jedenfalls soll das Ganze dynamisch sein. Zu jedem Zeitpunkt sind von jedem Kämpfer X- und Y-Koordinaten bekannt. Das wesentliche ist hierbei, dass man bei der Auswahl rechts / links nicht einfach unabhängig von der Position zwischen Monsterauswahl und Spielerauswahl wechselt, sondern sich der Cursor "sinnvoll" weiterbewegen soll.
Der Einfachheit halber beschränke ich hier erstmal nur auf die Auswahl der Monster und lasse den Wechsel zwischen Spieler / Monster erstmal außen vor (es würde für mich da noch etwas anders abalufen als in den Ansätzen geschildert)

Mein erster Ansatz war es, bei Knopfdruck in eine Richtung das nächste Monster in dieser Richtung auswzuwählen, also wenn man zB nach rechts drückt, wird das Monster mit der nächsgrößeren X-Koordinate ausgewählt. Klingt vielleicht einleichtend, ist aber für die Auswahl oft nicht intuitiv. Beispiel:

Code:

---

--2--
-----
-----
1---3

---

Hier sind die Monster 1 und 3 quasi nebeneinander, dazwischen, aber viel weiter oben ist das Monster 2. Intuitiv würde man erwarten, dass man rechts von 1 nach 3 kommt, da 2 aber die kleinere X-Koordinate hat, würde man stattdessen zu 2 wechseln.
Bei einer größeren Anzahl von Monstern kommen solche Fälle öfter vor, was die Navigation doch eher unangenehm gestaltet.

Mein zweiter (und bisher bevorzugter) Ansatz war es, primär nach der Y-Distanz zu sortieren. Heißt konkret: Wenn man nach rechts drückt und sich ein weiteres Monster auf der gleichen Höhe rechts daneben befindet, wird auch dieses ausgewählt. In dem Beispiel von oben würde man also wie erwartet von 1 zu 3 wechseln können. Da der Ansatz vielleicht etwas merkwürdig formuliert klingt, ein Beispiel mit 5 Monstern:

Code:

---

---1-
-2--3
---4-
--5--

---

2 und 3 haben die Y-Distanz 0, also würde man bei Auswahl nach rechts immer direkt zwischen 2 und 3 wechseln. Gleiches hilt für 1 und 4 in der X-Distanz, da würde man nach oben / unten wechseln können.
Etwas kompliziertes ist es für die 4 wenn man nach links dürckt. Hier haben 2 und 5 beide die Y-Distanz 1. Hier würde ich wie nach dem 1. Ansatz die 5 auswählen, weil es nach der X-Koordinate näher ist. Von der 4 nach unten kommt man auch zur 5: 1 hat zwar die geringere X-Distanz, ist aber weiter oben als die 4 selbst und wird deshalb nicht berücksichtigt.
Klingt swoeit vielleicht kompliziert, scheint aber für die meisten Fälle intuitiv zu funktionieren. Problematisch wird es hier für mindestens einen Sonderfall sowie den Wechsel von einem Rand zum andern, etwa wenn man vom linkesten Monster nach links drückt.
Erstmal der konkrete Problemfall:

Code:

---

1---2
--5--
3---4

---

Die 5 ist unerreichbar. 1-4 bilden ein perfektes Rechteck und von keiner Position ist nach diesem Ansatz die 5 zu erreichen. Zumindest sollte das aber bei <=5 Monstern der einzige Sonderfall sein und solange die Monster sich nicht bewegen, ließe sich das vermeiden.
Der andere kleine Schönheitsfehler ist wie gesagt der Randwechsel wo man sich mehr überlegen müsste, wie man es umsetzen will:

Code:

---

---12
3----

---

Wenn man von der 2 nach rechts dürckt, kommt man, wenn man streng dem prinzip folgt und einfach links wieder eintritt bei der 1 rein. 3 wäre wahrscheinlich intuitiver.
Sind zwar beides eher kleine Macken im Vergelich zu Ansatz 1, aber es zeigt zumindest, dass auch der Ansatz nicht perfekt ist.

3. Ansatz auf den ich kurz eingehen will, ist für statische Monsterpositionen das ganze im Voraus für jede Monstergruppe per Hand anzulegen. Das Problem ist hier die Aktualisierung, wenn ein Monster tot / nicht mehr auswählbar ist. Egal wie man hier weitergeht, es gibt viele Beispiele, wo die Cursorführung total unsinnig wird und Monster unerreichbar werden können.
Alternativ könnte man für jede Auswahl verbeleibender Monster die Bewegung per Hand definieren, aber bei 5 Monstern hätte man schon 31 Fälle zu beachten...

Darüber hinaus kann man sich sicherlich weitere Ansätze überlegen - Mit der euklidschen Dustanz rumhantieren, oder was ganz anderes was mir nicht eingefallen ist.

Ihr könnt mir jetzt sicher vorwerfen, dass ich mir viel zu viele komplizierte Gedanken über einen eigentlich einfachen Sachverhalt mache, aber in der Technik achte ich auf solche Kleinigkeiten und mich würde einfach interessieren, falls sich jemand die Mühe macht das durchzulesen:
Gibt es da irgendeine etablierte Lösung von "großen" RPGs? Was wäre sonst eurer Meinung nach die sinnvollste Lösung für das Problem, gibt es irgendwelche sinnigen Ansätze die mir nicht eingefallen sind?

Danke für die Antworten falls sich jemand die Mühe macht :)

Also meine spontane Lösung wäre folgende:

Bei einer links-rechts-Auswahl würde ich, wenn ich nach rechts will, erst einmal die kürzeste Distanz zum nächsten auf der rechten Seite ermitteln.
(Was links und rechts liegt wird man wahrscheinlich über positive und negative X-Differenz ermitteln. Das wäre eine einfache Abfrage.)
Die Distanz würde man über den Satz des Pythagoras ermitteln, mit dem XP/VX ja ohne weiteres umsetzbar.
Bei einer gleichen Distanz müsste man dann erst einmal den mit dem geringsten Abstand auf der X-Achse ermitteln, schließlich will man ja nach rechts und erwartet den anzuvisieren, der dann die kürzeste X-Distanz hat.
Bei gleicher Gesamt- und X-Distanz würde ich dann einfach von oben nach unten gehen, schließlich lesen wir ja auch von oben nach unten und haben deshalb wohl auch dieses Denkmuster.

Kurz:
Wenn nach rechts, dann -> kürzester Sqrt(x²+y²)-Abstand (-> kürzester X-Abstand (-> Y von oben nach unten)) -> Nächster gefunden

Insgesamt wohl weniger Mathematik, sondern mehr Abfragen.

Das Problem was ich bei deinem Ansatz sehe: Wenn ein Gegner nun nur wenige Pixel höher/tiefer sitzt als 2 andere, also praktisch als Beispiel mit mehr Zoom wie deine

Code:

---

------1----------2
------1-----3----2
------1-----3----2
------1-----3----2
------------3-----

---

würde ich mit nach rechts von 1 nach 3 wechseln wollen, aber nach einigen deiner Ansätze geht er dann auf 2. Hm. Dabei stehen sie nur leicht versetzt zu einander.

Ausserdem würde ich bei deinem ersten Beispiel intuitiv auf die 2 gehen wollen - aber ich kann mir auch Fälle vorstellen, wo ich eher mit oben/unten hantieren wollte.

Ich hätte da diverse Ansätze.
Der eine Ansatz ist soweit, das etwas unintuitiver zu machen, aber wers erklärt kriegt, würde da schnell reinkommen:
Konzentration auf eine Achse. Rechts: nächster Gegner auf der X-Achse, Links, nächster Gegner auf der X-Achse nach links.

Gegen den Fall

Code:

---

1--
---3
----
2--

---

könnte man dann noch , falls ein "Nachbar" mit X-Abstand==0 den Y-Abstand checken und wenn der bei Rechts größer ist, dahin springen, und wenn er bei Links kleiner ist, dahin springen, ansonsten verwerfen und wirklich zum nächsten "echten" Nachbarn mit X-Abstand != 0 gehen.

Nicht ganz intuitiv in manchen Situationen, aber kommt man rein.
Würde dir auch Oben/unten für wechsel zwischen Charas und Gegnern lassen.

Andere Option die ich sehe ist Abwandlung von Rettans Vorschlag - du gehst erstmal nach dem euklidischen Abstand, prüfst aber je nach Richtung, ob der gefundene Kandidat nicht zu weit in eine entsprechende Richtung ausfällt, oder ob eine gewissen X/Y-Abstands-Verhältnis-Grenze nicht über/unterschritten wird. D.h. wenn im Fall

Code:

---

3--------
----------
1-------2

---

von der 1 die rechts kommt, findet er zwar 3, verwirft aber, da das x/y-abstandsverhältnis extrem (in dem fall unendlich) hoch ist, und geht auf 2, oder

Code:

---

---3-------------
------------------
------------------
------------------
1---------------2

---

würde bei der 1 auf Rechts auch die 3 gewählt werden, aber ist soweit von der 1 in der Y-Ebene entfernt, dass er auf die 2 springt.

Was für dich intuitiv ist oder nicht - dafür kannst du die Grenzwerte passend wählen.

Die Option halt ich zwar für mit die schönste, wenn auch extrem umständlich zu implementieren, einziges Problem wo man drüber nachdenken könnte: auch hierbei können durchaus Fälle auftreten, wo einzelne Punkte nicht erreicht werden können. Evtl kann man das auch durch entsprechende Grenzwertwahl umgehen, oder man sucht sich eine noch komplexere Option - so was wie ein Algorythmus der berechnet, welche Punkte nicht erreichbar sind und dann ggf. dynamisch die Grenzwerte hochsetzt/für einzelne Pfade damit der Punkt erreichbar werden kann (Erreichbarkeitsproblem für Graphen, wenn du die erreichbarkeit von Ziel auf Ziel mit einer Richtungseingabe als Graph betrachtest)? Was die implementierung nicht gerade unkomplizierter macht ~.~

Danke schonmal für die Antworten, die letzte Lösung gefällt mir soweit ganz gut.
Wenn man da als Grenzwert für das X/Y-Abstand-Verhältnis 1 nimmt, also quasi alles in Betracht zieht, was innerhalb eines 45° Winkels liegt, sollte eigentlich nichts unerreichbar werden, in meinem Beispiel mit der 5 in der Mitte wäre die 5 gerade noch am Rand der betrachteten Punkte und würde entsprechend gewählt werden.
Ich spiel das noch für ein paar Beispiele durch und wenns mir gefällt, freu ich mich auf die Implementierung :P