我有一个填充六边形的网格，我想计算从所有方向的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>这是一个已经解决的问题，有很多文献可以支持它。我所知道的最好的资源是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
。如果你真的想使用其他系统，那么在需要时转换为。