Large Maze Support
Okay, this has started to turn into a bit of an obsession. While making human-scale mazes was fine, generating ones that push the browser to its limits proved to require extensive rework of the code. The fundamental issue with the more basic code is that it absorbed all the resources of the browser and provided no feedback as to where it was in the generation process. Worse yet, browsers such as Firefox pop up modal dialog boxes warning that the script is unresponsive.
The current code is now limited only by the browser’s memory which allows for mazes on the scale of half a million cells or more—say 2500 rows by 200 columns on a reasonable-sized system.
Generator: here. Updated source: here.
The solution is to yield time back to the processor which is tricky with JavaScript since it doesn’t directly support such a mechanism universally. This required replacing the row and column iterators with a generalized loop counter with Continuation-passing style (CPS) support.
function iter(f, done, fc, fp)
{
var max = 50; // a reasonable number
var count = 0;
/* a functor that manages calls to f() */
var loop = function (state)
{
while((state = f(state)) != done) {
if (count < max) {
count++;
}
else {
count = 0;
setTimeout(function() {loop(state)}, 0);
break;
}
}
if(fp) {
fp(state, done);
}
if(fc && (state == done)) {
setTimeout(function() {fc()}, 0);
}
}
/* call the loop function with the initial state */
loop(0);
}
The above code calls a function f(i) until it returns a result that indicates processing is complete. The value “state” passed to f() is the result of the previous call to f(). Every “max” iterations, processing is yielded to allow responsiveness.
- f
- a function that takes a state parameter and returns an updated state
- done
- the final state that indicates that iteration is complete
- fc
- an optional continuation function that is called when processing is complete
- fp
- an optional callback function used to indicate progress though the iteration
related: http://www.mazeworks.com/mazegen/index.htm
» Posted by Anonymous on August 25, 2008 11:24 AM