Ouroboros: reinventing Nibbles

Introduction

I talked about some classic arcade games in a previous post that I had worked on over the years and mentioned that I’d get around to posting some implementation details of one of them. A few months later here we are and the following is an overview of the implementation details of Ouroboros- my revisioning of the classic arcade game Nibbles that I enjoyed playing and learning about back in my QBasic days.

This write-up will go over the activities associated with the software development process from specification to implementation. Before I get into the details, here’s a game play of what is that I’ll be explaining how to make:

Specification

The goal of the game is to collect rewards. Each time a reward is collected, the user’s score is increased. The snake is constantly moving in the direction last requested by the user. The user can direct the snake to move either left, up, right or down. To make the game more challenging, the snake will grow whenever the snake consumes a reward. The game then ends once the snake spans the entire board or the snake collides with itself. When the snake “hits” a wall, its position wraps around the board. When either of the terminating conditions is meet the user is asked if he or she wishes to play again.

Requirements

The user may control the direction the snake may move by using the keyboard. The following keys are valid: {←, ↑, →, ↓} and {a, w, d, s} to the directions {left, up, right and down}.

The game is to be displayed to the user as as command line interface (CLI), 2D graphical user interface (2DGUI) using WinForms and a 3D GUI (3DGUI) using Windows Presentation Foundation. The CLI and 2DGUI shall appear as boards that the snake and reward appear on. The 3DGUI shall appear as a torus that the snake and reward appear on.

The game may not appear to be slower as the length of the snake increases.

Design

The Board

The board is a simple coordinate system with a fixed side length . Each coordinate may be occupied by at most one snake segment. For each view, a mapping from the model space, , to the view space, , is necessary to achieve the required behavior.

For the CLI view, let since every coordinate maps one-to-one with a cursor position on the console.

The 2DGUI view requires a scaling factor, , otherwise the board would appear to be too small to play- unless for example, upon a cellphone LCD. Let .

The 3DGUI view requires an initial mapping from a coordinate to a system. This is accomplished by where is the length of the edge of the board. A torus is defined in terms of an interior radius, , and the swept radius, . Thus a torus is defined as the following:

The Snake

The snake is conceptually a sequence of segments that I choose to represent as a singly-linked list where each node contains a pointer to the next segment and the segment’s position. The following illustrates a snake of length five:

To achieve movement, the position of the head segment is passed to the next segment, and the next segment on to its next segment so on and so forth until the tail is reached.

Each time the snake moves, its coordinate will be calculated as .

Scoring should be done in such a way that rewards become more valuable as time continues. Since the initial length of the snake is 1, a snake of length will have collected rewards. Thus, let represent the scoring function. Where 100 is maximum score for a reward, -1/10 is the decay factor.

Once a snake has consumed a reward, a new node is added to the tail with a location identical to the tail location.

To determine if a the snake is on top of a reward, each segment’s position will be compared to the reward’s position. If a segment and reward are identical then the snake is on top of the reward. If no match is found, then the snake is not on top of the reward. This process can be done in linear time. Constant time, if you choose to generate rewards that are not on top of snake.

When drawing the game it is useful to observe that the only thing that ever changes between time step is the the head and tail of the snake. Thus, it is prudent to only draw the current head position and erase the previous tail position. This will produce a length independent drawing method so that the game does not appear to be slower as the snake gets larger.

Implementations may be written using recursion, but beware that with larger board sizes that you run the risk of a stack overflow on systems that don’t give you much memory to work with. Using a cursor to search the singly-linked list may be more appropriate when using larger board sizes.

Implementation

I decided to go with a Model-View-Controller (MVC) pattern since I’d like to be able to view the CLI, 2DGUI and 3DGUI all at once. Below is a complete UML class diagram of all the MVC components that I choose to implement.

The following is the core engine of the game; it perform each of the core tasks of performing logic, drawing the board, getting user input and maintaining time.

public class Program {
    [STAThread]
    static public void Main(string[] args) {
        List views = new List(new IGameView[] { 
            new CLIGameView(), 
            new GUI2DGameView(), 
            new GUI3DGameView() 
        });
        IGameController controller = new CLIGameController();

        int boardSize = 32;
        double maxScore = double.MinValue;

        views.ForEach((view) => view.initialize(boardSize));
        
        do {
            SnakeDirection desiredDirection = SnakeDirection.Up;
            SnakePoint reward = SnakePoint.Random(boardSize);
            SnakeSegment snake = new SnakeSegment(SnakePoint.Random(boardSize));

            views.ForEach((view) => view.drawBoard());

            do {
                if (controller.InputAvailable) {
                    SnakeDirection possible = controller.getDirection();
                    if (possible != SnakeDirection.Nop)
                        desiredDirection = possible;
                }

                if (snake.isOnTopOf(reward)) {
                    snake.grow();

                    if (snake.Length != boardSize * boardSize) {
                        do {
                            reward = SnakePoint.Random(boardSize);
                        } while (snake.isOnTopOf(reward));
                    }

                    maxScore = Math.Max(maxScore, snake.Score);

                    views.ForEach((view) => view.drawScore(snake.Score, maxScore));
                }

                SnakePoint oldTail = snake.Tail.Location;

                snake.move(desiredDirection, boardSize);

                views.ForEach((view) => view.drawSnake(snake, oldTail));
                views.ForEach((view) => view.drawReward(reward));

                System.Threading.Thread.Sleep(1000 / 15);
            } while (!snake.selfCollision());

            views.ForEach((view) => view.drawGameOver());
            views.ForEach((view) => view.drawPlayAgain());

        } while (controller.playAgain());

        views.ForEach((view) => view.deinitialize());
        views.Clear();
    }
}

public class GUI3DGameView : IGameView {
    private int boardSize;
    private Form canvas;
    private ScoreLabel score;
    private TorusScene scene;


    public int BoardSize {
        get { return boardSize; }
    }

    public GUI3DGameView() {
        canvas = new Form();
        canvas.BackColor = System.Drawing.Color.FromArgb(0x33,0x33,0x33);
        canvas.FormBorderStyle = FormBorderStyle.FixedToolWindow;
        canvas.MaximizeBox = false;
        canvas.MinimizeBox = false;
        canvas.SizeGripStyle = SizeGripStyle.Hide;
        canvas.Text = "GUI3DGameView";
        canvas.ClientSize = new Size(384, 384);

        ElementHost host = new ElementHost();
        host.Child = scene = new TorusScene();
        host.Dock = DockStyle.Fill;
        canvas.Controls.Add(host);

        score = new ScoreLabel();
        score.Dock = DockStyle.Bottom;
        
        canvas.Controls.Add(score);
    }

    public void initialize(int boardSize) {
        this.boardSize = boardSize;

        if (!canvas.Visible)
            canvas.Show();
    }

    public void deinitialize() {
        canvas.Dispose();
    }

    public void drawBoard() {
        score.reset();
        scene.removeSnake();    
    }

    public void drawGameOver() {
    
    }

    public void drawPlayAgain() {
    
    }

    public void drawReward(SnakePoint reward) {
        scene.moveReward(reward.x, reward.y);
    }

    public void drawScore(double current, double max) {
        score.setScore(current, max);
    }

    public void drawSnake(SnakeSegment head, SnakePoint oldTail) {
        scene.addSegment(head.Location.x, head.Location.y, head.Length);
    }
}

using System;
using System.Collections.Generic;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Media.Media3D;

namespace Snake.View.GUI3D {
    public class TorusScene : Viewport3D {
        private Queue<ModelVisual3D> patches;
        private ModelVisual3D reward;

        public TorusScene() {
            Camera = new PerspectiveCamera(new Point3D(10, 10, 10), new Vector3D(-10, -10, -10), new Vector3D(0, 1, 0), 60);

            AmbientLight aLight = new AmbientLight(Color.FromRgb(0x33,0x33,0x33));
            ModelVisual3D aLightHost = new ModelVisual3D();
            aLightHost.Content = aLight;
            Children.Add(aLightHost);

            DirectionalLight light = new DirectionalLight(Colors.Orange, new Vector3D(0, -10, 0));
            ModelVisual3D lightHost = new ModelVisual3D();
            lightHost.Content = light;
            Children.Add(lightHost);

            DirectionalLight rearLight = new DirectionalLight(Colors.LightBlue, new Vector3D(0, 10, 0));
            ModelVisual3D rearLightHost = new ModelVisual3D();
            rearLightHost.Content = rearLight;
            Children.Add(rearLightHost);

            Model3DGroup torus = new Model3DGroup();
            double N = 16.0;
            double dTheta = Math.PI / N, dPhi = Math.PI / N;
            double R = 5.0, r = 2.0;

            Color surface = SnakeColors.MGround;
            
            for (double theta = 0.0; theta <= 2.0 * Math.PI; theta += dTheta) {
                for (double phi = 0.0; phi <= 2.0 * Math.PI; phi += dPhi) {
                    Point3D[] S = square(dTheta, dPhi, R, r, theta, phi);
                    torus.Children.Add(triangle(S[0], S[1], S[3], surface));
                    torus.Children.Add(triangle(S[3], S[2], S[0], surface));
                }
            }

            ModelVisual3D model = new ModelVisual3D();
            model.Content = torus;
            Children.Add(model);

            patches = new Queue<ModelVisual3D>();
        }


        public void addSegment(double u, double v, int max) {
            ModelVisual3D snake = addSphere(u, v, 0.5, SnakeColors.MHead);

            if (patches.Count != 0 && patches.Count == max)
                Children.Remove(patches.Dequeue());
            patches.Enqueue(snake);

            Point3D[] S = square(Math.PI / 16.0, Math.PI / 16.0, 5.0, 2.5, u / 16.0 * Math.PI, v / 16.0 * Math.PI);
            double r = 30.0 / Math.Sqrt(3.0) / Math.Sqrt(S[0].X * S[0].X + S[0].Y * S[0].Y + S[0].Z * S[0].Z);
            Camera.SetValue(PerspectiveCamera.PositionProperty, new Point3D(r * S[0].X, r * S[0].Y, r * S[0].Z));
            Camera.SetValue(PerspectiveCamera.LookDirectionProperty, new Vector3D(-r * S[0].X, -r * S[0].Y, -r * S[0].Z));
        }

        public void moveReward(double u, double v) {
            if (reward != null) {
                Children.Remove(reward);
                reward = null;
            }

            reward = addSphere(u, v, 0.25, SnakeColors.MReward);
        }

        public void removeSnake() {
            while (patches.Count != 0)
                Children.Remove(patches.Dequeue());
        }


        private ModelVisual3D addSphere(double u, double v, double r, Color color) {
            Model3DGroup sphere = new Model3DGroup();
            Point3D center = parameterized(5.0, 2.0 + r, u / 16.0 * Math.PI, v / 16.0 * Math.PI);
            Vector3D vec = new Vector3D(center.X, center.Y, center.Z);

            double dTheta, dPhi;
            dTheta = dPhi = Math.PI / 3.0;

            for (double theta = 0.0; theta <= 2.0 * Math.PI; theta += dTheta) {
                for (double phi = 0.0; phi <= 2.0 * Math.PI; phi += dPhi) {
                    Point3D[] S = square(dTheta, dPhi, 0, r, theta, phi);
                    for (int n = 0; n < S.Length; n++)
                        S[n] = Point3D.Add(S[n], vec);

                    sphere.Children.Add(triangle(S[0], S[1], S[3], color));
                    sphere.Children.Add(triangle(S[3], S[2], S[0], color));
                }
            }

            ModelVisual3D model = new ModelVisual3D();
            model.Content = sphere;
            Children.Add(model);

            return model;
        }

        private Point3D parameterized(double R, double r, double theta, double phi) {
            return new Point3D(
                (R + r * Math.Cos(phi)) * Math.Cos(theta),
                r * Math.Sin(phi),
                (R + r * Math.Cos(phi)) * Math.Sin(theta)
            );
        }

        private Point3D[] square(double dTheta, double dPhi, double R, double r, double theta, double phi) {
            return new Point3D[] {
                parameterized(R, r, theta, phi),
                parameterized(R, r, theta, phi + dPhi),
                parameterized(R, r, theta + dTheta, phi),
                parameterized(R, r, theta + dTheta, phi + dPhi)
            };
        }

        private Model3DGroup triangle(Point3D a, Point3D b, Point3D c, Color color) {
            MeshGeometry3D mesh = new MeshGeometry3D();
            mesh.Positions.Add(a);
            mesh.Positions.Add(b);
            mesh.Positions.Add(c);
            mesh.TriangleIndices.Add(0);
            mesh.TriangleIndices.Add(1);
            mesh.TriangleIndices.Add(2);

            Material material = new DiffuseMaterial(new SolidColorBrush(color));
            GeometryModel3D model = new GeometryModel3D(mesh, material);
            Model3DGroup group = new Model3DGroup();
            group.Children.Add(model);
            return group;
        }
    }
}

Reimplementing arcade classics

Arcade games are a fun exercise in trying out different techniques that ultimately yield the same result: a responsive graphical interface where an agent is controlled by the user’s keyboard. I’ve had a chance to design a few applications in a couple of languages and thought I’d go over the design decisions of each. Plus a little variety never hurts in tuning your skill set.

Tetris was a simple game pushed by Nintendo to fuel sales of the Game Boy in the early 90s. I wrote a variant awhile ago that uses blocks rather than tetrominoes to cut out unnecessary complexity. This C# implementation revolved around the .Net WinForms and falls under the umbrella of Object Oriented and Event Driven designs. A one dimensional array keeps tabs of how deep a block can fall along with a list of fallen blocks. Any time a block lands on top of another block or the user hits a key, an event handler processes the event and causes the screen to be repainted. This design felt forced but otherwise worked as needed. I hope to refine this approach in future applications.

Pacman was the iconic flagship of 80s arcade armada. During college I wrote a simple version of Pacman in C that relied on the prototypical input, logic and draw loop. In this implementation, an array is kept that represents the inanimate actors: nothing, reward and walls. In addition separate cursors are kept to keep track of Pacman and each of the ghosts. Design-wise, this worked out really well. Input was parsed and applied to Pacman, each of the ghosts move towards Pacman, termination conditions are checked and finally the array and animated actors are painted on the screen. Out of these designs, this one felt the most versatile.

Snake, also known as Nibbler or Nibbles was a classic game that used to get put onto cell phones (when phones used to come with games for free…) where you have a snake that grows as it consumes rewards. The snake moves around a torus (represented as a 2d surface) and the game is over when the snake covers the surface or when part of the snake crosses over itself. This implementation went with C# relying purely on the Console. The snake is represented as a linked list where every node holds a direction and location. As each loop passes, the direction and location of the head is passed onto the next segment and so on until the tail is reached. If the snake is on top of a reward a new segment is appended to the tail. The design is the same as my Pacman implementation, however there is no underlying array to maintain.

If the comments call for it, I’ll post more implementation details on any of the above.