Perspective Based Lingo Mazes: The Director Dungeon Crawl

February 22, 2001
by Andrew M. Phelps

Introduction

This article outlines the process of creating a typical "maze game" in which characters move around via the arrow keys, and must navigate passages defined by the walls of the maze. Further, the view that the character is presented with is one based in first person perspective, meaning that they see the maze as if they were in it. This type of system was popularized by adventure games in the early 1980's like Bard's Tale(tm), Wizardry(tm), and Might& Magic(tm), and has remained a staple of the genre to this day.

This paper is split into two major sections, the first describing the basics of the program, including the relevant data structures and engine setup, and the second linking the underlying engine to the display system producing the illusion of perspective. There is also a future work section describing a few uses for an engine such as this, and links and references to other maze-game implementations.

The Maze Game Engine Core

Tutorial File Setup

The idea of a maze game has been around for a while, and was popularized in the 1980's by one of my favorite games of all time, A Bard's Tale by Interplay Productions. A Bard's Tale also included character advancement and combat in a pseudo-Dungeons & Dragons type storyline, and it should be noted that this engine implements absolutely none of that, it is only concerned with movement and rendering. This engine is provided as a stepping-stone for games of that ilk, or for many other genres, it is concerned primarily with the "how" of the maze rather than the "why".

To begin, download the demo files and unzip them into a directory of your choice. Start the movie. Upon starting the movie you will be placed into a most incredibly boring maze, one that has no walls. Given that this tends to be rather unimpressive, click the load button. Select the maze01.txt file that was included in the download package. The world we will reload, and you will be faced with the screen in figure 1.

Figure 1: Screenshot of the Maze Engine version 1.0 in action.

This is the demonstration maze that the engine ships with, and you can explore it using the map in Figure 2. The up arrow moves forward, and the right and left arrows turn you right or left. If you get lost you can always reload and you will be placed back at the start position, on the X in figure 2, facing north (up on the map).

Figure 2: Map of the sample maze. Start position is (3,1).

Data Structures & Global Variables

At the root of all maze games is a rather common data structure, a two-dimensional array. This is the common structure used in more traditional 2D or "top down" games, and have been implemented in Lingo by Gary Rozenzweig and countless other authors. This engine creates a two dimensional array, but goes one step further in that it stores in each position of the list a property list that describes the position or "square" of the current location. The process of list creation and manipulation has been well documented by other authors like Peter Small and thus this paper offers little explanation on these basic features.

The original array is created by calling the Make_Maze handler in the Maze Tools script. This handler in turn calls the Create_Maze handler, which creates the array.

You can make a properly formatted maze square using the Make_Maze_Square handler, you can add it to the maze list with Add_Square_To_Maze, you can get the property list from a specific location within the maze array by using Get_Square_From_Maze, and you can get the associated value for any key in the property list calling the Get_Value_From_Square handler.

Finally, the entire creation of the array is governed by the global variables declared in the startMovie handler. Table 1 describes their use in the overall construction of the engine.

Table 1: Global Variables inside Maze Engine

Multiple Levels and File Abstraction

After all of this setup and instantiation, the movie calls Populate_Maze and Fake_Maze, which are handlers designed to load the default world that you get when you start the movie. This presents an interesting problem and it is one that is common to this type of application, how to store the maze or series of mazes that make up a game. One solution is the Fake_Maze handler, which is essentially a script that inserts a hard-coded level into the maze. This is, of course, less than ideal, as it requires the programmer to create a script for each maze or level. Additionally, it requires that the author of this script know something about how the maze is structured, and it is rare that the level designer and/or content writer is also the programmer.

This engine also makes use of a second solution to this issue, storing maze descriptions in separate text files. It does this be ready and writing the array to text files using the fileIO Xtra that ships with Director. This is done by calling save_maze and load_maze, which are bound to the save and load buttons within the interface. These in turn format and save the text, or read and load the array, respectively. How each handler calls the next can be seen in the trace diagram in Figure 3. This method of "wrapping" the fileIO Xtra, originally developed by Steve Kurtz, makes it easy to reuse this block of code over and over, as we have done here at R.I.T. on numerous projects.

Figure 3: Calling hierarchy for load / save functions.

Movement & Collision Detection

The final responsibility of the engine core is to account for the movement of the character and the inability of the character to move through walls (at least in most cases, the classic games of the genre generally incorporate hidden walls and teleports in addition to standard collision detection). Moving through the maze is fairly straightforward, and is implemented in the Move_Me handler . This handler begins by deciding whether the character is moving forward or backward, and then querying the array for the description of the square the character is currently occupying. If in the property list for the square the value for the characters current facing direction is a blank, then the character is allowed to proceed forward. If this value is returned as a wall, then the character is not allowed to move. This is the reason for describing each square in a property list, by doing so you can determine whether there are any obstacles in the way to block movement.

Assuming the character is allowed to move forward, then the Move_Me handler calls Find_Direction that modifies the global current_pos_x and/or current_pos_y variables to reflect a move on either the X or Y axis respectively. Additionally, this handler contains the logic to make the maze "wrap around" by checking to see if the X or Y of the character has exceeded the maximum number of rows or columns defined at engine startup.

The Illusion of Perspective

Basic Perspective & Lingo Quad Implementation

The real distinction of this system from the more traditional maze systems that have been implemented in Lingo is not so much the code in how it works, but the way in which it is drawn to the stage. This first-person perspective view has a long history, and was probably one of the reasons for the success of the games that originally implemented it, like A Bard's Tale (see figure 4).

Figure 4: A Bard's Tale III, by Interplay Productions.

This view could be achieved by a traditional 3D engine, projecting the planes against a center of projection and using a lot of neat math tricks. Instead, this engine uses none of this math, it works instead in the simplest possible manner, manipulating only the visibility property of a number of sprites to produce the illusion.

The first step in creating this illusion is "quadding" the sprites on the stage. What this really means is using the quad property to position the corners of a series of sprites to produce the illusion of depth. This is done in the Position_Walls handler, and while this script hard codes the values for the positions of the walls relative to a 640x480 window, there is nothing preventing a more advanced solution that uses the scale of the window to determine the coordinate points. In any event, the sprites are positioned so that they appear in perspective. If there were only 3 sprites possible (i.e. the character could only see the square he was currently on) and they were not textured with bitmaps, it would look like the original test application in figure 5.

Figure 5: Original Maze Test (left wall in red, forward all in blue, right wall in red showing the placement and quad locations of individual sprites).

All the program is responsible for is turning these sprites on and off, which it does through the visibility property. In essence, all of the walls are there all of the time, its just that they are sometimes "clear." The program looks at the square the character is currently occupying, and quesries that square for the my_left_dir, my_right_dir, and facing_dir values, if these come back as "wall" then it renders the sprite as visible, if the lookup returns a "blank" then the sprite is invisible.

Additional Depth Sorting

This is, however, only part of the illusion. The shot above of the original application is rather unconvincing as view into a world, primarily because it fails to allow a character to see into the distance. In order to allow a character to see further, we align more sprites towards the center of the stage. The closer we are to the center, the closer we are to the vanishing points and the smaller the sprites. This engine is set to allow a character to view the square it is on and two additional squares forward. Note that just like the original sprites, these sprites are always present, and their visibility is manipulated in similar fashion in relation to the property list for the square. The engine simulates the position of the character by adding temporary values before lookup to the character's facing_dir.

Other Visible Surfaces

The final steps in the illusion are the pieces of walls that are parallel with the front of the view's square, and the floor. The floor is very simple, as this engine assumes that the floor is always present, thus there is no need to check for a visibility flag for the floor, and the demonstration world ships with no ceiling. The little pieces of the walls are accounted for by adding yet another round of sprites, to account for the widening field of vision from the characters perspective (see Figure 6). These values are calculated again by querying the array for "wall" or "blank" but offsetting the character's position not only along the forward direction, but also to the left and right.

Recursive Solutions

Needless to say, hard-coding each pass of what is visible and not visible is not an ideal solution. There would most likely be a recursive solution based on a depth_view parameter that determines how many squares away a character is able to see (in outdoor worlds this is commonly used to determine the difference between day and night, or to temporarily "blind" characters to only the square they are currently on). While not implemented here, it should be trivial, based on the implementation above to devise such a system, and probably to position the sprites automatically as well. This version of the engine is presented as a teaching tool and as such does not contain the more abstracted code.

All of this lookup and manipulation occurs in the Render_Maze handler, where case after case and lookup after lookup are performed. Because Director seems to have fairly good performance in list lookup, and because the engine is not trying to smoothly pan the transition, there is little to no lag from the user's point of view. After this lookup the Render_Maze handler calls Draw_Maze which actually manipulates the visibility of the sprites.

Moving & Spinning

Characters move by using the arrow keys, and as such the movie binds the keyDownScript property to the keyPressed handler. This handler checks the incoming ASCII value to ascertain which arrow was pressed, and then calls the Spin_left, Spin_right, or Move_Me handler as appropriate, passing "forward" for the up arrow key and "backward" for the down. This is the same Move_Me handler that was described previously, but at the end of the handler is a call to the Render_Maze function to update the view.

The final touch to the whole program is the ability of the character to change their forward direction, which is performed in the spin_left and spin_right handlers. These handlers change the forward direction, and then calculate the other three global variables by calling Set_Init_Dir. This again calls the rendering loop after the spin, so that the stage is updated.

Conclusions

This engine proves Director a capable tool for creating games that were incredibly difficult to program a few short years ago. While not offering the peak of performance, the Lingo environment can still be used to maximum advantage by playing to its strengths, and this engine does exactly that. This system is a fairly open, generic engine devised to support a first person perspective maze game. With different graphics laid atop the core code, this engine could be used in many different types of systems to provide users with interesting puzzles. Additionally, it can be retooled as the basis for a much more complicated game, and is a suitable teaching tool for students who need to understand the basics of lists, multi-dimensional arrays, and property lists.

My personal goal would be to see this system incorporated into a multi-player game using the Shockwave Multiuser Server, allowing each player to play a member of an adventuring party. If you implement the ideas presented here please contact the author.

A sample Director 8 movie is available for download in Mac or Windows format (approximately 1.4MB each). The download includes the full text of this article in PDF format, and a sample maze text file.

Copyright 1997-2024, Director Online. Article content copyright by respective authors.