{"version":3,"file":"generate-maze.cjs","sources":["../src/generate-maze.ts"],"sourcesContent":["type Cell = {\n x: number,\n y: number,\n top: boolean,\n left: boolean,\n bottom: boolean,\n right: boolean,\n set: number,\n}\n\nfunction compact(array: T[]): T[] {\n return array.filter(Boolean);\n}\nfunction difference(c: T[], d: T[]): T[] {\n return [c, d].reduce((a, b) => a.filter(c => !b.includes(c)));\n}\nfunction initial(array: T[]): T[] {\n return array.slice(0, -1);\n}\nfunction groupBy(list: T[], key: string): { [key: string]: T[] } {\n const keys = list.map(item => item[key]);\n let dict = uniq(keys).reduce((prev, next) => {\n return {\n ...prev,\n [next]: []\n }\n }, {});\n\n list.forEach(item => dict[item[key]].push(item));\n\n return dict;\n}\nfunction last(array: T[]): T {\n return array[array.length - 1];\n}\nfunction range(n: number, end = 0): number[] {\n return end ? Array.from(Array(end - n).keys()).map(k => k + n) : Array.from(Array(n).keys());\n}\nfunction uniq(array: T[]): T[] {\n return [...new Set(array)];\n}\nfunction sampleSize(array: T[], n: number, random: () => number) {\n n = n == null ? 1 : n;\n const length = array == null ? 0 : array.length;\n if (!length || n < 1) {\n return [];\n }\n n = n > length ? length : n;\n let index = -1;\n const lastIndex = length - 1;\n const result = [...array];\n while (++index < n) {\n const rand = index + Math.floor(random() * (lastIndex - index + 1));\n const value = result[rand];\n result[rand] = result[index];\n result[index] = value;\n }\n return result.slice(0, n);\n}\n\nfunction mulberry32(seed: number) {\n return function () {\n let t = seed += 0x6D2B79F5;\n t = Math.imul(t ^ t >>> 15, t | 1);\n t ^= t + Math.imul(t ^ t >>> 7, t | 61);\n return ((t ^ t >>> 14) >>> 0) / 4294967296;\n }\n}\n\nfunction mergeSetWith(row: Cell[], oldSet: number, newSet: number) {\n row.forEach(box => {\n if (box.set === oldSet) box.set = newSet;\n });\n}\n\nfunction populateMissingSets(row: Cell[], random: () => number) {\n const setsInUse = compact(uniq(row.map(row => row.set)));\n const allSets = range(1, row.length + 1);\n const availableSets = difference(allSets, setsInUse).sort(() => 0.5 - random());\n row.filter(box => !box.set).forEach((box, i) => box.set = availableSets[i]);\n}\n\nfunction mergeRandomSetsIn(row: Cell[], random: () => number, probability = 0.5) {\n // Randomly merge some disjoint sets\n const allBoxesButLast = initial(row);\n allBoxesButLast.forEach((current, x) => {\n const next = row[x + 1];\n const differentSets = current.set !== next.set;\n const shouldMerge = random() <= probability;\n if (differentSets && shouldMerge) {\n mergeSetWith(row, next.set, current.set);\n current.right = false;\n next.left = false;\n }\n });\n}\n\nfunction addSetExits(row: Cell[], nextRow: Cell[], random: () => number) {\n // Randomly add bottom exit for each set\n const setsInRow = Object.values(groupBy(row, 'set'));\n const { ceil } = Math;\n setsInRow.forEach(set => {\n const exits = sampleSize(set, ceil(random() * set.length), random);\n exits.forEach(exit => {\n if (exit) {\n const below = nextRow[exit.x];\n exit.bottom = false;\n below.top = false;\n below.set = exit.set;\n }\n });\n });\n}\n\nfunction generate(width = 8, height = width, closed = true, seed = 1) {\n const random = mulberry32(seed);\n const maze = [];\n const r = range(width);\n\n // Populate maze with empty cells:\n for (let y = 0; y < height; y += 1) {\n const row = r.map(x => {\n return {\n x,\n y,\n top: closed || y > 0,\n left: closed || x > 0,\n bottom: closed || y < (height - 1),\n right: closed || x < (width - 1)\n };\n });\n maze.push(row);\n }\n\n // All rows except last:\n initial(maze).forEach((row, y) => { // TODO initial temp?\n populateMissingSets(row, random);\n mergeRandomSetsIn(row, random);\n addSetExits(row, maze[y + 1], random);\n });\n\n const lastRow = last(maze);\n populateMissingSets(lastRow, random);\n mergeRandomSetsIn(lastRow, random, 1);\n\n return maze;\n}\n\nexport default generate;\n"],"names":["initial","array","slice","range","n","end","Array","from","keys","map","k","uniq","Set","populateMissingSets","row","random","setsInUse","set","filter","Boolean","availableSets","c","length","d","reduce","a","b","includes","sort","box","forEach","i","mergeRandomSetsIn","probability","current","x","next","differentSets","shouldMerge","oldSet","newSet","mergeSetWith","right","left","width","height","closed","seed","t","Math","imul","mulberry32","maze","r","y","top","bottom","push","nextRow","setsInRow","Object","values","list","key","dict","item","prev","groupBy","ceil","index","lastIndex","result","rand","floor","value","sampleSize","exit","below","addSetExits","lastRow"],"mappings":"irBAgBA,SAASA,EAAWC,GAClB,OAAOA,EAAMC,MAAM,GAAI,GAkBzB,SAASC,EAAMC,EAAWC,EAAM,GAC9B,OAAOA,EAAMC,MAAMC,KAAKD,MAAMD,EAAMD,GAAGI,QAAQC,IAAIC,GAAKA,EAAIN,GAAKE,MAAMC,KAAKD,MAAMF,GAAGI,QAEvF,SAASG,EAAQV,GACf,MAAO,IAAI,IAAIW,IAAIX,IAoCrB,SAASY,EAAoBC,EAAaC,GACxC,MAAMC,EAAoBL,EAAKG,EAAIL,IAAIK,GAAOA,EAAIG,MAjErCC,OAAOC,SAmEdC,GAjEeC,EAgELlB,EAAM,EAAGW,EAAIQ,OAAS,GAhETC,EAiEaP,EAhEnC,CAACK,EAAGE,GAAGC,OAAO,CAACC,EAAGC,IAAMD,EAAEP,OAAOG,IAAMK,EAAEC,SAASN,MAgEJO,KAAK,IAAM,GAAMb,KAjExE,IAAuBM,EAAQE,EAkE7BT,EAAII,OAAOW,IAAQA,EAAIZ,KAAKa,QAAQ,CAACD,EAAKE,IAAMF,EAAIZ,IAAMG,EAAcW,IAG1E,SAASC,EAAkBlB,EAAaC,EAAsBkB,EAAc,IAElDjC,EAAQc,GAChBgB,QAAQ,CAACI,EAASC,KAChC,MAAMC,EAAOtB,EAAIqB,EAAI,GACfE,EAAgBH,EAAQjB,MAAQmB,EAAKnB,IACrCqB,EAAcvB,KAAYkB,EAC5BI,GAAiBC,IApBzB,SAAsBxB,EAAayB,EAAgBC,GACjD1B,EAAIgB,QAAQD,IACNA,EAAIZ,MAAQsB,IAAQV,EAAIZ,IAAMuB,KAmBhCC,CAAa3B,EAAKsB,EAAKnB,IAAKiB,EAAQjB,KACpCiB,EAAQQ,OAAQ,EAChBN,EAAKO,MAAO,oBAsBlB,SAAkBC,EAAQ,EAAGC,EAASD,EAAOE,GAAS,EAAMC,EAAO,GACjE,MAAMhC,EAvDR,SAAoBgC,GAClB,kBACE,IAAIC,EAAID,GAAQ,WAGhB,OAFAC,EAAIC,KAAKC,KAAKF,EAAIA,IAAM,GAAQ,EAAJA,GAC5BA,GAAKA,EAAIC,KAAKC,KAAKF,EAAIA,IAAM,EAAO,GAAJA,KACvBA,EAAIA,IAAM,MAAQ,GAAK,YAkDnBG,CAAWJ,GACpBK,EAAO,GACPC,EAAIlD,EAAMyC,GAGhB,IAAK,IAAIU,EAAI,EAAGA,EAAIT,EAAQS,GAAK,EAAG,CAClC,MAAMxC,EAAMuC,EAAE5C,IAAI0B,IACT,CACLA,EAAAA,EACAmB,EAAAA,EACAC,IAAKT,GAAUQ,EAAI,EACnBX,KAAMG,GAAUX,EAAI,EACpBqB,OAAQV,GAAUQ,EAAKT,EAAS,EAChCH,MAAOI,GAAUX,EAAKS,EAAQ,KAGlCQ,EAAKK,KAAK3C,GAIZd,EAAQoD,GAAMtB,QAAQ,CAAChB,EAAKwC,KAC1BzC,EAAoBC,EAAKC,GACzBiB,EAAkBlB,EAAKC,GAxC3B,SAAqBD,EAAa4C,EAAiB3C,GAEjD,MAAM4C,EAAYC,OAAOC,OAhF3B,SAAoBC,EAAWC,GAE7B,IAAIC,EAAOrD,EADEmD,EAAKrD,IAAIwD,GAAQA,EAAI,MACZzC,OAAO,CAAC0C,EAAM9B,WAE7B8B,OACH9B,CAACA,GAAO,KAET,IAIH,OAFA0B,EAAKhC,QAAQmC,GAAQD,EAAKC,EAAI,KAAOR,KAAKQ,IAEnCD,EAqEyBG,CAAQrD,KAClCsD,KAAEA,GAASnB,KACjBU,EAAU7B,QAAQb,KA5DpB,SAAuBhB,EAAYG,EAAWW,GAC5CX,EAAS,MAALA,EAAY,EAAIA,EACpB,MAAMkB,EAAkB,MAATrB,EAAgB,EAAIA,EAAMqB,OACzC,IAAKA,GAAUlB,EAAI,EACjB,MAAO,GAETA,EAAIA,EAAIkB,EAASA,EAASlB,EAC1B,IAAIiE,GAAS,EACb,MAAMC,EAAYhD,EAAS,EACrBiD,EAAS,IAAItE,GACnB,OAASoE,EAAQjE,GAAG,CAClB,MAAMoE,EAAOH,EAAQpB,KAAKwB,MAAM1D,KAAYuD,EAAYD,EAAQ,IAC1DK,EAAQH,EAAOC,GACrBD,EAAOC,GAAQD,EAAOF,GACtBE,EAAOF,GAASK,EAElB,OAAOH,EAAOrE,MAAM,EAAGE,IA6CPuE,CAAW1D,EAAKmD,EAAKrD,IAAWE,EAAIK,QAASP,GACrDe,QAAQ8C,IACZ,GAAIA,EAAM,CACR,MAAMC,EAAQnB,EAAQkB,EAAKzC,GAC3ByC,EAAKpB,QAAS,EACdqB,EAAMtB,KAAM,EACZsB,EAAM5D,IAAM2D,EAAK3D,SA8BrB6D,CAAYhE,EAAKsC,EAAKE,EAAI,GAAIvC,KAGhC,MAAMgE,GA7GS9E,EA6GMmD,GA5GRnD,EAAMqB,OAAS,GAD9B,IAAiBrB,EAiHf,OAHAY,EAAoBkE,EAAShE,GAC7BiB,EAAkB+C,EAAShE,EAAQ,GAE5BqC"}