Sechseckige Zeichenbewegung mit axialen Koordinaten

() translation by (you can also view the original English article)

Final product image — What You'll Be Creating

Im ersten Teil der Serie haben wir die verschiedenen Koordinatensysteme für hexagonale Kachel-basierte Spiele mit Hilfe eines hexagonalen Tetris-Spiels untersucht. Eine Sache, die Sie vielleicht bemerkt haben, ist, dass wir uns immer noch auf die Versatzkoordinaten verlassen, um die Ebene mithilfe des levelData-Arrays auf den Bildschirm zu zeichnen.

Vielleicht sind Sie auch neugierig, wie wir die Axialkoordinaten einer hexagonalen Kachel aus den Pixelkoordinaten auf dem Bildschirm bestimmen können. Die im Tutorial zum hexagonalen Minensuchboot verwendete Methode basiert auf den Versatzkoordinaten und ist keine einfache Lösung. Sobald wir dies herausgefunden haben, werden wir Lösungen für die Bewegung und Pfadfindung hexagonaler Zeichen erstellen.

1. Konvertieren von Koordinaten zwischen Pixel und Axial

Dies wird etwas Mathematik beinhalten. Wir werden das horizontale Layout für das gesamte Tutorial verwenden. Beginnen wir damit, eine sehr hilfreiche Beziehung zwischen der Breite und Höhe des regulären Sechsecks zu finden. Bitte beachten Sie das Bild unten.

Hexagonal tile its angles lengths are displayed

Betrachten Sie das blaue reguläre Sechseck links im Bild. Wir wissen bereits, dass alle Seiten gleich lang sind. Alle Innenwinkel betragen jeweils 120 Grad. Wenn Sie jede Ecke mit der Mitte des Sechsecks verbinden, erhalten Sie sechs Dreiecke, von denen eines mit roten Linien dargestellt ist. Dieses Dreieck hat alle Innenwinkel gleich 60 Grad.

Wenn die rote Linie die beiden Eckwinkel in der Mitte teilt, erhalten wir 120/2 =60. Der dritte Winkel beträgt 180- (60+ 60)=60, da die Summe aller Winkel innerhalb des Dreiecks 180 Grad betragen sollte. Somit ist das Dreieck im Wesentlichen ein gleichseitiges Dreieck, was weiter bedeutet, dass jede Seite des Dreiecks die gleiche Länge hat. Im blauen Sechseck sind die beiden roten Linien, die grüne Linie und jedes blaue Liniensegment gleich lang. Aus dem Bild geht hervor, dass die grüne Linie hexTileHeight/2 ist.

Wenn wir zum Sechseck rechts gehen, können wir sehen, dass bei einer Seitenlänge von hexTileHeight / 2 die Höhe des oberen dreieckigen Teils hexTileHeight / 4 und die Höhe des unteren dreieckigen Teils hexTileHeight / 4 betragen sollte summiert sich auf die volle Höhe des Sechsecks, hexTileHeight.

Betrachten Sie nun das kleine rechtwinklige Dreieck oben links mit einem grünen und einem blauen Winkel. Der blaue Winkel beträgt 60 Grad, da er die Hälfte des Eckwinkels ist, was wiederum bedeutet, dass der grüne Winkel 30 Grad (180-(60+90) beträgt. Mit diesen Informationen erhalten wir eine Beziehung zwischen der Höhe und Breite des regulären Sechsecks.

1	tan 30 = opposite side/adjacent side;
2	1/sqrt(3) = (hexTileHeight/4)/(hexTileWidth/2);
3	hexTileWidth = sqrt(3)*hexTileHeight/2;
4	hexTileHeight = 2*hexTileWidth/sqrt(3);

Konvertieren von Axial- in Pixelkoordinaten

Bevor wir uns der Konvertierung nähern, betrachten wir noch einmal das Bild des horizontalen hexagonalen Layouts, in dem wir die Zeile und Spalte hervorgehoben haben, in denen eine der Koordinaten gleich bleibt.

Horizontal hexagonal layout with rows and columns highlighted where coordinates remain same

Wenn man den y-Wert des Bildschirms betrachtet, kann man sehen, dass jede Zeile einen y-Versatz von 3*hexTileHeight/4 hat, während man auf der grünen Linie nach unten geht. Der einzige Wert, der sich ändert, ist i. Wir können daher schließen, dass der y-Pixelwert nur von der axialen i-Koordinate abhängt.

1	y= (3hexTileHeight/4)i;
2	y = 3/2si;

Wobei s die Seitenlänge ist, die als hexTileHeight/2 befunden wurde.

Der x-Wert des Bildschirms ist etwas komplizierter. Wenn Sie die Kacheln in einer einzelnen Reihe betrachten, hat jede Kachel einen x-Versatz von hexTileWidth, der eindeutig nur von der axialen j-Koordinate abhängt. Jede alternative Zeile hat jedoch einen zusätzlichen Versatz von hexTileWidth/2 in Abhängigkeit von der axialen i-Koordinate.

Wenn wir uns die grüne Linie noch einmal vorstellen, wäre die Linie vertikal gewesen und hätte die Gleichung x=j*hexTileWidth erfüllt. Da sich die einzige Koordinate, die sich entlang der grünen Linie ändert, i ist, hängt der Versatz davon ab. Dies führt uns zu der folgenden Gleichung.

1	x=jhexTileWidth+(ihexTileWidth/2);
2	= j* sqrt(3)hexTileHeight/2 + i sqrt(3)*hexTileHeight/4;
3	= sqrt(3)s(j+ (i/2));

Hier haben wir sie also: die Gleichungen zum Konvertieren von Axialkoordinaten in Bildschirmkoordinaten. Die entsprechende Konvertierungsfunktion ist wie folgt.

var rootThree=Math.sqrt(3);
var sideLength=hexTileHeight/2;
function axialToScreen(axialPoint){
    var tileX=rootThree*sideLength*(axialPoint.y+(axialPoint.x/2));
    var tileY=3*sideLength/2*axialPoint.x;
    axialPoint.x=tileX;
    axialPoint.y=tileY;
    return axialPoint;
}

Der überarbeitete Code zum Zeichnen des hexagonalen Gitters lautet wie folgt.

for (var i = 0; i < levelData.length; i++)
{
    for (var j = 0; j < levelData[0].length; j++)
    {
        axialPoint.x=i;
        axialPoint.y=j;
        axialPoint=offsetToAxial(axialPoint);
        screenPoint=axialToScreen(axialPoint);
        if(levelData[i][j]!=-1){
            hexTile= new HexTileNode(game, screenPoint.x, screenPoint.y, 'hex', false,i,j,levelData[i][j]);
            hexGrid.add(hexTile);
        }
    }  
}

Pixel in Axialkoordinaten konvertieren

Das Umkehren dieser Gleichungen durch einfaches Ersetzen einer Variablen führt uns zum Bildschirm für axiale Umrechnungsgleichungen.

1	i=y/(3/2*s);
2	j=(x-(y/sqrt(3)))/s*sqrt(3);

Obwohl die erforderlichen Axialkoordinaten ganze Zahlen sind, führen die Gleichungen zu Gleitkommazahlen. Wir müssen sie also abrunden und einige Korrekturen vornehmen, wobei wir uns auf unsere Hauptgleichung x+y+z=0 stützen. Die Konvertierungsfunktion ist wie folgt.

function screenToAxial(screenPoint){
    var axialPoint=new Phaser.Point();
    axialPoint.x=screenPoint.y/(1.5*sideLength);
    axialPoint.y=(screenPoint.x-(screenPoint.y/rootThree))/(rootThree*sideLength);
    var cubicZ=calculateCubicZ(axialPoint);
    var round_x=Math.round(axialPoint.x);
    var round_y=Math.round(axialPoint.y);
    var round_z=Math.round(cubicZ);
    if(round_x+round_y+round_z===0){
        screenPoint.x=round_x;
        screenPoint.y=round_y;
    }else{
        var delta_x=Math.abs(axialPoint.x-round_x);
        var delta_y=Math.abs(axialPoint.y-round_y);
        var delta_z=Math.abs(cubicZ-round_z);
        if(delta_x>delta_y && delta_x>delta_z){
            screenPoint.x=-round_y-round_z;
            screenPoint.y=round_y;
        }else if(delta_y>delta_x && delta_y>delta_z){
            screenPoint.x=round_x;
            screenPoint.y=-round_x-round_z;
        }else if(delta_z>delta_x && delta_z>delta_y){
            screenPoint.x=round_x
            screenPoint.y=round_y;
        }
    }
    return screenPoint;
}

Schauen Sie sich das interaktive Element an, das diese Methoden verwendet, um Kacheln anzuzeigen und Taps zu erkennen.

2. Charakterbewegung

Das Kernkonzept der Zeichenbewegung in einem beliebigen Raster ist ähnlich. Wir fragen nach Benutzereingaben, bestimmen die Richtung, finden die resultierende Position, prüfen, ob die resultierende Position innerhalb einer Wand im Raster liegt, oder verschieben den Charakter an diese Position. Sie können sich auf mein Tutorial zur Bewegung isometrischer Zeichen beziehen, um dies in Bezug auf die Konvertierung isometrischer Koordinaten in Aktion zu sehen.

Die einzigen Dinge, die hier anders sind, sind die Koordinatenumwandlung und die Bewegungsrichtungen. Für ein horizontal ausgerichtetes hexagonales Gitter stehen sechs Bewegungsrichtungen zur Verfügung. Wir könnten die Tastaturtasten A, W, E, D, X und Z verwenden, um jede Richtung zu steuern. Das Standardtastaturlayout stimmt perfekt mit den Anweisungen überein, und die zugehörigen Funktionen sind wie folgt.

function moveLeft(){
    movementVector.x=movementVector.y=0;
    movementVector.x=-1*speed;
    CheckCollisionAndMove();
}
function moveRight(){
    movementVector.x=movementVector.y=0;
    movementVector.x=speed;
    CheckCollisionAndMove();
}
function moveTopLeft(){
    movementVector.x=-0.5*speed;//Cos60
    movementVector.y=-0.866*speed;//sine60
    CheckCollisionAndMove();
}
function moveTopRight(){
    movementVector.x=0.5*speed;//Cos60
    movementVector.y=-0.866*speed;//sine60
    CheckCollisionAndMove();
}
function moveBottomRight(){
    movementVector.x=0.5*speed;//Cos60
    movementVector.y=0.866*speed;//sine60
    CheckCollisionAndMove();
}
function moveBottomLeft(){
    movementVector.x=-0.5*speed;//Cos60
    movementVector.y=0.866*speed;//sine60
    CheckCollisionAndMove();
}

Die diagonalen Bewegungsrichtungen bilden mit der horizontalen Richtung einen Winkel von 60 Grad. So können wir die neue Position mithilfe der Trigonometrie mithilfe von Cos 60 und Sine 60 direkt berechnen. Aus diesem movementVektor ermitteln wir die neue resultierende Position und prüfen, ob sie wie unten beschrieben in eine Wand im Raster fällt.

function CheckCollisionAndMove(){
    var tempPos=new Phaser.Point();
    tempPos.x=hero.x+movementVector.x;
    tempPos.y=hero.y+movementVector.y;
    var corner=new Phaser.Point();
    //check tl
    corner.x=tempPos.x-heroSize/2;
    corner.y=tempPos.y-heroSize/2;
    if(checkCorner(corner))return;
    //check tr
    corner.x=tempPos.x+heroSize/2;
    corner.y=tempPos.y-heroSize/2;
    if(checkCorner(corner))return;
    //check bl
    corner.x=tempPos.x-heroSize/2;
    corner.y=tempPos.y+heroSize/2;
    if(checkCorner(corner))return;
    //check br
    corner.x=tempPos.x+heroSize/2;
    corner.y=tempPos.y+heroSize/2;
    if(checkCorner(corner))return;
    
    hero.x=tempPos.x;
    hero.y=tempPos.y;
}
function checkCorner(corner){
    corner=screenToAxial(corner);
    corner=axialToOffset(corner);
    if(checkForOccuppancy(corner.x,corner.y)){
        return true;
    }
    return false;
}

Wir fügen den movementVector zum Heldenpositionsvektor hinzu, um die neue Position für das Zentrum des Heldensprites zu erhalten. Dann finden wir die Position der vier Ecken des Helden-Sprites und prüfen, ob diese kollidieren. Wenn es keine Kollisionen gibt, setzen wir die neue Position auf das Helden-Sprite. Lassen Sie uns das in Aktion sehen.

Normalerweise ist diese Art der frei fließenden Bewegung in einem gitterbasierten Spiel nicht zulässig. Normalerweise bewegen sich Zeichen von Kachel zu Kachel, dh von Kachelmitte zu Kachelmitte, basierend auf Befehlen oder Tippen. Ich vertraue darauf, dass Sie die Lösung selbst herausfinden können.

3. Pathfinding

Hier sind wir also beim Thema Pfadfindung, ein für manche sehr beängstigendes Thema. In meinen vorherigen Tutorials habe ich nie versucht, neue Pfadfindungslösungen zu erstellen, sondern immer leicht verfügbare Lösungen verwendet, die kampferprobt sind.

Dieses Mal mache ich eine Ausnahme und werde das Rad neu erfinden, hauptsächlich weil verschiedene Spielmechaniken möglich sind und keine einzige Lösung allen zugute kommen würde. Es ist also praktisch zu wissen, wie das Ganze gemacht wird, um Ihre eigenen benutzerdefinierten Lösungen für Ihre Spielmechanik zu entwickeln.

Der grundlegendste Algorithmus, der zur Pfadfindung in Gittern verwendet wird, ist der Dijkstra-Algorithmus. Wir beginnen am ersten Knoten und berechnen die Kosten für den Umzug zu allen möglichen Nachbarknoten. Wir schließen den ersten Knoten und bewegen uns zum Nachbarknoten mit den niedrigsten Kosten. Dies wird für alle nicht geschlossenen Knoten wiederholt, bis wir das Ziel erreichen. Eine Variante davon ist der A*-Algorithmus, bei dem wir neben den Kosten auch eine Heuristik verwenden.

Eine Heuristik wird verwendet, um die ungefähre Entfernung vom aktuellen Knoten zum Zielknoten zu berechnen. Da wir den Weg nicht wirklich kennen, ist diese Entfernungsberechnung immer eine Annäherung. Eine bessere Heuristik ergibt also immer einen besseren Weg. Abgesehen davon muss die beste Lösung nicht diejenige sein, die den besten Pfad liefert, da wir auch die Ressourcennutzung und die Leistung des Algorithmus berücksichtigen müssen, wenn alle Berechnungen in Echtzeit oder einmal pro Aktualisierung durchgeführt werden müssen Schleife.

Die einfachste und einfachste Heuristik ist die Manhattan-Heuristik oder Manhattan-Entfernung. In einem 2D-Gitter ist dies tatsächlich der Abstand zwischen dem Startknoten und dem Endknoten in Luftlinie oder die Anzahl der Blöcke, die wir laufen müssen.

Sechseckige Manhattan-Variante

Für unser sechseckiges Gitter müssen wir eine Variante für die Manhattan-Heuristik finden, um die Entfernung zu approximieren. Während wir auf den sechseckigen Kacheln gehen, besteht die Idee darin, die Anzahl der Kacheln zu ermitteln, über die wir gehen müssen, um das Ziel zu erreichen. Lassen Sie mich Ihnen zuerst die Lösung zeigen. Bewegen Sie die Maus über das interaktive Element unten, um zu sehen, wie weit die anderen Kacheln von der Kachel unter der Maus entfernt sind.

Im obigen Beispiel finden wir die Kachel unter der Maus und den Abstand aller anderen Kacheln davon. Die Logik besteht darin, zuerst die Differenz der i- und j-Axialkoordinaten beider Kacheln zu ermitteln, z. B. di und dj. Finden Sie die absoluten Werte dieser Unterschiede, absi und absj, da die Abstände immer positiv sind.

Wir bemerken, dass wenn sowohl di als auch dj positiv sind und wenn sowohl di als auch dj negativ sind, der Abstand absi + absj ist. Wenn di und dj von entgegengesetzten Zeichen sind, ist der Abstand der größere Wert zwischen absi und absj. Dies führt zu der heuristischen Berechnungsfunktion getHeuristic wie unten.

getHeuristic=function(i,j){
    j=(j-(Math.floor(i/2)));
    var di=i-this.originali;
    var dj=j-this.convertedj;
    var si=Math.sign(di);
    var sj=Math.sign(dj);
    var absi=di*si;
    var absj=dj*sj;
    if(si!=sj){
        this.heuristic= Math.max(absi,absj);
    }else{
        this.heuristic= (absi+absj);
    }
}

Eine Sache zu bemerken ist, dass wir nicht darüber nachdenken, ob der Weg wirklich begehbar ist oder nicht; Wir gehen einfach davon aus, dass es begehbar ist, und stellen den Entfernungswert ein.

Den sechseckigen Pfad finden

Fahren wir mit der Pfadfindung für unser hexagonales Gitter mit der neu gefundenen heuristischen Methode fort. Da wir die Rekursion verwenden, wird es einfacher zu verstehen sein, wenn wir die Kernlogik unseres Ansatzes aufschlüsseln. Jedes sechseckige Plättchen hat einen heuristischen Abstand und einen damit verbundenen Kostenwert.

Wir haben eine rekursive Funktion, z. B. findPath(tile), die eine sechseckige Kachel aufnimmt, die die aktuelle Kachel ist. Dies ist zunächst das Startplättchen.
Wenn die Kachel gleich der Endkachel ist, endet die Rekursion und wir haben den Pfad gefunden. Ansonsten fahren wir mit der Berechnung fort.
Wir finden alle begehbaren Nachbarn der Fliese. Wir werden alle Nachbarkacheln durchlaufen und weitere Logik auf jede von ihnen anwenden, sofern sie nicht closed sind.
Wenn ein Nachbar zuvor nicht besucht und nicht geschlossen wurde, ermitteln wir mithilfe unserer Heuristik den Abstand der Nachbarkachel zur Endkachel. Wir setzen die Kosten des Nachbarplättchens auf die cost des aktuellen Plättchens + 10. Wir setzen das Nachbarplättchen als besucht. Wir setzen die previous tile der Nachbarkachel als aktuelle Kachel. Wir tun dies auch für einen zuvor besuchten Nachbarn, wenn die Kosten der aktuellen Kachel + 10 geringer sind als die Kosten dieses Nachbarn.
Wir berechnen die Gesamtkosten als die Summe aus dem Kostenwert der Nachbarkachel und dem heuristischen Entfernungswert. Unter allen Nachbarn wählen wir den Nachbarn aus, der die niedrigsten Gesamtkosten ergibt, und rufen findPath auf dieser Nachbarkachel auf.
Wir setzen die aktuelle Kachel auf geschlossen, damit sie nicht mehr berücksichtigt wird.
In einigen Fällen finden wir keine Kachel, die die Bedingungen erfüllt, und schließen dann die aktuelle Kachel, öffnen die vorherige Kachel und wiederholen sie.

Es gibt eine offensichtliche Fehlerbedingung in der Logik, wenn mehr als eine Kachel die Bedingungen erfüllt. Ein besserer Algorithmus findet alle verschiedenen Pfade und wählt den mit der kürzesten Länge aus, aber das werden wir hier nicht tun. Überprüfen Sie die Pfadfindung in Aktion unten.

In diesem Beispiel berechne ich Nachbarn anders als im Tetris-Beispiel. Bei Verwendung von Axialkoordinaten haben die Nachbarkacheln Koordinaten, die um einen Wert von 1 höher oder niedriger sind.

function getNeighbors(i,j){
    //coordinates are in axial
    var tempArray=[];
    var axialPoint=new Phaser.Point(i,j);
    var neighbourPoint=new Phaser.Point();
    neighbourPoint.x=axialPoint.x-1;//tr
    neighbourPoint.y=axialPoint.y;
    populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
    neighbourPoint.x=axialPoint.x+1;//bl
    neighbourPoint.y=axialPoint.y;
    populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
    neighbourPoint.x=axialPoint.x;//l
    neighbourPoint.y=axialPoint.y-1;
    populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
    neighbourPoint.x=axialPoint.x;//r
    neighbourPoint.y=axialPoint.y+1;
    populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
    neighbourPoint.x=axialPoint.x-1;//tr
    neighbourPoint.y=axialPoint.y+1;
    populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
    neighbourPoint.x=axialPoint.x+1;//bl
    neighbourPoint.y=axialPoint.y-1;
    populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
    return tempArray;
}

Die rekursive Funktion findPath lautet wie folgt.

function findPath(tile){//passes in a hexTileNode
    if(Phaser.Point.equals(tile,endTile)){
        //success, destination reached
        console.log('success');
        //now paint the path.
        paintPath(tile);
    }else{//find all neighbors
        var neighbors=getNeighbors(tile.originali,tile.convertedj);
        var newPt=new Phaser.Point();
        var hexTile;
        var totalCost=0;
        var currentLowestCost=100000;
        var nextTile;
        
        //find heuristics & cost for all neighbors
        while(neighbors.length){
            newPt=neighbors.shift();
            hexTile=hexGrid.getByName("tile"+newPt.x+"_"+newPt.y);
            if(!hexTile.nodeClosed){//if node was not already calculated
                if((hexTile.nodeVisited && (tile.cost+10)<hexTile.cost) ||
                !hexTile.nodeVisited){//if node was already visited, compare cost
                    hexTile.getHeuristic(endTile.originali,endTile.originalj);
                    hexTile.cost=tile.cost+10;
                    hexTile.previousNode=tile;//point to previous node
                    hexTile.nodeVisited=true;
                    hexTile.showDifference();//display heuristic & cost
                }else continue;
                totalCost=hexTile.cost+hexTile.heuristic;
                if(totalCost<currentLowestCost){//select the next neighbour with lowest total cost
                    nextTile=hexTile;
                    currentLowestCost=totalCost;
                }
            }else{
                console.log('node closed');
            }
        }
        tile.nodeClosed=true;
        if(nextTile!==null){
            findPath(nextTile);//call algo on the new tile
            nextTileToCall=nextTile;
        }else{
            if(tile.previousNode!==null){
                //current tile is now closed, open previous tile and redo.
                tile.previousNode.cost-=10;
                tile.previousNode.nodeClosed=false;
                findPath(tile.previousNode);//call algo on the previous tile
                nextTileToCall=tile.previousNode;
            }else{
               //no path
               nextTileToCall=null; 
            }
        }
    }
}

Es kann weitere und mehrfache Lektüre erfordern, um richtig zu verstehen, was vor sich geht, aber glauben Sie mir, es ist die Mühe wert. Dies ist nur eine sehr einfache Lösung und könnte stark verbessert werden. Informationen zum Verschieben des Zeichens entlang des berechneten Pfads finden Sie im folgenden Tutorial in meinem isometrischen Pfad.

Das Markieren des Pfads erfolgt mit einer anderen einfachen rekursiven Funktion, paintPath(tile), die zuerst mit der Endkachel aufgerufen wird. Wir markieren nur den previousNode der Kachel, falls vorhanden.

function paintPath(tile){
    tile.markDirty();
    if(tile.previousNode!==null){
        paintPath(tile.previousNode);
    }
}

Abschluss

Mit Hilfe aller drei sechseckigen Tutorials, die ich geteilt habe, sollten Sie in der Lage sein, mit Ihrem nächsten fantastischen, auf sechseckigen Kacheln basierenden Spiel zu beginnen.

Bitte beachten Sie, dass es auch andere Ansätze gibt und dass Sie dort viel weiterlesen können, wenn Sie dazu bereit sind. Bitte lassen Sie mich durch die Kommentare wissen, wenn Sie weitere Informationen zu sechseckigen Spielen auf Kachelbasis benötigen.