next up previous contents
Next: Tree Search Up: Programs for Playing Lemmings Previous: Planning

First Experiments with Lemmings

Perhaps I am too unambitious, but Lemmings strikes me as presenting considerable experimental difficulties, and I advocate starting slowly. Here are some steps.

  1. A tool is needed for programs that interact with the Lemmings program. It should begin with interaction with the pixel maps displayed by the program. Programs like Planet X bring the pixel map of a Macintosh into an X-window, and an analogous program could bring it into an X-window reachable by a Common Lisp or C++ program. Alternatively, the Lemmings pixel map might be accessed directly by programs in the Macintosh or in a PC.
  2. Another early step is the parsing of the pixel map into regions. The result of such a parsing is a tree of regions and subregions. Very likely the parsings will have to be extendable when the program decides that it is necessary to go back to the pixel map for more information.
  3. The first programs to play the game should concentrate on the easier games. Many of these can be solved greedily, i.e. by reacting to the scene with actions that move the situation closer to the goal.
  4. The next step is tree search as discussed in the next subsection.

John McCarthy
Mon Mar 2 16:21:50 PDT 1998