|
|
|
|
Circuit Setup
1. Introduction
1.1
Sound-Bite
Our final project recreates Rush Hour® as a video
game that is played using a touchpad implemented using 2D electric-field
(E-field) sensors.
1.2
Motivation
Rush Hour appealed to us as one of the better puzzles
out there. Its level of difficulty can range from simple games to hard
ones, thus making it suitable for players of most ages. As such, we
decided to use it as a basis for our final project.
For this final project, we also decided to design a
touchpad. Essentially, it is a 6x6 grid of sensor electrodes that uses
E-field sensors which will provide the necessary response on we touch one of
the grids. We are going to use this touchpad to play our game. The
MCU will read the inputs from the touchpad sensors and move the objects and
solve the puzzle.
1.3
Summary
The player plays by moving his/her fingers on a 6 × 6
grid (Rush Hour® original design) and by “pressing” a Select button (E-field
sensor) to select a car. The E-field sensors will detect and transmit the
sensor signals to the microcontroller unit (MCU). The MCU interprets the
signals and reflects the player’s actions on a black-and-white television
screen. The (MCU) is also programmed to prevent invalid moves and to allow the
player to progress through new levels.
The Freescale Semiconductor MC33794D chip serves as
the E-field sensor. The Atmel ATmega32 microcontroller (MCU) is used in this
final project.
2. Rush Hour Game
The Goal: Drive the red car
out of the car park.
Sounds easy? Not really…
The Rush Hour® Game is a traffic game puzzle invented
by Nob Yoshigahara in the late 1970s. The goal is to drive the red car through
the exit (yellow arrow in diagram). In the game, cars and trucks are placed in
the 6 × 6 grid with the red car. Vertical vehicles can only move up/down, and
horizontal vehicles can only move left/right. By moving the vehicles in the
correct combination, the red car can be driven out. This puzzle has varying
levels of difficulty, and expert levels can become very complicated that one
requires over 40 moves to solve.
Image from http://www.igoweb.org/~wms/comp/
3. High Level Design
3.1 Hardware
Block Diagram Overview
The following block diagram
describes our basic hardware layout.
3.2
The following state machine
diagram provides an overview of our software
Figure: State Diagram for the
Rush Hour Game
The program flow is captured in a form of a state diagram like the one shown
above. It consists of 10 states: Initialization, poll, compute,
draw, next_stage, waiting, clearWords, loadGame,
ending, waiting2. An brief explanation of the states and
what they do are further explained below. For a complete description of the
algorithm used, please refer to a later section of the report for the details.
Initialization
In this state, the program
initializes the necessary hardware and software operators on different aspects
of the program. The different aspects are: video pulse synchronization, video
display, and signal reception from the touchpad. In video pulse
synchronization, Timer 1 is set up to generate sync pulses for the video
output. For video, the grid lines are drawn. The exit location is also
shown by printing the name “EXIT” on the screen corresponding to that
location. The difficulty of the current game is then displayed on the
screen right beside the word “LEVEL” on the top left corner of the
screen. The difficulty levels are represented from anything in the range
of 1 to 8, 1 being the simplest game and 8 being the most difficult. In
the initialization stage, the value that is being displayed is ‘1’.
poll – Poll inputs from
touchpad electrodes
At this state, the program
extracts the inputs from the 12 electrodes, from which the program will
determine the x-location and y-location of the cursor, and also find out if the
user intends to select a car. Once the polling is complete, the program
re-initializes the polling variables so that polling can take place again when
the state machine enters this state again. If the user indicates that he wants
to select a car, the program finds out if it is a valid selection, and which
car is selected. If the user were to release the select button, an car
that were selected previously would be de-selected. More on this later in
the report.
compute – Interpret User Input
The program enters this state,
acting on user input if a car were to be selected by the user. With a car
selected previously, the user indicates the new position that the selected car
should be. The program will then determine if the new position is
valid. If it is, the move is accepted. Otherwise, the move is
denied, and the car is kept at its current position. Note that the computation
is slightly different for horizontally placed cars than it is for vertically
placed cars.
draw – Update the locations of
the car in the video display.
If any changes were made to
the car positions, the changes would be reflected on the video display.
The updated location of the cursor is also reflected here. At this state,
the program also checks if the user has solved the puzzle. If the puzzle
has been solved, the program moves on to the next level.
next_stage – Moving on to the next level
In this state there are 2
phases. The program will first remove the cars from the previous stage,
and later it will show the message “CONGRATS LOADING NEXT STAGE”.
waiting – system pause
After the program displays the
message, it waits for an arbitrary amount of time before loading up a new
game. In this case the waiting time is 2.5 seconds.
clearWords – removing the message
After the system is done
waiting, it removes the congratulatory message from the video display in
preparation of loading a new game.
loadGame – loading a new game to
the video display
Once the congratulatory
message is removed, the program loads a new game to the video display.
ending – display shown when the
entire game is completed
When the player completes the
entire game, the program will detect that in the draw state. If
so, the program will remove the cars, the gridlines and the words “EXIT” and
“LEVEL XX”. Basically we will start with a blank screen. Later, the
congratulatory message “CONGRATS YOU R DONE” is shown on the
screen. An ending animation will be shown on the video display.
waiting2 – controlling the ending animation
This state basically controls
the movement of the cars in the ending animation.
3.3 Patents,
copyrights, and trademarks
We
are not using our project for any commercial purposes.
4. Hardware Design
4.1
Setting up the E-Field Sensors
For the E-field sensors, we used two MC33794D chips from
Freescale Semiconductor. Each MC33794 chip has 9 electrodes, but our game
requires 13 electrodes – 6 each for the rows and columns and 1 for select
button. Thus, two chips are used. 6 electrodes for the row are attached to the
first MC33794D chip, and 7 electrodes (including the select button) are
attached on the second chip.
Since E-field sensors are prone to noise and
instability, there are several physical and electrical considerations that must
be addressed in order for us to implement a reliable and functional playing
grid design.
The
MC33794D chip is an E-field / capacitive-based sensor
The chip contains nine sensor electrodes, each of
which will be grounded if not attached. An E-field sensor is also known as a
capacitive-based sensor. If two electric plates are separated by a distance d
and they have a potential difference of V, the electric field E is
Diagram of a Parallel Plate
Capacitor: Q => charge, E => electric field, d => distance
The capacitance C of a capacitor
with charge Q and –Q and potential difference V follows this general
equation
For a parallel plate
capacitor as shown on the right, the capacitance is given by
where 
is
the permittivity of the material in between the plates, A is the surface area
of the plates, and d is the distance separating the plates. The ratio of
the permittivity of the material X to air (free space) gives us the relative
dielectric constant of the material X. The dielectric constant gives us a
measurement of how much the material support electrostatic fields.
The current that is flowing through the two plates
can be measured by this equation, where dV/dt is the rate of change of the
potential difference between the two plates.
The MC33794 makes use of these capacitive properties
to create an E-field sensor. If a wire is connected to the sensor electrode,
and nothing is near it, the voltage will remain high. But if a human finger
comes close to the wire, the e-field will naturally form a path to the finger and
to ground. This is because humans are mainly composed of water, which has a
high dielectric constant and is highly conductive as well due to the ionic
nature of water. This change in electric field current is registered by the
MC33794D and reflected as a change in output voltage in a pin labeled as LEVEL.
Since current I can only be present in when voltage V
is changing with time, the MC33794D Integrated Circuit is capable of generating
a sine-wave that is optimized at 120 Hz to prevent noise interference (60Hz).
More specific details regarding how the chips work and the technical data can
be found in the References section.
Size of
MC33794D Electrode Tradeoff
Attaching a conductive material to the wire to
increase the surface area for increased range and sensitivity is good. But as
the electrode size increases, so do the interference and noise effects
increase. This tradeoff is not easy to resolve, because the MC33794D is capable
of non-contact detection. In order to minimize noise and interference effects,
the MC33794 data sheet recommended designing the electrode to fit the surface
area of the object being detected – in our case, a human finger.
Therefore, we modeled our playing grid after the
actual playing grid of the Rush Hour game. Our square grids are 0.39 × 0.39
inch (1 × 1 cm) so that a human finger will be able to touch both the column
and row electrodes when placed on one grid.
Fringing
Effects due to Paired Electrodes
We plan to design and build the game board using a 2D
array of E-field sensors. This means that paired electrodes have to be used to
detect both the row and column of the player’s finger. Fringing effects occur
when paired electrodes are placed together. As seen in the following diagram,
the fringing field allows ungrounded objects to be detected in the “third”
dimension – the space above the 2D array. The larger the distance between the
two electrodes, the larger the fringing field.
The Effects of Fringing and Distance
between Paired Electrodes
Final Design Decision
Taking into account the
above points, we decided not to increase the surface areas of our
electrodes. Since our paired electrodes are closely spaced (0.197 inch/
0.5 cm) within a grid, we cannot rely on the greatly reduced fringing effects
to detect the height dimension of the player’s fingers. The player must
therefore be physically touching the wires in order for the sensor to register
a change in current.
Building the 6×6 Playing Grid
In order to create a playing
board, we built a 6 × 6 cardboard grid that has wires running through each row
and each column. Our design follows the configuration as shown in the diagram.
Note that the horizontal and vertical wires do not touch at any point in time.
Also, there is no extra material placed on the electrodes as marked by E1, E2,
E3 and all the other electrodes in the diagram.
Column-Row Wire Configuration:
Diagram from Freescale AN1985 technical sheet
Since there are six rows and six columns, twelve electrodes
run through the grid as shown in the diagram (grid diagram and underside).
Since E-field sensors are used, all the wires cannot come into contact with
each other at any point in time as this causes interference and corrupts the
readings. Therefore, we wove the wires through the cardboard and inserted
strips of cardboard to prevent the wires from touching. See diagram (underside
of grid)
Figure: Diagram of 12 electrodes
running through the touchpad.
Note that at no point in the
setup do any 2 electrodes touch each other.
Figure: Underside of
Diagram.
Note how the vertical electrodes are
taped to provide electrical insulation from the horizontal electrodes.
Figure: Underside of
Diagram.
Strips of cardboard were added to increase
the electrical insulation between the vertical and horizontal electrodes.
Constructing the Select button
Simply put, the select
button is just another electrode that uses E-field sensors to detect the user
selection. For this project, it is just
a single wire that is taped onto the game board, which the user can then use to
select any car.
Transmitting
and Receiving the Sensor Signals
One MC33794D chip has one LEVEL pin that reads the
output from a selected electrode. This means that only one electrode output can
be polled at one time. How then does the MC33794D allow
polling for the other 8 electrodes?
The MC33794 chip has the following Electrode Selection Table in the technical
data sheet. ABCD are control pins of the MC33794D that allow the user to select
and poll a specific electrode. The table shows which electrode output will be
set in LEVEL after the control signals have been set. This emphasizes the need
for bi-directional communication between the MC33794D and the MCU.
|
TERMINAL/SIGNAL |
D |
C |
B |
A |
|
Source (internal) |
0 |
0 |
0 |
0 |
|
E1 |
0 |
0 |
0 |
1 |
|
E2 |
0 |
0 |
1 |
0 |
|
E3 |
0 |
0 |
1 |
1 |
|
E4 |
0 |
1 |
0 |
0 |
|
E5 |
0 |
1 |
0 |
1 |
|
E6 |
0 |
1 |
1 |
0 |
|
E7 |
0 |
1 |
1 |
1 |
|
E8 |
1 |
0 |
0 |
0 |
|
E9 |
1 |
0 |
0 |
1 |
We programmed the MCU to set ABCD to poll E1 to E6 in
the first MC33794D chip – this represents 6 rows of the grid. Next the MCU will
set ABCD to poll E1 to E7 on the second MC33794D chip to poll the 6 columns of
the grid and the select button. The MC33794D data sheet recommended that
LEVEL should be polled at least 1.5 ms after ABCD is set to allow for settling
time. Time is needed for the signal to settle down because a capacitor (LP_CAP)
is used filter the output noise in LEVEL.
Therefore, we set the polling interval in the
interrupt to be approximately 1.9ms. We obtained 1.9ms by setting the polling
period to occur once every 30 horizontal sync pulses are sent in the
interrupt as described in Dr. Bruce Land’s video code.
The video refreshes the screen at 60 frames/ second.
Hence 1 frame takes 63.6µs. The black-and-white television prints 262 lines per
frame. Therefore each polling period is
This allows for sufficient
time for the LEVEL output from the MC33794D to settle before polling its
result.
Railing
the LEVEL output
When a human finger is placed
on the polled electrode, the output voltage of LEVEL becomes 0 volts.
However, when the finger is removed, LEVEL reads 1.87 volts.
Initially, we considered using
the analog/digital converter (ADC) capability of the ATmega32 MCU so that we
can program the input signal (which is the LEVEL output) to be HIGH if it
exceeds a certain threshold voltage. However, upon consulting our TA Idan, we
realized that the ADC is used mainly for measuring a range of values that
require some degree of accuracy (e.g temperature). The ADC is not needed here
because we want the MCU to give us either a yes (1 – finger there) or a no (0 –
finger not there). We needed a circuit that can rail our output to 5V if the
finger is on the wire and 0V otherwise. This will enable the MCU to interpret
the 0 or 5V input easily.
Figure: Schematic of the
amplification circuit.
Note that it takes in the LEVEL output
from the MC33794 and inverts it, railing it from 0V to 5V.
We consulted Dr. Bruce, who
suggested that we use a general purpose amplifier –the 2N3904 NPN transistor.
Basically, the output voltage of the 2N3904 will read 5V if the input voltage
is less than 0.7V. If the input voltage is above 0.7V, the output voltage from
the 2N3904 will read 0V. The reaction time of the 2N3904 is around 35-50 ns,
which is insignificant compared to the settling time of the LEVEL output.
An NPN transistor was chosen because
of the behavior of LEVEL output. If the finger is on the polled electrode, the
LEVEL output was 0.07V. Since we wanted the MCU to read a HIGH (5V), the NPN
transistor serves as an excellent voltage inverter that is fast and accurate.
The NPN circuit gave railed outputs from 0V to 5.02V ~ 0V to 5V when the finger
left and touched the wire.
Minimizing
Wire Distance from MC33794 to MCU
We encountered some challenges
when we wired the grid output wires to the MC33794D. We secured the wires
neatly on the underside of a piece of cardboard that has our grid attached on
top. Even though the output read right when only one row is connected and
tested at a time, when all the rows are connected, the second grid row
dominated the output readings in the television.
We then discovered that the
length of the wires do play a critical role in ensuring a correct LEVEL output.
The previous design uses long wires which affected the capacitive property of the
wires. This resulted in the shortest wire (i.e. row 2) dominating the grid when
the MCU interprets the results. The wires were re-routed and shortened so as to
minimize the physical length of wire. The finalized setup for the
touchpad is given below.
Figure: Finalized setup for touchpad.
Note that the wires should not be too close,
otherwise it will influence each others’ E-field
5. Software Design
Making the Game Graphics
- Drawing the Grids on TV
36 grids are drawn on the TV
to simulate the playing field. Each grid is 14 × 14 pixels in dimension.
An “EXIT” sign is also printed beside the grid where the red car is supposed to
drive to in order to complete the game.
- Drawing the Cars on TV
Since our television is unable
to print in color, all our “non-red” vehicles are drawn in the same manner,
making them indistinguishable. Only the “red” car has to be distinct from the
other vehicles. Simply put, the “red” car as addressed in this project is the
car that anyone playing this game would want reach the exit point. One
can see from the following table that there are eight unique car “portions” in
this game.
|
|
|
|
|
|
