25:["$","title",null,{"children":"Hexagonal grid generation with relaxation | Степан Гребнев | Observable"}] 49:T27e6,class Hexagrid { constructor({sideSize, rng, searchIterationCount}){ this.sideLength = Math.sin( 60 * Math.PI / 180 ); this.sideSize = sideSize; this.rng = rng || Math.random; this.searchIterationCount = searchIterationCount; this.points = []; this.triangles = []; this.baseQuads = []; this.quads = []; this.neighbours = []; this.init(); } init(){ this.initPoints(); this.initTriangles(); this.adjacentTrianglesToQuads(); const middles = this.quadsBreakdown(); this.handleRemainingTriangles(middles); this.computeNeighbours(); } initPoints(){ const maxHeight = this.sideSize * 2 - 1; const maxDeltaHeight = this.sideSize - maxHeight * 0.5; const ratio = maxHeight / 2 - maxDeltaHeight; for (let x = 0; x < this.sideSize * 2 - 1; x++) { const height = (x < this.sideSize) ? this.sideSize + x : this.sideSize * 3 - 2 - x; const deltaHeight = this.sideSize - height * 0.5; for (let y = 0; y < height; y++) { const isSide = (x === 0) || x === (this.sideSize * 2 - 2) || (y === 0) || (y === height - 1); const p = new Point({ x:(x - this.sideSize + 1) * this.sideLength / ratio, y:(y + deltaHeight - maxHeight / 2) / ratio, side:isSide }) this.points.push(p); } } } initTriangles(){ let offset = 0; for (let x = 0; x < (this.sideSize * 2 - 2); x++) { let height = (x < this.sideSize) ? (this.sideSize + x) : (this.sideSize * 3 - 2 - x); if (x < this.sideSize - 1) { // left side for (let y = 0; y < height; y++) { const t = new Triangle({ A:offset + y, B:offset + y + height, C:offset + y + height + 1, valid : true }) this.triangles.push(t); if (y >= height - 1) break; const t2 = new Triangle({ A:offset + y + height + 1, B:offset + y + 1, C:offset + y, valid : true }); this.triangles.push(t2); } } else { // right side for (let y = 0; y < height - 1; y++) { const t = new Triangle({ A:offset + y, B:offset + y + height, C:offset + y + 1, valid : true }); this.triangles.push(t); if (y >= height - 2) break; const t2 = new Triangle({ A:offset + y + 1, B:offset + y + height, C:offset + y + height + 1, valid : true }); this.triangles.push(t2); } } offset += height; } } adjacentTrianglesToQuads(){ let triIndex = 0; const adjacents = []; while(true) { let searchCount = 0; do{ triIndex = this.rng() * this.triangles.length | 0; searchCount++; } while(searchCount < this.searchIterationCount && !this.triangles[triIndex].valid); if (searchCount === this.searchIterationCount) break; adjacents.length = 0; let adjacentCount = this.getAdjacentTriangles(triIndex, adjacents); if (adjacentCount > 0) { const triangle0 = this.triangles[triIndex]; const triangle1 = this.triangles[adjacents[0]]; let indices = [ triangle0.A, triangle0.B, triangle0.C, triangle1.A, triangle1.B, triangle1.C ].sort((a, b) => a - b); const quadIndices = new Array(4); let quadIndexCount = 1; quadIndices[0] = indices[0]; for (let i = 1; i < 6; i++) { if (indices[i] !== indices[i - 1]) { quadIndices[quadIndexCount++] = indices[i]; } } if(quadIndexCount !== 4) throw Error('Hexagrid.adjacentTrianglesToQuads : quadIndexCount !== 4') const q = new Quad({ A: quadIndices[0], B: quadIndices[2], C: quadIndices[3], D: quadIndices[1] }); this.baseQuads.push(q); triangle0.valid = false; triangle1.valid = false; } } } quadsBreakdown(){ const middles = {}; for (let i = 0; i < this.baseQuads.length; i++) { const quad = this.baseQuads[i]; const indexCenter = this.points.length; const point0 = this.points[quad.A]; const point1 = this.points[quad.B]; const point2 = this.points[quad.C]; const point3 = this.points[quad.D]; const p = new Point({ x: (point0.x + point1.x + point2.x + point3.x) / 4.0, y: (point0.y + point1.y + point2.y + point3.y) / 4.0, side: false }); this.points.push(p); this.subdivide(4, quad.getVerticesArray(), middles, indexCenter); } return middles; } handleRemainingTriangles(middles){ for (let i = 0; i < this.triangles.length; i++) { const triangle = this.triangles[i]; if (triangle.valid) { const indexCenter = this.points.length; const point0 = this.points[triangle.A]; const point1 = this.points[triangle.B]; const point2 = this.points[triangle.C]; const p = new Point({ x: (point0.x + point1.x + point2.x) / 3.0, y: (point0.y + point1.y + point2.y) / 3.0, side: false }); this.points.push(p); this.subdivide(3, triangle.getVerticesArray(), middles, indexCenter); } } } computeNeighbours(){ this.neighbours.length = this.points.length; for (let i = 0; i < this.neighbours.length; i++) { this.neighbours[i] = new Neighbours({}); } for (let i = 0; i < this.quads.length; i++) { const quad = this.quads[i]; for (let j = 0; j < 4; j++) { const index1 = quad.getVertex(j); const index2 = quad.getVertex((j + 1) & 3); let neighbour = this.neighbours[index1]; let good = true; for (let k = 0; k < neighbour.neighbours.length; k++) { if(neighbour.neighbours[k] === index2) { good = false; break; } } if (good) { if(neighbour.neighbours.length >= 6) throw Error('Hexagrid.computeNeighbours : neighbour.length >= 6') neighbour.neighbours.push(index2); } neighbour = this.neighbours[index2]; good = true; for (let k = 0; k < neighbour.neighbours.length; k++) { if(neighbour.neighbours[k] === index1) { good = false; break; } } if (good) { if(neighbour.neighbours.length >= 6) throw Error('Hexagrid.computeNeighbours : neighbour.length >= 6') neighbour.neighbours.push(index1); } } } } relax() { for (let i = 0; i < this.points.length; i++) { if (this.points[i].side) continue; const neighbour = this.neighbours[i]; let sumX = 0; let sumY = 0; for (let j = 0; j < neighbour.neighbours.length; j++) { sumX += this.points[neighbour.neighbours[j]].x; sumY += this.points[neighbour.neighbours[j]].y; } this.points[i].x = sumX / neighbour.neighbours.length; this.points[i].y = sumY / neighbour.neighbours.length; } } relaxWeighted() { for (let i = 0; i < this.points.length; i++) { if (this.points[i].side) continue; const neighbour = this.neighbours[i]; let sumX = 0; let sumY = 0; let weight = 0; for (let j = 0; j < neighbour.neighbours.length; j++) { let w = Math.sqrt( Math.pow(this.points[i].x - this.points[neighbour.neighbours[j]].x, 2) + Math.pow(this.points[i].y - this.points[neighbour.neighbours[j]].y, 2) ); sumX += this.points[neighbour.neighbours[j]].x * w; sumY += this.points[neighbour.neighbours[j]].y * w; weight += w; } this.points[i].x = sumX / weight; this.points[i].y = sumY / weight; } } relaxSide() { const radius = 1; for (let i = 0; i < this.points.length; i++) { if (!this.points[i].side) continue; const dx = this.points[i].x; const dy = this.points[i].y; const distance = radius - Math.sqrt(dx * dx + dy * dy); this.points[i].x += (dx * distance) * 0.1; this.points[i].y += (dy * distance) * 0.1; } } subdivide(count, indices, middles, indexCenter) { const halfSegmentIndex = new Array(count); for (let j = 0; j < count; j++) { const indexA = indices[j]; const indexB = indices[(j + 1) % count]; const pointA = this.points[indexA]; const pointB = this.points[indexB]; const key = `${Math.min(indexA, indexB)} -> ${Math.max(indexA, indexB)}`; if (!middles.hasOwnProperty(key)) { halfSegmentIndex[j] = this.points.length; const isSide = pointA.side && pointB.side; const p = new Point({ x: (pointA.x + pointB.x) / 2.0, y:(pointA.y + pointB.y) / 2.0, side:isSide }) this.points.push(p); middles[key] = halfSegmentIndex[j]; } else halfSegmentIndex[j] = middles[key]; } for (let j = 0; j < count; j++) { const nextIndex = (j + 1) % count; const q = new Quad({ A: indexCenter, B: halfSegmentIndex[j], C: indices[nextIndex], D: halfSegmentIndex[nextIndex] }); this.quads.push(q); } } getAdjacentTriangles(triIndex, adjacents) { const triangle = this.triangles[triIndex]; for (let i = 0; i < this.triangles.length; i++) { const ntriangle = this.triangles[i]; if (i === triIndex || !ntriangle.valid) continue; let shareCount = 0; for(let j = 0; j < 3; j++) { for (let k = 0; k < 3; k++) { if (triangle.getVertex(j) === ntriangle.getVertex(k)) { shareCount ++; break; } } } if(shareCount >= 3) throw Error('Hexagrid.getAdjacentTriangles : shareCount >= 3'); if (shareCount === 2) { adjacents.push(i); if(adjacents.length >= 4) throw Error('Hexagrid.getAdjacentTriangles : adjacents.length >= 4'); } } return adjacents.length; } }4a:T50b,function drawGridSectors(context, resizedPoints){ context.strokeStyle = 'rgba(245, 75, 125, 0.75)'; context.fillStyle = 'rgba(245, 75, 125, 0.2)'; context.lineWidth = 1; context.beginPath(); for (let i = 0; i < grid.baseQuads.length; i++) { const quad = grid.baseQuads[i]; const point0 = resizedPoints[quad.A]; const point1 = resizedPoints[quad.B]; const point2 = resizedPoints[quad.C]; const point3 = resizedPoints[quad.D]; context.moveTo(point0.x, point0.y); context.lineTo(point1.x, point1.y); context.lineTo(point2.x, point2.y); context.lineTo(point3.x, point3.y); context.closePath(); } context.fill(); context.stroke(); context.strokeStyle = 'rgba(80, 180, 240, 0.75)'; context.fillStyle = 'rgba(80, 180, 240, 0.2)'; context.lineWidth = 1; context.beginPath(); for (let i = 0; i < grid.triangles.length; i++) { const triangle = grid.triangles[i]; if (!triangle.valid) continue; const point0 = resizedPoints[triangle.A]; const point1 = resizedPoints[triangle.B]; const point2 = resizedPoints[triangle.C]; context.moveTo(point0.x, point0.y); context.lineTo(point1.x, point1.y); context.lineTo(point2.x, point2.y); context.closePath(); } context.fill(); context.stroke(); }4b:[] 29:{"id":"4c11ecdeb0b54f16","slug":null,"title":"Hexagonal grid generation with relaxation","thumbnail":"c72bcd7ab535a501a73dd9f2423d2d1531682c5646eae542945475bd4caf0f51","access_level":"public","create_time":"$D2023-07-24T23:20:19.420Z","update_time":"$D2023-07-24T23:20:19.420Z","view_time":null,"first_public_time":"$D2023-07-24T23:20:19.420Z","has_unpublished_edits":null,"fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"a77e3d98d736999b","login":"76ca7f05a63c88cb","name":"Степан Гребнев","avatar_url":"https://avatars-next.observableusercontent.com/d182fd2954f237a9992945306347e2ceb86da632484e40adc07e0d5099572e7a","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":617,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"76ca7f05a63c88cb","login":"76ca7f05a63c88cb","name":"Степан Гребнев","avatar_url":"https://avatars-next.observableusercontent.com/d182fd2954f237a9992945306347e2ceb86da632484e40adc07e0d5099572e7a","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"76ca7f05a63c88cb","login":"76ca7f05a63c88cb","name":"Степан Гребнев","avatar_url":"https://avatars-next.observableusercontent.com/d182fd2954f237a9992945306347e2ceb86da632484e40adc07e0d5099572e7a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Hexagonal grid generation with relaxation","cells":[{"id":0,"value":"md`# Hexagonal grid generation with relaxation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":491,"value":"md`\nPort of [Cedric Guillemet](https://github.com/CedricGuillemet/HexagridRelaxing)'s C++ implementation of [Oskar Stålberg](https://twitter.com/osksta)'s hexagonal grid generation. It's used in the game [Townscaper](https://store.steampowered.com/app/1291340/Townscaper/), which I'm very fond of.\n\nI used a class based approach, which is not super practical in JavaScript IMO. You can also check [Kevin Chapelier](https://github.com/kchapelier/hexagrid-relaxing)'s JS port, which seems to use arrays instead of classes. I used the same weighted relaxation approach, which I found to give cleaner results in circle shape (relaxed sides).\n` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"canvas = {\n const canvas = DOM.canvas(width, width/2);\n const ctx = canvas.getContext(\"2d\");\n ctx.translate(canvas.width/2, canvas.height/2);\n \n const n = config.sideSize * config.searchIterationCount;\n for(let i=0; i new Point({x: p.x*minWH/2, y: p.y*minWH/2, side: p.side}));\n for (let i = 0; i < resizedPoints.length; i++) {\n const point = resizedPoints[i];\n const neighbour = grid.neighbours[i];\n\n for (let k = 0; k < neighbour.neighbours.length; k++) {\n const npoint = resizedPoints[neighbour.neighbours[k]];\n\n context.moveTo(point.x, point.y);\n context.lineTo(npoint.x, npoint.y);\n }\n }\n context.stroke();\n\n if (drawSectors) drawGridSectors(context, resizedPoints)\n\n if (drawPositions) drawGridPositions(context, resizedPoints)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":480,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":486,"value":"function drawGridPositions(context, resizedPoints, pointSize = .75){\n for (let i = 0; i < resizedPoints.length; i++) {\n const point = resizedPoints[i];\n \n context.fillStyle = point.side ? 'red' : 'black';\n context.beginPath();\n context.arc(point.x, point.y, pointSize, 0, 6.3);\n context.fill();\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"Math.seed = function(s) {\n return function() {\n s = Math.sin(s) * 10000; \n return s - Math.floor(s);\n };\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"relax = relaxationView === 'Relax';","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":225,"value":"relaxSides = options === 'Relax sides';","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"relaxWeighted = relaxationView.includes('Relax weighted');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"drawSectors = drawingOptions.includes('Draw sectors')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":243,"value":"drawPositions = drawingOptions.includes('Draw positions')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"import {checkbox, radio, slider, button} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 24:null