Create a 3d maze with Silverlight 5.0

I would like to start this post saying I'm not a game development expert. During the first times of my work with computers I've been fashinated by the matter but I never gone deep on this development branch. Once I've meet the first time Silverlight 5.0 and I known about the 3D programming the first idea I had is to create a very simple maze as the one someone could write as the basis of a 3D game. In this post I want to briefly illustrate the work you can download at the end of the text. Here you can view a short video of the result of my work.

The maze in this video is made totally with the 3D API in Silverlight 5.0 and is totally compatible with the RTW bits. The maze is randomly generated every time you load the program and you can control the movement using the keyboard.

Generate the maze

At the base of the example there is a random generation algorithm. I think there are lot of algorithms you can find on internet and probably the one I used is really simple, but it is really effective.

The maze if based on a square divided in a number of cells and every cell has a wall on every side. Once I decided the size of the side I fill the square of celle and then I choose a random cell on a side. Then I search for an adiacent cell to move to. If the cell exists I remove the walls betweek the two cells then I move to the new position.

The algorithm continue to crawl the cells while there are room to move. If during this loop I meet a position that have not a free adiacent cell I crawl back on my steps searching for some cell to move to. When the position returns to the very first position where I started so the work is finished and all the cells have been used. Here is the core of the algorithm I described:

   1: int progress = 0;

   2:  

   3: Stack<Cell> stack = new Stack<Cell>();

   4: this.Reset();

   5:  

   6: Cell cell = this.GetRandom(0);

   7: cell.Type = CellType.Enter;

   8: cell.Visited = true;

   9:  

  10: while (true)

  11: {

  12:     Cell adiacent = this.GetAdiacentNonVisited(cell);

  13:  

  14:     if (adiacent != null)

  15:     {

  16:         stack.Push(cell);

  17:         adiacent.Visited = true;

  18:         cell = adiacent;

  19:  

  20:         progress++;

  21:  

  22:         this.OnGenerationProgressChanged((int)(progress * 100.0 / (this.Width * this.Height)));

  23:     }

  24:     else

  25:     {

  26:         if (stack.Count > 0)

  27:             cell = stack.Pop();

  28:         else

  29:             break;

  30:     }

  31: }

  32:  

  33: cell = this.GetRandom(this.Height - 1);

  34: cell.Type = CellType.Exit;

  35:  

  36: this.OnGenerationCompleted();

The figure on the side shows the resulting maze that is generated by the algorithm. It is very close to the labyrinths you can find in puzzles magazines.

Create the 3D view

Once the maze has been calculated it is time to render it using Silverlight 3D API. The rendering is made creating a square plan representing the floor of the maze and then iterating over oll the cells and creating the remaining walls.

A wall is exactly a parallelepiped created on a side. Since the thickness of the square side is zero, the wall is created across this line. some point external and some point internal. To avoid gaps in the corners all the walls include the corner of the square, also if another wall already used the same space.

Silverlight 3D API let you create every kind of figure using a collection of edges. The edges are drawed to create triangles.  A triangle is the sole surface you can create connecting three edges, that for sure is part of a single plane. Every other surface you can create can be constructed using a collection of triangles but is not necessarily part of a single plane. So to create the rectangle representing a face of a wall you have to use two triangles.

On the left side you can see the aspect of a wall. The figure shows the triangles that compose the three visible faces of the wall. Remember that the other side has exactly the same faces in the opposite position.

Drawing with the API you have to create the vertices of the figure then create the triangles connecting the vertices with edges. The full collection of edges makes the figure and it is added to a greater collection that represents the entire drawing. This collection is used to draw the final scene. The following snippet shows how to create a single wall:

   1: private void AddWall(List<VertexPositionColor> edges, float xOffset, float zOffset, float xSize, float zSize)

   2: {

   3:     var wall = new List<VertexPositionColor>();

   4:  

   5:     Vector3 topLeftFront = new Vector3(xOffset, this.Height, zOffset + zSize);

   6:     Vector3 bottomLeftFront = new Vector3(xOffset, 0.0f, zOffset + zSize);

   7:     Vector3 topRightFront = new Vector3(xOffset + xSize, this.Height, zOffset + zSize);

   8:     Vector3 bottomRightFront = new Vector3(xOffset + xSize, 0.0f, zOffset + zSize);

   9:     Vector3 topLeftBack = new Vector3(xOffset, this.Height, zOffset);

  10:     Vector3 topRightBack = new Vector3(xOffset + xSize, this.Height, zOffset);

  11:     Vector3 bottomLeftBack = new Vector3(xOffset, 0.0f, zOffset);

  12:     Vector3 bottomRightBack = new Vector3(xOffset + xSize, 0.0f, zOffset);

  13:  

  14:     Color c1 = Color.FromNonPremultiplied(200, 200, 200, 255);

  15:     Color c2 = Color.FromNonPremultiplied(150, 150, 150, 255);

  16:     Color c3 = Color.FromNonPremultiplied(100, 100, 100, 255);

  17:  

  18:     // Front face

  19:     wall.Add(new VertexPositionColor(topRightFront, c1));

  20:     wall.Add(new VertexPositionColor(bottomLeftFront, c1));

  21:     wall.Add(new VertexPositionColor(topLeftFront, c1));

  22:     wall.Add(new VertexPositionColor(topRightFront, c1));

  23:     wall.Add(new VertexPositionColor(bottomRightFront, c1));

  24:     wall.Add(new VertexPositionColor(bottomLeftFront, c1));

  25:  

  26:     // Back face 

  27:     wall.Add(new VertexPositionColor(bottomLeftBack, c1));

  28:     wall.Add(new VertexPositionColor(topRightBack, c1));

  29:     wall.Add(new VertexPositionColor(topLeftBack, c1));

  30:     wall.Add(new VertexPositionColor(bottomRightBack, c1));

  31:     wall.Add(new VertexPositionColor(topRightBack, c1));

  32:     wall.Add(new VertexPositionColor(bottomLeftBack, c1));

  33:  

  34:     // Top face

  35:     wall.Add(new VertexPositionColor(topLeftBack, c2));

  36:     wall.Add(new VertexPositionColor(topRightBack, c2));

  37:     wall.Add(new VertexPositionColor(topLeftFront, c2));

  38:     wall.Add(new VertexPositionColor(topRightBack, c2));

  39:     wall.Add(new VertexPositionColor(topRightFront, c2));

  40:     wall.Add(new VertexPositionColor(topLeftFront, c2));

  41:  

  42:     // Left face

  43:     wall.Add(new VertexPositionColor(bottomLeftFront, c3));

  44:     wall.Add(new VertexPositionColor(bottomLeftBack, c3));

  45:     wall.Add(new VertexPositionColor(topLeftFront, c3));

  46:     wall.Add(new VertexPositionColor(topLeftFront, c3));

  47:     wall.Add(new VertexPositionColor(bottomLeftBack, c3));

  48:     wall.Add(new VertexPositionColor(topLeftBack, c3));

  49:  

  50:     // Right face 

  51:     wall.Add(new VertexPositionColor(bottomRightBack, c3));

  52:     wall.Add(new VertexPositionColor(bottomRightFront, c3));

  53:     wall.Add(new VertexPositionColor(topRightFront, c3));

  54:     wall.Add(new VertexPositionColor(bottomRightBack, c3));

  55:     wall.Add(new VertexPositionColor(topRightFront, c3));

  56:     wall.Add(new VertexPositionColor(topRightBack, c3));

  57:  

  58:     edges.AddRange(wall);

  59: }

When the entire scene has been created it is time to draw it to the viewport. While you are drawing the scene, the collection of edges does not change anymore because it represents the object to draw on the 3D space. What really changes is the position from where the scene is viewed. This position is a vector located in the 3D space and have a direction to it points. Imagine it as your eye pointing a direction in the space that plus or minus is the direction pointed by your nose. Another important component of a scene is the light source. My example uses a omnidirectional light source but for the sake of simplicity I will leave this argument open. So here is the code that create the scene.

   1: XNA3DMazeRenderer renderer = 

   2:     new XNA3DMazeRenderer(System.Windows.Media.Colors.Red, (float)this.CellSize, 5.0f);

   3:  

   4: IEnumerable<VertexPositionColor> edges = renderer.Render(this.Maze);

   5:  

   6: this.Buffer = new VertexBuffer(

   7:     GraphicsDeviceManager.Current.GraphicsDevice,

   8:     VertexPositionColor.VertexDeclaration,

   9:     edges.Count(),

  10:     BufferUsage.WriteOnly);

  11:  

  12: this.Buffer.SetData(0, edges.ToArray(), 0, edges.Count(), 0);

Then the code that creates/updates the camera. It is full of matricial maths but it simply creates two points on the space and then connect one to the other. The first is the position of the camera and the second is the position of the target pointed by the camera:

   1: private void UpdateCamera()

   2: {

   3:     float x = (float)(this.CellSize * this.Maze.Width * this.Observer.Position.X);

   4:     float y = (float)(this.CellSize * this.Maze.Height * this.Observer.Position.Y);

   5:     float course = (float)(this.Observer.Course * (Math.PI / 180.0));

   6:     float tilt = (float)(this.Observer.Tilt * (Math.PI / 180.0));

   7:     Vector3 cameraPosition = new Vector3(x, 3.0f, y);

   8:     System.Windows.Point target = 

   9:         new System.Windows.Point(x + Math.Sin(course) * 100.0, y + Math.Cos(course) * 100.0);

  10:     float elevation = (float)(3.0 + Math.Sin(tilt) * 100.0);

  11:     Vector3 cameraTarget = new Vector3((float)target.X, elevation, (float)target.Y);

  12:  

  13:     this.View =

  14:         Matrix.CreateLookAt(cameraPosition, cameraTarget, Vector3.Up);

  15: }

As you can see in the code I use an "Observer" object that represents the player in the maze. It has a X and Y position on the 2D surface of the game, a course from 0 to 360 degrees representing the direction to it is pointing and finally a Tilt property that is used to move up and down. These properties are connected with the keyboard actions and determines the movement of the player onto the game surface.

Moving the player and making walls solid

Viewing the maze rendered the first time is for sure wonderful, but the very great thing is being able to navigate inside it with the keyboard. Every time a property of the Observer object is updated the change is reflected externally with the Change event. The event cause the update of the camera position and then the redraw of the scene. Using up and down arrow you can move forward and backward and with left and right arrows it is possible to turn the course in these directions. Additionally you can use PageUp and PageDown to tilt up and down the camera as the player tilt the head.

To catch the keyboard events continuously I use a trick. This is because keyboard event in silverlight does not repeats automatically. Using a KeyboardState class I created I check for KeyUp and KeyDown changing the status of monitored keys. Then a timer changed the observer properties according with the pressed keys. This tecnique allows also to use more that a single key at a time allowing the observer to turn since it is moving forward.

Finally you have to face another problem. While you are moving you have to check for the presence of a wall and cancel the motion when the observer hits it. Without this check the observer will pass through walls missing a great part of the realistic representation of the scene. The following code tests the presence of a wall and eventually cancel the movement:

   1: private void Observer_Changing(object sender, ObserverChangingEventArgs e)

   2: {

   3:     double x = this.Maze.Width * this.CellSize * e.Position.X;

   4:     double y = this.Maze.Height * this.CellSize * e.Position.Y;

   5:  

   6:     Cell cell = this.Maze.CellAt(

   7:         (int)(this.Maze.Width * e.Position.X),

   8:         (int)(this.Maze.Height * e.Position.Y));

   9:  

  10:     Rect boundaries = new Rect(

  11:         cell.X * this.CellSize + 1.25,

  12:         cell.Y * this.CellSize + 1.25,

  13:         this.CellSize - 2.5,

  14:         this.CellSize - 2.5);

  15:  

  16:     e.Cancel = false;

  17:  

  18:     if (cell.Top.IsSolid && y < boundaries.Top) e.Cancel = true;

  19:     if (cell.Bottom.IsSolid && y > boundaries.Bottom) e.Cancel = true;

  20:     if (cell.Left.IsSolid && x < boundaries.Left) e.Cancel = true;

  21:     if (cell.Right.IsSolid && x > boundaries.Right) e.Cancel = true;

  22: }

The collision algoritm here is very simple. It creates a buffer around the walls of the cell where the observer is located and then tests if the position goes out of these boundaries.

Working with 3D

Working with 3D in silverlight is for sure interesting but it requires a good knowledge of 3D math to achieve good results. Every time you get something really effective since it is a low level API using it programming interface becomes mostly difficult. So if you need to work with 3D I suggest to use an hi level framework that abstracts the API and let you think in terms of solid figures instead of collection of edges. Balder is for sure a good example of what I mean: http://balder.codeplex.com/

Download: http://www.silverlightplayground.org/assets/sources/SLPG.Maze.zip (270kb)