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

Question

我正在创建一个路径搜索应用程序，我希望将每个hexgon(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添加了一个连接。有没有任何算法或方法使我的代码不那么笨重？(现在它被if-否则条款污染了)？激励我的网站:https://clementmihailescu.github.io/Pathfinding-Visualizer/#

编辑:问题不在于绘制六边形(它们已经是SVG)，而是分配它们的边和连接。

Answer 1

有趣的问题..。为了奠定坚实的基础，这里有一个六边形网格类，它既不长也不挑剔，基于一个简单的线列阵数据结构。一些笔记..。

(hexHeight).

• The构造函数
• ，HexagonGrid构造函数接受六边形的网格尺寸，即六边形的宽度(hexWidth)，由六边形的数量表示，高的HexagonGrid hexHeight每一列都有一个额外的六边形，以获得更令人愉悦的外观。因此，在第一列和最后一列中，以相同的六边形数表示六边形网格的奇数。0..length.
• The hexWidth属性
• 表示网格中的六边形总数。
• 每个六边形都由hexWidth hexagonIndex方法中的一个线性索引引用，该方法采用(x，y)坐标，根据最接近的六边形的近似返回线性索引。因此，当接近六边形边缘时，返回的索引可能是近邻。
• 对类结构不完全满意，但足以显示线性索引六边形网格所涉及的关键算法。

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

另外一个例子是，通过单击任何六边形，可以将鼠标坐标转换为六边形索引，这将用更厚的边框重新绘制六边形。

​

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 />

​

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

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