Welcome back to my blog series on implementing procedurally-generated map compasses! In the last posting, I started implementation of Lodestone, a tool to execute procedural generation grammars. So far I have designed the rule language and implemented a parser that outputs a dictionary of rules. In this posting I'll develop the code to execute the rules and create procedural output.
First, let me quickly review how a procedural generation grammar works and outline the algorithm for executing the rules. A grammar is a collection of rules which have non-terminals on their left-hand sides and an expansion on their right-hand sides:
<name> => <lost> <coast> <coast> => coast | shore | banks <lost> => lost | forgotten | accursed
So in this example, if we start from “<name>" the first rule would expand that into “<lost> <coast>" and the next two rules would expand <lost> and <coast> into a word choice, so we might end up with "Accursed Shore."
That explanation provides a general notion of the rule expansion algorithm, but let me describe it in more detailed terms before getting to the code.
The algorithm begins with the start non-terminal in a stack. The (basic) algorithm then loops repeatedly over the following steps until the stack is empty:
- Pop the top element of the stack.
- If it's a non-terminal, find a rule that matches and push the right-hand side of the rule onto the stack.
- If it's something else, add it to the end of the output.
You can try this out in your head with the example above. Note that this algorithm works from left to right, always expanding the left-most terminal and building the output from left-to-right as well.
The way the Lodestone dictionary is constructed, there is always only one rule that will match a non-terminal. But the rule can have multiple choices on the right-hand side, so we need a step to select the right-hand side choice.
- Pop the top element of the stack
- If it's a non-terminal, find a rule that matches and:
- Randomly select one of the right-hand side choices for this rule
- Push the selected choice onto the stack
- If it's something else, add it to the end of the output
By the time the rules are being executed, there are only two other elements that are non-terminals: strings and embedded Javascript. For a string, the action is to push it onto the output. For a Javascript element, we need to execute it:
- Pop the top element of the stack.
- If it's a non-terminal, find a rule that matches and:
- Randomly select one of the right-hand side choices for this rule
- Push the selected choice onto the stack
- If it's embedded Javascript, then:
- Recursively expand the element
- Execute the expanded element in Javascript
- Add the return value to the end of the output
- If it's a string, add it to the end of the output.
Note that an embedded Javascript element can itself look like the right-hand side of a rule, using non-terminals and choices and so on, so we need to recursively run it through the same algorithm to get it down to a string that can be executed.
There are a couple of other nuances. First, one-time non-terminals should only be expanded once. We'll do this before starting the algorithm, and then use that value when we encounter a one-time non-terminal:
Pre: Iterate through the dictionary, expand all one-time non-terminals and save their values.
- Pop the top element of the stack.
- If it's a one-time non-terminal, add it's value to the end of the output.
- If it's a non-terminal, find a rule that matches and:
- Randomly select one of the right-hand side choices for this rule
- Push the selected choice onto the stack
- If it's embedded Javascript, then:
- Recursively expand the element
- Execute the expanded element in Javascript
- Add the return value to the end of the output
- If it's a string, add it to the end of the output.
The last nuance has to do with selecting a right-hand side choice. This is done according to the relative weights of the choices. But weights (like embedded Javascript) can have values that look like the right-hand side of a rule. So to evaluate weights, we'll have to recursively run them through the expansion algorithm just as we do for Javascript.
Pre: Iterate through the dictionary, expand all one-time non-terminals and save their values.
- Pop the top element of the stack.
- If it's a one-time non-terminal, add it's value to the end of the output.
- If it's a non-terminal, find a rule that matches and:
- Recursively expand all the choice weights
- Randomly select one of the right-hand side choices for this rule
- Push the selected choice onto the stack
- If it's embedded Javascript, then:
- Recursively expand the element
- Execute the expanded element in Javascript
- Add the return value to the end of the output
- If it's a string, add it to the end of the output.
The code itself is somewhat lengthy, so I'll walk through it piece by piece.
function executeRules(start, rules, context, otValues=null) { // For convenience, if a single string gets passed in we'll convert it to // a non-terminal. Otherwise the start should be an initial stack of elements. let stack = Array.isArray(start) ? [...start] : [{type: "nterm", value: start}]; let output = ""; otValues = otValues || {}; // Expand any unexpanded one-time rules for (let nt in rules) { // Is this a otnt with no value? if (nt[1] == "$" && !(nt in otValues)) { // Put a placeholder in otValues so that we don't try to // recursively evaluate this otnt. Real values for otnts // will be strings, so any non-string number will do. otValues[nt] = NaN; // Recursively evaluate nt. Mark it with an illegal value // before starting so that let val = executeRules([{type: "otnterm", value:nt}], rules, context, otValues); otValues[nt] = val; }; };
The function takes an initial stack (or starting element), the rules dictionary, a context (which is used to evaluate embedded Javascript) and optionally a dictionary of values of the one-time non-terminals. The first step is to evaluate any unevaluated one-time non-terminals. To do this, I iterate through the rules dictionary looking for rules with a one-time non-terminal on the left-hand side that doesn't already have a value in the otValues dictionary. Since I'm going to call executeRules recursively to evaluate the right-hand side of this rule, I need to give the one-time non-terminal a value, otherwise the first thing the recursive call will try to do is evaluate the same one-time non-terminal. The value from the recursive call becomes the value of the one-time non-terminal.
The next step is to start iterating through the stack.
// Iterate the stack until it is empty or we hit a limit let count = 0; while (stack.length > 0 && count < 1000) { count++; const current = stack.pop(); // If it's a one-time non-terminal that has been defined, add // it's value to the end of the output. Otherwise it will fall // through and get evaluated. if (current.type == "otnterm" && otValues[current.value] && otValues[current.value] != NaN) { output = output.concat(otValues[current.value]); continue; };I've implement a “guard" on this iteration that gives up after 1000 iterations. It's easy to accidentally write rules that will never terminate, so this provides a little safety if that occurs.
The top element in the stack is popped off and then dealt with based upon its type. The first type to be handled is a one-time non-terminal. Assuming this has a value, that value will be pulled from the otValues dictionary and added to the output. If it doesn't have a value or has the NaN placeholder value, it falls through to get evaluated as if it was a regular non-terminal. (This is how one-time non-terminals get defined in the recursive call from earlier.)
// If it's a non-terminal, find a rule that matches, select a choice, // and push the choice on the stack. if (current.type == "nterm" || current.type == "otnterm") { // Select a choice from the available rules let choice = getChoice(current.value, rules, context, otValues); if (choice) { // Push choice on the stack. stack = stack.concat(choice.slice().reverse()); } else { // No choice was found, so treat the nterm as a string output = output.concat(current.value); }; continue; };The next part deals with non-terminals (and unevaluated one-time non-terminals). The getChoice function selects a right-hand side from among the choices for this non-terminal. The right-hand side is then pushed onto the top of the stack. Note that since stacks in Javascript actually push and pop from the end of the array, we need to reverse the right-hand side before adding it to the stack. We also copy the array with .slice() so that any changes we make don't inadvertently change the rule this choice was taken from. If for some reason we encounter a non-terminal that doesn't have a rule, we just treat it like a string and add it to the output.
Before I go on to the rest of the engine, let's look at how getChoice works:
function getChoice(key, rules, context, preValues) { // If there's no rule for this key or no rhs, give up. if (!rules[key] || ! rules[key].rhs) return null; return selectFromRHS(rules[key].rhs, rules, context, preValues); };
getChoice itself is just a front-end to selectFromRHS that checks to see that a rule actually exists for this non-terminal. selectFromRHS is more complex:
function selectFromRHS (rhs, rules, context, otValues) { // If there's only one choice, return that. if (rhs.length == 1) { return rhs[0].elements; }; // Otherwise we need to iterate through the possible choices // and add up all the weights to decide which to pick. let weights = []; let totalWeight = 0; for (let choice of rhs) { let weight; // Simplification, weight might just be a string or a number if (typeof choice.weight == 'string') { weight = parseFloat(executeRules(choice.weight, rules, context, otValues)); // If weight isn't a number if (weight == NaN) { console.log('Weight is NaN: '+weight); weight = 1; }; } else { ...
To start, for the common case where there's only one choice for the right-hand side of a rule, we return that choice. Otherwise we iterate through all the choices, evaluating the weight for each choice and keeping track of the total as we go. The weight might just be a string like “1" and in that case we can simply turn it into a number. But the value of the weight might itself be the right-hand side of a rule:
} else { // Weight is itself a RHS, so we need to select from it and then // expand the selection const select = selectFromRHS(choice.weight, rules, context, otValues); if (select) { const expanded = executeRules(select.slice().reverse(), rules, context, otValues); if (typeof expanded === 'string' || expanded instanceof String) { // The string should parse to a number weight = parseFloat(expanded); // If weight isn't a number if (weight == NaN) { console.log('Weight evaluated to NaN: '+choice.weight); weight = 1; }; } else { console.log('Expansion did not return a string for '+choice.weight); weight = 1; }; } else { // selectFromRHS failed console.log('Unable to select from '+choice.weight); weight = 1; }; };
In that case we need to recursively select one of the choices, execute the choice, and then turn it into a number. If any of those steps goes wrong, we just set the weight to 1 and continue on.
In any case, once we have a number for the weight of this choice, we save it and add it to the total:
// Save weight so that we don't evaluate it again during selection. weights.push(weight); totalWeight += weight; };
Now that we have all the weights and the total of the weights, we can randomly select one of the choices based upon the weights and return that:
// Now figure out our selection. let selection = Utils.rand(totalWeight); for (let i=0;i<weights.length;i++) { selection -= weights[i]; if (selection <= 0) return rhs[i].elements; }; // Something likely went wrong console.log('Fell out of selection loop in getChoice'); return rhs[rhs.length-1].elements; };
If for some reason that didn't work, we'll return the last choice.
Now back to the main execution loop. We've covered how non-terminals are evaluated. Now we'll cover embedded Javascript:
// If it's embedded Javascript, then: // Recursively expand the element // Execute the expanded element in Javascript // Add the return value to the end of the output if (current.type == "jscript") { // The value of the jscript is a right-hand side, so make // a choice from there. let choice = selectFromRHS(current.value, rules, context, otValues); // Copy the value before reversing it onto the stack. // Reuse otValues so we continue to use the one-time values. const expanded = executeRules(choice.slice().reverse(), rules, context, otValues); if (typeof expanded === 'string' || expanded instanceof String) { // Execute in the provided context. const execVal = String(context(expanded)); if (typeof execVal === 'string' || execVal instanceof String) { output = output.concat(execVal); } else { console.log('Unable to coerce context value to String for '+expanded); }; } else { console.log('Expansion did not return a string for '+current.value); }; continue; };
The value of the embedded Javascript is a right-hand side, so this looks much like the handling above for a weight. We select a choice from the right-hand side, expand it to a string, then we evaluate it using the provided context function. Finally we force the result of the evaluation to be a string and append it to the output.
The last possibility is a string element:
// If it's a string, add it to the end of the output. if (current.type == "string") { output = output.concat(current.value); continue; };
In that case we simply add the string to the output.
If something falls through these cases (although nothing should!) then we'll simply treat it as a string and add it to the output.
// Else complain but treat as a string console.log('Unknown element type "'+current.type+'" in executeRules.'); output = output.concat(String(current.value)); }; if (count >= 1000) { console.log('executeRules hit the iteration limit.'); }; return output; };
That's the end of the iteration loop. When the stack has been emptied (or we've reached the 1000 iterations limit), we return the output.
Here's a simple rule set that tests all the capabilities:
<$pi> => `Math.PI`; <start> => <first> [1] | <second> [`99+99`]; <first> => I am surprised this was selected!; <second> => The value of pi is <$pi>;
Running this almost always produces:
The value of pi is 3.141592653589793
function test(svg) { // Create a Parser object from our grammar. const parser = new nearley.Parser(nearley.Grammar.fromCompiled(Lodestone)); // Parse text parser.feed("<$pi> => `Math.PI`;\n\ <start> => <first> [1] | <second> [`99+99`];\n\ <first> => I am surprised this was selected!;\n\ <second> => The value of pi is <$pi>;"); console.log('Parse is '+parser.results[0]); let rules = processRules(parser.results[0]); console.log('rules is '+rules); let result = executeRules('<start>', rules, s => eval(s)); console.log('result is '+result); };
It's rather irritating to have to escape all the newlines to enter a rule set, so next time I'll work on some code to read in the rules from a separate rules file.
Lodestone is now complete, and you can download it in the Part 13 branch from the Procedural Map Compasses repository on Github to access all of this code. Part 1 has instructions, but the short version (on Windows) is to double-click mongoose-free-6.9.exe to start up a web server in the Part 13 directory, and then select the test.html link. Obviously you can browse the code and other files, and make changes of your own. You can also try out this code on the web at https://dragonsabound-part13.netlify.app/test.html although you'll only be able to run the code, not modify it.
Suggestions to Explore
- It's not currently possible to use a single quote in a Lodestone rule; the parser will always expect that to be the start of a quote string. Likewise for a < sign. How would you modify the Lodestone parser to allow those characters?
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.