hexyl = { const exports = {}; const pointToArray = (pt) => { return [pt.x, pt.y]; } class Hex { constructor(q, r, s) { this.q = q; this.r = r; this.s = s; this.cost = Object({f:2000, h:1000, g:1000, value:5000}); if (Math.round(q + r + s) !== 0) throw "q + r + s must be 0 ---- q=${q}, r=${r}, s=${s}"; } updateCost(start, end) { this.cost = Object({f:this.g + this.h, h:this.distance(end), g:this.distance(start), value:this.distance(end)*5}); } add(b) { return new Hex(this.q + b.q, this.r + b.r, this.s + b.s); } subtract(b) { return new Hex(this.q - b.q, this.r - b.r, this.s - b.s); } scale(k) { return new Hex(this.q * k, this.r * k, this.s * k); } rotateLeft() { return new Hex(-this.s, -this.q, -this.r); } rotateRight() { return new Hex(-this.r, -this.s, -this.q); } static direction(direction) { return Hex.directions[direction]; } neighbor(direction) { return this.add(Hex.direction(direction)); } diagonalNeighbor(direction) { return this.add(Hex.diagonals[direction]); } len() { return (Math.abs(this.q) + Math.abs(this.r) + Math.abs(this.s)) / 2; } distance(b) { return this.subtract(b).len(); } round() { var qi = Math.round(this.q); var ri = Math.round(this.r); var si = Math.round(this.s); var q_diff = Math.abs(qi - this.q); var r_diff = Math.abs(ri - this.r); var s_diff = Math.abs(si - this.s); if (q_diff > r_diff && q_diff > s_diff) { qi = -ri - si; } else if (r_diff > s_diff) { ri = -qi - si; } else { si = -qi - ri; } return new Hex(qi, ri, si); } lerp(b, t) { return new Hex( this.q * (1.0 - t) + b.q * t, this.r * (1.0 - t) + b.r * t, this.s * (1.0 - t) + b.s * t ); } linedraw(b) { var N = this.distance(b); var a_nudge = new Hex(this.q + 1e-06, this.r + 1e-06, this.s - 2e-06); var b_nudge = new Hex(b.q + 1e-06, b.r + 1e-06, b.s - 2e-06); var results = []; var step = 1.0 / Math.max(N, 1); for (var i = 0; i <= N; i++) { results.push(a_nudge.lerp(b_nudge, step * i).round()); } return results; } toString() { return 'q#' + d3.format('+')(this.q) + '; r#' + d3.format('+')(this.r) + '; s#' + d3.format('+')(this.s) } } Hex.prototype.equals = function (o) { return (this.q == o.q && this.r == o.r && this.s == o.s); }; Hex.directions = [ new Hex(1, 0, -1), new Hex(1, -1, 0), new Hex(0, -1, 1), new Hex(-1, 0, 1), new Hex(-1, 1, 0), new Hex(0, 1, -1) ]; Hex.diagonals = [ new Hex(2, -1, -1), new Hex(1, -2, 1), new Hex(-1, -1, 2), new Hex(-2, 1, 1), new Hex(-1, 2, -1), new Hex(1, 1, -2) ]; exports.parseStringToHex = (strhex) => { const [q, r, s] = strhex.split(";", 3).map(d => parseFloat(d.split("#")[1].replace('−','-'))); return new Hex(q,r,s); } Hex.prototype['operator=='] = (h) => { return this.q == h.q && this.r == h.r && this.s == h.s; } Hex.prototype['operator!='] = (h) => { return !(this == h); } exports.Hex = Hex; class OffsetCoord { constructor(col, row) { this.col = col; this.row = row; } static qoffsetFromCube(offset, h) { var col = h.q; var row = h.r + (h.q + offset * (h.q & 1)) / 2; if (offset !== OffsetCoord.EVEN && offset !== OffsetCoord.ODD) { throw "offset must be EVEN (+1) or ODD (-1)"; } return new OffsetCoord(col, row); } static qoffsetToCube(offset, h) { var q = h.col; var r = h.row - (h.col + offset * (h.col & 1)) / 2; var s = -q - r; if (offset !== OffsetCoord.EVEN && offset !== OffsetCoord.ODD) { throw "offset must be EVEN (+1) or ODD (-1)"; } return new Hex(q, r, s); } static roffsetFromCube(offset, h) { var col = h.q + (h.r + offset * (h.r & 1)) / 2; var row = h.r; if (offset !== OffsetCoord.EVEN && offset !== OffsetCoord.ODD) { throw "offset must be EVEN (+1) or ODD (-1)"; } return new OffsetCoord(col, row); } static roffsetToCube(offset, h) { var q = h.col - (h.row + offset * (h.row & 1)) / 2; var r = h.row; var s = -q - r; if (offset !== OffsetCoord.EVEN && offset !== OffsetCoord.ODD) { throw "offset must be EVEN (+1) or ODD (-1)"; } return new Hex(q, r, s); } } exports.OffsetCoord = OffsetCoord; OffsetCoord.EVEN = 1; OffsetCoord.ODD = -1; class DoubledCoord { constructor(col, row) { this.col = col; this.row = row; } static qdoubledFromCube(h) { var col = h.q; var row = 2 * h.r + h.q; return new DoubledCoord(col, row); } qdoubledToCube() { var q = this.col; var r = (this.row - this.col) / 2; var s = -q - r; return new Hex(q, r, s); } static rdoubledFromCube(h) { var col = 2 * h.q + h.r; var row = h.r; return new DoubledCoord(col, row); } rdoubledToCube() { var q = (this.col - this.row) / 2; var r = this.row; var s = -q - r; return new Hex(q, r, s); } } exports.DoubledCoord = DoubledCoord; class Orientation { constructor(f0, f1, f2, f3, b0, b1, b2, b3, start_angle) { this.f0 = f0; this.f1 = f1; this.f2 = f2; this.f3 = f3; this.b0 = b0; this.b1 = b1; this.b2 = b2; this.b3 = b3; this.start_angle = start_angle; } } Orientation.pointy = new Orientation( Math.sqrt(3.0), Math.sqrt(3.0) / 2.0, 0.0, 3.0 / 2.0, Math.sqrt(3.0) / 3.0, -1.0 / 3.0, 0.0, 2.0 / 3.0, 0.5 ); Orientation.flat = new Orientation( 3.0 / 2.0, 0.0, Math.sqrt(3.0) / 2.0, Math.sqrt(3.0), 2.0 / 3.0, 0.0, -1.0 / 3.0, Math.sqrt(3.0) / 3.0, 0.0 ); Orientation.enum = [{value:Orientation.pointy, text:"pointy"}, {value:Orientation.flat, text:"flat"}] exports.Orientation = Orientation; // Conversions exports.permuteQRS = (q, r, s) => { return new Hex(q, r, s); }; exports.permuteSRQ = (s, r, q) => { return new Hex(q, r, s); }; exports.permuteSQR = (s, q, r) => { return new Hex(q, r, s); }; exports.permuteRQS = (r, q, s) => { return new Hex(q, r, s); }; exports.permuteRSQ = (r, s, q) => { return new Hex(q, r, s); }; exports.permuteQSR = (q, s, r) => { return new Hex(q, r, s); }; // Grid class HexGrid { constructor(config = {}) { //row, col, size, orientation, margin = {x:0, y:0} let { row = 6, col = 6, size = 16, orientation = Orientation.flat, margin = {x:50, y:50} } = config; this.r_max = config.size; this.r_min = config.size * Math.sqrt(3) / 2; this.row = config.row; this.col = config.col; this.orientation = config.orientation; this.margin = config.margin; this.parity = orientation == Orientation.flat ? (((col-col%2)/2)%2 == 1 ? OffsetCoord.ODD : OffsetCoord.EVEN) : (((row-row%2)/2)%2 == 1 ? OffsetCoord.ODD : OffsetCoord.EVEN); if (orientation === Orientation.flat) { this.width = ((this.col-(this.col%2))/2) * 3 * this.r_max + (this.col%2==0?1/2:2) * this.r_max; this.height = (2*this.row + 1)*this.r_min; this.origin = { x: (this.width / 2) + this.margin.x + (this.col%2 == 0 ? 3/4 : 0)*this.r_max, y: (this.height / 2) + this.margin.y + (this.row%2 == 0 ? -0.5 : 0.5)*this.r_min } var hexes = []; var i1 = -Math.floor(row/2), i2 = i1 + row; var j1 = -Math.floor(col/2), j2 = j1 + col; for (var j = j1; j < j2; j++) { var jOffset = -Math.floor(j/2); for (var i = i1 + jOffset; i < i2 + jOffset; i++) { hexes.push(new Hex(j, -i-j, i)); } } this.hexes = hexes; } else { this.width = (2*this.col + 1)*this.r_min; this.height = ((this.row-(this.row%2))/2) * 3 * this.r_max + (this.row%2==0?1/2:2) * this.r_max; this.origin = { x: (this.width / 2) + this.margin.x + (this.col%2 == 0 ? -0.5 : 0.5)*this.r_min, y: (this.height / 2) + this.margin.y + (this.row%2 == 0 ? 3/4 : 0)*this.r_max } var hexes = []; var i1 = -Math.floor(col/2), i2 = i1 + col; var j1 = -Math.floor(row/2), j2 = j1 + row; for (var j = j1; j < j2; j++) { var jOffset = -Math.floor(j/2); for (var i = i1 + jOffset; i < i2 + jOffset; i++) { hexes.push(new Hex(-i-j, j, i)); } } this.hexes = hexes; } } trueHexDistance(hex1, hex2) { var v1 = this.hexToPixel(hex1); var v2 = this.hexToPixel(hex2); return Math.sqrt((v2.x-v1.x)**2+(v2.y-v1.y)**2) } hexToPixel(hex) { var x = this.origin.x + (this.orientation.f0 * hex.q + this.orientation.f1 * hex.r) * this.r_max; var y = this.origin.y + (this.orientation.f2 * hex.q + this.orientation.f3 * hex.r) * this.r_max; return { x: x, y: y}; } hexToPixelArray(hex) { var pix = this.hexToPixel(hex); return [pix.x, pix.y]; } pixelToHex(pix) { if (this.origin.x == pix.x && this.origin.y == pix.y) {return this.origin;} var pt = {x:(pix.x - this.origin.x) / this.r_max, y:(pix.y - this.origin.y) / this.r_max}; var q = this.orientation.b0 * pt.x + this.orientation.b1 * pt.y; var r = this.orientation.b2 * pt.x + this.orientation.b3 * pt.y; return new Hex(q, r, -q - r); } arrayPixelToHex(arr) { var pix = { x: arr[0], y: arr[1]}; return this.pixelToHex(pix); } hexCornerOffset(corner) { var angle = (2.0 * Math.PI * (this.orientation.start_angle - corner)) / 6.0; return {x:this.r_max * Math.cos(angle), y:this.r_max * Math.sin(angle)}; } polygonCorners(hex) { var corners = []; var center = this.hexToPixel(hex); for (var i = 0; i < 6; i++) { var offset = this.hexCornerOffset(i); corners.push({x:center.x + offset.x, y:center.y + offset.y}); } return corners; } labelSVG(layer, color) { this.hexes.forEach(hex => { var lbl = this.hexLabelData(hex, color); layer.append("g") .selectAll(".hexlbl") .data(lbl) .enter().append('text') .attr("class", "hexlbl") .attr('x', d => d.x) .attr('y', d => d.y) .attr("font-family", "sans-serif") .attr("font-size", "10px") .attr('text-anchor', 'middle') .attr('fill', d => d.color) .text(d => d.txt); }) } hexLabelData(hex, color="black") { if (color.constructor !== Array) { color = [color, color, color]; } var center = this.hexToPixel(hex); return [ { x: (center.x /2) + (this.polygonCorners(hex)[1].x + this.polygonCorners(hex)[2].x) / 4, y: 4 + (center.y / 2) + (this.polygonCorners(hex)[1].y + this.polygonCorners(hex)[2].y) / 4, txt: hex.len() === 0 ? "0" : hex.q, color:color[0] }, { x: (center.x /2) + (this.polygonCorners(hex)[5].x + this.polygonCorners(hex)[0].x) / 4, y: 4 + (center.y / 2) + (this.polygonCorners(hex)[5].y + this.polygonCorners(hex)[0].y) / 4, txt: hex.len() === 0 ? "0" : hex.r, color:color[1] }, { x: (center.x /2) + (this.polygonCorners(hex)[3].x + this.polygonCorners(hex)[4].x) / 4, y: 4 + (center.y / 2) + (this.polygonCorners(hex)[3].y + this.polygonCorners(hex)[4].y) / 4, txt: hex.len() === 0 ? "0" : hex.s, color:color[2] } ]; } labelCanvas(ctx, color) { this.hexes.forEach(hex => { this.hexLabelData(hex, color).map(l => { ctx.save(); ctx.beginPath(); ctx.font = "10px sans-serif"; ctx.fillStyle = l.color; ctx.fillText(l.txt, l.x - 4, l.y); ctx.closePath(); ctx.restore(); }) }) } pathHex(hex, path) { if (!path) { path = d3.path();} var corners = this.polygonCorners(hex); path.moveTo(corners[5].x, corners[5].y); for (var i = 0; i < 6; i++) { path.lineTo(corners[i].x, corners[i].y); } return path; } path() { const path = d3.path(); this.hexes.forEach(hex => { this.pathHex(hex, path) }); return path; } hexRing(center, radius) { let results = []; if( radius === 0) { results.push(center); } else { const dir4 = Hex.direction(4); // South-West let hex = center.add( dir4.scale(radius)); for( let i = 0; i < 6; i++) { for( let j = 0; j < radius; j++) { results.push(hex); hex = hex.neighbor(i); } } } return results.filter(hex => this.hexes.some(h=>h.equals(hex))); } pathfinding(origin, target, barriers) { var openHexes = []; // initialization this.hexes.map(hex => { hex.cost.f = 0; hex.cost.g = 0; hex.cost.h = 0; hex.dist = 0; hex.visited = false; hex.closed = false; hex.parent = null; }); openHexes.push(origin); // main loop while(openHexes.length > 0) { // Sort array by f_cost, and by h_cost for hexes with equal f_cost and grab the lowest hex to process next var current = openHexes.sort((a, b) => (a.cost.f == b.cost.f ? (a.cost.h == b.cost.h ? a.dist - b.dist : a.cost.h - b.cost.h) : a.cost.f - b.cost.f))[0]; // Check if finished if (current.equals(target)) { // End case -- result has been found, return the traced path var path_hex = current; var ret = []; while(path_hex.parent) { ret.push(path_hex); path_hex = path_hex.parent; } return ret.reverse(); } // Normal case -- move current from open to closed, process each of its neighbors openHexes = openHexes.filter((hex) => {return !(hex.equals(current));}); current.closed = true; var neighbors = this.hexRing(current, 1).filter(hex => barriers.every(b => (!b.equals(hex)))); // Open more hexes for (var neighbor of neighbors) { if (neighbor.closed) { continue; } // g score is the shortest distance from start to current node, we need to check if // the path we have arrived at this neighbor is the shortest one we have seen yet var gScore = current.g_cost + 1; // 1 is the distance from a node to it's neighbor var gScoreIsBest = false; if(!neighbor.visited) { // This the the first time we have arrived at this node, it must be the best // Also, we need to take the h (heuristic) score since we haven't done so yet gScoreIsBest = true; neighbor.dist = this.trueHexDistance(neighbor, target); neighbor.cost.h = neighbor.distance(target)*5; neighbor.visited = true; openHexes.push(neighbor); } else if(gScore < neighbor.g_cost) { // We have already seen the node, but last time it had a worse g (distance from start) gScoreIsBest = true; } if(gScoreIsBest) { // Found an optimal (so far) path to this node. Store info on how we got here and just how good it really is. //// neighbor.parent = current; neighbor.cost.g = gScore; neighbor.cost.f = neighbor.cost.g + neighbor.cost.h; } } } // No result was found -- empty array signifies failure to find path //mutable spy = 'No result was found -- empty array signifies failure to find path' return []; } getHexHullArea(nodes) { const hexes = []; if (nodes.length==0) { return []; } if (nodes.length==1) { return nodes.map(loc => this.getHexAtXY(loc)); } if (nodes.length==2) { let n0 = this.getHexAtXY(nodes[0]); let n1 = this.getHexAtXY(nodes[1]); return n0.linedraw(n1); } if (nodes.length>2) { //const points = nodes.map(hex => pointToArray(this.hexToPixel(hex))); //const hull = d3.polygonHull(points); const hull = d3.polygonHull(nodes); this.hexes.map(hex => { if (d3.polygonContains(hull, pointToArray(this.hexToPixel(hex)))) { hexes.push(hex); } }); return hexes; } } getHexPolygonArea(nodes) { const hexes = []; if (nodes.length==0) { return []; } if (nodes.length==1) { //return nodes; return nodes.map(loc => this.getHexAtXY(loc)); } if (nodes.length==2) { //return nodes[0].linedraw(nodes[1]); let n0 = this.getHexAtXY(nodes[0]); let n1 = this.getHexAtXY(nodes[1]); return n0.linedraw(n1) } if (nodes.length>2) { //const points = nodes.map(hex => pointToArray(this.hexToPixel(hex))); this.hexes.map(hex => { //if (d3.polygonContains(points, pointToArray(this.hexToPixel(hex)))) { if (d3.polygonContains(nodes, pointToArray(this.hexToPixel(hex)))) { hexes.push(hex); } }); return hexes; } } getHexAtXY(loc) { let res = null; this.hexes.map(hex => { if (d3.polygonContains(this.polygonCorners(hex).map(h=>pointToArray(h)), loc)) { res = hex; } }); return res; } } exports.HexGrid = HexGrid; return exports; }