four-dimensional maze

Welcome to my documentation: (list 'testing 1 2 3).

1  01.mt3

TODO:Triple exclamation mark indicate symbols in the program. What is the right way to do this?

Multiple questio marks and TODO inicate stuff I have to investigate further, or just check to be sure,

If anyone knows how to do any of the things I’m asking about, please let me know.

2 How I got started on this project

I might first mention that the things that motivated me originally constitute an order of magnitude effort than what I’ve accomplished. Don’t look for miracle solutions!

So why did I go about implementing this rather trivial four-dimensional maze game?

I’ve been in an online D&D group since the pandemic started.

It was held once a wek in my dining room before that, which pretty well meant my dining room tabe cot cleared regularaly and was often usable for other purposes, such as dining.

Now we held it online instead. At first we used on of the online chat programs, but quickly started using roll20 to show us tha map. Voice chat did not work at first. Sometimes one or more of us had trouble using it at all. That may have happened because of limitations of out computing equpment, or our network access, or of roll20 itself.

So we used roll20’s text chat instead. It worked, thought typing was slow.

Eventually we got out computers audio systems to work together, but roll20’s voice chat did not work well. If I reember correctly had occasional dropouts and disconnects, presumably because of server limitations, network quality, and difficulties relating to to the browsers we were using. Browsers seem to keep changing security constraints without warning.

For voice conversation we switched, first to jitsi’s free service, and later to Discord.

Roll20 was under development by its developers all the time, and gradually got more and more features. We could have managed with just a map display with movable character and moster icons, forms to show character data, and maybe jointly visible dice rolling.

It kept acquiring more and more D&D rules built in, which was a convenience. We no longer had to keep referring to our D&D books. We didn’t all have copies of all the references we were using. At the dining table we could easily pass them back and forth.

It still had user interface issues – sometimes navigation was unnecessariy awkward. The designers had often rated visual elegance above ease of use.

A character sheet, for example, consisted of three scrollble pages of information. Basic information, like stats and possessions, took one page. Magic spells took another. I kept having to switch between these pages. Trouble was, the tool to switch pages was on the pages themselves, near the top. That means you had to scroll the page to near the top before you could change to the other page, and then scroll again to see the part you wanted. Why it couldn’t just be the usual UI tab mechanism at the top or at the side of the page area like most UI’s escaped me. Scrolling was often very slow.

But roll20 did make playing the game feasible while we were each living in isolation, and for that I am thankful.

But whenever roll20 was bizarrely slow, or when it had bugs, or when its imlementation of the D&D rules was wrong or merely strange, I wondered – What was involved in doing such a thing. How did one manage mulitple users communication with one another and a multiplayer state over a browser? And how did one implement coherently a grab bg of rules and mechanismssuch as the D&D rule set? True, it had a number of basic mechanisms having to do with dice rolling and player and moster statistics, but item and spell descriptions also had a huge number of exceptions. For in-person games, the dungeonmaster (DM) would make decisions on the fly, not always the ones specified in the rules, which worked. Getting exact understanding how the rules and exceptions were designed to wotl would slow the game down enormously. But with the server making these decisions was another matter. THe live dungeionmaster would decide in accordance with his artistic conception of how his world worked. If I wsas DM, I would ofte make decisions onf the fly, intuitively, without much consideration as to what the official rules were. When program bugs interpret the rules, it can get awkward. Yes, the DM can overrule the server. No. The tools the server has for adjusting the state of the game are sometimes extremely obscure. We’ve had many discussions between experienced and less experienced DM’s as they attemot to explain to one another how to use the uer interface that roll20 provides.

So I’ve wondered what was involved in such a software system.

I’ve certainly wondered what tools would be used to organise the code. I’ve wondered what is needed for and even simpler system, such as one for doing jig-saw puzzles online. Now there is no shortage of onlind jig-saw puzzle games running on Android, and probaby on Apple tablets too. But none of them that I’ve found allow multiple players to collaborate on one puzzle. even if everyone is in the same room. online could have some advantages. For one thing, we would not have to get backaches leaning over the same table where we were playing. For another, we would not have to finish the puzzle before we could set the table for dinner.

3 The Maze

Then I got the idea of writing a program that would let you do semething in other geometries, such as four-dimensional space.

Not that I can really simulate what it would be like to be an person living in such a space – our eyes have only two-dimensional retinas, and every artificial mechanism I’ve seen has problems providing the extra dimension – one which forces the new dimension to be presented differently from the others. Rotations become strange: things qualitatively change their medium of presentation as they merely turn.

Well, discard visual. Try a purely textual representation.

I tried using procedural content generation to build a four-dimensinol maze to use in a text adventure game. Implementing a minimal version of such a game was easy. The program was pretty well identical to one for a three-dimensional text game – I just had to use a our-dimensional array of rooms, and pick two new words for two new directions. An online search revealed that the new directions already had names:

You needed something to make it interesting. Maybe some furniture, Maybe some things to carry around and drop so you have a chace of seeing when you get back to a place you’ve already been before. Drawing a map on paper was effective in the old Adventure game (called advent on ancient Unix systems). But those rooms had interesting descriptions, even if the geometry didn’t always line up.

I decided to try making the place more interesting by having multiple players , calling out to each other, describing what they encounteres, trying to meet up, to figure out how to get into the same room.

That’s when I realised I wanted a networked game.

4 Networking

The next stage was to build in communication between a server (containing the game) and multiple users. The users would be using browsers over a network.

How to keep game state? I decided keep it on the server for the durations of the game. Yes, I thought of making it a totally distributed system, with enough game state on each user’s machine, and enough communications between all the users’ machines to make it work, but that immediately semed far too much work. Yes, I thought of frequently writing it to disk to enable restart in case of crash, but that too seemed more work than it was worth, since the maze game was expected to take only a few minutes of play. Maybe there would someday be a reason to put in this effort, but it didn’t seem to need doing now.

So the game state would be stored on a single machine which everyone coud communicate with, and if that machine went down, the game would be over.

The program I ended up writing had two main modules: the game itself, called "maze.rkt" and the communication infrastructure, called "webfront.rkt".

They are currently available on http://topoi.pooq.com/hendrik/maze-source. They change frequently as I clean them up and improve them. If you want to use them as a basis for your own work, make a copy – you can’t rely on any of this to remain compatible.

I plan eventually to have a somewhat definitive, well-documented version available.

So how did I go about building this?

Well, first I made a trivial version of the game. One that accepts move requests from one player and provides trivial responses, such as "received message foo" when the player sends "foo". The idea was to use this as a game for testing drafts of the communication infrastructure.

Then I started working on the communication infrastructure.

Starting with a single user. I wanted something that could accept an HTTP request, consult the game implementation, and reply with what the game said it should reply.

And I had to run the game, however trivial, on a web server, accepting HTML equests.

Now I already had a web server, the one that provides my static web site topoi.pooq.com. But the simplest way to maintain the game state was to maintain it within a single running Unix process. And using things like CGI was complicated. Each user request would be processed by a separate Unix process, so I would have to deal with a lot of processes and their Unix interprocess communications. THis was a big step up from a static web page.

Instead, I looked for an easily reprogrammable web server. And found one. The publicly avalaible program libraries for the programming language Racket contained the building blocks for one. (I wonder – is there also an easily reprogrammable brower?) It has tools for accepting TCP connections, HTTP and HTTPS connections, parsing the incoming requests, constructing responses, and sending them bach to the client. All I would have to do is figure out how to use them, deal with any networking problems that arose, and connect them to the game – at first, the tivial dummy game, and later, the real game.

The dummy game does nothing except to print a few messages to signal that the functions it contains have been called.

To handle multiple players, I had to make it possible to identify individual users.

To do that I first had to get a request form a user and reply. This was the easy part. I could mostly copy some code out of the Racket webserver manual. Then I had to add some code to consult the game. All fairly easy. The players’ browsers want to see HTML requests, wrapped in some protocol. The web server took care of the protocol, providing appropriate headers and such. It would even (if so asked) find or start up a browser to show me the resulting web page! (the automatically providd browser was started on the same computer as the server. So I could use the development environment Drracket on my laptop to try all this out, and the new browser window would appear on the same laptop screen as the code I was editing! Convenient!.

And synthesising the HTML was straightforward for the trivial test. A string constant like "<html><body>Ooof!</body></html>" was enough too put "Ooof!" onto the browser screen.

Next I had to learn how to recognise individual users. so I could tell diferent players’ moves apart.

The standard way to do this is with cookies. You place a cookie on the user’s machine, and get the browser to include that cookie in every user request, so you can tell who is who.

The cookies I chose to use are randomly chosed large integers. With large enough integers, the chance of getting randomly chosen integers to be the same is nil, so they can be used as ID values. Simple in principle, and it ment I could avoid having to write a game-openeing dialogue where people would have to choose a user name and I’d register them into a table. (Would I then have to have a privacy policy in case anyone from Europe uses the game because I’m storing private information?)

And Racket also has functions to make cookies to send to the player and to parse them when they come back.

So when a player connects, I extract the identity value if there is one. If not, I generate a random ID. I check the ID in a hash table of IDs of existing players. This hash table maps ID values to data structures desctibing players. If it’s there, I use it. If not, I generate a new player data structure and put it in to the hash table and use it. I then consider the player’s identity to ba known.

In early debugging, I put the player’s identity number into the HTML message I send back to the user. This way I can check whether the identity checking works.

TODO: I’m still doing it now. Guess I’m still debugging.

I tried connecting to the same run of the server from different browsers (each one had its own store of cookies, and so were recognised as different players even though they might be running on the same machine.

How did I generate syntactically correct HTML? Racket has HTML libraries that can build HTML from a tree structure and also parse HTML to generate such tree structures. I use them.

5 02.mt3

The Racket libraries have some functions somewhere (I don’t know where) that contain functinos like ’p’, ’li’ ’br’ and so forth that build tree structures for HTML constructs out of tree structures for their components, giving a straightforward way ofcoding HTML. The functions that send responses to clients recognise these structures and unparse them into correctly structured HTML.

I found it easier to build these tree structures more directly by using quasiquote and unquote (See Quasiquoting: quasiquote, unquote, and unquote-splicing and

for details.) I found it convenient to use automatically counted parentheses in drracket and be sure that the HTML open and closing tags would match.

See Continue: Web Applications in Racket for a less formal introduction to web programming in Racket. x-expressons are defined in Rendering HTML, which goes on to describe how to use quasiquote to make x-expressions.

TODO: Find out how contracts work. I don’t use them, but the x-expression specification in chapter 4 is a contract definition. But it looks almost like a function to test whether something is an x-expression.

TODO: The definition of xexpr is a contract. Is there a way of asking if something is an xexpr without triggering a contract faiure?

TODO: And what do the dots mean in the definition render-post : (post? . -> . xexpr/c) ?

6 webfront

The main function in webfront is start. start is called in start-game near the end of the webfront module. It is one of the many erguments to serve/servlet.

It says what to do for an incoming request from a user. Its main jon is to examine the incoming HTTP request, determine if we have a new or old user, and to hand off any game actions to the game. It currently contains a *lot* of printf statements to aid in debugging.

Note that start is confusingly recursive. Akfter printing a trace message, it immediately and unconditionally calls start again. This would seem to be an unbounded infinite-loop tail recursion. Its saving grace is that the inner call’s argument is evaluated before the inner call is performed. racket (normally) evaluated arguments before doing a call. All the work happens in the argument, and then, work done, it does the tail call to get ready for the next request.

It is returned from a call to send/suspend. send/request accepts a function that takes an http: request. Initially, that will be the first request from a player to start a new game.

TODO: that http-requesting function is an inline lambda-expression. Would the code be clearer or easier to explain if it were a named function?

The argument to send/suspend is a function that accepts an http: request. That function’s job is to build an x-expression to return to the player as the web page showing his status in the game and inviting him to get on with his next move.

send/suspend waits for an incoming http: request. When one finally comes in, it calls its parameter function (the one without a nema), passing it the url from the request.

TODO: Maybe extract the source IP number from the request for tracing or debugging? Is that still information accessible? Do I have any connection information aside frin the URL and its paraneters?

The nameless!!! function extracts cookies from the URL (TODO: evidently there is more information that the URL) in order to see if the player is known as already part of the game. find-player looks up any identity cookie it finds.

TODO: There are places in the code where I want the ID cookie of a player, instead of the struct player. When I wrote some of those I seem not to have known the id was in the player structure. As a result, there are places where I pass an identiy number intead of a player structure. This invites changes!

TODO: the-script is not yet part of the system. Its purpose is to make it possible for the server to send news to the player even when the player has not recebtly sent a request. It requres some nontrivial work before its’s even slightly useful. Work in progress, will be worked on later. HTTP: is a query-response protocol – everything has to be initiated by the client, and the server just has to wait until the client asks for something. The script is ultimately inteded to get downloaded from the server to prod the client to extend a long-term request that the server can respond to whenever there’s news to report. Further explanation will appear once I’ve written the code to explain about.

I quickly discovered I needed a debugging mechanism for incoming HTTP: requests. examine-request does this. It takes a request and sets up an xexpr that can be placed into the response to the player. Or just printed at teh server. The frequent use of ’format’ is to take an internal data structure and convert it ino a string that can be embedded into an xexpr. This is also an example of the use of quasiquote to build an xexpr.

TODO: I there a better arrangement of functions in thie program? And in this writeup, which is currently chronological? Maybe have all the cookie builders together?

remove-cookies!!! is a repair mechanism. In the early days of coding, cookies were left on the testing machines. This function is to remove them. Nowadays. cookie are set with an expiry time of one hour.

TODO: Do I need another semaphore to serialize game actions?

There’s player-states-semaphore and that’s the only one in webfront right now. It is used to prevent simultaneous access and modification of the id -> player hash table. And there’s none in maze.

The player-states-semaphore is there to serialize requests. Since playres can interact by arriving in the same place in the maze (currently not reported promptly enough) and Racket’s web server does not guarantee to serialise http requests, I have to do this myself. And the players’ identity hashtable get written to and read from, so I need concurency control.

The code for entering new players into a game is somewhat messy.

player-states is a hash mapping player id’s (the id’s stored in browser cookies) to player structures. This struct is initialized when one runs the entire program. Rerunning the entire Racket program starts new game. Obsolete ID’s are ignored, because they will not be in the hash table.

new-state cretes a new player from a player id. It gets called only after checking the id is not in the hash table. Internally, it asks the game’s interface functin to create whatever the game wants for a new player.

TODO: Shouldn’t this function be called something like new-player??? Except that’s already a function.

id-of-player is just the field-selector player-id renamed, perhaps becsuse I forgot the name temporarily?

new-id creates a new random id and makes sure it isn’t already in the hash table. If Racket’s random generator is good enough, the check for duplicates probably won’t find any between now and the heat death of the universe. And if it does anyway, the code will take care of it

TODO: (The game itself was intended to use player structures, not player id’s, but it hasn’t worked out that way. This should be explained when we look at the maze.rkt program)

Next comes the real new-player function. It creates a new player record if there isn’t already one in the hash table.

There might seem to be excessive numbers of printf statements in a number of functions. They were introduced during debugging, because when the webserver software hit contract violations, the backtrace information in Racket wa usually insufficient to locate the place in my code to blame for feeding it invalid data (such a wrong x-expressions). It seems these x-expressions are turned into HTML using timing determined lazily when the packets are being emitted, which in turn depends on the dynamics of network communication. Reponses my code generates may get delayed in send queues.

find-player also looks for a player record in the hash table, and creates one if necessary. There seems to be some redundancy between all the functions that find player records from id’s.

for-players iterates through all players in teh hash table.

TODO: Should it be inside the player-states semaphore?

start-game is the function in webfront that starts the game. It wakes up webfront by starting to wait for an incoming connection.

The servlet parameters:

• #:connection-close? #t : Every move by a player comes in as an http request. The web server tends to keep the http connection open for a while after seding a response. This can prevent other http requests from coming in at the same port. This parameter tells the web server not to do that.

• #:stateless? #t : The Racket web server provides a mechanism whereby the state of the web server is packaged into the http response as a continuation. This option tells the wen server not to do that. The typical game just has too much state for it tow be worth shuffling back and forth between client and server. Besides, I’d end up with a different continuation for each player, making them effectively running in separate games.

• #:listen-ip #f ; listen on all available incoming ports, instead of listening only on 127.0.0.1

• #;port : the game-port!!! Currently 8080, because 80, the usual web service port, is already in use on my server for my regular web page.

• #:launch-browser? #f THis option is useful for early testing. It starts a browser for me and makes it send the game an appropriate URL that it sends to the server. Not what I want during productin or during multiplayer testing.

• #:servlet-path "/4d" used in construction the url to reach the game.

The webfront module is currently set up to be called from the maze program. As such, it needs to export stuff to maze.rkt so that the maxe.rkt can call on its functions, many of which will call back to code implementing the maze.

7 maze.rkt

This module implments the maze – its data structure and the operations on it.

It also gets actions from webfront and uses webfront to return responses to the players.

The responses to the players are in the form of x-expressions. These can encode pretty arbitrary html pages, so it’s possible to include graphics and audio if wanted. The current program uses text-only output. Trying to represent four dimensions on a flat two-diensional screen wasn’t something I wanted to tackle.

7.1 Generating the maze

The maze itself is in a four-dimensional array, though a lot (nit alas! not all) of the code is written in a way that’s independent of the number of dimensions.

TODO: use Racket’s test mechanisms to enclose code that was written to act like unit testing.

valid-ref and xvalid-ref are there so I can tell whether an index into the four-dimensional array is valid without stopping the program by inexing out of bounds.

The eight directions implemented are up, down, north, south, east, west, ana, and kata. Ana and kata are for the fourth dimension. The others should already be familiar. I have not provided anything like northwest or southana.

TODO: I have used symbols to deNote the directions. shOULD i USE STRINGS INSTEAD?

TODO: To make the program truly independent of the number of dimensions I should find a way to synthesise names for more dimension.

Motions are coded as a list of two numbers – one to denote the dimension, and one to denote forward and backward.

TODO: Is there a more convenient was to encode a direction of motion?

The maze contains rooms. Each room is denoted by a room structure. A room may have doors in the walls (leading to other rooms (this makes it into a maze)), it may contain things (to make it less boring to come to a room in the game), and it will be made part of a region as part of the maze-generating process. A region is a set of interconnected rooms. The largest available region is the one players will be put into. It doesn’t seem fair to place a player in a room with no doors and no place to go to.

The room structure contains a lost of doors. The doors represented in this list are the ones in the up, north, east, and ana directions, each being represented bya boolean indicating whether the door is present in tthe room. The remaining walls may also have doors, but they are encoded as doors in the neighbouring rooms.

fprint-room and print-room describe a room as a string of ASCII text. fprint-room, like fprint, takes a stream for output. TODO: Is this helpful? Or am I better off with an x-expression? And do I ever use a stream other thsn current-output-port!!!?

And then there’s for-loc, a looping construct to iterate over all the rooms in the array of rooms. It is implemented as four nested loops. This is another function taht must be changed to make the maze program dimension-independent.

The code that determines regions builds a list of regions. Each region is represented by a structure that contains a list of its locations. As well as its number, which is an arbitrary identifier, and its size, which is the number of locations it contains.

It works similar to a garbage-collection algorithm. The marking roots ar all the rooms in the array.

It picks a root, and if it isn’t part of a region yet, it starts a new region amd marks the room as being in the region (and adds it to the region’s list of locations). Then it proceeds through the room’s doors to recursively mark the neighbouring rooms.

It finished using rooms as marking roots when there are no more left.

Then it’s easy to pick the largest one to be the main region where the game is played.

And finally, we emplace things randomly into rooms. TODO: the list of thingss could easily be expaned or itself use some kind of procedural generation.

That’s how the maze is generated.

7.2 Game actions

There are several obsolete functions here.

First, there’s move! and a series of one-letter abbreviations for the directions. They are no longer used. When testing the maze before there was any networking involved, I could easily type, in Racket’s interactive shell,

(m u) (m n) (m a)

to move a single defaile player up, north, and then ana.

It’s obsolete now that all nondebugging input and output goes via browser.

Once again I do a hash table that defined directions – this time to turn stringfor direction into symbols.

And there’s another function for describibg a room, this time producing an x-expression.

And one to show whether anyone other than the current player is in the same room.

TODO: Can the desciber that produces an x-expression be easily combined with the one that doesn’t.

Then do-action!!!, which performs an action (if possible) and returns an x-expression to be reported to the player.

A list of x-expressions it not an x-expression. To make a list into an x-expressoin, I prefix it with ’div. That will make an <div> ... </dev> item, which is valid HTML – usually used for grouping. I also use it when I need to return an x-expression but have nothing to put ino it. I do wish x-expresions had a better notation for this so I wouldn’t end up generating a log of <div>’s and </div>’s which only contribute bulk to the generated HTML. Now I understand why I so often see a lot of unnecesary <div>’s when I View Page Source in a browser.

Finally, w4d is the game structure that is given to webfront so it can play a real game instead of the disfuntional dummy game.

And then call start-game with w4d as parameter to start the networking needed to use w4d.