For our "robot creatures on a table" project,
I put together this simple-minded algorithm
that allows a bunch of robots
to get from a start position to an end position,
without crashing into each other.
The basic approach is "divide and conquer:" First find a position 1/2 way along the path where they don't crash into each other, then find 1/4 and 3/4 positions, and so on. Finally, gradually "relax" the paths, by alternately smoothing them and pushing them away from each other. In this demo applet, we choose random setups (random start and end positions), and the robots need to figure out a path that works. Instructions Drag on any robot to move it. Then:
|
Source code: | pathApplet.java | extends BufferedApplet |
calls PathFinder.java |
Copyright 2003 Ken Perlin