javascript - 在六边形网格中找到最短路径

Question

我有一个用六边形填充的网格，我想计算从所有方向上从 pointA 到 pointB 的最短路径。

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

This这是我想要实现的目标。

这些方法负责计算网格上任意两点之间的路径:

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;
},

....

示例:

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

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

.如果您真的想使用其他系统，则在需要时来回转换。