Thoughts on delivering software

Preface

A lot can happen in four years. We get used to its passing as a milestone marking a transition from one stage of life to another. I was thinking about the last four some odd years since I’d graduated from college and came to realize that while I’ve learned a lot since then, I still have a ways to go. One recurring question I have floating around my head all this time is how to deliver a complete product. At the end of college I had the theoretical side of the story, but I only had limited exposure doing internships and consulting.

My first job after college was working for a small company focusing on healthcare. Our development group was just a couple months old and I was the second developer brought on board. We started out as a group of cowboys doing what was necessary to retain customers and bring on new ones. Despite the chaos, lack of requirements and ever shifting priorities, we managed to make the company successful and a leader in its industry. During that time, I feel that I have learned a lot about how to deliver software in the face of uncertainty.

More importantly, I’ve learned how be more than just a developer and grow into someone trusted to autonomously improve the business with my vision and execution. I’m going to cover a few choice topics that I feel have had the biggest impact on how I deliver software. Things that I feel answer that burning question of how to deliver a complete product. This isn’t intended to be comprehensive, but it should give someone where I was four years ago a little insight into how to get a quality product out the door even when it feels like it’ll never happen.

Communication

When you are sitting in front of a computer, it’s easy to get excited and starting writing whatever happens to pop into mind and race its way down your fingers. Few things are more satisfying as a developer than falling into flow and building something to completion- going through the motions of refactoring, testing and becoming convinced that you’ve written something solid. You eagerly present your product to the stakeholders. They look back at you and say, “this isn’t at all what we asked for”.

It is easy to make this mistake. Not taking the time to fully understand the stakeholder’s needs and more importantly, making sure they do too. After all, the biggest reason why software fails to meet expectations is because expectations weren’t established and requirements weren’t well defined. The source of these failures lies in failures in communication. It should seem obvious, but any software endeavor that involves more than one person relies on thorough communication to execute a shared goal- to bring a solution to market in a timely manner.

To make sure that you avoid this pitfall, take the time to work with your stakeholders. An hour of talking and planning can prevent you from wasting a day of misdirected development time. Focus on the domain problem and its solution. How the solution is implemented, is largely irrelevant compared to its completeness of requirements. To ensure that you and your stakeholder have the same view of the product, produce a dossier similar to a user’s guide that outlines how the solution behaves. Once defined, produce a quick prototype and present it to the stakeholder. Upon their approval, implement the product.

Simplicity

Now, simplicity doesn’t imply mediocre no more than complexity implies extraordinary. As Antoine de Saint-Exupéry said in Wind, Sand and Stars, “Il semble que la perfection soit atteinte non quand il n’y a plus rien à ajouter, mais quand il n’y a plus rien à retrancher“. Simplicity is simply the path to perfection and removing that which is unnecessary. Much of what can be said about delivering software can be said about managing complexity. Markets change and so too do the demands on products. As a consequence, so too do the demands on code. How much that code has to change depends largely on how well it was written.

Complexity encroaches on software in one of two ways. A product that grows organically without any direction and second through poor coding practices and design. This lack of direction comes from stakeholders committing to one-off functionality without thinking how it contributes to a uniform product. In the second example, an unorthodox solution results in a product that can never be changed and a bad set of abstractions make it difficult to change anything.

What can be done to avoid complexity and enable simplicity? Focus on established principles of the field. Design components that are modular, capable only of doing one thing and doing it well. Interfaces between systems should be flexible in what they accept and resistant to change. Code should assert its assumptions and not be ad hoc in its solutions. Above all, code should be written with meaningful abstractions that represent the problem and take into consideration how that problem can mutate or be extended to other problems. Doing this intelligently, results in maintainable, reliable and predictable code -but more importantly- code that ships.

Introspection

Being a software professional requires a certain degree of introspection. Solving problems requires us to build complex models in our minds and walk around them to discover insights that lead to solutions. The ability to maintain these mental models is an important factor to our ability to deliver a product. Despite the amount of time spent in one’s mind, there is often a failure to think about how one carries out his or her job. Lucid requirements, minimal designs and all the theory in the world are useless if you don’t know how to keep up with the demands placed upon you.

What happens when you fail to keep up? You might think to spend an extra hour a day trying to catch up. This works for a bit, but not for long. You end up giving something up for that extra hour and usually it means sacrificing sleep, relationships, interests or your health. Doing this for prolonged periods leads to falling further and further behind until deadlines are racing past you, pounds piling up on your body and work invading every aspect of your life. Ultimately, it all leads to burnout.

To keep up with demands, and to get that product out the door, it is important to know yourself and set limitations. Figure out if you are most effective in the morning or night. Understand if you like switching between projects or like focusing on one project at a time. At the end of each day, write down what you’ve accomplished and what you hope to accomplish the next day. A list makes it easy for you to see that things are getting done and what you need to be working on. If you find yourself behind due to reasons beyond your control, negotiate with the stakeholders to extend the timeline. Nothing is ever set in stone.

Epilogue

I doubt there is an all encompassing answer to how to deliver a complete product. Each year I have a different take on the question and no doubt I will continue to in the years to come. I am certain however, that building a product takes more than just a few clever software professionals, it takes a broad set of skills and abilities from people of different backgrounds. Sales, management, marketing, accounting, information technology and many other disciplines contribute to the delivery of a complete product. Building a product with these groups in mind makes it easier to deliver a complete product but also one that is successful.

Do each of these groups have the tools they need to provide a quality service to customers? Is there a well defined process for supporting the product and escalating issues to development? Does sales and marketing have access to usage data to know what customers are doing with the product? Does accounting and payroll have the information they need to send out bills and payments for services rendered? A product can really only be called complete if there is a set of processes, services and tools supporting it.

Take the time to really learn your company and industry. It’s easy enough to just be someone who spends all day writing code, but its just as easy to spend time learning what the business is really all about and what problems it aims to solve in its industry. Spend the time to learn what other groups in the company are up to and how their efforts are contributing to the success of your product. The technical mind is a great platform for spotting opportunities that can result in better products and ultimately a better company. When you have the big picture, there really isn’t anything holding you back from delivering a complete product.

Space Cowboy: A Shoot’em up game in C#: Part 3

Introduction

I’ve been working on a small video game the past few months and recent finished its development. You can read up on the original vision of the game and then check out how the prototype went. In this final installment of the series, I am going to present two sides of the application: the first is the layout of the application and how some of the high-level organizational aspects were implemented. The second side of the application is the gameplay and how some of the more interesting aspects were implemented. Here is a full demo of the game:

User Interface

Design

The majority of the application is based around the idea of stories and storyboards. Stories are analogous to tasks and storyboards to work flows. The transition between stories on a storyboard is initiated by the end user or by an automatic timer. The application has three main storyboards:

• Main Storyboard – describes the stories that constitute the application oriented stories
• Game Storyboard – defines the stories that make up the gameplay
• High Scores Storyboard – how the end user interacts with the high score stories

Main Storyboard

When the user launches the game, they will be presented the Title Story. The Title Story displays the application logo and will transition to the Menu Story after a few seconds. The Menu Story displays a list of actions that the user can initiate. The user may start a new game, view the high scores, review the settings or exit the application. When the user starts a new game, they will be presented the Game Storyboard. When the user views the high scores, they will be presented the High Scores Storyboard. When the user reviews the settings, they will be presented the Settings Story. The Settings will list out all the keyboard commands. When the user exits the application, the End Title Story is displayed. The End Title Story will display the application tagline for a few seconds and then the application will terminate.

Game Storyboard

When the user elects to start a new game, the Countdown Story is displayed. The Countdown Story will display 3… 2… 1… prior to transitioning to the Gameplay Story. The Gameplay Story allows the user to play the actual game. When a user completes a level in the game, the user will be shown the Level Completed Story. The user will be able to review their performance and decide if they are done playing or want to play the next level. If they elect to quit playing, they will be taken to the High Scores Storyboard, otherwise they will be presented the Countdown Story prior to beginning the next level. If the user is destroyed and has no more lives, the user is presented the Game Over Story and after a few seconds elapses, the user will be presented the High Scores Storyboard. If a user completes all of the levels in the game, they will be presented the Game Completed Story. Similar to the Game Over Story, the Game Completed Story will transition to the High Scores Storyboard after a few seconds.

High Scores Storyboard

If a user had received a new high score during their game, they will be presented with the New High Score Story. They will enter in their name and then be transitioned to the High Scores Story. If user did not receive a new high score during their game, they will be presented the High Scores Story. The High Scores Story will display the top highest scores recorded in the game. Once the user is done reviewing the scores, they may return to the Main Storyboard. If the user had transitioned from the Main Storyboard to the High Scores Storyboard, then they will only be presented the High Scores Story.

Implementation

Each of the of storyboards is responsible for the displaying stories on the screen and transitioning between stories and storyboards (in the following I use each interchangeably). This functionality is achieved by keeping references to each story and instantiating each story on demand. When a new story is to be displayed, the storyboard will unload the current story and load up the new story. Unloading a story consists of removing the instance from the Controls collection, unregistering all event handlers and disposing of the story. Loading a story creates a new instance of the story, registers all relevant event handlers and then displays the story by adding it to the Controls collection.

To illustrate a concrete example of this practice, here is the implementation of the Main Storyboard.

using System;
using System.Windows.Forms;
using UserInterface.GameScreen.Presentation;
using UserInterface.HighScoreScreen.Presentation;
using UserInterface.HomeScreen.Presentation;
using UserInterface.Resources;
using UserInterface.SettingsScreen.Presentation;
using UserInterface.ShutdownScreen.Presentation;
using UserInterface.StartupScreen.Presentation;

namespace UserInterface {
	public class MainWindow : Form {
		private DisplayStartupStory displayStartupStory;
		private MainMenuUserControl mainMenuUserControl;
		private HighScoreStoryBoard highScoreStoryBoard;
		private DisplaySettingsStory displaySettingsStory;
		private GameStoryBoard gameStoryBoard;
		private DisplayShutdownStory displayShutdownStory;

		public MainWindow() {
			base.Width = 320;
			base.Height = 480;
			base.FormBorderStyle = FormBorderStyle.FixedSingle;
			base.MaximizeBox = false;
			base.SizeGripStyle = SizeGripStyle.Hide;
			base.BackColor = InMemoryResources.BackgroundColor;
			base.Text = "Space Cowboy";
			base.Icon = InMemoryResources.LogoIcon;
		}

		protected override void OnLoad(EventArgs e) {
			base.OnLoad(e);
			this.Location = this.DesktopLocation = new System.Drawing.Point(400, 100);
			loadStartup();
		}

		private void handleStartupDisplayed() {
			unloadStartup();
			loadMenu();
		}

		private void handleNewGame() {
			unloadMenu();
			loadGame();
		}

		private void handleGameOver(int score) {
			unloadGame();
			loadHighScores(score);
		}

		private void handleShowHighScores() {
			unloadMenu();
			loadHighScores(null);
		}

		private void handleHighscoreShowMenu() {
			unloadHighScores();
			loadMenu();
		}

		private void handleShowSettings() {
			unloadMenu();
			loadSettings();
		}

		private void handleSettingsShowMenu() {
			unloadSettings();
			loadMenu();
		}

		private void handleExit() {
			unloadMenu();
			loadShutdown();
		}

		private void handleShutdownDisplayed() {
			unloadShutdown();
			Application.Exit();
		}

		private void loadStartup() {
			displayStartupStory = new DisplayStartupStory();
			displayStartupStory.Dock = DockStyle.Fill;
			displayStartupStory.Displayed += new Action(handleStartupDisplayed);
			Controls.Add(displayStartupStory);
		}

		private void unloadStartup() {
			Controls.Clear();
			displayStartupStory.Displayed -= handleStartupDisplayed;
			displayStartupStory.Dispose();
			displayStartupStory = null;
		}

		
		private void loadMenu() {
			mainMenuUserControl = new MainMenuUserControl();
			mainMenuUserControl.Dock = DockStyle.Fill;
			mainMenuUserControl.NewGame += new Action(handleNewGame);
			mainMenuUserControl.ShowHighScores += new Action(handleShowHighScores);
			mainMenuUserControl.ShowSettings += new Action(handleShowSettings);
			mainMenuUserControl.Exit += new Action(handleExit);
			Controls.Add(mainMenuUserControl);
		}
	
		private void unloadMenu() {
			Controls.Clear();
			mainMenuUserControl.NewGame -= handleNewGame;
			mainMenuUserControl.ShowHighScores -= handleShowHighScores;
			mainMenuUserControl.ShowSettings -= handleShowSettings;
			mainMenuUserControl.Exit -= handleExit;
			mainMenuUserControl.Dispose();
			mainMenuUserControl = null;
		}


		private void loadGame() {
			gameStoryBoard = new GameStoryBoard();
			gameStoryBoard.Dock = DockStyle.Fill;
			gameStoryBoard.GameOver += new Action<int>(handleGameOver);
			Controls.Add(gameStoryBoard);
		}

		private void unloadGame() {
			Controls.Clear();
			gameStoryBoard.GameOver -= handleGameOver;
			gameStoryBoard.Dispose();
			gameStoryBoard = null;
		}


		private void loadHighScores(int? score) {
			highScoreStoryBoard = (score == null) ? new HighScoreStoryBoard() : new HighScoreStoryBoard(score.Value);
			highScoreStoryBoard.ShowMenu += new Action(handleHighscoreShowMenu);
			highScoreStoryBoard.Dock = DockStyle.Fill;
			Controls.Add(highScoreStoryBoard);
		}

		private void unloadHighScores() {
			Controls.Clear();
			highScoreStoryBoard.ShowMenu -= handleHighscoreShowMenu;
			highScoreStoryBoard.Dispose();
			highScoreStoryBoard = null;
		}


		private void loadSettings() {

			displaySettingsStory = new DisplaySettingsStory();
			displaySettingsStory.ShowMenu += new Action(handleSettingsShowMenu);
			displaySettingsStory.Dock = DockStyle.Fill;
			Controls.Add(displaySettingsStory);
		}

		private void unloadSettings() {
			Controls.Clear();
			displaySettingsStory.ShowMenu -= handleSettingsShowMenu;
			displaySettingsStory.Dispose();
			displaySettingsStory = null;
		}


		private void loadShutdown() {
			displayShutdownStory = new DisplayShutdownStory();
			displayShutdownStory.Dock = DockStyle.Fill;
			displayShutdownStory.Displayed += new Action(handleShutdownDisplayed);
			Controls.Add(displayShutdownStory);
		}

		private void unloadShutdown() {
			Controls.Clear();
			displayShutdownStory.Displayed -= handleShutdownDisplayed;
			displayShutdownStory.Dispose();
			displayShutdownStory = null;
		}
	}
}

A typical story contains a few controls and a sparse amount of logic. The following is the Game Story and a custom control called the LevelCanvas which is responsible for drawing the actors of the universe on the screen. The LevelCanvas derives from a custom control that uses a manual double buffering scheme that I’ve written about in some of my previous posts.

using System.Windows.Forms;
using UserInterface.GameScreen.Gameplay;

namespace UserInterface.GameScreen.Presentation {
	public class GameStory : UserControl {
		private TableLayoutPanel panel;
		private GameStatisticsView headsUpDisplay;
		private LevelCanvas levelUserControl;

		public GameStory(Game game) {
			headsUpDisplay = new GameStatisticsView(game.GameStatistics);
			headsUpDisplay.Dock = DockStyle.Fill;

			levelUserControl = new LevelCanvas(game);
			levelUserControl.Dock = DockStyle.Fill;

			panel = new TableLayoutPanel();
			panel.ColumnStyles.Add(new ColumnStyle() { SizeType = SizeType.Percent, Width = 100.0f });
			panel.RowStyles.Add(new RowStyle() { SizeType = SizeType.Absolute, Height = 48.0f });
			panel.RowStyles.Add(new RowStyle() { SizeType = SizeType.Percent, Height = 100.0f });
			panel.Dock = DockStyle.Fill;
			panel.Controls.Add(headsUpDisplay, 0, 0);
			panel.Controls.Add(levelUserControl, 0, 1);

			Controls.Add(panel);
		}
	}

	public class LevelCanvas : DoubleBufferedUserControl {
		private Game game;
		private Level currentLevel;

		public LevelCanvas(Game game) {
			this.game = game;

			this.BorderStyle = BorderStyle.FixedSingle;

			game.StartLevel += new Action<Level>(handleStartLevel);
			game.LevelCompleted += new Action<SessionStatistics>(handleLevelCompleted);
			game.LevelOver += new Action(handleLevelOver);
		}

		override protected void Dispose(bool disposing) {
			base.Dispose(disposing);

			if (disposing) {
				game.StartLevel -= handleStartLevel;
				game.LevelCompleted -= handleLevelCompleted;
				game.LevelOver -= handleLevelOver;
			}
		}

		override protected void Draw(Graphics graphics) {
			if (currentLevel == null)
				return;

			graphics.InterpolationMode = InterpolationMode.Bicubic;
			graphics.PixelOffsetMode = PixelOffsetMode.HighSpeed;
			graphics.SmoothingMode = SmoothingMode.AntiAlias;

			foreach (Actor actor in currentLevel.Actors) {
				try {
					actor.View.Draw(graphics, ClientRectangle);
				} catch (Exception E) {
					System.Diagnostics.Trace.WriteLine(E);
				}
			}
		}

		private void handleLevelChanged() {
			if (InvokeRequired) {
				Invoke(new Action(handleLevelChanged));
				return;
			}

			Draw();
		}

		private void handleLevelCompleted(SessionStatistics statistics) {
			if (InvokeRequired) {
				Invoke(new Action<SessionStatistics>(handleLevelCompleted), statistics);
				return;
			}

			currentLevel.Stop();
			currentLevel.LevelChanged -= handleLevelChanged;
			currentLevel = null;

			Invalidate();
		}

		private void handleLevelOver() {
			if (InvokeRequired) {
				Invoke(new Action(handleLevelOver));
				return;
			}

			currentLevel.Stop();
			currentLevel.LevelChanged -= handleLevelChanged;
			currentLevel = null;

			Invalidate();
		}

		private void handleStartLevel(Level level) {
			if (InvokeRequired) {
				Invoke(new Action<Level>(handleStartLevel));
				return;
			}

			currentLevel = level;
			currentLevel.LevelChanged += new Action(handleLevelChanged);
			currentLevel.User.Behavior = new KeyboardActorBehavior(currentLevel, this);

			currentLevel.Start();

			Invalidate();
		}
	}
}

Gameplay

Design

Much of the gameplay design was focused on providing a positive end user experience. The end user experience revolves around making the gameplay predictable, so that the end user could learn how to play quickly, then shifts to introduce new dynamics keeping the experience fresh. The core concepts that constitute the end user experience can be summarized as:

• Mechanics – how things in the game universe behave
• Incentives – making the end user want to play the game again and again
• Extras – making the game more interesting and requiring new strategies

Mechanics

• The end user is given the ability to maneuver about the universe and to fire weapons. The user is able to issue commands to move the ship north, east, south or west. Each command results in a small amount of thrust being produced
• A user can rotate the ship’s weapons to the target an object in the universe and engage the weapons to emit projectiles. Projectiles follow the same rules as every other object in the universe
• The user is given a fixed number of health points. Each time a ship collides with another object in the universe, both objects have their health depleted by a fixed amount. If the total points goes to zero, the user has two additional lives to use. Once all the lives have been used up, the game is over
• All enemies in the universe will attempt to destroy the user at all costs

Incentives

• Each time a user destroys an object in the universe, they may receive a variable amount of points that contributes to their overall score

Extras

• The head-up display will flash and then fade back to normal whenever a value changes
• An object’s overall health can be determined by the object’s opacity on the screen. A completely healthy object will be full opaque and the closer an object is to be destroyed, the more transparent it will appear
• When an object is destroyed, it may reveal power-ups that were hidden inside or breakup into smaller pieces of debris. Power-ups come in the following flavors:
  • Health – Set’s the object’s health to 100%
  • Engine – Increases the propulsion of the object’s engine
  • Weapon – Replaces the standard weapon with three standard weapons

Implementation

Game state

The Level class is responsible for driving the game in terms of notifying the UI to redraw the universe and for evolving the universe according to the design rules. The main method of interest is the handleTick method, which is responsible for running through the objects in the universe and then firing off different events based on the state of the universe. The class also takes care of the process of breaking an object into debris and applying non-physical behavior to collisions.

using System;
using System.Collections.Generic;
using Library.Mathematics;
using UserInterface.GameScreen.Gameplay.Behavior;
using UserInterface.GameScreen.Physics;

namespace UserInterface.GameScreen.Gameplay {
	public class Level {
		static private Random RNG;

		static Level() {
			RNG = new Random((int)(DateTime.Now.Ticks & 0xffffff));
		}

		public event Action LevelChanged;
		public event Action<SessionStatistics> LevelCompleted;
		public event Action UserDestroyed;
		public event Action<int> UserScored;

		private LevelStatistics levelStatistics;
		private TimePiece timePiece;
		private PhysicsEngine physicsEngine;
		
		public List<Actor> Actors { get; protected set; }
		public UserActor User { get; protected set; }

		public Level(double width, double height) {
			physicsEngine = new PhysicsEngine(width, height);
			physicsEngine.Collided += new Action<Actor, Actor>(handleCollided);

			levelStatistics = new LevelStatistics();

			timePiece = new TimePiece();
			timePiece.Tick += new Action(handleTick);

			User = new UserActor();
			Actors = new List<Actor>() { User };
		}

		public void Start() {
			timePiece.Start();
		}

		public void Stop() {
			timePiece.Stop();
		}

		private List<Actor> breakUp(Actor actor) {
			List<Actor> actors = new List<Actor>();
			if (actor.Body.Radius <= 6)
				return actors;

			if (actor.GetType().Equals(typeof(PowerUpNeutralActor)))
				return actors;

			for (int n = 0; n < 3; n++) {
				Actor fragment = null;

				if (0.4 * actor.Body.Radius == 6.0) {
					int x = RNG.Next(0, 10);
					if (x == 0) {
						fragment = new HealthPowerUpNeutralActor();
					} else if (x == 1) {
						fragment = new EnginePowerUpNeutralActor();
					} else if (x == 2) {
						fragment = new WeaponPowerUpNeutralActor();
					} else {
						fragment = new DebrisNeutralActor();
					}
				} else {
					fragment = new DebrisNeutralActor();
				}

				fragment.Body = new Body() {
					CurrentMass = 0.1 * actor.Body.StartingMass,
					Radius = 0.4 * actor.Body.Radius
				};

				fragment.AngularMovement = new AngularMovement() {
					Acceleration = actor.AngularMovement.Acceleration,
					Heading = actor.AngularMovement.Heading,
					Velocity = actor.AngularMovement.Velocity
				};


				fragment.LinearMovement = new LinearMovement() {
					Acceleration = new Vector(2, (i) => actor.LinearMovement.Acceleration[i]),
					Location = new Vector(2, (i) => actor.LinearMovement.Location[i]),
					Velocity = new Vector(2, (i) => actor.LinearMovement.Velocity[i])
				};

				fragment.Points = 0;

				fragment.Behavior = new MeanderActorBehavior(fragment);

				Vector direction = new Vector(2);
				direction[0] = Math.Cos((n * 120.0) * (Math.PI / 180.0));
				direction[1] = Math.Sin((n * 120.0) * (Math.PI / 180.0));

				fragment.LinearMovement.Location += (actor.Body.Radius * 0.5) * direction;
				fragment.LinearMovement.Velocity = (0.3 * actor.LinearMovement.Velocity.Length()) * direction;

				actors.Add(fragment);
			}

			return actors;
		}

		private void handleCollided(Actor A, Actor B) {
			bool aIsPowerUp = A is PowerUpNeutralActor;
			bool bIsPowerUp = B is PowerUpNeutralActor;
			if (!(aIsPowerUp ^ bIsPowerUp))
				return;

			PowerUpNeutralActor powerUpActor = null;
			Actor receipentActor = null;
			if (aIsPowerUp) {
				powerUpActor = A as PowerUpNeutralActor;
				receipentActor = B;
			} else {
				powerUpActor = B as PowerUpNeutralActor;
				receipentActor = A;
			}

			if (receipentActor is BulletUserActor || receipentActor is BulletEnemyActor)
				return;

			powerUpActor.Apply(receipentActor);
		}

		private void handleTick() {
			physicsEngine.Step(0.1, Actors);

			List<Actor> actorsToAdd = new List<Actor>();
			for (int n = 0; n < Actors.Count; n++) {

				if (Actors[n].Body.CurrentMass <= 0.0) {
					if (Actors[n].Equals(User)) {
						userDestroyed();
					} else {
						if (Actors[n] is BulletUserActor || Actors[n] is BulletEnemyActor) {

						} else {
							userScored(Actors[n].Points);
							actorsToAdd.AddRange(breakUp(Actors[n]));
						}

						Actors.RemoveAt(n--);
					}
				}
			}
			Actors.AddRange(actorsToAdd);

			if (isLevelComplete())
				levelCompleted();

			int actorCount = Actors.Count;
			for (int n = 0; n < actorCount; n++)
				Actors[n].Step(0.1);

			levelChanged();
		}

		private bool isLevelComplete() {
			for (int n = 0; n < Actors.Count; n++) {
				if (Actors[n] is BulletEnemyActor || Actors[n] is BulletUserActor)
					continue;

				if (Actors[n] is EnemyActor || Actors[n] is NeutralActor)
					return false;
			}
			return true;
		}

		private void levelChanged() {
			if (LevelChanged != null)
				LevelChanged();
		}

		private void levelCompleted() {
			if (LevelCompleted != null) {
				levelStatistics.TimeTaken = TimeSpan.FromMilliseconds(timePiece.ElapsedTimeMilliseconds);
				LevelCompleted(new SessionStatistics() {
					LevelStatistics = levelStatistics
				});
			}
		}

		private void userDestroyed() {
			levelStatistics.LivesLost++;

			if (UserDestroyed != null)
				UserDestroyed();
		}

		private void userScored(int points) {
			levelStatistics.Scored += points;

			if (UserScored != null)
				UserScored(points);
		}
	}
}

Physics

One of the key features of the game is providing a realistic enough perception of a simulated universe and that the user is able to interact with objects. This is done by providing a handful of basic physical attributes that are implemented by the PhysicsEngine class. The core responsibilities of the class is to apply physical rules over the course of a slice of time. Objects in the universe can be destroyed and created during this process.

Collisions between actors is handled through the typical conservation of linear momentum approach. Two objects, and , with momentums, and , must have the same amount of momentum before and after the collision. Assuming a totally elastic collision, we end up with . Momentum is defined as , where is the mass of an object and is its velocity. Since no mass is being lost in the collision, the velocities must change as a result. Solving for the velocities yields the trajectories that the objects will follow after the collision.

Collisions between actors and walls is once again handled through the typical conservation of momentum. Since the wall is of infinite mass and has zero velocity, the colliding object’s velocity is reflected about the wall’s normal vector.

Any object that escapes or has invalid numerical data is removed from the universe.

using System;
using System.Collections.Generic;
using Library.Mathematics;

namespace UserInterface.GameScreen.Physics {
	public class PhysicsEngine {
		public event Action<Actor, Actor> Collided;

		private double Width, Height;

		public PhysicsEngine(double width, double height) {
			Width = width;
			Height = height;
		}

		public void Step(double dt, List<Actor> actors) {
			// Actor-Actor interactions
			for (int n = 0; n < actors.Count; n++)
				for (int m = n + 1; m < actors.Count; m++)
					if (intersects(actors[n], actors[m])) {
						collide(actors[n], actors[m]);
					}

			// Actor-Wall interactions
			for (int n = 0; n < actors.Count; n++) {
				Vector l = actors[n].LinearMovement.Location;
				Vector v = actors[n].LinearMovement.Velocity;
				double r = actors[n].Body.Radius;

				if (l[0] - r < 0)
					l[0] = r;

				if (l[0] + r > Width)
					l[0] = Width - r;

				if (l[1] - r < 0)
					l[1] = r;

				if (l[1] + r > Height)
					l[1] = Height - r;

				Vector N = getWallNormal(l, r);
				if (N != null)
					actors[n].LinearMovement.Velocity = v - (2 * N.dot(v)) * N;
			}

			// get rid of anything that escaped the universe.
			for (int n = 0; n < actors.Count; n++) {
				Vector l = actors[n].LinearMovement.Location;
				double r = actors[n].Body.Radius;

				if (double.IsInfinity(l[0]) || double.IsInfinity(l[1])) {
					actors.RemoveAt(n--);
					continue;
				}

				if (double.IsNaN(l[0]) || double.IsNaN(l[1])) {
					actors.RemoveAt(n--);
					continue;
				}

				if (l[0] - r < -5 || l[0] + r > Width + 5 || l[1] - r < -5 || l[1] + r > Height + 5)
					actors.RemoveAt(n--);
			}
		}

		private bool intersects(Actor A, Actor B) {
			Vector pointDistance = (A.LinearMovement.Location - B.LinearMovement.Location);
			double touchingPointDistance = (A.Body.Radius + B.Body.Radius);
			return pointDistance.Length() <= touchingPointDistance;
		}

		private void collide(Actor A, Actor B) {
			Vector a = (1.0 / (A.Body.CurrentMass + B.Body.CurrentMass)) * ((A.Body.CurrentMass - B.Body.CurrentMass) * A.LinearMovement.Velocity + (2 * B.Body.CurrentMass) * B.LinearMovement.Velocity);
			Vector b = (1.0 / (A.Body.CurrentMass + B.Body.CurrentMass)) * ((B.Body.CurrentMass - A.Body.CurrentMass) * B.LinearMovement.Velocity + (2 * A.Body.CurrentMass) * A.LinearMovement.Velocity);

			A.LinearMovement.Velocity = a;
			B.LinearMovement.Velocity = b;

			A.Body.CurrentMass -= 2.5;
			B.Body.CurrentMass -= 2.5;

			if (Collided != null)
				Collided(A, B);
		}

		private Vector getWallNormal(Vector l, double r) {
			Vector N = null;
			if (l[0] - r <= 0.0) {
				// left side of the body is against the left side of the frame
				if (l[1] - r <= 0.0) {
					// top of the body is against the top of the frame
					// => two point of contact
					N = new Vector(2, (i) => i == 0 ? 1 : -1);
				} else if (l[1] + r >= Height) {
					// bottom of the body is against the bottom of the frame
					// => two points of contact
					N = new Vector(2, (i) => i == 0 ? 1 : 1);
				} else {
					// body is between the top and bottom
					// => single point of contact
					N = new Vector(2, (i) => i == 0 ? 1 : 0);
				}
			} else if (l[0] + r >= Width) {
				// right side of the body is against the right side of the frame
				if (l[1] - r <= 0.0) {
					// top of the body is against the top of the frame
					// => two points of contact
					N = new Vector(2, (i) => i == 0 ? -1 : -1);
				} else if (l[1] + r >= Height) {
					// bottom of the body is against the bottom of the frame
					// => two points of contact
					N = new Vector(2, (i) => i == 0 ? -1 : 1);
				} else {
					// body is between the top and bottom
					// => single point of contact
					N = new Vector(2, (i) => i == 0 ? -1 : 0);
				}
			} else {
				// body is between the left and right
				if (l[1] - r <= 0.0) {
					// top of the body is against the top of the frame
					// => single point of contact
					N = new Vector(2, (i) => i == 1 ? -1 : 0);
				} else if (l[1] + r >= Height) {
					// bottom of the body is against the bottom of the frame
					// => single point of contact
					N = new Vector(2, (i) => i == 1 ? +1 : 0);
				} else {
					// body is between the top and bottom
					// => zero points of contact
				}
			}
			return N;
		}
	}
}

Enemy Targeting

To make the game more interesting, the enemy ships are able to target the user’s ship. Since the enemy must adhere to the same mechanics that the user does, it incrementally rotates clockwise and counterclockwise to keep the user in target. When the user is within an acceptable window of error, the enemy will fire its weapons in hopes of hitting the user.

The first approach here was to simply keep track of which direction the enemy is rotating and to rotate next in the direction that minimized the distance in radians between the enemy’s heading and the direction that the user is traveling. Unfortunately, this will result in overshooting the desired destination.

The second approach is to take into account how long it will take the rotation to slow down given its current angular velocity. If there is enough time then the rotation will increase, otherwise it will slowdown. Given the second approach, the enemies exhibit a reasonable accurate behavior of tracking the user’s ship.

using System;
using Library.Mathematics;
using UserInterface.GameScreen.Gameplay.Components;
using UserInterface.GameScreen.Physics;

namespace UserInterface.GameScreen.Gameplay.Behavior {
	public class TargetingActorBehavior : IBehavior {
		private Actor toControl;
		private Actor toTarget;
		private Level level;

		public TargetingActorBehavior(Actor toControl, Actor toTarget, Level level) {
			this.toControl = toControl;
			this.toTarget = toTarget;
			this.level = level;
		}

		public void Step(double dt) {
			Vector d = toTarget.LinearMovement.Location - toControl.LinearMovement.Location;
			Vector h = toControl.AngularMovement.HeadingVector;
			double radsToTarget = d.RadsBetween(h);
			
			double a = Math.PI / 5.0;

			AngularMovement cw = new AngularMovement();
			cw.Heading = toControl.AngularMovement.Heading - a;
			double radsToTargetCW = d.RadsBetween(cw.HeadingVector);

			AngularMovement ccw = new AngularMovement();
			ccw.Heading = toControl.AngularMovement.Heading + a;
			double radsToTargetCCW = d.RadsBetween(ccw.HeadingVector);

			double v = toControl.AngularMovement.Velocity;

			if (v < 0) {
				// rotating cw
				if (radsToTargetCW < radsToTargetCCW) { 
					// continuing to rotate cw will bring us closer to zero
					// first, check to see if we are going to overshoot if we
					// continue to rotate cw.
					double radsToStop = 1.5 * v * (v + -a * dt) / (-a * dt);
					if (radsToTarget <= radsToStop) {
						toControl.AngularEngine.Rotate(Rotation.CounterClockwise);
					} else if (radsToTarget > radsToStop) {
						toControl.AngularEngine.Rotate(Rotation.Clockwise);
					}
				} else if (radsToTargetCW >= radsToTargetCCW) { 
					// continuing to rotate cw will bring us further away from zero
					// => rotate the opposite direction
					toControl.AngularEngine.Rotate(Rotation.CounterClockwise);
				}
			} else if (v == 0) {
				// not rotating
				// pick which ever direction is closer to zero
				if (radsToTargetCW < radsToTargetCCW) {
					toControl.AngularEngine.Rotate(Rotation.Clockwise);
				} else if(radsToTargetCW >= radsToTargetCCW) {
					toControl.AngularEngine.Rotate(Rotation.CounterClockwise);
				}
			} else if (v > 0) { 
				// rotating ccw
				if (radsToTargetCCW < radsToTargetCW) {
					// continuing to rotate ccw will bring us closer to zero
					// first, check to see if we are going to overshoot if we
					// continue to rotate ccw.
					double radsToStop = 1.5 * v * (v + a * dt) / (a * dt);
					if (radsToTarget <= radsToStop) {
						toControl.AngularEngine.Rotate(Rotation.Clockwise);
					} else if (radsToTarget > radsToStop) {
						toControl.AngularEngine.Rotate(Rotation.CounterClockwise);
					}
				} else if (radsToTargetCCW >= radsToTargetCW) {
					// continuing to rotate ccw will bring us further away from zero
					// => rotate the opposite direction
					toControl.AngularEngine.Rotate(Rotation.Clockwise);
				}
			}

			// If the angle is less than five degrees (pi/36), then fire.
			if (radsToTarget < Math.PI / 36.0)
				level.Actors.AddRange(toControl.Weapon.Fire());
		}
	}
}

Space Cowboy: A Shoot’em up game in Haskell: Part 2

Introduction

A couple months back I wrote about a shoot’em up game that I was planning on making in Haskell. My goal was to make something a little more elaborate than my previous games and also take my understanding of Haskell further. Ultimately, I did not use Haskell and instead decided to use C# for the final product (main reason was productivity). Nonetheless, I felt it was worthwhile to post the work that was done on the prototype and talk a bit about the development process.

To get started, here is a quick demo of the features that were implemented in the prototype, namely, the user’s ability to navigate the ship and fire its weapons using the keyboard.

As others have put it, programming in Haskell is like writing a proof, so in similar vein I’m going to present the core modules of the prototype and then build upon those to present the more complicated ones (which follows more or less the development process). The code that is posted here was authored in Leksah, which replaces a lot of common syntax with “source candy”, so hopefully you will be able to deduce the formal syntax.

Mathematics Module

Since I didn’t have a lot experience in designing a game like this in Haskell, I decided I’d start with the basic mathematical model of the game. I thought about the concepts that were needed to represent bodies in a universe and settled on points, vectors and shapes to represent the ideas I had brewing in my head.

Point

The Point data type represents a single coordinate pair on the Euclidean Plane.

type Coordinate = Float

data Point = Point Coordinate Coordinate

pointZero :: Point
pointZero = Point 0.0 0.0

type Distance = Float

pointDistance :: Point →  Point →  Distance
pointDistance (Point x y) (Point u v) = sqrt ((x - u)↑2 + (y - v)↑2)

Vector

The Vector data type serves two purposes: the first is to describe the translation of points along the plane and the second is to describe the direction in which bodies are moving. The usual set of operations on Euclidean Vectors were implemented.

data Vector = Vector Coordinate Coordinate

instance Eq Vector where
    (Vector x y) ≡ (Vector u v) = (x ≡ u) ∧ (y ≡ v)
    (Vector x y) ≠ (Vector u v) = (x ≠ u) ∨ (y ≠ v)

vectorZero :: Vector
vectorZero = Vector 0.0 0.0

vectorUp :: Vector
vectorUp = Vector 0 1

vectorLeft :: Vector
vectorLeft = Vector (-1) 0

vectorDown :: Vector
vectorDown = Vector 0 (-1)

vectorRight :: Vector
vectorRight = Vector 1 0

vectorIdentity :: Vector →  Vector
vectorIdentity (Vector x y) = Vector x y

vectorAdd :: Vector →  Vector →  Vector
vectorAdd (Vector x y) (Vector x' y') = Vector (x + x') (y + y')

vectorDotProduct :: Vector →  Vector →  Float
vectorDotProduct (Vector x y) (Vector x' y') = (x * x') + (y * y')

vectorScale :: Float →  Vector →  Vector
vectorScale a (Vector x' y') = Vector (a * x') (a * y')

vectorMinus :: Vector →  Vector →  Vector
vectorMinus (Vector x y) (Vector x' y') = Vector (x - x') (y - y')

vectorMagnitude :: Vector →  Float
vectorMagnitude (u) = sqrt $ vectorDotProduct u u

vectorNormalize :: Vector →  Vector
vectorNormalize (u)
    | vectorMagnitude u ≡ 0 = Vector 0 0
    | otherwise = vectorScale (1.0 / (vectorMagnitude u)) u

pointAdd :: Point →  Vector →  Point
pointAdd (Point x y) (Vector u v) = Point (x + u) (y + v)

Shape

Bodies are represented as simple shapes. In the initial round of design, rectangles and ellipses were considered, but for the purpose of developing a prototype, I settled on circles. The benefit is that determining the minimum distance between two circles is simpler and consequently so is detecting collisions.

data Shape =
    Circle {
        center :: Point,
        radius :: Distance
    }

unitCircle :: Shape
unitCircle = Circle {
    center = pointZero,
    radius = 1.0
    }

shapeDistance :: Shape →  Shape →  Distance
shapeDistance (Circle c r) (Circle c' r') = (pointDistance c c') - (r + r')

shapeCollide :: Shape →  Shape →  Bool
shapeCollide a b = distance ≤ 0
    where
        distance = shapeDistance a b

Physics Module

Now that I had a mathematical model of the objects that would be considered, it made sense to tackle the physics model of the game. Bodies in the game are treated as simple Rigid Bodies with non-rotational Kinematics.

Movement

To capture the kinematics of the bodies, the Movement data type captures the location, velocity and acceleration of a body. The heart of the physics engine is captured in movementEvolved- it is responsible for updating the location, velocity and acceleration over a slice of time.

type Velocity = Vector

type Acceleration = Vector

data Movement = Movement {
    location :: Point,
    velocity :: Velocity,
    acceleration :: Acceleration
    }

movementZero :: Movement
movementZero = Movement {
    location = pointZero,
    velocity = vectorZero,
    acceleration = vectorZero
    }

type Time = Float

movementEvolve :: Movement →  Time →  Movement
movementEvolve (Movement l v a) t = Movement l' v' a'
    where a' = vectorIdentity a
          v' = vectorAdd (vectorScale t a) v
          l' = pointAdd l (vectorAdd (vectorScale (t * t / 2.0) a) (vectorScale t v))

Body

Each physical body in the universe has a mass, shape and movement. The second key component of the physics engine is the process of detecting collisions. bodiesCollide is responsible for taking a collection of bodies and for each one, collecting the bodies that collide with it and then supplying that body and its contacts to a function that determines the outcome of the collision.

type Mass = Float

data Body a = Body {
        shape :: Shape,
        mass :: Mass,
        movement :: Movement,
        description :: a
    }

bodyAddMass :: Body a →  Mass →  Body a
bodyAddMass (Body s m mo d) amount = Body {
        shape = s,
        mass = m + amount,
        movement = mo,
        description = d
    }

bodiesCollide :: [Body a] →  (Body a →  [Body a] →  [Body a]) →  [Body a]
bodiesCollide xs f = apply [] xs f

apply :: [Body a] →  [Body a] →  (Body a →  [Body a] →  [Body a]) →  [Body a]
apply _ [] _ = []
apply leftList (item:rightList) mapping = processed ⊕ remaining
    where
        processed =
            if null collisions
            then [item]
            else mapping item collisions
        collisions = filter (λx →  bodyCollide (item, x)) (leftList ⊕ rightList)
        remaining = apply (leftList ⊕ [item]) rightList mapping

bodyCollide :: (Body a, Body a) →  Bool
bodyCollide (a, b) = shapeCollide (shape a) (shape b)

bodyEvolve :: Body a →  Time →  Body a
bodyEvolve (Body (Circle c r) mass m d) t = Body {
    shape = Circle (location m') r,
    mass = mass,
    movement = m',
    description = d
    }
    where
        m' = movementEvolve m t

Universe

The game universe spans the plane, contains a collection of bodies and a sense of time. The universe brings together the two main components of the physics engine and exposes a way to remove items from the universe.

data Universe a = Universe {
    bodies :: [Body a],
    time :: Time
    }

universeAddBodies :: Universe a →  [Body a] →  Universe a
universeAddBodies u bs = Universe {
        bodies = (bodies u) ⊕ bs,
        time = time u
    }

universeCollide :: Universe a →  (Body a →  [Body a] →  [Body a]) →  Universe a
universeCollide (Universe bs t) f = Universe {
    bodies = bodiesCollide bs f,
    time = t
    }

universeEvolve :: Universe a →  Time →  Universe a
universeEvolve u t = Universe {
    bodies = map (λb →  bodyEvolve b t) (bodies u),
    time = t + (time u)
    }

universeFilter :: (Universe a) →  (Body a →  Bool) →  (Universe a)
universeFilter u p = Universe {
        bodies = filter p (bodies u),
        time = time u
    }

Game Module

Now that the physics of the universe have been described, we can start describing specific aspects of the game.

Weapon

Each ship has some number of weapons capable of doing some amount of damage and can fire projectiles with a given acceleration.

data Weapon =
    Torpedo

type Damage = Int

weaponDamage :: Weapon →  Damage
weaponDamage Torpedo = 2
weaponDamage _ = defined

type Thrust = Float

weaponThrust :: Weapon →  Thrust
weaponThrust Torpedo = 0.5
weaponThrust _ = undefined

Engine

Each ship has some number of engines capable of providing some amount of acceleration.

data Engine =
    Rocket

engineThrust :: Engine →  Thrust
engineThrust Rocket = 0.05
engineThrust _ = undefined

Ship

A ship is any body in the universe, described here as either a Projectile or a Fighter. It is what will be captured in the parametric type of the Universe data type.

data Ship =
    Projectile Thrust Damage
    | Fighter Engine Weapon

shipEngines :: Ship →  [Engine]
shipEngines (Fighter e _) = [e]
shipEngines _ = []

shipThrust :: Ship →  Thrust
shipThrust s = sum $ map engineThrust (shipEngines s)

shipWeapons :: Ship →  [Weapon]
shipWeapons (Fighter _ w) = [w]
shipWeapons _ = []

shipFireWeapons :: Ship →  [Ship]
shipFireWeapons s = map newProjectile $ shipWeapons s

Projectile

A projectile is any body fired from a weapon.

newProjectile :: Weapon →  Ship
newProjectile w = Projectile (weaponThrust w) (weaponDamage w)

projectileToBody :: Ship →  Movement →  Body Ship
projectileToBody p@(Projectile t d) m@(Movement l v a) = Body {
        shape = Circle {
            center = pointAdd l (vectorScale 1.1 vectorUp),
            radius = 0.2
        },
        movement = Movement {
            location = pointAdd l (vectorScale 1.25 vectorUp),
            velocity = vectorScale t vectorUp,
            acceleration = vectorIdentity a
        },
        description = p,
        mass = 1
    }

Fighter

The Fighter represents the end user and has a number of functions for controlling it. Notably, firing of the weapons and navigating the plane.

shipIsFighter :: Ship →  Bool
shipIsFighter (Fighter _ _) = True
shipIsFighter _ = False

fighterDestroyed :: (Universe Ship) →  Bool
fighterDestroyed (Universe bs t) = null $ filter (λb →  shipIsFighter (description b)) bs

fighterMove :: Body Ship →  Vector →  [Body Ship]
fighterMove (Body s mass (Movement l v a) d) direction = [Body {
        movement = Movement {
            location = l,
            velocity = vectorAdd δ v,
            acceleration = a
        },
        mass = mass,
        shape = s,
        description = d
    }]
    where
        δ = vectorScale (shipThrust d) direction

fighterFire :: Body Ship →  [Body Ship]
fighterFire b@(Body s mass m d) = [b] ⊕ bs
   where
        bs = map (λx →  projectileToBody x m) $ projectiles
        projectiles = shipFireWeapons d
        direction = vectorUp

universeActOnFighter :: (Universe Ship) →  (Body Ship →  [Body Ship]) →  (Universe Ship)
universeActOnFighter u f = Universe {
        bodies = bodiesActOnFighter (bodies u) f,
        time = time u
    }

bodiesActOnFighter :: [Body Ship] →  (Body Ship →  [Body Ship]) →  [Body Ship]
bodiesActOnFighter [] _ = []
bodiesActOnFighter (b:bs) f = b' ⊕ bs'
    where
        b' = bodyActOnFighter b f
        bs' = bodiesActOnFighter bs f

bodyActOnFighter :: Body Ship →  (Body Ship →  [Body Ship]) →  [Body Ship]
bodyActOnFighter b f
    | shipIsFighter $ description b = f b
    | otherwise = [b]

Graphics Module

The Graphics module deals with mapping the above data types into their corresponding HOpenGL counterparts. (I looked at a number of Haskell’s graphics libraries and ultimately chose to go with HOpenGL since I was the most familiar with OpenGL.)

coordinateToGLfloat :: Coordinate →  GLfloat
coordinateToGLfloat c = realToFrac c

type OpenGLPoint = (GLfloat, GLfloat, GLfloat)

pointToOpenGLPoint :: Geometry.Point →  OpenGLPoint
pointToOpenGLPoint (Geometry.Point x y) = (x', y', 0.0::GLfloat)
    where
        x' = coordinateToGLfloat x
        y' = coordinateToGLfloat y

type OpenGLView = [OpenGLPoint]

shapeToView :: Shape →  OpenGLView
shapeToView (Circle c r) = map pointToOpenGLPoint points
    where
        points = map (λθ →  Geometry.Point (r * (cos θ)) (r * (sin θ))) degrees
        degrees = map (λn →  n * increment ) [0..steps - 1]
        increment = 2.0 * pi / steps
        steps = 16

shipToView :: Ship →  OpenGLView
shipToView (Projectile _ _) = [ ... ]
shipToView (Fighter _ _) = [ ... ]
shipToView _ = undefined

openGLPointTranslate :: OpenGLPoint →  OpenGLPoint →  OpenGLPoint
openGLPointTranslate (x, y, z) (dx, dy, dz) = (x + dx, y + dy, z + dz)

openGLViewTranslate :: OpenGLView →  OpenGLPoint →  OpenGLView
openGLViewTranslate xs d = map (openGLPointTranslate d) xs

openGLPointToIO :: OpenGLPoint →  IO ()
openGLPointToIO (x, y, z) = vertex $ Vertex3 x y z

openGLViewToIO :: OpenGLView →  IO ()
openGLViewToIO ps = mapM_ openGLPointToIO ps

displayBody :: Body Ship →  IO()
displayBody (Body s mass m d) =
    color (Color3 (1.0::GLfloat) 1.0 1.0) >>
    renderPrimitive LineLoop ioShip
    where
        ioBody = openGLViewToIO $ openGLViewTranslate (shapeToView s) dl
        ioShip = openGLViewToIO $ openGLViewTranslate (shipToView d) dl
        dl = pointToOpenGLPoint l
        l = location m

displayUniverse :: Universe Ship →  IO ()
displayUniverse universe = mapM_ displayBody $ bodies universe

Main Module

The Main Module is the glue that brings together all of the other modules. Much of the functions described here are for gluing together the OpenGL callbacks to the functions described above.

theUniverse :: Universe Ship
theUniverse = ...

main :: IO()
main = do
    (programName, _) ←  getArgsAndInitialize
    initialDisplayMode $= [ DoubleBuffered ]
    createWindow "Space Cowboy"
    universe ←  newIORef theUniverse
    displayCallback $= (display universe)
    idleCallback $= Just (idle universe)
    keyboardMouseCallback $= Just (keyboardMouse universe)
    mainLoop

display :: IORef (Universe Ship) →  IO ()
display ioRefUniverse = do
    clear [ ColorBuffer ]
    loadIdentity
    scale 0.2 0.2 (0.2::GLfloat)
    universe ←  get ioRefUniverse
    displayUniverse universe
    swapBuffers
    flush

idle :: IORef (Universe Ship) →  IO ()
idle ioRefUniverse = do
    universe ←  get ioRefUniverse
    ioRefUniverse $= stepUniverse universe game
    threadDelay 10
    postRedisplay Nothing

stepUniverse :: (Universe Ship) →  (Universe Ship)
stepUniverse u = collided
    where
        collided = universeCollide filtered collide
        filtered = universeFilter evolved inBounds
        evolved = universeEvolve u 0.1

collide :: Body Ship →  [Body Ship] →  [Body Ship]
collide b@(Body s mass m (Projectile d t)) xs = []
collide b _ = [b]

inBounds :: Body Ship →  Bool
inBounds b@(Body _ _ (Movement (Geometry.Point x y) _ _) d)
    | shipIsFighter d = True
    | otherwise = and [abs x < 10, abs y < 10]

keyboardMouse ioRefUniverse key state modifiers position =
    keyboard ioRefUniverse key state

keyboard :: IORef (Universe Ship) →  Key →  KeyState →  IO ()
keyboard ioRefUniverse (Char 'q') Down = do exitSuccess
keyboard ioRefUniverse (Char ' ') Down = fire ioRefUniverse
keyboard ioRefUniverse (SpecialKey KeyLeft) Down = navigate ioRefUniverse vectorLeft
keyboard ioRefUniverse (SpecialKey KeyRight) Down = navigate ioRefUniverse vectorRight
keyboard ioRefUniverse (SpecialKey KeyUp) Down = navigate ioRefUniverse vectorUp
keyboard ioRefUniverse (SpecialKey KeyDown) Down = navigate ioRefUniverse vectorDown
keyboard _ _ _ = return ()

fire :: IORef (Universe Ship) →  IO()
fire ioRefUniverse = do
    universe ←  get ioRefUniverse
    ioRefUniverse $= universeActOnFighter universe fighterFire

navigate :: IORef (Universe Ship) →  Vector →  IO ()
navigate ioRefUniverse direction = do
    universe ←  get ioRefUniverse
    ioRefUniverse $= universeActOnFighter universe (λf →  fighterMove f direction)

Wrap-up

For a month of on-again, off-again work, the prototype turned out reasonably well and I got a lot out of it. I think that as I continue to use Haskell, my brain will slowly switch from thinking in terms of structures of data to flows of data and I will ultimately be able to be more productive in Haskell. Until then, I’m going to stick with my current technology stack and continue to experiment with Haskell. Keep an eye for part three of this series which will go over the completed product.

Water and Wine Problem

Take two containers, and . Initially, is full of water and is full of wine. Remove a teaspoon of water from and put it in , then a teaspoon of the mixture in and put it in . In what proportions are the water and wine now mixed in and ? What are the proportions of water and wine in each container after iterations?

First some assumptions: containers and are identical in volume and both capable of containing the combined fluid of each. The initial amount of fluid in each container is identical. When transferring fluids between the containers, none of the fluid is lost. Rather than focusing on what amount a teaspoon represents, we’ll state that we are going to transfer a percentage, , of to . Likewise, when transferring fluid from to , we’ll use a percentage . Note that the amount that is transferred, , from to has to be equal to the amount that is later transferred, , from to . From that fact we can conclude that . Following these conventions, we arrive at the following formulated events in the problem statement:

	Container A		Container B
	Water	Wine	Water	Wine
Initially, A is full of water and B is full of wine.
Remove a teaspoon of water from A and put it in B,
then a teaspoon of the mixture in B and put it in A.

One way of capturing these events is to model the system, , as a matrix. Each row of a matrix represents a container and each column of the matrix represents the amount of water or wine in the container. The initial state of the system, , is the amount of water and wine in each container. The act of transferring fluid from one container to another and back again is given by which simplifies to . To determine the quantities of water and wine in each container after iterations, we can looks at the recurrence relation which simplifies to .

To figure out a closed form solution to we’ll note that the system is a system of difference equations. The general solution being where is a coefficient based on initial conditions, is the i’th eigenvector and is the i’th eigenvalue, i.e., the i’th solution to .

Following this practice, we arrive at . To find and we solve for and . We go with because it represents a container starting with one type of fluid and none of the other. The solution is . Important to note that the solution represents both containers and one can swap the water and wine labels.

One last thing of interest is to look at the limiting behavior of . As increases, the first term remains constant and the second term tends towards zero given the domain of . Thus, . Thus, no mater what size scope we take, we’ll always arrive at a container containing equal parts water and wine.

An alternative approach to figuring out the limiting behavior is to look directly at . Matrix computations are time consuming, so we’ll want to have a way to compute that minimizes the number of computations. One way to do this is to apply an Eigen Decomposition of a matrix. The idea is that we can decompose a matrix into a product of three matrices: first is the eigenvectors of the matrix, the second has the matrix’s eigenvalues along the diagonal and the third is an inverse of the first. The decomposition looks like the following: with . One important consequence is that we can compute easily now by and as a direct consequence of how is defined, .

Given that knowledge, we can decompose .

Taking the limit leads to the steady state solution of .

One tree many possibilities: Part 3

Introduction

When I first began publishing content on this blog, I wrote a couple of posts entitled One tree many possibilities that covered how to enumerate the sets produced by different counting techniques. You can catch up on the idea in part one and the C# implementation in part two. In this post I’m going to cover how to take the knowledge from the first two posts and derive closed form solutions to each of the counting techniques through analysis of their respective recurrence relations.

Preliminaries

The basic idea is that that the set and each of its elements, , are supplied to a binary operation, , that maps to a subset of . This process is performed iteratively on until the process has been applied to a depth of or the resulting subset becomes the empty set.

Since we can have a variety of conceivable sets, we need to map sets of a given cardinality to a common set of the same cardinality. Let be a bijective function that maps a set to the set of positive integers from 1 to .

k-ary Cartesian Product

The k-ary cartesian product is the way of selecting items from a set where the order of the selection is important and items can be placed back into the set after selection.

The process uses where is an identity function. As an example, here is a graph of the process applied to with :

To count the number of elements, we need to count the number of nodes at depth . We will write this using the following recurrence relation:

If we think of the tree having a height of , then we can label each layer from (at the root) to zero. As a consequence, we can interpret the first statement as a node at depth zero will be considered a leaf node and should be counted once. The second statement says that for each element in we will add up whatever number of leaf nodes were counted in the layer beneath the current layer .

Rearranging the second statement leads to . Reducing further times leads to .

k-Permutations

The permutation and k-permutation is a way of selecting items () from a list where the order of the selection is important but items cannot be placed back into the set after selection.

The process uses where is the set difference operator. We use the set difference because the item is removed from the set upon each selection. As before, here is a graph of the process applied to with :

To count the number of elements, we need to count the number of nodes at depth . (The regular permutation can be counted when .) We will write this using the following recurrence relation:

Using the same labeling scheme as in the k-ary cartesian product, we can interpret the first statement as any node at depth zero will be considered a leaf node and counted once. The second statement says that for each element in we will add up whatever number of leaf nodes were counted in the layer beneath the current layer for the set . We use since we removed an element from .

Rearranging the second statement leads to . Taking times leads to .

Power Set

The power set is the way of selecting zero items to the cardinality of the set items from a set where the order of the selection is not important and items are not placed back into the set after selection.

The process uses where . As before, here is a graph of the process applied to :

To count the number of elements, we need to count the number of nodes in the tree. We will write this using the following recurrence relation:

The first statement says for any node a depth zero we will count it once. The second statement states that for each element in we will add up the result from to . Starting at is a way of encoding that all nodes should be counted. We go up to because there are elements in less than .

Rearranging the second statement leads to . Taking the expression to zero leads to .

k-Combinations

The k-combination is the way of selecting a fixed number of items from a set where the order of the selection is not important and items are not placed back into the set after selection.

The process is identical to the power set.

To count the number of elements, we need to count the number of nodes at depth in the tree. We will write this using the following recurrence relation:

The first statement says for depth zero we will count once, the second statement states that we will add up whatever sum was produced by iterating over from one to and reducing the depth by one. To find the closed form solution, we’ll approach the recurrence relation inductively:

Important to notice that for that we have the unit, for we have the natural numbers, for we have the triangle numbers, for we have the tetrahedral numbers and so on. The generalized sequence is the Figurate number- these numbers constitute Pascal’s Triangle which is one method of calculating combinations.

Space Cowboy: A Shoot’em up game in Haskell: Part 1

It’s the start of a new year and January always marks the return of Antimatroid, The. The past few months I’ve been busy working on a number of project around the house and spending some time working on a few projects for around here. This article serves as an introduction to a shoot’em up game that I’ve been working on since July. Future installments will cover the implementation and design aspects of the project.

Introduction

The past few months I’ve been working on a Shoot’em up game in Haskell and decided that I’d gotten to a point where a writeup was in order. I’ve always enjoyed the genre and I wanted to create something with a degree of complexity greater than my previous arcade games. Along the same lines, I decided to go with Haskell so that I could get a better hang of the language and build something tangible and practical beyond the utilities and solvers I’ve written. The title of the game is a nod to various Space Westerns that inspired me to get started. The following writeup goes over the software development process I applied to the project from specification to implementation.

Specification

Space Cowboy is a single player game consisting of a sequence of levels. The user starts on the first level and plays until he or she has completed the level and progresses onto the next level and so on. Once there are no more levels left, the user has won the game. If a user fails to complete a level, then the game is over. Each level is of a fixed length and contains a fixed number of opponents. To complete a level, the user either gets to the end of the level or destroys all of the opponents. If an opponent destroys the user, then the user does not complete the level and the game is over.

The user and the opponents are represented by ships. Ships start with a fixed number of hit points and lose hit points any time the ship is attacked or it collides with another ship. Once a ship has lost enough hit points to match its initial hit points, then it is considered destroyed. Ships can attack one another using weapons that come in a variety of rates of fire and magnitude of damage. Each ship can can maneuver around the level using engines that come in a variety of thrusts and rates of propulsion. The user’s ship can be maneuvered left, right, up and down and instructed to fire its weapons. Opponents ships are maneuvered by the game. Ships can improve their abilities by colliding with power-ups which upgrade weapons, engines and hit points. Power-ups are produced randomly whenever a ship is destroyed.

A score system keeps track of the user’s progress. When the user starts the game, his or her score is set to zero and increases as he or she plays each level. Whenever a user gets a power-up or destroys a ship, then their score increments proportionally to the magnitude of the power-up or ship destroyed. A user’s score is never decremented. The user is incentivised to play again to obtain a higher score than his or her previous trial.

Requirements

User Interface

The user interface will be a portfolio view consisting of four screens:

• Logo Screen: displays the developer’s logo and copyright information
• Menu Screen: allows the user to start a new game, view high scores and exit the application
• Game Screen: contains information about what level the user is on, their score, the number of lives they have left and the view of the game universe
• High Scores Screen: contains a list of the top five high scores achieved in the game

When the application starts, the user will see the Logo Screen which will transition to the Main Menu Screen after a few seconds. When the user presses the New Game Button, the application will go to the Game Screen. When the user presses the High Scores Button, the application will go to the High Scores Screen. When a user completes their game, they will transition to the High Scores Screen. If the user has a new high score, they will be asked to enter the name they want to associate with the score. The user may go back to the Main Menu Screen by clicking on the Menu Button.

Gameplay

The game universe is a simplified model of the physical universe. The game universe has two spatial dimensions and one temporal dimension. Both spatial dimensions are bounded and residents of the game universe may not exist outside of those boundaries. When the game starts, the user will be at one extreme of these boundaries and must reach the other extreme to complete the level.

Every resident in the game universe has a dimension, heading and location. No two residents of the game universe may occupy the same space at the same time. When two residents collide, their resulting motions will follow Newton’s laws of motion. If the damage done on either body during the collision is material, then the body will be reduced to debris and power-ups.

When a ship fires its engines, the thrust of the engine will advance the ship in the direction indicated by the user with respect to the ship’s heading. When the ship fires its weapons, the ship will experience kickback in accordance with Newton’s third law of motion. As the user’s ship moves through the game universe, the view of the game universe will be centered on the user’s ship.

Another busy month

I have had a busy August and it is looking like September will be equally busy. In August I took a vacation out to San Francisco, CA and enjoyed checking out Union Square, Chinatown, Fisherman’s Wharf, the Golden Gate Bridge and Alcatraz. I especially enjoyed riding from San Francisco up to Tiburon and catching a ferry back. In September I will be participating in the Buffalo Bicycle Classic that takes place here in Boulder, CO. I’ve done the event in the past and am looking forward to closing out my bicycle season with a ride along the front range to support the College of Arts and Sciences at the University of Colorado at Boulder.

As a consequence of how I want to be spending my time, I am finding it difficult to work on side projects and to post write ups. I am going to postpone posting any new content until later this year or around the start of next year. I enjoy taking my time working on interesting projects to produce interesting content, but feel that I would only be posting ho-hum content about ho-hum projects if I can’t commit the proper amount of time. I am planning on returning with posts covering a game I’ve been working on in Haskell, exploring the relationship between source code and team organization and developing some new tree drawing algorithms (which seem to bring a lot of you to this website.) I am also planning on writing on topics in business, finance and architecture as it relates to software engineering.

If you enjoy the content on this site, I recommend adding it to your RSS reader and keeping an eye out for future posts. In the mean time, take a look through the archives and find something interesting to read.

Haskell ecosystem on Windows XP

It’s been fun watching the Haskell ecosystem evolve into a mature system over the years. Seems that about every three months it takes a leap forward and I usually find myself uninstalling what I previously had and putting the latest and greatest on my laptop. To save myself some time in the future, I’ve compiled this post as a reference of basic “stuff” that is good to have for doing Haskell development on a Windows XP machine.

Haskell Platform

It used to be that you had to go find a number of different applications to get packages, compile source code and generate documents (among a handful of other things), then a group of folks identified an opportunity and put together a platform for getting new users a place to start. The result is the Haskell Platform.

• Glasgow Haskell Compiler (GHC) – The Haskell compiler that also comes with a command line interpreter (GHCi). Alternatives are the York Haskell Compiler (yhc) and Hugs
• Cabal – Basic package management system
• Haddock – used for generating documentation based on comments in source code

After installing, you’ll want to go to the command line and run the following commands to make sure that you’ve got the latest version of Cabal and to make sure that it has the latest package list:

C:\cabal install cabal-install
C:\cabal update

Leksah

Many developers are probably used to having a quality Integrated Development Environment (IDE) to work with and the Haskell Community’s answer is Leksah. Leksah is still fairly green and has a ways to go before being comparable to Eclipse or Visual Studio, but nonetheless, Leksah is packed with plenty of goodies that will make for easy development of packages and modules for distribution on Cabal.

It is best to use the installer from the Leksah website. Once you’ve installed the latest, you’ll need to run the following from the command-line

C:\ghc-pkg recache

So that the packages on the system (those provided by GHC) will show up when you have the browse pane open.

Gtk2hs

If you plan on doing any Graphical User Interfaces (GUIs), then you’ll want to get the Haskell binding to the GTK+ library. On the page there should be an “All-in-one bundle”- for the purpose of the following, I went with version 2.20.

After extracting the bundle on the machine, make sure that the path you extracted the bundle at along with the child bin directory is added to the PATH environment variable.

Then from the command-line run the following and you should be able to include GTK in your project:

C:\cabal install gtk

HOpenGL

I’ve been working on some basic game programming and I’ve done some stuff in the past with OpenGL so I decided to give the Haskell bindings a try. Windows doesn’t natively ship with the OpenGL library, so you’ll need to get it from here.

Then get the following packages off of Cabal:

c:\cabal install glut
C:\cabal install opengl

Wrap-up

I haven’t done a dry run to test all of the above, so if you follow all of the above and come across a problem, post the solution in the comments. I’ll continue to update this post as I identify any problems or come across additional “stuff” that falls into the must-have category.

Mathematics Test Practice Questions

I’ve had a fairly busy month, so I haven’t had a lot of time to work on any projects. I’ve got a few in the pipeline, but none really mature enough yet to get a write-up. I’ve been playing with the idea of graduate school for a couple years now and have always felt that a strong mathematics background is a good basis for pursuing more interesting (computer science) topics. So, this past week I’ve been working my way through the Mathematics Test Practice Book to see how well I’d fare. The examination seems fairly aggressive allowing for roughly 2.5 minutes per problem for 66 problems. I’m a little more methodical in my ways, so I would certainly take more time than what’s allotted. Nonetheless, I thought I’d share my take on a handful of problems from different subject matters that I found of particular interest:

Let be the set of all primes, , and for each integer , let be the set of all prime multiples of n, . Which of the following intersections is nonempty?

1. 
2. 
3. 
4. 
5. 

Given , we’ll pick two elements (one from each set) and solve for . We then assume that are of the form where is a composite. Thus, , we can conclude that . Thus, D is the correct answer.

---

For what value of is the line tangent to the curve at some point in the xy-plane?

Using operator notation, a line tangent to a curve is given by . To solve for we solve for

Which yields the following two equations: and since will never equal zero, we can conclude . Substituting for yields .

---

Suppose that two binary operations, denoted by and , are defined on a nonempty set , and that the following conditions are satisfied for all , and in :

(1) (Closure)
(2) (Associativity) and
(3) (Commutativity)

Also, for each and for each positive integer , the elements and are defined recursively as follows:

(4) (Identity Element)
(5) and if and have been defined, then and

Which of the following must be true?

1. I only
2. II only
3. III only
4. II and III only
5. I, II and III

I.) s.t.

Assume , from which we assume . If (3) were defined for , we could swap either side then apply (2) reducing it down to the recursive definition (5) and have a proof. Since that isn’t the case, we can’t conclude that .

II.) s.t.

Given (1) we can construct by using (4). We can state from (5), leading to by way of (3). and by (2). From (5) . Unfolding that set of steps leads to the following: , and . If we were to continue down this path for then we would find that .

III.) s.t. .

Starting with (5): we introduce an additional , and then apply (2) which leads to . The same set of steps once again leads to . By induction, we can conclude .

---

At a banquet, 9 women and 6 men are to be seated in a row of 15 chairs. If the entire seating arrangement is to be chosen at random, what is the probability that all of the men will be seated next to each other in 6 consecutive positions?

I’m going to use the notation to denote a number of men ( for the total number of men), to denote a number of women ( for the total) and to denote the number of seats. A sequence of this notation such as indicates a sequence of three women, six men and six women seated amongst the fifteen seats. Given the definition, we are interested in the probability of . Since there are a fixed number of seats and no two people can occupy the same seat, we know that the number of permutations of is the total number of possible arrangements (our sample space). There are ways in which the men can be arranged and there are ways in which the women can be arranged in the remaining seats. Since there are ways to “slide” the group of men along the seats we can conclude that:

Given the question, the solution is

---

If , then ?

1. 
2. 
3. 
4. 
5. 

First thing to observe is that is the 5′th root of unity which carries with it two properties:

1. 
2. 

Proof of property (1) is trivial, proof of property (2) is basic proof of the geometric series:

Given these properties, we begin to evaluate by separating the terms into reducible portions:

---

If denotes the greatest integer not exceeding x, then

1. 
2. 
3. 
4. 
5. 

When , we have a discontinuity in the function that we are integrating because of the floor function. To resolve this issue, we need to break up the integral into a sum of integrals as follows: .

Now we are left with a series that looks similar to a geometric series, so we evaluate it using a similar proof, then return to evaluating the integral.

.

(This last step can be produced by expanding the series.) We see that we have a geometric series (without the first term) which was proved earlier. From these facts we can conclude:

.

As we take the limit of of this expression (assuming for convergence) we find:

.

Returning to evaluating the integral, we now find:

.

---

The four shaded circles in Figure 1 above are congruent and each is tangent to the large circle and to two of the other shaded circles. Figure 2 is the result of replacing each of the shaded circles in Figure 1 by a figure that is geometrically similar to Figure 1. What is the ratio of the area of the shaded portion of Figure 2 to the area of the shaded portion of Figure 1?

1. 
2. 
3. 
4. 
5. 

The first goal is to construct one of the shaded circles in Figure 1. Once the circle has been constructed, we know that the scaling factor of Figure 1 onto Figure 2 will be the radius of the shaded circle (assuming the bounding circle is the unit circle).

Starting with the unit circle, , centered at the origin, select points and on . Construct the midpoint to construct the line . The intersection of with leads to the point . Let be perpendicular to at . Points and . We can now construct two angle bisectors: and . The intersection of these two lines is . Which implies the inscribed circle .

Thus, the area of is and the total shaded area in Figure 1 is . To figure out the shaded area of Figure 2, we’ll scale Figure 1 down by a factor of and multiply by 4 yielding . These two areas give a ratio of: .

(Images in this section were generated by GeoGebra.)

An Experiment in Optical Character Recognition

Introduction

I’ve always been interested in machine learning and how it can be applied to a number of different problems. I spent some time during college learning some of the techniques used in machine learning, but since then I’ve gotten a bit rusty. So, I revisited the subject by doing some additional research and decided to try my hand at Optical Character Recognition (OCR)- the process of identifying characters within an image and producing a text output. There are a handful of traditional aspects to this process: image acquisition, segmentation, recognition and correction. Acquisition is about correcting an input image so that a segmentation process can be readily applied; segmentation identifies the characters in the image, recognition maps those visual characters to text characters, finally correction takes the text output and rectifies any errors. The following outlines my approach to segmentation and recognition.

Segmentation

Consider the following body of text from one of my earlier posts:

The goal is to extract each of the characters in the image. The simplest way to accomplish this is to implement an algorithm that reads the image much in the same way one might read a block of text: start at the top of the text and scan downward identifying all of the rows of text, then for each row, read all the characters from left to right, then identify words based on white space. Figuring out the word boundaries is done via a simple clustering process. Assuming we have an ordered set of rectangles produced by the first two steps, we can calculate the average distance between consecutive rectangles. Then, once this average has been produced, to then iterate over the list once more adding rectangles to words when the distance between consecutive rectangles is less than the average distance, then creating new words when the distance is exceeded.

This segmentation approach isn’t perfect as it assumes that we are dealing with evenly spaced characters of the same size from the same font. Of course, this isn’t always the case and we have things like kerning and ligatures to deal with. In this example two categories of problems arise: character combinations such as ay, ey and ly that are separable then combinations such as yw, rt and ct that are not separable end up being interpreted as a single character using this method. For the first category, I chose to divide rectangles whenever a line of characters has a single black pixel that does not have a black pixel neighboring ((x-1, y + a) | a <- [-1, 1]) it to the left. The second case isn't as clear cut as all the pixels neighbor one another, in principal one could implement a k-means clustering algorithm, but that assumes you know how many characters (k) you have in the image. I decided to allow the error to propagate through the system.

Recognition

Starting out, I knew that I wanted to use an Artificial neural network (ANN), so I spent some time reading Stuart’s and Norvig’s “Artificial Intelligence: A Modern Approach“, but felt that it wasn’t as comprehensive as I wanted, so I also read MacKay’s “Information Theory, Inference and Learning Algorithms,” which was more in tune with what I had in mind. I also came across a series (1, 2, 3) of pdf files hosted at Aberdeen’s Robert Gordon University that provided a more practical view of applying neural networks to pattern recognition.

A little background on ANNs: The general idea is that an individual neuron aggregates the weighted inputs from other neurons then outputs a signal. The magnitude of the signal is determined as a function of the aggregation called the activation function. Neurons are organized into layers, typically an input layer, one or more hidden layers and finally an output layer. Values from the input layer and feed into the hidden layer, then those outputs feed into the next and so on until all the values have gone through the output layer. The process of getting the network to map an input to an output is accomplished through training, in this case, a method known as Backpropagation. Given an input and an expected output, the input is feed through the network and produces an output. The difference between the two output vectors is the error that then needs to be feed backward through the network updating each node’s input weights such that the net error of the system is reduced. The method is effectively a gradient descent algorithm. I recommend reading the aforementioned references for details on how it all works. Following is my implementation of the Backpropagation algorithm:

using System;
using System.Linq;
using Library.Mathematics;

namespace OCRProject.Recognizers.NeuralNetworks {
    public class Neuron {
        Func<double, double> activationFunction;

        public Vector InputWeights { get; set; }

        public Neuron(Func<double, double> activationFunction) {
            this.activationFunction = activationFunction;
        }

        public double Output(Vector input) {
            return activationFunction(InputWeights.dot(input));
        }
    }

    public class NeuralNetwork {
        private Neuron[] hiddenLayer, outputLayer;

	...

        public Vector Output(Vector input) {
            Vector hiddenLayerOutput = new Vector(hiddenLayer.Length, (i) => hiddenLayer[i].Output(input));
            return new Vector(outputLayer.Length, (i) => outputLayer[i].Output(hiddenLayerOutput));
        }

        public Vector Train(Vector input, Vector desiredOutput, double learningRate) {
            Vector hOutput = new Vector(hiddenLayer.Length, (i) => hiddenLayer[i].Output(input));
            Vector oOutput = new Vector(outputLayer.Length, (i) => outputLayer[i].Output(hOutput));

            Vector oError = new Vector(
                oOutput.Dimension,
                (i) => oOutput[i] * (1 - oOutput[i]) * (desiredOutput[i] - oOutput[i])
            );

            for (int n = 0; n < outputLayer.Length; n++) {
                outputLayer[n].InputWeights = new Vector(
                    hiddenLayer.Length,
                    (i) => outputLayer[n].InputWeights[i] + learningRate * oError[n] * hOutput[i]
                );
            }

            Vector hError = new Vector(
                hiddenLayer.Length,
                (i) => hOutput[i] * (1 - hOutput[i]) * (oError.dot(new Vector(oError.Dimension, (j) => outputLayer[j].InputWeights[i])))
            );

            for (int n = 0; n < hiddenLayer.Length; n++) {
                hiddenLayer[n].InputWeights = new Vector(
                    input.Dimension,
                    (i) => hiddenLayer[n].InputWeights[i] + learningRate * hError[n] * input[i]
                );
            }

            return oError;
        }
    }
}

In terms of how all of this applies to OCR, I started out with all visible characters and produced a collection of 16×16 images. Each image contained a single character centered in the image. This image was then mapped to a 256 dimensional vector with its corresponding character mapped to an 8 dimensional vector representing the expected output. The question that remains is how many hidden layer units should be used. To figure this out, I conducted a small experiment:

Hidden Units	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Minimum (%)	0	4	7	21	36	48	69	80	87	85	92	88	92	89	93	93
Average (%)	1	4	12	28	44	56	72	83	89	90	94	93	94	93	95	95
Maximum (%)	1	6	15	31	51	62	75	87	91	93	99	96	98	95	98	99

Each run consisted of 10 trials with each trial taking 5000 iterations to train the network. (Normally, one can measure the Mean squared error of the network and halt the training process once it is sufficiently small.) After doing this testing, I found that ANNs with 11 hidden units looked to give the highest accuracy with the fewest number of units. Given the original text that was used, the following text was produced:

As expected, the category of errors that were identified earlier (character combinations ff, rt, ct) were not segmented correctly and consequently not recognized correctly.

Wrap-up

There is a lot of additional work that could be thrown at the project. In the future, it’d be good to modify the solution to accept any sized font as well as any font, adding support for images containing scanned or photographed text rather than computer generated images and some error correction on the output to flag parts of the text that require review. I suspect that I will continue down this road and start investigating how these methods can be applied to general computer vision for some planned robotics projects.