在一个六边形网格中寻找最短路径。

Question

我有一个填满六边形的网格，我想计算出所有方向上从点A到点B的最短路径。

我正在使用我修改过的HexagonTools.js版本。目前它只在选择水平或垂直线上的两个点时有效。其他任何方向都不起作用。

这里是我想要实现的效果。

以下方法负责计算网格上任意两点之间的路径：

hex_round: function(h){
    var q = Math.trunc(Math.round(h.q));
    var r = Math.trunc(Math.round(h.r));
    var s = Math.trunc(Math.round(h.s));

    var q_diff = Math.abs(q - h.q);
    var r_diff = Math.abs(r - h.r);
    var s_diff = Math.abs(s - h.s);

    if (q_diff > r_diff && q_diff > s_diff){
        q = -r - s;
    }else if (r_diff > s_diff){
        r = -q - s;
    }else{
        s = -q - r;
    }

    return {q:q, r:r, s:s};
},
getHexDistance: function(a, b){
    var deltaX = a.pathCoordX - b.pathCoordX,
    deltaY = a.pathCoordY - b.pathCoordY;
    return ((Math.abs(deltaX) + Math.abs(deltaY) + Math.abs(deltaX - deltaY)) / 2);
},
hex_lerp: function(a, b, t){
    return { 
        q : (a.pathCoordX + (b.pathCoordX - a.pathCoordX) * t ) ,  
        r: (a.pathCoordY + (b.pathCoordY - a.pathCoordY) * t ), 
        s: (a.size.s + (b.size.s - a.size.s) * t)
    }
},
getHexDistance: function(a, b){
    var deltaX = a.pathCoordX - b.pathCoordX,
    deltaY = a.pathCoordY - b.pathCoordY;
    return ((Math.abs(deltaX) + Math.abs(deltaY) + Math.abs(deltaX - deltaY)) / 2);
},
calculatePath: function( h1, h2 ){/* (hexagon, hexagon)*/
    var N = this.getHexDistance(h1, h2)
    var results = [];
    var step = 1.0 / Math.max(N, 1);
    for( var i = 0; i <= N; i++ ){
        results.push( this.hex_round( this.hex_lerp(h1, h2, step * i) ) );
    }

    return results;
},

....

Example:

/////// [ Point.js ] /////////////////////////////////////////
////////////////////////////////////////////////////////////////
function Point(x, y){
 this.x = x;
 this.y = y;
}

/////// [ Hexagon.js ] /////////////////////////////////////////
////////////////////////////////////////////////////////////////

function Hexagon(id, x, y, def){
 this.Points = [];
 
 this.id = id;
 
 this.pos = {
  x: x,
  y: y
 };
 
 this.size = def.size;
 
 this.generate_points();
 
 this.TopLeftPoint = new Point(this.pos.x, this.pos.y);
 this.BottomRightPoint = new Point(this.pos.x + this.size.w, this.pos.y + this.size.h);
 this.MidPoint = new Point(this.pos.x + (this.size.w / 2), this.pos.y + (this.size.h / 2));
 
 this.selected_src = false;
 this.selected_dest = false;
 this.selected_path = false;
}

Hexagon.prototype = {
 constructor: Hexagon,
 generate_points: function(){
  var x1 = (this.size.w - this.size.s)/2;
  var y1 =  (this.size.h / 2);
  this.Points.push( new Point( x1 + this.pos.x, this.pos.y ) );
  this.Points.push( new Point( x1 + this.size.s + this.pos.x, this.pos.y ) );
  this.Points.push( new Point( this.size.w + this.pos.x, y1 + this.pos.y ) );
  this.Points.push( new Point( x1 + this.size.s + this.pos.x, this.size.h + this.pos.y ) );
  this.Points.push( new Point( x1 + this.pos.x, this.size.h + this.pos.y ) );
  this.Points.push( new Point( this.pos.x, y1 + this.pos.y ) );
 },
 
 draw: function(ctx){
  ctx.lineWidth = 1;
  if( this.selected_src ){
   ctx.strokeStyle = "yellow";
   ctx.fillStyle = "blue"
  }else if( this.selected_dest ){
   ctx.strokeStyle = "red";
   ctx.fillStyle = "green"
  }else if( this.selected_path ){
   ctx.strokeStyle = "red";
   ctx.fillStyle = "orange"
  }else{
   ctx.strokeStyle = "grey";
  }
  
  ctx.beginPath();
  ctx.moveTo(this.Points[0].x, this.Points[0].y);
  for(var i = 1; i < this.Points.length; i++){
   var p = this.Points[i];
   ctx.lineTo(p.x, p.y);
  }
  ctx.closePath();
  ctx.stroke();
  
  if(this.selected_src || this.selected_dest || this.selected_path ){
   ctx.fill();
  }
  
  if(this.id)
  {
   //draw text for debugging
   ctx.fillStyle = "black"
   //ctx.font = "bolder 7pt Trebuchet MS,Tahoma,Verdana,Arial,sans-serif";
   ctx.font="bolder 10px Georgia";
   ctx.textAlign = "center";
   ctx.textBaseline = 'middle';
   ctx.fillText(this.id, this.MidPoint.x, this.MidPoint.y - 5);
  }
  
  if(this.pathCoordX !== null && this.pathCoordY !== null && typeof(this.pathCoordX) != "undefined" && typeof(this.pathCoordY) != "undefined")
  {
   //draw co-ordinates for debugging
   //ctx.font = "bolder 8pt Trebuchet MS,Tahoma,Verdana,Arial,sans-serif";
   ctx.font="10px Georgia";
   ctx.textAlign = "center";
   ctx.textBaseline = 'middle';
   //var textWidth = ctx.measureText(this.Planet.BoundingHex.Id);
   ctx.fillText("("+this.pathCoordX+","+this.pathCoordY+")", this.MidPoint.x, this.MidPoint.y + 5);
  }
 },
 
 /**
  * Returns true if the x,y coordinates are inside this hexagon
  * @this {HT.Hexagon}
  * @return {boolean}
  */
 isInBounds: function(x,y){
  return this.contains(new HT.Point(x, y));
 },
 
 /**
  * Returns true if the point is inside this hexagon, it is a quick contains
  * @this {HT.Hexagon}
  * @param {HT.Point} p the test point
  * @return {boolean}
  */
 isInHexBounds : function( p ){  /*Point*/
  if(this.TopLeftPoint.x < p.x && this.TopLeftPoint.y < p.y && p.x < this.BottomRightPoint.x && p.y < this.BottomRightPoint.y){
   return true;
  }
  return false;
 },
 
 /**
  * Returns true if the point is inside this hexagon, it first uses the quick isInHexBounds contains, then check the boundaries
  * @this {HT.Hexagon}
  * @param {HT.Point} p the test point
  * @return {boolean}
  */
 contains: function( p ) { /*Point*/
  var isIn = false;
  if (this.isInHexBounds(p))
  {
   var i, j = 0;
   for (i = 0, j = this.Points.length - 1; i < this.Points.length; j = i++){
    var iP = this.Points[i];
    var jP = this.Points[j];
    if (
     ( ((iP.y <= p.y) && (p.y < jP.y)) || ((jP.y <= p.y) && (p.y < iP.y))) && (p.x < (jP.x - iP.x) * (p.y - iP.y) / (jP.y - iP.y) + iP.x)
    ){
     isIn = !isIn;
    }
   }
  }
  return isIn;
 },
 
 select_dest: function(){
  if( ! this.selected_dest ){
   this.selected_dest = true;
  }else{
   this.selected_dest = false;
  }
 },
 
 select_src: function(){
  if( ! this.selected_src ){
   this.selected_src = true;
  }else{
   this.selected_src = false;
  }
 },
 
 select_path: function(){
  if( ! this.selected_path ){
   this.selected_path = true;
  }
 },
 
 unselect: function(){
  this.selected_src = false;
  this.selected_dest = false;
  this.selected_path = false;
 },
 
 distanceFromMidPoint : function( p ){ /*Point*/
  var deltaX = this.MidPoint.x - p.x;
  var deltaY = this.MidPoint.y - p.y;
  return Math.sqrt( (deltaX * deltaX) + (deltaY * deltaY) );
 }
}

/////// [ Grid.js ] ////////////////////////////////////////////
////////////////////////////////////////////////////////////////
function Grid(width, height, hex_r, ctx, ctx_rect){
 this.Hexes = [];
 
 var HexagonsByXOrYCoOrd = {};
 this.width = width;
 this.height = height;
 var row = 0;
 var col = 0;
 var x,y = 0.0;
 var offset = 0.0;
 var hexID = -1;
 var h = 0;
 
 this.ctx = ctx;
 this.ctx_rect = ctx_rect;
 
 this.hex_def = {
  size: {
   w: hex_r * 2,
   h: (Math.sqrt(3)/2) * (hex_r * 2),
   s: hex_r
  }
 };
 
 this.letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
 
 var pathCoord = 0;
 
 while( y + this.hex_def.size.w <= height ){
  col = 0;
  offset = 0.0;
  
  if( (row % 2) == 1){
   offset = ( ( this.hex_def.size.w - this.hex_def.size.s ) /2 ) + this.hex_def.size.s;
   col = 1;
  }
  
  x =  offset;
  
  while ( x + this.hex_def.size.w <= width ){
   hexID = this.getHexID(row, col);
   h = new Hexagon(hexID, x, y, this.hex_def);
   pathCoord = col;
   
   h.pathCoordX = col; 
   
   this.Hexes.push(h);
   
   if( ! HexagonsByXOrYCoOrd[pathCoord] ){
    HexagonsByXOrYCoOrd[pathCoord] = [];
   }
   HexagonsByXOrYCoOrd[pathCoord].push(h);
   
   col+= 2;
   x += this.hex_def.size.w + this.hex_def.size.s;

  }
  
  row++;
  y += this.hex_def.size.h / 2;

 }
  
 //finally go through our list of hexagons by their x co-ordinate to assign the y co-ordinate
 var hexagonsByXOrY = {};
 var coord2 = 0;
 
 for(var coord1 in HexagonsByXOrYCoOrd){
  hexagonsByXOrY  = HexagonsByXOrYCoOrd[coord1];
  coord2 = Math.floor( (coord1 /2 ) + (coord1 % 2) );
  for( var i = 0, size = hexagonsByXOrY.length; i < size; i++ ){
   hexagonsByXOrY[i].pathCoordY = coord2++//Hexagon
  }
 }

 this.enable_mouse_events();
 this.draw();
};


Grid.prototype = {
 constructor: Grid,
 getHexID: function( row, col ){
  var letterIndex = row;
  var letters = "";
  while(letterIndex > 25)
  {
   letters = this.letters[letterIndex%26] + letters;
   letterIndex -= 26;
  }
   
  return this.letters[letterIndex] + letters + (col + 1);
 },
 
 /**
  * Returns a hex at a given point
  * @this {HT.Grid}
  * @return {HT.Hexagon}
  */
 getHexAt: function(p){ /* Point */
  for ( var h = 0, hs_l = this.Hexes.length; h < hs_l; h++){
   if ( this.Hexes[h].contains( p ) ){
    return this.Hexes[h];
   }
  }
  return null;
 },
 
 hex_round: function(h){
  var q = Math.trunc(Math.round(h.q));
  var r = Math.trunc(Math.round(h.r));
  var s = Math.trunc(Math.round(h.s));
  
  var q_diff = Math.abs(q - h.q);
  var r_diff = Math.abs(r - h.r);
  var s_diff = Math.abs(s - h.s);
  
  if (q_diff > r_diff && q_diff > s_diff){
   q = -r - s;
  }else if (r_diff > s_diff){
   r = -q - s;
  }else{
   s = -q - r;
  }
  
  return {q:q, r:r, s:s};
 },
 
 getHexDistance: function(a, b){
  var deltaX = a.pathCoordX - b.pathCoordX,
  deltaY = a.pathCoordY - b.pathCoordY;
  return ((Math.abs(deltaX) + Math.abs(deltaY) + Math.abs(deltaX - deltaY)) / 2);
 },
 

 hex_lerp: function(a, b, t){
  return { 
   q : (a.pathCoordX + (b.pathCoordX - a.pathCoordX) * t ) ,  
   r: (a.pathCoordY + (b.pathCoordY - a.pathCoordY) * t ), 
   s: (a.size.s + (b.size.s - a.size.s) * t)
  }
 },
 
 /**
  * Returns a distance between two hexes
  * @this {HT.Grid}
  * @return {number}
  */
 calculatePath: function( h1, h2 ){/* (hexagon, hexagon)*/
  var N = this.getHexDistance(h1, h2)
  var results = [];
  var step = 1.0 / Math.max(N, 1);
  for( var i = 0; i <= N; i++ ){
   results.push( this.hex_round( this.hex_lerp(h1, h2, step * i) ) );
  }
  
  return results;
 },
 
 showPath: function( hex_coords ){
  for( var h_c = 0, h_c_l = hex_coords.length; h_c < h_c_l; h_c++ ){
   for ( var h = 0, hs_l = this.Hexes.length; h < hs_l; h++){
    if( this.Hexes[h].pathCoordX == hex_coords[h_c].q && this.Hexes[h].pathCoordY == hex_coords[h_c].r ){
     this.Hexes[h].select_path( );
     console.log( this.Hexes[h] )
    }
   }
  }
 },
 
 unselectAll: function(){
  for ( var h = 0, hs_l = this.Hexes.length; h < hs_l; h++){
    this.Hexes[h].unselect();
  }
 },
 
 /**
  * Returns hex with specified id
  * @this {HT.Grid}
  * @return {HT.Hexagon}
  */
 getHexById: function(id){
  for(var i in this.Hexes)
  {
   if(this.Hexes[i].Id == id)
   {
    return this.Hexes[i];
   }
  }
  return null;
 },
 
 /**
 * Returns the nearest hex to a given point
 * @this {HT.Grid}
 * @param {HT.Point} p the test point 
 * @return {HT.Hexagon}
 */
 getNearestHex: function(p){ /*Point*/
  var dist;
  var minDist = Number.MAX_VALUE;
  var hx = null;
  // iterate through each hex in the grid
  for(var h = 0, hs_l = this.Hexes.length; h < hs_l; h++){
   dist = this.Hexes[h].distanceFromMidPoint(p);
   
   if(dist < minDist){
    minDist = dist;
    hx = this.Hexes[h];
   }
  }
  
  return hx;
 },
 
 draw: function(){
  this.ctx.clearRect(0, 0, this.width, this.height);
  for(var h = 0, hs_l = this.Hexes.length; h < hs_l; h++){
   this.Hexes[h].draw( this.ctx );
  }
 },
 
 enable_mouse_events: function(){
  var self = this;
  var mouse_coor;
  var result = null;
  var source_hex = null;
  var dest_hex = null;
  
  window.addEventListener( 'mousemove', function(e){
   mouse_coor = new Point( (e.clientX - self.ctx_rect.left ), (e.clientY - self.ctx_rect.top ) ) ;
  });
  
  window.addEventListener( 'mousedown', function(e){
   if( mouse_coor !== "undefined" ){
    result = self.getHexAt( mouse_coor );
    if( result != null ){
     if( source_hex == null || dest_hex == null ){
      if( source_hex == null ){
       source_hex = result;
       source_hex.select_src( self.ctx );
      }else{
       dest_hex = result;
       dest_hex.select_dest( self.ctx );
       self.showPath( self.calculatePath( source_hex, dest_hex )  );
      }
     }else{
      //// reseting the hexes ///
      self.unselectAll();
      dest_hex = null;
      source_hex = result;
      source_hex.select_src( self.ctx );
     }
    }
   }
  });
  
  /*window.addEventListener( 'mouseup', function(e){

  });*/
 }
};

var c_el = document.getElementById("myCanvas");
var ctx = c_el.getContext("2d");
var a_grid = new Grid(c_el.clientWidth, c_el.clientHeight, 20, ctx ,  c_el.getBoundingClientRect() );


function draw_all(){
 window.requestAnimationFrame( draw_all );
 ctx.clearRect(0, 0, c_el.width, c_el.height);
 a_grid.draw();
}

draw_all();

<body  stye="width: 100%; height: 100%" >
<canvas width="500px" height="500px" id="myCanvas" style="margin:0; padding:0; border:1px solid #d3d3d3;"></canvas>
</body>

- Alexus

Answer 1

这是一个已解决的问题，有很多文献支持。我知道的最好的资源在Red Blob Games上：https://www.redblobgames.com/grids/hexagons/。

简而言之，最可能的原因是您选择了错误的坐标系。使用立方体坐标系，解决方案就很简单，只需要一行代码：

function cube_distance(a, b):
return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2

如果你真的想使用其他系统，那么需要时进行相互转换。

- david.pfx