From c8b8770f49883f94678f215b98ece3d67f8aa9ef Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Mon, 24 Oct 2016 15:05:46 -0600 Subject: Mainly just lots and lots of comments. --- js/lost.js | 305 +++++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 246 insertions(+), 59 deletions(-) (limited to 'js/lost.js') diff --git a/js/lost.js b/js/lost.js index 20311f2..022c10b 100644 --- a/js/lost.js +++ b/js/lost.js @@ -5,27 +5,94 @@ // Helper functions // +// Return the id for the opposite direction of the direction given. +function oppositeDir( iDir ) +{ + if( iDir%2 === 1 ) + return iDir-1; + return iDir+1; +} + +// +// Create a new button element using the dom that has the given label, +// and calls the movePlayer method on the given map, along the provided +// dimension, and in the specified direction. +// +// The button created is then returned. +// +function createMoveButton( rMap, iDim, iDir, sLabel ) +{ + let btn = document.createElement('button'); + btn.addEventListener( + 'click', + Map.prototype.movePlayer.bind( + rMap, + iDim, + iDir + ) + ); + if( sLabel === null || sLabel === '' ) + { + btn.appendChild( + document.createTextNode('Dim ' + (j+1) + ': -') + ); + } + else + { + btn.appendChild( + document.createTextNode( sLabel ) + ); + } + return btn; +} + // // Class: RandomLcg // +// This implements a Linear Congruential Generator PRNG. Is this the best PRNG? +// Nope! Is it decently random for our purposes, sure. +// +// Why was this implemented? I wanted to be able to share mazes, in order to do +// that we needed two things that we can't get from JS by default: +// 1. To be able to set the seed (and get it if possible). +// 2. To be sure that the same algorithm would be used on every version of +// every browser. +// +// Unfortunately JavaScript doesn't gurantee either of these things, so instead +// of writing a CMWC and using a bunch of memory I just used the settings from +// the glibc random function and here we are. +// function RandomLcg() { + // Current state this.iState = 0; + + // Initial seed, remember this so we can display it easily later. this.iSeed = 0; + // Set the seed randomly to start. this.inventSeed(); } +// +// Replace the current seed and reset the state. +// RandomLcg.prototype.setSeed = function setSeed( iSeed ) { this.iState = this.iSeed = iSeed; } +// +// Get the seed that was initially used on this random number generator. +// RandomLcg.prototype.getSeed = function getSeed() { return this.iSeed; } +// +// Make up a seed. +// RandomLcg.prototype.inventSeed = function inventSeed() { // Based on my reading it's safest to assume that we can get 16 bits worth @@ -37,48 +104,52 @@ RandomLcg.prototype.inventSeed = function inventSeed() ); } +// +// Get us a random number between 0 and 1.0, exclusive of the upper bound. +// RandomLcg.prototype.random = function random() { this.iState = ((this.iState * 1103515245) + 12345) & 0x7fffffff; return this.iState/(0x7fffffff+1); } +// +// Get us a random integer between 0 and max, exclusive of the upper bound. +// RandomLcg.prototype.randInt = function randInt( max ) { return Math.floor(this.random() * max); } +// Lets just build a shared prng object to use all over. let lRand = new RandomLcg(); -// Just return a random integer between 0 and max, exclusive on the upper bound. -function randInt( max ) -{ - return lRand.randInt( max ); -// return Math.floor(Math.random() * max); -} - -// Return the id for the opposite direction of the direction given. -function oppositeDir( iDir ) -{ - if( iDir%2 === 1 ) - return iDir-1; - return iDir+1; -} - // // Class: Signal // +// Super simple implementation of a signal/slot concept. I didn't need most of +// the features, so this just lets us connect 0-parameter functions and call +// them en-masse whenever the signal is fired. +// function Signal() { this.aSlot = new Array(); } +// +// Connect this signal to a new slot (function to call). I recommend using bind +// to create valid object-function references that have state supposed to +// disembodied functions. +// Signal.prototype.connect = function connect( fSlot ) { this.aSlot.push( fSlot ); } -Signal.prototype.call = function call() +// +// Trigger the signal, and notify all slots bound to this signal. +// +Signal.prototype.emit = function emit() { for( let j = 0; j < this.aSlot.length; j++ ) { @@ -89,6 +160,8 @@ Signal.prototype.call = function call() // // Class: Cell // +// Simple container that tracks info about a cell in the maze. +// function Cell() { this.iDist = 0; @@ -99,6 +172,9 @@ function Cell() // // Class: Position // +// A simple class that keeps track of coordinates in N-dimensional space. +// That's really just an array of numbers with N spaces in it. +// function Position( iDims, ...Vals ) { if( typeof iDims === 'string' ) @@ -146,27 +222,45 @@ function Position( iDims, ...Vals ) } } +// +// Get the number of dimensions defined in this position. +// Position.prototype.getDims = function getDims() { return this.iDims; } +// +// Get the value of one dimension of the coordinate in this position. +// Position.prototype.get = function get( iDim ) { return this.aiValues[iDim]; } +// +// Set the value of one dimension of the coordinate in this position. +// This modifies the position in place. +// Position.prototype.set = function set( iDim, iVal ) { this.aiValues[iDim] = iVal; } +// +// Apply a delta to the specified dimension in the current position. +// This modifies the position in place. +// Position.prototype.add = function add( iDim, iDelta ) { this.aiValues[iDim] += iDelta; return this.aiValues[iDim]; } +// +// Copy the current position object and return one with a modified value in +// the specified dimension. +// Position.prototype.translate = function translate( iDim, iDelta ) { let tmp = new Position( this.iDims, ...this.aiValues.slice() ); @@ -174,11 +268,18 @@ Position.prototype.translate = function translate( iDim, iDelta ) return tmp; } +// +// Return an exact copy of this position object. +// Position.prototype.copy = function translate() { return new Position( this.iDims, ...this.aiValues.slice() ); } +// +// Compare two position objects for equality. Return true if they are the same, +// false otherwise. +// Position.prototype.equals = function equals( rhs ) { if( this.iDims != rhs.iDims && @@ -194,6 +295,9 @@ Position.prototype.equals = function equals( rhs ) return true; } +// +// Converts the position to a nicely formatted string of numbers. +// Position.prototype.toString = function toString() { let ret = this.aiValues[0].toString(); @@ -208,6 +312,10 @@ Position.prototype.toString = function toString() // // Class: Map // +// The maze itself. This doesn't do a whole lot on it's own except track data +// and manage the player position and worms. The worms do the real work of +// generating a maze. +// function Map( Dimensions ) { // Store dimensional data @@ -234,27 +342,44 @@ function Map( Dimensions ) } } +// +// Get the number of dimensions in this maze. +// Map.prototype.getDims = function getDims() { return this.Dimensions.getDims(); } +// +// Get the size of the specified dimension. +// Map.prototype.getSize = function getSize( iDim ) { return this.Dimensions.get( iDim ); } +// +// Get a reference to the current player position in the maze. +// Map.prototype.getPlayerPos = function getPlayerPos() { return this.pPlayer; } +// +// Replace the player position with a new position. +// Map.prototype.setPlayerPos = function setPlayerPos( pNewPos ) { this.pPlayer = pNewPos; - this.ePlayerMoved.call(); + this.ePlayerMoved.emit(); } +// +// Move the player the specified amount (iDelta) along the specified dimension +// (iDim). This takes walls and maze borders into account, and will not move +// the player in an "illegal" way. +// Map.prototype.movePlayer = function movePlayer( iDim, iDelta ) { let cCur = this.get( this.pPlayer ); @@ -271,14 +396,17 @@ Map.prototype.movePlayer = function movePlayer( iDim, iDelta ) return; this.pPlayer.add( iDim, iDelta ); - this.ePlayerMoved.call(); + this.ePlayerMoved.emit(); if( this.pPlayer.equals( this.pGoal ) ) { - this.eVictory.call(); + this.eVictory.emit(); } } +// +// Helper that determines if the provided position is inside the maze or not. +// Map.prototype.isInside = function isInside( Position ) { if( Position.getDims() != this.Dimensions.getDims() ) @@ -299,6 +427,12 @@ Map.prototype.isInside = function isInside( Position ) return true; } +// +// Internal helper function. This converts from a Position object to an array +// index, effectively flattening an arbitrarily dimensional coordinate into a +// one dimensional array coordinate. This is used to find the actual storage +// location of cells internally. +// Map.prototype.getIndex = function getIndex( Position ) { if( !this.isInside( Position ) ) @@ -316,17 +450,25 @@ Map.prototype.getIndex = function getIndex( Position ) return iIdx; } +// +// Get a cell at the given Position. +// Map.prototype.get = function get( Position ) { return this.aCell[this.getIndex( Position )]; } +// +// Create a new worm and add it to the maze. Specify the starting position +// and the loop chance (betweer 0.0 and 1.0). This returns the ID that the +// added worm was assigned, which starts at one and goes up from there. +// Map.prototype.addWorm = function addWorm( pStart, dLoopChance ) { if( this.pPlayer === null ) { this.pPlayer = pStart; - this.ePlayerSetup.call(); + this.ePlayerSetup.emit(); } else if( this.pGoal === null ) { @@ -344,6 +486,13 @@ Map.prototype.addWorm = function addWorm( pStart, dLoopChance ) return iNewId; } +// +// Worker function. This calls the timestep funcion on each worm until they +// report that they are done working and have exhausted all possible moves. +// +// At the moment this function assumes we have 2 worms and connects them +// automatically once it's done running. +// Map.prototype.buildMaze = function buildMaze() { do @@ -360,6 +509,13 @@ Map.prototype.buildMaze = function buildMaze() this.connect( 1, 2 ); } +// +// Connect the pathways created by two worms, specified by iWormId1 and +// iWormId2 to each other. this searches all walls in the maze and looks for +// a wall that seperates the path created by these two worms, then finds the +// wall that seperates the longest combined pathway between the two, and opens +// it up into a pathway. +// Map.prototype.connect = function connect( iWormId1, iWormId2 ) { let p = new Position( this.getDims() ); @@ -432,6 +588,8 @@ Map.prototype.connect = function connect( iWormId1, iWormId2 ) // // Class: Vector // +// Simple helper class that stores a position and direction. +// function Vector( pPos, iDir ) { this.pPos = pPos; @@ -441,6 +599,26 @@ function Vector( pPos, iDir ) // // Class: Worm // +// The main workhorse (workworm?) of maze generation. The worm "eats" a path +// through the maze. The basic algorithm works as follows: +// 1. Search all directions around the current cell and list all unvisited +// cells, the previous cell that we came from, and all cells that we +// created but are seperated from our current position by a wall. +// 2. If there are open cells, then we'll select one at random and travel to +// it, but first: +// 2.a. If there are adjacent cells that we created, generate a random +// number and compare it to the loop threshold. If it's smaller, +// then select an adjacent room at random and break through the wall +// to that room. +// 3. If there are not open cells then travel back to the previous cell that +// we came from. Start over from #1 in this cell. +// 4. If we reach the starting position again, then bailout and consider our +// work done. +// Every cell that a worm visits is marked with the worm's id (1 or greater), +// and a distance value that increases by one for each cell away from the start +// that we've traveled. When backtracking we update our current distance so +// that all distances are contiguous and increasing away from start. +// function Worm( iId, pStart, rMap, dLoopChance ) { // Initialize basic state, we start with distance set to 1 @@ -470,11 +648,14 @@ function Worm( iId, pStart, rMap, dLoopChance ) if( iDirs.length > 0 ) { // We are near a wall, pick a random wall to open a hole in - this.rMap.get(this.pPosition).iWalls |= iDirs[randInt(iDirs.length)]; + this.rMap.get(this.pPosition).iWalls |= iDirs[lRand.randInt(iDirs.length)]; this.rMap.get(this.pPosition).iPath = this.iId; } } +// +// Perform one step as descirbed in the constructor. +// Worm.prototype.timestep = function timestep() { // Handy to reference how many dimensions we have @@ -553,7 +734,7 @@ Worm.prototype.timestep = function timestep() } cCur = this.rMap.get( this.pPosition ); - let iSel = randInt( pDirs.length ); + let iSel = lRand.randInt( pDirs.length ); cCur.iWalls |= (1< 0 && lRand.random() <= this.dLoopChance ) { - iSel = pLoopDirs[randInt( pLoopDirs.length )]; + iSel = pLoopDirs[lRand.randInt( pLoopDirs.length )]; cCur.iWalls |= (1<