[{"_1":2,"_172":-5,"_173":-5},"loaderData",{"_3":4,"_91":92},"root",{"_5":6,"_34":35,"_64":65},"ctx",{"_7":8,"_23":-5,"_24":25,"_26":27,"_28":20,"_29":20,"_30":20,"_31":32,"_33":20},"auth",{"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20,"_21":22},"sessionClaims","sessionId","sessionStatus","userId","actor","orgId","orgRole","orgSlug","orgPermissions","factorVerificationAge","isAuthenticated",false,"tokenType","session_token","user","preferencesKeybindings","default","preferencesTheme","light","preferencesFixers","preferencesCopilot","preferencesSelectionAi","notificationCount",0,"flagDenols","ENV",{"_36":37,"_38":39,"_40":41,"_42":43,"_44":45,"_46":47,"_48":49,"_50":51,"_52":53,"_54":55,"_56":57,"_58":59,"_60":61,"_62":63},"REACT_APP_SENTRY_DSN","https://586020d86f05489db63a554690acf1e9@o1398359.ingest.sentry.io/6724499","VAL_RUNTIME_NAME","prod","RENDER_GIT_COMMIT","0fffb492b08724537e73cd8bc4c3f31babbf0bd5","RENDER_GIT_BRANCH","main","CLERK_PUBLISHABLE_KEY","pk_live_Y2xlcmsudmFsLnRvd24k","POSTHOG_API_TOKEN","phc_nmoyuAkStEZuUp69rYlg1DZgrIt19Gx0Y4Hwf8tGgJP","POSTHOG_API_HOST","https://wart.val.town","WEB_API_TEMPLATE","https://{val}.web.val.run","APP_URL","https://www.val.town","MODULE_URL","https://esm.town","VANITY_WEB_API_TEMPLATE","https://{label}.val.run/","DENOLS_URL","https://lsp.val.town","NODE_ENV","production","API_URL","https://api.val.town","clerkState",{"_66":67},"__internal_clerk_state",{"_68":69,"_70":45,"_71":72,"_73":72,"_74":20,"_75":72,"_76":72,"_77":72,"_78":72,"_79":80,"_89":20,"_90":20},"__clerk_ssr_state",{"_21":22,"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20},"__publishableKey","__proxyUrl","","__domain","__isSatellite","__signInUrl","__signUpUrl","__afterSignInUrl","__afterSignUpUrl","__clerk_debug",{"_81":20,"_19":20,"_82":72,"_83":84,"_85":72,"_86":45,"_87":20,"_88":72},"isSignedIn","proxyUrl","reason","session-token-and-uat-missing","message","publishableKey","isSatellite","domain","__telemetryDisabled","__telemetryDebug","routes/embed.x.$handle.$name.$",{"_93":94,"_95":96,"_97":98,"_99":100,"_146":147,"_169":170,"_171":-5},"handle","dthyresson","name","a-mazing-maze-days","path","backend/maze/generator.ts","project",{"_101":102,"_95":96,"_103":104,"_105":-5,"_106":20,"_107":108,"_109":-5,"_110":-5,"_12":111,"_112":-5,"_113":20,"_114":-5,"_115":32,"_14":116,"_117":118,"_119":118,"_120":121,"_122":121,"_123":121,"_124":118,"_125":118,"_23":126,"_129":130,"_132":133,"_145":20},"id","f290afaa-35cd-11f0-9b77-9e149126039e","createdAt",["D",1747781910261],"deletedAt","legacyEnvVars","privacy","public","description","imageUrl","1167e096-63d9-481f-b740-997fcea83426","pinnedFileId","pinPreview","screenshotVersion","likeCount","8433e007-847e-4c91-8408-c94f14e035f8","userPerm","r","valPerm","blobPerm","rw","emailPerm","sqlitePerm","projectPerm","telemetryPerm",{"_93":94,"_127":128},"profileImageUrl","https://img.clerk.com/eyJ0eXBlIjoicHJveHkiLCJzcmMiOiJodHRwczovL2ltYWdlcy5jbGVyay5kZXYvb2F1dGhfZ2l0aHViL2ltZ18yY2VObmZYclBVbjhpdnlQQkROeEIycWViSTYifQ","org",{"_93":94,"_131":128,"_12":111},"avatar","branch",{"_134":135,"_95":43,"_101":136,"_137":102,"_138":-5,"_139":-5,"_140":-5,"_141":-5,"_142":-5,"_143":96,"_144":94},"version",28,"f290e128-35cd-11f0-9b77-9e149126039e","projectId","forkedBranchId","forkedBranchVersion","forkedProjectPrivacy","forkedProjectId","forkedProjectOrgId","projectName","userHandle","isOwned","file",{"_101":148,"_95":149,"_150":151,"_152":153,"_154":136,"_155":156,"_157":158,"_103":159,"_134":32,"_160":161,"_162":163,"_164":20,"_165":-5,"_97":166},"7d603b1e-35ce-11f0-9524-9e149126039e","generator.ts","fileId","7d603bf0-35ce-11f0-9524-9e149126039e","parentId","a1029839-1c87-4be4-8c5d-0773f33c8b98","branchId","branchVersion",5,"latest",true,["D",1747782143143],"fileType","script","content","import { Cell, CellType, Difficulty, Maze, MazeAlgorithm } from \"../../shared/types.ts\";\n\n// Initialize an empty grid with walls\nfunction initializeGrid(width: number, height: number): Cell[][] {\n const grid: Cell[][] = [];\n \n for (let y = 0; y < height; y++) {\n const row: Cell[] = [];\n for (let x = 0; x < width; x++) {\n row.push({ type: CellType.WALL, x, y });\n }\n grid.push(row);\n }\n \n return grid;\n}\n\n// Generate a maze using recursive backtracking (DFS)\nfunction generateRecursiveBacktracking(width: number, height: number, difficulty: Difficulty): Cell[][] {\n // Ensure odd dimensions for proper maze generation\n const actualWidth = width % 2 === 0 ? width + 1 : width;\n const actualHeight = height % 2 === 0 ? height + 1 : height;\n \n const grid = initializeGrid(actualWidth, actualHeight);\n \n // Start at a random odd position\n const startX = 1;\n const startY = 1;\n grid[startY][startX].type = CellType.PATH;\n \n const stack: [number, number][] = [[startX, startY]];\n \n // Directions: [dx, dy]\n const directions = [\n [0, -2], // Up\n [2, 0], // Right\n [0, 2], // Down\n [-2, 0] // Left\n ];\n \n while (stack.length > 0) {\n const [currentX, currentY] = stack[stack.length - 1];\n \n // Get unvisited neighbors\n const neighbors: [number, number][] = [];\n \n for (const [dx, dy] of directions) {\n const newX = currentX + dx;\n const newY = currentY + dy;\n \n if (\n newX > 0 && newX < actualWidth - 1 &&\n newY > 0 && newY < actualHeight - 1 &&\n grid[newY][newX].type === CellType.WALL\n ) {\n neighbors.push([newX, newY]);\n }\n }\n \n if (neighbors.length > 0) {\n // Choose a random neighbor\n const [nextX, nextY] = neighbors[Math.floor(Math.random() * neighbors.length)];\n \n // Carve a path to the neighbor\n grid[nextY][nextX].type = CellType.PATH;\n \n // Carve the wall between current and neighbor\n grid[(currentY + nextY) / 2][(currentX + nextX) / 2].type = CellType.PATH;\n \n // Push the neighbor to the stack\n stack.push([nextX, nextY]);\n } else {\n // Backtrack\n stack.pop();\n }\n }\n \n // Add some random paths based on difficulty to make it easier/harder\n const pathModifier = difficulty === Difficulty.EASY ? 0.1 : \n difficulty === Difficulty.MEDIUM ? 0.05 : 0.02;\n \n for (let y = 1; y < actualHeight - 1; y += 2) {\n for (let x = 1; x < actualWidth - 1; x += 2) {\n if (Math.random() < pathModifier && grid[y][x].type === CellType.WALL) {\n grid[y][x].type = CellType.PATH;\n }\n }\n }\n \n return grid;\n}\n\n// Generate a maze using Kruskal's algorithm\nfunction generateKruskal(width: number, height: number, difficulty: Difficulty): Cell[][] {\n // Ensure odd dimensions for proper maze generation\n const actualWidth = width % 2 === 0 ? width + 1 : width;\n const actualHeight = height % 2 === 0 ? height + 1 : height;\n \n const grid = initializeGrid(actualWidth, actualHeight);\n \n // Create cells at odd coordinates\n const cells: { x: number; y: number; set: number }[] = [];\n let setCounter = 0;\n \n for (let y = 1; y < actualHeight - 1; y += 2) {\n for (let x = 1; x < actualWidth - 1; x += 2) {\n grid[y][x].type = CellType.PATH;\n cells.push({ x, y, set: setCounter++ });\n }\n }\n \n // Create walls between cells\n const walls: { x: number; y: number; cell1: number; cell2: number }[] = [];\n \n for (let i = 0; i < cells.length; i++) {\n const { x, y } = cells[i];\n \n // Right wall\n if (x + 2 < actualWidth - 1) {\n const rightCellIndex = cells.findIndex(cell => cell.x === x + 2 && cell.y === y);\n if (rightCellIndex !== -1) {\n walls.push({ x: x + 1, y, cell1: i, cell2: rightCellIndex });\n }\n }\n \n // Bottom wall\n if (y + 2 < actualHeight - 1) {\n const bottomCellIndex = cells.findIndex(cell => cell.x === x && cell.y === y + 2);\n if (bottomCellIndex !== -1) {\n walls.push({ x, y: y + 1, cell1: i, cell2: bottomCellIndex });\n }\n }\n }\n \n // Shuffle walls\n for (let i = walls.length - 1; i > 0; i--) {\n const j = Math.floor(Math.random() * (i + 1));\n [walls[i], walls[j]] = [walls[j], walls[i]];\n }\n \n // Process walls\n for (const wall of walls) {\n const { x, y, cell1, cell2 } = wall;\n \n if (cells[cell1].set !== cells[cell2].set) {\n // Remove the wall\n grid[y][x].type = CellType.PATH;\n \n // Merge sets\n const oldSet = cells[cell2].set;\n const newSet = cells[cell1].set;\n \n for (const cell of cells) {\n if (cell.set === oldSet) {\n cell.set = newSet;\n }\n }\n }\n }\n \n // Add some random paths based on difficulty\n const pathModifier = difficulty === Difficulty.EASY ? 0.15 : \n difficulty === Difficulty.MEDIUM ? 0.08 : 0.03;\n \n for (let y = 1; y < actualHeight - 1; y++) {\n for (let x = 1; x < actualWidth - 1; x++) {\n if (Math.random() < pathModifier && grid[y][x].type === CellType.WALL) {\n grid[y][x].type = CellType.PATH;\n }\n }\n }\n \n return grid;\n}\n\n// Generate a maze using Prim's algorithm\nfunction generatePrim(width: number, height: number, difficulty: Difficulty): Cell[][] {\n // Ensure odd dimensions for proper maze generation\n const actualWidth = width % 2 === 0 ? width + 1 : width;\n const actualHeight = height % 2 === 0 ? height + 1 : height;\n \n const grid = initializeGrid(actualWidth, actualHeight);\n \n // Start with a random cell\n const startX = 1;\n const startY = 1;\n grid[startY][startX].type = CellType.PATH;\n \n // Add walls of the starting cell to the wall list\n const walls: [number, number][] = [\n [startX + 1, startY],\n [startX, startY + 1]\n ];\n \n while (walls.length > 0) {\n // Pick a random wall\n const randomIndex = Math.floor(Math.random() * walls.length);\n const [wallX, wallY] = walls[randomIndex];\n walls.splice(randomIndex, 1);\n \n // Check if the wall connects a path cell and a wall cell\n const neighbors: [number, number][] = [\n [wallX - 1, wallY], // Left\n [wallX + 1, wallY], // Right\n [wallX, wallY - 1], // Up\n [wallX, wallY + 1] // Down\n ];\n \n let pathCount = 0;\n for (const [nx, ny] of neighbors) {\n if (\n nx >= 0 && nx < actualWidth &&\n ny >= 0 && ny < actualHeight &&\n grid[ny][nx].type === CellType.PATH\n ) {\n pathCount++;\n }\n }\n \n // If the wall connects exactly one path cell, remove it\n if (pathCount === 1) {\n grid[wallY][wallX].type = CellType.PATH;\n \n // Add neighboring walls to the wall list\n for (const [nx, ny] of neighbors) {\n if (\n nx >= 1 && nx < actualWidth - 1 &&\n ny >= 1 && ny < actualHeight - 1 &&\n grid[ny][nx].type === CellType.WALL\n ) {\n // Check if this is a valid wall (between cells)\n const isValidWall = (\n (nx % 2 === 1 && ny % 2 === 0) || \n (nx % 2 === 0 && ny % 2 === 1)\n );\n \n if (isValidWall && !walls.some(([x, y]) => x === nx && y === ny)) {\n walls.push([nx, ny]);\n }\n }\n }\n }\n }\n \n // Add some random paths based on difficulty\n const pathModifier = difficulty === Difficulty.EASY ? 0.12 : \n difficulty === Difficulty.MEDIUM ? 0.06 : 0.02;\n \n for (let y = 1; y < actualHeight - 1; y++) {\n for (let x = 1; x < actualWidth - 1; x++) {\n if (Math.random() < pathModifier && grid[y][x].type === CellType.WALL) {\n grid[y][x].type = CellType.PATH;\n }\n }\n }\n \n return grid;\n}\n\n// Find a valid start and end position that are far apart\nfunction findStartAndEndPositions(grid: Cell[][]): { \n startPosition: { x: number; y: number }; \n endPosition: { x: number; y: number }; \n} {\n const height = grid.length;\n const width = grid[0].length;\n \n // Find all path cells\n const pathCells: { x: number; y: number }[] = [];\n \n for (let y = 0; y < height; y++) {\n for (let x = 0; x < width; x++) {\n if (grid[y][x].type === CellType.PATH) {\n pathCells.push({ x, y });\n }\n }\n }\n \n // Choose start position from the left side\n const leftSideCells = pathCells.filter(cell => cell.x < width / 3);\n const startPosition = leftSideCells[Math.floor(Math.random() * leftSideCells.length)];\n \n // Choose end position from the right side\n const rightSideCells = pathCells.filter(\n cell => cell.x > (width * 2) / 3 && \n Math.abs(cell.y - startPosition.y) > height / 3\n );\n const endPosition = rightSideCells[Math.floor(Math.random() * rightSideCells.length)];\n \n // Set cell types\n grid[startPosition.y][startPosition.x].type = CellType.START;\n grid[endPosition.y][endPosition.x].type = CellType.END;\n \n return { startPosition, endPosition };\n}\n\n// Generate a maze based on the specified algorithm, size, and difficulty\nexport function generateMaze(\n name: string,\n algorithm: MazeAlgorithm,\n width: number,\n height: number,\n difficulty: Difficulty\n): Maze {\n // Ensure minimum size\n const actualWidth = Math.max(width, 5);\n const actualHeight = Math.max(height, 5);\n \n let grid: Cell[][];\n \n // Generate maze based on algorithm\n switch (algorithm) {\n case MazeAlgorithm.RECURSIVE_BACKTRACKING:\n grid = generateRecursiveBacktracking(actualWidth, actualHeight, difficulty);\n break;\n case MazeAlgorithm.KRUSKAL:\n grid = generateKruskal(actualWidth, actualHeight, difficulty);\n break;\n case MazeAlgorithm.PRIM:\n grid = generatePrim(actualWidth, actualHeight, difficulty);\n break;\n default:\n grid = generateRecursiveBacktracking(actualWidth, actualHeight, difficulty);\n }\n \n // Find start and end positions\n const { startPosition, endPosition } = findStartAndEndPositions(grid);\n \n return {\n name,\n algorithm,\n difficulty,\n width: actualWidth,\n height: actualHeight,\n grid,\n startPosition,\n endPosition\n };\n}","deleted","label",[167,168,149],"backend","maze","permalink","https://www.val.town/x/dthyresson/a-mazing-maze-days/code/backend/maze/generator.ts","extension","actionData","errors"]