I was enjoying reading an article from Quantum Magazine “Is it Turtles all the way down?” and noted (under Puzzle 2) John Von Neumann’s 1949 “middle square” method for calculating pseudo random numbers from a seed. The method takes a seed number with an even number of digits, squares the number and returns the middle four digits which can also be used as the next seed value.
The algorithm has several flaws though, as it can get stuck (if all of the middle digits are zero and can return quite short cycles of values depending upon the initial seed. The saving grace is that the flaws are obvious when they show up.
I was thinking about random numbers in JavaScript and their application in JavaScript games and ended up looking at a very interesting set of answers on StackOverflow.
I rather liked one of the simpler solutions (from Remco Kranenburg and Antti Kissaniemi) that made it easy to run multiple independent random number sequences – partly because it only contained a single “magic number”.
How does the function rand1() (or rand2()) keep supplying new values? The newly created method Math.seed() defines and returns a function that encloses and keeps safe the value s ready to be used on each subsequent call. Of course, each call changes the value of s ready for it to be used to generate the next pseudo random number. This is not completely dissimilar to JVN’s methodology and makes neat use of a JavaScript closure.
Seed: 1027
Squared: 1054729
Add leading zero if less than 8 digits: 01054927
Return: 0549
Next: 3014, 0841 etc.
The algorithm has several flaws though, as it can get stuck (if all of the middle digits are zero and can return quite short cycles of values depending upon the initial seed. The saving grace is that the flaws are obvious when they show up.
I was thinking about random numbers in JavaScript and their application in JavaScript games and ended up looking at a very interesting set of answers on StackOverflow.
I rather liked one of the simpler solutions (from Remco Kranenburg and Antti Kissaniemi) that made it easy to run multiple independent random number sequences – partly because it only contained a single “magic number”.
Math.seed = function(s) {
return function() {
s =
Math.sin(s) * 10000;
return s - Math.floor(s);
};
};
var rand1 = Math.seed(26);
var rand2 = Math.seed(rand1());
var ret1 = [], ret2 =
[];
for(let i = 0; i < 10; i++) {
ret1.push(rand1());
ret2.push(rand2());
}
alert(ret1.join('\n'));
alert(ret2.join('\n'));
How does the function rand1() (or rand2()) keep supplying new values? The newly created method Math.seed() defines and returns a function that encloses and keeps safe the value s ready to be used on each subsequent call. Of course, each call changes the value of s ready for it to be used to generate the next pseudo random number. This is not completely dissimilar to JVN’s methodology and makes neat use of a JavaScript closure.
If you start again with the same seed value (example above was 26) then you will get the same sequence of values and a repeatable sequence is sometimes just what you want. If you want a (just about) unique sequence then you could use the value returned by Date.now() as a seed.
All of the related posts on StackOverflow are worth your attention if you have an interest in the topic.
I was also thinking about generating mazes which was why I
was thinking about a pseudo random number generator that could take a seed
value. There are many good maze generating algorithms and this GitHubrepository has some interesting examples and a web page link to try them out.
My stab at this takes a very simple algorithm based upon a grid of closed cells. It starts from a random location within that grid and then looks around to locate up to four adjoining cells (up, down, left and right) that are within the grid and which have not yet been visited by the process. A random cell from that group is then selected to be the next cell and the walls between the two cells are removed. From time to time, there will be no valid cell to move to and so the process backs up to find a cell from which progress can be made. When all of the cells have been visited (and connected) then the process is complete.
The demo starts with some HTML:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible">
<title>Amazed</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" type="text/css" media="screen" href="main.css" />
</head>
<body>
<div id="dvViewer">
<canvas id="cvView"></canvas>
</div>
<script src="main.js"></script>
</body>
</html>
Minimalist CSS
html { padding: 0; margin: 0; border: 0;}
The JavaScript file starts with that pseudo random number generator and some objects:
Math.seed = function(s) {
return function() {
s = Math.sin(s) * 10000;
return s - Math.floor(s);
};
};
const dir = Object.freeze({"up": 1, "down":2, "left": 3,"right" : 4});
var maze = {
cellsWide: 25,
cellsHigh: 25,
side: 10,
wallWidth: 2,
wallColour: "black",
cellColour: "white",
map: [],
rand: Math.seed(Date.now())
};
var view = {
canvas: null,
ctx: null
};
var Cell = function(x, y){
this.up = this.down = this.left = this.right = 1;
this.x = x;
this.y = y;
this.visited = false;
};
[I suspect that some of the members of the maze object should be in the view object but thats how it started out.]
At the bottom of the JavaScript there is a call to an initialise() function to set up the canvas object.
function initialise() {
view.canvas = document.getElementById("cvView");
view.ctx = view.canvas.getContext("2d");
view.canvas.width = maze.cellsWide * (maze.side + maze.wallWidth) + maze.wallWidth;
view.canvas.height = maze.cellsHigh * (maze.side + maze.wallWidth) + maze.wallWidth;
buildMaze();
renderView();
}
initialise();
The initialise() function calls buildMaze() to do just that and then renderView() to draw the result.
function buildMaze() {
for(let i = 0; i < maze.cellsHigh; i++){
maze.map.push([]);
for(let j = 0; j < maze.cellsWide; j++){
maze.map[i].push(new Cell(j,i));
}
}
let totalCells = maze.cellsWide * maze.cellsHigh;
let current = maze.rand() * totalCells; // random cell
current = maze.map[Math.floor(current / maze.cellsWide)][Math.floor(current % maze.cellsHigh)];
current.visited = true; let walk = [current]; let visited = 1; while(visited < totalCells){ let possibles = [[current.y-1, current.x, dir.up], [current.y+1, current.x, dir.down], [current.y, current.x-1, dir.left], [current.y, current.x+1, dir.right]]; let valid = []; for(let i = 0; i < 4; i++){ if(maze.map[possibles[i][0]] !== undefined && maze.map[possibles[i][0]][possibles[i][1]] !== undefined && !maze.map[possibles[i][0]][possibles[i][1]].visited){ valid.push(possibles[i]); // unvisited valid cell } } if(valid.length){ let next = valid[Math.floor(maze.rand() * valid.length)]; let nextCell = maze.map[next[0]][next[1]]; // remove wall between current and next cell switch(next[2]){ case dir.up: current.up = 0; nextCell.down = 0; break; case dir.down: current.down = 0; nextCell.up = 0; break; case dir.left: current.left = 0; nextCell.right = 0; break; case dir.right: current.right = 0; nextCell.left = 0; break; } current = nextCell; current.visited = true; walk.push(current); visited++; } else { current = walk.pop(); // no way forward so go back and try again } } }
The code could be more succinct but I hope that this version is clear and easy to follow.
That function is usually very fast but on occasion takes a couple of seconds to complete the path from the random start location to the final cell.
The (slightly imperfect) rendering follows:
My recent book "Learn To Program, with Games and JavaScript" uses a grid of cells forming a game "world" for a First person Shooter
game project using ray casting. One variant might be to create a maze of walls for the player to navigate. The book project output includes a map
and it could be a nice idea to hide the players location until he/she finds a particular artifact and then to only reveal the player's path from that point
onward. Coding a complex maze would be something of a trial so perhaps we can add some code to generate a suitable array representing the maze.
Suitable code can be found in the next post on this blog.
current.visited = true; let walk = [current]; let visited = 1; while(visited < totalCells){ let possibles = [[current.y-1, current.x, dir.up], [current.y+1, current.x, dir.down], [current.y, current.x-1, dir.left], [current.y, current.x+1, dir.right]]; let valid = []; for(let i = 0; i < 4; i++){ if(maze.map[possibles[i][0]] !== undefined && maze.map[possibles[i][0]][possibles[i][1]] !== undefined && !maze.map[possibles[i][0]][possibles[i][1]].visited){ valid.push(possibles[i]); // unvisited valid cell } } if(valid.length){ let next = valid[Math.floor(maze.rand() * valid.length)]; let nextCell = maze.map[next[0]][next[1]]; // remove wall between current and next cell switch(next[2]){ case dir.up: current.up = 0; nextCell.down = 0; break; case dir.down: current.down = 0; nextCell.up = 0; break; case dir.left: current.left = 0; nextCell.right = 0; break; case dir.right: current.right = 0; nextCell.left = 0; break; } current = nextCell; current.visited = true; walk.push(current); visited++; } else { current = walk.pop(); // no way forward so go back and try again } } }
The code could be more succinct but I hope that this version is clear and easy to follow.
That function is usually very fast but on occasion takes a couple of seconds to complete the path from the random start location to the final cell.
The (slightly imperfect) rendering follows:
function renderView(){
view.ctx.fillStyle = maze.cellColour;
view.ctx.fillRect(0,0,view.canvas.width, view.canvas.height);
view.ctx.strokeStyle = maze.wallColour;
view.ctx.lineWidth = maze.wallWidth;
let lineLength = maze.side + maze.wallWidth, adj = maze.wallWidth/2;
for(let i = 0; i < maze.cellsHigh; i++){
let y = i * lineLength + adj;
for(let j = 0; j < maze.cellsWide; j++){
let x = j * lineLength + adj;
if(maze.map[i][j].up){
view.ctx.moveTo(x, y);
view.ctx.lineTo(x+lineLength,y);
view.ctx.stroke();
}
if(maze.map[i][j].down){
view.ctx.moveTo(x, y+lineLength);
view.ctx.lineTo(x+lineLength,y+lineLength);
view.ctx.stroke();
}
if(maze.map[i][j].left){
view.ctx.moveTo(x, y);
view.ctx.lineTo(x,y+lineLength);
view.ctx.stroke();
}
if(maze.map[i][j].right){
view.ctx.moveTo(x+lineLength,y);
view.ctx.lineTo(x+lineLength,y+lineLength);
view.ctx.stroke();
}
}
}
}
And, of course, you can keep reloading the page until you get one you particularly like.
My recent book "Learn To Program, with Games and JavaScript" uses a grid of cells forming a game "world" for a First person Shooter
game project using ray casting. One variant might be to create a maze of walls for the player to navigate. The book project output includes a map
and it could be a nice idea to hide the players location until he/she finds a particular artifact and then to only reveal the player's path from that point
onward. Coding a complex maze would be something of a trial so perhaps we can add some code to generate a suitable array representing the maze.
Suitable code can be found in the next post on this blog.
nice alternate algorithm for pseudo random numbers from Stack Exchange. Allows a repeatable sequence (using the same seed) if required.
ReplyDelete// the initial seed
Math.seed = 6;
// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
max = max || 1;
min = min || 0;
Math.seed = (Math.seed * 9301 + 49297) % 233280;
var rnd = Math.seed / 233280;
return min + rnd * (max - min);
}