Quicksilver - a Bike Messenger Simulation Game


Background - Project Notes

This project began as a proof of concept for a route-plotting software application based on the Census Bureau's TIGER/Line files. The code uses Dijkstra's single-source shortest path algorithm to determine the shortest path between any two arbitrary locations on the map. This was one of the primary functional requirements, and you can see this in action in one of the screenshots below. Although fun to implement, this turns out to be rather basic stuff.

One of the most interesting and challenging aspects of the project turned out to be related to what everyone thought was a relatively minor UI requirement. The spec calls for a mouse cursor motion event to fire a search for whatever segment (road) is nearest to it, displaying the result in the status bar. To do this properly requires some fairly sophisticated data structures, since naive search will be far too expensive to calculate in real time. This problem led me to the excellent work of the authors cited below, and the discovery of the nearest neighbor graph algorithms and data structures such as the PMR Quadtree.

The PMR Quadtree defines a disjoint partitioning of the map space into blocks, each of which may only contain a certain maximum number of segments. Beginning with a single root node containing all the space of interest, segments are added until a threshold is reached. Whenever the threshold is reached in a given leaf node, that leaf node becomes a parent node and is split into four children, and the parent's segments are inserted anew into each child in which they fall. This enables you to identify the block containing a given query point in logarithmic time, thus greatly reducing the number of segments needed to test for shortest distance to the query point.

My implementation of the PMR Quadtree enables the nearest neighbor search function to complete on average 5,000 times per second on "slow" hardware (400 MHz Pentium 2) using a small graph with about 3,000 edges. This meant that even with a fast refresh rate of 85 Hz, the function could run about 60 times before the monitor could update itself. This was well within optimal design parameters for usability!

Since the PMR Quadtree was so much fun, I decided to take a subset of the code public in what is a hopefully amusing application. I'm not much of a game designer, so the AI is really simplistic. As a result I can't attest much to its playability. If nothing else, I hope this project will help promote the fine work of the authors cited below and inspire others who face similar challenges working with graph algorithms and datasets.


  • Erik Hoel and Hanan Samet, "Efficient Processing of Spatial Queries in Line Segment Databases", Advances in Spatial Databases - 2nd Symp., SSD '91, (O. Gunther and H. J. Schek, eds.), Lecture Notes in Computer Science 525, Springer-Verlag, Berlin, 1991, 237-256.
  • G. R. Hjaltason and H. Samet, "Ranking in spatial databases", in Advances in Spatial Databases - 4th Symposium, SSD'95, M. J. Egenhofer and J. R. Herring, Eds., Lecture Notes in Computer Science 951, Springer-Verlag, Berlin, 1995, 83-95.
  • Gisli Hjaltason and Hanan Samet, "Speeding Up Construction of PMR Quadtree-Based Spatial Indexes", The VLDB Journal, 11 (2002) 2, pp. 109-137. Springer-Verlag.

Quicksilver - Release Notes


Quicksilver is a bike messenger simulation game. You will play the role of the dispatcher for a team of bike messengers whose job is to pickup and deliver packages in the most efficient manner possible. The main window of the program depicts a city map of the territory your team has to cover. Icons appear on the screen to identify the locations of your messengers and packages that are awaiting pickup. When new packages appear, you will assign them to a particular messenger. The objective of the game is to minimize the time it takes to deliver the packages.

The Map

Currently you can choose to play in either Chicago or New York City. The map window operates in much the same way as you would expect from other commercial mapping applications. Buttons are provided below the map window allowing you to zoom in and out, and pan to the north, south, west, and east. A "Reset Map" button restores the view to its original centered position. Although street labels are not present on the map, as you move the mouse over the map window, the status bar will update with the name of the street nearest to the mouse pointer. This feature works "most of the time". If the mouse pointer moves over the icon of a messenger or package, the status bar will update with brief information about the messenger or package. If you hold down the left mouse button while the mouse pointer is hovering over a package icon, the path to the package's destination will be highlighted on the map in red, with a red circle to indicate its target location. Similarly, if a messenger is en route to pickup or deliver a package, holding down the left mouse button will highlight the messenger's current route.

How to Play

Double-clicking a package icon in the map window will bring up the Package Detail screen. You can use the drop-down box on this screen to assign the package to a messenger. Double-clicking a messenger icon in the map window brings up the Messenger Detail screen. When a package is assigned to a messenger, two new commands are added to the end of a messenger's task list: pickup and deliver. You can move commands up and down the task list, but the list won't allow you to deliver a package before you pick it up! Packages can be re-assigned as long as they haven't already been picked up by another messenger.

Press "F2" to bring up a dialog box with a summary list of your messengers. You can also get here by pressing the messenger icon button below the map, or choosing View->Messengers from the menu. Pressing "F3" will bring up a dialog box with a summary list of undelivered packages (also available from the package icon button or from View->Packages). You can double-click on a particular messenger or package list item to bring up the detail screen.

In summary, the basic gameplay is very simple: assign packages to a messenger, then adjust the order of commands in the messenger's task list as needed. There are two other factors that affect gameplay: 1) package size and 2) messenger energy levels.

Every package has an associated weight ranging from Tiny (1), Small (2), Medium (4), Large (8), to Extra Large (16). The numbers in parentheses indicate the numeric weight of the package. A messenger can hold at most a weight of 16, i.e. 16 Tiny packages or 8 Small packages or 4 Medium packages, etc. Any combination of packages can be held en route, as long as the total weight does not exceed 16. Tiny packages are the most common while Extra Large packages are rare -- given the fact that a messenger can only carry one of them and nothing else.

While travelling, messengers burn energy. As their energy level declines, their average speed will decline. Thus, it's important to allow messengers to rest from time to time. Messengers will regain energy if they are idle, and during the short spans of time it takes to process pickups and deliveries. Additionally, you can specifically tell a messenger to take a break by clicking the "Break" button in the messenger detail screen. During crunch times, you can tell a messenger to pour on some extra speed by clicking the "Sprint" button. But beware: sprinting burns twice as much energy as normal.


Every time a package is delivered, points are added to (or subtracted from) your score based on how long it took to deliver the package (calculated from the time the package first appeared). Based on the difficulty level and the number of messengers, a "par" time span is chosen. If you deliver the package under par, the difference will be added to your score.

Special Notes

This program is a work in progress. There are likely to be crashes, glitches, and other bugs of assorted shapes and sizes. Furthermore, the controls may seem awkward and the game logic will need fine-tuning. The goal of this initial release is to gather opinions on what needs improvement. Please send your suggestions and any problems you encounter to the email address listed above. Thank you and many speedy deliveries!


Click on an image below to see a larger picture

The first image of downtown Chicago illustrates the shortest path (bold red) for a messenger travelling to pickup a package. The second image of lower Manhattan shows the results of the nearest neighbor search algorithm, with the mouse cursor centered on Broadway.


Win32 Binary

Click below to download a zip file containing the Quicksilver binary for Windows.

Download Quicksilver for Windows


Quicksilver is written in C++ using the wxWindows API. This means it can also run on Mac and UNIX platforms, but to do so you will need to set up wxWindows to compile for your platform. Click below to download a zip file containing all source code.

Download Quicksilver Source Code

Browse Source Code

All the files contained in the source code zip are available below.