3f:null 40:["$","title",null,{"children":"2D Labyrinth | Claudio Esperança | Observable"}] 46:T4b7,{ let left = html`Turn left`; let right = html`Turn right`; let fwd = html`Walk ahead`; left.onclick = () => game.rotate('counter') right.onclick = () => game.rotate('clock') fwd.onclick = () => game.ahead() let resetSmall = html`Restart (small labyrinth)`; let resetLarge = html`RESTART (large labyrinth)`; resetSmall.onclick = () => { mutable labSize = [4,6] mutable cellSize = 80 } resetLarge.onclick = () => { mutable labSize = [15,20] mutable cellSize = 40 } return html`

${left} ${fwd} ${right}

${resetSmall} ${resetLarge} ` }47:T5a8,// Creates a labyrinth composed of rows x cols cells makeLabyrinth = function (rows,cols) { let lab = []; let [imax,jmax] = [rows,cols].map(n=>2*n+1) // Fill the labyrinth for (let i = 0; i < imax; i++) { lab.push([]) for (let j = 0; j < jmax; j++) { lab[i][j] = (i&j&1) == 1 ? 'U' : 'W'; } } // Directions to walk let dir = [[1,0],[-1,0], [0,1],[0,-1]]; // Function to shuffle an array let shuffle = (inputArray) => { // Make a copy let array = [...inputArray] for (let i = array.length - 1; i > 0; i--) { let j = Math.floor(Math.random() * (i + 1)); // random index from 0 to i [array[i], array[j]] = [array[j], array[i]]; } return array } // Make a random walk breaking walls starting from cell i,j, // breaking walls until all reachable neighbor cells are visited. // Returns the longest path found as an array of cell indices. let visit = (i,j) => { lab [i][j] = '.' let longest = []; for (let [di,dj] of shuffle(dir)) { let [I,J] = [i+di*2,j+dj*2]; if (I<0||J<0||I>=imax||J>=jmax) continue; if (lab[I][J] == 'U') { lab [i+di][j+dj] = '.' let newpath = visit (I,J) if (newpath.length > longest.length) longest = newpath } } longest.push([i,j]) return longest } // Recursively visit the labyrinth grid from cell 1,1 let path = visit (1,1); return { lab , path } } 48:T14fc,// // The main code for drawing the labyrinth and responding to // user interaction // game = { let {lab,path} = labyrinth; let [imax,jmax] = [lab.length,lab[0].length] let [w,h]=boxPos(imax,jmax); let canvas = DOM.canvas(w,h); let ctx = canvas.getContext("2d"); // Load the check and exit images and mark the start position of // the player as visited (V), and the finish position as 'E' let checkMark = await FileAttachment('whitecheck.png').image(); let exitSign = await FileAttachment('exit.png').image(); let finish = path[0]; let start = path[path.length-1]; lab [finish[0]][finish[1]] = 'E'; lab [start[0]][start[1]] = 'V'; // Draws one cell of the labyrinth let drawCell = (i,j) => { if (lab[i][j] == 'W') { ctx.fillStyle = 'black'; ctx.fillRect (...boxPos(i,j), ...boxSize(i,j)) } else { ctx.fillStyle = 'lightGray'; ctx.fillRect (...boxPos(i,j), ...boxSize(i,j)) if (lab [i][j] == 'E') { ctx.drawImage (exitSign, ...boxPos(i,j), cellSize, cellSize) } else if (lab [i][j] == 'V') { let [x,y] = boxPos(i,j); ctx.drawImage (checkMark, x+cellSize/4, y+cellSize/4, cellSize/2, cellSize/2) } } } // Draws all cells of the labyrinth let drawLab = () => { for (let i = 0; i < imax; i++) { for (let j = 0; j < jmax; j++) { drawCell(i,j); } } } // return vector v rotated by angle a let rotVec = (v,a) => { return glmatrix.vec2.transformMat2([],v,glmatrix.mat2.fromRotation([],a)) } // Draws an arrow at position x,y, pointing in direction vx,vy let arrowLen = cellSize*0.4; let tipLen = arrowLen/3; let drawArrow = (x,y,vx,vy) => { ctx.strokeStyle = 'red'; ctx.lineWidth = 4; ctx.beginPath(); let s1 = arrowLen/2; let [x0,y0] = [x-vx*s1,y-vy*s1] ctx.moveTo (x0,y0); let s2 = s1-tipLen; let [x1,y1] = [x+vx*s1,y+vy*s1]; let [x2,y2] = [x+vx*s2,y+vy*s2]; ctx.lineTo (x2,y2); let turn = Math.PI/2; let [ax,ay] = rotVec([vx,vy],turn); ctx.lineTo (x2+ax*tipLen,y2+ay*tipLen); ctx.lineTo (x1,y1); let [bx,by] = rotVec([vx,vy],-turn); ctx.lineTo (x2+bx*tipLen,y2+by*tipLen); ctx.lineTo (x2,y2); ctx.stroke(); } // Player position and direction let player = { pos : start, dir : [1,0] } // Draws an arrow at the current player position let drawPlayer = () => { drawArrow(...boxPos(...player.pos).map(x => x+cellSize/2), ...player.dir) } // Turns the player clock/counterclockwise let animating = false; // Flag telling if animation is still in course let id; // id of the setInterval callback if animating let rotate = function (direction='clock') { if (animating) return; // Don't do anything if its still finishing animation let rotation = glmatrix.mat2.fromRotation([],direction=='clock'? Math.PI/2/30:-Math.PI/2/30); let counter = 0; function animation () { counter += 1; player.dir = glmatrix.vec2.transformMat2(player.dir,player.dir,rotation); drawCell(...player.pos); drawPlayer(); if (counter == 30) { clearInterval(id); animating = false; } } animating = true; id = setInterval(animation, 250/30); } let success = function() { ctx.font = '48px serif'; ctx.textAlign = 'center'; ctx.textBaseline = 'middle'; ctx.fillStyle = "red"; let counter = 0; function animation () { counter += 1; ctx.resetTransform (); ctx.clearRect (0,0,w,h); let mat = glmatrix.mat2d.fromTranslation([],[w/2+w/6*Math.sin(counter/15*Math.PI),h/2]) ctx.setTransform(...mat) ctx.fillText("You Win!",0,0) if (counter == 30) { clearInterval(id); animating = false; } } animating = true; id = setInterval(animation, 2000/30); } // Advances the player one cell, if possible let ahead = function () { if (animating) return; // Don't do anything if its still finishing animation let oldPos = [...player.pos]; let fwd = [Math.round(player.dir[1]),Math.round(player.dir[0])] let wallPos = glmatrix.vec2.add([],oldPos,fwd); if (lab[wallPos[0]][wallPos[1]] != '.') return; // Can't walk into a wall let newPos = glmatrix.vec2.add([],wallPos,fwd); let arrowCoords = (t)=>{ let a = boxPos(...oldPos) let b = boxPos(...newPos) return glmatrix.vec2.lerp([],a,b,t).map(x=>x+cellSize/2) } let counter = 0; function animation () { counter += 1; drawCell(...oldPos); drawCell(...wallPos); drawCell(...newPos); drawArrow(...arrowCoords(counter/30), ...player.dir) if (counter == 30) { clearInterval(id); animating = false; player.pos = newPos; lab[newPos[0]][newPos[1]] = 'V'; drawCell(...newPos) drawPlayer() if (newPos[0]==finish[0] && newPos[1]==finish[1]) success() } } animating = true; id = setInterval(animation, 250/30); } // Initial render drawLab() drawPlayer() // Do not forget to clear possible animations when cell is invalidated invalidation.then(() => { if (animating) clearInterval(id); }) return {canvas,rotate,ahead} }49:[{"id":"8f0c76b4c5b18a30f19518ac4e8863c6caadc0469859ecbc9311954429969229f9ec4e970b4819d4f79f175e4ea9889f4dd4890868402463141ff1ee539d7608","href":"https://static.observableusercontent.com/files/8f0c76b4c5b18a30f19518ac4e8863c6caadc0469859ecbc9311954429969229f9ec4e970b4819d4f79f175e4ea9889f4dd4890868402463141ff1ee539d7608","name":"exit.png","type":"image/png","lastModified":1599319325967.799,"size":12521},{"id":"cb47fe65703ae0fdd8658efe34b882c0f51a5316302f59ae2106e480a86788a27bd69672f2022af0b6c06c681ac9ba6843b4cd4abf7769f2e0c9874e7d0cf6cd","href":"https://static.observableusercontent.com/files/cb47fe65703ae0fdd8658efe34b882c0f51a5316302f59ae2106e480a86788a27bd69672f2022af0b6c06c681ac9ba6843b4cd4abf7769f2e0c9874e7d0cf6cd","name":"whitecheck.png","type":"image/png","lastModified":1599319326074.065,"size":13401}] 44:{"id":"2b41bd0baa466dee","slug":"2d-labyrinth","title":"2D Labyrinth","thumbnail":"10e95750bd06ae7bc4924ccd9ae8166bb98a211a17171a070cd5acc476037b4a","access_level":"public","create_time":"$D2020-09-05T12:34:12.067Z","update_time":"$D2020-09-09T13:27:24.281Z","view_time":null,"first_public_time":"$D2020-09-06T21:12:02.935Z","has_unpublished_edits":null,"fork":false,"stars":5,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024","bio":"Computer Graphics & Visualization @ufrj.br ","following":false},"version":240,"publish_version":240,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"bio":"Computer Graphics & Visualization @ufrj.br ","following":false}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":73,"collection":null,"type":"notebook","body":{"titling":"auto","title":"2D Labyrinth","cells":[{"id":0,"value":"md`# 2D Labyrinth \n\nA proof-of-concept implementation of a 2D labyrinth with a very simple interface.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"game.canvas","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"md`

\n## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$47","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"// Number of rows and columns in the labyrinth\nmutable labSize = [4,6]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"// Thickness of the walls with respect to the size of the cell\nwallThick = 0.1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"// Size of a cell\nmutable cellSize = 60","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"// Create the labyrinth\nlabyrinth = makeLabyrinth(...labSize)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"// The labyrinth drawing is done with boxes, both\n// the cells that have odd coordinates and the walls that have even\n// coordinates. This returns the size of the box at grid position i,j\nfunction boxSize (i,j) {\n return [j%2 ? cellSize : cellSize*wallThick, \n i%2 ? cellSize : cellSize*wallThick] \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"// Returns the canvas coordinates of the top left corner\n// of grid cell i,j\nfunction boxPos (i,j) {\n return [(Math.floor(j/2)*(1+wallThick)+(j%2)*wallThick) * cellSize,\n (Math.floor(i/2)*(1+wallThick)+(i%2)*wallThick) * cellSize]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"$48","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"glmatrix = require('https://bundle.run/gl-matrix@3.3.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W49","stdlib":"1"}} 45:"$44:body"