6 Feb. 2012.
To establish whether or not a player is allowed to move to a next position in a game, path walking usually is the easiest to program, because all possibilities are known. This article describes 2 different path walkers, both programmed in javascript, for games on the OmegaJunior Consultancy.
Path walking is a relativley simple mechanism: given the possible next steps and the current position: where can the player go next?
We'll show a simple and a complex variation. The simple one is used in our 3D Bar Maze Puzzle, a technology proof of concept for a game that may some day get developed. Here, the player must guide a ball through a maze.
The complex one we created for our Zjramble5 word game. Here, the player must find as many words as possible, on a 4 by 4 letter grid, without reusing letters.
Obviously, the goal for each is the same, but their methods necessarily differ.
Simple Path Walker
The simple path walker depends on a maze. We allow others to write and offer mazes for use in our game. It's a simple construct like this:
Each row is a bar of cube wall patterns... Each maze holds 20 bars. Each bar holds 6 cubes. The ball can be moved from one bar to the next, and from one cube to the next, if the wall it needs to pass through is open. In our cube wall pattern, an open wall has a 1 bit, and a closed wall has a 0 bit. A bit pattern for open and closed walls.
Then we define which bit position in the bit pattern indicates which wall. From left to right: ceiling, right wall, floor, left wall, back wall, front wall. So all our path walker has to do is remember the ball position, find the appropriate wall pattern, and figure out whether the desired move is allowed:
And then somewhere else, that patternRight would be defined as 0x010000.
It's so easy, after every move our game calculates the next possible moves and enables or disables the appropriate action buttons.
Complex Path Walker
The letter grid presents 4 rows of 4 letters each, resulting in 16 nodes numbered 0 to 15. The actual letters on these nodes are stored in an array we called 'run'.
Our complex path walker needs to remember previously chosen nodes during the same turn, for a player is prohibited from reusing chosen nodes. And, when the player enters their word in the input box, those nodes that form the word, get highlighted. Since the grid may contain multiple copies of a letter, the path walker needs to determine all complete paths to all letters typed thus far, and update that for each typed letter.
And, last but not least, the same path walker is used in our Genetic Search Algorithm, to determine how many words any combination of grid letters will yield, ensuring the player receives a challenging grid.
So, we start again with an array of possible moves. Unlike the maze, this grid doesn't change its possible moves: only the contents (letters) of the positions change, not how they interact.
Either the player types a word, or our vocabulary presents a word to test. We'll call it a verb, and split it up into its separate letters. The letter run needs to be variable, since the function is used both while playing (when the run is set) and before that, while determining the best run.
We use Array understanding, in this case the forEach() function, to run our loop. It takes a function name and a new 'this' value, in our case an object we named tally.
Inside the walkVerbPathLetters() function, we keep track of how many paths the grid letters run contains to form the word. When we've reached the last word letter, and there's still some paths left, we know the typed word exists in the grid letters run.
While we are investigating a path, and the next word letter can be played with several grid letters, we spawn as many new paths as needed, and add them to the amount of paths needing to be investigated. After every word letter, any path that does not end in that letter, is removed.
That takes another 3 loops inside each other: the first to investigate every path, the second to investigate every letter, and the third to check every node. You can imagine the CPU power needed to get this done fast enough for the grid highlighting to keep up with the player's typing speed.
Conclusion
We've shown 2 kinds: a simple one that only looks from a current position to the next, and a complex one that considers every past position and must investigate every possible path. We hope that you can learn from and improve upon our examples and implementations.
Afterthoughts
There are other kinds of path walkers. Our complex walker uses lots of nested loops, which probably isn't the most effective method. Suggestions are welcome!
We'll show a simple and a complex variation. The simple one is used in our 3D Bar Maze Puzzle, a technology proof of concept for a game that may some day get developed. Here, the player must guide a ball through a maze.
The complex one we created for our Zjramble5 word game. Here, the player must find as many words as possible, on a 4 by 4 letter grid, without reusing letters.
Obviously, the goal for each is the same, but their methods necessarily differ.
Simple Path Walker
The simple path walker depends on a maze. We allow others to write and offer mazes for use in our game. It's a simple construct like this:
my.Maze: ({
bars: [//each row is a bar of cube wall patterns
/* 0 */[0x011000,0,0,0,0,0],
/* 1 */[0x000101,0x010010,0,0,0,0],
/* 2 */[0,0x000101,0x010010,0,0,0],
/* 3 */[0,0,0x000101,0x010010,0,0],
/* 4 */[0,0,0,0x000101,0x010010,0]
/* etc. */
]
});Each row is a bar of cube wall patterns... Each maze holds 20 bars. Each bar holds 6 cubes. The ball can be moved from one bar to the next, and from one cube to the next, if the wall it needs to pass through is open. In our cube wall pattern, an open wall has a 1 bit, and a closed wall has a 0 bit. A bit pattern for open and closed walls.
Then we define which bit position in the bit pattern indicates which wall. From left to right: ceiling, right wall, floor, left wall, back wall, front wall. So all our path walker has to do is remember the ball position, find the appropriate wall pattern, and figure out whether the desired move is allowed:
var currentPosition = my.Ball.position,
Maze = my.Maze,
wallPattern = 0;
wallPattern = Maze[ currentPosition.bar ][ currentPosition.cube ];
switch (direction) {
case 'right':
if ( wallPattern & patternRight ) {
return true;
}
break;
}
return false;
And then somewhere else, that patternRight would be defined as 0x010000.
It's so easy, after every move our game calculates the next possible moves and enables or disables the appropriate action buttons.
Complex Path Walker
The letter grid presents 4 rows of 4 letters each, resulting in 16 nodes numbered 0 to 15. The actual letters on these nodes are stored in an array we called 'run'.
Our complex path walker needs to remember previously chosen nodes during the same turn, for a player is prohibited from reusing chosen nodes. And, when the player enters their word in the input box, those nodes that form the word, get highlighted. Since the grid may contain multiple copies of a letter, the path walker needs to determine all complete paths to all letters typed thus far, and update that for each typed letter.
And, last but not least, the same path walker is used in our Genetic Search Algorithm, to determine how many words any combination of grid letters will yield, ensuring the player receives a challenging grid.
So, we start again with an array of possible moves. Unlike the maze, this grid doesn't change its possible moves: only the contents (letters) of the positions change, not how they interact.
nextNodes:[
/* Defines options where to go next from any given node.
Nodes run from 0 to 15,
where 0 is upper left and 15 is lower right. */
/* from 0 (corner) to */ [1,4,5],
/* from 1 (edge) to */ [0,2,4,5,6],
/* from 2 (edge) to */ [1,3,5,6,7],
/* from 3 (corner) to */ [2,6,7],
/* from 4 (edge) to */ [0,1,5,8,9]
/* etc. */
]
Either the player types a word, or our vocabulary presents a word to test. We'll call it a verb, and split it up into its separate letters. The letter run needs to be variable, since the function is used both while playing (when the run is set) and before that, while determining the best run.
function walkVerbPaths( verbLetters, run ) {
var tally = ({
"run": run,
"paths": [ ],
"pathComplete": false
});
verbLetters.forEach( walkVerbPathLetters, tally );
return tally.paths;
}We use Array understanding, in this case the forEach() function, to run our loop. It takes a function name and a new 'this' value, in our case an object we named tally.
Inside the walkVerbPathLetters() function, we keep track of how many paths the grid letters run contains to form the word. When we've reached the last word letter, and there's still some paths left, we know the typed word exists in the grid letters run.
While we are investigating a path, and the next word letter can be played with several grid letters, we spawn as many new paths as needed, and add them to the amount of paths needing to be investigated. After every word letter, any path that does not end in that letter, is removed.
That takes another 3 loops inside each other: the first to investigate every path, the second to investigate every letter, and the third to check every node. You can imagine the CPU power needed to get this done fast enough for the grid highlighting to keep up with the player's typing speed.
Conclusion
We've shown 2 kinds: a simple one that only looks from a current position to the next, and a complex one that considers every past position and must investigate every possible path. We hope that you can learn from and improve upon our examples and implementations.
Afterthoughts
There are other kinds of path walkers. Our complex walker uses lots of nested loops, which probably isn't the most effective method. Suggestions are welcome!
Need problem solving?
Talk to me. Let's meet for coffee or over lunch. Mail me at “omegajunior at protonmail dot com”.