I have a grid populated with hexagons and I would like to calculate the shortest possible path from pointA to pointB in all directions.
I'm using my modified version of HexagonTools.js. So far it only seems to be working when selecting two points on horizontal or vertical line. Any other direction doesn't work.
This is what I would like to achieve.
These methods are responsible for calculating the path between any two points on the grid:
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>