Antimatroid, The

thoughts on computer science, electronics, mathematics

Archive for the ‘Projects’ Category

Large-Scale Detection and Tracking of Aircraft from Satellite Images

leave a comment »

Abstract
In this paper a distributed system for detecting and tracking commercial aircraft from medium resolution synthetic satellite images is presented. Discussion consisting of the system’s Apache Spark distributed architecture, correlation-based template matching, heuristic-based tracking, and evaluation of the system’s Standalone, Cluster, and Cloud modes of operation are covered before concluding with future work. Experimental results support 10 m detection accuracy, 96% detection rate, and 200 ms/image and 10 mb/sec Cloud processing performance. The goal of this work is to demonstrate that a satellite-based aircraft tracking system is feasible and that the system’s oversimplifying assumptions offer a baseline which similar real-world systems may be compared. Applications of this system include real-time tracking of commercial aircraft, flight deviation, and the automatic discovery of commercial aircraft from historic imagery. To the best of the author’s knowledge, a system of this nature has not been published publicly.

Introduction

Motivation

Historically, search and rescue operations have relied on on-site volunteers to expedite the recovery of missing aircraft. However, on-site volunteers are not always an option when the search area is very broad, or difficult to access or traverse as was the case when Malaysia Airlines Flight 370 disappeared over the Indian Ocean in March, 2014. Crowd-sourcing services such as tomnod.com have stepped up to the challenge by offering volunteers to manually inspect satellite images for missing aircraft in an attempt to expedite the recovery process. This process is effective, but slow. Given the urgency of these events, an automated image processing solution is needed.

Prior Work

The idea of detecting and tracking objects from satellite images is not new. There is plenty of academic literature on detection or tracking, but often not both for things like oil tankers, aircraft, and even clouds. Most distributed image processing literature is focused on using grid, cloud, or specialized hardware for processing large streams of image data using specialized software or general platforms like Hadoop. Commercially, companies like DigitalGlobe have lots of satellite data, but haven’t publicized their processing frameworks. Start-ups like Planet Labs have computing and satellite resources capable of processing and providing whole earth coverage, but have not publicized any work on this problem.

The FAA has mandated a more down to earth approach through ADS-B. By 2020, all aircraft flying above 10,000 ft will be required to have Automatic dependent surveillance broadcast transceivers in order to broadcast their location, bearing, speed and identifying information so that they can be easily tracked. Adoption of the standard is increasing with sites like Flightrader24.com and Flightaware.org providing real-time access to ongoing flights.

Problem Statement

Fundamentally, there are two variants of this problem: online and offline. The offline variant most closely resembles the tomnod.com paradigm which is concerned with processing historic satellite images. The online variant most closely resembles air traffic control systems where we’d be processing a continual stream of images coming from a satellite constellation providing whole earth coverage. The focus of this work is on the online variant since it presents a series of more interesting problems (of which the offline problem can be seen as a sub-problem.)

In both cases, we’d need to be able to process large volumes of satellite images. One complication is that large volumes of satellite images are difficult and expensive to come by. To work around this limitation, synthetic images will be generated based off OpenFlights.org data with the intent of evaluating natural images on the system in the future. To generate data we’ll pretend there are enough satellites in orbit to provide whole earth coverage capturing simulated flights over a fixed region of space and window of time. The following video is an example of the approximately 60,000 flights in the dataset being simulated to completion:

To detect all these aircraft from a world-wide image, we’ll use correlation based template matching. There are many ways to parallelize and distribute this operation, but an intuitive distributed processing of image patches will be done with each cluster node performing a parallelized Fast Fourier Transform to identify any aircraft in a given patch. Tracking will be done using an online heuristic algorithm to “connect the dots” recovered from detection. At the end of the simulation, these trails of dots will be paired with simulated routes to evaluate how well the system did.

The remainder of this post will cover the architecture of the system based on Apache Spark, its configurations for running locally and on Amazon Web Services, and how well it performs before concluding with possible future work and cost analysis of what it would take to turn this into a real-world system.

System Architecture

Overview

pipeline
Figure 1: Data pipeline architecture.

The system relies on the data pipeline architecture presented above. Data is read in from the OpenFlights.org dataset consisting of airport information and flight routes. A fixed number of national flights are selected and passed along to a simulation module. At each time step, the simulator identifies which airplanes to launch, update latitude and longitude coordinates, and remove those that have arrived at their destination.

To minimize the amount of network traffic being exchanged between nodes, flights are placed into buckets based on their current latitude and longitude. Buckets having flights are then processed in parallel by the Spark Workers. Each worker receives a bucket and generates a synthetic satellite image; this image is then given to the detection module which in turn recovers the coordinates from the image.

These coordinates are coalesced at the Spark Driver and passed along to the tracking module where the coordinates are appended to previously grown flight trails. Once 24 hours worth of simulated time has elapsed (in simulated 15 minute increments), the resulting tracking information is passed along to a reporting module which matches the simulated routes with the flight trails. These results are then visually inspected for quality.

Simulation Assumptions

All latitude and longitude calculations are done under the Equirectangular projection. A corresponding flight exists for each route in the OpenFlights.org dataset (Open Database License). Flights departing hourly follow a straight line trajectory between destinations. Once en route, flights are assumed to be Boeing 747s traveling at altitude of 35,000 ft with a cruising speed of 575 mph.

Generation

grids
Figure 2: Conceptual layering and data representations between the modules of the pipeline. World silhouette by Wikimedia Commons.

Flights are mapped to one of 4000 \times 8000 buckets based on each flight’s latitude and longitude coordinate. Each bucket spans a 0.045 \times 0.045 degree region as illustrated in the middle layer of Fig. (2). Given a bucket, a 512 \times 512 oversimplified synthetic medium-resolution monochromatic satellite image is created with adorning aircraft silhouettes for each 71 \times 65 m Boeing 747 airliner in the bucket. (Visual obstructions such as clouds or nightfall will not be depicted.) This image, in addition to the latitude and longitude of the top-left and bottom-right of the image, are then passed along to the detection module.

Detection

Given an image and its world coordinate frame, the detection module performs textbook Fourier-based correlation template matching to identify silhouettes of airplanes, X, in the image, Y:

\displaystyle Z = \mathcal{F}^{-} \left( \mathcal{F}(X) \circ \mathcal{F}(Y) \right ) (1)

Where the two-dimensional Discrete Fourier Transform and inverse transform are defined as:

\displaystyle \mathcal{F}(f)(u,v) = \frac{1}{M N} \sum_{m = 0}^{M - 1} \sum_{n = 0}^{N - 1} f(m, n) \exp{ \left( -2 \pi i \left( \frac{mu}{M} + \frac{nv}{N} \right ) \right ) } (2)

\displaystyle \mathcal{F^{-}}(F)(m,n) = \sum_{u = 0}^{M - 1} \sum_{v = 0}^{N - 1} F(u, v) \exp{ \left( 2 \pi i \left( \frac{mu}{M} + \frac{nv}{N} \right ) \right ) } (3)

To carry out these calculations efficiently, a parallelized two-dimensional Fast Fourier Transform (FFT) \mathcal{O}(N \log N) time algorithm was implemented for both forward and inverse operations by leveraging the fact that operations (2), (3) can be factored so that the FFT can be computed row-wise, and then on those results column-wise. Hadamard (element-wise) product of the frequency domain representation of the airplane and satellite image is done naively in quadratic time.

To denoise the results, the recovered spatial product, Z, is thresholded so that any real values greater than 90% of the product’s real maximum, Z^*, are kept:

\displaystyle Z_{x,y} = \Re{ \left( Z_{x, y} \right ) } 1_{ [ \Re{ \left( Z_{x, y} \right ) } \ge 0.9 Z^{*}  ] } (4)

Since there are many values greater than the threshold, a linear time (in number of nodes) connected component labeling algorithm is applied to identify the most likely aircraft locations. The algorithm treats each pixel of the image as a node if that pixel’s value is greater than the threshold. An edge exists between two nodes if the nodes’ pixel coordinates are within an \ell_\infty distance of two. The centroid of each connected component is then taken to be the true coordinate of each detected aircraft. Next only those centroids derived from clusters having more than half the average number of pixels per cluster are kept. Finally, these centroids are transformed to latitude and longitude coordinates given the world coordinate frame.

Tracking

The tracking module uses an 181 \times 361 grid of buckets with each bucket representing approximately a square degree region as illustrated as the top layer in Fig. (2). Each individual bucket consists of a stack of sightings where a sighting is a timestamped collection of coordinates. Here an individual coordinate is allowed to “connect” up to two other coordinates. Coordinates connected in this fashion form a trail, which is the primary output of the module.

tracking-heuristics
Figure 3: (Left) Collinear and (Right) directional tracking heuristics. Blue points C represent coordinates that would be accepted under these heuristics and red points C^\prime that would be rejected.

For each latitude and longitude coordinate from the detection module, d \in D, the tracking module picks all the previous time step’s coordinates, p \in P, from the neighboring (\ell_\infty \le 5) buckets of d‘s bucket. From P, only those coordinates that satisfy the following criteria are considered:

  • p must be free to “connect” to another coordinate.
  • d must be collinear to the coordinates of the trail headed by p, i.e., \lvert AC - AB - BC \rvert \le \epsilon as in Fig. (3).
  • Given the predecessor of p, the inner product of the vectors formed from the predecessor to p and d must be positive, i.e., \langle \overrightarrow{AB}, \overrightarrow{AC} \rangle > 0 as in Fig. (3).

Next, the nearest neighbor of p is chosen from this remaining set of points. If a nearest neighbor exists, then p is appended to the end of the nearest neighbor’s trail, otherwise a new trail is created. Finally, p is added to its designated bucket so that it can be used for future trail building.

When the simulation completes, all trails from tracking module are analyzed and matched to the known routes used in the simulation. Matching is done by minimizing the distance from the trail’s origin and destination to a route’s origin and destination respectively. If the mean orthogonal distance:

\displaystyle MOD(x) = \frac{1}{N} \sum_{i} \frac{ \lvert \langle w, x_i \rangle + b \rvert  }{ \lVert w \rVert  } (5)

from the coordinates in the trail to the line formed by connecting the route’s origin and destination is greater than 25 m, then the match is rejected.

Reporting

The reporting module is responsible for summarizing the system’s performance. The average mean orthogonal distance given by Eqn. (5) is reported for all identified routes, total number of images processed and coordinates detected, and the portion of routes correctly matched is reported.

System Configurations

Standalone

standalone
Figure 4: Standalone configuration components.

Standalone mode runs the application in a single JVM without using Spark. Experiments were ran on the quad-core Intel i7 3630QM laptop jaws, which has 8 GB of memory, 500 GB hard drive, and is running Windows 8.1 with Java SE 7.

Cluster

cluster
Figure 5: Cluster configuration components.

Cluster mode runs the application on a Spark cluster in standalone mode. Experiments were ran on a network consisting of two laptop computers connected to a private 802.11n wireless network. In addition to jaws, the laptop oddjob was used. oddjob is a quad-core Intel i7 2630QM laptop with 6 GB of memory, 500 GB hard drive running Windows 7. Atop each machine, Oracle VM VirtualBox hosts two cloned Ubuntu 14.04 guest operating systems. Each virtual machine has two cores, 2 GB of memory and a 8 GB hard drive. Each virtual machine connects to the network using a bridged network adapter to its host’s. Host and guest operating systems are running Java SE 7, Apache Hadoop 2.6, and Scala 2.11.6 as prerequisites for Apache Spark 1.3.1. In total, there are four Spark Workers who report to a single Spark Master which is driven by a single Spark Driver.

Cloud

cloud
Figure 6: Cloud configuration components.

Cloud mode runs the application on an Amazon Web Services (AWS) provisioned Spark cluster managed by Apache Yarn. Experiments were ran using AWS’s Elastic Map Reduce (EMR) platform to provision the maximum allowable twenty[1] Elastic Compute Cloud (EC2) previous generation m1.medium instances (one master, nineteen core) by scheduling jobs to execute the application JARs from the Simple Storage Service (S3). Each m1.medium instance consists of one 2 GHz CPU, 3.7 GB of memory, 3.9 GB hard drive running Amazon Machine Image (AMI) 3.6 equipped with Red Hat 4.8, Java SE 7, Spark 1.3.0. In total, there are nineteen Spark Workers and one Spark Master – one per virtual machine – managed by a Yarn Resource Manager driven by a single Yarn Client hosting the application.

System Evaluation

Detection Rate

detection-rate
Figure 7: \overline{D}_r reported for flights in a single 25 km2 region. Larger \overline{D}_ris better.

\displaystyle D_R = \frac{\# \left( \text{Detected coordinates} \right)}{\# \left( \text{Expected coordinates} \right)} (6)

When an image is sparsely populated, the system consistently detects the presence of the aircraft, however as the density increases, the system is less adapt at finding all flights in the region as shown in Fig. (7). This is unexpected behavior. Explanations include the possibility that the threshold needs to be made to be adaptive, or that a different approach needs to be taken all together. In terms of real world implications, FAA regulations (JO 7110.65V 5-4-4) state that flights must maintain a minimum lateral distance of 3 and 5 miles (4.8 to 8 km). In principle, there could be at most four flights in a given image under these guidelines and the system would still have a 96.6% chance of identifying all four positions.

Detection Accuracy

den-ctl
Figure 8: Detected and actual positions of a fight from Denver to Charlotte.

A flight from DIA to CTL was simulated to measure how accurate the template matching approach works as illustrated in Fig. (8). Two errors were measured: the mean orthogonal distance given by Eqn. (5) and the mean distance between the detected and actual coordinate for all time steps:

\displaystyle MD(x, y) = \frac{1}{N} \sum_i \lVert  x_i - y_i \rVert_2 (7)

For Eqn. (5) a mean error of 9.99 \pm 3.2 m was found, and for Eqn. (7) 19.95 \pm 3.3 m. Both errors are acceptable given a single pixel represents approximately 10 m. (For context, the global positioning system (GPS) has a 7.8 m error.)

mod-dist
Figure 9: 65% of the paired trails and routes have a MOD less than 26 m. Smaller error is better.

In terms of how accurate detection is at the macro level, 500 flights were simulated and the resulting mean orthogonal distance was analyzed. Fig. (9) illustrates the bimodal distribution that was observed. 65% of the flights observed an accuracy less than 26 m with an average accuracy of 14.2 \pm 5.8 m, while the remaining 35% saw an average accuracy of 111.9 \pm 100 km which is effectively being off by a full degree. It is assumed that this 35% are cases where trails are paired incorrectly with routes. Based on these findings, the system enforces that all pairings not exceed a mean orthogonal distance of 25 m.

Tracking Rate

tracking-rate
Figure 10: 2^n for n \in [0, 10] national fights were simulated to completion with their mean tracking rate reported over 15 trials. Larger \overline{T}_R is better.

\displaystyle T_R = \frac{\# \left( \text{Correctly paired trails} \right)}{\# \left(\text{ Expected trails} \right)} (8)

For Fig. (10), an increasing number of random flights were simulated to completion and the resulting mean tracking rate reported. Based on these findings, the tracking module is having difficulty correctly handling many concurrent flights originating from different airports. This behavior is likely a byproduct of how quickly the detection rate degrades when many flights occupy a single region of space. When running a similar simulation where all flights originate from the same airport, the tracking rate is consistently near-perfect independent of the number of flights. This would suggest the system has difficulty with flights that cross paths. (For context, there is on average 7,000 concurrent flights over US airspace at any given time that we would wish to track.)

Performance

performance
Figure 11: Average processing time per image in milliseconds for the three dierent congurations. Smaller ms/image is better.

A series of experiments was conducted against the three configurations to measure how quickly the system could process different volumes of flights across the United States over a 24-hours period. The results are illustrated in Fig. (11). Unsurprisingly, the Cloud mode outperforms both the Standalone and Cluster modes by a considerable factor as the number of flights increases.

Configuration ms/image mb/sec Time (min)
Standalone 704 3.00 260
Cluster 670 2.84 222
Cloud 207 9.67 76
Table 1: Processing time per image, megabytes of image data processed per second, and overall processing time for 22k images by system configuration.

Table (1) lists the overall processing time for 22k images representing roughly 550k km2, and 43 GB of image data. If the Cloud configuration was used to monitor the entire United States, then it would need approximately 22 hours to process a single snapshot consisting of 770 GB of image data. Obviously, the processing time is inadequate to keep up with a recurring avalanche of data every fifteen minutes. To do so, a real-world system would need to be capable of processing an image every 2 ms. To achieve this 1) more instances could be added, 2) the implementation can be refined to be more efficient, 3) the implementation can leverage GPUs for detection, and 4) a custom tailored alternative to Spark could be used.

Discussion

Future Work

There are many opportunities to exchange the underlying modules with more robust techniques that both scale and are able to handle real-world satellite images. The intake and generation modules can be adapted to either generate more realistic flight paths and resulting satellite imagery, or adapted to handle real-world satellite imagery from a vendor such as Skybox Imaging, Planet Labs, or DigitalGlobe.

For detection, the correlation based approach can be replaced with a cross-correlation approach, or with the more involved Scale Invariant Feature Transformation (SIFT) method which would be more robust at handling aircraft of different sizes and orientations. Alternatively, the parallelism granularity can be changed so that the two-dimensional FFT row-wise and column-wise operations are distributed over the cluster permitting the processing of larger images.

Tracking remains an open issue for this system. Getting the detection rate to be near perfect will go a long way, but the age of historical sightings considered could be increased to account for “gaps” in the detection trail. Yilmaz et al. provide an exhaustive survey of deterministic and statistical point tracking methods that can be applied here, in particular the Joint Probability Data Association Filter (JPDAF) and Multiple Hypothesis Tracking (MHT) methods which are worth exploring further.

On the reporting end of the system, a dashboard showing all of the detected trails and coordinates would provide an accessible user interface to end-users to view and analyze flight trails, discover last known locations, and detect anomalies.

Real-world Feasibility

While the scope of this work has focused on system internals, it is important to recognize that a real-world system requires a supporting infrastructure of satellites, ground stations, computing resources, facilities and staff- each of which imposes its own set of limitations on the system. To evaluate the system’s feasibility, its expected cost is compared to the expected cost of the ADS-B approach.

Following the CubeSat model and a 1970 study by J. G. Walker, 25 satellites ($1M ea.) forming a constellation in low earth orbit is needed to provide continuous whole earth coverage for $25M. Ground stations ($120k ea.) can communicate with a satellite at a time bringing total costs to $50M.[2] Assuming that a single computer is responsible for square degree region, the system will require 64,800 virtual machines, equivalently 1,440 quad-core servers ($1k ea.) bringing the running total to $51M.

ADS-B costs are handled by aircraft owners. Average upgrade costs are $5k with prices varying by vendor and aircraft. Airports already have Universal Access Transceivers (UATs) to receive the ADS-B signals. FAA statistics list approximately 200,000 registered aircraft suggesting total cost of $1B.

Given that these are very rough estimates, an unobtrusive $51M system would be a good alternative to a $1B dollar exchange between private owners to ADS-B vendors. (Operational costs of the system were estimated to be $1.7M/year based on market rates for co-locations and staff salaries.)

Conclusions

In this work, a distributed system has been presented to detect and track commercial aircraft from synthetic satellite imagery. The system’s accuracy and detection rates are acceptable given established technologies. Given suitable hardware resources, it would be an effective tool in assisting search-and-rescue teams locate airplanes from historic satellite images. More work needs to be done to improve the system’s tracking abilities for it to be a viable real-world air traffic control system. While not implemented, the data needed to support flight deviation, flight collision detection and other air traffic control functionality is readily available. Spark is an effective tool for quickly distributing work to a cluster, but more specialized high performance computing approaches may yield better runtime performance.

References

[1] Automatic dependent surveillance-broadcast (ads-b) out equipment and use. Technical Report 14 CFR 91.225, U.S. Department of Transportation Federal Aviation Administration, May 2010.

[2] General aviation and air taxi activity survey. Technical Report Table 1.2, U.S. Department of Transportation Federal Aviation Administration, Sep 2014.

[3] Nanosats are go! The Economist, June 7 2014.

[4] A. Eisenberg. Microsatellites: What big eyes they have. New York Times, August 10 2013.

[5] A. Fasih. Machine vision. Lecture given at Transportation Informatics Group, ALPEN-ADRIA University of Klagenfurt, 2009.

[6] S. Kang, K. Kim, and K. Lee. Tablet application for satellite image processing on cloud computing platform In Geoscience and Remote Sensing Symposium (IGARSS), 2013 IEEE International, pages 1710-1712, July 2013.

[7] W. Lee, Y. Choi, K. Shon, and J. Kim. Fast distributed and parallel pre-processing on massive satellite data using grid computing. Journal of Central South University, 21(10):3850-3855, 2014.

[8] J. Lewis. Fast normalized cross-correlation. In Vision interface, volume 10, pages 120-123, 1995.

[9] W. Li, S. Xiang, H. Wang, and C. Pan. Robust airplane detection in satellite images. In Image Processing (ICIP), 2011 18th IEEE International conference on, pages 2821-2824, Sept 2011.

[10] D. G. Lowe. Distinctive image features from scale-invariant keypoints. International journal of computer vision, 60(2):91-110, 2004.

[11] H. Prajapati and S. Vij. Analytical study of parallel and distributed image processing. In Image Information Processing (ICIIP), 2011 International Conference on, pages 1-6, Nov 2011.

[12] E. L. Ray. Air traffic organization policy. Technical Report Order JO 7110.65V, U.S. Department of Transportation Federal Aviation Administration, April 2014.

[13] J. Tunaley. Algorithms for ship detection and tracking using satellite imagery. In Geoscience and Remote Sensing Symposium, 2004. IGARSS ’04. Proceedings. 2004 IEEE International, volume 3, pages 1804-1807, Sept 2004.

[14] J. G. Walker. Circular orbit patterns providing continuous whole earth coverage. Technical report, DTIC Document, 1970.

[15] Y. Yan and L. Huang. Large-scale image processing research cloud. In CLOUD COMPUTING 2014, The Fifth International Conference on Cloud Computing, GRIDs, and Virtualization, pages 88-93, 2014.

[16] A. Yilmaz, O. Javed, and M. Shah. Object tracking: A survey. Acm computing surveys (CSUR), 38(4):13, 2006.

Advertisements

3D Printed Toy Robot

with one comment

Left-to-right: Original pixel art illustration, nearest neighbor extrapolation, vectorized version and 3D CAD model.
design-progression


Introduction

At the beginning of the year I decided to change my approach to working on personal projects; in short, more time on quality and less on quantity. With that mindset I thought about my interests and how they could come together to form an interdisciplinary project that would be ambitious, but doable. After much thought, I zeroed in on mechatronics -the interplay of form, computation, electronics and mechanics- and began to explore how I could draw from these disciplines to form the foundation of my next project.

Like most people coming from a software background, much of what I work on is abstract in nature. Every once in a while I have a strong desire to work on something tangible. Lacking the proper space and tools to work with traditional mediums like wood and metal, I thought about newer mediums I’d read about and directed my attention to 3D printing. Despite being 30 years old, the technology has only become accessible to consumers within the past seven years with the launch of several online services and open source printers. Having watched this growth, I was curious about the technology and decided it would be worth exploring in this project.

I’d been looking for an excuse to get back into electronics and work on a project that would require me to delve deeper into analog circuit design. This desire was drawn from the belief that I ought to be able to reason about computation regardless of how it is represented- be it by mathematics, software or hardware. This of course meant avoiding microcontrollers; my goal here was to better learn the foundations of the discipline, not make something quickly and cheaply.

To stay true to the mechatronics concept, I decided I would incorporate mechanical elements in to the project. Having zero knowledge of mechanics, I knew whatever I’d make would be simplistic and not much to write about. However, I felt that whatever I decided to do, I wanted the mechanically driven functionality to ignite a sense of fun in whoever was interacting with the end result. After all, the end result is something you might only interact with briefly, but it should be memorable and what better way to achieve that than to make it entertaining.

I searched for inspiration to figure out how I would tie all of these disciplines together. Growing up I read a lot of Sci-fi literature and a lot of that material stuck with me over the years, especially the portrayal of robots from the golden age. Above all, it captured the sense that anything was possible with technology and served as a great source of inspiration in my career. So without much surprise, I found the inspiration I needed for the project in my robot avatar. My mind was flickering with ideas as to how I could bring that simple icon to life and with that excitement I began my work.

Over the course of eight months I taught myself the necessary disciplines and skills to carry out my vision of building a simple 3D printed toy robot. Having finished my work at the end of July, I began compiling my notes and documenting my work and concluded this writing in the middle of October. This post is the culmination of that work and it will cover my technical work, thinking and experience. Above all, this is my story of bringing an idea to fruition while digging into the world of traditional engineering.

Outline

The scope of the project is fairly broad, so naturally, there’s a lot that I’m going to cover in this post. To help set some expectations on what you’ll encounter, I’m going to cover the three main stages of the project consisting of planning, building and evaluating; each covering the technical aspects related to industrial design, electronics and mechanics. In the planning section you can expect to read about the requirements, project plan and design of the product. In the building section, I’m going to cover the process of sourcing materials, prototyping and building the finished product. I’ll be wrapping up with a section dedicated to how the product was tested and some reflections on how I would approach the project again given the experience.

Related Work

While I was in the midst of doing some brainstorming last December I came across a series of YouTube videos by Jaimie Mantzel covering his experience building 3D printed toy hexapods. His “3D printed big robot” series really captured his enthusiasm and energy for the medium and while I wasn’t going to be making something as complicated as a hexapod, it was helpful to get a window into someone else’s mind and see how they approach the problem of making a product from scratch. Hopefully this document will inspire others to get out there and make something as much as these videos inspired me to do the same.

Planning Phase

Requirements

I designed my avatar about ten years ago and in reflecting on how I illustrated it at the time I began to think about what it would do in the real world. For starters, I envisioned an illuminated eye and chest opening with the later glowing on and off. The second thing I envisioned was that the arms would be able to swing back and forth opposite to one another giving the illusion of body language depending on the initial position of the arms: straight down giving the impression of marching, forward as though it were in a zombie state, all the way up as though in a panic and flung backward as though it were running around frantically. In short a variety of different personas.

Implicit to these behaviors are some underlying requirements. The toy requires power, so it makes sense to provide an on-off button somewhere on the design that is easy at access while the arms are in motion. Since the arms are in motion, it’s begs the question of for how long are the arms swinging in each direction and how quickly. Finally there is the frequency at which the chest lights pulsate on and off and with what type of waveform. The physical enclosure would be required to enclose all of the electronics and hardware components and also provide a means of assembling the parts within the enclosure and then providing a mechanism for securely closing the enclosure.

Since we are talking about engineering it makes sense to have a handful of engineering centric requirements. From an electronics engineering point of view, the components must be within their stated current and voltage tolerances as the power supply diminishes over time. From a mechanical point of view, the motor must supply sufficient torque to the mechanical system to ensure efficient transfer of motion to the arms so that the movement remains fluid, plus the product would need to be stable under static and dynamic loads. Finally, from an industrial design point of view, the product itself must be sturdy enough to withstand the forces that will be applied to it and be designed in a way that the fabrication process will yield a quality result.

Ultimately, we are talking about making a consumer product. That product needs to be polished in its appearance and stay true to the original avatar illustration. The product needs to be conscious of its life cycle as well in terms of being made from environmentally friendly components and practices, to being efficient in its use of energy and being capable of being recycled at the end of its life. As is the case with any project, there are a number of more nuanced requirements imposed by each of the components and tools used in the process of creating the product. I will discuss along the way how these constraints affected the project.

Methodology

Thinking about how to approach the project, I thought about how I’d approached projects of similar size and scope. My approach typically follows the iterative and incremental development methodology; do a lot of up front planning, cycle through some iterations and wrap up with a deployment. Rinse and repeat.

Center: Project activities and outputs (bold) for each stage consisting of initial planning (green), development iteration (blue), and deployment (maroon) stages.
methodology


In the introduction I talked about my thought process and motivation that constituted the brainstorming that was done to generate the requirements. From these requirements, I broke the problem down into smaller more digestible components that I could research and learn the governing models that dictate how those components behave from a mathematical point of view and on the computer through simulations. With that understanding, it was possible to put together a design that fulfills a specific set of conditions that result in the desired set of outputs. This design is the cornerstone of the initial planning.

The bulk of work is based in working through iterations that ultimately result in working components based on the design that was produced in the planning stage. Each iteration corresponds to a single component/requirement that starts off with building a prototype. For electronics this is done by prototyping on a breadboard, mechanics and industrial design with cardboard elements. The result is a functioning prototype that is used to create a refined design for the component that is then built. For example, a soldered protoboard or 3D printed volume. A completed component is tested and if accepted, stored for assembly.

As accepted components are completed, they are assembled into the broader view of the product. Each component is tested as part of the whole and if working correctly, fastened into place. Once all of the components are incorporated, the end product is tested and ultimately accepted. Throughout the process, if a particular output for an activity fails, then the previous activity is revisited until the root cause is identified, corrected and the process moves forward to completion.

Design

Industrial Design

Part Design

Knowing I didn’t know what I didn’t know about how to make a durable product, I did some research about part design and came across a set of design guidelines from Bayer Material Sciences covering the type of features that are added to products to make them more resilient to the kind of abuse consumer products are subjected to. This was helpful since it gave me a set of primitives to work with and in this project I ended up using a few of these features for providing strength to the product- ribs, gussets and trusses- and a few for allowing parts to be mated together- counterbores, taps and bosses.

Left-to-right: Part design features used in the design of the product consisting of ribs, gussets, counterbores and bosses.
part-design


Ribs are used whenever there is a need to reduce the thickness of a plate and retain the plate’s original strength. When the thickness of the plate is reduced, so is the volume, and hence the cost but so too is the plate’s strength. To compensate, a rib is placed along the center of the plate and this increases the plate’s strength to its original state. A similar approach is deployed when talking about gussets as a way of providing added strength between two orthogonal faces. While not depicted above, the last technique deployed were trusses. Like what you’d find in the frames of your roof, the truss is a series of slats that form a triangular mesh that redistribute forces placed on the frame allowing it to take on greater load.

Counterbores are used so that the top of a machine screw sits flush or below the surface that needs to be fastened to another. The machine screws are then fastened to either a tap or a boss. A tap is a bored out section of material that is then threaded to act like a nut. Since we want to minimize material, the alternative is to carve out the material around the bore and leave a standing post that the machine screw will fasten to. Since the boss is freestanding, it may have gussets placed around its perimeter depending on the boss’s height.

Modeling

The first step in getting the 3D model put together was to use the pixel art version of my avatar to create a vectorized version for the purpose of developing a system of units and measurements that I could then use to develop a 3D model of the product in OpenSCAD. After having a chance to learn the software and its limitations, I set out to create a series of conventions to make it easy to work with parts, assemblies, enclosures in a variety of units and scales. Since real world elements would factor into the design of the product, I included all of the miscellaneous parts into the CAD model as well to make it easier to reason about the end result. After about a month of work the model was completed, let’s take a look at how it all came together.


The product consists of two arms, body, bracket and back plate. Each arm consists of a rounded shoulder with openings for fastening shaft collars; the shaft collars themselves and the shaft that extends from the body. The extended arm is hollow with interior ribs to add strength to the printed result. To support the printing process, small holes are added on the underside so that supporting material can be blown out.

On the exterior face of the back plate, the embossed designer logo, copyright and production number are provided to identify the product. Counterbores allow machines screws to be fastened to the main body at the base of legs and back of the head. On the interior face, the electronic components are fastened to bosses using machine screws. Since the back plate is just a thin plate, ribs were added to increase that plate’s strength.

The body has an opening on the top of the head for the on-off switch, and the face an opening for the eye plate and on the chest an opening for the chest plate. Counterbores line the hips so that machine screws can be fastened to the bracket to hold it in place. On the interior, horizontal bosses mate with counterbores on the back plate and several trusses and ribs were added to provide strength.

Left-to-right: Symbols and details consisting of the resin identification code (RIC) for polyamide 2200, waste electrical and electronic equipment (WEEE) to promote recycling, my personal logo with production number and identifying information.
symbols


A shelf separates the eye cavity from the chest cavity so that illumination from one doesn’t interfere with the other. Under the interior of the shoulders are the RIC for the material, WEEE logo, and along the leg, text describing the product with title, designer, date and copyright.

Finally, the bracket consists of two flanges with openings for ball bearings and a main shelf with an opening for the motor and set screws to secure the motor. The bracket has four taps that mate with the counterbores along the hip of the body.

Analysis

While I had a set of guidelines on how to make the product durable, most of the modeling process was more art than engineering. Since the 3D printing process would be fairly expensive, I wanted some additional confidence that the result was going to come out sturdy, so I thought a bit about it from a physics point of view. I knew of stress-strain analysis and that to understand how a complex object responds to loads I would need to use a Finite Element Analysis (FEA) solver on the 3D model. I researched the subject a bit, and once I felt I had a working understanding, I decided to use CalculiX to perform the actual computations. This section will cover the background, process and results at a very high level.

Stress-Strain Analysis

When a physical body is put under load, the particles of the body exert forces upon one another; the extent of these internal forces is quantified by stress. When the load begins to increase beyond the material’s ability to cope, the particles may begin to displace; how much they move about is quantified by strain.

Center: Stress-strain curve.
stress-strain


For small amounts of strain the material will behave elastically; returning to its original form once any applied forces are removed. As the amount of strain increases, and consequently the stress past the yield stress, the material begins to behave plastically; first hardening and then beginning to neck (i.e., thinning and separating) until it finally fractures. The specific critical values will depend entirely on the material and in this project an isotropic material, Polyamide PA 2200 (Nylon 12), will be used in the 3D printing process.

For a durable product, we obviously want to avoid subjecting the body to any forces that will result in permanent deformation which means keeping stress below the yield stress and even lower from an engineering point of view. The acceptable upper bound is given by a safety factor that linearly reduces the yield stress to an acceptable level. According to the literature a safety factor in the range N \in [1.1, 1.5] is appropriate.

To establish a design criteria, I went with a safety factor of N = 1.5. The material datasheet, omitted the precise yield value, but upon further research, the average yield stress for Nylon 12 was reported to be \sigma_Y = 33 \text{ MPa}. Thus, an upper bound of \sigma_{N} = 22 \text{ MPa} will be used as an acceptable level of stress- which is on the order of about a five hundred pound object resting on a square centimeter of area. While that may make the idea of performing the full analysis overkill, it’s still valuable from an intuition building point of view.

Linear Stress-Strain Relationship

Given that we want to stay within the linear region, we can now begin to look at the specific relationship between stress, \sigma, and strain, \varepsilon, for a three dimensional point which is given by a system of partial differential equations subject to equilibrium and compatibility conditions, fixed (Dirichlet) and load bearing (Neumann) boundary conditions:

\sigma C = \varepsilon


Both stress and strain are second-order tensors that relate how each of the three bases of a coordinate system relates to one another. When acting in the same dimension, the result is normal stress, \sigma_{xx}, and strain, \varepsilon_{yy}, otherwise the result is shear stress, \tau_{xy}, and (engineering) shear strain, \gamma_{xz}. The strain terms are partial derivatives of the displacement field, u(\vec{x}), to be determined and stress terms are constants. C is the elasticity matrix that relates the two.

Since we are working with an isotropic material, the resulting equations can be simplified to the following:

\displaystyle \begin{pmatrix} \varepsilon_{xx} \\ \varepsilon_{yy} \\ \varepsilon_{zz} \end{pmatrix} = \frac{1}{E} \begin{pmatrix} 1 && -\nu && -\nu \\ -\nu && 1 && -\nu \\ -\nu && -\nu && 1 \end{pmatrix} \begin{pmatrix} \sigma_{xx} \\ \sigma_{yy} \\ \sigma_{zz} \end{pmatrix}

\displaystyle \gamma_{xy} = \frac{\tau_{xy}}{G} \quad \gamma_{yz} = \frac{\tau_{yz}}{G} \quad \gamma_{zx} = \frac{\tau_{zx}}{G}


Characteristic Description Polyamide 2200 Values
Young’s modulus Slope of the stress-strain curve in the linear region. E = 1.7 \text{ GPa}
Poisson’s ratio Measure of how much a material will reduce as a consequence of being stretched. \nu = 0.4
Shear modulus Function of the previous two and quantifies how force is needed before the material begins to shear. G = \frac{E}{2(1+\nu)} = 0.61


Finite Element Method (FEM)

To determine the stress and strain of a body under load we’ll rely on the FEM, a general purpose numerical method for calculating the approximate solution to a boundary value problem whose analytic solution is elusive. The general idea is that the problem domain can be broken into smaller elements, each analyzed individually, and the corresponding analyses combined so that an overarching solution can be determined.

Center: Example domain with Dirichlet and Neumann conditions converted into a mesh consisting of linear triangular elements, Dirichlet nodes and Neumann edges.
triangulation


In the discretization step, the exact elements depend on the nature of the problem being solved, and in the case of stress analysis, into (linear or quadratic) tetrahedral elements consisting of nodes, edges and faces. In general, the nodes are being subjected to (unknown) internal and (known) external forces and the displacements of the nodes are to be determined. The relationship between the two is assumed to be linear. Thus, the following equation characterizes the state of the physical model at the element.

\vec{f} =\textbf{k} \vec{u}


Where k is the stiffness matrix, \vec{u} is the displacement vector and \vec{f} is the force vector (also known as the load vector). Fixed boundary conditions are defined in the displacement vector and load boundary conditions in the force vector when necessary. After defining the relationship at each node, the assembly process aggregates each statement into the global stiffness matrix which represents the state of the full physical model.

\vec{F} = \textbf{K} \vec{U}


Standard algorithms such as Gaussian Elimination and the Gauss-Seidel Method can be used to solve for the displacement vector. With the displacement vector, stress and strain can then be computed at the nodes and interpolated across each element to produce the desired stress analysis. As the number elements increases, the error between the exact and approximate solution will decrease. This means that the FEM solution serves as lower bound to the actual solution.

Tool Chain
Left-to-right: Interchange formats between applications.
fea-workflow


Given the theory, it’s time to assemble the tools to carry out the job. The abundance of free computer aided design (CAD) and engineering (CEA) software made it easy to narrow down the options to OpenSCAD to define the geometry, MeshLab to clean the geometry, Netgen to mesh and define boundary conditions, and finally CalculiX to perform the necessary calculations and visualize the analysis. While each tool is excellent at carrying out their technical tasks, they are less polished from a usability point of view so additional time was spent digging under the hood to deduce expected behavior. Given the extra time involved, it’s worth covering the steps taken to obtain the end results.

The geometry of the product was modeled in OpenSCAD using its built-in scripting language. To share the geometry with Netgen, it is exported as a Standard Tessellation Language (STL) file which consists of a lattice of triangular faces and their corresponding normal vectors. Sometimes I found the exported STL file from OpenSCAD would cause Netgen to have a hard time interpreting the results, so MeshLab was used to pre-process the STL file and then hand it off to Netgen.

Netgen is used to load the geometry, generate the mesh and define boundary conditions. Once the geometry is loaded and verified with the built-in STL doctor, the engine is configured to generate a mesh and the process (based on the Delaunay algorithm) is carried out. Once the resulting mesh is available, the faces that correspond to the boundary conditions are assigned identifiers so they can be easily identified in CalculiX. The end result is exported a neutral volume file that CalculiX will be able to work with.

CalculiX consists of two components: GraphiX (CGX) and CrunchiX (CXX). CGX is used as a pre-processor to export the mesh in a format (MSH) that CCX can easily interpret, and specify and export the boundary conditions consisting of the fixed surfaces (NAM) and load conditions (DLO). CCX takes a hand written INP file that relates the material properties, mesh, and boundary conditions to the type of analysis to perform and then CCX carries out that analysis and outputs a series of files, most notably, the FRD file. CGX is then used as a post-processor to visualize the resulting stress and deformation results.

Finite Element Analysis (FEA)

The completed product will have pressure applied to the top of the head whenever the pushbutton is pushed to turn the product on or off; based on the design criteria, a uniform static pressure of 22 \text{ MPa} will be applied across the top of the head for the load boundary condition. It will be assumed that the product is sitting on a surface such that the bases of the feet are fixed producing the remaining boundary conditions.

Six configurations were run in order to evaluate the designs consisting of three mesh granularities against the model before and after strengthening enhancements were introduced. For the purpose of the analysis, it is assumed that the eye, chest and back plate are fixed to the body.

Left-to-right: Displacement before and after, and Von Mises stress before and after for the “Very Fine” granularity.
correct-fea


Looking at the plots, the maximum displacement is centered about the through hole for the pushbutton which is consistent with one’s intuition. It appears that stress is most concentrated along the front where the head meets the shoulders and along the rim of the through hole for the pushbutton which matches up with the literature. After enhancements were introduced, it appears that displacement was reduced and that stress became more concentrated. Quantitatively:

(Enhancement) (Mesh Size) Stress (MPa) Displacement (mm)
Min Max Min Max
Before Moderate 0.0166 1.27 0 0.519
Fine 0.0109 1.83 0 0.888
Very Fine 0.00151 5.99 0 2.01
After Moderate 0.000648 2.5 0 0.631
Fine 0.000348 5.06 0 1.11
Very Fine 0.000148 11.2 0 1.75


After collecting the extremum from the test cases, the stress results seemed spurious to me. It didn’t feel intuitively right that applying a large amount of pressure to the head would result in at most a half of that pressure appearing throughout the body. I am assuming that there was a mix-up in the order magnitude of the units somewhere along the way. If the calculations are correct, then everything will be well below the yield stress and the product will be able to support what seems like a lot of stress. On the other hand, if the numbers are wrong, then I can’t make any claims other than relative improvements in the before and after; which was the main reason for carrying out the analysis.

From the literature, a finer mesh (i.e., a greater number of nodes) results in more accurate results. Looking at the outcome of the “Very Fine” mesh shows that the maximum stress in the product after enhancements is greater than the maximum stress before changes. However, the product is more rigid after the enhancement and admitted a reduced maximum displacement. This seems like an acceptable tradeoff since the goal was to make a product sturdier through enhancements.

Mechanics

Construction
Left-to-right: Technical drawing of the front and side views of the mechanical system. Actual gears will have an involute profile.
mechanical-drawing


The next step in completing the design of the product was to focus on how to make a machine to rotate the arms. Not knowing a whole lot, the first step was to read up on the established elements and to think how they could be used to fulfill my needs. Out of this reading I came across the differential and how it was configured to rotate shafts at different speeds. Deconstructing the mechanism down to its primitive components enabled me to see how I could borrow from that design to come up with my own.

Gearmotor

At the heart of the mechanical system is a 100:1 (gear ratio) gearmotor consisting of a direct current (DC) motor and a gear train. For every rotation of the output shaft, the motor’s shaft rotates 100 times. This is achieved through the arrangement of gears in the gear train attached to the DC motor’s shaft. Since torque is proportional to the gear ratio, this means we get greater mechanical advantage.

Gear Train

The gearmotor is used to drive a gear train consisting of three gears: a pinion gear attached to the shaft of the gearmotor and two bevel gears that are perpendicular to the pinion. As the pinion gear rotates clockwise (resp. counterclockwise), one of the bevel gears will rotate clockwise (resp. counterclockwise) and the other will rotate counterclockwise (resp. clockwise). The pinion gear and bevel gears that will be used are in ratio of 1.3:1.

Shaft Assembly

To fix elements to the shaft, shaft collars are used to pinch the element into place along the shaft and each shaft collar is then fastened to the shaft using screw sets to retain the position and inward pressure on the element. Each bevel gear is connected to a shaft that extends outward to an arm. The main elements fastened using the sandwiching technique are the bevel gears, radial ball bearings that mesh with the bracket and body, and the arm. Outside the body, a spacer is used to displace the arm from the body and openings exist in the shoulder of the arm to access the shaft collars used to secure the arm.

Bracket

A modified clevis bracket will be used to hold the mechanical elements in place. The bracket consists of an opening in the middle to house the gearmotor along with two set screws openings to fasten it in place. To allow the bracket to be fitted with the body, machine screws are tapped along the edges of the bracket. Along the flanges of the bracket are openings for the radial ball bearings and each flange are supported by gussets to ensure that they don’t easily break off.

Analysis

Since we want to control the output of the arm as much as possible, we’ll want to explore how the arms behave at different orientations. To do so, we’ll assume that no external forces (with the exception of gravity) are acting on the arm and that the motor we are using a permanent magnet, direct current motor with a gearbox, specifically the KM-12FN20-100-06120 from the Shenzhen Kinmore Motor Co., Ltd. There are three views of the model that we’ll take into account: the arm, and the motor’s physical and electrical characteristics. Each view of the model will be presented, and then used to answer two questions (1) are there any orientations of the arm that cannot be supported by the motor and (2) are there any orientations that the motor cannot accelerate up to in order to achieve a steady angular velocity.

Arm
Center: Free body diagram of the arm. The inner most circle is an opening for the shaft and the next inner more circle is an opening for the shaft collar.
physics


While the geometry of the arm is more complex than a standard geometric primitive, it will be modeled as a cuboid with square edge length of, H = 1 \text{ in} and projected length L = 3.5 \text{ in}. The wall thickness, wt = 3/32 \text{ in}, gives a total approximate volume of V = 0.704 \text{ in}^3. According to the material’s datasheet, the density of the printed material is \delta = 0.93 \text{ g}/\text{cm}^3 giving us an approximate mass of m = 11.5 \text{ g}.

Since we are talking about rotating the arm, the moment of inertia will come into play. We’ll use the standard formula for a cuboid, superposition principle to account for the hollow interior and parallel axis theorem to deal with the pivot about the elbow in order to come up with the actual moment of inertia for the model, M_{\text{Arm}} = 214 \text{ g cm}^2.

Physics

We have a series of torques being applied to the arm: first from the motor itself, \tau_m, the viscous friction, \tau_f, and finally from gravity, \tau_g.

The torque from the motor, \tau_m = K_m I, is proportional to the current, I, that is applied with respect to the motor’s torque constant, K_m. The torque constant can be calculated by taking the quotient of the stall torque and current. For the motor that will be used, that values comes out to be K_m = 0.069 \text{ Nm/A}.

The viscous friction, \tau_f = K_f \omega, is proportional to the speed at which the motor is rotating and the motor’s viscous friction constant, K_f. The datasheet doesn’t include this value, so a near zero value was chosen based on properties of similar motors.

Torque due to gravity, \tau_g = \lVert F_g(\theta) \times \Delta(\theta) \rVert, is a function of the force due to gravity, F_g(\theta) and the orientation of the arm, \theta. Assuming that gravity and friction are acting in opposition of the motor, the net torque is the sum of these torques giving:

\displaystyle M_{\text{Arm}} \frac{d^2}{dt^2} \theta = - m g \Delta \sin(\theta) - K_f \frac{d}{dt} \theta + K_m I


Electronics

The ideal electronic model of the motor system is a series circuit consisting of the voltage, V, applied to the terminals of the motor, the motor’s internal resistance, R, due to the coils, resulting inductance, L, and the back electromagnetic field, V_b, generated by the motor.

Center: Electronic model of an ideal DC motor. The node between the voltage and resistor will indicate the reference node in all electrical schematics.
motor-model


By Kirchhoff’s voltage law, the voltage applied to the terminals is equal to the sum of the potentials across each of the components giving:

\displaystyle V = L\frac{d}{dt}I + R I + K_b \frac{d}{dt} \theta


The three constants in the equation, L, R, K_b are all unknown with the exception of the motor voltage constant, K_b, which is just the same as the motor torque constant K_m.

Since the resistance and inductance are not listed on the datasheet for the motor and could not be located online, we’d have to purchase the motor and then experimental determine their values. To complete the analysis, we’ll make simplify assumptions to work around this limitation.

Completed Model

Rewriting the physical and electronic governing equations in terms of the angular velocity, \omega, we end up with a system of inhomogeneous linear ordinary differential equations which can be solved using the technique of variation of parameters.

\displaystyle \frac{d}{dt}\underbrace{\begin{pmatrix} I \\ \omega \end{pmatrix}}_{\vec{x}} = \underbrace{\begin{pmatrix} -\frac{R}{L} && -\frac{K_b}{L} \\ \frac{K_m}{M_{\text{Arm}}} && -\frac{K_f}{M_{\text{Arm}}} \end{pmatrix}}_{\textbf{A}} \begin{pmatrix} I \\ \omega \end{pmatrix}  + \displaystyle \underbrace{\begin{pmatrix} \frac{V}{L} \\ -\frac{m g \Delta }{M_{\text{Arm}}} \end{pmatrix}}_{\vec{b}} \to \frac{d}{dx} \vec{x} = \textbf{A} \vec{x} + \vec{b}


In doing so, we’d uncover nonlinear transient behavior and steady state fixed values that both current and angular velocity will approach in the limiting case.

Now that we have a complete model, we’ll make some simplifying assumptions in order to resolve questions (1) and (2). First, we’ll assume that the viscous friction constant is several orders magnitude smaller than the other terms and can be set to zero. Second, we’ll assume that the motor has accelerated up to a fixed angular velocity. Finally, we’ll assume the motor will always be supporting the worst case load from the arm. Under those assumptions we arrive at:

\displaystyle \begin{pmatrix} V \\ m g \Delta \end{pmatrix} = \begin{pmatrix} R && K_b \\ K_m && 0 \end{pmatrix} \begin{pmatrix} I \\ \omega \end{pmatrix}


To approach question (2), let’s think about the current side of the system. The maximum current takes place when the motor shaft is not rotating. Using an ohmmeter to determine the terminal resistance, R = 20.6 \Omega, the maximum current works out to be I_{\text{Max}} = 291 \text{ mA} which is higher than the rated current of I_{\text{Rated}} = 135 \text{ mA} but less than the stall current of I_{\text{Stall}} = 420 \text{ mA}. From a steady state point of view the motor will operate within the specified bounds.

However, when we go to reverse the motor, we’ll introduce a drop from the steady state speed down to zero and then ramp back up in the opposite direction. So in reality, we may observe current changes on the order of twice that of I_{\text{Max}} which will push us outside the stated boundaries so we’ll need to ensure that we operate a voltage no higher than V_{\text{Max}} \le 4.32 \text{ V}. Provided we keep the voltage below 72 \% the rated voltage of 6 \text{ V}, sufficient current will be supplied to motor and it will rotate up to a constant angular velocity and thus, obtain any desired orientation.

Electronics

The final step in completing the design was to focus on how the electronics would illuminate the eye and chest cavity and drive the rotation of the arms. Being the main focus of the project, I will be covering how the electronics fulfill these requirements in a bit more depth than the two prior sections.

Motor Control

The motor control subsystem is responsible for managing how frequently and how quickly the motor needs to rotate in each direction. The subsystem consists of a timing circuit determining how frequently the motor will rotate, a pulse width modulated circuit to determine how quickly, a Boolean logic circuit to form composite signals that will be feed to a motor driver, and an H-Bridge circuit serving as the motor driver used to drive the gearmotor.

Series Resistor-Capacitor (RC) Circuits

To understand the basis for timing we’ll need to discuss series resistor-capacitor circuits briefly. Assume a series circuit consisting of a voltage source, V_{\text{cc}} (Volts), resistor with resistance R (Ohms), and a capacitor with capacitance C (Farads). There are two scenarios to consider, the first in which the capacitor is fully discharged and second when it is fully charged.

rc-circuit-charging

In the first, the capacitor will begin to charge allowing some of the current to pass through and then, once fully charged, it have such impedance that no current will flow through. Kirchhoff’s voltage law says that the voltage across the resistor and capacitor is equal to the supply voltage.

V_{cc} = V_R(t) + V_C(t)


Since there is one path for current to flow through the entire circuit, the amount of current flowing through the resistor is the same as the capacitor. Using Ohm’s law and the definition of capacitance and current we arrive at an initial value problem consisting of a linear ordinary differential equation that can be solved using the technique of integrating factors.

\displaystyle \frac{V_{cc}}{ RC} = \frac{d}{dt}V_C(t) + \frac{1}{RC}V_C(t)


Solving for equation we get a curve that grows with exponential decay and in the limiting case, approaches V_{cc}. For mathematical simplicity, let \tau = 1/RC be the timing constant.

\displaystyle V_{C}(t) = V_{cc} \left ( 1 - e^{-\tau t} \right )


rc-circuit-discharging

In the case of the discharging capacitor, Kirchhoff’s voltage law says the voltage of the capacitor is equal in magnitude to the voltage across the resistor.

V_C(t) = -V_R(t)


Making the same assumptions as before, we arrive at another initial value problem consisting of a linear ordinary differential equation that can be solved using its characteristic equation.

\displaystyle 0 = \frac{d}{dt}V_C(t) + \frac{V_C(t)}{RC}


As a result we get a curve that declines with exponential decay that will eventually approach zero in the limiting case. Using the timing constant again, we arrive at the following curve.

\displaystyle V_C(t) = V_{cc} e^{-\tau t}


Timing
Center: 50% Duty Cycle 555 based Circuit. Source: Adapted from National Semiconductor LM555 datasheet Page 10, Figure 14.
555


In order to tell the motor how long it needs to be on in one direction, a 555 integrated circuit is used to generate a square waveform of a fixed frequency. This is done by chaining a RC circuit with the inputs of the integrated circuit in astable mode to generate a 50% duty cycle waveform. The duty cycle is a way of measuring what percent the resulting square wave will spend in a high state relative to the period of the waveform. Here, we’ll have equal parts high state and low state each period.

Center: Illustration of the 555’s output as the capacitor voltage charges and discharges after hitting trigger and threshold values.
555-output


When an input voltage of one third that of the reference is applied to the trigger input, the output of the integrated circuit will be the same as the reference voltage. When two thirds the reference voltage is applied to the threshold input, the output voltage goes to ground. In this set up, the capacitor in the circuit will be continuously charging until the ceiling has been hit and then discharge until the floor and so on.

Characteristic Time (seconds)
Initial ramp up time \ln(3) R_1 C
Discharge times \displaystyle t_1 = \left ( \frac{R_1 R_2}{R_1 + R_2} \right ) C \ln{\left( \frac{R_2 - 2R_1}{2R_2-R_1} \right)}
Subsequent charge times t_2 = \ln(2) R_1 C
Period T = t_1 + t_2
Frequency \displaystyle f = \frac{1}{T}
Duty cycle \displaystyle D = \frac{ t_1  }{ T}


To calculate the values for R_1, R_2 \text{ and } C, I wrote a program to explore the combinations of standard resistor and capacitor values, then narrowed it down to those combinations that would give nearly the desired duty cycle and a period of about a few seconds. Values of 4.7 \text{ k} \Omega, 2 \text{ k} \Omega, \text{ and } 100 \text{ } \mu F for the variables gave a period of roughly 6.5 seconds and a duty cycle of 49.6\% providing the closest fit.

Pulse Width Modulation (PWM)
Center: PWM Circuit. Source: Adapted from Afrotechmods.com PWM Tutorial.
pwm


In order to control how fast the motor rotates, we’ll take advantage of the fact that the motor’s speed is linearly proportional to the voltage supplied to the motor and that the average output voltage of a PWM signal is linearly proportional to its duty cycle. To realize that plan, a 555 integrated circuit in astable mode is used to generate a high frequency signal whose duty cycle is controlled by the use of a potentiometer.

The fundamental operation of the 555 integrated circuit remains unchanged, however, the PWM circuit has a different topology than the timing circuit’s and as a result, has different timing characteristics. When the circuit is initially charging, current will go through R_1, the bottom diode, R_2 and C_1 until the threshold values bound has been reached. Then, during the discharge phase, current will then travel through the complementary side R_2^{\prime} of the potentiometer, the top diode to the discharge pin until the trigger voltage has been reached.

Using values of R_1 = 330 \Omega, R_2 = 0 - 100 \text{ k}\Omega and C_1 = 0.1 \mu \text{F} we find the following:

Characteristic Time (seconds)
Initial ramp up time \ln(3) (R_1 + R_2) C_1
Discharge times t_1 = ln(2) R_2^{\prime} C_1
Subsequent charge times t_2 = \ln(2) (R_1 + R_2) C_1


Thus, we’ll end up with a circuit running at 144 \text{ Hz} with a duty cycle range of 0.005\% - 99.7\% giving a very broad range of voltage values that can be chosen at run time.

NOT-Gates and Resistor-Transistor Logic (RTL)
Center: RTL NOT-Gate using 2N3904 NPN Transistor
rtl-not-gate


To begin talking about the logic used to combine the PWM and timing signals, we’ll need to perform negation of a signal, A, into \bar{A}. The simplest such way is to use a RTL based NOT-Gate as depicted above. Assuming V_cc = 5\text{ V} is logical true, and zero volts is logical false, then when A = T, then we’ll switch the transistor on so that \bar{A} = F, and vice versa when A = F to switch it off so that \bar{A} = T.

To determine the values of the resistors, we’ll need to look at the low-frequency, large signal model of the transistor which consists of three states: cut-off, active-linear and saturation. For the logic gate, we’ll want to minimize the active-linear region and focus on flip-flopping between the cut-off and saturation regions based on the value of A.

For the output to be logically true, V_{cc} = 5 \text{ V}, the input voltage must be less than or equal to the saturation constant between the base and emitter, V_L = V_{\text{BE(SAT)}} = 0.65 \text {V}. This condition will put the switch into a cut-off state.

If however, the input voltage is greater than V_{\text{BE(SAT)}}, then the transistor will be in saturation mode and from Kirchhoff’s current laws we’ll see that the current for the base and collector are:

\displaystyle I_B = \frac{V_{\text{In}} - V_{\text{BE(SAT)}}}{R_1} \quad I_C = \frac{V_{cc} - V_{\text{CE(SAT)}}}{R_2}.


Based on the condition that the ratio of the collector current and base current be less than the gain, I_C < I_B \beta, we’ll find that

\displaystyle \underbrace{ \frac{1}{\beta}\frac{R_1}{R_2} \left ( V_{cc} - V_{\text{CE(SAT)}} \right )  + V_{\text{BE(SAT)}}}_{V_H} < V_{\text{In}}


Center: Transfer characteristics of the NOT-Gate. Resistor values will be picked as to minimize the active linear region.
transistor-switch


Given the latest piece of information, it’s possible to decide on a value of one resistor and pick the value of the other such that the collector resistor is several times larger than the base resistor and greater than 25 \ \Omega to ensure that the max current, I_{\text{C(Max)}} = 200 \text{ mA}, into the transistor is not exceeded. Based on these criteria, I went with R_1 = 330\ \Omega, R_2 = 1 \text{ k} \Omega.

Logic
Center: Logical operations performed on the PWM and timing signals for the left and right output signals.
logic-output


Given the timing signal and the PWM signal, we’ll produce a composite signal that will retain the period of the timing signal while controlling the observed amplitude from the PWM signal. This will give a signal that can be used to control one of the terminals of the gearmotor. Since the gearmotor terminals are designed to have one be in a ground state while the other in a high state, there will be a second composite signal that is simply the composite of the negation of the timing signal with the PWM signal.

Center: Completed logic circuit.
logic


Since there were multiple signals to conjoin, I opted to use the 7408 quad, two-input AND-gate integrated circuit based on Transistor-transistor logic (TTL), a more efficient way of approaching the problem. I could have just as well used RTL to perform the conjunction, but the protoboard real estate required exceeded what I’d allocated and it simplified the design. There were NOT-gate integrated circuits that I could have used as well (e.g., 7404), but I decided to use the RTL based solution since it gave me an opportunity to learn the basics of transistors which would be required to understand the motor driver.

Driving the Motor
Center: Motor driver circuit. Source: Adapted from Texas Instruments SN754410 Datasheet Page 6, Figure 3.
h-bridge


With the motor controller specified, it’s time to look at the motor driver. The gearmotor will draw a fair amount of current and since most of the logic circuitry is designed for low current consumption, it’s not feasible to drive the motor using the controller. Instead, an H-Bridge will be used to supply enough current while isolating the controlling logic.

An H-Bridge consists of several transistor switches and fly back diodes for controlling the flow of current. The motor is designed to rotate clockwise or counterclockwise depending on the polarity of the charges applied to the terminals. Since we’ve got two signals that designate which terminal is ground and which is high, it’s a matter of feeding the signals to the inputs of the bridge that correspond to rotating in the desired direction.

I’d put together two designs, one using bipolar junction transistors (BJT) and one using the SN754410 quadruple half-H-bridge integrated circuit. The first required a handful of components and wanting to better understand transistors, I opted to go this route for prototyping. In creating the production protoboard I decided to go with the SN74410 for reason’s I’ll cover in that section. As far as the design is concerned, they are functionality identical for exposing a higher voltage source to a motor while insulating the lower voltage controller circuitry.

Completed Motor Controller
Center: Motor controller protoboard circuit. Wires between nodes are represented as lines with arrows and traces are solid lines. Primary output (gold), intermediate results (blue), ground (black), voltage high (red).
soldered---motor-control-pc


With a full list of schematics for the motor controller, the next step is to design the circuit that will be soldered to the controller’s protoboard. The motor controller will sit in one of the legs of the product and reside on a 2 \times 8 \text{ cm} protoboard. With the limited real estate, it is necessary to utilize each position on the protoboard. To do this, the PWM and timing circuits occupy the right-hand side of the board, while the logic circuitry occupies the left side. Two block terminals are used to route input and output signals for the logic voltage and ground, and the two output signals. The motor driver itself will reside along with the circuitry for the LEDs which will be covered in the next section.

LED Control

Overall, the product consists of a single red LED for the eye, three blue LEDs for the chest and three green indicator LEDs used for debugging the circuit. The eye LED is always on, and a constant 6 \text{ V} charge is always supplied when the product is on. The three LEDs are driven by a triangle oscillator and each of the indicator lights by their respective signals. One complication in designing the indicators is that the idealist view of driving them with 6 \text{ V} and switching them on and off with a transistor switch controlled by their respective signals consumes a lot of protoboard real estate. As a compromise, the indicators are driven by their signals.

Since the triangle oscillator represents the bulk of the circuit, this section will be dedicated to its analysis, operation and characteristics.

Voltage Divider

voltage-divider

Since we’ll be using a single supply operational amplifier design to control the chest LEDs, we’ll need to create a reference voltage between the supply and ground. This will be achieved using a voltage divider. By Kirchhoff’s voltage law we have V_{cc} = I (R_1 + R_2) which means that the voltage difference from left to center across the first resistor is V_1  = \frac{R_1}{R_1 + R_2}V_{cc} and V_2 = \frac{R_2}{R_1 + R_2} V_{cc} across the second resistor to ground. Since we want a voltage half that of the reference, R_1 = R_2 so that V_1 = V_2 = \frac{1}{2}V_{cc}.

Non-inverting Schmitt Trigger
Center: Voltage transfer characteristic of the non-inverting Schmitt Trigger which exhibits a hysteresis effect.
schmitt-trigger-transfer-ch

In the timing section we focused on creating a square wave output using a 555 timer. While this is one way to go about it, another is to use an operational amplifier based non-inverting Schmitt Trigger. The idea is that for a given voltage input, V_{\text{In}}, the output, V_{\text{Out}}, will be either the operational amplifier’s rail low, V_L, or rail high, V_H, voltage depending if the input voltage is increasing or decreasing past either the transition to lower, V_{TL}, or transition to higher, V_{TH}, voltage thresholds.

Center: Non-inverting Schmitt Trigger with reference voltage.
non-inverting-schmitt-trigg

In this configuration, the operational amplifier is used as a positive feedback loop, in which case there are two defining characteristics of its ideal behavior: (1) the output voltage of the amplifier, V_{\text{Out}} = A(V_{+} - V_{-}), is linearly proportional to the difference between the two terminals on the order of the amplifier’s gain, A, (2), there is no current flowing in to either of the terminals, I_{+} = I_{-} = 0. Based on these assumptions, we’ll apply Kirchhoff’s current law to the non-inverting terminal of the amplifier to determine the appropriate values for V_{TL} and V_{TH}.

\displaystyle I_{+} = I_{1} + I_{2} \implies 0 = \frac{V_{+} - V_{\text{In}}}{R_1} + \frac{V_{+} - V_{\text{Out}}}{R_2}

There are two cases to explore, in the first, we’ll assume V_{\text{Out}} = V_{H}. For that to be true, V_{+} \ge V_{\text{Ref}} due to characteristic (1). In the second, we’ll assume that V_{\text{Out}} = V_{L}, which means V_{+} \le V_{\text{Ref}} for the same reasons. Based on these two different sets of assumptions we find the following relationships.

\displaystyle V_{\text{TL}} = \left(\frac{R_1}{R_2} + 1 \right)V_{\text{Ref}} - V_H \left(\frac{R_1}{R_2}\right) \quad V_{\text{TH}} = \left(\frac{R_1}{R_2} + 1 \right)V_{\text{Ref}} - V_L \left(\frac{R_1}{R_2}\right)

On its own, the circuit won’t generate a square wave, but as the input varies with time, the circuit will flop-flop between ground and the supply voltage. The timing of which will be determined in part by the circuit’s noise immunity, i.e., the difference between the thresholds.

Inverting Integrator
Center: Inverting integrator with reference voltage.
inverting-integrator

To complete the triangle oscillator, we’ll need to review the inverting integrator based on an operational amplifier. The idea behind the circuit is that as the input voltage varies with time, the output voltage will be the negated accumulation of that input.

The inverting integrator is an example of a negative feedback loop. The characteristics that applied to analyzing a positive feedback loop also apply to analyzing a negative feedback loop with the additional characteristic that (3) the voltage of the two terminals is identical, V_{+} = V_{-}.

Par for the course, we’ll start by applying Kirchhoff’s current law to the inverting terminal of the operational amplifier.

\displaystyle I_{-} = I_R + I_C \implies 0 = \frac{V_{\text{In}} - V_{-}}{R} + C \frac{d}{dt} \left ( V_{\text{Out}} - V_{-} \right )
\displaystyle \implies \int_{0}^{t} \frac{d}{dt} \left ( V_{\text{Out}}(t) - V_{\text{Ref}} \right ) \, dt = -\frac{1}{RC}\int_{0}^{t} V_{\text{In}}(t) - V_{\text{Ref}} \, dt
\displaystyle \implies V_{\text{Out}}(t) = -\frac{1}{RC}\int_{0}^{t} V_{\text{In}}(t) \, dt + \left(\frac{t}{RC} + 1 \right ) V_{\text{Ref}}


Let’s assume that the input voltage can only take one of two values V_{\text{In}} = V_{cc} and V_{\text{In}} = 0 and that the reference voltage is half the maximum of these two voltage, V_{\text{Ref}} = \frac{1}{2} V_{cc}. Based on these assumptions the observed output voltage is then:

\displaystyle V_{\text{Out}}(t) =  \frac{1}{2}\left(1 \pm \frac{t}{RC} \right ) V_{cc}

When V_{\text{In}} = V_{cc} the output will decrease linearly and when V_{\text{In}} = 0 the output will increase linearly. If we uniformly toggle back and forth between these two values, then the output voltage will produce a triangle wave.

Triangle Oscillator
Center: Schmitt Trigger input (black) and output (blue).
triangle-oscillator-output

Now that the Non-inverting Schmitt Trigger and Inverting Integrator have been covered, it’s time to loop the two together so that the trigger’s output feeds into the integrator’s input and its output into the trigger’s input. Assuming that when the circuit is started that the trigger’s output is the high state, the input – and hence the integrator’s output- has to be greater than the trigger’s upper threshold. (The complementary set of events would take place if we had instead assumed that the trigger was originally outputting a low state.)

As the trigger’s output continues to be the high state, the inverting integrator’s output will linearly decrease over time. This output will continue to be fed back into the trigger until the trigger’s lower threshold is surpassed. Once this happens, the trigger’s output will be the low state. As the trigger’s output continues to be in the low state, the integrator’s output will linearly increase over time. This output will continue to be fed back into the trigger until the trigger’s upper threshold is surpassed. The trigger’s output will then be the high state and the whole cycle will repeat itself.

Center: Triangle Oscillator circuit using a LM358 dual operational amplifier. Source: Adapted from Op Amps for Everyone Page A-44 Figure A-44.
triangle

The completed circuit consists of a voltage divider, trigger and integrator around a LM358 dual operational amplifier. To provide a wide range of frequencies, I opted to use a potentiometer to control the frequency of the output rather than relying on a single fixed value resistor. This was done since I didn’t know what would be the ideal frequency and it bought me a range of solutions and not just one.

Based on the equations derived, the frequency and maximum outputs of the system are:

\displaystyle f = \frac{R_F}{4 C R_1 R_2}

Using values of R_1 = R_2 = 20 \text{ k}\Omega, R_F = 0-100 \text{ k}\Omega and C = 10 \ \mu \text{F}, buys a frequency range of 0-6.25 \text{Hz}. For the purpose of flashing a series of LEDs, this is sufficient. As far as the extrema of the output voltage is concerned, we are looking at:

\displaystyle V_{\text{Out}} = \frac{1}{2} \left( 1 \pm \frac{R_2}{R_F} \right) V_{cc}

The design will use blue LEDs which come with a voltage drop of about 3 \text{ V} meaning that for a value of R_F = 20 \text{ k}\Omega we should expect fairly triangular output in the lights, but as that value increases, and the resulting output window narrows, we’ll see only blips of light fade in, then out followed by a period of darkness before cycling.

Completed LED Controller
Center: Triangle oscillator, motor driver and LEDS protoboard circuit. Primary output (gold), intermediate results (blue), ground (black), logic voltage high (red), motor voltage high (purple).
soldered---main-pcb-schemat

All of the LEDs in the product in the chest cavity of the body and reside on a 5 \times 7 \text{ cm} protoboard. While there are numerous positions, most of the components on the protoboard were required to be in specific locations and took up a fair amount of space. The triangle oscillator took up the left-hand side of the circuit with the motor driver taking up the right-hand side. The top of the circuit consisted of the chest and eye LEDs and the bottom of the circuit had input and output block terminals for taking in logic and driving voltage as well as ground, and the two motor control signals. The output block terminals are then connected to the motor.

Power Control

In designing the electronics for managing the power in the product, I chose to provide two separate voltage sources: two AAA batteries giving a combined 3 \text{ V} and a single 9 \text{ V} battery. The former is used to power a boost converter up to 5 \text{ V} for the purpose of powering all of the logical circuits in the product; the latter is used to power a 6 \text{ V} linear regulator for the purpose of powering the LEDs and motor. Both voltage sources are controlled by a single latching push button.

Of the subcomponents in the circuit, the boost converter is the most interesting; this section will be primarily devoted to discussing its analysis, operation and characteristics.

Series-Parallel Resistor-Inductor-Capacitor (RLC) Circuits

To begin talking about the boost converter, it’s necessary to talk about the series-parallel RLC circuit which differs from the standard series and parallel circuit topologies in that the inductor runs in series to a resistor and capacitor in parallel.

Center: Series-parallel RLC circuit.
series-parallel-rlc

While the topologies may differ, the characteristics used to simplify the analysis of RLC circuits remain the same. When convenient, the following substitutions will be made:

Characteristic Equation
Natural frequency \omega_0 = \sqrt{\frac{1}{LC}}
Dampening attenuation \alpha = \frac{1}{2RC}
Dampening factor \zeta = \frac{\alpha}{\omega_0}
Dampened natural frequency \omega_d = \sqrt{\alpha^2 - \omega_0^2}

Based on Kirchhoff’s voltage law the voltage source is the sum of the voltage across the inductor and that of the RC subcircuit. Kirchhoff’s current law says that the amount of current flowing through the inductor is the same as the aggregate current flowing through the capacitor and resistor. Based on these assumptions, we arrive at the following second order linear nonhomogeneous ordinary differential equation:

\displaystyle V_{cc} \omega_0^2 = \frac{d^2}{dt^2} V + 2 \alpha \frac{d}{dt} V + \omega_0^2 V

The general solution for a differential equation of this form is to take the superposition of the homogeneous solution with the particular (nonhomogeneous) solution. For the former we’ll use the characteristic equation of the homogeneous equation and then the method of undetermined coefficients for the latter.

\displaystyle \lambda^2 + 2 \alpha \lambda + \omega_0^2 = 0 \implies \lambda = - \alpha \pm \sqrt{\alpha^2 - \omega_0^2} = - \alpha \pm \omega_0 \sqrt{\zeta^2 - 1} = -\alpha \pm \omega_d

Since we have a second order equation, we can run into repeated real roots (critically damped \zeta = 1), unique real roots (overdamped \zeta > 1) and unique complex roots (underdamped \zeta < 1) when solving the characteristic equation. Since the end goal is to understand to explore the boost converter, only the underdamped case will be reviewed. For the particular solution, V_p, we have a constant forcing function, g(t) = V_{cc} \omega_0^2, so the method of undetermined coefficients says we’ll end up with a constant valued particular solution. Taking these results together we arrive at:

\displaystyle V = e^{-\alpha t} \left( c_0 \cos(\omega_d t) + c_1\sin(\omega_d t) \right) + c_2


In order to determine the coefficients’ values, we’ll need to determine the initial conditions of the system. Initially, the inductor will resist any change in current, so since there is no current, the initial current is zero, I(0) = 0. If no current is following, then the inductor acts briefly like a switch and the voltage is then zero, V(0) = 0. Looking at the limiting behavior of the circuit, the inductor will turn into a plain connection and the capacitor will become fully charged and disappear from the circuit; this means that the steady state voltage will become the source voltage, c_2 = V_{cc}. As a result we end up with the following solution:

\displaystyle V = V_{cc} \left( 1 - e^{-\alpha t} \left( \cos(\omega_t) + \frac{\alpha}{\omega_d} \sin(\omega_d t) \right) \right)


Center: Output of an under dampened series-parallel RLC circuit with a low dampened natural frequency.
series-parallel-rlc-voltage


Looking at the voltage over time we see that the output voltage is greater than the input voltage at the beginning of the circuit’s uptime and as time elapses, the output voltage converges to the input voltage. The peak output voltage will be observed very early on at t_{\text{Max}} = \frac{\pi}{\omega_d}:

\displaystyle V_{\text{Max}} = V_{cc} \left ( 1 + \alpha \exp{ \left(-\frac{\alpha \pi}{\omega_d} \right ) } \right )


We’ll leverage this behavior to get the boost in voltage from the boost converter.

DC-DC Boost Converter
Center: DC-DC Switching Boost Converter.
boost-converter


The boost converter is a way of converting an input voltage to a higher output voltage by switching between two different states that charge and discharge the inductor’s magnetic field. In the charging state, S_1 is switched closed and S_2 is switched open for a period of time t_{\text{On}} resulting in two isolated circuits consisting of a single voltage supply and inductor circuit and a RC circuit. The RC circuit will discharge to produce a decreasing output voltage. In the discharge state, S_1 is switched open and S_2 is switched closed for a period of time t_{\text{Off}} resulting in a series-parallel RLC circuit that produces in an increasing output voltage. The output voltage is therefore the average of voltage over switching between the two states.

Center: Simplified boost converter output.
boost-converter-output


For a thorough analysis of the boost converter, you should refer to Wens and Steyaert from which the following input-output voltage relationship is attributed.

\displaystyle V_{\text{Out}} = V_{\text{In}} \frac{1}{1 - \delta} \quad \delta = \frac{t_{\text{On}}}{t_{\text{On}} + t_{\text{Off}}}


As the duty cycle \delta increases from zero to one, the output voltage will start off as the input voltage and increase towards infinity. Realistically though, this is not obtainable and a 5x multiple is a more reasonable upper bound.

3V to 5V Boost Converter

To realize this boost converter design, I went with the Maxim MAX630 to serve as the first switch in the system and a 1N4148 diode to serve as the second switch. (The diode functions as a switch by only allowing current to move in one direction.) According to the Maxim datasheet, the MAX630 works by monitoring the voltage on VFB and when it is too low, the MAX630 oscillates its internal N-channel MOSFET at a high frequency open and shut on LX to put the system into the charging state. Once VFB is above the desired voltage, LX is left open to put the system into the discharging state. This cycle repeats until the system is powered off.

Center: Boost converter. Source: Adapted from Maxim 630 Datasheet Page 11 Figure 5.
booster


Due to the oscillatory nature of the charging phase used by the MAX630, the analysis that was performed for the series-parallel RLC circuit is cumbersome to use here to determine the appropriate values for the passive components. Fortunately, the MAX630’s datasheet had a schematic for a 3 \text{ V} to 5 \text{ V} boost converter utilizing an inductance of \L = 470 \ \mu \text{H} and capacitance C = 470 \ \mu \text{F}. The voltage dividers on the left-hand side of the schematic are used for low battery detection and the voltage divider on the right-hand side is used in reference to the voltage comparison done by the VBF input. Based on the datasheet these values come out to be R_1 = 249 \text{ k} \Omega, R_2 = 499 \text{ k} \Omega, R_3 = 200 \text{ k} \Omega and R_4 = 540 \text{ k} \Omega.

Completed Power Controller
Center: Power management protoboard circuit. Primary output (gold), intermediate results (blue), ground (black), voltage high (red).
soldered---power-management


The power controller will sit in one of the legs of the body and reside on a 2 \times 8 \text{ cm} protoboard. The voltage regulator sits on the left-hand side of the circuit while the boost converter occupies the right-hand side. In between are the block terminals for taking in the on-off switch, grounds, 3 \text{ V} and 9 \text{ V} supplies. Above that block terminal is the output terminal providing 6 \text{ V}, 5 \text{ V} and ground.

Building Phase

Sourcing

Center: 3D printed enclosures, acrylic plates, protoboards, electronic, electromechanical and mechanical components.
parts-2


One thing that surprised me perhaps more than anything about this project was how difficult it was to find the right parts having the desired characteristics. Overall, I had orders with about a half dozen vendors from here in the United States and abroad.

3D Printing services were carried out by Shapeways, Inc. out of New York, New York. After receiving my package, I noticed a missing piece. After contacting their customer service they were able to resolve the matter and ship me a replacement part. Evidently since the missing piece was inside the main shell the operator didn’t see it on the reference, so it didn’t get shipped. The hiccup delayed me by about two weeks, but nonetheless, they made right by the mistake.

The Acrylic plates used on the front of the product were sourced from TAP Plastics of Mountain View, California. Painting supplies and adhesives and additional finishing tools were acquired from McGuckin’s Hardware store of Boulder, Colorado.

Machine elements were received from McMaster-Carr of Elmhurst, Illinois. They had quite possibility the fastest order placement to shipping time I’ve ever seen. I’d love to see the system that powers that operation. Additional elements were acquired from various Amazon merchants and local big-brand hardware stores. Gearmotor was purchased from Sparkfun Electronics of Boulder, Colorado.

Electronic components were primarily received from Mouser Electronics of Mansfield, Texas. Their selection and speed of shipping were superb. Additional components were purchased from electronics store J. B. Saunder’s of Boulder, Colorado when I needed something quickly and from various Amazon merchants.

In terms of cost of these parts, buying in bulk and in single orders saves on per item cost and on shipping. Buying just the components needed would have ended up being more expensive than buying them in bulk. In effect, multiple versions of the product could be produced cheaper than just producing one.

Prototyping

Industrial Design

Left-to-right: Prototype reverse and front. Shaded regions represent volumes that would be knocked out in the final design.
prototype


To develop a sense of how the product would come together, it was helpful to construct a cardboard based version of the final product based off the measurements I’d put together during the design phase. This enabled me to understand proportions, and the working space for the electronic and mechanical components. It also helped remind me that I was working towards a well-defined end goal.

Mechanical

As in the previous section, I also put together some cardboard based prototypes of the drive system. This consisted of a couple cardboard gears, a mocked up motor and a couple straws. Not being very savvy when it comes to all things mechanical, it was helpful to see the parts in action before committing to anything.

Once I had purchased the machine elements I wanted to see how the shafts and everything would mesh together so I decided to make a wooden version of the motor carriage. My thinking here was that if it was easy enough to make I could skip having that component 3D printed to save on cost. After a few trips to the lumber store, some careful drilling and wood glue, the motor carriage was put together and I was able to verify that the axle and motor assemblies would mesh together and be capable of reliably holding everything in place.

From this exercise I concluded that it wasn’t worth the extra effort to really spend a lot of time on the wooden version. I simply didn’t have the right tools or workspace to get the kind of precision that would be needed to make everything run smoothly so I proceeded to think about what the 3D printed version would look like.

Electronics

Working with the electronics was a bit of a steep learning curve to traverse, but as time went on, it became easier to translate circuit diagrams to the breadboard. Coming from a software background, I put together the circuits in as modular a way as possible to facilitate testing of sub circuits in isolation. This made it significantly easier than attempting to debug issues with the circuit as a whole.

Production

Industrial Design

Left-to-right: Reverse and front of the 3D printed components consisting of back plate, body, arms and motor bracket.
3d-print


3D printing of the product was done by laser sintering. This is a process where a thin layer of ESA Polyamide 2200 is laid down and then the cross section of the product is heated to bond the material together with a new layer added and the process repeated until the volume is rendered.

After a month of modeling the product in OpenSCAD, the resulting STL file was submitted to be printed. After ten days, the product was fabricated and delivered. As an observation, the end result had a look and feel similar to that of a sugar cube. Overall, the detail on the product came out crisp and only those openings whose diameter was less than 2mm ended up coming out slightly deformed on one side. The rest of the details came out well. The back plate logo and copyright text as well as the interior WEEE symbol, RIC symbol and copyright text came out crisp and legible despite having fine details.

From left-to-right: Primed body, first coat of paint and final coat of paint.
painting


From here, it was time to undertake the process of giving the exterior of the model an aluminum looking finish. This was achieved by applying an aerosol primer for plastics and several coats of a metallic paint that formed a firm film of enamel that added some extra strength to the body. In between coats, the body was sanded down with finer and finer grit to remove any imperfections or inconsistencies introduced during the spray paint process. I decided to keep the striations from the printing process since it gave the finished product a more believable brushed metal look. I didn’t paint the interior since I didn’t want any miniscule metallic flakes from the paint to potentially interact with the electronics.

From left-to-right: Finished product reverse and front.
assembly


The acrylic for the eye and chest plate was cut by hand and seated into the body with an epoxy for binding acrylic to plastics. To give the chest plate the same look as the original illustration, several layers of electrical tape were placed on the back of the chest plate and the openings were cut out with an X-Acto knife. Each of the mechanical and electronic components that were part of the body was then secured with additional adhesives. To make sure the mechanical components lined up properly I threaded an aluminum shaft through the ball bearings and then glued each bearing to the body or bracket. Once the adhesive had dried, it was easy to slowly pull the shaft back out.

Mechanics

Center: Arms, bracket, motor and gear train in relation to the arms.
mechanics


The final production work on the mechanics dealt with securing the pinion gear to the motor shaft, motor to the chassis, bevel gears and machine elements to the shafts and finally securing the arms. One of the major complications in putting the mechanical system together was the fact that many of parts came from different vendors and possessed a mixture of imperial and metric units. As a result, things were done in more of a roundabout way than I would have liked to realize the original design. C’est la vie.

Starting with the gears themselves, the bevel gear had racetrack shaped interior diameter of about 4mm. The closest aluminum dowel that would fit was 5/64” in diameter. Being a nonstandard imperial diameter, I went with a 3/16″ diameter rod since it was a more prevalent diameter among the hardware vendors. To compromise, the bevel gears were attached and centered to the 5/64” dowel with adhesive and left to set. Once set, they were then placed and centered inside the 3/16″ rod and fixed with adhesive.

The pinion gear and the motor’s shaft both had a 3mm radius, but the shaft was D-shaped since it was intended to mate with a RC car wheel. (Coincidentally, the gears were part of a larger differential gear set intended for a RC car.) Despite the mismatch, the pinion and motor shaft shared the same diameter, so it was easy to secure the pinion on the shaft with adhesive.

You’ll note that fewer shaft collars were used as a consequence of this complication which was primarily rooted in my choice of gears. I didn’t have many options when it came to gears, and I went with the best of my worst options since it was cheaper to purchase the gears as a set, than it was to go out and buy all the gears individually for far more than I was willing to pay. Nonetheless, everything came together within reason.

Electronics

Center: Protoboards fastened to back plate consisting of power management (top left), motor and LED control (right) and timing (bottom left).
electronics


Transcribing each portion of the prototype from the breadboard over to the protoboard was a challenge that lasted for a few months. I’d spent a fair amount of time and was becoming fatigued by the experience and had hit a low point in terms of morale and motivation. As a result, I made mistakes that I shouldn’t have been making and I recognized I needed to change what I was doing if I was going to finish the project. After taking a two week break and thinking I’d gotten things under control by double and triple checking my designs and taking my time to make sure I wasn’t putting parts in backward or offset or connecting parts together that shouldn’t be by accident, I ran into a major problem.

I could not identify a short in my original BJT based H-bridge design. After reviewing the protoboard layout, breadboard layout, the design, my reference material and datasheets, I was stumped. This went on for weeks and I realized that this was just something more involved to get right that I had led myself to believe and that I needed to move on. As a result, I compromised on the design and decided to use a quad half H-bridge integrated circuit in place of a BJT based H-bridge design.

I also concluded that I needed to change my approach to the power management for the project. I felt that drawing current from a single voltage supply for both the logic and drive wasn’t the right thing to do and that I need to split these concerns into their own dedicated voltage supplies. Not wanting to just throw another 9 \text{ V} battery into the mix, I decided I would go with the boost converter off of a 3 \text{ V} supply in order to supply 5 \text{ V} to the logic components while leaving the existing 9 \text{ V} supply to be regulated down to 6 \text{ V} for the motor and LEDs.

In retrospect it wasn’t the right decision since it meant adding complexity to the end result. It also meant desoldering a lot of work and spending additional time and money on new parts and a new design. But at this point, I had committed to the change and proceeded. After receiving the new parts I went through another round of testing on the new designs on the breadboard and concluded that the changes would work and proceeded to solder the changes to the protoboards.

Ironically, the boost converter and quad half H-bridge integrated circuit were the easiest things to map to the protoboard and any doubt that I could not get the final electronics to work were gone. Despite the big change and the frustration, I felt hat I had turned things around and was back on track.

Having finished the protoboards I fastened them to the back plate and made sure there was enough room in the body for everything to fit. I’d given myself some room between the machinery and the electronics, but not enough for the wires to lie in between. With some electrical tape I was able to bind the wires tightly and secure everything in its place and was finally ready to test drive the end result.

Evaluation Phase

Testing

Having put so much effort into the body of the product, I didn’t really have the heart to subject the 3D printed bodies through any serious stress tests. In handling the material and developing a feel for it, I didn’t develop an impression that it was overly fragile; it withstood several rounds of aggressive sanding, boring and drilling without fracturing and warping. For me, this was good enough for something that would ultimately find a home on my bookshelf.

To identify any problems with the machinery of the product, I oriented the arms of the robot in to the various positions I talked about in the requirements section to see how it would behave. All the elevated orientations resulted in the arms swinging down then being driven by the machinery. I attribute this mainly to how the arms were fastened to the shaft by being pinched between two shaft collars and padded from the shaft with some electrical tape. In one sense this was good since it was putting too much strain on the motor, but on the other hand disappointing. Despite this complication, I decided that I was ok with just having the arms hanging down and shuffling back and forth.

The second big part of the character of the product was the illumination of the eye and chest. The eye ended up having plenty of light while the chest merely flickered on and off. Changing the power supply design and dimensions of the body resulted in a reduced voltage and increased displacement resulting in the diminished output. Since things were already soldered, I chose to leave things as is.

Future Work

The end result here isn’t without flaws. Working through the project I recognized along the way that there were things I hadn’t done quite right or that just didn’t sit with me well. The following is a list of things I would try to keep in mind next time I take on a project like this.

As far as the 3D printing process went, I would go back and redo how I incorporated the latching mechanism for the motor chassis and back plate. The biggest problem here was that post fabrication modifications had to be made since I incorrectly understood the tapping process. Nothing ruins precision faster than making changes by hand.

I had overlooked the theory behind illumination and had instead focused more on intuition. In the future I would spend more time reading up literature on the right amount of light to use based on what I wanted to illuminate and the different techniques that exist for providing different types of coverage. In retrospect, I think this would have given the end result a more polished look.

The mechanical work was complicated by the impedance between the imperial and metric standards of the parts involved. Part of this was poor planning on my part; part was difficultly finding the right parts at a hobbyist price point. Nonetheless, I’d like to continue to develop my understanding of mechanical systems and how they can be incorporated into electronically driven solutions.

I would have also incorporated some wiring management directly into the part so that it was less of a hassle to fit the back plate to the body with everything. I’d also switch to an existing cable management system instead of relying on screw terminals so that it was easier to snap things together and give the board a lower profile to save on space.

I’d like to explore printed circuit boards the next time I approach a project like this. My knowledge of circuit design going into this was limited, and it would have meant a lot of wasted time, material and money had I gone ahead and ordered PCBS this round. Given that I now have a working model to base future work, I would like to explore this route in the future.

As far as the on-off functionality goes, next time I think I will use a series of relays to switch access to the voltage supplies whenever a momentary push button is engaged. I think this would lead to a cleaner separation of the two voltage supplies.

The timing circuit was complicated by the initial ramp up time giving rise to a slow initial rotation until the threshold was reached to go in to astable mode. In the future I’d like to come up with a way to eliminate that initial ramp up from showing up in the output of the arms. Related to this, I’d like to be able to control the length of the timing pulses to swing between clockwise and counterclockwise rotations. In all likelihood, I’d use a microcontroller since it would give me the greatest range of flexibility.

Conclusion

With the finished product sitting on my bookshelf and reflecting on this project, the seasons it encompassed and the ups and downs I worked through, I have developed a greater appreciation for mechatronics, the physical product design cycle and the work people put into everyday products.

Taking the time to make something tangible for a change presented me with a number of challenges that I hadn’t had to face before and that’s what I enjoy most about these kinds of projects. It’s really about developing a new set of tools, techniques and thinking that I can apply to problems that arise in my personal and professional work.

This project allowed me to explore a number of interesting concepts within the framework of a seemingly simple toy. Let’s iterate over the main bullet points:

  • Analog circuit design- complete analysis and use of passive components coupled with semiconductors with first real exposure to transistors, operational amplifiers and 555 timers.
  • Protoboard design, soldering, debugging and desoldering techniques.
  • Exposure to driving DC Motors using various techniques.
  • Better understanding of hardware development and the product design process.
  • Learned about industrial design guidelines and techniques for making cost effective products using 3D printed materials.
  • Use of the finite element method to perform stress analysis of a complex geometric object. (Finally had an excuse to learn tensors.)
  • Learned how to use an assortment of CAD, CAM and CAE software solutions.

Overall, the project produced a number of positive outcomes. As a stepping stone, this project has left me wanting to explore mechatronics more deeply and I’ve got a number of ideas brewing in mind that could lead to more advanced “toys” in the future. I feel confident that I can take the lessons learned from this experience and avoid pitfalls that I might encounter in more advanced projects of similar focus going forward. For now, those ideas will have to wait as I return to my world of code and numbers.

About the Author

Untitled-2 Garrett Lewellen is a software developer working at a private start-up in the Denver Metro Area designing and developing SaaS-based systems. With eight years’ experience and formal education in computer science with emphasis in applied mathematics, his primary interests lie in the application of statistical models to problems that arise in general computing. When he’s not working on projects, he’s out exploring the Rocky Mountains and enjoying the great outdoors.

Copyright

“3D Printed Toy Robot” available under CC BY-NC-ND license. Copyright 2013 Garrett Lewellen. All rights reserved. Third-part trademarks property of their respective owners.

Bibliography

Part and Mold Design. [pdf] Pittsburgh, PA: Bayer Material Science, 2000. Web.

“A.5.8 Triangle Oscillator.” Op Amps For Everyone Design Guide (Rev. B). [pdf] Ed. Ron Mancini. N.p.: n.p., 2002. N. pag. Texas Instruments, 22 Aug. 2002. Web.

Boost Converter.” Wikipedia. Wikimedia Foundation, 09 July 2013. Web. 15 Sept. 2013.

What Is PWM? Pulse Width Modulation Tutorial in HD.” Electronics Tutorial Videos. N.p., 28 Nov. 2011. Web. 11 Sept. 2013.

Amado-Becker, Antonio, Jorge Ramos-Grez, María José Yañez, Yolanda Vargas, and Luis Gaete. “Elastic Tensor Stiffness Coefficients for SLS Nylon 12 under Different Degrees of Densification as Measured by Ultrasonic Technique.” [pdf] Rapid Prototyping Journal 14.5 (2008): 260-70. Web.

Chaniotakis. Cory. “Operational Amplifier Circuits Comparators and Positive Feedback”. [pdf] 6.071J/22.071, Introduction to Electronics, Signals, and Measurement. Spring 2006 Lecture Notes.

Cook, David. “Driving Miss Motor.” Intermediate Robot Building. 2nd ed. Apress, 2010. N. pag. Print.

Cook, David. “H-Bridge Motor Driver Using Bipolar Transistors.” Bipolar Transistor HBridge Motor Driver. N.p., n.d. Web. 11 Sept. 2013.

EOS GmbH – Electro Optical Systems, “PA 2200”: [pdf] Material sheet, 2008.

Demircioglu, Ismail H. “Dynamic Model of a Permanent Magnet DC Motor”. [pdf] 11 Aug. 2007.

Jung, Walt, ed. Op Amp Applications Handbook. N.p.: Analog Devices, 2002. Web.

Kim, Nam H., and Bhavani V. Sankar. Introduction to Finite Element Analysis and Design. 1st ed. New York: John Wiley & Sons, 2009. Print.

Lancaster, Don. RTL Cookbook. [pdf] 3rd ed. Thatcher, Arizona: Synergetics, 2013. Web. 11 Sept. 2013.

Maksimović, Dragan. “Feedback in Electronic Circuits: An Introduction”. [pdf] ECEN 4228, Analog IC Design. Lecture Notes 1997.

Mantzel, Jamie. 3D Print Big Robot Project No. 1. N.d. Youtube.com. 11 Mar. 2012. Web.

Maxim, “CMOS Micropower Step-Up Switching Regulator”, [pdf] MAX630 datasheet, Sept. 2008. .

Movellan, Javier R. “DC Motors.” [pdf] 27 Mar. 2010.

National Semiconductor, “LM555 Timer,” [pdf] LM555 datasheet, July 2006.

Najmabadi, Farrokh. “Bipolar-Junction (BJT) transistors.” [pdf] ECE60L, Components & Circuits Laboratory. Spring 2004 Lecture Notes. .

Nikishkov, G.P. “Introduction to the Finite Element Method”. [pdf] 2004 Lecture Notes.

Platt, Charles. Make: Electronics (Learning by Discovery). 1st ed. Sebastopol, CA: O’Reilly Media, Inc., 2009. Print.

Roberts, Dustyn. Making Things Move DIY Mechanisms for Inventors, Hobbyists, and Artists. 1st ed. N.p.: McGraw-Hill, 2010. Print.

Sayas, Francisco-Javier. “A gentle introduction to the Finite Element Method”. [pdf] 2008 Lecture Notes.

Shenzhen Kinmore Motor Co., Ltd, “Outline”, [pdf] KM20100507 datasheet, Nd.

Texas Instruments, “LM158, LM158A, LM258, LM258A, LM358, LM358A, LM2904, LM2904V Dual Operational Amplifiers”, [pdf] LM358 datasheet, June 1976 [Revised July 2010].

Texas Instruments, “SN754410 Quadruple Half-H Driver”, [pdf] SN754410 datasheet, Nov. 1986 [Revised 1995].

Toledo, Manuel. “Basic Op Amp Circuits”. [pdf] INEL 5205, Instrumentation. Lecture Notes. 13 Aug, 2008.

Wens, Mike, and Michiel Steyaert. “Reflections on Steady-State Calculation Methods.” Design and Implementation of Fully-integrated Inductive DC-DC Converters. N.p.: Springer, 2011. N. pag. Print. Analog Circuits and Signal Processing.

Viderefit: A Fitness Tracking App for Android Tablets

with one comment

Introduction

Earlier this year I talked a bit about how I wanted to do some Android development to broaden my skill set. A little after that post I finally joined the 21st century and got an Android smartphone. Over the course of the summer I recorded all of my hikes and bike rides using Google’s My Tracks app. With my season coming to a close, I began to think about what I could do with all this data that I’d collected and what kind of insights I could discover. As a result, I came up with Viderefit, a simple Android tablet app, that allows me to review my changes in my performance over time. In this post I’m going to go over the product design cycle that went into making this first phase of the app- from brain storming, requirements building, user interface design, development, and post-production. I’ll be finishing up with some thoughts on the next set of features I’ll be contemplating to make the app commercially viable on Google Play.

Goals

For the first phase of the project, I set out with a few simple goals that I wanted to focus on:

  • Since I’d been focusing research projects lately, I wanted to return to my roots and focus a bit on user experience and interface design. As a result, I decided It was important to me that I create an intuitive to use and visually appealing user interface that utilized a number of appropriate and meaningful information visualization techniques.
  • I’ve done a lot of C# and Haskell development lately, and I wanted to do something relatively new, so I decided that I would develop on Android and dust off my Java skills from my college days.
  • I wanted a “quick win”, something that I knew that I could complete over the course of a couple weeks. As a result, I decided that I would spend two weeks planning the project starting in mid-September, followed by another two weeks of development wrapping up mid-October, and the remaining two weeks of October to put together this post for a November publication.

Brain Storming

In thinking about what exactly it was I was going to build I began to ask myself, what questions should I be asking myself. So, I opened up Word and began typing out a bullet point list of questions to understand where I was going with this project. First thing I began to think about was what exactly is physical fitness? What exactly is being measured over time to show improvement? What exactly is improvement? I had some ideas from my experience, but nothing formal, so like anyone else, I jumped Wikipedia and came across the following quotation on the topic’s page:

Physical fitness has been defined as a set of attributes or characteristics that people have or achieve that relates to the ability to perform physical activity. – Physical Activity and Health: A Report of the Surgeon General

Not being completely satisfied with this, I looked around a bit more and found several pages outlining five areas that constitute physical fitness: aerobic or cardiovascular endurance, body composition, muscular strength, muscular endurance and finally, flexibility. Having felt like some progress was made, I moved on to the next question pertaining to measurements. Researching each of the five areas yielded some insights in the types of tests and measurements being used to assess these abilities such as VO2 max, BMI, ROM, S&R and a whole slew of alphabet soup measurements that I unfortunately did not have access to nor were they obtainable from the available set of data.

Thinking a bit more about the data that was available to me, it was clear the only area of physical fitness I could focus on was aerobic endurance. Despite the fact I lacked sufficient data to derive some of the formal measures of physical fitness, I could derive some common sense measures to relate my performance over time. Am I going longer, going further, going faster as I got deeper into my season? Is my improvement uniform over time or did I hit any plateaus? And so on. To explore these ideas, I exported all of the My Tracks data from my smartphone to a SD Card and combined the results using a throwaway C# application and loaded the combined CSV file into Excel.

Left to right: Plot of total time vs total distance, distribution of time spent at a given elapsed time and monthly total time.

Based on my explorations in Excel, I decided that I had the data I needed to answer the types of common sense question I was thinking about and decided what I was after was three different views of my data: a summary dashboard, performance reporting and a raw view of the data.

Requirements

In deciding on my requirements, I thought a bit about what I had read in Ben Fry‘s Visualizing Data: Exploring and Explaining Data, that exploring most data sets consists of acquiring, parsing, filtering, mining, representing, refining and interacting with the data set. Keeping that in mind, I decided that I would likely have a series of tabs providing different views of the underlying data and sets of tools on each tab to assist in that data’s interpretation.

The summary dashboard is about capturing the “big picture” of the underlying data. In thinking about what was important to me, I wanted to capture how far I’d gone, how long I’d spent and how many times I went out. Each of these three sections would be broken down into a total, a percentage of some reference figures (e.g., the distance between cities), a chart showing the total broken out by activity type and month, box plot showing the underling distribution, a stacked bar chart showing the underlying activity distribution and finally the longest, furthest, or most common track was to be presented.

Performance reporting is about enabling the end user to explore the underlying data. In essence, enabling the end user to chart different features plotted against one another and summarized according to some scheme. The user would then be able to filter by activity type and break the data set out into pre-season, mid-season and post-season components to better see trends taking place over time.

Finally, the raw view of the data provides a listing of all the tracks that were captured. Selecting a track displays a speed and altitude plot along with box plots for speed and altitude for the track in addition to box plots for the season so that the user can compare how a particular track compares to seasonal statistics.

Design

With an idea of the type of requirements that would be needed, it is time to flush out what the user interface will look like and how the user will interact with it. There are a lot of great products out there for mocking up user interfaces, I’ve used Balsamiq and really enjoyed it, but decided for this project, I would keep things simple and just mock things up in Photoshop since it’s easy to work with and low fidelity designs are all that’s needed at this point.

The summary dashboard incorporates the requirements into a vertical three panel design capturing distance, time and frequency of the underlying data. The dashboard is meant to be looked at and not interacted with, as a result the only thing the end user can do at this point is click on other tabs.

Season dashboard mockup.

Bulk of the features in the application will appear on the performance reporting tab. The user will be able to select x-Axis, y-Axis features and y-Axis feature aggregation strategy in order to plot out the results in the right-hand chart area. Beneath the selection criteria are checkboxes for splitting the data out in to full season, pre-season, mid-season and post-season components. Finally, the user can filter out different activities by checking each activity for exclusion or inclusion.

Performance reporting mockup.

The view of the raw data is to provide a view outlining all of the user’s tracks. Each track listing includes the name of the track, date, length, duration and a altitude sparkline. Clicking on a track reveals a speed and altitude plot along with the box plots described in the previous section.

Raw data view mockup.

Development

Based on the planning done earlier in the project, development was a matter spending some time in IntelliJ, translating the design into the appropriate Android conventions and implementing the necessary logic to calculate various statistics and data calculations.

Much of what was needed to implement the application was available in the JDK and Android SDK, however there were a few areas I felt I could leverage existing open source libraries without having to roll my own solution (especially given the timeline I had decided upon):

  • For charting I decided to use achartengine (1.0.0) since it looked to be the most stable and used charting library for Android.
  • To parse the CSV file containing all of the track information, I went with opencsv (2.3) since it seems to most widely used. Although it does look like an Apache Commons CSV package is in the works but not yet final.
  • Since the time and date handing in Java is embarrassingly lacking in JDK 1.6, I ended up using joda-time (2.1) for presenting end user friendly date and time representations.

The three libraries are all licensed under the Apache License 2.0

In terms of code organization and events that take place, the application is structured around Android’s fragment approach to deal with having to provide different views based on the device being used. Since the focus of the application was to develop a tablet application, no additional layouts were developed to support smaller screen sizes. The main activity consists of loading data from an SD card and creating handlers for tab events for each of the three tabs. Each individual tab consists of a replicated paradigm of master-detail fragments and additional settings that are passed between fragments as bundles whenever an end user event takes place.

Application overview. Relationship of fragments to views, flow of data based on events and underlying packages used.

The referenced packages: common, controls, reporting and serialization contain classes for binding views to data, data aggregation (essentially a watered-down version of .NET’s LINQ and Haskell’s higher order functions), and classes for loading track data into memory.

Post-production

With development complete, I set out to do some polishing and make the application visually consistent. To start things off, I wanted to settle on a color palette for the application. This was done by sampling the HSB space on 60 degrees increments of hue offset by 0, 15, and 30 degrees of hue, with fixed 100% saturation and 80% brightness giving a vibrant 24 color palette to work with.

Color palette and derived color scheme for various parts of the user interface.

Once the color scheme was established, it was a matter of going through the application and making sure each user interface element was using the correct color resource. Once the colors were applied, I focused on applying a consistent spacing between all of the UI elements- specifically 16 dp and 8 dp depending on the context and bordering between components. From there, each chart was examined to make sure that the axes units and labels were presented correctly. One gripe about achartengine is that I was unable to find a way to set the axis title’s padding, so there is some overlap between the axis value labels and the axis title.

With the application spruced up, it was on to icon design and selection. For the application icon I decided to to do a simple vector-based tri-folded map with an overlaid panel and chart.

Lef to right on white and black backgrounds: Initial icon, overlaid icon and final icon.

For the icons to be used in the application, I used those found in Google’s My Tracks app since those icons are available under a Creative Commons 3.0 BY-SA license and represent the vast majority of data that would be imported. Worth noting that most of those icons are based on the National Park Service’s Map Symbols Collection. Future versions of Viderefit will likely switch over to the NPS set since they represent a more considerable collection of activities and the collection is under a public domain license.

Top to bottom: NPS Map Collection icons vs. Google’s My Tracks icons.

Last thing to settle on was the name of the application. During development the name was simply “My Track Visualizer”, but I wanted the app to be more than that, so I decided on “SeeFit” or “cFit”, whichever happened to be available. After a Google search, neither were available so, I decided to use the Latin word for “to see”, Videre, and luckily “Viderefit” didn’t show up in any Google search results, so presumably nobody else has taken it.

End result

After finishing post-production, the application was looking much more consistent and polished. Below are screenshots of each tab taken from my 10.1″ Acer Iconia Tab A500 development device.

Summary dashboard.

Performance reporting. x-Axis options: Distance Traveled (m), Time Elapsed (s). y-Axis options: Altitude (m), Bearing (deg), Distance Traveled (m), Time Elapsed (s). y-Axis aggregation options: Count, Maximum, Mean, Median, Minimum, Total.

Raw data view.

Future Work

In thinking about what it will take to get this product market worthy, there are a few things that stand out in my mind:

  • Data importing – for this project the data resided on an external SD card and was loaded into memory from a parsed CSV file. Ideally, the end user should be able to import data from multiple applications and in varying formats such that the data is stored more efficiently using the built-in SQLite capabilities of the platform.
  • Data exporting – one open question is how this application fits into the broader fitness application ecosystem and what exportable data is of use to other applications.
  • Territory – the project omits any presentation of actual GPS data recorded during each session. For those individuals who are more interested in where they’ve been over their measurements, it seems a territory view would be a selling point. In addition, some form of integration done with the Google Maps API would also help visualize territory and speeds on the map over time.
  • Additional screen support – right now the application was designed specifically for tablets, but other users may wish to use this application on their smartphone.
  • Goal support – having reviewed other applications on the market, the idea of goal tracking is a recurring theme. To make the product more marketable, it would be useful to add in this kind of functionality.

Conclusion

Reflecting back on the goals I set out at the beginning of the project, I feel I made an intuitive and easy to use product consisting of appropriate information visualization techniques; worked on a new platform other than my typical C# and Haskell environments; finally, managed to complete the project according to the timeline I established by finishing all work a full two weeks sooner than originally scheduled. Working on a new platform and hardware was a fun experience. With the work that I’ve done, I feel that I can proceed onto the next phase of the project and determine how to get the application ready for the marketplace and hopefully bring in some revenue in the process.

Written by lewellen

2012-11-01 at 8:00 am

Posted in Projects

Tagged with , , ,

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

leave a comment »

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, A and B, with momentums, p_{A} and p_{B}, must have the same amount of momentum before and after the collision. Assuming a totally elastic collision, we end up with p_{A}^{(b)} + p_{B}^{(b)} = p_{A}^{(a)} + p_{B}^{(a)}. Momentum is defined as p = \frac{1}{2} m v^{2}, where m is the mass of an object and v is its velocity. Since no mass is being lost in the collision, the velocities must change as a result. Solving for the v^{(a)} 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());
		}
	}
}

Written by lewellen

2011-05-01 at 8:00 am

Posted in Projects

Tagged with ,

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

with one comment

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.

Written by lewellen

2011-04-01 at 8:00 am

Posted in Projects

Tagged with , , ,

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

with 2 comments

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.

Written by lewellen

2011-01-01 at 8:00 am

Posted in Projects

Tagged with ,

aBox: Electronics and Databases and Everything Else Inbetween

with one comment

Prelude

Back in January, a local Boulder company had a special promotion to give away $100,000 in electronics goodies. Naturally, a lot of people caught wind of this and it was the incentive I needed to take a look at electronics and physical computing. While I didn’t receive any free goodies, I did place an order for a number of parts and components anyways and drove up to their office and picked up my order one day during lunch. The key component I ordered from them was an Arduino Starter Kit (DEV-09284). The Arduino (specifically the Duemilanove) is a simple piece of hardware built around the ATMega328 microcontroller that’s easy to program over USB using a free IDE from the Arduino website. After playing around with the components and learning a bit about electronics, I began to think more critically about what I’d like to make.

In addition to the starter kit, I also got a 20×4 LCD (LCD-00256) and a piece of hardware that attaches on top of the Arduino allowing for network connectivity called an Ethernet Shield (DEV-09026). From these components I began to picture a little box with a simple text display, a series of buttons, maybe a LED to show status and an Ethernet connection that I began to call a(rdunio)Box. In a nutshell: have a piece of hardware that is able to exchange messages with a server and display the output of these messages to the LCD. Interacting with the buttons would change which messages were sent to the server. Part of the message exchange would involve getting a configuration of which messages the device can send to the server. Given the device, it made sense that it would be fun to have a web interface to setup configurations and different views that could be displayed on the device and data providers that operate behind the views. Which, of course, hints to the fact that there would need to be a database behind the web interface that the server component of this design would talk to as well. Below is a diagram of the general architecture of the project.

In terms of technology decisions, the client side is comprised of C and libraries provided by the Arduino platform- pretty standard embedded environment. The aBox and HTTP Server is written in C# using the .NET framework running as a multithreaded process. The .NET stack is fantastic and makes it easy to get things done quickly. The Web Interface is straightforward XHTML, CSS, XSL and JavaScript. No libraries were used on the client-side as I wanted to learn JavaScript a little better. Finally, the server points to a MySQL Community Server edition database. The aBox Client-Server protocol is a simple TCP (most easily accessible protocol in the Arduino Ethernet library) message exchange that is somewhat RESTful. The exchange between the Web Interface and HTTP Server is a clean cut AJAX exchange following RESTful principles. Server-Database communication is the de facto TCP exchange.

In terms of deployment, the aBox and HTTP Server resides on a Windows XP laptop. The database on an Ubuntu 8.04 virtual machine running inside VirtualBox on the XP machine. I went with Ubuntu rather than XP for the database as MySQL is easier to manage under that environment. The aBox Client lives on the Arduino hardware. All of these are on the same Ethernet network.

Client

The Arduino environment comes with a suite of really great tools that work effortlessly out of the box. Fritzing is one of those tools; it is a simple diagramming tool that comes with a preloaded set of widgets that can be arranged as though you had the breadboard in front of you. Given the functionality that I wanted I knew that I needed a handful of discrete components: at least one button to switch between views, a potentiometer to control the contrast of the LCD, a LED as a status indicator and for future purposes, a thermistor. In addition to these parts, I needed two 330Ω resistors to limit the current going into the button and LED and a 10kΩ resistor so that I can get accurate results out of the thermistor. The diagram at right is the initial setup I came up with in prototyping. The Ethernet Shield uses up pins 10-13 of the Arduino board. The LCD requires 4 pins for pushing data and an additional two for control. These are pins 2-7. Finally, a pin for receiving a digital input from a button and one for controlling a single LED used by pins 8-9. While the breadboard approach makes for easy assembly and rearranging of components, it’s a pain to continuously take it apart and put it back together. So, I decided to put together a soldered board of the components that were on the bread board. The Bill of Materials is the following:

Item SFE Part # Unit Price Units Ext. Amt.
Basic LED – Green COM-08532 $0.35 1 $0.35
Break Away Female Headers PRT-00115 $1.50 8/40 $0.30
Momentary Push Button Switch – 12mm Square COM-09190 $0.50 1 $0.50
ProtoBoard – Square 1″ Single Sided PRT-08808 $1.50 1/2 $0.75
Resistor 10k Ohm 1/6th Watt PTH COM-08374 $0.25 1 $0.25
Resistor 330 Ohm 1/6th Watt PTH COM-08377 $0.25 2 $0.50
Thermistor 10K SEN-00250 $1.95 1 $1.95
Trimpot 100K COM-08647 $0.95 1 $0.95
$5.20

Given these materials, I set out with the above board layout. Layout of the board was done using a greedy algorithm. I started by first placing the button and associated resistor using as little space as possible- sat back and compared it to my breadboard to make sure my logic was sound. Once I was convinced, I repeated this process by placing the potentiometer, LED and the thermistor down on the board until I ran out of space. Designing the board and actually soldering the board turned into a rather interesting set of lessons. Applying the right amount of heat, making sure that parts were added in the right order and making sure that the polarity and orientation of the components was correct going onto the board required constant, conscious effort. The board was completed after a couple nights with a handful of little modifications. Notably, reducing the dual seeding of components and minimizing wiring distance between components beneath the board.

In terms of writing the code that would be placed on the Ardunio, I spent some time writing a handful of modules: dealing with dynamic array and C styled strings, interfacing with the button, LCD, LED, Ethernet Shield, logging, configuration, message exchange, handling and parsing, and of course the application itself. A lot of time was spent debugging memory allocation and deallocation issues, working on timing and response issues and making sure that final product was able to fit into the allotted 30k of memory.

Database

Before I jump into the Server and Web Interface, I want to run down the basic data model that is used. At a high level, there are devices, views and providers. A device is a collection of views, a view is an instance of a provider with supporting arguments and a provider is an interface provided by the Server that can be setup with parameters. The entity relationship model for all of these items is summarized below:

To give some concrete examples of the above consider a provider that’s an interface into the Netflix Service that retrieves specific information based on the provider parameter- say the contents of a queue or the status of what movies are in the mail. A view is then created on top of this provider to specify a concrete realization of the provider- we might have one view called “Netflix Queue” and one called “Netflix In Mail” that can then be added to a device. The device is what is sent down to a specific Client. Right now, the first device found is what is sent down to the hardware, but in the future it would be ideal for a Client to have a configurable identifier (say a DIP Switch – 8 Position (COM-08034)) that would specify which device to get from the Server. Alternatively, an additional button that would cycle between devices similarly to how the view cycle button works.

Server

Getting the server put together took the least amount of time in comparison to the Client and Web Interface as there weren’t any unknowns to research. Both the aBox and HTTP server have listener threads in place that then delegate requests to queues to make sure the listeners receive requests in a timely manner. Each queue then looks at the request and attempts to find the appropriate handler to produce a response. If no handler is found, then (in the event of the HTTP server) the contents of the requested file are returned. If all else fails, the server returns an error message in the appropriate protocol. The aBox portion sets up a TCP socket to pick up requests coming to port 8888, the HTTP portion utilizes the .NET class HttpListener under System.Net that picks up standard TCP port 80 traffic. I decided against implementing the the HTTP part as a TCP socket because the value from doing so didn’t justify the time to implement the protocol. Alternatives to HttpListener include ISAPI on IIS, mod_aspnet on Apache http and WCF AJAX Services on IIS. Each one has it’s pros and cons; ultimately, I choose HTTPListener as it reduces the complexity of the system at the end of the day and exhibited the fastest conception to completion.

The aBox exchange is a simple name-value list that first describes the verb and noun, followed by any supporting data. As an example, when the Client starts up, it will send Get:Configuration, and the server will query the database views table and send something like Post:Configuration|Time:0|Weather:1|News:0 which the Client will put in memory and default to sending Get:Weather until the End User pushes a button and the view selection increments to News and results in Get:News being sent.

The HTTP exchange is very typical, standard HTTP Request that comes in and an appropriate handler is picked based on the URL and Content represented in the request; the handler accepts the request and produces a response. The response will be an asset that exists on the Server, e.g., a CSS file; or the Server will return an XML document and function as a RESTful Web Service. This is preferential to the SOAP Web Service approach as it greatly reduces the design-by-committee XML boilerplate that is commonly associated with SOAP (not to mention that it is an order magnitude easier to work with in JavaScript). The Web Interface is then responsible for performing something with that data. The Server strictly yields data back to the client and does not generate any XHTML for the client to consume. The usual REST verbs are allowed where HTTP Get, Put, Post and Delete map to corresponding handler functions Get, Add, Update and Remove.

In addition to the main threads for dealing with requests, there is an additional thread that periodically runs data providers. As an example, a view that uses a RSS provider for a weather site will run at a specified period, requesting data from the specified web site and store the resulting data in the database that will be acquired by the aBox or HTTP threads to be shipped down to the client. The reason these are decoupled is that we do not want to go and query potentially expensive or metered resources every time a request comes in. This way, if the Server is ever used by multiple devices, a corresponding third party web service isn’t issued multiple requests a second, instead it will issue a handful of requests a minute or hour instead.

Web Interface

Dealing with the Web Interface took almost as long as the Client to implement, but the majority of the time spent was learning JavaScript and XSL to make sure that the Client ended up being the fat-client that I had in mind. The basic approach was to use HttpXMLRequest to issue HTTP Requests to the Server and then apply XSL files against the resulting XML response using the XSLTProcessor to produce XHTML fragments. I like this approach as it keeps the logic squarely in the JavaScript, the look and feel of data in the XSL and CSS and the data as XML. I found that once I had gotten a grasp on the nuances of JavaScript that I was able to implement the main page and make minor modifications with each additional page resulting in a large time investment up-front, but a low time commitment to bring on additional pages.

When I produce a website, I typically jump into Photoshop and start producing some mock pages of what I want the site to look like and start formulating how it will all work in terms of End User actions as well as polishing the front-end with user experience elements. I decided to go with a simple tabbed header menu and tabbed menu that produces a central details and appendages regions. Details are things like that entity name and description, appendages are things like the views that are associated with a specific device. The following is a sample of the devices tab:

I found it easiest to organize my assets by elements of the page (tab, menu, details, appendages) rather than by the main tab (devices, views, providers) as it allowed for an easier generalization of these regions as it applied to each of the tabs rather than trying to repeat most of the same code along each of the tabs. This process applied to the CSS, JS and XLS files. There was a single XHTML index page that then routes all of the options back through the document; this probably isn’t the preferred way to do things from an exchange standpoint, however, this is a single front end that won’t likely ever need to have its URLs sent around to go find a specific item. learning JavaScript was an interesting experience as it reminded me a lot of writing the client code for the Arduino. Very procedural, quasi ability to fake traditional OO design, but overall, much more of an exercise in keeping everything ordered and organized.

Wrap-up

This has been a rather involved project over the course of the past two months working 2-3 hours during the week and usually a Sunday afternoon to produce the hardware, implement the code for the Client, Server and Web Interface and debug it all, as well as produce this write-up. It’s been exciting to get into hardware and spend some time getting a feel for the minutiae of electronics and microcontrollers. Spending time getting a better feel for some of the AJAX approach (especially for a guy coming from a ASP.NET/PHP background) has been very eye opening and enjoyable. I’m looking forward to spending some time in the future to revisit the hardware and think about how I would add additional functionality from a data acquisition stand point (sensor data) and end user experience stand point (more buttons, LEDS, using ICs and so on). Finally, once all the hardware is squared away, to actually sit down and produce an enclosure for it all so that I can keep the device running all the time. Taking my usual approach with designing Web Sites to designing an enclosure, I spent some time in Photoshop and produced the very basic design of where this could head.

Written by lewellen

2010-03-01 at 8:00 am