Formel Umrechnung Koordinaten einer sechseckigen Karte?

Der Titel ist zugegebener Masen etwas dürftig aber mir ist kein besserer eingefallen

Zu meinem Problem/Frage:

Aktuell habe ich in meinem Spiel eine normale isometrische Karte bestehend aus 4-eckigen Kacheln. Jedoch will ich die Karte jetzt umbauen und auf sechseckige Kacheln umsteigen.

Aus diesem Grund habe ich mir ein paar Gedanken darüber gemacht und bin zu Ergebnis gekommen, dass ich um optimal mit der Karte arbeiten zu können 2 verschiedene Koordinatensystem benötige. Zu sehen in der Grafik:

Das Koordinatensystem, welches durch die jeweilige obere Zahlenreihe dargestellt wird, benötige ich z.B. zum Zeichnen der Karte, da ich im Endergebnis von der Form her kein um 45° gedrehtes 4-eck haben will und ich mit diesem System das Zeichnen der Karte so recht einfach umsetzen kann. Zusätzlich vereinfacht dieses System noch das herausfinden, ob ein Feld den Rand bildet. Denn die äußeren Reihen der kompletten Karte sollen nicht bebaubar sein und im ganzen eine schöne Fläche zu erhalten.

Das Koordinatensystem, welches durch die jeweiligen unteren Zahlenreihen dargestellt wird benötige ich zur Berechnung der Distanz zwischen 2 Feldern.

Was ich jetzt suche ist ein Funktion, mit der ich mit den Koordinaten des 1. Systems die Koordinaten des 2. Systems berechnen kann oder noch besser eine Formel, mit der ich mit Hilfe des 1. Systems die Entfernung zwischen 2 Feldern berechnen kann (wobei diese nicht zu komplex sein sollte, dass man diese auch beruhigt in einem SQL Query einsetzen kann; und das wird bei der Formel wohl der Knackpunkt sein)

Wie im Screen zu sehen ist, komme ich schon auf die Koordinaten beider Systeme aber leider nur im zeichnen und nicht, wenn ich nur die Koordinaten eines einzelnen Feldes gegeben habe.

Und wehe ihr habt jetzt eine total einfache Formel. Dann muss ich mich selbst in Frage stellen, weil ich schon nen Stück dran sitz

Hm in dem Bild hast du 10 Reihen, warum nicht 5?

Auch wenn jedes 2.Feld etwas nach unten versetzt ist, kannst du doch so tun, als wäre es eine Reihe.

Original von blum

Hm in dem Bild hast du 10 Reihen, warum nicht 5?

Auch wenn jedes 2.Feld etwas nach unten versetzt ist, kannst du doch so tun, als wäre es eine Reihe.

Habe mir beides mal angeschaut (die von dir genannte Variante ist nur auskommentiert ) und bei meiner Variante ist es die komplette obere und untere Reihe, welche als Kartenende gilt und nicht bebaut werden darf. Würde ich jedes 2. Feld versetzen, wäre der Codeaufwand größer, den ich benötigen würde um das zu überprüfen. Nagut ein if x%2 != 0 ist jetzt kein hoher Aufwand... aber sonst sehe ich nicht unbedingt nen Vorteil, wenn ich die Reihe versetze. Zumin habe ich auch dann keine einfache Formel gefunden, um den Abstand  zu berechnen (ohne herbeinahme des 2. Koordinatensystems).

Ich denke das hier hilft dir weiter: http://www.gamedev.net/reference/articles/article1800.asp

Inklusive Pixel => Koordiante und Koordinate => Pixel..

Das ganze nochmal => http://www.gamedev.net/reference/articles/article747.asp

So long...

Maxx

Was fuer ein Brainfuck. Ahhh.

Ich habe grade geschlagene 30 Minuten damit verbracht eine Formel zu finden. Ich fand keine die 100%ig passt. Ich weiss, das ist sehr bloed so etwas vorzuschlagen, da es keine Antwort auf Deine Frage ist aber was spricht dagegen ein "normales" Koordinatensystem zu nehmen:

Code:

0,0     2,0     4,0     6,0
    1,0     3,0     5,0
0,1     2,1     4,1     6,1
    1,1     3,1     5,1 

damit wird die Abstandsberechnung trivial: max(|x1-x2|, |y1-y2|)

das Zeichnen der Karte ist auch nicht so schwer: 2 Schleifen ineinander und die aeussere Schleife setzt immer einen Offset entweder 0 oder die Anzahl der Pixel die Du einrueckst.

Und die Bestimmung des Randes ist auch ganz einfach, der rechte und obere Rand sind 0 und der linke und untere Rand sind maxX und maxY.

Edit: achja die 2 Gamedev Artikel wollte ich auch noch posten aber MrMaxx war schneller ;-)

Original von MrMaxx

Ich denke das hier hilft dir weiter: http://www.gamedev.net/reference/articles/article1800.asp

Inklusive Pixel => Koordiante und Koordinate => Pixel..

Das ganze nochmal => http://www.gamedev.net/reference/articles/article747.asp

So long...

Maxx

Die ordnen die Felder auf jeden Fall genau so an wie ich, jedoch kann ich ich in den Artikeln keine Formel finden, um die Entfernung zwischen 2 Feldern zu berechnen oder wie ich von von meinem "1. Koordinatensystem" auf die Koords meines "2. Systems" komme? (ist aber auch möglich, dass ich das übersehen habe)

Aber trotzdem danke für Links. Nehmen mir bestimmt Denkarbeit bei der Minimap ab

Sorry für Doppelpost aber da kam während des Schreibens der ersten Antwort schon die nächste

Original von cherry

Was fuer ein Brainfuck. Ahhh.

Ich habe grade geschlagene 30 Minuten damit verbracht eine Formel zu finden. Ich fand keine die 100%ig passt. Ich weiss, das ist sehr bloed so etwas vorzuschlagen, da es keine Antwort auf Deine Frage ist aber was spricht dagegen ein "normales" Koordinatensystem zu nehmen:

Code:

0,0     2,0     4,0     6,0
    1,0     3,0     5,0
0,1     2,1     4,1     6,1
    1,1     3,1     5,1 

damit wird die Abstandsberechnung trivial: max(|x1-x2|, |y1-y2|)

das Zeichnen der Karte ist auch nicht so schwer: 2 Schleifen ineinander und die aeussere Schleife setzt immer einen Offset entweder 0 oder die Anzahl der Pixel die Du einrueckst.

Und die Bestimmung des Randes ist auch ganz einfach, der rechte und obere Rand sind 0 und der linke und untere Rand sind maxX und maxY.

Aber warum bitte so ne einfache Formel?? AHHH! Ich habe heute sonst was für A4 Blätter mit kompliziertem Zeug vollgeschrieben und dann geht das mit sowas einfachem o0.

Dass das zeichnen nicht so schwer ist kann ich bestätigen. Wie erwähnt habe ich die Form auch schon getestet und der entsprechende Code ist nur rauskommentiert.

Aber bei dem Rand kann ich dir nicht zustimmen, denn von der y Koordinate will ich ja nur jedes 2. Feld. Aber ist trotzdem einfach. Einfach den Rest bei der Division durch 2 überprüfen.

Nochmal zur Formel... Die ist wäre ja echt einfacher als die, für mein "2. Koordinatensystem". Da hatte ich dann:

(|x1-x2| |y1-y2| |((x1-x2) - (y1-y2))|)/2

In PHP Code vllt verständlicher (wen es interessiert):

PHP:

$dX = $x1 - $x2;
$dY = $y1 - $y2;
$distance = (abs($dX)   abs($dY)   abs($dX - $dY)) / 2;
?>

 Naja wie auch immer Danke für die Formel. Werde mir nochmal angucken ob die auch wirklich immer ein richtiges Erg. bringt. Aber beim grob durchdenken erscheint mir es schonmal so.

Ah, ich habe gerade gesehn da ist ein Bug in meiner Abstandsformel... ich mach mich nochmal dran..

Wenn Du von 0,0 auf 1,1 willst stimmt sie nicht.

Deinen Einwand bezueglich des Randes verstehe ich nicht ganz.

Stimmt auch wenn man von 3,5 auf 4,6 o.ä. will.

Code:

(0,0)     (2,0)     (4,0)     (6,0)
      1,0       3,0       5,0
0,1        2,1        4,1      6,1
      1,1       3,1       5,1 

Das mit dem Rand ist nur ne Kleinigkeit denn ich will nur die Felder in den Klammern. Aber ist nicht das Prob:

PHP:

// oberer Rand ja/nein?
if($y%2 != 0)
    echo "joar!";
?>

 Naja mal gucken ob man die Formel noch abwandeln kann *wiederBlätterUndStiftRaushol*.

Hm, ist doch nicht so trivial wie es aussah :-)

Hab noch ein Script gebaut um zu testen. Da ich keine grosse schoene Karte hab wie Du faellts mir aber schwer zuverlaessig Testcases zu baun. Vielleicht hilfts Dir, ist ziemlich selbsterklaerend (PLUS durch das plus Zeichen ersetzen... das Forum verschluckt das irgendwie). Weder f1 noch f2 sind korrekt...

PHP:

  //                   x1 y1  x2 y2
  $tests = array(array( 0, 0,  1, 1 ), // 2
                 array( 2, 2,  3, 3 ), // 1
                 array( 2, 0,  5, 1 ), // 3
                 array( 4, 1,  3, 1 ), // 1
                 array( 0, 0,  6, 6 ), // 7
                 array( 0, 0,  5, 1 )  // 5           
                );
  $result = array(2, 1, 3, 1, 7, 5);
  foreach($tests as $i => $t)
  {
    $r = f2($t[0], $t[1], $t[2], $t[3]);
    if($r != $result[$i])
      echo("testcase " . $i . ": failed; result=" . $r . " expected=" . 
        $result[$i] . "
");
    else
      echo("testcase " . $i . ": ok
");
  }  
  function f1($x1, $y1, $x2, $y2)
  {
    return max(abs($x1-$x2), abs($y1-$y2));
  }
  function f2($x1, $y1, $x2, $y2)
  {
    return max(max(abs($x1-$x2), abs($y1-$y2)), abs($y1-$y2)  PLUS 1);
  }
?>

Danke für deine Bemühungen. Ich werde die Formel nochmal durchtesten aber ich glaube nichtmehr heute *gähn*

Dass der Post nicht so leer ist hier noch das Bsp der Karte mit "normalem Koordsystem"... zur Vorstellung und so.

Edit:

Deine neue Formel ist leider auch nicht Fehlerfrei. Bsp: 1,1 -> 5,4

Od.: 1,1 auf 10,10 weicht um 4 Felder ab

Ich hab auch einige Spiele mit Hexfeldern und verwende zur Entfernungsberechnung einen AStar-Algorythmus. Bei mir sind zwar die Tiles etwas anders angeordnet (die zweite Spalte nicht nach unten versetzt, sondern die zweite Reihe), aber die Anpassung sollte nicht so schwer sein.

Nach langem Gruebeln bin ich jetzt auch auf Deine Loesung gekommen...

Mit folgendem Koordinatensystem

Code:

 0, 0      -1, 1       -2, 2       -3, 3       -4, 4
      0, 1       -1, 2       -2, 3       -3, 4
 1, 1       0, 2       -1, 3       -2, 4       -3, 5
      1, 2        0, 3       -1, 4       -2, 5
 2, 2       1, 3        0, 4       -1, 5       -2, 6
      2, 3        1, 4        0, 5       -1, 6
 3, 3       2, 4        1, 5       0, 6        -1, 7

was im Grunde Deinem 2. entsprechen sollte. Die Seite hier bestaetigt die Formel auch: http://jmz.iki.fi/blog/programming/hexagonal_maps

Ich werde es jetzt so machen, dass ich beide von mir im ersten Post genannten Koordinatensystem nutzen werde. Es bekommt einfach beim Eintragen der Karte in die DB jedes Feld seine Koordinaten für jedes System zugeordnet.

Dadurch kann ich alles mir einfallenden Probleme recht einfach und performant lösen.

Original von progs

Ich hab auch einige Spiele mit Hexfeldern und verwende zur Entfernungsberechnung einen AStar-Algorythmus. Bei mir sind zwar die Tiles etwas anders angeordnet (die zweite Spalte nicht nach unten versetzt, sondern die zweite Reihe), aber die Anpassung sollte nicht so schwer sein.

Da ich gerade mit "AStar-Algorithmus" nichts anfangen konnte hab eich mal fix einen Artikel darüber überflogen und es ist, wenn ich das jetzt auf die schnelle richtig verstanden habe, genau das was ich aktuell schon auf meiner 4eckigen Karte mache.

Und um das optimal  zu gestalten gibt es ja einen gewissen Erwartungswert vom Weg. Ich zitiere dafür mal aus einem Artikel:

Pfadbewertung

Der Schlüssel dazu, welche Quadrate für den Pfad in Frage kommen, ist folgende Gleichung:

F = G H

wobei

• G = Die Bewegungskosten, um vom Startpunkt A zu einem gegebenen Quadrat des Gitters unter Verwendung des dafür ermittelten Pfades zu gelangen.
• H = Die geschätzten Kosten, um von dem gegebenen Quadrat zum Zielpunkt B zu gelangen. Dies wird oft heuristisch genannt, was ein bisschen verwirrend sein kann. Der Grund, warum dies so genannt wird, ist, dass diese Kosten auf Vermutung beruhen, denn tatsächlich kennen wir die wirkliche Entfernung erst, wenn wir den Pfad dorthin gefunden und auf dem Weg liegende Hindernisse (Wände, Wasser, etc.) berücksichtigt haben. In diesem Artikel wird ein möglicher Weg gezeigt, wie H ermittelt werden kann; es gibt aber viele weitere, die in anderen Web-Artikeln beschrieben sind.

Genau dieses H meine ich. Man könnte das war auch weglassen, aber dann läuft der Algorithmus in den meisten Fällen ja unnötig länger. Denn dieses H bildet bei mir bisher die direkte Entfernung zwischen 2 Feldern und das kann ich auch so bei den Hexafeldern übernehmen.

Gruß,
n26

Der Abstand im ersten System ist wirklich einfach nur das Minmum der Beträge der y und x -Koodinaten-Differenzen, wenn es möglich ist, über die Ecken zum Nachbarfeld zu gehen. Ansonsten ist es die Summe der Beträge.
Für die Distanz auf der Hex-Karte, must Du durch Start- und End-Punkt jeweils die orthogonalen Diagonalen (die Du ja schon für die erste Koordinate gewählt hast) nehmen und gucken, wo die einen Schnittpunkt haben. Die zweite Diagonale wäre dann z.B. d = b-y+x, wobei b die Breite des Feldes wäre. Die Schnittpunkte liegen für x1,d1 und x2,d2 dann bei x1,d2 und x2,d1 und die Distanz auf dem Weg ist dann |d1-d2| + |x1-x2|.
=> distance := |-y1+x1+y2-x2| + |x1-x2|
Kleiner Test:
y1=y2 und x1=x2 => distance = 0
1,1 -> 10,10 => distance = |-1+1+10-10| + |1-10| = 0 + 9 = 9
-1,2 -> 2,6 => distance = |-2-1+6-2| + |-1-2| = 1 + 3 = 4
A* funktioniert dafür nicht, weil man für die Abschätzung des Restweges (Heuristik) die Entfernung zum Zielpunkt braucht (damit würde sich das in den Schwanz beißen). Ausserdem ist das Problem in O(1) lösbar und dann sollte man das auch so machen
Um die Uhrzeit kann da natürlich mal ein kleiner Fehler drin sein

Original von Todi42

1,1 -> 10,10 => distance = |-1+1+10-10| + |1-10| = 0 + 9 = 9

Habe jetzt deine Formel noch nicht durchdacht, werde ich aber noch tun. Was mir aber aufgefallen ist, ist, dass der Abstand zw 1,1 und 10,10 doch 14 Felder beträgt!?

Original von n26

Original von Todi42

1,1 -> 10,10 => distance = |-1+1+10-10| + |1-10| = 0 + 9 = 9

Habe jetzt deine Formel noch nicht durchdacht, werde ich aber noch tun. Was mir aber aufgefallen ist, ist, dass der Abstand zw 1,1 und 10,10 doch 14 Felder beträgt!?

 Wenn ich auf dem Bild, dass Du als aller erstes gepostet hast, die Spalte ganz rechts so weit nach oben verlängere, dass ich bei 10,10 ankommen, dann liegt 10,10 mit 1,1 genau auf einer Diagonalen und bei einer Breite von 10 Feldern ergibt das genau 9 Schritte über die Diagonale.

Original von Todi42

Original von n26

Original von Todi42

1,1 -> 10,10 => distance = |-1+1+10-10| + |1-10| = 0 + 9 = 9

Habe jetzt deine Formel noch nicht durchdacht, werde ich aber noch tun. Was mir aber aufgefallen ist, ist, dass der Abstand zw 1,1 und 10,10 doch 14 Felder beträgt!?

 Wenn ich auf dem Bild, dass Du als aller erstes gepostet hast, die Spalte ganz rechts so weit nach oben verlängere, dass ich bei 10,10 ankommen, dann liegt 10,10 mit 1,1 genau auf einer Diagonalen und bei einer Breite von 10 Feldern ergibt das genau 9 Schritte über die Diagonale.

Hm, aber nur wenn du das 2. Koordinatensystem im ersten Bild nimmst. Das ist ja eh schon das mit dem es ganz einfach geht

Ja, das hatte ich genommen Ok, 6 Thema verfehlt.

Ich habe mal in den Sourcen von einem alten Spiel von mir geguckt, da hatte ich das schon mal gemacht. Es werden drei mögliche Wege berechnet, und davon der kürzeste genommen. Neben dem Weg über den Schnittpunkt der Diagonalen, gibt es noch den Weg, über eine der Diagonalen und dann die Senkrechte zu gehen. xa, ya und xb, yb sind Start- und Ziel-Koordinaten
[code]
  // calculate diagonal numbers
  data::default_int right_diag_a = xa - ya /2;
  data::default_int right_diag_b = xb - yb /2;
  data::default_int left_diag_a = xa + (ya+1) /2;
  data::default_int left_diag_b = xb + (yb+1) /2;
   
  const int dright = std::abs(right_diag_a - right_diag_b);
  const int dleft = std::abs(left_diag_a - left_diag_b);
  return data::distance(static_cast(
  std::min(dy + dright, std::min(dright + dleft, dleft + dy))));
[/code]

Und? Gibt es noch eine Rückmeldung zum Thema?

Original von Todi42

Und? Gibt es noch eine Rückmeldung zum Thema?

Sorry, garnicht gesehen, dass hier nochwas war.... Ich habe mir jetzt deine Formel nicht im Detail angeschaut, da sie eher weniger direkt für SQL Querys geeignet scheint. Danke trotzdem.

Ich werde jetzt bei mir für jedes Feld die Koordinaten beide von mir genannter Koordinatensystem eintragenn und habe somit alle Möglichkeiten, die ich brauche.

Die Wegberechnung werde ich dann so machen:

Original von n26

PHP:

$dX = $x1 - $x2;
$dY = $y1 - $y2;
$distance = (abs($dX) plus abs($dY) plus abs($dX - $dY)) / 2;
?>

Gruß,
n26