javascript - A*Pathfinding en una rejilla hexagonal

html5 canvas

Question

¿Puede alguien indicarme un ejemplo simple que implemente un algoritmo de búsqueda de rutas A * en una cuadrícula hexagonal (en JS)? Lo hice funcionando en una cuadrícula cuadrada, sin embargo, todos mis intentos de hacerlo funcionar en una cuadrícula hexagonal han fracasado.

Así es como se ve mi cuadrícula:

Estoy usando la misma técnica para dibujar la cuadrícula y generar coordenadas como se ve en este topic .

Aquí están los datos de las colas de la cuadrícula junto con el inicio, el fin de las coords:

        [0, 0] , [0, 1],  [0, 2],
    [1, 0],  [1, 1],  [1, 2],  [1, 3],
 [2, 0],  [2, 1],  [2, 2],  [2, 3],  [2, 4],
    [3, 0],  [3, 1], [3, 2],  [3, 3], 
        [4, 0], [4, 1],  [4, 2]


start_point: [0,2]
end_point: [4.0]

Después de actualizar el cálculo de la distancia de manhattan a:

var dx = pos1[0] - pos0[0];
    var dy = pos1[1] - pos0[1];

    var dist;
    if ( Math.sign(dx) == Math.sign(dy) ){
        dist = Math.abs (dx + dy);
    }else{
        dist = Math.max(Math.abs(dx), Math.abs(dy))
    }

return dist;

Obtengo este resultado:

Y también la forma en que estoy calculando el camino más corto:

if (!Array.prototype.remove) {
    Array.prototype.remove = function(from, to) {
        var rest = this.slice((to || from) + 1 || this.length);
        this.length = from < 0 ? this.length + from : from;
        return this.push.apply(this, rest);
    };
}

var astar = {
    init: function(grid) {
        for(var x = 0; x < grid.length; x++) {
            for(var y = 0; y < grid[x].length; y++) {
                grid[x][y].f = 0;
                grid[x][y].g = 0;
                grid[x][y].h = 0;
    //grid[x][y].content = false;
                grid[x][y].visited = false;
                grid[x][y].closed = false;
                grid[x][y].debug = "";
                grid[x][y].parent = null;
    console.log([grid[x][y].coords[0],grid[x][y].coords[1]])
            }
        }
    },
    search: function(grid, start, end, heuristic) {
        this.init(grid);
        heuristic = heuristic || this.manhattan;

        var openList = [];
  
  //// find the start and end points in the grid ////
  start = grid[start.pos[0]][start.pos[1]];
  end =  grid[end.pos[0]][end.pos[1]];
  
  console.log( start, end )
  
        openList.push(start);
  
        while(openList.length > 0) {
   
            // Grab the lowest f(x) to process next
            var lowInd = 0;
            for(var i=0; i<openList.length; i++) {
                if(openList[i].f < openList[lowInd].f) { lowInd = i; }
            }
            var currentNode = openList[lowInd];

            // End case -- result has been found, return the traced path
            if( currentNode == end ) {
                var curr = currentNode;
                var ret = [];
                while(curr.parent) {
                    ret.push(curr);
                    curr = curr.parent;
                }
                return ret.reverse();
            }

            // Normal case -- move currentNode from open to closed, process each of its neighbors
            openList.remove( lowInd );
            currentNode.closed = true;

            var neighbors = this.neighbors(grid, currentNode);
            for(var i=0; i<neighbors.length;i++) {
                var neighbor = neighbors[i];

                if( neighbor.closed || neighbor.content == 2 ) { // not a valid node to process, skip to next neighbor
                    continue;
                }

                // g score is the shortest distance from start to current node, we need to check if
                //   the path we have arrived at this neighbor is the shortest one we have seen yet
                var gScore = currentNode.g + 1; // 1 is the distance from a node to it''s neighbor
                var gScoreIsBest = false;

                if(!neighbor.visited) {
                    // This the the first time we have arrived at this node, it must be the best
                    // Also, we need to take the h (heuristic) score since we haven''t done so yet
                    gScoreIsBest = true;
                    neighbor.h = heuristic(neighbor.coords, end.coords);
                    neighbor.visited = true;
                    openList.push(neighbor);
                }
                else if(gScore < neighbor.g) {
                    // We have already seen the node, but last time it had a worse g (distance from start)
                    gScoreIsBest = true;
                }

                if(gScoreIsBest) {
                    // Found an optimal (so far) path to this node.  Store info on how we got here and just how good it really is. ////
                    neighbor.parent = currentNode;
                    neighbor.g = gScore;
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.debug = "F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h;
                }
            }
        }

        // No result was found -- empty array signifies failure to find path
        return [];
    },
    manhattan: function(pos0, pos1) { //// heuristics : use manhattan distances  ////
        var dx = pos1[0] - pos0[0];
        var dy = pos1[1] - pos0[1];
  
        return  Math.abs (dx + dy);
    },
    neighbors: function(grid, node) {
        var ret = [];
        var x = node.coords[0];
        var y = node.coords[1];
  
        if(grid[x-1] && grid[x-1][y] ) {
            ret.push(grid[x-1][y]);
        }
        if( grid[x+1] && grid[x+1][y] ) {
            ret.push(grid[x+1][y]);
        }
        if( grid[x][y-1] && grid[x][y-1] ) {
            ret.push(grid[x][y-1]);
        }
        if( grid[x][y+1] && grid[x][y+1] ) {
            ret.push(grid[x][y+1]);
        }
        return ret;
    }
};

Intenté buscar algunos buenos ejemplos o documentos en Internet, pero no pude encontrar nada útil.

Answer 1

Como ya lo mencionó alguien aquí, la forma en que estaba generando la cuadrícula, y también las coordenadas eran incorrectas.

He leído otra vez la guide implementación de Amit Patel y utilicé su forma de generar la cuadrícula y también el sistema de coordenadas, incluida la coordenada. conversiones

generate: function(){
        var n_hex = null; 
        var row = 0, col = 0;
        for (var q = -this.grid_r; q <= this.grid_r; q++) {
            var r1 = Math.max(-this.grid_r, -q - this.grid_r);
            var r2 = Math.min(this.grid_r, -q + this.grid_r);
            col = q + this.grid_r;
            this.hexes[ col ] = [];
            for (var r = r1; r <= r2; r++) {
                row = r - r1;
                n_hex = new Hex( [q, r], [col, row], this.layout );
                this.hexes[ col ][ row ] = n_hex;
            }
        }
    },

Cuando comencé a usar las coordenadas del cubo, lo único que tuve que cambiar en el algoritmo de búsqueda de rutas a * fue el cálculo de la distancia:

return Math.max(Math.abs(a.x - b.x), Math.abs(a.y - b.y), Math.abs(a.z - b.z))

ahora la búsqueda de caminos está trabajando en diseños "puntiagudos" y "planos":

Answer 2

El algoritmo de búsqueda de ruta "clásico" funciona de la siguiente manera:

• Inicializa todas las celdas con cero.
• Comience en el punto de inicio y marque este punto con el número 1.
• Comienzo de bucle con n = 1:
• Tome todas las celdas con el número n y marque todas las celdas adyacentes, que contienen un cero, con el número (n + 1). Si alguna de estas celdas adyacentes es la salida, deje el bucle. Si no se encuentra una celda adyacente con el número cero, no hay camino para salir.
• Incremento n y goto loop

Si se encuentra la salida entonces:

• Iniciar bucle en la salida:
• Busca la celda adyacente con el número n y recuerda esta celda.
• Decrementar n y goto loop

Todas las celdas recordadas construyen la ruta del resultado (en orden inverso).

Cheerz

Hennes

Answer 3

El problema reside en el método de tus neighbors : aunque un hexágono tiene seis vecinos (6), solo presionas cuatro (4) hacia la ret . La siguiente figura destaca el problema. El hex gris claro representa el nodo actual (es decir, el neighbor ). Los hexágonos verdes se agregan a ret , pero los hexágonos rojos no.

Para solucionar esto, agregue los siguientes dos (2) casos a su método de neighbors :

    if( grid[x+1][y-1] && grid[x+1][y-1] ) {
        ret.push(grid[x][y-1]);
    }
    if( grid[x-1][y+1] && grid[x-1][y+1] ) {
        ret.push(grid[x][y+1]);
    }

Con respecto a su método de manhattan actualizado: es correcto. La siguiente figura utiliza colores para mostrar la distancia desde el hexágono central actual (en [0: 0] en rojo) a cada otro hex. Por ejemplo, las fichas hexadecimales naranjas son un (1) movimiento del rojo. Los amarillos son dos (2) movimientos del rojo. Y así.

Puede observar el patrón: si las coordenadas x e y comparten el mismo signo, la distancia es igual a la magnitud de la coordenada más grande. De lo contrario, la distancia es la suma de sus valores absolutos. Esta es exactamente la forma en que calculaste la distancia en tu método de manhattan actualizado . Así que estás bien allí.

Con respecto a la búsqueda heurística en general: Esta es una forma sencilla de comprobar si una solución subóptima es el resultado de un error en la implementación heurística o de un error en la implementación del algoritmo. Simplemente use el valor heurístico cero (0) para todos los valores, es decir, use la heurística trivial. Si, mientras se usa la heurística trivial, el camino no es óptimo, entonces sabes que no es un problema heurístico, es un problema de algoritmo.

Answer 4

Este es un problema resuelto, con mucha literatura que lo respalda. El mejor recurso que conozco es en Red Blob Games: https://www.redblobgames.com/grids/hexagons/ .

En resumen, la razón más probable es que haya elegido el sistema de coordenadas incorrecto. El uso de un sistema de coordenadas de cubo que implementa el algoritmo A * es bastante simple. Vea la demostración en vivo en el enlace de arriba.

Si realmente desea utilizar algún otro sistema, conviértalo cuando sea necesario.