Virtual Mazes

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:

  1. Walls. Gotta have walls. They define the maze.
  2. Addresses. All locations in the maze have a unique “coordinate” of some kind. We can address any location by its coordinates.
  3. Cursor. At any given moment, “we” have a current location within the maze.
  4. Movement. We need to be able to change our location.
  5. Entrance and Exit. (Alternately, Start and Goal.) These are just fixed designated locations within the maze.
  6. 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:

  1. Is there a north wall?
  2. Is there an east wall?
  3. Is there a south wall?
  4. 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:

  1. Move north (if possible).
  2. Move east (if possible).
  3. Move south (if possible).
  4. 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:

  1. Test for a wall in the indicated direction.
  2. If there’s a wall, then return “BUMMER!”
  3. Otherwise, move in that direction.
  4. 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!

About Wyrd Smythe

The canonical fool on the hill watching the sunset and the rotation of the planet and thinking what he imagines are large thoughts. View all posts by Wyrd Smythe

13 responses to “Virtual Mazes

  • Wyrd Smythe

    WordPress has some long-time annoying bugs. Notice how this post is supposedly published on November 18th? Nope, it was published today, November 19th. I even checked it in preview — showed being published today.

    Know why the date’s wrong? Because I was foolish enough to use the Quick Edit function in the Post listing for my Draft posts. I just wanted to add some Tags.

    But I’ve been burned before, years ago, when I learned that doing that sets the Publish date to the date of your edit. So when you go to post your post, it fucking back posts to that edit date.

    I’d try to let someone in WP know, but I’ve been underwhelmed before by even getting them to acknowledge a bug let alone actually go after it. Especially when this is the Classic Admin system which they’ve abandoned. (I am not a fan of the new interface. I still use the Classic Editor.)

    For The Record: This post should have been posted when I actually posted it, just a few minutes before the date and time of this comment.

    😦

    • Wyrd Smythe

      And I see double-click to edit a comment is back in the Classic Comments section. Damn it!

      This is why I don’t bother trying anymore. I complained about this before and it took several rounds of back and forth to even get them to understand what I was saying. (And I’m not totally sure they ever did.) But more than a year after that you could double-click on a comment to highlight part of it and then copy that part. (As you might do when replying to people since WP has no quoting capability.) The double-click didn’t take you into Edit mode on the comment. (I should think a very rarely used feature. Who even though double-click to edit was a good idea?)

      But just recently I double-clicked on a comment in order to copy part of the text and WP took me into edit mode on the comment.

      Damn it!

    • Wyrd Smythe

      The sad thing is I thought about changing the post date and even Scheduling the post to publish in just a few minutes. That would have reset the date. But I got fooled by the damn Preview, which showed today’s date, and thought I was okay.

      You’d think by now I would have learned to trust my gut instincts more. Second-guessing myself almost always steers me wrong.

      • Wyrd Smythe

        Ha! Well, ain’t that a pip! It just occurred to me that I can use the same Quick Edit feature that screwed up the post date to reset the post date!

        So now it’s published on the correct date — today! Yay!

        But twice burned now, so avoid Quick Edit on unpublished posts is the lesson. It inadvertently sets the Schedule Date to the edit date (but does not actually schedule the post). When you do Publish later, your post will be back-dated to that date. (Unless you Schedule the post, which obviously changes that date.)

      • Wyrd Smythe

        But what does that say that we can manipulate the publish dates even after the post is published?

        The first time this happened to me it was a post that had been in my Drafts folder a long time, and the Schedule date — due to using Quick Edit to edit the tags — was over a year in the past. So when I finally published the post, it didn’t show up on my page because it was dated so long ago. (It was there, you just had to scroll back to that date.)

        I was able to use Quick Edit to change the date on that post, too. Almost weird you can do that, don’t you think?

  • SelfAwarePatterns

    I’ve never used Quick Edit. The one time I went into it, I didn’t like the feel. Sounds like it’s more trouble than it’s worth. The annoying thing about posts being back dated is that a lot of people end up missing them in the Reader.

    You can actually edit the publication date in the main editor, but I heard the WordPress people frown on it, and eventually give you grief if it’s done too often. Mostly I think they’re concerned about people using it to bump their posts up in the Reader.

    Interestingly, this post still shows up as Nov 18 at 21:11 in Inoreader, coming from the RSS feed. Did you schedule it, or just hit Publish?

    I used to use the scheduling feature all the time, but it was unreliable in a lot of ways, particularly in posting to social media. Eventually I decided it too was more trouble than it was worth.

    • Wyrd Smythe

      “I’ve never used Quick Edit.”

      I use Quick Edit on comments (rather than Edit) if I want to tweak a typo or fix bad formatting. I also use it sometimes when I’m cleaning up the Tags in old posts. But never use it on a Draft!

      “Interestingly, this post still shows up as Nov 18 at 21:11 in Inoreader, coming from the RSS feed. Did you schedule it, or just hit Publish?”

      Publish, although a nagging voice in my head said I really ought to Schedule it. If that field above the [Publish] button doesn’t say “Publish Immediately” then the publish date has been set. (If the Schedule flag has been set, the button says either [Schedule] or [Updated], depending on whether you’ve saved it once already or not.)

      (I’ve never had issues with Scheduling a post, but I don’t have any social media connections. I usually just Publish unless there’s a reason for staging the publication.)

      Internally, WP, based on what’s in the XML download, has both pubDate and post_date fields, and I can see making one immutable (I would if designing this). The edit I made changed the URL and the byline date, but I see the WP Reader still thinks I published it last night.

      OTOH, the site RSS only contains pubDate, which is Tue, 19 Nov 2019 12:28:44 +0000, so it could be the reader might be using old XML. I’ve got the Livemarks Add-on for Firefox, and sometimes getting it to refresh the XML is a pain.

      And, as I’ve said, I think the WP Reader is buggy.

      • SelfAwarePatterns

        “OTOH, the site RSS only contains pubDate, which is Tue, 19 Nov 2019 12:28:44 +0000, so it could be the reader might be using old XML.”

        That’s weird. Inoreader still lists it as Nov 18, even after I explicitly refreshed the feed for your blog. I wonder what it’s using for its timestamp. I do sometimes see its listed times change, so I know it’s mutable.

        Yeah, my use of the Reader has diminished over time. I used to enjoy getting in it and discovering new content. I still occasionally do it, but either it doesn’t work as well as it used to, or my patience with its quirks is a lot less, or some combination of the two.

      • Wyrd Smythe

        “Inoreader still lists it as Nov 18,”

        That is weird. FWIW, if you have any way of checking the RSS XML, the date field is:

        <pubDate>Tue, 19 Nov 2019 12:28:44 +0000</pubDate>

        And seems to be the only date in the XML, so who knows. As I said, I sometimes have similar issues with Livemarks in Firefox. (I’ve been thinking of writing my own RSS viewer… I’m using RSS enough, and so far not really happy with existing products, that it might be worthwhile.)

        WRT the WP Reader, I don’t use the Follow part (like, ever). I always “Visit Site” to read a post. Or to leave the first comment if I make one. I have found the Conversations part of the Reader useful for following discussions once I’ve joined in, and I mostly read threads and reply there. (It’s really good for replying to a specific comment, regardless of indent level. It’s the one thing the Reader does I really appreciate.)

        I use the Comments section of the old-style Admin to reply to comments on my blog(s). That’s the only editor that allows full HTML (hence the nicely colored quotes I use here).

      • SelfAwarePatterns

        I see the same pubdate as you when I look at https://logosconcarne.com/feed/
        Unfortunately, there doesn’t appear to be a way for me to see what Inoreader itself is seeing in the feed. I can see its crawler history, and that it got your latest post at 13:04 today, and this post (I assume) at 10:25am on Nov 19. So it’s not using own receipt time. I have no idea where it’s getting that timestamp from.

        On comments, it remains on ongoing source of frustration to me that people can’t reply to comments once they’ve gotten indented, unless they use alternate UIs, or follow the link in the notification email.

        But that’s also another source of frustration. The notification I as the blog owner get doesn’t have a reply link. I have to either subscribe to the comments (and get two notices) or use one of the admin interfaces, but the hierarchy isn’t preserved in those UIs, which often makes them awkward to use.

        Overall, I really wish the comment system would be cleaned up and modernized.

      • Wyrd Smythe

        All this is exactly what drives me to write as much of my own software as possible! (And to avoid things like Bank software apps.)

      • SelfAwarePatterns

        But then you spend a lot of time writing and maintaining software. Which is fine if that’s what you enjoy doing.

      • Wyrd Smythe

        I used to enjoy it a lot. The last few years it’s gotten old (if I have to write one more “for loop”…), but it was a good run. I still get into it once in a while if something engages me.

%d bloggers like this: