Space in the lemming world is two dimensional. Nevertheless, an epistemologically adequate representation of space and objects for the Lemmings world requires features that go beyond what has been treated in the AI literature.
The screen in the Lemmings world is a pixel map. Like all modern computer games it uses colors, but the literature says Lemmings is playable on a gray scale display. We suppose this pixel map is accessible to a program that plays the game. To play the game it also needs the ability to imitate moving and depressing the mouse. There are keyboard shortcuts for some of the mouse actions, but we ignore them, because we are not trying to formalize human speed of action.
The problem for AI is that a human player does not decide what to do operating directly from the pixel map. Instead the human considers the screen as divided into regions, some of which are chambers consisting of empty space that can contain lemmings and possibly other objects and some of which are solid material. Some of the solid material can be turned into space by digging. Separated regions are sometimes combined when lemmings build bridges.
Human players do not convert the picture into an internal form from which all decisions are made without further reference to the picture. Information from the picture is put into mental forms that are not well understood physiologically or psychologically, and decisions about what to do involve repeated reference to the picture. In particular, one often looks at the details of particular areas of the scene or puts newly relevant global features into the mental model. On the other hand, important facts about the picture can be internalized well enough so that I player can get a new idea about how to win while out of sight of the game.
We claim that these aspects of the human way of handling visual information are not just peculiarities of humans. Their main aspects are features of what we have called the common sense informatic situation [McCarthy, 1989]. Computer programs operating in the real world, e.g. controlling mobile robots, also face the common sense informatic situation. This is characterized by incomplete information about the situation itself and incomplete information about the laws that determine the effects of actions.
Therefore, we plan that a Lemmings program will parse the scene into a collection of regions and relations among them. The initial parsing will be later extendable by further reference to the pixel map. Like the human the program will use the scene as its own most comprehensive model, although not always its most intelligible or useful model.
The parsing therefore has two unusual aspects.
The simplest kind of region may be called a chamber. The simplest
kind of chamber has an essentially horizontal floor and walls at each
end that reflect walkers.
In section 8, page 
, we will discuss
actions and events using situation calculus. S0 stands for the
situation when a particular game called Game0 starts. Game0 is a
simplification of the first game in Lemmings Jr. There is only one
lemming. See figure [].
A simple chamber will be rectangular on the screen with walls at both
ends. We make 
a simple chamber in 
and can rely on persistence
to keep it a simple chamber in 
and beyond. This would be used in
planning to solve Game0. Alternatively, if we are actually playing Game0,
we can observe that is a simple chamber in . This requires
a mechanism for associating names with features of the picture and with
situations depicted on the screen. We haven't decided how to do this yet.
Consider chambers which confine lemmings until something is done about it. They are bounded by simple closed curves, but that high level of generality isn't the common sense way of thinking about them. One could suppose that chambers in the lemming world are a subclass of the interiors of simple closed curves and try to formalize a suitable subclass. This is a bad idea, because we haven't seen all the chambers Psygnosis Ltd. has chosen to use, and they are likely to invent new ones with each new lemming variant they market. Their artists draw the chambers and the regions that surround them according to the requirements of the game designers and their artistic taste. These drawings are then digitized. No human player can represent a digitized screen pixel by pixel, and our formalism can't do this either.
Instead we start with simple figures and elaborate them. The simple
chamber is one of these starts. A program that reasoned about the game
would observe the screen of Game0 and recognize the upper chamber
as a simple chamber and give it a name. In Game0, the floor of is
not entirely even, but these surface rills make no difference. It doesn't
matter where 
digs its hole. In other lemming games it does make a
difference. For example, it might have been necessary in Game0 to dig
in a low place in order that the lemmings should not fall too far.
We propose to handle unevenness by allowing additional statements about chambers that have been identified as simple chambers. Complete descriptions of surfaces are not required, but relevant observations may be expressed. Perhaps this is a form of belief revision, e.g. the player formerly believed the chamber was simple and has changed hsi mind; some of the considerations advanced in the study of belief revision might then apply. Another way of handling this idea is to say that c0 is a certain kind of simple chamber and express the unevenness in describing what kind.
We also will handle the chamber with the digger's hole by elaborating the simple chamber description. This will be belief update rather than belief revision.
We can implement the above using a notion of chamber type, or more
generally, type of lemming region. 
would
be the type that is instantiated by . 
is is instantiated by
. (We are not committed to this particular notation for
elaborating simple figures.) We need types in the formalism and
not just individual regions, because we need to make new types by
elaborating simpler ones, e.g. we make a chamber with the lemming
sink at one end by elaborating simple chambers.