From b496a29a7de381765f3c45ced9fa18f026b2e314 Mon Sep 17 00:00:00 2001 From: Star Rauchenberger Date: Sat, 28 Oct 2023 00:16:07 -0400 Subject: serve --- app/assets/audio/wittle/.keep | 0 app/assets/audio/wittle/panel_abort_tracing.aac | Bin 0 -> 5606 bytes app/assets/audio/wittle/panel_failure.aac | Bin 0 -> 8543 bytes app/assets/audio/wittle/panel_start_tracing.aac | Bin 0 -> 12082 bytes app/assets/audio/wittle/panel_success.aac | Bin 0 -> 46061 bytes app/assets/config/wittle_manifest.js | 2 + app/assets/images/wittle/.keep | 0 app/assets/javascripts/wittle/application.js | 13 + app/assets/javascripts/wittle/custom_mechanics.js | 201 +++++ app/assets/javascripts/wittle/display2.js | 299 +++++++ app/assets/javascripts/wittle/polyominos.js | 331 ++++++++ app/assets/javascripts/wittle/puzzle.js | 507 +++++++++++ app/assets/javascripts/wittle/serializer.js | 346 ++++++++ app/assets/javascripts/wittle/solve.js | 531 ++++++++++++ app/assets/javascripts/wittle/svg.js | 422 +++++++++ app/assets/javascripts/wittle/trace2.js | 988 ++++++++++++++++++++++ app/assets/javascripts/wittle/utilities.js.erb | 697 +++++++++++++++ app/assets/javascripts/wittle/validate.js | 391 +++++++++ 18 files changed, 4728 insertions(+) create mode 100644 app/assets/audio/wittle/.keep create mode 100644 app/assets/audio/wittle/panel_abort_tracing.aac create mode 100644 app/assets/audio/wittle/panel_failure.aac create mode 100644 app/assets/audio/wittle/panel_start_tracing.aac create mode 100644 app/assets/audio/wittle/panel_success.aac delete mode 100644 app/assets/images/wittle/.keep create mode 100644 app/assets/javascripts/wittle/application.js create mode 100644 app/assets/javascripts/wittle/custom_mechanics.js create mode 100644 app/assets/javascripts/wittle/display2.js create mode 100644 app/assets/javascripts/wittle/polyominos.js create mode 100644 app/assets/javascripts/wittle/puzzle.js create mode 100644 app/assets/javascripts/wittle/serializer.js create mode 100644 app/assets/javascripts/wittle/solve.js create mode 100644 app/assets/javascripts/wittle/svg.js create mode 100644 app/assets/javascripts/wittle/trace2.js create mode 100644 app/assets/javascripts/wittle/utilities.js.erb create mode 100644 app/assets/javascripts/wittle/validate.js (limited to 'app/assets') diff --git a/app/assets/audio/wittle/.keep b/app/assets/audio/wittle/.keep new file mode 100644 index 0000000..e69de29 diff --git a/app/assets/audio/wittle/panel_abort_tracing.aac b/app/assets/audio/wittle/panel_abort_tracing.aac new file mode 100644 index 0000000..1871586 Binary files /dev/null and b/app/assets/audio/wittle/panel_abort_tracing.aac differ diff --git a/app/assets/audio/wittle/panel_failure.aac b/app/assets/audio/wittle/panel_failure.aac new file mode 100644 index 0000000..c61fe94 Binary files /dev/null and b/app/assets/audio/wittle/panel_failure.aac differ diff --git a/app/assets/audio/wittle/panel_start_tracing.aac b/app/assets/audio/wittle/panel_start_tracing.aac new file mode 100644 index 0000000..9b828f1 Binary files /dev/null and b/app/assets/audio/wittle/panel_start_tracing.aac differ diff --git a/app/assets/audio/wittle/panel_success.aac b/app/assets/audio/wittle/panel_success.aac new file mode 100644 index 0000000..d6e75fe Binary files /dev/null and b/app/assets/audio/wittle/panel_success.aac differ diff --git a/app/assets/config/wittle_manifest.js b/app/assets/config/wittle_manifest.js index af556d6..079ddad 100644 --- a/app/assets/config/wittle_manifest.js +++ b/app/assets/config/wittle_manifest.js @@ -1 +1,3 @@ //= link_directory ../stylesheets/wittle .css +//= link_directory ../javascripts/wittle .js +//= link_directory ../audio/wittle .aac diff --git a/app/assets/images/wittle/.keep b/app/assets/images/wittle/.keep deleted file mode 100644 index e69de29..0000000 diff --git a/app/assets/javascripts/wittle/application.js b/app/assets/javascripts/wittle/application.js new file mode 100644 index 0000000..e54c646 --- /dev/null +++ b/app/assets/javascripts/wittle/application.js @@ -0,0 +1,13 @@ +// This is a manifest file that'll be compiled into application.js, which will include all the files +// listed below. +// +// Any JavaScript/Coffee file within this directory, lib/assets/javascripts, vendor/assets/javascripts, +// or any plugin's vendor/assets/javascripts directory can be referenced here using a relative path. +// +// It's not advisable to add code directly here, but if you do, it'll appear at the bottom of the +// compiled file. JavaScript code in this file should be added after the last require_* statement. +// +// Read Sprockets README (https://github.com/rails/sprockets#sprockets-directives) for details +// about supported directives. +// +//= require_tree . diff --git a/app/assets/javascripts/wittle/custom_mechanics.js b/app/assets/javascripts/wittle/custom_mechanics.js new file mode 100644 index 0000000..d4733db --- /dev/null +++ b/app/assets/javascripts/wittle/custom_mechanics.js @@ -0,0 +1,201 @@ +namespace(function() { + +function isCellBridgePathFriendly(puzzle, color, pos) { + if (pos.x%2 === 0 && pos.y%2 === 0) return false + var cell = puzzle.getCell(pos.x, pos.y) + return cell == null || cell.color == null || cell.color === color +} + +function makeMinimalTree(graph, root, required) { + var seen = Array(graph.length).fill(false) + var result = Array(graph.length).fill(false) + result[root] = true + function dfs(node) { + seen[node] = true + result[node] = required[node] + for (var child of graph[node]) { + if (!seen[child]) { + dfs(child) + result[node] = result[node] || result[child] + } + } + } + dfs(root) + return result +} + +function isTreeUnique(graph, isInTree) { + var seen = isInTree.slice() + function dfs(node) { + seen[node] = true + var reachableTreeNode = null + for (var child of graph[node]) { + var candidate = null + if (isInTree[child]) { + candidate = child + } else if (!seen[child]) { + candidate = dfs(child) + } + if (candidate != null && candidate !== reachableTreeNode) { + if (reachableTreeNode == null) { + reachableTreeNode = candidate + } else { + return -1 + } + } + } + return reachableTreeNode + } + for (var i = 0; i < graph.length; i++) { + if (!seen[i]) { + if (dfs(i) === -1) return false + } + } + return true +} + +function puzzleCellsAdjacent(first, second, pillar) { + if (pillar && first.y == second.y && Math.abs(second.x - first.x) === puzzle.width - 1) + return true + return Math.abs(second.x - first.x) + Math.abs(second.y - first.y) === 1 +} + +function bridgeTest(region, puzzle, color, bridges) { + var nodes = region.cells.filter(pos => isCellBridgePathFriendly(puzzle, color, pos)) + var graph = Array.from(Array(nodes.length), () => []) + for (var ir = 1; ir < nodes.length; ir++) { + var right = nodes[ir] + for (var il = 0; il < ir; il++) { + var left = nodes[il] + if (puzzleCellsAdjacent(left, right, puzzle.pillar)) { + graph[il].push(ir) + graph[ir].push(il) + } + } + } + var isBridge = nodes.map(node => bridges.some(bridge => node.x === bridge.x && node.y === bridge.y)) + var isInTree = makeMinimalTree(graph, isBridge.indexOf(true), isBridge) + for (var i = 0; i < nodes.length; i++) { + if (isBridge[i] && !isInTree[i]) return false + } + return isTreeUnique(graph, isInTree) +} + +window.validateBridges = function(puzzle, region, regionData) { + var bridges = {} + for (var pos of region) { + var cell = puzzle.getCell(pos.x, pos.y) + if (cell == null) continue + + // Count color-based elements + if (cell.color != null) { + if (cell.type === 'bridge') { + if (bridges[cell.color] == null) { + bridges[cell.color] = [] + } + bridges[cell.color].push(pos) + } + } + } + + for (var color in bridges) { + var total = 0 + var discardable = 0 + for (var x=1; x < puzzle.width; x+=2) { + for (var y=1; y < puzzle.height; y+=2) { + var cell = puzzle.getCell(x, y) + if (cell != null) { + if (cell.type === 'bridge' && cell.color === color) total++ + if (cell.type === 'nega') discardable++ + } + } + } + + if (bridges[color].length != total) { + if (bridges[color].length >= total - discardable) { + // TODO: Negations in other regions can validate the solution + for (var bridge of bridges[color]) { + regionData.addInvalid(bridge) + } + } else { + for (var bridge of bridges[color]) { + regionData.addVeryInvalid(bridge) + } + } + } else if (!window.bridgeTest(region, puzzle, color, bridges[color])) { + for (var bridge of bridges[color]) { + regionData.addInvalid(bridge) + } + } + } +} + +var DIRECTIONS = [ + {'x': 0, 'y':-1}, + {'x': 1, 'y':-1}, + {'x': 1, 'y': 0}, + {'x': 1, 'y': 1}, + {'x': 0, 'y': 1}, + {'x':-1, 'y': 1}, + {'x':-1, 'y': 0}, + {'x':-1, 'y':-1}, +] + +window.validateArrows = function(puzzle, region, regionData) { + for (var pos of region) { + var cell = puzzle.getCell(pos.x, pos.y) + if (cell == null) continue + if (cell.type != 'arrow') continue + dir = DIRECTIONS[cell.rot] + + var count = 0 + var x = pos.x + dir.x + var y = pos.y + dir.y + for (var i=0; i<100; i++) { // 100 is arbitrary, it's just here to avoid infinite loops. + var line = puzzle.getLine(x, y) + console.spam('Testing', x, y, 'for arrow at', pos.x, pos.y, 'found', line) + if (line == null && (x%2 !== 1 || y%2 !== 1)) break + if (line > window.LINE_NONE) count++ + if (count > cell.count) break + x += dir.x * 2 + y += dir.y * 2 + if (puzzle.matchesSymmetricalPos(x, y, pos.x + dir.x, pos.y + dir.y)) break // Pillar exit condition (in case of looping) + } + if (count !== cell.count) { + console.log('Arrow at', pos.x, pos.y, 'crosses', count, 'lines, but should cross', cell.count) + regionData.addInvalid(pos) + } + } +} + +window.validateSizers = function(puzzle, region, regionData) { + var sizers = [] + var regionSize = 0 + for (var pos of region) { + if (pos.x%2 === 1 && pos.y%2 === 1) regionSize++ // Only count cells for the region + var cell = puzzle.getCell(pos.x, pos.y) + if (cell == null) continue + if (cell.type == 'sizer') sizers.push(pos) + } + console.debug('Found', sizers.length, 'sizers') + if (sizers.length == 0) return // No sizers -- no impact on sizer validity + + var sizerCount = regionSize / sizers.length + if (sizerCount % 1 != 0) { + console.log('Region size', regionSize, 'is not a multiple of # sizers', sizers.length) + for (var sizer of sizers) { + regionData.addInvalid(sizer) + } + return + } + + if (puzzle.sizerCount == null) puzzle.sizerCount = sizerCount // No other sizes have been defined + if (puzzle.sizerCount != sizerCount) { + console.log('sizerCount', sizerCount, 'does not match puzzle sizerCount', puzzle.sizerCount) + for (var sizer of sizers) { + regionData.addInvalid(sizer) + } + } +} + +}) diff --git a/app/assets/javascripts/wittle/display2.js b/app/assets/javascripts/wittle/display2.js new file mode 100644 index 0000000..52069d6 --- /dev/null +++ b/app/assets/javascripts/wittle/display2.js @@ -0,0 +1,299 @@ +namespace(function() { + +window.draw = function(puzzle, target='puzzle') { + if (puzzle == null) return + var svg = document.getElementById(target) + console.info('Drawing', puzzle, 'into', svg) + while (svg.firstChild) svg.removeChild(svg.firstChild) + + // Prevent context menu popups within the puzzle + svg.oncontextmenu = function(event) { + event.preventDefault() + } + + if (puzzle.pillar === true) { + // 41*width + 30*2 (padding) + 10*2 (border) + var pixelWidth = 41 * puzzle.width + 80 + } else { + // 41*(width-1) + 24 (extra edge) + 30*2 (padding) + 10*2 (border) + var pixelWidth = 41 * puzzle.width + 63 + } + var pixelHeight = 41 * puzzle.height + 63 + svg.setAttribute('viewbox', '0 0 ' + pixelWidth + ' ' + pixelHeight) + svg.setAttribute('width', pixelWidth) + svg.setAttribute('height', pixelHeight) + + var rect = createElement('rect') + svg.appendChild(rect) + rect.setAttribute('stroke-width', 10) + rect.setAttribute('stroke', window.BORDER) + rect.setAttribute('fill', window.OUTER_BACKGROUND) + // Accounting for the border thickness + rect.setAttribute('x', 5) + rect.setAttribute('y', 5) + rect.setAttribute('width', pixelWidth - 10) // Removing border + rect.setAttribute('height', pixelHeight - 10) // Removing border + + drawCenters(puzzle, svg) + drawGrid(puzzle, svg, target) + drawStartAndEnd(puzzle, svg) + // Draw cell symbols after so they overlap the lines, if necessary + drawSymbols(puzzle, svg, target) + + // For pillar puzzles, add faders for the left and right sides + if (puzzle.pillar === true) { + var defs = window.createElement('defs') + defs.id = 'cursorPos' + defs.innerHTML = '' + + '\n' + + ' \n' + + ' \n' + + ' \n' + + '\n' + + '\n' + + ' \n' + + ' \n' + + '\n' + svg.appendChild(defs) + + var leftBox = window.createElement('rect') + leftBox.setAttribute('x', 16) + leftBox.setAttribute('y', 10) + leftBox.setAttribute('width', 48) + leftBox.setAttribute('height', 41 * puzzle.height + 43) + leftBox.setAttribute('fill', 'url(#fadeInLeft)') + leftBox.setAttribute('style', 'pointer-events: none') + svg.appendChild(leftBox) + + var rightBox = window.createElement('rect') + rightBox.setAttribute('x', 41 * puzzle.width + 22) + rightBox.setAttribute('y', 10) + rightBox.setAttribute('width', 30) + rightBox.setAttribute('height', 41 * puzzle.height + 43) + rightBox.setAttribute('fill', 'url(#fadeOutRight)') + rightBox.setAttribute('style', 'pointer-events: none') + svg.appendChild(rightBox) + } +} + +function drawCenters(puzzle, svg) { + // @Hack that I am not fixing. This switches the puzzle's grid to a floodfilled grid + // where null represents cells which are part of the outside + var savedGrid = puzzle.switchToMaskedGrid() + if (puzzle.pillar === true) { + for (var y=1; y 1) { + // Add rounding for other intersections (handling gap-only corners) + var circ = createElement('circle') + circ.setAttribute('cx', x*41 + 52) + circ.setAttribute('cy', y*41 + 52) + circ.setAttribute('r', 12) + circ.setAttribute('fill', window.FOREGROUND) + svg.appendChild(circ) + } + } + } + } + // Determine if left-side needs a 'wrap indicator' + if (puzzle.pillar === true) { + var x = 0; + for (var y=0; y window.DOT_NONE) { + params.type = 'dot' + if (cell.dot === window.DOT_BLACK) params.color = 'black' + else if (cell.dot === window.DOT_BLUE) params.color = window.LINE_PRIMARY + else if (cell.dot === window.DOT_YELLOW) params.color = window.LINE_SECONDARY + else if (cell.dot === window.DOT_INVISIBLE) { + params.color = window.FOREGROUND + // This makes the invisible dots visible, but only while we're in the editor. + if (document.getElementById('metaButtons') != null) { + params.stroke = 'black' + params.strokeWidth = '2px' + } + } + drawSymbolWithSvg(svg, params) + } else if (cell.gap === window.GAP_BREAK) { + // Gaps were handled above, while drawing the grid. + } else if (x%2 === 1 && y%2 === 1) { + // Generic draw for all other elements + Object.assign(params, cell) + window.drawSymbolWithSvg(svg, params, puzzle.settings.CUSTOM_MECHANICS) + } + } + } +} + +function drawStartAndEnd(puzzle, svg) { + for (var x=0; x= 4 || y >= 4) return false + return (polyshape & mask(x, y)) !== 0 +} + +// This is 2^20, whereas all the other bits fall into 2^(0-15) +window.ROTATION_BIT = (1 << 20) + +window.isRotated = function(polyshape) { + return (polyshape & ROTATION_BIT) !== 0 +} + +function getRotations(polyshape) { + if (!isRotated(polyshape)) return [polyshape] + + var rotations = [0, 0, 0, 0] + for (var x=0; x<4; x++) { + for (var y=0; y<4; y++) { + if (isSet(polyshape, x, y)) { + rotations[0] ^= mask(x, y) + rotations[1] ^= mask(y, 3-x) + rotations[2] ^= mask(3-x, 3-y) + rotations[3] ^= mask(3-y, x) + } + } + } + + return rotations +} + +// 90 degree rotations of the polyomino +window.rotatePolyshape = function(polyshape, count=1) { + var rotations = getRotations(polyshape | window.ROTATION_BIT) + return rotations[count % 4] +} + +// IMPORTANT NOTE: When formulating these, the top row must contain (0, 0) +// That means there will never be any negative y values. +// (0, 0) must also be a cell in the shape, so that +// placing the shape at (x, y) will fill (x, y) +// Ylops will have -1s on all adjacent cells, to break "overlaps" for polyominos. +window.polyominoFromPolyshape = function(polyshape, ylop=false, precise=true) { + var topLeft = null + for (var y=0; y<4; y++) { + for (var x=0; x<4; x++) { + if (isSet(polyshape, x, y)) { + topLeft = {'x':x, 'y':y} + break + } + } + if (topLeft != null) break + } + if (topLeft == null) return [] // Empty polyomino + + var polyomino = [] + for (var x=0; x<4; x++) { + for (var y=0; y<4; y++) { + if (!isSet(polyshape, x, y)) continue + polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y)}) + + // "Precise" polyominos adds cells in between the apparent squares in the polyomino. + // This prevents the solution line from going through polyominos in the solution. + if (precise) { + if (ylop) { + // Ylops fill up/left if no adjacent cell, and always fill bottom/right + if (!isSet(polyshape, x - 1, y)) { + polyomino.push({'x':2*(x - topLeft.x) - 1, 'y':2*(y - topLeft.y)}) + } + if (!isSet(polyshape, x, y - 1)) { + polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y) - 1}) + } + polyomino.push({'x':2*(x - topLeft.x) + 1, 'y':2*(y - topLeft.y)}) + polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y) + 1}) + } else { + // Normal polys only fill bottom/right if there is an adjacent cell. + if (isSet(polyshape, x + 1, y)) { + polyomino.push({'x':2*(x - topLeft.x) + 1, 'y':2*(y - topLeft.y)}) + } + if (isSet(polyshape, x, y + 1)) { + polyomino.push({'x':2*(x - topLeft.x), 'y':2*(y - topLeft.y) + 1}) + } + } + } + } + } + return polyomino +} + +window.polyshapeFromPolyomino = function(polyomino) { + var topLeft = {'x': 9999, 'y': 9999} + for (var pos of polyomino) { + if (pos.x%2 != 1 || pos.y%2 != 1) continue // We only care about cells, not edges or intersections + + // Unlike when we're making a polyomino, we just want to top and left flush the shape, + // we don't actually need (0, 0) to be filled. + if (pos.x < topLeft.x) topLeft.x = pos.x + if (pos.y < topLeft.y) topLeft.y = pos.y + } + if (topLeft == null) return 0 // Empty polyomino + + var polyshape = 0 + for (var pos of polyomino) { + if (pos.x%2 != 1 || pos.y%2 != 1) continue // We only care about cells, not edges or intersections + var x = (pos.x - topLeft.x) / 2 // 0.5x to convert from puzzle coordinates to polyshape coordinates + var y = (pos.y - topLeft.y) / 2 // 0.5x to convert from puzzle coordinates to polyshape coordinates + polyshape |= mask(x, y) + } + + return polyshape +} + +// In some cases, polyominos and onimoylops will fully cancel each other out. +// However, even if they are the same size, that doesn't guarantee that they fit together. +// As an optimization, we save the results for known combinations of shapes, since there are likely many +// fewer pairings of shapes than paths through the grid. +var knownCancellations = {} + +// Attempt to fit polyominos in a region into the puzzle. +// This function checks for early exits, then simplifies the grid to a numerical representation: +// * 1 represents a square that has been double-covered (by two polyominos) +// * Or, in the cancellation case, it represents a square that was covered by a polyomino and not by an onimoylop +// * 0 represents a square that is satisfied, either because: +// * it is outside the region +// * (In the normal case) it was inside the region, and has been covered by a polyomino +// * (In the cancellation case) it was covered by an equal number of polyominos and onimoylops +// * -1 represents a square that needs to be covered once (inside the region, or outside but covered by an onimoylop) +// * -2 represents a square that needs to be covered twice (inside the region & covered by an onimoylop) +// * And etc, for additional layers of polyominos/onimoylops. +window.polyFit = function(region, puzzle) { + var polys = [] + var ylops = [] + var polyCount = 0 + var regionSize = 0 + for (var pos of region) { + if (pos.x%2 === 1 && pos.y%2 === 1) regionSize++ + var cell = puzzle.grid[pos.x][pos.y] + if (cell == null) continue + if (cell.polyshape === 0) continue + if (cell.type === 'poly') { + polys.push(cell) + polyCount += getPolySize(cell.polyshape) + } else if (cell.type === 'ylop') { + ylops.push(cell) + polyCount -= getPolySize(cell.polyshape) + } + } + if (polys.length + ylops.length === 0) { + console.log('No polyominos or onimoylops inside the region, vacuously true') + return true + } + if (polyCount > 0 && polyCount !== regionSize) { + console.log('Combined size of polyominos and onimoylops', polyCount, 'does not match region size', regionSize) + return false + } + if (polyCount < 0) { + console.log('Combined size of onimoylops is greater than polyominos by', -polyCount) + return false + } + var key = null + if (polyCount === 0) { + if (puzzle.settings.SHAPELESS_ZERO_POLY) { + console.log('Combined size of polyominos and onimoylops is zero') + return true + } + // These will be ordered by the order of cells in the region, which isn't exactly consistent. + // In practice, it seems to be good enough. + key = '' + for (var ylop of ylops) key += ' ' + ylop.polyshape + key += '|' + for (var poly of polys) key += ' ' + poly.polyshape + var ret = knownCancellations[key] + if (ret != null) return ret + } + + // For polyominos, we clear the grid to mark it up again: + var savedGrid = puzzle.grid + puzzle.newGrid() + // First, we mark all cells as 0: Cells outside the target region should be unaffected. + for (var x=0; x 0) { + for (var pos of region) puzzle.grid[pos.x][pos.y] = -1 + } + // In the exact match case, we leave every cell marked 0: Polys and ylops need to cancel. + + var ret = placeYlops(ylops, 0, polys, puzzle) + if (polyCount === 0) knownCancellations[key] = ret + puzzle.grid = savedGrid + return ret +} + +// If false, poly doesn't fit and grid is unmodified +// If true, poly fits and grid is modified (with the placement) +function tryPlacePolyshape(cells, x, y, puzzle, sign) { + console.spam('Placing at', x, y, 'with sign', sign) + var numCells = cells.length + for (var i=0; i 0) { + console.log('Cell', x, y, 'has been overfilled and no ylops left to place') + return false + } + if (allPolysPlaced && cell < 0 && x%2 === 1 && y%2 === 1) { + // Normal, center cell with a negative value & no polys remaining. + console.log('All polys placed, but grid not full') + return false + } + } + } + if (allPolysPlaced) { + console.log('All polys placed, and grid full') + return true + } + + // The top-left (first open cell) must be filled by a polyomino. + // However in the case of pillars, there is no top-left, so we try all open cells in the + // top-most open row + var openCells = [] + for (var y=1; y= 0) continue + openCells.push({'x':x, 'y':y}) + if (puzzle.pillar === false) break + } + if (openCells.length > 0) break + } + + if (openCells.length === 0) { + console.log('Polys remaining but grid full') + return false + } + + for (var openCell of openCells) { + var attemptedPolyshapes = [] + for (var i=0; i0 polys, but no valid recursion.') + return false +} + +}) diff --git a/app/assets/javascripts/wittle/puzzle.js b/app/assets/javascripts/wittle/puzzle.js new file mode 100644 index 0000000..a7ad10a --- /dev/null +++ b/app/assets/javascripts/wittle/puzzle.js @@ -0,0 +1,507 @@ +namespace(function() { + +// A 2x2 grid is internally a 5x5: +// corner, edge, corner, edge, corner +// edge, cell, edge, cell, edge +// corner, edge, corner, edge, corner +// edge, cell, edge, cell, edge +// corner, edge, corner, edge, corner +// +// Corners and edges will have a value of true if the line passes through them +// Cells will contain an object if there is an element in them +window.Puzzle = class { + constructor(width, height, pillar=false) { + if (pillar === true) { + this.newGrid(2 * width, 2 * height + 1) + } else { + this.newGrid(2 * width + 1, 2 * height + 1) + } + this.pillar = pillar + this.settings = { + // If true, negation symbols are allowed to cancel other negation symbols. + NEGATIONS_CANCEL_NEGATIONS: true, + + // If true, and the count of polyominos and onimoylops is zero, they cancel regardless of shape. + SHAPELESS_ZERO_POLY: false, + + // If true, the traced line cannot go through the placement of a polyomino. + PRECISE_POLYOMINOS: true, + + // If false, incorrect elements will not flash when failing the puzzle. + FLASH_FOR_ERRORS: true, + + // If true, mid-segment startpoints will constitute solid lines, and form boundaries for the region. + FAT_STARTPOINTS: false, + + // If true, custom mechanics are displayed (and validated) in this puzzle. + CUSTOM_MECHANICS: false, + + // If true, polyominos may be placed partially off of the grid as an intermediate solution step. + // OUT_OF_BOUNDS_POLY: false, + } + } + + static deserialize(json) { + var parsed = JSON.parse(json) + // Claim that it's not a pillar (for consistent grid sizing), then double-check ourselves later. + var puzzle = new Puzzle((parsed.grid.length - 1)/2, (parsed.grid[0].length - 1)/2) + puzzle.name = parsed.name + puzzle.autoSolved = parsed.autoSolved + puzzle.grid = parsed.grid + // Legacy: Grid squares used to use 'false' to indicate emptiness. + // Legacy: Cells may use {} to represent emptiness + // Now, we use: + // Cells default to null + // During onTraceStart, empty cells that are still inbounds are changed to {'type': 'nonce'} for tracing purposes. + // Lines default to {'type':'line', 'line':0} + for (var x=0; x= this.width) return false + if (y < 0 || y >= this.height) return false + return true + } + + getCell(x, y) { + x = this._mod(x) + if (!this._safeCell(x, y)) return null + return this.grid[x][y] + } + + setCell(x, y, value) { + x = this._mod(x) + if (!this._safeCell(x, y)) return + this.grid[x][y] = value + } + + getSymmetricalDir(dir) { + if (this.symmetry != null) { + if (this.symmetry.x === true) { + if (dir === 'left') return 'right' + if (dir === 'right') return 'left' + } + if (this.symmetry.y === true) { + if (dir === 'top') return 'bottom' + if (dir === 'bottom') return 'top' + } + } + return dir + } + + // The resulting position is guaranteed to be gridsafe. + getSymmetricalPos(x, y) { + if (this.symmetry != null) { + if (this.pillar === true) { + x += this.width/2 + if (this.symmetry.x === true) { + x = this.width - x + } + } else { + if (this.symmetry.x === true) { + x = (this.width - 1) - x + } + } + if (this.symmetry.y === true) { + y = (this.height - 1) - y + } + } + return {'x':this._mod(x), 'y':y} + } + + getSymmetricalCell(x, y) { + var pos = this.getSymmetricalPos(x, y) + return this.getCell(pos.x, pos.y) + } + + matchesSymmetricalPos(x1, y1, x2, y2) { + return (y1 === y2 && this._mod(x1) === x2) + } + + // A variant of getCell which specifically returns line values, + // and treats objects as being out-of-bounds + getLine(x, y) { + var cell = this.getCell(x, y) + if (cell == null) return null + if (cell.type !== 'line') return null + return cell.line + } + + updateCell2(x, y, key, value) { + x = this._mod(x) + if (!this._safeCell(x, y)) return + var cell = this.grid[x][y] + if (cell == null) return + cell[key] = value + } + + getValidEndDirs(x, y) { + x = this._mod(x) + if (!this._safeCell(x, y)) return [] + + var dirs = [] + var leftCell = this.getCell(x - 1, y) + if (leftCell == null || leftCell.gap === window.GAP_FULL) dirs.push('left') + var topCell = this.getCell(x, y - 1) + if (topCell == null || topCell.gap === window.GAP_FULL) dirs.push('top') + var rightCell = this.getCell(x + 1, y) + if (rightCell == null || rightCell.gap === window.GAP_FULL) dirs.push('right') + var bottomCell = this.getCell(x, y + 1) + if (bottomCell == null || bottomCell.gap === window.GAP_FULL) dirs.push('bottom') + return dirs + } + + // Note: Does not use this.width/this.height, so that it may be used to ask about resizing. + getSizeError(width, height) { + if (this.pillar && width < 4) return 'Pillars may not have a width of 1' + if (width * height < 25) return 'Puzzles may not be smaller than 2x2 or 1x4' + if (width > 21 || height > 21) return 'Puzzles may not be larger than 10 in either dimension' + if (this.symmetry != null) { + if (this.symmetry.x && width <= 2) return 'Symmetrical puzzles must be sufficiently wide for both lines' + if (this.symmetry.y && height <= 2) return 'Symmetrical puzzles must be sufficiently wide for both lines' + if (this.pillar && this.symmetry.x && width % 4 !== 0) return 'X + Pillar symmetry must be an even number of rows, to keep both startpoints at the same parity' + } + + return null + } + + + // Called on a solution. Computes a list of gaps to show as hints which *do not* + // break the path. + loadHints() { + this.hints = [] + for (var x=0; x window.LINE_NONE) { + this.hints.push({'x':x, 'y':y}) + } + } + } + } + + // Show a hint on the grid. + // If no hint is provided, will select the best one it can find, + // prioritizing breaking current lines on the grid. + // Returns the shown hint. + showHint(hint) { + if (hint != null) { + this.grid[hint.x][hint.y].gap = window.GAP_BREAK + return + } + + var goodHints = [] + var badHints = [] + + for (var hint of this.hints) { + if (this.getLine(hint.x, hint.y) > window.LINE_NONE) { + // Solution will be broken by this hint + goodHints.push(hint) + } else { + badHints.push(hint) + } + } + if (goodHints.length > 0) { + var hint = goodHints.splice(window.randInt(goodHints.length), 1)[0] + } else if (badHints.length > 0) { + var hint = badHints.splice(window.randInt(badHints.length), 1)[0] + } else { + return + } + this.grid[hint.x][hint.y].gap = window.GAP_BREAK + this.hints = badHints.concat(goodHints) + return hint + } + + clearLines() { + for (var x=0; x 0) this._floodFill(x, y - 1, region, col) + if (x < this.width - 1) this._floodFill(x + 1, y, region, this.grid[x+1]) + else if (this.pillar !== false) this._floodFill(0, y, region, this.grid[0]) + if (x > 0) this._floodFill(x - 1, y, region, this.grid[x-1]) + else if (this.pillar !== false) this._floodFill(this.width-1, y, region, this.grid[this.width-1]) + } + + // Re-uses the same grid, but only called on edges which border the outside + // Called first to mark cells that are connected to the outside, i.e. should not be part of any region. + _floodFillOutside(x, y, col) { + var cell = col[y] + if (cell === MASKED_PROCESSED) return + if (x%2 !== y%2 && cell !== MASKED_GAP2) return // Only flood-fill through gap-2 + if (x%2 === 0 && y%2 === 0 && cell === MASKED_DOT) return // Don't flood-fill through dots + col[y] = MASKED_PROCESSED + + if (x%2 === 0 && y%2 === 0) return // Don't flood fill through corners (what? Clarify.) + + if (y < this.height - 1) this._floodFillOutside(x, y + 1, col) + if (y > 0) this._floodFillOutside(x, y - 1, col) + if (x < this.width - 1) this._floodFillOutside(x + 1, y, this.grid[x+1]) + else if (this.pillar !== false) this._floodFillOutside(0, y, this.grid[0]) + if (x > 0) this._floodFillOutside(x - 1, y, this.grid[x-1]) + else if (this.pillar !== false) this._floodFillOutside(this.width-1, y, this.grid[this.width-1]) + } + + // Returns the original grid (pre-masking). You will need to switch back once you are done flood filling. + switchToMaskedGrid() { + // Make a copy of the grid -- we will be overwriting it + var savedGrid = this.grid + this.grid = new Array(this.width) + // Override all elements with empty lines -- this means that flood fill is just + // looking for lines with line=0. + for (var x=0; x window.LINE_NONE) { + row[y] = MASKED_PROCESSED // Traced lines should not be a part of the region + } else if (cell.gap === window.GAP_FULL) { + row[y] = MASKED_GAP2 + } else if (cell.dot > window.DOT_NONE) { + row[y] = MASKED_DOT + } else { + row[y] = MASKED_INB_COUNT + } + } + this.grid[x] = row + } + + // Starting at a mid-segment startpoint + if (this.startPoint != null && this.startPoint.x%2 !== this.startPoint.y%2) { + if (this.settings.FAT_STARTPOINTS) { + // This segment is not in any region (acts as a barrier) + this.grid[this.startPoint.x][this.startPoint.y] = MASKED_OOB + } else { + // This segment is part of this region (acts as an empty cell) + this.grid[this.startPoint.x][this.startPoint.y] = MASKED_INB_NONCOUNT + } + } + + // Ending at a mid-segment endpoint + if (this.endPoint != null && this.endPoint.x%2 !== this.endPoint.y%2) { + // This segment is part of this region (acts as an empty cell) + this.grid[this.endPoint.x][this.endPoint.y] = MASKED_INB_NONCOUNT + } + + // Mark all outside cells as 'not in any region' (aka null) + + // Top and bottom edges + for (var x=1; x 0) row[x] = ' ' + if (cell.dot > 0) row[x] = 'X' + if (cell.line === 0) row[x] = '.' + if (cell.line === 1) row[x] = '#' + if (cell.line === 2) row[x] = '#' + if (cell.line === 3) row[x] = 'o' + } else row[x] = '?' + } + output += row.join('') + '\n' + } + console.info(output) + } +} + +// The grid contains 5 colors: +// null: Out of bounds or already processed +var MASKED_OOB = null +var MASKED_PROCESSED = null +// 0: In bounds, awaiting processing, but should not be part of the final region. +var MASKED_INB_NONCOUNT = 0 +// 1: In bounds, awaiting processing +var MASKED_INB_COUNT = 1 +// 2: Gap-2. After _floodFillOutside, this means "treat normally" (it will be null if oob) +var MASKED_GAP2 = 2 +// 3: Dot (of any kind), otherwise identical to 1. Should not be flood-filled through (why the f do we need this) +var MASKED_DOT = 3 + +}) diff --git a/app/assets/javascripts/wittle/serializer.js b/app/assets/javascripts/wittle/serializer.js new file mode 100644 index 0000000..e440569 --- /dev/null +++ b/app/assets/javascripts/wittle/serializer.js @@ -0,0 +1,346 @@ +namespace(function() { + +window.serializePuzzle = function(puzzle) { + var s = new Serializer('w') + var version = 0 + + s.writeInt(version) + s.writeByte(puzzle.width) + s.writeByte(puzzle.height) + s.writeString(puzzle.name) + + var genericFlags = 0 + if (puzzle.autoSolved) genericFlags |= GENERIC_FLAG_AUTOSOLVED + if (puzzle.symmetry) { + genericFlags |= GENERIC_FLAG_SYMMETRICAL + if (puzzle.symmetry.x) genericFlags |= GENERIC_FLAG_SYMMETRY_X + if (puzzle.symmetry.y) genericFlags |= GENERIC_FLAG_SYMMETRY_Y + } + if (puzzle.pillar) genericFlags |= GENERIC_FLAG_PILLAR + s.writeByte(genericFlags) + for (var x=0; x 0) { + s.writeInt(puzzle.path.length) + s.writeByte(startPos.x) + s.writeByte(startPos.y) + for (var dir of puzzle.path) s.writeByte(dir) + } + } else { + s.writeInt(0) + } + + var settingsFlags = 0 + if (puzzle.settings.NEGATIONS_CANCEL_NEGATIONS) settingsFlags |= SETTINGS_FLAG_NCN + if (puzzle.settings.SHAPELESS_ZERO_POLY) settingsFlags |= SETTINGS_FLAG_SZP + if (puzzle.settings.PRECISE_POLYOMINOS) settingsFlags |= SETTINGS_FLAG_PP + if (puzzle.settings.FLASH_FOR_ERRORS) settingsFlags |= SETTINGS_FLAG_FFE + if (puzzle.settings.FAT_STARTPOINTS) settingsFlags |= SETTINGS_FLAG_FS + if (puzzle.settings.CUSTOM_MECHANICS) settingsFlags |= SETTINGS_FLAG_CM + s.writeByte(settingsFlags) + + return s.str() +} + +window.deserializePuzzle = function(data) { + // Data is JSON, so decode it with the old deserializer + if (data[0] == '{') return Puzzle.deserialize(data) + + var s = new Serializer('r', data) + var version = s.readInt() + if (version > 0) throw Error('Cannot read data from unknown version: ' + version) + + var width = s.readByte() + var height = s.readByte() + var puzzle = new Puzzle(Math.floor(width / 2), Math.floor(height / 2)) + puzzle.name = s.readString() + + var genericFlags = s.readByte() + puzzle.autoSolved = genericFlags & GENERIC_FLAG_AUTOSOLVED + if ((genericFlags & GENERIC_FLAG_SYMMETRICAL) != 0) { + puzzle.symmetry = { + 'x': ((genericFlags & GENERIC_FLAG_SYMMETRY_X) != 0), + 'y': ((genericFlags & GENERIC_FLAG_SYMMETRY_Y) != 0), + } + } + puzzle.pillar = (genericFlags & GENERIC_FLAG_PILLAR) != 0 + for (var x=0; x 0) { + var path = [{ + 'x': s.readByte(), + 'y': s.readByte(), + }] + for (var i=0; i 0xFF) throw Error('Cannot write out-of-range byte ' + b) + this.data += String.fromCharCode(b) + } + + readInt() { + var b1 = this.readByte() << 0 + var b2 = this.readByte() << 8 + var b3 = this.readByte() << 16 + var b4 = this.readByte() << 24 + return b1 | b2 | b3 | b4 + } + + writeInt(i) { + if (i < 0 || i > 0xFFFFFFFF) throw Error('Cannot write out-of-range int ' + i) + var b1 = (i & 0x000000FF) >> 0 + var b2 = (i & 0x0000FF00) >> 8 + var b3 = (i & 0x00FF0000) >> 16 + var b4 = (i & 0xFF000000) >> 24 + this.writeByte(b1) + this.writeByte(b2) + this.writeByte(b3) + this.writeByte(b4) + } + + readLong() { + var i1 = this.readInt() << 32 + var i2 = this.readInt() + return i1 | i2 + } + + writeLong(l) { + if (l < 0 || l > 0xFFFFFFFFFFFFFFFF) throw Error('Cannot write out-of-range long ' + l) + var i1 = l & 0xFFFFFFFF + var i2 = (l - i1) / 0x100000000 + this.writeInt(i1) + this.writeInt(i2) + } + + readString() { + var len = this.readInt() + this._checkRead(len) + var str = this.data.substr(this.index, len) + this.index += len + return str + } + + writeString(s) { + if (s == null) { + this.writeInt(0) + return + } + this.writeInt(s.length) + this.data += s + } + + readColor() { + var r = this.readByte().toString() + var g = this.readByte().toString() + var b = this.readByte().toString() + var a = this.readByte().toString() + return 'rgba(' + r + ', ' + g + ', ' + b + ', ' + a + ')' + } + + writeColor(c) { + // Adapted from https://gist.github.com/njvack/02ad8efcb0d552b0230d + this.colorConverter.fillStyle = 'rgba(0, 0, 0, 0)' // Load a default in case we are passed garbage + this.colorConverter.clearRect(0, 0, 1, 1) + this.colorConverter.fillStyle = c + this.colorConverter.fillRect(0, 0, 1, 1) + var rgba = this.colorConverter.getImageData(0, 0, 1, 1).data + this.writeByte(rgba[0]) + this.writeByte(rgba[1]) + this.writeByte(rgba[2]) + this.writeByte(rgba[3]) + } + + readCell() { + var cellType = this.readByte() + if (cellType === CELL_TYPE_NULL) return null + + var cell = {} + cell.dir = null + cell.line = 0 + if (cellType === CELL_TYPE_LINE) { + cell.type = 'line' + cell.line = this.readByte() + var dot = this.readByte() + if (dot != 0) cell.dot = dot + var gap = this.readByte() + if (gap != 0) cell.gap = gap + } else if (cellType === CELL_TYPE_SQUARE) { + cell.type = 'square' + cell.color = this.readColor() + } else if (cellType === CELL_TYPE_STAR) { + cell.type = 'star' + cell.color = this.readColor() + } else if (cellType === CELL_TYPE_NEGA) { + cell.type = 'nega' + cell.color = this.readColor() + } else if (cellType === CELL_TYPE_TRIANGLE) { + cell.type = 'triangle' + cell.color = this.readColor() + cell.count = this.readByte() + } else if (cellType === CELL_TYPE_POLY) { + cell.type = 'poly' + cell.color = this.readColor() + cell.polyshape = this.readLong() + } else if (cellType === CELL_TYPE_YLOP) { + cell.type = 'ylop' + cell.color = this.readColor() + cell.polyshape = this.readLong() + } else if (cellType == CELL_TYPE_NONCE) { + cell.type = 'nonce' + } + + var startEnd = this.readByte() + if (startEnd & CELL_START) cell.start = true + if (startEnd & CELL_END_LEFT) cell.end = 'left' + if (startEnd & CELL_END_RIGHT) cell.end = 'right' + if (startEnd & CELL_END_TOP) cell.end = 'top' + if (startEnd & CELL_END_BOTTOM) cell.end = 'bottom' + + return cell + } + + + writeCell(cell) { + if (cell == null) { + this.writeByte(CELL_TYPE_NULL) + return + } + + // Write cell type, then cell data, then generic data. + // Note that cell type starts at 1, since 0 is the "null type". + if (cell.type == 'line') { + this.writeByte(CELL_TYPE_LINE) + this.writeByte(cell.line) + this.writeByte(cell.dot) + this.writeByte(cell.gap) + } else if (cell.type == 'square') { + this.writeByte(CELL_TYPE_SQUARE) + this.writeColor(cell.color) + } else if (cell.type == 'star') { + this.writeByte(CELL_TYPE_STAR) + this.writeColor(cell.color) + } else if (cell.type == 'nega') { + this.writeByte(CELL_TYPE_NEGA) + this.writeColor(cell.color) + } else if (cell.type == 'triangle') { + this.writeByte(CELL_TYPE_TRIANGLE) + this.writeColor(cell.color) + this.writeByte(cell.count) + } else if (cell.type == 'poly') { + this.writeByte(CELL_TYPE_POLY) + this.writeColor(cell.color) + this.writeLong(cell.polyshape) + } else if (cell.type == 'ylop') { + this.writeByte(CELL_TYPE_YLOP) + this.writeColor(cell.color) + this.writeLong(cell.polyshape) + } + + var startEnd = 0 + if (cell.start === true) startEnd |= CELL_START + if (cell.end == 'left') startEnd |= CELL_END_LEFT + if (cell.end == 'right') startEnd |= CELL_END_RIGHT + if (cell.end == 'top') startEnd |= CELL_END_TOP + if (cell.end == 'bottom') startEnd |= CELL_END_BOTTOM + this.writeByte(startEnd) + } +} + +var CELL_TYPE_NULL = 0 +var CELL_TYPE_LINE = 1 +var CELL_TYPE_SQUARE = 2 +var CELL_TYPE_STAR = 3 +var CELL_TYPE_NEGA = 4 +var CELL_TYPE_TRIANGLE = 5 +var CELL_TYPE_POLY = 6 +var CELL_TYPE_YLOP = 7 +var CELL_TYPE_NONCE = 8 + +var CELL_START = 1 +var CELL_END_LEFT = 2 +var CELL_END_RIGHT = 4 +var CELL_END_TOP = 8 +var CELL_END_BOTTOM = 16 + +var GENERIC_FLAG_AUTOSOLVED = 1 +var GENERIC_FLAG_SYMMETRICAL = 2 +var GENERIC_FLAG_SYMMETRY_X = 4 +var GENERIC_FLAG_SYMMETRY_Y = 8 +var GENERIC_FLAG_PILLAR = 16 + +var SETTINGS_FLAG_NCN = 1 +var SETTINGS_FLAG_SZP = 2 +var SETTINGS_FLAG_PP = 4 +var SETTINGS_FLAG_FFE = 8 +var SETTINGS_FLAG_FS = 16 +var SETTINGS_FLAG_CM = 32 + +}) diff --git a/app/assets/javascripts/wittle/solve.js b/app/assets/javascripts/wittle/solve.js new file mode 100644 index 0000000..13b9650 --- /dev/null +++ b/app/assets/javascripts/wittle/solve.js @@ -0,0 +1,531 @@ +namespace(function() { + +// @Volatile -- must match order of MOVE_* in trace2 +// Move these, dummy. +var PATH_NONE = 0 +var PATH_LEFT = 1 +var PATH_RIGHT = 2 +var PATH_TOP = 3 +var PATH_BOTTOM = 4 + +window.MAX_SOLUTIONS = 0 +var solutionPaths = [] +var asyncTimer = 0 +var task = null +var puzzle = null +var path = [] +var SOLVE_SYNC = false +var SYNC_THRESHOLD = 9 // Depth at which we switch to a synchronous solver (for perf) +var doPruning = false + +var percentages = [] +var NODE_DEPTH = 9 +var nodes = 0 +function countNodes(x, y, depth) { + // Check for collisions (outside, gap, self, other) + var cell = puzzle.getCell(x, y) + if (cell == null) return + if (cell.gap > window.GAP_NONE) return + if (cell.line !== window.LINE_NONE) return + + if (puzzle.symmetry == null) { + puzzle.updateCell2(x, y, 'line', window.LINE_BLACK) + } else { + var sym = puzzle.getSymmetricalPos(x, y) + if (puzzle.matchesSymmetricalPos(x, y, sym.x, sym.y)) return // Would collide with our reflection + + var symCell = puzzle.getCell(sym.x, sym.y) + if (symCell.gap > window.GAP_NONE) return + + puzzle.updateCell2(x, y, 'line', window.LINE_BLUE) + puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW) + } + + if (depth < NODE_DEPTH) { + nodes++ + + if (y%2 === 0) { + countNodes(x - 1, y, depth + 1) + countNodes(x + 1, y, depth + 1) + } + + if (x%2 === 0) { + countNodes(x, y - 1, depth + 1) + countNodes(x, y + 1, depth + 1) + } + } + + tailRecurse(x, y) +} + +// Generates a solution via DFS recursive backtracking +window.solve = function(p, partialCallback, finalCallback) { + if (task != null) throw Error('Cannot start another solve() while one is already in progress') + var start = (new Date()).getTime() + + puzzle = p + var startPoints = [] + var numEndpoints = 0 + puzzle.hasNegations = false + puzzle.hasPolyominos = false + for (var x=0; x 0) { + // Tasks are pushed in order. To do DFS, we need to enqueue them in reverse order. + for (var i=newTasks.length - 1; i >= 0; i--) { + task = { + 'code': newTasks[i], + 'nextTask': task, + } + } + } + + // Asynchronizing is expensive. As such, we don't want to do it too often. + // However, we would like 'cancel solving' to be responsive. So, we call setTimeout every so often. + var doAsync = false + if (!SOLVE_SYNC) { + doAsync = (asyncTimer++ % 100 === 0) + while (nodes >= percentages[0]) { + if (partialCallback) partialCallback(100 - percentages.length) + percentages.shift() + doAsync = true + } + } + + if (doAsync) { + setTimeout(function() { + taskLoop(partialCallback, finalCallback) + }, 0) + } else { + taskLoop(partialCallback, finalCallback) + } +} + +function tailRecurse(x, y) { + // Tail recursion: Back out of this cell + puzzle.updateCell2(x, y, 'line', window.LINE_NONE) + if (puzzle.symmetry != null) { + var sym = puzzle.getSymmetricalPos(x, y) + puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_NONE) + } +} + +// @Performance: This is the most central loop in this code. +// Any performance efforts should be focused here. +// Note: Most mechanics are NP (or harder), so don't feel bad about solving them by brute force. +// https://arxiv.org/pdf/1804.10193.pdf +function solveLoop(x, y, numEndpoints, earlyExitData) { + // Stop trying to solve once we reach our goal + if (solutionPaths.length >= window.MAX_SOLUTIONS) return + + // Check for collisions (outside, gap, self, other) + var cell = puzzle.getCell(x, y) + if (cell == null) return + if (cell.gap > window.GAP_NONE) return + if (cell.line !== window.LINE_NONE) return + + if (puzzle.symmetry == null) { + puzzle.updateCell2(x, y, 'line', window.LINE_BLACK) + } else { + var sym = puzzle.getSymmetricalPos(x, y) + if (puzzle.matchesSymmetricalPos(x, y, sym.x, sym.y)) return // Would collide with our reflection + + var symCell = puzzle.getCell(sym.x, sym.y) + if (symCell.gap > window.GAP_NONE) return + + puzzle.updateCell2(x, y, 'line', window.LINE_BLUE) + puzzle.updateCell2(sym.x, sym.y, 'line', window.LINE_YELLOW) + } + + if (path.length < NODE_DEPTH) nodes++ + + if (cell.end != null) { + path.push(PATH_NONE) + puzzle.endPoint = {'x': x, 'y': y} + var puzzleData = window.validate(puzzle, true) + if (puzzleData.valid()) solutionPaths.push(path.slice()) + path.pop() + + // If there are no further endpoints, tail recurse. + // Otherwise, keep going -- we might be able to reach another endpoint. + numEndpoints-- + if (numEndpoints === 0) return tailRecurse(x, y) + } + + var newEarlyExitData = null + if (doPruning) { + var isEdge = x <= 0 || y <= 0 || x >= puzzle.width - 1 || y >= puzzle.height - 1 + newEarlyExitData = [ + earlyExitData[0] || (!isEdge && earlyExitData[2].isEdge), // Have we ever left an edge? + earlyExitData[2], // The position before our current one + {'x':x, 'y':y, 'isEdge':isEdge} // Our current position. + ] + if (earlyExitData[0] && !earlyExitData[1].isEdge && earlyExitData[2].isEdge && isEdge) { + // See the above comment for an explanation of this math. + var floodX = earlyExitData[2].x + (earlyExitData[1].x - x) + var floodY = earlyExitData[2].y + (earlyExitData[1].y - y) + var region = puzzle.getRegion(floodX, floodY) + if (region != null) { + var regionData = window.validateRegion(puzzle, region, true) + if (!regionData.valid()) return tailRecurse(x, y) + + // Additionally, we might have left an endpoint in the enclosed region. + // If so, we should decrement the number of remaining endpoints (and possibly tail recurse). + for (var pos of region) { + var endCell = puzzle.grid[pos.x][pos.y] + if (endCell != null && endCell.end != null) numEndpoints-- + } + + if (numEndpoints === 0) return tailRecurse(x, y) + } + } + } + + if (SOLVE_SYNC || path.length > SYNC_THRESHOLD) { + path.push(PATH_NONE) + + // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles + if (y%2 === 0) { + path[path.length-1] = PATH_LEFT + solveLoop(x - 1, y, numEndpoints, newEarlyExitData) + + path[path.length-1] = PATH_RIGHT + solveLoop(x + 1, y, numEndpoints, newEarlyExitData) + } + + if (x%2 === 0) { + path[path.length-1] = PATH_TOP + solveLoop(x, y - 1, numEndpoints, newEarlyExitData) + + path[path.length-1] = PATH_BOTTOM + solveLoop(x, y + 1, numEndpoints, newEarlyExitData) + } + + path.pop() + tailRecurse(x, y) + + } else { + // Push a dummy element on the end of the path, so that we can fill it correctly as we DFS. + // This element is popped when we tail recurse (which always happens *after* all of our DFS!) + path.push(PATH_NONE) + + // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles + var newTasks = [] + if (y%2 === 0) { + newTasks.push(function() { + path[path.length-1] = PATH_LEFT + return solveLoop(x - 1, y, numEndpoints, newEarlyExitData) + }) + newTasks.push(function() { + path[path.length-1] = PATH_RIGHT + return solveLoop(x + 1, y, numEndpoints, newEarlyExitData) + }) + } + + if (x%2 === 0) { + newTasks.push(function() { + path[path.length-1] = PATH_TOP + return solveLoop(x, y - 1, numEndpoints, newEarlyExitData) + }) + newTasks.push(function() { + path[path.length-1] = PATH_BOTTOM + return solveLoop(x, y + 1, numEndpoints, newEarlyExitData) + }) + } + + newTasks.push(function() { + path.pop() + tailRecurse(x, y) + }) + + return newTasks + } +} + +window.cancelSolving = function() { + console.info('Cancelled solving') + window.MAX_SOLUTIONS = 0 // Causes all new solveLoop calls to exit immediately. + tasks = [] +} + +// Only modifies the puzzle object (does not do any graphics updates). Used by metapuzzle.js to determine subpuzzle polyshapes. +window.drawPathNoUI = function(puzzle, path) { + puzzle.clearLines() + + // Extract the start data from the first path element + var x = path[0].x + var y = path[0].y + var cell = puzzle.getCell(x, y) + if (cell == null || cell.start !== true) throw Error('Path does not begin with a startpoint: ' + JSON.stringify(cell)) + + for (var i=1; i max ? max : value +} + +class BoundingBox { + constructor(x1, x2, y1, y2, sym=false) { + this.raw = {'x1':x1, 'x2':x2, 'y1':y1, 'y2':y2} + this.sym = sym + if (BBOX_DEBUG === true) { + this.debug = createElement('rect') + data.svg.appendChild(this.debug) + this.debug.setAttribute('opacity', 0.5) + this.debug.setAttribute('style', 'pointer-events: none;') + if (data.puzzle.symmetry == null) { + this.debug.setAttribute('fill', 'white') + } else { + if (this.sym !== true) { + this.debug.setAttribute('fill', 'blue') + } else { + this.debug.setAttribute('fill', 'orange') + } + } + } + this._update() + } + + shift(dir, pixels) { + if (dir === 'left') { + this.raw.x2 = this.raw.x1 + this.raw.x1 -= pixels + } else if (dir === 'right') { + this.raw.x1 = this.raw.x2 + this.raw.x2 += pixels + } else if (dir === 'top') { + this.raw.y2 = this.raw.y1 + this.raw.y1 -= pixels + } else if (dir === 'bottom') { + this.raw.y1 = this.raw.y2 + this.raw.y2 += pixels + } + this._update() + } + + inMain(x, y) { + var inMainBox = + (this.x1 < x && x < this.x2) && + (this.y1 < y && y < this.y2) + var inRawBox = + (this.raw.x1 < x && x < this.raw.x2) && + (this.raw.y1 < y && y < this.raw.y2) + + return inMainBox && !inRawBox + } + + _update() { + this.x1 = this.raw.x1 + this.x2 = this.raw.x2 + this.y1 = this.raw.y1 + this.y2 = this.raw.y2 + + // Check for endpoint adjustment + if (this.sym !== true) { + var cell = data.puzzle.getCell(data.pos.x, data.pos.y) + } else { + var cell = data.puzzle.getSymmetricalCell(data.sym.x, data.sym.y) + } + if (cell.end === 'left') { + this.x1 -= 24 + } else if (cell.end === 'right') { + this.x2 += 24 + } else if (cell.end === 'top') { + this.y1 -= 24 + } else if (cell.end === 'bottom') { + this.y2 += 24 + } + + this.middle = { // Note: Middle of the raw object + 'x':(this.raw.x1 + this.raw.x2)/2, + 'y':(this.raw.y1 + this.raw.y2)/2 + } + + if (this.debug != null) { + this.debug.setAttribute('x', this.x1) + this.debug.setAttribute('y', this.y1) + this.debug.setAttribute('width', this.x2 - this.x1) + this.debug.setAttribute('height', this.y2 - this.y1) + } + } +} + +class PathSegment { + constructor(dir) { + this.poly1 = createElement('polygon') + this.circ = createElement('circle') + this.poly2 = createElement('polygon') + this.pillarCirc = createElement('circle') + this.dir = dir + data.svg.insertBefore(this.circ, data.cursor) + data.svg.insertBefore(this.poly2, data.cursor) + data.svg.insertBefore(this.pillarCirc, data.cursor) + this.circ.setAttribute('cx', data.bbox.middle.x) + this.circ.setAttribute('cy', data.bbox.middle.y) + + if (data.puzzle.pillar === true) { + // cx/cy are updated in redraw(), since pillarCirc tracks the cursor + this.pillarCirc.setAttribute('cy', data.bbox.middle.y) + this.pillarCirc.setAttribute('r', 12) + if (data.pos.x === 0 && this.dir === MOVE_RIGHT) { + this.pillarCirc.setAttribute('cx', data.bbox.x1) + this.pillarCirc.setAttribute('static', true) + } else if (data.pos.x === data.puzzle.width - 1 && this.dir === MOVE_LEFT) { + this.pillarCirc.setAttribute('cx', data.bbox.x2) + this.pillarCirc.setAttribute('static', true) + } else { + this.pillarCirc.setAttribute('cx', data.bbox.middle.x) + } + } + + if (data.puzzle.symmetry == null) { + this.poly1.setAttribute('class', 'line-1 ' + data.svg.id) + this.circ.setAttribute('class', 'line-1 ' + data.svg.id) + this.poly2.setAttribute('class', 'line-1 ' + data.svg.id) + this.pillarCirc.setAttribute('class', 'line-1 ' + data.svg.id) + } else { + this.poly1.setAttribute('class', 'line-2 ' + data.svg.id) + this.circ.setAttribute('class', 'line-2 ' + data.svg.id) + this.poly2.setAttribute('class', 'line-2 ' + data.svg.id) + this.pillarCirc.setAttribute('class', 'line-2 ' + data.svg.id) + + this.symPoly1 = createElement('polygon') + this.symCirc = createElement('circle') + this.symPoly2 = createElement('polygon') + this.symPillarCirc = createElement('circle') + data.svg.insertBefore(this.symCirc, data.cursor) + data.svg.insertBefore(this.symPoly2, data.cursor) + data.svg.insertBefore(this.symPillarCirc, data.cursor) + this.symPoly1.setAttribute('class', 'line-3 ' + data.svg.id) + this.symCirc.setAttribute('class', 'line-3 ' + data.svg.id) + this.symPoly2.setAttribute('class', 'line-3 ' + data.svg.id) + this.symPillarCirc.setAttribute('class', 'line-3 ' + data.svg.id) + + this.symCirc.setAttribute('cx', data.symbbox.middle.x) + this.symCirc.setAttribute('cy', data.symbbox.middle.y) + + if (data.puzzle.pillar === true) { + // cx/cy are updated in redraw(), since symPillarCirc tracks the cursor + this.symPillarCirc.setAttribute('cy', data.symbbox.middle.y) + this.symPillarCirc.setAttribute('r', 12) + var symmetricalDir = getSymmetricalDir(data.puzzle, this.dir) + if (data.sym.x === 0 && symmetricalDir === MOVE_RIGHT) { + this.symPillarCirc.setAttribute('cx', data.symbbox.x1) + this.symPillarCirc.setAttribute('static', true) + } else if (data.sym.x === data.puzzle.width - 1 && symmetricalDir === MOVE_LEFT) { + this.symPillarCirc.setAttribute('cx', data.symbbox.x2) + this.symPillarCirc.setAttribute('static', true) + } else { + this.symPillarCirc.setAttribute('cx', data.symbbox.middle.x) + } + } + } + + if (this.dir === MOVE_NONE) { // Start point + this.circ.setAttribute('r', 24) + this.circ.setAttribute('class', this.circ.getAttribute('class') + ' start') + if (data.puzzle.symmetry != null) { + this.symCirc.setAttribute('r', 24) + this.symCirc.setAttribute('class', this.symCirc.getAttribute('class') + ' start') + } + } else { + // Only insert poly1 in non-startpoints + data.svg.insertBefore(this.poly1, data.cursor) + this.circ.setAttribute('r', 12) + if (data.puzzle.symmetry != null) { + data.svg.insertBefore(this.symPoly1, data.cursor) + this.symCirc.setAttribute('r', 12) + } + } + } + + destroy() { + data.svg.removeChild(this.poly1) + data.svg.removeChild(this.circ) + data.svg.removeChild(this.poly2) + data.svg.removeChild(this.pillarCirc) + if (data.puzzle.symmetry != null) { + data.svg.removeChild(this.symPoly1) + data.svg.removeChild(this.symCirc) + data.svg.removeChild(this.symPoly2) + data.svg.removeChild(this.symPillarCirc) + } + } + + redraw() { // Uses raw bbox because of endpoints + // Move the cursor and related objects + var x = clamp(data.x, data.bbox.x1, data.bbox.x2) + var y = clamp(data.y, data.bbox.y1, data.bbox.y2) + data.cursor.setAttribute('cx', x) + data.cursor.setAttribute('cy', y) + if (data.puzzle.symmetry != null) { + data.symcursor.setAttribute('cx', this._reflX(x)) + data.symcursor.setAttribute('cy', this._reflY(y)) + } + if (data.puzzle.pillar === true) { + if (this.pillarCirc.getAttribute('static') == null) { + this.pillarCirc.setAttribute('cx', x) + this.pillarCirc.setAttribute('cy', y) + } + if (data.puzzle.symmetry != null) { + if (this.symPillarCirc.getAttribute('static') == null) { + this.symPillarCirc.setAttribute('cx', this._reflX(x)) + this.symPillarCirc.setAttribute('cy', this._reflY(y)) + } + } + } + + // Draw the first-half box + var points1 = JSON.parse(JSON.stringify(data.bbox.raw)) + if (this.dir === MOVE_LEFT) { + points1.x1 = clamp(data.x, data.bbox.middle.x, data.bbox.x2) + } else if (this.dir === MOVE_RIGHT) { + points1.x2 = clamp(data.x, data.bbox.x1, data.bbox.middle.x) + } else if (this.dir === MOVE_TOP) { + points1.y1 = clamp(data.y, data.bbox.middle.y, data.bbox.y2) + } else if (this.dir === MOVE_BOTTOM) { + points1.y2 = clamp(data.y, data.bbox.y1, data.bbox.middle.y) + } + this.poly1.setAttribute('points', + points1.x1 + ' ' + points1.y1 + ',' + + points1.x1 + ' ' + points1.y2 + ',' + + points1.x2 + ' ' + points1.y2 + ',' + + points1.x2 + ' ' + points1.y1 + ) + + var firstHalf = false + var isEnd = (data.puzzle.grid[data.pos.x][data.pos.y].end != null) + // The second half of the line uses the raw so that it can enter the endpoint properly. + var points2 = JSON.parse(JSON.stringify(data.bbox.raw)) + if (data.x < data.bbox.middle.x && this.dir !== MOVE_RIGHT) { + points2.x1 = clamp(data.x, data.bbox.x1, data.bbox.middle.x) + points2.x2 = data.bbox.middle.x + if (isEnd && data.pos.x%2 === 0 && data.pos.y%2 === 1) { + points2.y1 += 17 + points2.y2 -= 17 + } + } else if (data.x > data.bbox.middle.x && this.dir !== MOVE_LEFT) { + points2.x1 = data.bbox.middle.x + points2.x2 = clamp(data.x, data.bbox.middle.x, data.bbox.x2) + if (isEnd && data.pos.x%2 === 0 && data.pos.y%2 === 1) { + points2.y1 += 17 + points2.y2 -= 17 + } + } else if (data.y < data.bbox.middle.y && this.dir !== MOVE_BOTTOM) { + points2.y1 = clamp(data.y, data.bbox.y1, data.bbox.middle.y) + points2.y2 = data.bbox.middle.y + if (isEnd && data.pos.x%2 === 1 && data.pos.y%2 === 0) { + points2.x1 += 17 + points2.x2 -= 17 + } + } else if (data.y > data.bbox.middle.y && this.dir !== MOVE_TOP) { + points2.y1 = data.bbox.middle.y + points2.y2 = clamp(data.y, data.bbox.middle.y, data.bbox.y2) + if (isEnd && data.pos.x%2 === 1 && data.pos.y%2 === 0) { + points2.x1 += 17 + points2.x2 -= 17 + } + } else { + firstHalf = true + } + + this.poly2.setAttribute('points', + points2.x1 + ' ' + points2.y1 + ',' + + points2.x1 + ' ' + points2.y2 + ',' + + points2.x2 + ' ' + points2.y2 + ',' + + points2.x2 + ' ' + points2.y1 + ) + + // Show the second poly only in the second half of the cell + this.poly2.setAttribute('opacity', (firstHalf ? 0 : 1)) + // Show the circle in the second half of the cell AND in the start + if (firstHalf && this.dir !== MOVE_NONE) { + this.circ.setAttribute('opacity', 0) + } else { + this.circ.setAttribute('opacity', 1) + } + + // Draw the symmetrical path based on the original one + if (data.puzzle.symmetry != null) { + this.symPoly1.setAttribute('points', + this._reflX(points1.x2) + ' ' + this._reflY(points1.y2) + ',' + + this._reflX(points1.x2) + ' ' + this._reflY(points1.y1) + ',' + + this._reflX(points1.x1) + ' ' + this._reflY(points1.y1) + ',' + + this._reflX(points1.x1) + ' ' + this._reflY(points1.y2) + ) + + this.symPoly2.setAttribute('points', + this._reflX(points2.x2) + ' ' + this._reflY(points2.y2) + ',' + + this._reflX(points2.x2) + ' ' + this._reflY(points2.y1) + ',' + + this._reflX(points2.x1) + ' ' + this._reflY(points2.y1) + ',' + + this._reflX(points2.x1) + ' ' + this._reflY(points2.y2) + ) + + this.symCirc.setAttribute('opacity', this.circ.getAttribute('opacity')) + this.symPoly2.setAttribute('opacity', this.poly2.getAttribute('opacity')) + } + } + + _reflX(x) { + if (data.puzzle.symmetry == null) return x + if (data.puzzle.symmetry.x === true) { + // Mirror position inside the bounding box + return (data.bbox.middle.x - x) + data.symbbox.middle.x + } + // Copy position inside the bounding box + return (x - data.bbox.middle.x) + data.symbbox.middle.x + } + + _reflY(y) { + if (data.puzzle.symmetry == null) return y + if (data.puzzle.symmetry.y === true) { + // Mirror position inside the bounding box + return (data.bbox.middle.y - y) + data.symbbox.middle.y + } + // Copy position inside the bounding box + return (y - data.bbox.middle.y) + data.symbbox.middle.y + } +} + +var data = {} + +function clearGrid(svg, puzzle) { + if (data.bbox != null && data.bbox.debug != null) { + data.svg.removeChild(data.bbox.debug) + data.bbox = null + } + if (data.symbbox != null && data.symbbox.debug != null) { + data.svg.removeChild(data.symbbox.debug) + data.symbbox = null + } + + window.deleteElementsByClassName(svg, 'cursor') + window.deleteElementsByClassName(svg, 'line-1') + window.deleteElementsByClassName(svg, 'line-2') + window.deleteElementsByClassName(svg, 'line-3') + puzzle.clearLines() +} + +// This copy is an exact copy of puzzle.getSymmetricalDir, except that it uses MOVE_* values instead of strings +function getSymmetricalDir(puzzle, dir) { + if (puzzle.symmetry != null) { + if (puzzle.symmetry.x === true) { + if (dir === MOVE_LEFT) return MOVE_RIGHT + if (dir === MOVE_RIGHT) return MOVE_LEFT + } + if (puzzle.symmetry.y === true) { + if (dir === MOVE_TOP) return MOVE_BOTTOM + if (dir === MOVE_BOTTOM) return MOVE_TOP + } + } + return dir +} + +window.trace = function(event, puzzle, pos, start, symStart=null) { + /*if (data.start == null) {*/ + if (data.tracing !== true) { // could be undefined or false + var svg = start.parentElement + data.tracing = true + window.PLAY_SOUND('start') + // Cleans drawn lines & puzzle state + clearGrid(svg, puzzle) + onTraceStart(puzzle, pos, svg, start, symStart) + data.animations.insertRule('.' + svg.id + '.start {animation: 150ms 1 forwards start-grow}\n') + + hookMovementEvents(start) + } else { + event.stopPropagation() + // Signal the onMouseMove to stop accepting input (race condition) + data.tracing = false + + // At endpoint and in main box + var cell = puzzle.getCell(data.pos.x, data.pos.y) + if (cell.end != null && data.bbox.inMain(data.x, data.y)) { + data.cursor.onpointerdown = null + setTimeout(function() { // Run validation asynchronously so we can free the pointer immediately. + puzzle.endPoint = data.pos + var puzzleData = window.validate(puzzle, false) // We want all invalid elements so we can show the user. + + for (var negation of puzzleData.negations) { + console.debug('Rendering negation', negation) + data.animations.insertRule('.' + data.svg.id + '_' + negation.source.x + '_' + negation.source.y + ' {animation: 0.75s 1 forwards fade}\n') + data.animations.insertRule('.' + data.svg.id + '_' + negation.target.x + '_' + negation.target.y + ' {animation: 0.75s 1 forwards fade}\n') + } + + if (puzzleData.valid()) { + window.PLAY_SOUND('success') + // !important to override the child animation + data.animations.insertRule('.' + data.svg.id + ' {animation: 1s 1 forwards line-success !important}\n') + + // Convert the traced path into something suitable for solve.drawPath (for publishing purposes) + var rawPath = [puzzle.startPoint] + for (var i=1; i 1) { + // Stop tracing for two+ finger touches (the equivalent of a right click on desktop) + window.trace(event, data.puzzle, null, null, null) + return + } + data.lastTouchPos = event.position + } + document.ontouchmove = function(event) { + if (data.tracing !== true) return + + var eventIsWithinPuzzle = false + for (var node = event.target; node != null; node = node.parentElement) { + if (node == data.svg) { + eventIsWithinPuzzle = true + break + } + } + if (!eventIsWithinPuzzle) return // Ignore drag events that aren't within the puzzle + event.preventDefault() // Prevent accidental scrolling if the touch event is within the puzzle. + + var newPos = event.position + onMove(newPos.x - data.lastTouchPos.x, newPos.y - data.lastTouchPos.y) + data.lastTouchPos = newPos + } + document.ontouchend = function(event) { + data.lastTouchPos = null + // Only call window.trace (to stop tracing) if we're really in an endpoint. + var cell = data.puzzle.getCell(data.pos.x, data.pos.y) + if (cell.end != null && data.bbox.inMain(data.x, data.y)) { + window.trace(event, data.puzzle, null, null, null) + } + } +} + +// @Volatile -- must match order of PATH_* in solve +var MOVE_NONE = 0 +var MOVE_LEFT = 1 +var MOVE_RIGHT = 2 +var MOVE_TOP = 3 +var MOVE_BOTTOM = 4 + +window.onMove = function(dx, dy) { + { + // Also handles some collision + var collidedWith = pushCursor(dx, dy) + console.spam('Collided with', collidedWith) + } + + while (true) { + hardCollision() + + // Potentially move the location to a new cell, and make absolute boundary checks + var moveDir = move() + data.path[data.path.length - 1].redraw() + if (moveDir === MOVE_NONE) break + console.debug('Moved', ['none', 'left', 'right', 'top', 'bottom'][moveDir]) + + // Potentially adjust data.x/data.y if our position went around a pillar + if (data.puzzle.pillar === true) pillarWrap(moveDir) + + var lastDir = data.path[data.path.length - 1].dir + var backedUp = ((moveDir === MOVE_LEFT && lastDir === MOVE_RIGHT) + || (moveDir === MOVE_RIGHT && lastDir === MOVE_LEFT) + || (moveDir === MOVE_TOP && lastDir === MOVE_BOTTOM) + || (moveDir === MOVE_BOTTOM && lastDir === MOVE_TOP)) + + if (data.puzzle.symmetry != null) { + var symMoveDir = getSymmetricalDir(data.puzzle, moveDir) + } + + // If we backed up, remove a path segment and mark the old cell as unvisited + if (backedUp) { + data.path.pop().destroy() + data.puzzle.updateCell2(data.pos.x, data.pos.y, 'line', window.LINE_NONE) + if (data.puzzle.symmetry != null) { + data.puzzle.updateCell2(data.sym.x, data.sym.y, 'line', window.LINE_NONE) + } + } + + // Move to the next cell + changePos(data.bbox, data.pos, moveDir) + if (data.puzzle.symmetry != null) { + changePos(data.symbbox, data.sym, symMoveDir) + } + + // If we didn't back up, add a path segment and mark the new cell as visited + if (!backedUp) { + data.path.push(new PathSegment(moveDir)) + if (data.puzzle.symmetry == null) { + data.puzzle.updateCell2(data.pos.x, data.pos.y, 'line', window.LINE_BLACK) + } else { + data.puzzle.updateCell2(data.pos.x, data.pos.y, 'line', window.LINE_BLUE) + data.puzzle.updateCell2(data.sym.x, data.sym.y, 'line', window.LINE_YELLOW) + } + } + } +} + +// Helper function for pushCursor. Used to determine the direction and magnitude of redirection. +function push(dx, dy, dir, targetDir) { + // Fraction of movement to redirect in the other direction + var movementRatio = null + if (targetDir === 'left' || targetDir === 'top') { + movementRatio = -3 + } else if (targetDir === 'right' || targetDir === 'bottom') { + movementRatio = 3 + } + if (window.settings.disablePushing === true) movementRatio *= 1000 + + if (dir === 'left') { + var overshoot = data.bbox.x1 - (data.x + dx) + 12 + if (overshoot > 0) { + data.y += dy + overshoot / movementRatio + data.x = data.bbox.x1 + 12 + return true + } + } else if (dir === 'right') { + var overshoot = (data.x + dx) - data.bbox.x2 + 12 + if (overshoot > 0) { + data.y += dy + overshoot / movementRatio + data.x = data.bbox.x2 - 12 + return true + } + } else if (dir === 'leftright') { + data.y += dy + Math.abs(dx) / movementRatio + return true + } else if (dir === 'top') { + var overshoot = data.bbox.y1 - (data.y + dy) + 12 + if (overshoot > 0) { + data.x += dx + overshoot / movementRatio + data.y = data.bbox.y1 + 12 + return true + } + } else if (dir === 'bottom') { + var overshoot = (data.y + dy) - data.bbox.y2 + 12 + if (overshoot > 0) { + data.x += dx + overshoot / movementRatio + data.y = data.bbox.y2 - 12 + return true + } + } else if (dir === 'topbottom') { + data.x += dx + Math.abs(dy) / movementRatio + return true + } + return false +} + +// Redirect momentum from pushing against walls, so that all further moment steps +// will be strictly linear. Returns a string for logging purposes only. +function pushCursor(dx, dy) { + // Outer wall collision + var cell = data.puzzle.getCell(data.pos.x, data.pos.y) + if (cell == null) return 'nothing' + + // Only consider non-endpoints or endpoints which are parallel + if ([undefined, 'top', 'bottom'].includes(cell.end)) { + var leftCell = data.puzzle.getCell(data.pos.x - 1, data.pos.y) + if (leftCell == null || leftCell.gap === window.GAP_FULL) { + if (push(dx, dy, 'left', 'top')) return 'left outer wall' + } + var rightCell = data.puzzle.getCell(data.pos.x + 1, data.pos.y) + if (rightCell == null || rightCell.gap === window.GAP_FULL) { + if (push(dx, dy, 'right', 'top')) return 'right outer wall' + } + } + // Only consider non-endpoints or endpoints which are parallel + if ([undefined, 'left', 'right'].includes(cell.end)) { + var topCell = data.puzzle.getCell(data.pos.x, data.pos.y - 1) + if (topCell == null || topCell.gap === window.GAP_FULL) { + if (push(dx, dy, 'top', 'right')) return 'top outer wall' + } + var bottomCell = data.puzzle.getCell(data.pos.x, data.pos.y + 1) + if (bottomCell == null || bottomCell.gap === window.GAP_FULL) { + if (push(dx, dy, 'bottom', 'right')) return 'bottom outer wall' + } + } + + // Inner wall collision + if (cell.end == null) { + if (data.pos.x%2 === 1 && data.pos.y%2 === 0) { // Horizontal cell + if (data.x < data.bbox.middle.x) { + push(dx, dy, 'topbottom', 'left') + return 'topbottom inner wall, moved left' + } else { + push(dx, dy, 'topbottom', 'right') + return 'topbottom inner wall, moved right' + } + } else if (data.pos.x%2 === 0 && data.pos.y%2 === 1) { // Vertical cell + if (data.y < data.bbox.middle.y) { + push(dx, dy, 'leftright', 'top') + return 'leftright inner wall, moved up' + } else { + push(dx, dy, 'leftright', 'bottom') + return 'leftright inner wall, moved down' + } + } + } + + // Intersection & endpoint collision + // Ratio of movement to be considered turning at an intersection + var turnMod = 2 + if ((data.pos.x%2 === 0 && data.pos.y%2 === 0) || cell.end != null) { + if (data.x < data.bbox.middle.x) { + push(dx, dy, 'topbottom', 'right') + // Overshot the intersection and appears to be trying to turn + if (data.x > data.bbox.middle.x && Math.abs(dy) * turnMod > Math.abs(dx)) { + data.y += Math.sign(dy) * (data.x - data.bbox.middle.x) + data.x = data.bbox.middle.x + return 'overshot moving right' + } + return 'intersection moving right' + } else if (data.x > data.bbox.middle.x) { + push(dx, dy, 'topbottom', 'left') + // Overshot the intersection and appears to be trying to turn + if (data.x < data.bbox.middle.x && Math.abs(dy) * turnMod > Math.abs(dx)) { + data.y += Math.sign(dy) * (data.bbox.middle.x - data.x) + data.x = data.bbox.middle.x + return 'overshot moving left' + } + return 'intersection moving left' + } + if (data.y < data.bbox.middle.y) { + push(dx, dy, 'leftright', 'bottom') + // Overshot the intersection and appears to be trying to turn + if (data.y > data.bbox.middle.y && Math.abs(dx) * turnMod > Math.abs(dy)) { + data.x += Math.sign(dx) * (data.y - data.bbox.middle.y) + data.y = data.bbox.middle.y + return 'overshot moving down' + } + return 'intersection moving down' + } else if (data.y > data.bbox.middle.y) { + push(dx, dy, 'leftright', 'top') + // Overshot the intersection and appears to be trying to turn + if (data.y < data.bbox.middle.y && Math.abs(dx) * turnMod > Math.abs(dy)) { + data.x += Math.sign(dx) * (data.bbox.middle.y - data.y) + data.y = data.bbox.middle.y + return 'overshot moving up' + } + return 'intersection moving up' + } + } + + // No collision, limit movement to X or Y only to prevent out-of-bounds + if (Math.abs(dx) > Math.abs(dy)) { + data.x += dx + return 'nothing, x' + } else { + data.y += dy + return 'nothing, y' + } +} + +// Check to see if we collided with any gaps, or with a symmetrical line, or a startpoint. +// In any case, abruptly zero momentum. +function hardCollision() { + var lastDir = data.path[data.path.length - 1].dir + var cell = data.puzzle.getCell(data.pos.x, data.pos.y) + if (cell == null) return + + var gapSize = 0 + if (cell.gap === window.GAP_BREAK) { + console.spam('Collided with a gap') + gapSize = 21 + } else { + var nextCell = null + if (lastDir === MOVE_LEFT) nextCell = data.puzzle.getCell(data.pos.x - 1, data.pos.y) + if (lastDir === MOVE_RIGHT) nextCell = data.puzzle.getCell(data.pos.x + 1, data.pos.y) + if (lastDir === MOVE_TOP) nextCell = data.puzzle.getCell(data.pos.x, data.pos.y - 1) + if (lastDir === MOVE_BOTTOM) nextCell = data.puzzle.getCell(data.pos.x, data.pos.y + 1) + if (nextCell != null && nextCell.start === true && nextCell.line > window.LINE_NONE) { + gapSize = -5 + } + } + + if (data.puzzle.symmetry != null) { + if (data.sym.x === data.pos.x && data.sym.y === data.pos.y) { + console.spam('Collided with our symmetrical line') + gapSize = 13 + } else if (data.puzzle.getCell(data.sym.x, data.sym.y).gap === window.GAP_BREAK) { + console.spam('Symmetrical line hit a gap') + gapSize = 21 + } + } + if (gapSize === 0) return // Didn't collide with anything + + if (lastDir === MOVE_LEFT) { + data.x = Math.max(data.bbox.middle.x + gapSize, data.x) + } else if (lastDir === MOVE_RIGHT) { + data.x = Math.min(data.x, data.bbox.middle.x - gapSize) + } else if (lastDir === MOVE_TOP) { + data.y = Math.max(data.bbox.middle.y + gapSize, data.y) + } else if (lastDir === MOVE_BOTTOM) { + data.y = Math.min(data.y, data.bbox.middle.y - gapSize) + } +} + +// Check to see if we've gone beyond the edge of puzzle cell, and if the next cell is safe, +// i.e. not out of bounds. Reports the direction we are going to move (or none), +// but does not actually change data.pos +function move() { + var lastDir = data.path[data.path.length - 1].dir + + if (data.x < data.bbox.x1 + 12) { // Moving left + var cell = data.puzzle.getCell(data.pos.x - 1, data.pos.y) + if (cell == null || cell.type !== 'line' || cell.gap === window.GAP_FULL) { + console.spam('Collided with outside / gap-2', cell) + data.x = data.bbox.x1 + 12 + } else if (cell.line > window.LINE_NONE && lastDir !== MOVE_RIGHT) { + console.spam('Collided with other line', cell.line) + data.x = data.bbox.x1 + 12 + } else if (data.puzzle.symmetry != null) { + var symCell = data.puzzle.getSymmetricalCell(data.pos.x - 1, data.pos.y) + if (symCell == null || symCell.type !== 'line' || symCell.gap === window.GAP_FULL) { + console.spam('Collided with symmetrical outside / gap-2', cell) + data.x = data.bbox.x1 + 12 + } + } + if (data.x < data.bbox.x1) { + return MOVE_LEFT + } + } else if (data.x > data.bbox.x2 - 12) { // Moving right + var cell = data.puzzle.getCell(data.pos.x + 1, data.pos.y) + if (cell == null || cell.type !== 'line' || cell.gap === window.GAP_FULL) { + console.spam('Collided with outside / gap-2', cell) + data.x = data.bbox.x2 - 12 + } else if (cell.line > window.LINE_NONE && lastDir !== MOVE_LEFT) { + console.spam('Collided with other line', cell.line) + data.x = data.bbox.x2 - 12 + } else if (data.puzzle.symmetry != null) { + var symCell = data.puzzle.getSymmetricalCell(data.pos.x + 1, data.pos.y) + if (symCell == null || symCell.type !== 'line' || symCell.gap === window.GAP_FULL) { + console.spam('Collided with symmetrical outside / gap-2', cell) + data.x = data.bbox.x2 - 12 + } + } + if (data.x > data.bbox.x2) { + return MOVE_RIGHT + } + } else if (data.y < data.bbox.y1 + 12) { // Moving up + var cell = data.puzzle.getCell(data.pos.x, data.pos.y - 1) + if (cell == null || cell.type !== 'line' || cell.gap === window.GAP_FULL) { + console.spam('Collided with outside / gap-2', cell) + data.y = data.bbox.y1 + 12 + } else if (cell.line > window.LINE_NONE && lastDir !== MOVE_BOTTOM) { + console.spam('Collided with other line', cell.line) + data.y = data.bbox.y1 + 12 + } else if (data.puzzle.symmetry != null) { + var symCell = data.puzzle.getSymmetricalCell(data.pos.x, data.pos.y - 1) + if (symCell == null || symCell.type !== 'line' || symCell.gap === window.GAP_FULL) { + console.spam('Collided with symmetrical outside / gap-2', cell) + data.y = data.bbox.y1 + 12 + } + } + if (data.y < data.bbox.y1) { + return MOVE_TOP + } + } else if (data.y > data.bbox.y2 - 12) { // Moving down + var cell = data.puzzle.getCell(data.pos.x, data.pos.y + 1) + if (cell == null || cell.type !== 'line' || cell.gap === window.GAP_FULL) { + console.spam('Collided with outside / gap-2') + data.y = data.bbox.y2 - 12 + } else if (cell.line > window.LINE_NONE && lastDir !== MOVE_TOP) { + console.spam('Collided with other line', cell.line) + data.y = data.bbox.y2 - 12 + } else if (data.puzzle.symmetry != null) { + var symCell = data.puzzle.getSymmetricalCell(data.pos.x, data.pos.y + 1) + if (symCell == null || symCell.type !== 'line' || symCell.gap === window.GAP_FULL) { + console.spam('Collided with symmetrical outside / gap-2', cell) + data.y = data.bbox.y2 - 12 + } + } + if (data.y > data.bbox.y2) { + return MOVE_BOTTOM + } + } + return MOVE_NONE +} + +// Check to see if you moved beyond the edge of a pillar. +// If so, wrap the cursor x to preserve momentum. +// Note that this still does not change the position. +function pillarWrap(moveDir) { + if (moveDir === MOVE_LEFT && data.pos.x === 0) { + data.x += data.puzzle.width * 41 + } + if (moveDir === MOVE_RIGHT && data.pos.x === data.puzzle.width - 1) { + data.x -= data.puzzle.width * 41 + } +} + +// Actually change the data position. (Note that this takes in pos to allow easier symmetry). +// Note that this doesn't zero the momentum, so that we can adjust appropriately on further loops. +// This function also shifts the bounding box that we use to determine the bounds of the cell. +function changePos(bbox, pos, moveDir) { + if (moveDir === MOVE_LEFT) { + pos.x-- + // Wrap around the left + if (data.puzzle.pillar === true && pos.x < 0) { + pos.x += data.puzzle.width + bbox.shift('right', data.puzzle.width * 41 - 82) + bbox.shift('right', 58) + } else { + bbox.shift('left', (pos.x%2 === 0 ? 24 : 58)) + } + } else if (moveDir === MOVE_RIGHT) { + pos.x++ + // Wrap around to the right + if (data.puzzle.pillar === true && pos.x >= data.puzzle.width) { + pos.x -= data.puzzle.width + bbox.shift('left', data.puzzle.width * 41 - 82) + bbox.shift('left', 24) + } else { + bbox.shift('right', (pos.x%2 === 0 ? 24 : 58)) + } + } else if (moveDir === MOVE_TOP) { + pos.y-- + bbox.shift('top', (pos.y%2 === 0 ? 24 : 58)) + } else if (moveDir === MOVE_BOTTOM) { + pos.y++ + bbox.shift('bottom', (pos.y%2 === 0 ? 24 : 58)) + } +} + +}) diff --git a/app/assets/javascripts/wittle/utilities.js.erb b/app/assets/javascripts/wittle/utilities.js.erb new file mode 100644 index 0000000..406adda --- /dev/null +++ b/app/assets/javascripts/wittle/utilities.js.erb @@ -0,0 +1,697 @@ +function namespace(code) { + code() +} + +namespace(function() { + +/*** Start cross-compatibility ***/ +// Used to detect if IDs include a direction, e.g. resize-top-left +if (!String.prototype.includes) { + String.prototype.includes = function() { + return String.prototype.indexOf.apply(this, arguments) !== -1 + } +} +Event.prototype.movementX = Event.prototype.movementX || Event.prototype.mozMovementX +Event.prototype.movementY = Event.prototype.movementY || Event.prototype.mozMovementY +Event.prototype.isRightClick = function() { + return this.which === 3 || (this.touches && this.touches.length > 1) +} +Element.prototype.disable = function() { + this.disabled = true + this.style.pointerEvents = 'none' + this.className = 'noselect' +} +Element.prototype.enable = function() { + this.disabled = false + this.style.pointerEvents = null + this.className = null +} +Object.defineProperty(Event.prototype, 'position', { + 'get': function() { + return { + 'x': event.pageX || event.clientX || (event.touches && event.touches[0].pageX) || null, + 'y': event.pageY || event.clientY || (event.touches && event.touches[0].pageY) || null, + } + } +}) +/*** End cross-compatibility ***/ + +var proxy = { + 'get': function(_, key) { + try { + return this._map[key] + } catch (e) { + return null + } + }, + 'set': function(_, key, value) { + if (value == null) { + delete this._map[key] + } else { + this._map[key] = value.toString() + window.localStorage.setItem('settings', JSON.stringify(this._map)) + } + }, + 'init': function() { + this._map = {} + try { + var j = window.localStorage.getItem('settings') + if (j != null) this._map = JSON.parse(j) + } catch (e) {/* Do nothing */} + + function setIfNull(map, key, value) { + if (map[key] == null) map[key] = value + } + + // Set any values which are not defined + setIfNull(this._map, 'theme', 'light') + setIfNull(this._map, 'volume', '0.12') + setIfNull(this._map, 'sensitivity', '0.7') + setIfNull(this._map, 'expanded', 'false') + setIfNull(this._map, 'customMechanics', 'false') + return this + }, +} +window.settings = new Proxy({}, proxy.init()) + +var tracks = { + 'start': new Audio(src = '<%= asset_url("wittle/panel_start_tracing.aac") %>'), + 'success': new Audio(src = '<%= asset_url("wittle/panel_success.aac") %>'), + 'fail': new Audio(src = '<%= asset_url("wittle/panel_failure.aac") %>'), + 'abort': new Audio(src = '<%= asset_url("wittle/panel_abort_tracing.aac") %>'), +} + +var currentAudio = null +window.PLAY_SOUND = function(name) { + if (currentAudio) currentAudio.pause() + var audio = tracks[name] + audio.load() + audio.volume = parseFloat(window.settings.volume) + audio.play().then(function() { + currentAudio = audio + }).catch(function() { + // Do nothing. + }) +} + +window.LINE_PRIMARY = '#8FF' +window.LINE_SECONDARY = '#FF2' + +if (window.settings.theme == 'night') { + window.BACKGROUND = '#221' + window.OUTER_BACKGROUND = '#070704' + window.FOREGROUND = '#751' + window.BORDER = '#666' + window.LINE_DEFAULT = '#888' + window.LINE_SUCCESS = '#BBB' + window.LINE_FAIL = '#000' + window.CURSOR = '#FFF' + window.TEXT_COLOR = '#AAA' + window.PAGE_BACKGROUND = '#000' + window.ALT_BACKGROUND = '#333' // An off-black. Good for mild contrast. + window.ACTIVE_COLOR = '#555' // Color for 'while the element is being pressed' +} else if (window.settings.theme == 'light') { + window.BACKGROUND = '#0A8' + window.OUTER_BACKGROUND = '#113833' + window.FOREGROUND = '#344' + window.BORDER = '#000' + window.LINE_DEFAULT = '#AAA' + window.LINE_SUCCESS = '#FFF' + window.LINE_FAIL = '#000' + window.CURSOR = '#FFF' + window.TEXT_COLOR = '#000' + window.PAGE_BACKGROUND = '#FFF' + window.ALT_BACKGROUND = '#EEE' // An off-white. Good for mild contrast. + window.ACTIVE_COLOR = '#DDD' // Color for 'while the element is being pressed' +} + +window.LINE_NONE = 0 +window.LINE_BLACK = 1 +window.LINE_BLUE = 2 +window.LINE_YELLOW = 3 +window.DOT_NONE = 0 +window.DOT_BLACK = 1 +window.DOT_BLUE = 2 +window.DOT_YELLOW = 3 +window.DOT_INVISIBLE = 4 +window.GAP_NONE = 0 +window.GAP_BREAK = 1 +window.GAP_FULL = 2 + +var animations = '' +var l = function(line) {animations += line + '\n'} +// pointer-events: none; allows for events to bubble up (so that editor hooks still work) +l('.line-1 {') +l(' fill: ' + window.LINE_DEFAULT + ';') +l(' pointer-events: none;') +l('}') +l('.line-2 {') +l(' fill: ' + window.LINE_PRIMARY + ';') +l(' pointer-events: none;') +l('}') +l('.line-3 {') +l(' fill: ' + window.LINE_SECONDARY + ';') +l(' pointer-events: none;') +l('}') +l('@keyframes line-success {to {fill: ' + window.LINE_SUCCESS + ';}}') +l('@keyframes line-fail {to {fill: ' + window.LINE_FAIL + ';}}') +l('@keyframes error {to {fill: red;}}') +l('@keyframes fade {to {opacity: 0.35;}}') +l('@keyframes start-grow {from {r:12;} to {r:24;}}') +// Neutral button style +l('button {') +l(' background-color: ' + window.ALT_BACKGROUND + ';') +l(' border: 1px solid ' + window.BORDER + ';') +l(' border-radius: 2px;') +l(' color: ' + window.TEXT_COLOR + ';') +l(' display: inline-block;') +l(' margin: 0px;') +l(' outline: none;') +l(' opacity: 1.0;') +l(' padding: 1px 6px;') +l(' -moz-appearance: none;') +l(' -webkit-appearance: none;') +l('}') +// Active (while held down) button style +l('button:active {background-color: ' + window.ACTIVE_COLOR + ';}') +// Disabled button style +l('button:disabled {opacity: 0.5;}') +// Selected button style (see https://stackoverflow.com/a/63108630) +l('button:focus {outline: none;}') +l = null + +var style = document.createElement('style') +style.type = 'text/css' +style.title = 'animations' +style.appendChild(document.createTextNode(animations)) +document.head.appendChild(style) + +// Custom logging to allow leveling +var consoleError = console.error +var consoleWarn = console.warn +var consoleInfo = console.log +var consoleLog = console.log +var consoleDebug = console.log +var consoleSpam = console.log +var consoleGroup = console.group +var consoleGroupEnd = console.groupEnd + +window.setLogLevel = function(level) { + console.error = function() {} + console.warn = function() {} + console.info = function() {} + console.log = function() {} + console.debug = function() {} + console.spam = function() {} + console.group = function() {} + console.groupEnd = function() {} + + if (level === 'none') return + + // Instead of throw, but still red flags and is easy to find + console.error = consoleError + if (level === 'error') return + + // Less serious than error, but flagged nonetheless + console.warn = consoleWarn + if (level === 'warn') return + + // Default visible, important information + console.info = consoleInfo + if (level === 'info') return + + // Useful for debugging (mainly validation) + console.log = consoleLog + if (level === 'log') return + + // Useful for serious debugging (mainly graphics/misc) + console.debug = consoleDebug + if (level === 'debug') return + + // Useful for insane debugging (mainly tracing/recursion) + console.spam = consoleSpam + console.group = consoleGroup + console.groupEnd = consoleGroupEnd + if (level === 'spam') return +} +setLogLevel('info') + +window.deleteElementsByClassName = function(rootElem, className) { + var elems = [] + while (true) { + elems = rootElem.getElementsByClassName(className) + if (elems.length === 0) break + elems[0].remove() + } +} + +window.loadHeader = function(titleText) { + document.body.style.marginLeft = '0px' + + var navbar = document.createElement('div') + document.body.appendChild(navbar) + navbar.className = 'navbar' + navbar.style = 'min-width: 700px; position: absolute; top: 0; width: 100%; z-index: 1' + navbar.style.borderBottom = '2px solid ' + window.BORDER + navbar.style.background = window.PAGE_BACKGROUND + + var navbarPadding = document.createElement('div') + document.body.appendChild(navbarPadding) + navbarPadding.className = 'navbar-padding' + + var titleDiv = document.createElement('div') + navbar.appendChild(titleDiv) + titleDiv.style = 'position: absolute; width: 100%; pointer-events: none' + + var titleLabel = document.createElement('label') + titleDiv.appendChild(titleLabel) + titleLabel.style = 'font-size: 48; pointer-events: auto' + titleLabel.id = 'title' + titleLabel.innerText = titleText + + var link = document.createElement('label') + navbar.appendChild(link) + link.style = 'float: left; margin-left: 32px; cursor: pointer; line-height: 60px' + link.className = 'navbar-content' + + if (window.location.href.endsWith('browse.html')) { + navbar.style.position = 'fixed' // When browsing, pin the navbar to the top so that it's visible during infinite scroll. + + link.innerText = 'Create a puzzle' + link.onpointerdown = function() {window.location = 'editor.html'} + + var link2 = document.createElement('label') + navbar.appendChild(link2) + link2.style = 'float: left; margin-left: 20px; cursor: pointer; line-height: 60px; display: none' + link2.className = 'navbar-content' + link2.innerText = 'Jump to top' + link2.id = 'scrollToTop' + link2.onpointerdown = function() {window.scrollTo(0, 0)} + + } else if (window.location.href.includes('/play/')) { + link.innerText = 'Back to all puzzles' + link.onpointerdown = function() {window.location = '../browse.html'} + } else /* All other pages */ { + link.innerText = 'Browse all puzzles' + link.onpointerdown = function() {window.location = 'browse.html'} + } + + var feedbackButton = document.createElement('label') + navbar.appendChild(feedbackButton) + feedbackButton.id = 'feedbackButton' + feedbackButton.style = 'float: right; margin-right: 8px; cursor: pointer; line-height: 60px' + feedbackButton.innerText = 'Send feedback' + feedbackButton.className = 'navbar-content' + feedbackButton.onpointerdown = function() { + var feedback = prompt('Provide feedback:') + if (feedback) { + sendFeedback(feedback) + } + } + + var separator = document.createElement('label') + navbar.appendChild(separator) + separator.style = 'float: right; line-height: 60px; padding-left: 6px; padding-right: 6px' + separator.className = 'navbar-content' + separator.innerText = '|' + + var sourceLink = document.createElement('label') + navbar.appendChild(sourceLink) + sourceLink.style = 'float: right; line-height: 60px; cursor: pointer' + sourceLink.innerText = 'Source code' + sourceLink.className = 'navbar-content' + sourceLink.onpointerdown = function() {window.open('https://github.com/jbzdarkid/jbzdarkid.github.io', '_blank')} + + var collapsedSettings = drawSymbol({'type': 'plus', 'width':20, 'height':20}) + navbar.appendChild(collapsedSettings) + collapsedSettings.style = 'width: 20px; height: 20px; position: absolute; left: 0; cursor: pointer' + collapsedSettings.style.border = '2px solid ' + window.BORDER + collapsedSettings.id = 'collapsedSettings' + collapsedSettings.onpointerdown = function() { + this.style.display = 'none' + var expandedSettings = document.getElementById('expandedSettings') + expandedSettings.style.display = null + window.settings.expanded = 'true' + } + + var expandedSettings = document.createElement('div') + navbar.appendChild(expandedSettings) + expandedSettings.style = 'width: 300px; position: absolute; left: 0; display: none; padding: 10px' + expandedSettings.style.border = '2px solid ' + window.BORDER + expandedSettings.style.background = window.PAGE_BACKGROUND + expandedSettings.id = 'expandedSettings' + + var minus = drawSymbol({'type':'minus', 'width':20, 'height':20}) + minus.style = 'width: 20px; height: 20px; cursor: pointer; position: absolute; top: 0; left: 0' + expandedSettings.appendChild(minus) + minus.onpointerdown = function() { + this.parentElement.style.display = 'none' + var collapsedSettings = document.getElementById('collapsedSettings') + collapsedSettings.style.display = null + window.settings.expanded = 'false' + } + + if (window.settings.expanded == 'true') { + collapsedSettings.onpointerdown() + } + + // Now, for the contents of the settings + var settingsLabel = document.createElement('label') + expandedSettings.appendChild(settingsLabel) + settingsLabel.innerText = 'settings' + settingsLabel.style = 'line-height: 0px' // Attach to the top + + expandedSettings.appendChild(document.createElement('br')) + expandedSettings.appendChild(document.createElement('br')) + + // Theme + document.body.style.color = window.TEXT_COLOR + document.body.style.background = window.PAGE_BACKGROUND + var themeButton = document.createElement('button') + expandedSettings.appendChild(themeButton) + if (window.settings.theme == 'night') { + themeButton.innerText = 'Night theme' + themeButton.onpointerdown = function() { + window.settings.theme = 'light' + location.reload() + } + } else if (window.settings.theme == 'light') { + themeButton.innerText = 'Light theme' + themeButton.onpointerdown = function() { + window.settings.theme = 'night' + location.reload() + } + } + + expandedSettings.appendChild(document.createElement('br')) + + // Sensitivity + var sensLabel = document.createElement('label') + expandedSettings.appendChild(sensLabel) + sensLabel.htmlFor = 'sens' + sensLabel.innerText = 'Mouse Speed 2D' + + var sens = document.createElement('input') + expandedSettings.appendChild(sens) + sens.type = 'range' + sens.id = 'sens' + sens.min = '0.1' + sens.max = '1.3' + sens.step = '0.1' + sens.value = window.settings.sensitivity + sens.onchange = function() { + window.settings.sensitivity = this.value + } + sens.style.backgroundImage = 'linear-gradient(to right, ' + window.ALT_BACKGROUND + ', ' + window.ACTIVE_COLOR + ')' + + // Volume + var volumeLabel = document.createElement('label') + expandedSettings.appendChild(volumeLabel) + volumeLabel.htmlFor = 'volume' + volumeLabel.innerText = 'Volume' + + var volume = document.createElement('input') + expandedSettings.appendChild(volume) + volume.type = 'range' + volume.id = 'volume' + volume.min = '0' + volume.max = '0.24' + volume.step = '0.02' + volume.value = parseFloat(window.settings.volume) + volume.onchange = function() { + window.settings.volume = this.value + } + volume.style.backgroundImage = 'linear-gradient(to right, ' + window.ALT_BACKGROUND + ', ' + window.ACTIVE_COLOR + ')' + + // Custom mechanics -- disabled for now + window.settings.customMechanics = false + /* + var customMechanics = createCheckbox() + expandedSettings.appendChild(customMechanics) + customMechanics.id = 'customMechanics' + if (window.settings.customMechanics == 'true') { + customMechanics.style.background = window.BORDER + customMechanics.checked = true + } + + customMechanics.onpointerdown = function() { + this.checked = !this.checked + this.style.background = (this.checked ? window.BORDER : window.PAGE_BACKGROUND) + window.settings.customMechanics = this.checked + window.location.reload() + } + + var mechLabel = document.createElement('label') + expandedSettings.appendChild(mechLabel) + mechLabel.style.marginLeft = '6px' + mechLabel.htmlFor = 'customMechanics' + mechLabel.innerText = 'Custom mechanics' + */ +} + +// Automatically solve the puzzle +window.solvePuzzle = function() { + if (window.setSolveMode) window.setSolveMode(false) + document.getElementById('solutionViewer').style.display = 'none' + document.getElementById('progressBox').style.display = null + document.getElementById('solveAuto').innerText = 'Cancel Solving' + document.getElementById('solveAuto').onpointerdown = function() { + this.innerText = 'Cancelling...' + this.onpointerdown = null + window.setTimeout(window.cancelSolving, 0) + } + + window.solve(window.puzzle, function(percent) { + document.getElementById('progressPercent').innerText = percent + '%' + document.getElementById('progress').style.width = percent + '%' + }, function(paths) { + document.getElementById('progressBox').style.display = 'none' + document.getElementById('solutionViewer').style.display = null + document.getElementById('progressPercent').innerText = '0%' + document.getElementById('progress').style.width = '0%' + document.getElementById('solveAuto').innerText = 'Solve (automatically)' + document.getElementById('solveAuto').onpointerdown = solvePuzzle + + window.puzzle.autoSolved = true + paths = window.onSolvedPuzzle(paths) + window.showSolution(window.puzzle, paths, 0) + }) +} + +window.showSolution = function(puzzle, paths, num, suffix) { + if (suffix == null) { + var previousSolution = document.getElementById('previousSolution') + var solutionCount = document.getElementById('solutionCount') + var nextSolution = document.getElementById('nextSolution') + } else if (suffix instanceof Array) { + var previousSolution = document.getElementById('previousSolution-' + suffix[0]) + var solutionCount = document.getElementById('solutionCount-' + suffix[0]) + var nextSolution = document.getElementById('nextSolution-' + suffix[0]) + } else { + var previousSolution = document.getElementById('previousSolution-' + suffix) + var solutionCount = document.getElementById('solutionCount-' + suffix) + var nextSolution = document.getElementById('nextSolution-' + suffix) + } + + if (paths.length === 0) { // 0 paths, arrows are useless + solutionCount.innerText = '0 of 0' + previousSolution.disable() + nextSolution.disable() + return + } + + while (num < 0) num = paths.length + num + while (num >= paths.length) num = num - paths.length + + if (paths.length === 1) { // 1 path, arrows are useless + solutionCount.innerText = '1 of 1' + if (paths.length >= window.MAX_SOLUTIONS) solutionCount.innerText += '+' + previousSolution.disable() + nextSolution.disable() + } else { + solutionCount.innerText = (num + 1) + ' of ' + paths.length + if (paths.length >= window.MAX_SOLUTIONS) solutionCount.innerText += '+' + previousSolution.enable() + nextSolution.enable() + previousSolution.onpointerdown = function(event) { + if (event.shiftKey) { + window.showSolution(puzzle, paths, num - 10, suffix) + } else { + window.showSolution(puzzle, paths, num - 1, suffix) + } + } + nextSolution.onpointerdown = function(event) { + if (event.shiftKey) { + window.showSolution(puzzle, paths, num + 10, suffix) + } else { + window.showSolution(puzzle, paths, num + 1, suffix) + } + } + } + + if (paths[num] != null) { + if (puzzle instanceof Array) { // Special case for multiple related panels + for (var i = 0; i < puzzle.length; i++) { + // Save the current path on the puzzle object (so that we can pass it along with publishing) + puzzle.path = paths[num][i] + // Draws the given path, and also updates the puzzle to have path annotations on it. + window.drawPath(puzzle[i], paths[num][i], suffix[i]) + } + } else { // Default case for a single panel + // Save the current path on the puzzle object (so that we can pass it along with publishing) + puzzle.path = paths[num] + // Draws the given path, and also updates the puzzle to have path annotations on it. + window.drawPath(puzzle, paths[num], suffix) + } + } +} + +window.createCheckbox = function() { + var checkbox = document.createElement('div') + checkbox.style.width = '22px' + checkbox.style.height = '22px' + checkbox.style.borderRadius = '6px' + checkbox.style.display = 'inline-block' + checkbox.style.verticalAlign = 'text-bottom' + checkbox.style.marginRight = '6px' + checkbox.style.borderWidth = '1.5px' + checkbox.style.borderStyle = 'solid' + checkbox.style.borderColor = window.BORDER + checkbox.style.background = window.PAGE_BACKGROUND + checkbox.style.color = window.TEXT_COLOR + return checkbox +} + +// Required global variables/functions: <-- HINT: This means you're writing bad code. +// window.puzzle +// window.onSolvedPuzzle() +// window.MAX_SOLUTIONS // defined by solve.js +window.addSolveButtons = function() { + var parent = document.currentScript.parentElement + + var solveMode = createCheckbox() + solveMode.id = 'solveMode' + parent.appendChild(solveMode) + + solveMode.onpointerdown = function() { + this.checked = !this.checked + this.style.background = (this.checked ? window.BORDER : window.PAGE_BACKGROUND) + document.getElementById('solutionViewer').style.display = 'none' + if (window.setSolveMode) window.setSolveMode(this.checked) + } + + var solveManual = document.createElement('label') + parent.appendChild(solveManual) + solveManual.id = 'solveManual' + solveManual.onpointerdown = function() {solveMode.onpointerdown()} + solveManual.innerText = 'Solve (manually)' + solveManual.style = 'margin-right: 8px' + + var solveAuto = document.createElement('button') + parent.appendChild(solveAuto) + solveAuto.id = 'solveAuto' + solveAuto.innerText = 'Solve (automatically)' + solveAuto.onpointerdown = solvePuzzle + solveAuto.style = 'margin-right: 8px' + + var div = document.createElement('div') + parent.appendChild(div) + div.style = 'display: inline-block; vertical-align:top' + + var progressBox = document.createElement('div') + div.appendChild(progressBox) + progressBox.id = 'progressBox' + progressBox.style = 'display: none; width: 220px; border: 1px solid black; margin-top: 2px' + + var progressPercent = document.createElement('label') + progressBox.appendChild(progressPercent) + progressPercent.id = 'progressPercent' + progressPercent.style = 'float: left; margin-left: 4px' + progressPercent.innerText = '0%' + + var progress = document.createElement('div') + progressBox.appendChild(progress) + progress.id = 'progress' + progress.style = 'z-index: -1; height: 38px; width: 0%; background-color: #390' + + var solutionViewer = document.createElement('div') + div.appendChild(solutionViewer) + solutionViewer.id = 'solutionViewer' + solutionViewer.style = 'display: none' + + var previousSolution = document.createElement('button') + solutionViewer.appendChild(previousSolution) + previousSolution.id = 'previousSolution' + previousSolution.innerHTML = '←' + + var solutionCount = document.createElement('label') + solutionViewer.appendChild(solutionCount) + solutionCount.id = 'solutionCount' + solutionCount.style = 'padding: 6px' + + var nextSolution = document.createElement('button') + solutionViewer.appendChild(nextSolution) + nextSolution.id = 'nextSolution' + nextSolution.innerHTML = '→' +} + +var SECONDS_PER_LOOP = 1 +window.httpGetLoop = function(url, maxTimeout, action, onError, onSuccess) { + if (maxTimeout <= 0) { + onError() + return + } + + sendHttpRequest('GET', url, SECONDS_PER_LOOP, null, function(httpCode, response) { + if (httpCode >= 200 && httpCode <= 299) { + var output = action(JSON.parse(response)) + if (output) { + onSuccess(output) + return + } // Retry if action returns null + } // Retry on non-success HTTP codes + + window.setTimeout(function() { + httpGetLoop(url, maxTimeout - SECONDS_PER_LOOP, action, onError, onSuccess) + }, 1000) + }) +} + +window.fireAndForget = function(verb, url, body) { + sendHttpRequest(verb, url, 600, body, function() {}) +} + +// Only used for errors +var HTTP_STATUS = { + 401: '401 unauthorized', 403: '403 forbidden', 404: '404 not found', 409: '409 conflict', 413: '413 payload too large', + 500: '500 internal server error', +} + +var etagCache = {} +function sendHttpRequest(verb, url, timeoutSeconds, data, onResponse) { + currentHttpRequest = new XMLHttpRequest() + currentHttpRequest.onreadystatechange = function() { + if (this.readyState != XMLHttpRequest.DONE) return + etagCache[url] = this.getResponseHeader('ETag') + currentHttpRequest = null + onResponse(this.status, this.responseText || HTTP_STATUS[this.status]) + } + currentHttpRequest.ontimeout = function() { + currentHttpRequest = null + onResponse(0, 'Request timed out') + } + currentHttpRequest.timeout = timeoutSeconds * 1000 + currentHttpRequest.open(verb, url, true) + currentHttpRequest.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded') + + var etag = etagCache[url] + if (etag != null) currentHttpRequest.setRequestHeader('If-None-Match', etag) + + currentHttpRequest.send(data) +} + +function sendFeedback(feedback) { + console.error('Please disregard the following CORS exception. It is expected and the request will succeed regardless.') +} + +}) diff --git a/app/assets/javascripts/wittle/validate.js b/app/assets/javascripts/wittle/validate.js new file mode 100644 index 0000000..333d2e1 --- /dev/null +++ b/app/assets/javascripts/wittle/validate.js @@ -0,0 +1,391 @@ +namespace(function() { + +class RegionData { + constructor() { + this.invalidElements = [] + this.veryInvalidElements = [] + this.negations = [] + } + + addInvalid(elem) { + this.invalidElements.push(elem) + } + + addVeryInvalid(elem) { + this.veryInvalidElements.push(elem) + } + + valid() { + return (this.invalidElements.length === 0 && this.veryInvalidElements.length === 0) + } +} + +// Sanity checks for data which comes from the user. Now that people have learned that /publish is an open endpoint, +// we have to make sure they don't submit data which passes validation but is untrustworthy. +// These checks should always pass for puzzles created by the built-in editor. +window.validateUserData = function(puzzle, path) { + if (path == null) throw Error('Path cannot be null') + + var sizeError = puzzle.getSizeError(puzzle.width, puzzle.height) + if (sizeError != null) throw Error(sizeError) + + var puzzleHasStart = false + var puzzleHasEnd = false + + if (puzzle.grid.length !== puzzle.width) throw Error('Puzzle width does not match grid size') + for (var x=0; x window.LINE_NONE) { + if (cell.gap > window.GAP_NONE) { + console.log('Solution line goes over a gap at', x, y) + puzzleData.invalidElements.push({'x': x, 'y': y}) + if (quick) return puzzleData + } + if ((cell.dot === window.DOT_BLUE && cell.line === window.LINE_YELLOW) || + (cell.dot === window.DOT_YELLOW && cell.line === window.LINE_BLUE)) { + console.log('Incorrectly covered dot: Dot is', cell.dot, 'but line is', cell.line) + puzzleData.invalidElements.push({'x': x, 'y': y}) + if (quick) return puzzleData + } + } + } + } + + if (needsRegions) { + var regions = puzzle.getRegions() + } else { + var monoRegion = [] + for (var x=0; x 0 && veryInvalidElements.length > 0) { + var source = negationSymbols.pop() + var target = veryInvalidElements.pop() + puzzle.setCell(source.x, source.y, null) + puzzle.setCell(target.x, target.y, null) + baseCombination.push({'source':source, 'target':target}) + } + + var regionData = regionCheckNegations2(puzzle, region, negationSymbols, invalidElements) + + // Restore required negations + for (var combination of baseCombination) { + puzzle.setCell(combination.source.x, combination.source.y, combination.source.cell) + puzzle.setCell(combination.target.x, combination.target.y, combination.target.cell) + regionData.negations.push(combination) + } + return regionData +} + +// Recursively matches negations and invalid elements from the grid. Note that this function +// doesn't actually modify the two lists, it just iterates through them with index/index2. +function regionCheckNegations2(puzzle, region, negationSymbols, invalidElements, index=0, index2=0) { + if (index2 >= negationSymbols.length) { + console.debug('0 negation symbols left, returning negation-less regionCheck') + return regionCheck(puzzle, region, false) // @Performance: We could pass quick here. + } + + if (index >= invalidElements.length) { + var i = index2 + // pair off all negation symbols, 2 at a time + if (puzzle.settings.NEGATIONS_CANCEL_NEGATIONS) { + for (; i window.DOT_NONE) { + console.log('Dot at', pos.x, pos.y, 'is not covered') + regionData.addVeryInvalid(pos) + if (quick) return regionData + } + + // Check for triangles + if (cell.type === 'triangle') { + var count = 0 + if (puzzle.getLine(pos.x - 1, pos.y) > window.LINE_NONE) count++ + if (puzzle.getLine(pos.x + 1, pos.y) > window.LINE_NONE) count++ + if (puzzle.getLine(pos.x, pos.y - 1) > window.LINE_NONE) count++ + if (puzzle.getLine(pos.x, pos.y + 1) > window.LINE_NONE) count++ + if (cell.count !== count) { + console.log('Triangle at grid['+pos.x+']['+pos.y+'] has', count, 'borders') + regionData.addVeryInvalid(pos) + if (quick) return regionData + } + } + + // Count color-based elements + if (cell.color != null) { + var count = coloredObjects[cell.color] + if (count == null) { + count = 0 + } + coloredObjects[cell.color] = count + 1 + + if (cell.type === 'square') { + squares.push(pos) + if (squareColor == null) { + squareColor = cell.color + } else if (squareColor != cell.color) { + squareColor = -1 // Signal value which indicates square color collision + } + } + + if (cell.type === 'star') { + pos.color = cell.color + stars.push(pos) + } + } + } + + if (squareColor === -1) { + regionData.invalidElements = regionData.invalidElements.concat(squares) + if (quick) return regionData + } + + for (var star of stars) { + var count = coloredObjects[star.color] + if (count === 1) { + console.log('Found a', star.color, 'star in a region with 1', star.color, 'object') + regionData.addVeryInvalid(star) + if (quick) return regionData + } else if (count > 2) { + console.log('Found a', star.color, 'star in a region with', count, star.color, 'objects') + regionData.addInvalid(star) + if (quick) return regionData + } + } + + if (puzzle.hasPolyominos) { + if (!window.polyFit(region, puzzle)) { + for (var pos of region) { + var cell = puzzle.grid[pos.x][pos.y] + if (cell == null) continue + if (cell.type === 'poly' || cell.type === 'ylop') { + regionData.addInvalid(pos) + if (quick) return regionData + } + } + } + } + + if (puzzle.settings.CUSTOM_MECHANICS) { + window.validateBridges(puzzle, region, regionData) + window.validateArrows(puzzle, region, regionData) + window.validateSizers(puzzle, region, regionData) + } + + console.debug('Region has', regionData.veryInvalidElements.length, 'very invalid elements') + console.debug('Region has', regionData.invalidElements.length, 'invalid elements') + return regionData +} +}) -- cgit 1.4.1