29:null 2a:["$","title",null,{"children":"Pointy/Flat-topped hexagonal 2D grid for canvas or svg | linard-y | Observable"}] 30:T6d7,{ const margin = config.margin; const grid = new hexyl.HexGrid(config); const svg = d3 .create('svg') .attr("width", grid.width+100) .attr("height", grid.height+100) .attr("viewBox", `0 0 ${grid.width+100} ${grid.height+100}`); svg.append('rect') .attr("height", grid.height) .attr("width", grid.width) .style("fill", mapColor(1)) .style("stroke", mapColor(5)) .style("stroke-width", '6px') .attr('transform','translate(' + margin.x + ',' + margin.y + ')'); svg.append("line") .attr("x1", margin.x) .attr("y1", margin.y + grid.height/2) .attr("x2", margin.x + grid.width) .attr("y2", margin.y + grid.height/2) .style("stroke-dasharray", ("3, 3")) .style("stroke-width", '2px') .style("stroke", mapColor(5)); svg.append("line") .attr("x1", margin.x + grid.width/2) .attr("y1", margin.y) .attr("x2", margin.x + grid.width/2) .attr("y2", margin.y + grid.height) .style("stroke-dasharray", ("3, 3")) .style("stroke-width", '1px') .style("stroke", mapColor(5)); const pathgrid = svg.append('path').attr('d', grid.path()); pathgrid.attr('fill', mapColor(2)); pathgrid.attr('fill-opacity', '0.6'); pathgrid.attr('stroke-width', '3'); pathgrid.attr('stroke', mapColor(3)); const pathgring = svg.append('g'); const ringR3 = grid.hexRing( new hexyl.Hex(0,0,0), 3); ringR3.forEach( hex => { pathgring.append('path').attr('d', grid.pathHex(hex)); pathgring.attr('fill', mapColor(7)); pathgring.attr('fill-opacity', '0.4'); pathgring.attr('stroke-width', '3'); pathgring.attr('stroke', mapColor(8)); }); if (showLabels) { grid.labelSVG(svg.append('g'), [mapColor(17), mapColor(6), mapColor(11)]); } yield svg.node(); }31:T856,{ const grid = new hexyl.HexGrid(config); const path = new Path2D(grid.path()); const context = DOM.context2d(grid.width+100, grid.height+100); context.clearRect(0,0, grid.width+100, grid.height+100); context.save(); context.beginPath(); context.rect(config.margin.x, config.margin.y, grid.width, grid.height); context.fillStyle = mapColor(1); context.strokeStyle = mapColor(5); context.lineWidth = 6; context.fill(); context.stroke(); context.closePath(); context.beginPath(); context.moveTo(config.margin.x, config.margin.y + grid.height/2); context.lineTo(config.margin.x + grid.width, config.margin.y + grid.height/2); context.lineWidth = 1; context.setLineDash([5, 5]); context.strokeStyle = mapColor(5); context.stroke(); context.closePath(); context.beginPath(); context.moveTo(config.margin.x + grid.width/2, config.margin.y); context.lineTo(config.margin.x + grid.width/2, config.margin.y + grid.height); context.lineWidth = 1; context.setLineDash([5, 5]); context.strokeStyle = mapColor(5); context.stroke(); context.closePath(); context.restore(); context.save(); context.beginPath(); context.globalAlpha = 0.6; context.fillStyle = mapColor(2); context.fill(path); context.closePath(); context.restore(); context.save(); context.beginPath(); context.strokeStyle = mapColor(3); context.lineWidth = 3; context.stroke(path); context.closePath(); context.restore(); const ringR3 = grid.hexRing( new hexyl.Hex(0,0,0), 3); ringR3.forEach( hex => { context.save(); context.beginPath(); context.globalAlpha = 0.4; context.fillStyle = mapColor(7); context.fill(new Path2D(grid.pathHex(hex))); context.closePath(); context.restore(); context.save(); context.beginPath(); context.strokeStyle = mapColor(8); context.lineWidth = 3; context.stroke(new Path2D(grid.pathHex(hex))); context.closePath(); context.restore(); }); if (showLabels) { grid.labelCanvas(context, [mapColor(17), mapColor(6), mapColor(11)]); } return context.canvas }32:Tb28,{ const svg = d3.select(DOM.svg(grid.width+100, grid.height+100)); const spyHex = (event, d) => { mutable spy1 = md` cube q::${d.q}, r::${d.r}, s::${d.s} offset row::${(hexyl.OffsetCoord.qoffsetFromCube(grid.parity, d)).row} , col::${(hexyl.OffsetCoord.qoffsetFromCube(grid.parity, d)).col} pixel x::${(grid.hexToPixel(d)).x}, y::${(grid.hexToPixel(d)).y}` ; } const pointToArray = (pt) => { return [pt.x, pt.y];} const selectHex = (event, d) => { const selectedPoint = nodes.slice(); selectedPoint.push(d); mutable nodes = selectedPoint; } svg.append('rect') .attr("height", grid.height) .attr("width", grid.width) .style("fill", mapColor(1)) .style("stroke", mapColor(5)) .style("stroke-width", '6px') .attr('transform','translate(' + grid.margin.x + ',' + grid.margin.y + ')'); // grid const pathgrid = svg.append('g').attr('id', 'grid') .selectAll(".hexgrid") .data(grid.hexes) .enter().append('path') .attr('class', 'hexgrid') .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(2)) .attr('fill-opacity', '0.6') .attr('stroke-width', '3') .attr('stroke', mapColor(3)) .on("mouseover", spyHex) .on("click", selectHex); const patharea = svg.append("g").attr('id', 'hull') .selectAll(".hexarea") .data(area=='HULL'?grid.getHexHullArea(nodes.map(hex => pointToArray(grid.hexToPixel(hex)))):grid.getHexPolygonArea(nodes.map(hex => pointToArray(grid.hexToPixel(hex))))) .enter().append('path') .attr("class", "hexarea") .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(12)) .attr('fill-opacity', '0.9') .attr('stroke-width', '3') .attr('stroke', mapColor(16)) .on("mouseover", spyHex) .on("click", selectHex); const pathnodes = svg.append("g").attr('id', 'nodes') .selectAll(".hexnode") .data(nodes) .enter().append('path') .attr("class", "hexnode") .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(17)) .attr('fill-opacity', '0.9') .attr('stroke-width', '3') .attr('stroke', mapColor(16)) .on("mouseover", spyHex); if (nodes.length>1) { const points = nodes.map(hex => pointToArray(grid.hexToPixel(hex))); points.push(points[0]); const hull = d3.polygonHull(points); hull.push(hull[0]); const zone = area=='HULL'?hull:points; svg.append("g").append("path").datum({ type: "LineString", coordinates: zone }).attr("d", d3.geoPath()) .attr('fill', 'none') .attr('stroke-width', '3') .attr('stroke', mapColor(17)) .attr('stroke-dasharray', '0.8, 9.2') .attr('stroke-linecap', 'round') .attr('stroke-dashoffset', '-1.2'); } yield svg.node(); }33:Td45,{ const svg = d3.select(DOM.svg(grid.width+100, grid.height+100)); const spyHex = (event, d) => { mutable spy2 = md` cube q::${d.q}, r::${d.r}, s::${d.s} offset row::${(hexyl.OffsetCoord.qoffsetFromCube(grid.parity, d)).row} , col::${(hexyl.OffsetCoord.qoffsetFromCube(grid.parity, d)).col} pixel x::${(grid.hexToPixel(d)).x}, y::${(grid.hexToPixel(d)).y}` ; } const updateHex = (event, d) => { switch (tool) { case 'TARGET': mutable target = d; mutable log = "new target::" + d.toString(); break; case 'WALL': const walls = barriers.map(d => new hexyl.Hex(d.q, d.r, d.s)); if (walls.every(w => (!w.equals(d)))) { walls.push(d); mutable barriers = walls; mutable log = "add wall::" + d.toString(); } else { mutable barriers = walls.filter(w => (!d.equals(w))); mutable log = "remove wall::" + d.toString(); } break; default: // 'ORIGIN' mutable origin = d; mutable log = "new origin::" + d.toString(); } } svg.append('rect') .attr("height", grid.height) .attr("width", grid.width) .style("fill", mapColor(1)) .style("stroke", mapColor(5)) .style("stroke-width", '6px') .attr('transform','translate(' + grid.margin.x + ',' + grid.margin.y + ')'); // grid const pathgrid = svg.selectAll(".hexgrid") .data(grid.hexes) .enter().append('g') .attr('class', 'hexgrid') .attr('id', 'grid') .append('path') .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(2)) .attr('fill-opacity', '0.6') .attr('stroke-width', '3') .attr('stroke', mapColor(3)) .on("mouseover", spyHex) .on("click", updateHex); // walls const pathwalls = svg.append('g').attr('id', 'walls') .selectAll(".wall") .data(barriers) .enter().append('path') .attr("class", "wall") .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(5)) .attr('fill-opacity', '1.0') .attr('stroke-width', '3') .attr('stroke', mapColor(5)) .on("mouseover", spyHex) .on("click", updateHex); // pathfinding results const pathfound_layer = svg.selectAll(".hexpath") .data(grid.pathfinding(origin, target, barriers)) .enter().append('g') .attr("class", "hexpath") .attr('id', 'hexpath') .append('path') .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(7)) .attr('fill-opacity', '0.4') .attr('stroke-width', '3') .attr('stroke', mapColor(8)) .on("mouseover", spyHex) .on("click", updateHex); // origin svg.append('g').append('path') .attr('d', grid.pathHex(origin)) .attr('fill', mapColor(12)) .attr('fill-opacity', '0.9') .attr('stroke-width', '3') .attr('stroke', mapColor(11)) .on("mouseover", spyHex); // target const target_layer = svg.append("g").attr('id', 'target') .selectAll(".target") .data([target]) .enter().append('path') .attr("class", "target") .attr('d', d => grid.pathHex(d)) .attr('fill', mapColor(12)) .attr('fill-opacity', '0.9') .attr('stroke-width', '3') .attr('stroke', mapColor(16)) .on("mouseover", spyHex); yield svg.node(); }34:T4741,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; }35:[] 2d:{"id":"2953a5e61fe73021","slug":"hexyl","title":"Pointy/Flat-topped hexagonal 2D grid for canvas or svg","thumbnail":"f91f28b08867418b3162e1b48f5d45d640ad0ed5001cf6b0853e60ae57290150","access_level":"public","create_time":"$D2022-05-04T13:09:21.299Z","update_time":"$D2025-05-09T17:49:56.381Z","view_time":null,"first_public_time":"$D2022-05-16T18:52:06.977Z","fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"9784867a3e59436b","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":"starter_2024"},"version":2655,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null}],"members":[{"type":"individual","id":"c6e84137b8a39d94","login":"linard-y","name":"","avatar_url":"https://avatars-next.observableusercontent.com/0ce44546efae24745b35d9327acbc99a3f3fdaeac3595375f92848f133b06ded","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Pointy/Flat-topped hexagonal 2D grid for canvas or svg","cells":[{"id":0,"value":"# Pointy/Flat-topped hexagonal 2D grid for canvas or svg","pinned":false,"hidden":false,"mode":"md"},{"id":1261,"value":"...inspired by Amit Patel's hex grid library at https://www.redblobgames.com/grids/hexagons/implementation.html.","pinned":false,"hidden":false,"mode":"md"},{"id":488,"value":"viewof marginx = Inputs.range([0, 100], {value: 50, step: 1, label: \"Left margin\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":496,"value":"viewof marginy = Inputs.range([0, 100], {value: 50, step: 1, label: \"Top margin\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":503,"value":"viewof r = Inputs.range([6, 24], {value: 24, step: 1, label: \"Radius\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":515,"value":"viewof row = Inputs.range([2, 60], {value: 8, step: 1, label: \"Rows\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":518,"value":"viewof col = Inputs.range([2, 120], {value: 12, step: 1, label: \"Columns\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1121,"value":"viewof orientation = Inputs.radio(hexyl.Orientation.enum, {value: hexyl.Orientation.enum.find(t => t.text === \"flat\"), label: \"Orientation\", format:d => d.text})","pinned":false,"hidden":false,"mode":"ojs"},{"id":848,"value":"config = Object({row:row, col:col, size:r, orientation:orientation.value, margin:{x:marginx, y:marginy}})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1994,"value":"viewof showLabels = Inputs.toggle({label: \"Show labels\", value: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1299,"value":"### Rendering with SVG","pinned":false,"hidden":false,"mode":"md"},{"id":1083,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":1303,"value":"### Rendering with Canvas","pinned":false,"hidden":false,"mode":"md"},{"id":1279,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":2395,"value":"## Some tests","pinned":false,"hidden":false,"mode":"md"},{"id":1578,"value":"grid = new hexyl.HexGrid({row: 44, col: 78, size: 6, orientation: hexyl.Orientation.flat, margin: {x: 20, y: 20}});","pinned":false,"hidden":false,"mode":"ojs"},{"id":2350,"value":"### Test coordinates change...","pinned":false,"hidden":false,"mode":"md"},{"id":2405,"value":"With hexagonal grid, we can choose multiple coordinate systems. hexyl is first build around cube coordinates but offset or interlaced/doubled coordinates are also convenient and the library has several conversion methods betwwen these systems.\nThe cube system allows us to add, subtract, multiply, and divide with hex coordinates. The offset coordinate systems do not allow this, and that's part of what makes algorithms simpler with cube coordinates.","pinned":false,"hidden":false,"mode":"md"},{"id":2367,"value":"Let's find the offset coordinates of the hex (q=-1, r=-3, s= 4)","pinned":false,"hidden":false,"mode":"md"},{"id":2355,"value":"hexyl.OffsetCoord.qoffsetFromCube(grid.parity, new hexyl.Hex(-1, -3, 4))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2417,"value":"Let's find the doubled coordinates of the hex (q=-1, r=-3, s= 4)","pinned":false,"hidden":false,"mode":"md"},{"id":2411,"value":"hexyl.DoubledCoord.qdoubledFromCube(new hexyl.Hex(-1, -3, 4))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2451,"value":"### Test area selection...","pinned":false,"hidden":false,"mode":"md"},{"id":2458,"value":"mutable nodes = []","pinned":false,"hidden":false,"mode":"ojs"},{"id":2504,"value":"mutable spy1 = null","pinned":false,"hidden":false,"mode":"ojs"},{"id":2587,"value":"viewof reset = Inputs.button(\"Reset\", {label: \"Click in grid to define area...\", value: null, reduce: () => {mutable nodes=[];}})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2604,"value":"viewof area = Inputs.radio(['POLYGON', 'HULL'], {label: html`Area definition...`, value:'POLYGON'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2461,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":2019,"value":"### Test pafhfinding...","pinned":false,"hidden":false,"mode":"md"},{"id":1593,"value":"mutable barriers = [new hexyl.Hex(2, 1, -3), new hexyl.Hex(1, 2, -3), new hexyl.Hex(3, 0, -3), new hexyl.Hex(-1, 3, -2), new hexyl.Hex(0, 3, -3), new hexyl.Hex(-2, 2, 0), new hexyl.Hex(-3, 2, 1), new hexyl.Hex(-3, 1, 2), new hexyl.Hex(-1, -1, 2), new hexyl.Hex(-2, 0, 2), new hexyl.Hex(0, -2, 2), new hexyl.Hex(1, -2, 1), new hexyl.Hex(2, -2, 0), new hexyl.Hex(2, -1, -1), new hexyl.Hex(3, -1, -2)]","pinned":false,"hidden":false,"mode":"ojs"},{"id":2172,"value":"viewof tool = Inputs.radio(new Map([['change origin', 'ORIGIN'], ['change target', 'TARGET'], ['add/remove wall', 'WALL']]), {label: html`By clicking...`, value:'ORIGIN'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2304,"value":"md`active tool:: ${tool}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2060,"value":"mutable spy2 = null","pinned":false,"hidden":false,"mode":"ojs"},{"id":1657,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":2112,"value":"mutable log = ''","pinned":false,"hidden":false,"mode":"ojs"},{"id":1587,"value":"mutable origin = new hexyl.Hex(0,0,0)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1590,"value":"mutable target = new hexyl.Hex(5, 1, -6)","pinned":false,"hidden":false,"mode":"ojs"},{"id":904,"value":"md`## Hex Grid Library`","pinned":false,"hidden":false,"mode":"ojs"},{"id":905,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":656,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":588,"value":"mapColor = d3\n .scaleThreshold()\n .domain([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17])\n .range(\"ffff-e6deb2-dec367-ecb45b-ed8238-e07a5f-d9636c-ab90a4-85aab1-6a8782-869e80-80B266-aad09d-b5ddbf-9ac1ae-aea9a4-947f67-000000\".split(\"-\").map((d) => `#${d}`))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2653,"value":"mapColor(9)","pinned":true,"hidden":false,"mode":"ojs"},{"id":770,"value":"PickHex = (selection, callback) => {\n selection\n .on(\"pointerdown\", (e) => trackPointer(e, {\n start: (p) => {\n callback(p.point);\n }\n }));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":773,"value":"import {trackPointer} from '@fil/pointer-events'","pinned":false,"hidden":false,"mode":"ojs"},{"id":268,"value":"d3 = require(\n 'd3@6',\n 'd3-hexbin',\n 'd3-hexgrid'\n)","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}} 2e:"$2d:body"