The applet requires Java 1.5 or higher. It is known to work on Windows XP and Vista under Internet Explorer, Mac OS X Leopard under Safari, and Ubuntu Linux under Firefox.
The applet has a Control Panel on the left for configuring the parameters of the puzzle and has a representation of Grid City in the pane on the right. Each block is depicted along with its four entrances. The plow is represented by a small colored square. The plow is initially green and in the top left corner of Grid City.
As paths are plowed the number inside each block is updated to show its score - that is, the farthest that a pedestrian must walk from that block to get to a neighboring block (north, east, south or west).
In order for you to use the keyboard the Grid City pane must have keyboard focus, which means it is receiving the keystrokes that are being entered. Moving the mouse onto the Grid City pane should be enough to accomplish this, however you may need to cajole the applet to get keyboard focus. One thing that usually works is to click in an edit field in the Control Panel (e.g. the field for editing the number of blocks Grid City has going across) and then move the mouse over to the Grid City pane.
When the Grid City pane has keyboard focus it will be drawn with an interior border, as shown in the image below.
|Closeup of Grid City pane with interior border indicating keyboard focus.|
If you have more than one plow (as specified by the "Plowing Rules") you can now position the next plow in its starting position and plow a second path.
The plow is green when it is not plowing and red when it is plowing.
|Plowing a path. Tiny indicator arrows point to "offending blocks".|
When the maximum distance from a block to any of its neighbors is not zero, indicator arrows will point to the "offending" block or blocks - that is, the block or blocks that account for the maximum distance. To avoid clutter, no indication will be shown if the distance to all neighbors is infinity.
Indicator arrows can be seen in the image above.
Click on a block in Grid City to enter "Inspect Mode". The selected block will be shaded and red lines will be drawn to show the shortest paths (if any) to its adjacent blocks. Click on the block again to exit "Inspect Mode".
|Inspect mode. Paths from the gray block to each neighbor are shown in red.|
It is possible to specify an entire puzzle configuration in one go using the "Set Puzzle" dialog (bottom of the Control Panel). It is also possible to run a script (a sequence of key commands) using the "Run Script" dialog (also at the bottom of Control Panel). The dialog will come up with the key commands that have been entered so far.
Because of Java applet security restrictions it is currently not possible to copy from or paste to these dialogs.
The applet should be reasonably responsive for small grid sizes (up to 8 x 10). For larger grid sizes the applet will become noticeably slow and may take several seconds to respond to an action. Currently the applet is not set up to show a busy cursor (e.g. hourglass) to indicate when it is performing a slow computation.
This section discusses the algorithm that is used internally to compute the shortest paths. The shortest paths have to be recomputed every time a street is plowed or any time a change is made to the configuration. Ideally this recomputation should occur within a few hundred milliseconds so that the user delay is minimal and the applet doesn't feel sluggish.
To compute the shortest paths between blocks I construct a graph where every intersection and every entrance is a vertex, and then I connect:
So with an 8x10 grid there are 99 intersections and 320 entrances for 419 vertices in total. If, for example, every street is plowed that makes 178 edges connecting intersections (9*10 for the north-south streets and 8*11 for the east-west streets). Each intersection can service up to four entrances (regardless of whether entrances are on corners or sides), yielding another 396 (=99*4) edges at most. If "Walk through buildings" is checked there are 480 (=80*choose(4,2)) edges connecting entrances within the blocks. So in the worst case there are 1054 edges (=178+396+480) for an 8x10 grid.
To compute the shortest paths I run Dijkstra's algorithm from each entrance vertex. Originally I used BFS which is much faster but Dijkstra's algorithm supports arbitrary nonnegative weights (e.g. for walking through buildings) and allows for a much more natural graph construction. The internal MIN-QUEUE inside Dijkstra is a naive linear implementation, so the total running time is O(V^3), that is, cubic in the number of vertices.
I considered all-pairs shortest paths algorithms but these are typically cubic or at best O(V^2 lg V) and for a graph this small I felt the extra overhead of the more complicated algorithm would offset the improvement in going from V to lg V. I also considered a binary MIN-QUEUE implementation so that finding the min would happen in log rather than linear time, but again for this number of vertices I felt the considerable overhead of managing the heap and keeping the handles in sync would not yield much improvement.
I did introduce a few optimizations that made a substantial difference in the response time of the applet.
Written by Arefin Huq
Comments? Email me at firstname.lastname@example.org