在矩形网格上制作和连接六边形

Question

我正在创建一个寻路应用程序，我想将每个六边形 (H) 连接到它的相邻六边形。网格是一个矩形，但填充有六边形。问题是现在连接这些六边形的代码冗长且极其挑剔。我想要实现的一个例子是：

问题是一个六边形与其相邻六边形（范围从 2-6 取决于它们在网格中的位置）之间的连接无法正常工作。我现在使用的将六边形与 6 个邻居连接起来的代码示例是：

        currentState.graph().addEdge(i, i + 1, 1);
        currentState.graph().addEdge(i, i - HexBoard.rows + 1, 1);
        currentState.graph().addEdge(i, i - HexBoard.rows, 1);
        currentState.graph().addEdge(i, i + HexBoard.rows +1, 1);
        currentState.graph().addEdge(i, i + HexBoard.rows , 1);

图本质上是网格，addEdge按顺序添加从src ->dest到cost(c)的连接。是否有任何算法或方法可以减少我的代码的体积？（现在它被 if-else 子句污染了）？启发我的网站：https://clementmihailescu.github.io/Pathfinding-Visualizer/#

编辑：问题不在于绘制六边形（它们已经是 SVG），而在于为它们分配边和连接。

Answer 1

有趣的问题...为了打下坚实的基础，这里有一个六边形网格class，它既不冗长也不挑剔，基于线性数组的简单数据结构。一些注意事项...

HexagonGrid 构造函数接受六边形网格尺寸，即六边形宽数 (hexWidth) 乘以六边形高数 (hexHeight)。
hexHeight 每隔一列由一个额外的六边形交替出现，以获得更令人愉悦的外观。因此，hexWidth 的奇数以第一列和最后一列中相同数量的六边形作为六边形网格的书尾。
length 属性表示网格中六边形的总数。
每个六边形都由从 0..length.
hexagonIndex 方法采用 (x,y) 坐标 returns 和基于最近六边形近似值的线性索引。因此，当靠近六边形的边缘时，返回的索引可能是一个近邻。
我对 class 结构并不完全满意，但足以展示线性索引六边形网格中涉及的关键算法。

为了帮助可视化线性索引方案，代码片段在六边形中显示了线性索引值。这种索引方案提供了具有相同长度的平行数组的机会，该数组通过索引表示每个特定六边形的特征。

还举例说明了从鼠标坐标转换为六边形索引的能力，通过单击任何六边形，这将重新绘制具有更粗边框的六边形。

const canvas = document.getElementById( 'canvas' );
const ctx = canvas.getContext( '2d' );

class HexagonGrid {

  constructor( hexWidth, hexHeight, edgeLength ) {
    this.hexWidth = hexWidth;
    this.hexHeight = hexHeight;
    this.edgeLength = edgeLength;
    
    this.cellWidthPair = this.hexHeight * 2 + 1;
    this.length = this.cellWidthPair * ( hexWidth / 2 |0 ) + hexHeight * ( hexWidth % 2 );
    
    this.dx = edgeLength * Math.sin( Math.PI / 6 );
    this.dy = edgeLength * Math.cos( Math.PI / 6 );
  }
  
  centerOfHexagon( i ) {
    let xPairNo = i % this.cellWidthPair;
    return {
      x: this.dx + this.edgeLength / 2 + ( i / this.cellWidthPair |0 ) * ( this.dx + this.edgeLength ) * 2 + ( this.hexHeight <= i % this.cellWidthPair ) * ( this.dx + this.edgeLength ),
      y: xPairNo < this.hexHeight ?  ( xPairNo + 1 ) * this.dy * 2 : this.dy + ( xPairNo - this.hexHeight ) * this.dy * 2
    };
  }
  
  hexagonIndex( point ) {
    let col = ( point.x - this.dx / 2 ) / ( this.dx + this.edgeLength ) |0;
    let row = ( point.y - ( col % 2 === 0 ) * this.dy ) / ( this.dy * 2 ) |0;
    let hexIndex = ( col / 2 |0 ) * this.cellWidthPair + ( col % 2 ) * this.hexHeight + row;
    //console.log( `(${point.x},${point.y}):  col=${col}  row=${row}  hexIndex=${hexIndex}` );
    return ( 0 <= hexIndex && hexIndex < this.length ? hexIndex : null );
  }
  
  edge( i ) {
    let topCheck = i % ( this.hexHeight + 0.5 );
    return (
      i < this.hexHeight
      || ( i + 1 ) % ( this.hexHeight + 0.5 ) === this.hexHeight
      || i % ( this.hexHeight + 0.5 ) === this.hexHeight
      || ( i + 1 ) % ( this.hexHeight + 0.5 ) === 0
      || i % ( this.hexHeight + 0.5 ) === 0
      || this.length - this.hexHeight < i
     );
  }
  
  drawHexagon( ctx, center, lineWidth ) {
    let halfEdge = this.edgeLength / 2;
    
    ctx.lineWidth = lineWidth || 1;
    
    ctx.beginPath();
    ctx.moveTo( center.x - halfEdge, center.y - this.dy );
    ctx.lineTo( center.x + halfEdge, center.y - this.dy );
    ctx.lineTo( center.x + halfEdge + this.dx, center.y );
    ctx.lineTo( center.x + halfEdge, center.y + this.dy );
    ctx.lineTo( center.x - halfEdge, center.y + this.dy );
    ctx.lineTo( center.x - halfEdge - this.dx, center.y );
    ctx.lineTo( center.x - halfEdge, center.y - this.dy );
    ctx.stroke();
  }
  
  drawGrid( ctx, topLeft ) {
    ctx.font = '10px Arial';
    for ( let i = 0; i < this.length; i++ ) {
      let center = this.centerOfHexagon( i );
      this.drawHexagon( ctx, { x: topLeft.x + center.x, y: topLeft.y + center.y } );

      ctx.fillStyle = this.edge( i ) ? 'red' : 'black';
      ctx.fillText( i, topLeft.x + center.x - 5, topLeft.y + center.y + 5 );
    }
  }
  
}

let myHexGrid = new HexagonGrid( 11, 5, 20 );
let gridLeftTop = { x: 20, y: 20 };
myHexGrid.drawGrid( ctx, gridLeftTop );

canvas.addEventListener( 'mousedown', function( event ) {
  let i = myHexGrid.hexagonIndex( { x: event.offsetX - gridLeftTop.x, y: event.offsetY - gridLeftTop.y } );
  if ( i !== null ) {
    let center = myHexGrid.centerOfHexagon( i );
    myHexGrid.drawHexagon( ctx, { x: gridLeftTop.x + center.x, y: gridLeftTop.y + center.y }, 3 );
  }
} );

<canvas id=canvas width=1000 height=1000 />

线性索引的一大好处是它使路径搜索更容易，因为每个 interior 六边形都被相对索引为 -1、-6、-5 的六边形包围, +1, +6, +5。例如，将相对索引应用于六边形 18 会导致周围的六边形列表为 17、12、13、19、24、23。

作为奖励，edge 方法指示六边形是否在网格的边缘。（在代码片段中，边缘单元格由红色文本标识。）强烈建议边缘单元格不要成为路径的一部分（即，它们不可到达），因为这会简化任何路径搜索。否则路径逻辑变得非常复杂，就像现在在边缘单元格上一样，指示周围六边形的相对索引不再完全适用...

在矩形网格上制作和连接六边形

Making and connecting hexagons on a rectangle grid

javascript

math

geometry