Quicksilver - a Bike Messenger Simulation Game
Contents
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.
References:
- 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.
