First I discussed five physical causal systems. Next I considered numeric representations of those systems. Then I began to explore the idea of virtual causality, and now I’ll continue that in the context of virtual mazes (such as we might find in a computer game).
I think mazes make a simple enough example that I should be able to get very specific about how a virtual system implements causality.
With mazes, it’s about walls and paths, but mostly about paths.
Actual physical mazes (like the one pictured above) have walls, floor, and maybe a ceiling. Some mazes might have doors that can open (or not). These things all have physical properties — strength, opacity, height, thickness, etc.
But mazes can also be viewed as encoding information about a set of connected paths. Given how a maze limits travel, it’s easy to see it in terms of walls, but a maze is actually a network of paths. The walls just delineate those paths.
Further, what really matters is the network connections. The length of any given path between those connections is irrelevant with regard to the network (or solving!) of the maze.
Mathematically speaking, the information a maze encodes is a graph, which — as an abstraction — is easy to represent numerically. When we analyze a maze’s logical properties, we do it at this level.
However mazes often have a physical shape we’d like to preserve, especially in a game context. In these cases we do want to represent a degree of physical information.
Plus, a static graph of paths doesn’t encode much causality. We really are interested in the walls (and possible doors) in this case. The path information here is secondary and derives from the definition of the walls.
So let’s start with a list of requirements:
- Walls. Gotta have walls. They define the maze.
- Addresses. All locations in the maze have a unique “coordinate” of some kind. We can address any location by its coordinates.
- Cursor. At any given moment, “we” have a current location within the maze.
- Movement. We need to be able to change our location.
- Entrance and Exit. (Alternately, Start and Goal.) These are just fixed designated locations within the maze.
- Possibly Doors. Defined as parts of a wall that can be opened. (As opposed to an opening or passageway that cannot be closed.)
All but #4 are objects (“nouns”) in our maze model. Movement is a function (“verb”) that changes our current location. This is the dynamics of the maze and therefore its causality.
Simply put: maze causality allows us to move the cursor from location to location, but not through walls!
Of the five objects, all but #6 are static. Doors can be open or closed. As such they’re just complicated enough that I’ll ignore the possibility of doors for now.
A simple implementation might use a grid (a two-dimensional array) as the background on which to define the maze.
This results in a regularly spaced rectangular maze (such as shown here). Each square of the grid is an addressable location in the maze.
The address of a square is simply the row and column of the grid (starting from one in the upper left).
For example, in the maze shown here, the entrance (red square) is [1,1] and exit (green square) is [8,8].
Movement is constrained in two ways: Firstly, the cursor only moves one square at a time. Secondly, it must not move through walls!
Which brings us to the walls.
Our current location, as well as the location of the entrance and exit, can be coordinates stored outside the grid (in their own variables), or they can be encoded into the grid squares they occupy.
I find it makes sense to code landmarks (like entrances) into the grid, but the cursor (because it’s dynamic) works best as external data. That way the current location is always handy, rather than having to search the grid for it every time you reference it.
The point is that the walls can also be encoded into the grid squares, and there are many ways to do this. Here are three:
Firstly (kinda old school), if each grid square is just a number (as might be the case in low-level programming languages), we can think of each wall as one bit of that number. We might arrange it like this:
- North Wall = bit 1
- East Wall = bit 2
- South Wall = bit 3
- West Wall = bit 4
- Is an Entrance = bit 5
- Is an Exit = bit 6
If a wall exists, its bit is set to 1, otherwise 0. The last two items flag a given square as an entrance or exit (by setting the bit to 1).
Each number in the grid has a value in which the bits are set appropriately. We test whether we’re allowed to move in a given direction by testing the bit corresponding to the wall in that direction. If it’s set to 1, we cannot pass.
Secondly (a bit easier to debug), if bits seem a bother, we could use a string for each square. The string would contain characters or words defining whether a wall exists (or an entrance).
It could be as simple as the characters ‘N’, ‘E’, ‘S’, & ‘W’ or it could use the words ‘north’, ‘east’, ‘south’, & ‘west’. And entrance or exit might be tagged with ‘I’ (or ‘in’) and ‘O’ (or ‘out’), respectively.
Thus a given string might look like: “NSI” (or “north south in”). We test whether a move is legal by scanning for the appropriate character (or word). Finding it in the string means no.
Finally, many programming languages don’t confine to a single value (a number or a string) in an array. When a language allows compound objects, then each piece of information is a different member of the set.
There would be, for instance, a
northwall member of the collection, and that member would be true or false depending on whether there was a wall. Testing a move means looking at the relevant member.
⇒ As an aside, notice that this model has an issue. What if square A says there’s a wall to the north, but square B — the square directly north of A — does not say there’s a wall to the south? Does that mean a one-way wall (or is it a bug)?
The problem comes from how the squares on both sides of a wall must identify the wall — which means walls are defined in two places, which is the dreaded synchronization problem (a key source of programming bugs).
Far better to represent walls (or anything!) only once to avoid the problem. For now I’ll leave how that might be accomplished as a potential reader exercise. Tender your solutions in the comments.
Regardless of how we actually implement walls, the idea is that, from any given location in the maze, we can ask four questions:
- Is there a north wall?
- Is there an east wall?
- Is there a south wall?
- Is there a west wall?
And get a yes/no (or true/false) answer. A simple implementation might look like:
function Wall-Test (Location, Direction) as set Cell to Maze[Location.row, Location.col]. set Wall to Cell.getWall(Direction). return Wall end function
The above assumes our Maze object supports a function,
getCell(), that retrieves a Cell (a grid square) given some Location. It also assumes that maze Cell objects support a
getWall() function that retrieves the appropriate wall given a Direction.
On this we can build four possible actions we can take:
- Move north (if possible).
- Move east (if possible).
- Move south (if possible).
- Move west (if possible).
It will be up to us to provide for what happens if the move is not possible. These actions break down into several steps:
- Test for a wall in the indicated direction.
- If there’s a wall, then return “BUMMER!”
- Otherwise, move in that direction.
- Return “YIPPEE!”
We can wrap this in a simple single function:
function Move (Location, Direction) as set Wall to Wall-Test(Location, Direction) if Wall then return "Bummer!" else Update-Location(Location) return "Yippee!" end if end function
So the client code must pay attention to what this returns. If “BUMMER!” then the move was unsuccessful and location hasn’t changed. If “YIPPEE!” then it was and it has.
If the move fails, what the client code does next depends on the situation. If it tries another direction of its current square, it may be able to move. Or, if all three forward directions are walls, we’re down a blind alley and need to back up.
[Regarding the three forward directions: in any given maze square, backwards is where we came from, which leaves left, forwards, and right.]
There are different types of mazes, many of which we can’t implement using the grid described here.
The curved paths of the garden maze shown up top are one type of maze that requires a fancier implementation. Multi-level mazes also cannot be represented by a simple grid.
But one advantage our wall-defining approach does have (besides preserving the shape of the maze) is that it represents both simply- and multiply-connected mazes the same way. Techniques that focus on paths can require different implementations.
(Or not. An implementation for a multiply-connected maze should be able to represent a simply-connected maze.)
A bigger point is that virtual mazes need not even be realizable in any physical terms. A maze can be four- (or more!) dimensional. It can connect in ways not possible in the real world, even in just a printed maze.
This lack of reality includes causal behavior.
I mentioned a potential issue with defining walls for each square. Image a maze in which (deliberately or by error) there are no south walls. You can walk south with no restriction (including leaving the maze).
But the north, east, and west, walls all work as normal.
The point is, through error or intent, what might seem “normal” causality for a virtual system can be anything at all.
Causality is entirely arbitrary in virtual reality (cf. The Matrix).
Next time I’ll drill down on the arbitrary nature of virtual causality as it pertains to walls and other objects, but more in the context of virtual reality.
I want to move from an abstract functional representation of maze information to one that better preserves what we think of as physical causality. The goal is to simulate “real” walls better.
Stay amazed, my friends!