Antimatroid, The

thoughts on computer science, electronics, mathematics

Ouroboros: reinventing Nibbles

leave a comment »

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 B. Each \vec{x} \subset { \{ 0, 1, \ldots B - 1 \} }^{2} coordinate may be occupied by at most one snake segment. For each view, a mapping f : M \to V from the model space, M, to the view space, V, is necessary to achieve the required behavior.

snake_space1

For the CLI view, let f(\vec{x}) = \vec{x} since every coordinate maps one-to-one with a cursor position on the console.

The 2DGUI view requires a scaling factor, c > 1, otherwise the board would appear to be too small to play- unless for example, upon a cellphone LCD. Let f(\vec{x}) = c\vec{x}.

The 3DGUI view requires an initial mapping from a \vec{x} = (x,y) coordinate to a \vec{y} = (\vartheta, \varphi) system. This is accomplished by g(\vec{x}) = \frac{2\pi}{B}\vec{x} where B is the length of the edge of the board. A torus is defined in terms of an interior radius, R, and the swept radius, r. Thus a torus is defined as the following:

\displaystyle (f \circ g)(\vec{x}) = \begin{pmatrix}(R + r cos(\varphi))cos(\vartheta)\\(R + r cos(\varphi))cos(\vartheta)\\r sin(\varphi)\end{pmatrix}

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:

snake_model

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 x^{(k)} coordinate will be calculated as x_{n+1}^{(k)} = x_{n}^{(k)} + dx_{\text{dir}}^{(k)} \pmod{B}.

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 N will have collected N - 1 rewards. Thus, let S(N) = \sum_{n = 0}^{N}{100 (1 - e^{\frac{-(N - 1)}{10}})} 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.

snake21

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;
        }
    }
}
Advertisements

Written by lewellen

2009-02-01 at 12:00 am

Posted in Projects

Tagged with , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: