2013-01-23 23 views
11

Was ich versuche zu tun ist, wie viele Sechsecke zwischen zwei Punkten auf einem Hex-Gitter sind. Ich habe versucht, online nach einer Formel zu suchen, aber ich war nicht in der Lage, eine zu finden, die dem Typ des Hex-Gitters entspricht, das ich verwende.Berechnung der Entfernung auf einem Sechseck-Gitter

Das Hex-Gitter ist wie diese mit dem gleichen Koordinatensystem angelegt: http://www.gamedev.net/index.php?app=core&module=attach&section=attach&attach_rel_module=ccs&attach_id=1962

Ich bin mir bewusst, dass dies nicht möglich sein, kann mit diesem System koordinieren, aber das ist ein letzter verzweifelter Versuch, bevor ich zurück und ändern gehen es. Vielen Dank im Voraus. Hier

+0

Beziehen Sie sich auf die Punkte, die auf den Sechsecken zentriert sind? Mit anderen Worten, versuchen Sie herauszufinden, wie viele zwischen [0,0] und [3,3] liegen würden? – ChiefTwoPencils

+0

Ja das ist genau das, was ich herausfinden möchte – DeathorGlory9

+0

wie definierst du zwischen? der Satz von hex zwischen zwei Punkten ist nicht einzigartig – thang

Antwort

4

Thanks @ user2709663 und @jonathankoren für Antworten zu geben. Ich verbringe viel Zeit mit Ihren Antworten, aber beide haben Probleme. Zumindest die Art des für diese Antworten berücksichtigten Rasters wird nicht klar angegeben. Jedoch fand ich eine sehr nette Tutorial- und Code-Implementierung dieses Problems zusammen mit einer Bibliothek zur Verwaltung von Hex-Grids unter: http://www.redblobgames.com/grids/hexagons/ (Bibliothekscode: http://www.redblobgames.com/grids/hexagons/implementation.html).Ich habe auch eine Matlab-Version des Abstands Code für die "odd-q" vertikales Layout wie folgt implementieren:

function f = offset_distance(x1,y1,x2,y2) 
    ac = offset_to_cube(x1,y1); 
    bc = offset_to_cube(x2,y2); 
    f = cube_distance(ac, bc); 
end 

function f = offset_to_cube(row,col) 
    %x = col - (row - (row&1))/2; 
    x = col - (row - mod(row,2))/2; 
    z = row; 
    y = -x-z; 
    f = [x,z,y]; 
end 

function f= cube_distance(p1,p2) 
    a = abs(p1(1,1) - p2(1,1)); 
    b = abs(p1(1,2) - p2(1,2)); 
    c = abs(p1(1,3) - p2(1,3)); 
    f = max([a,b,c]); 
end 

Hier ist ein Matlab Testcode

sx = 6; 
sy = 1; 
for i = 0:7 
    for j = 0:5 
     k = offset_distance(sx,sy,i,j); 
     disp(['(',num2str(sx),',',num2str(sy),')->(',num2str(i),',',num2str(j),')=',num2str(k)]) 
    end 
end 
0

ist suboptimal, aber nicht zu suboptimale (sollte O (n) sein) Algorithmus:

Erstens, eine Funktion machen, dass, wenn ein Sechseck in dem hex Gitter an einer bestimmten Stelle bestimmt, mit einem Liniensegment schneidet, ein bestimmter Startpunkt und Endpunkt (zum Beispiel die sechs Linien, aus denen es besteht und etwa: http://alienryderflex.com/intersect/)

Zweitens, machen Sie eine Funktion, die bestimmt, welches Sechseck auf dem Hex-Gitter ein Punkt ist. Geben Sie Ihren Algorithmus folgendermaßen ein:

  • Halten Sie eine Liste aller Hexagone, die das Liniensegment bisher
  • Beginnen Sie mit dem Sechseck, die in der Start des Liniensegments ist
  • überlappt eine für jedes Sechseck umgibt die zuletzt überlappt hat, wenn es ist nicht in der Liste, sehen Sie, ob das lin segmente das Sechseck schneidet. Wenn ja, machen dies der neue Kopf der Liste und wiederholen
  • Wenn wir aus Hexagone laufen zu testen, geben Sie die Liste, die wir
  • gemacht haben

Ich würde vorschlagen, dass Sie den Fall eines Liniensegments testen sein genau parallel zu und entlang der Naht zwischen Sechsecken, um zu sehen, ob Sie die Sechsecke auf einer Seite, auf beiden Seiten oder auf keiner Seite bekommen (und damit aufhören).

2

Um einen kürzesten Weg zwischen zwei Flüche zu finden:

  1. von einem hex Ab
  2. Während auf verschiedenen Reihen, eine diagonale Richtung zu anderen Reihe folgen.
  3. Während Sie in derselben Reihe sind, gehen Sie geradeaus in Richtung des anderen Sechsecks.

ist der Unterschied in der x-Richtung dydx und die Differenz in der y-Richtung zurückgerufen. Wenn dy/2 > dx, müssen Sie Schritt zwei nicht tun, so ist die Entfernung einfach dy. Ansonsten ist die Entfernung dy + (dx - dy/2). Es sei denn, ich habe einen Fehler gemacht.

+0

Danke, es funktioniert nicht 100%, aber es ist ziemlich nah. – DeathorGlory9

0

Wenn Fliesen auf dem Gitter kann möglicherweise blockiert werden, dann sind Sie in der A interessiert * (oder A-Star) Labyrinth-Lösung Algorithmus: http://labs.makemachine.net/2010/03/a-star-maze-solver/

Der Mechanismus in diesem Video verwendet bezieht sich auf ein Raster von Quadraten , aber mit kaum einer zusätzlichen Codierung könnte man es auf ein Sechsecknetz anwenden. Für jede Kachel weiß der Solver, welche Kacheln als nächstes zu verwenden sind, da die Kacheln Zeiger auf ihre umgebenden Kacheln speichern.In einem Gitter aus Quadraten würde jede Kachel maximal 4 Zeiger speichern ( maximal, da sie nur Zeiger auf nicht blockierte Kacheln speichern), und der einzige Unterschied in Ihrem Fall wäre das Speichern von maximal 6 Zeigern.

Wenn Kacheln immer verfahrbar sind, dann wird A * sicherlich die Arbeit erledigen, aber es gibt wahrscheinlich einen schnelleren Weg. Wenn ich deine Frage richtig interpretiere, interessiert dich das nicht in einer Entfernung, sondern in einer ganzzahligen Zählung der Anzahl von Hexen zwischen 2 vorgegebenen Hexes? Versuchen Sie Folgendes:

class Coord { 
    int x; 
    int y; 
} 

int dist(Coord hex1, Coord hex2) { 
    int xSteps = Math.abs(hex1.x - hex2.x); 
    int ySteps = Math.abs(hex1.y - hex2.y); 

    return Math.max(xSteps, ySteps) + Math.abs(xSteps - ySteps); 
} 

Warum können Sie fragen? Bei dieser Frage geht es darum, wie oft wir uns bewegen müssen vertikal oder horizontal im Gegensatz zu diagonal. Wir wollen uns so weit wie möglich diagonal bewegen, sonst sind wir nicht schlau bei unseren Entfernungen. Math.abs(xSteps - ySteps) ist die Anzahl der nicht diagonalen Bewegungen, die wir machen müssen. Fügen Sie dazu die größeren Entfernungen von x und y hinzu, und Sie sind fertig.

+0

Das scheint nicht zu funktionieren, wenn ich die Koordinaten 0,0 und 3,3 verwende, ist die zurückgegebene Entfernung 3 statt 4. – DeathorGlory9

6

Wenn Sie ein Koordinatensystem benutzt hatte, die in zwei Richtungen entlang der Maserung der Flüche geht, könnten Sie verwendet haben:

distance = max(
    abs(dest.y - start.y),  
    abs(dest.x - start.x), 
    abs((dest.x - dest.y)*-1 - (start.x - start.y)*-1) 
) 

aber Sie nicht, Sie verwenden ein squiggly Koordinatensystem, das geht mit dem Korn nur in eine Richtung (horizontal). Zum Glück können wir zwischen den beiden mit

straight.y = squiggle.y 
straight.x = ciel(squiggle.y/-2) + squiggle.x 

Also, die Lösung für die Ferne mit diesem System von Gleichungen zu verwandeln bekommt man:

distance = max(
    abs(dest.y - start.y),  
    abs(ceil(dest.y/-2) + dest.x - ceil(start.y/-2) - start.x), 
    abs(-dest.y - ceil(dest.y/-2) - dest.x + start.y + ceil(start.y/-2) + start.x) 
) 

Das wird Sie die Manhattan-Distanz zwischen zwei Flüche erhalten mit nur ihre Koordinaten (Angenommen, ich habe keine Tippfehler gemacht, die x und y transponieren, da Ihr Gitter um 90 Grad von meinem gedreht ist. Du musst jedoch einen Keks für meinen Middle-School-Algebra-Lehrer kaufen, damit er funktioniert, sonst hätte ich das Distributionseigentum durcheinander gebracht.

Hinweis: Möglicherweise müssen Sie mit negativen Koordinaten arbeiten, habe ich nicht überprüft.

2

The accepted answer ist falsch. Ich war anfangs misstrauisch, als es erwähnte, orthogonale Koordinaten auf nicht-orthogonalen Achsen zu verwenden, aber das Ausführen des Codes gegen meine eigene Lösung zeigt, dass die Überschätzung der Distanzverbindungen.

Die tatsächliche richtige Lösung ist:

def hexDistance(start, dest): 
    if (start.x == dest.x): 
    return abs(dest.y - start.y) 
    elif (start.y == dest.y): 
    return abs(dest.x - start.x) 
    else: 
    dx = abs(dest.x - start.x) 
    dy = abs(dest.y - start.y) 
    if start.y < dest.y: 
     return dx + dy - int(math.ceil(dx/2.0)) 
    else: 
     return dx + dy - int(math.floor(dx/2.0)) 

Dies verwendet die Hex-> Quadrat Darstellung:

 
     ------   
------ 0, +1 ------ 
-1, +1 ------ +1, +1 
------ 0, 0 ------ 
-1, 0 ------ +1, 0 
------ 0, -1 ------ 
     ------   

-------------------------- 
| -1, +1 | 0, +1 | +1, +1 | 
|-------------------------- 
| -1, 0 | 0, 0 | +1, 0 | 
|--------------------------| 
|  | 0, -1 |  | 
-------------------------- 
+0

ist das die richtige Lösung für die ungerade-r obwohl? – Artistan

2

MH Rasel diesen Beitrag in seinem früheren verknüpft Antwort: Hexagonal Grids. Nach diesem ausgezeichneten Beitrag fand ich heraus, dass ich Würfelkoordinaten brauchte; das gibt die einfachste Möglichkeit, die Entfernungen zu berechnen. Hier ist ein Code-Schnipsel in Kotlin:

data class Point(val x: Int, val y: Int, val z: Int) { 

    fun distance(b: Point): Int { 
     return (abs(x - b.x) + abs(y - b.y) + abs(z - b.z))/2 
    } 

} 

var x = 0 
var y = 0 
var z = 0 

val p1 = Point(x, y, z) // starting position 

val steps = "ne,ne,ne".split(",") // go to North-East 3 times 

for (direction in steps) { 
    when(direction) { 
     "n" -> { ++y; --z } 
     "ne" -> { ++x; --z } 
     "se" -> { ++x; --y } 
     "s" -> { --y; ++z } 
     "sw" -> { --x; ++z } 
     "nw" -> { ++y; --x } 
    } 
} 

val p2 = Point(x, y, z) // we arrived here 
val dist = p1.distance(p2) // the result is here (in this example: 3) 

Edit: Ich gehe davon eine abgeflachte hex grid.

0

Wenn Ihre sechseckigen Kacheln Richtungen haben: N, NE, S, S, SW, NW wie in Advent of Code 2017 problem 11 und Sie versetzen das Ziel auf (0,0) (durch Subtrahieren Ihrer Position vom Ziel im Voraus) die folgende Logik für mich gearbeitet:

def distance(self): 
    # Take diagonal steps towards self.x == 0 
    steps = abs(self.x) 
    # y moves closer to 0 by steps because moving diagonal, but never moving too far 
    if self.y > 0: 
     # Might still be positive, but never negative 
     y = max(self.y - steps, 0) 
    else: 
     # Might still be negative, but not positive 
     y = min(self.y + steps, 0) 
    # You move 2 positions north/south by a single move so divide y's by 2 
    return abs(y) // 2 + abs(steps) 

ich denke, es könnte für die hex-Gitter mit Richtungen Ost und West statt Nord und Süd wie das Ihre Arbeit, indem nur die Rollen von x und y umgeschaltet wird. In diesem Fall würden Sie sich diagonal (falls erforderlich) usw. zu self.y == 0 bewegen.

Verwandte Themen