Your browser does not support the applet tag.
This applet allows one to simulate robot freeze tag for any setup of robots. The way robot freeze tag
works is you start with one robot that's awake (colored green), and some number of sleeping robots (red)
located throughout the plane. As in the game freeze tag when players are tagged, the robots can't move
until they are woken up by another robot that touches it. The goal for a given setup is typically to find
the optimum schedule for which robot wakes up which such that all robots wake up in the shortest time
possible. This is discussed further in http://maven.smith.edu/~orourke/TOPP/P35.html#Problem.35A,
and http://arxiv.org/abs/cs.DS/0402045 (the latter is the paper proving this problem to be NP-complete).

In this applet you click the mouse on the canvas to place robots, and a schedule will be maintained
automatically as you do this, which is just a complete binary tree in which the order you place the nodes
is the level order for the tree. Once you have some robots placed, you can press start to watch them wake up.
Reset allows you to return to your original configuration of robots after watching them wake up, and you can
try different schedules to compare the total times elapsed to wake up.

A few distinct algorithms are provided to try and find good schedules. The greedy algorithms create
the schedule by starting with the root and essentially picking the closest robots as the next ones to be
woken up. Version 1 only considers the already woken up robot that has travelled the least distance and
gives that robot its two children by finding the two closest, whereas version two considers all robots
that can still have children and finds the unclaimed robot closest to any child-able robot to add to the
schedule. Both are reasonably fast, although beyond n = 1000 version 2 starts to take quite a long time

Finally, optimal considers all n! permutations of the schedule for robots and takes
an untractably long time for n > 10 or so. (10 takes about 10 seconds, so 11 takes about 11*10 seconds
= 2 minute, etc.) Note that optimal is not truly optimal yet, as the topological structure of the tree is
always kept as close to complete as possible, so really it'll be even more than n! permutations,
when all the tree structures are considered.

Areas that I think could use updating:
Reset button should keep the previous schedule; right now greedy algorithms lose it after running.
Optimal algorithm should actually be optimal.
Having some preset configurations of robots could be interesting. of robots could be interesting.
Some kind of easy to use manual rescheduling (right now manual does nothing).