PyTraffic
What is it?
PyTraffic
is a computer version of the board puzzle Rush Hour invented by
the famous puzzle designer Nob Yoshigahara and commercialized by
Binary Arts Corporation. The goal is to remove the red car out of the
grid through the slot on the right. To do this you have to slide the
other cars out of the way. PyTraffic is written in the scripting language
Python.
Playing the game on a real board is much more fun than playing it on
the computer (ask my daughter!). So after having used PyTraffic you may
consider buying the real thing.
Features
- PyTraffic comes with about 19.000 puzzles ranging in difficulty
from "Intermediate" to "Expert".
- In addition it is possible to play
"Trivial" and "Easy" levels which are generated on the fly. These are
suitable for small children. My six year old daughter Sarah routinely
does "Easy" puzzles.
-
PyTraffic has a help facility which is able to find
the best move in every position. It is available through a button on
the toolbar.
- PyTraffic comes with several "themes". Some of the themes have a 3D-look.
Making your own
themes is not very hard.
Installation
The short story:
- For windows there is a self-extracting installer which includes all
depencies.
If you have an earlier version of PyTraffic then it is strongly recommended to uninstall
it first.
The long story is as follows. PyTraffic has the following dependencies:
-
PyTraffic is written in the scripting language Python. Python
is usually installed by default on GNU/Linux distributions. If not,
then it is at least included on the installation media. You may also
grab Python from www.python.org.
- For its GUI, PyTrafffic uses "pygtk", the Python binding to the
gtk-toolkit. Again gtk and pygtk are usually installed by default.
- For sound and music PyTraffic uses "pygame" which in turn depends
on SDL. If pygame does not come with your distribution (for example in
a "contrib" or "extra" section) then see the homepage of pygame for
installation instructions.
Here are some installation methods if you are not using the monolytic
Windows installer. Remember that you will have to take
care
of the dependencies.
How does the help feature work?
- The help feature is based on an exhaustive search. For a given
level PyTraffic creates a graph of all positions as well as a
hash table for quick lookup. Then using a standard algorithm in graph
theory it determines for every node the minimal distance to one the
leaf nodes, i.e. a node where the red car has escaped the grid. Using
this information PyTraffic can easily determine the best move in
every position.
- PyTraffic uses a precomputed database with about 19.000
interesting positions. These were generated by searching through ALL
levels and keeping those which take at least 20 moves to solve.
Generating this file took about 60 hours on a Dell P600 with 80Mb,
running RH-Linux 6.0. Of course for this to be possible examining a
single level had to be very fast. By applying various optimizations
to the algorithm outlined in the previous paragraph the computer could
solve a level in (on average) 0.03 seconds.
- If you want more information on how PyTraffic stores levels you
can look here.
Notes
- To reset the state of the program, delete the config file
~/.pytraffic (the meaning of ~ is system dependent: it is the user's
home directory on Unix).
- If you have solved a level and you are curious what the best
solution would have been, push the Restart button and then repeatedly
push the Hint button until the level is solved again (or start demo mode).
- If your are on GNU/Linux and experience sound problems you may want
to read this.
Acknowledgement
-
PyTraffic was inspired by Gtraffic, a
Gnome version of Rush Hour, and supersedes
TTraffic which was a Tcl/Tk
version of Rush Hour.
- Out of principle I used mostly free tools for the creation of
PyTraffic. Thanks go to the creators of Python,
the Python Imaging
Library, gtk,
pygtk,
distutils, SWIG, Gimp, Inkscape, ImageMagick,
Netpbm,
SDL,
pygame,
Audacity,
the Gnu/Linux
operating system,
the Mingw/gcc-compiler,
the Cygwin environment,
the Inno Setup program and
the py2exe
executable generator on windows.
- For the creation of the 3D-themes I used
POV-Ray.
POV-Ray is a very powerful, cross-platform ray tracer which however is currently not
free software nor
open source. The current developers
cannot change this since not all the original developers can be contacted. However they
have repeatedly indicated that the next version of POV-Ray (4.0) will use a more liberal license.
- The subroutine 'gethomedir' was taken from the PySol
distribution by Markus Oberhumer.
-
The sound track is "Ranger Song" which was licensed under the GPL by
its author Carl Larsson (aka Nightbeat). I took it from the PySol
distribution.
- The animation routine was contributed by Jesse Weinstein.
- Thanks to the people of http://www.lib.utexas.edu/Libs/PCL/Map_collection/Map_collection.html
for making copyright free maps available. I used one of those to
produce the background for the Fancy2D theme.
- Finally thanks to Google
for providing us with Google
Images.
Bugs
PyTraffic has no known bugs but there are some 'issues'
:
- The hint feature takes about 15Mb of memory. The high memory demand is
due to the fact that PyTraffic currently stores all edges of the move
graph in a table instead of generating them dynamically.
- The hint feature only works on Windows and Unix since I have no
access to a Mac and I have no idea how C-extensions work there. In fact I have not tested PyTraffic on a Mac so it could be that it does not work at all!
- There are no levels included containing cars and trucks in the same row or
column, although some of these appear to be interesting.
- On older systems PyTraffic takes a rather long time to start up.
This is because the cars are PNG-images which have to be loaded first.
License
PyTraffic is covered by the GNU General Public License.
Extras
- There are many Java versions of Rush Hour.
See for example here.
-
Here is nice article about the combinatorial complexity of traditional
games.