[N.A.B.G. picture] [ABC cover]


This page contains text from the draft version of a book "A Beginners' C++"; this text is intended for "CS1, CS2" introductory Computer Science courses that use C++ as an implementation language.

This particular page contains the first part of a chapter that presents a relatively elaborate example of the use of class inheritance, polymorphism, dynamic binding etc. The example is a "Moria" ("Rogue") style game.


29: The Power of Inheritance and Polymorphism (first of two files)

This chapter is another that presents just a single example program illustrating how to apply features of the C++ language. In this case, the focus is on class inheritance and the use of polymorphism. The application program is a simple game.

In the days before "Doom", "Marathon", and "Dark Forces", people had to be content with more limited games! The basic game ideas were actually rather similar. The player had to "explore a maze", "find items", and avoid being eliminated by the "monsters" that inhabited the maze. However, details of graphics and modes of interaction were more limited than the modern games. A maze would be represented as an array of characters on the screen (walls represented by '#' marks, staircases between levels by characters like '<' and so forth). Single character commands allowed the player to move the maze-explorer around within the boundaries of the maze. "Rogue" and "Moria" are typical examples of such games; you may find that you have copies on old floppies somewhere.

You aren't quite ready to put Lucas Arts out of business by writing a replacement for "Dark Forces", but if you have got this far you can write your own version of Moria.

The example code given here is simplified with lots of scope for elaboration. It employs a single level maze (or "dungeon"). A map of the dungeon is always displayed, in full, on the screen. The screen size limits the size of the map; having the complete map displayed simplifies play. (Possible elaborations include showing only those parts of the map already explored and "scrolling" maps that are too large to fit on a screen.) The map and other data are displayed using the same system features as used in the "cursor graphics" examples from Chapter 12.

The map, details of the items to be found, and the monsters that are to be avoided (or destroyed) are taken from text file input. Again, this is a simplification. Games like Moria usually generate new maps for every game played.

The playing mechanism is limited. The user is prompted for a command. After a user command has been processed, all the "monsters" get a chance to "run". A "Monster:: Run()" function captures the essence of "monsterdom" i.e. a desire to eliminate the human player.

Naturally, such a game program requires numerous obvious objects - the "monsters", the "items" that must be collected, the "player" object, the dungeon object itself. In addition there will have to be various forms of "window" object used to display other information. Since there will be many "monsters" and many "items", standard collection classes will be needed.

There are two separate class hierarchies as well as a number of independent classes. One limited class hierarchy defines "windows". There is a basic "window" class for display of data with a couple of specializations such as a window used to output numeric data (e.g. player's "health") and a window to get input. (These "window" classes are further elaborated in the next chapter.)

There is also a hierarchy of "things found in the dungeon". Some, like the "items" that must be collected, are passive, they sit waiting until an action is performed on them. Others, like the player and the monsters, are active. At each cycle of the game, they perform some action.

Naturally, there are many different kinds of monster. Each different kind (subclass) employs a slightly different strategy when trying to achieve their common objective of "eliminating the player". This is where the polymorphism comes in. The "dungeon" object will work with a collection of monsters. When it is the monsters' turn, the code has a loop that lets each monster "run" (Monster *m; ...; m->Run();). The pointer m is polymorphic - pointing to different forms of monster at different times. Each different form has its own interpretation of Run().


29.1 The "Dungeon" Game

The "dungeon" game program is to:


[29.1]

Figure 29.1 "Dungeon" game's display.


29.2 Design

29.2.1 Preliminaries

This "preliminaries" section explores a few aspects of the program that seem pretty much fixed by the specification. The objective is to fill out some details and get a few pointers to things that should be considered more thoroughly.

For example the specification implies the existence of "class Dungeon", "class Player", "class Monster", a class for "collectable items" and so forth. We might as well jot down a few initial ideas about these classes, making a first attempt to answer the perennial questions "What does class X do? What do instances of class X own?". Only the most important responsibilities will get identified at this stage; more detailed consideration of specific aspects of the program will result in further responsibilities being added. Detailed analysis later on will also show that some of the classes are interrelated, forming parts of a class hierarchy.

Other issues that should get taken up at this preliminary stage are things like the input files and the form of the main program. Again, they are pretty much defined by the specification, but it is possible to elaborate a little.

We can start with the easy parts - like the main() function! This is obviously going to have the basic form "create the principal object, tell it to run":

int main()
{
	Dungeon *d;
	d = new Dungeon;
	
	Prompt user for name of file and read in name
	...

	d->Load(aName);

	int status = d->Run();
	Terminate(status);
	
	return 0;
}

The principal object is the "Dungeon" object itself. This has to load data from a file and run the game. When the game ends, a message of congratulations or commis-erations should be printed. The Dungeon::Run() function can return a win/lose flag that can be used to select an appropriate message that is then output by some simple Terminate() function.

First idea for files

The files are to be text files, created using some standard editor. They had better specify the size of the map. It would be simplest if the map itself were represented by the '#' and ' ' characters that will get displayed. If the map is too large, the top-left portion should be used.

Following the map, the file should contain the data necessary to define the player, the collectable items, and the monsters. The program should check that these data define exactly one player object and at least one collectable item. The program can simply terminate if data are invalid. (It would help if an error message printed before termination could include some details from the line of input where something invalid was found.)

Collectable items and other objects can be represented in the file using a character code to identify type, followed by whatever number of integers are needed to initialize an object of the specified type. A sentinel character, e.g. 'q', can mark the end of the file.

A plausible form for an input file would be:

width and height (e.g 70 20)
several (20) lines of (70) characters, e.g.
##################### ... ... ###########
#          #        # ... ...        #  #
# ######## #        # ... ...   ####### #
dungeon items
h 30 18 ...		human (i.e. player), coords, other data
w 2 2 10 ...		wandering monster, coords, ...
...
$ 26 6 0 30 0	collectable item, coords, values
q			end mark
Any additional details can be resolved once the objects have been better characterized.
class Dungeon

Consideration of the main() function identified two behaviours required of the Dungeon object: loading a file, and running the game.

The Dungeon::Load() function will be something along the following lines:

Dungeon::Load
	Open file with name given
	Load map
	Load other data

Dungeon:: load map
	read size
	loop reading lines of characters that define 
		the rows of the map

Dungeon:: load other data
	read type character
	while character != 'q'
		create object of appropriate type
		tell it to read its own data
		if it is a monster, add to monster collection
		if it is a collectable, add to collectable 
			items collection
		if player, note it (make sure no existing player)

	check that the data defined some items to collect

The Dungeon::Run() function could have the following general form:

Dungeon::Run() 
	Finalize setting up of displays
	Draw initial state

	while(player "alive") 
		player "run"

		if(all collectables now taken)
			break;

		for each Monster m in monster collection
			m->Run();

	return (player "alive");

The displays must be set up. Obviously, the Dungeon object owns some window objects. (Some might belong to the Player object; this can be resolved later.) The Dungeon object will get primary responsibility for any work needed to set up display structures.

The main loop has two ways of terminating - "death" of player, and all collectable objects taken. The game was won if the player is alive at the end.

The Dungeon object owns the collection of monsters, the collection of collectable items, and the player object. Collections could use class List or class DynamicArray.

The Player object will need to access information held by the Dungeon object. For example, the Player object will need to know whether a particular square is accessible (i.e. not part of a wall), and whether that square is occupied by a collectable item or a monster. When the Player takes a collectable item, or kills a monster, the Dungeon should be notified so that it can update its records. Similarly, the monsters will be interested in the current position of the Player and so will need access to this information.

Consequently, in addition to Load() and Run(), class Dungeon will need many other member functions in its public interface - functions like "Accessible()", and "Remove Monster()". The full set of member functions will get sorted out steadily as different aspects of the game are considered in detail.

Most "dungeon items" will need to interact with the Dungeon object in some way or other. It would be best if they all have a Dungeon* data member that gets initialized as they are constructed.

class Player

The Player object's main responsibility will be getting and interpreting a command entered by the user.

Commands are input as single characters and define either movements or, in this game, directional applications of destructive "magic". The characters 1...9 can be used to define movements. If the keyboard includes a number pad, the convenient mapping is 7 = "north west", 8 = "north", 9 = "north east", 4 = "west" and so forth (where "north" means movement toward the top of the screen and "west" means movement leftwards). Command 5 means "no movement" (sometimes a user may want to delay a little, e.g. to let the player object recover from injury).

The "magic action" commands can use the keys q, w, e, a, d, z, x, and c (on a standard QWERTY keyboard, these have the same relative layout and hence define the same directional patterns as the keys on the numeric keypad).

The main Player::Run() function will be something like:

Player::Run()
	char ch = GetUserCommand();
	if(isdigit(ch)) PerformMovementCommand(ch);
	else PerformMagicCommand(ch);
	UpdateState();
	ShowStatus();

It will involve several auxiliary (private) member functions of class Player.

A GetUserCommand() function can arrange to read the input. Input is echoed at the current location of the cursor. This could mess up the map display. Consequently it will be necessary to position the cursor prior to reading a command character. This work of cursor positioning and actual data input will involve interactions with window object(s).

A function UpdateState() can deal with the business about a Player object's health and manna levels increasing. A ShowStatus() function can keep the displays current; again this will involve interactions with windows.

The Perform... functions will involve interactions with the Dungeon object, and possibly other objects as well.

class Collectable

The collectable items could be made instances of a class Collectable. It does not seem that there will be any differences in their behaviours, so there probably won't be any specialized subclasses of class Collectable. At this stage, it doesn't appear as if Collectable objects will do much at all.

They have to draw themselves when asked (presumably by the Dungeon object when it is organizing displays); they will own a character that they use to represent themselves. They will also need to own integer values representing the amounts by which they change the Player object's health etc when they get taken. Some access functions will have to exist so that the Player object can ask for the relevant data.

A monster object moving onto the same point as a Collectable object will hide it. When the monster object moves away, the Collectable object should be redrawn. The Dungeon object had better arrange to get all Collectable objects draw themselves at regular intervals; this code could be added to the while() loop in Dungeon::Run().

class Monster

As explained in the dungeon game specification, the basic behaviour of a Monster is to attack whenever possible, otherwise to advance toward the Player when this is possible, otherwise to continue with some "normal action". This behaviour could be defined in the Monster::Run() function which would involve a number of auxiliary functions:

Monster::Run()
	if(CanAttack())
		Attack();
	else
	if(CanDetect())
		Advance();
	else
	NormalMove();

Different subclasses of class Monster can specialize the auxiliary functions so as to vary the basic behaviour. Naturally, these functions will be declared as virtual. Auxiliary private member functions used by Run()

Default definitions are possible for some member functions. The default CanAttack() function should return true if the Player object is adjacent. The default Attack() function would tell the Player object that it has been hit for a specified number of points of damage. The default implementations for the other functions could all be "do nothing" (i.e. just an empty body { } for Advance() and NormalMove() and a return 0 for CanDetect()).

Checking adjacency will involve getting a pointer to the Player object (this can be provided by the Dungeon object) and then asking the Player for its position. It might be worth having some simple class to represent (x, y) point coordinates. A Monster object could have an instance of class Pt to represent its position. The Player could return its coordinates as an instance of class Pt. The first Pt could be asked whether it is adjacent to the second.


29.2.2 WindowRep and Window classes

Previous experience with practical windowing systems has influenced the approach developed here for handling the display. As illustrated in Figure 29.2, the display system uses class WindowRep and class Window (and its specialized subclasses).

WindowRep

Actual communication with the screen is the responsibility of a class WindowRep (Window Representation). Class WindowRep encapsulates all the sordid details of how to talk to an addressable screen (using those obscure functions, introduced in Chapter 12, like cgotoxy(x,y,stdout);). In addition, it is responsible for trying to optimize output to the screen. When the WindowRep object gets a request to output a character at a specific point on the screen, it only performs an output operation if the character given is different from that already shown. In order to do this check, the WindowRep object maintains a character array in memory that duplicates the information currently on the screen.

The program will have exactly one instance of class WindowRep. All "window" objects (or other objects) that want to output (or input) a character will have to interact with the WindowRep object. (There can only be one WindowRep object in a program because there is only one screen and this screen has to have a unique owner that maintains consistency etc.)
[29.2]

Figure 29.2 Class WindowRep and the Windows class hierarchy.

A class for which there can only be a single instance, an instance that must be accessible to many other objects, an instance that may have to create auxiliary data structures or perform some specialized hardware initialization - this is a common pattern in programs. A special term "singleton class" has been coined to describe this pattern. There are some standard programming "cliches" used when coding such classes, they are followed in this implementation.

The unique WindowRep object used in a program provides the following services:

There is another specialized static (class) function, Instance(). This handles aspects of the "singleton pattern" (programming cliche) as explained in the implementation (Section 29.3). Essentially, the job of this function is to make certain that there is an instance of class WindowRep that is globally available to any other object that needs it (if necessary, creating the program's unique WindowRep object).

Window

Window objects, instances of class Window or its subclasses, are meant to be things that own some displayable data (an array of characters) and that can be "mapped onto the screen". A Window object will have coordinates that specify where its "top-left" corner is located relative to the screen. (In keeping with most cursor-addressable screen usage, coordinate systems are 1-based rather than 0-based so the top left corner of the screen is at coordinate (1,1).) Window objects also define a size in terms of horizontal and vertical dimensions. Most Window objects are "framed", their perimeters are marked out by '-', '|', and '+' characters (as in Figure 29.1). A Window may not fit entirely on the screen (the fit obviously depends on the size and the origin). The WindowRep object resolves this by ignoring output requests that are "off screen".

Window objects have their own character arrays for their displayable content. Actually, they have two character arrays: a "background array" and a "current array". When told to "draw" itself, a Window object executes a function involving a double loop that takes characters from the "current array", works out where each should be located in terms of screen coordinates (taking into account the position of the Window object's top-left corner) and requests the WindowRep object to display the character at the appropriate point.

The "background array" defines the initial contents of the window (possibly all blank). Before a window is first shown on the screen, its current array is filled from the background. A subsequent "clear" operation on a specific point in the window, resets the contents of the current window to be the same as the background at the specified point.

A specific background pattern can be loaded into a window by setting the characters at each individual position. In the dungeon game, the Dungeon object owns the window used to display the map; it sets the background pattern for that window to be the same as its map layout.

The Window class has the following public functions:

The class requires a few auxiliary member functions. For example, the coordinates passed to functions like Set() must be validated.

A Window owns its dimension data and its arrays. These data members should be protected; subclasses will require access to these data.

The functionality of class Window will be extended in its subclasses. However the subclasses don't change the existing functions like ShowAll(). Consequently, these functions are not declared as virtual.

The relationships between class Window and its subclasses, and class Monster and its subclasses, are subtly different. The subclasses of Window add functionality to a working class, but don't change its basic behaviours. Consequently, the member functions of class Window are non-virtual (apart from the destructor). Class Monster defines a general abstraction; e.g. all Monster object can execute some "NormalMove" function, different subclasses redefine the meaning of "NormalMove". Many of the member functions of class Monster are declared as virtual so as to permit such redefinition. Apart from the differences with respect to the base class member function being virtual or non-virtual, you will also see differences in the accessibility of additional functions defined by subclasses. When inheritance is being used to extend a base class, many of the new member functions appear in the public interface of the subclass. When inheritance is being used to specialize an existing base class, most of the new functions will be private functions needed to implement changes to some existing behaviour. Both styles, "inheritance for extension" and "inheritance for redefinition", are common.

Subclasses of class Window

This program has two subclasses for class Window: NumberItem and EditText. Instances of class NumberItem are used to display numeric values; instances of class EditText can be used to input commands. As illustrated in Figure 29.3, these are displayed as framed windows that are 3 rows deep by n-columns wide. The left part of the window will normally contain a textual label. The right part is used to display a string representing a (signed) numeric value or as input field where input characters get echoed (in addition to being stored in some data buffer owned by the object).


[29.3]

Figure 29.3 NumberItem and EditText Windows.

NumberItem
The class declaration for NumberItem is:
class NumberItem : public Window {
public:
	NumberItem(int x, int y, int width, char *label,
				long initval = 0);
	void	SetVal(long newVal);
	long	GetVal() { return fVal; }
private:
	void	SetLabel(int s, char*);
	void	ShowValue();
	long	fVal;
	int	fLabelWidth;
};

In addition to the character arrays and dimension data that a NumberItem object already has because it is a kind of Window, a NumberItem owns a long integer holding the value to be displayed (and, also, an integer to record the number of characters used by the label so that numeric outputs don't overwrite the label). What does a NumberItem do?

The constructor for class NumberItem completes the normal initialization processes of class Window. The auxiliary private member function SetLabel() is used to copy the given label string into the background array. The inherited PrepareContent() function loads the current array from the background and adds the frame. Finally, using the auxiliary ShowValue() function, the initial number is converted into characters that are added to the current image array.

Once constructed, a NumberItem can be used by the program. Usually, usage will be restricted to just three functions - GetVal() (return fVal;), SetVal() (changes fVal and uses ShowValue() to update the current image array), and ShowAll() (the function, inherited from class Window, that gets the window displayed).

EditText

The primary responsibility of an EditText object is getting character input from the user. In the dungeon game program, individual input characters are required as command characters. More generally, the input could be a multicharacter word or a complete text phrase.

An EditText object should be asked to get an input. It should be responsible for getting characters from the WindowRep object (while moving the cursor around to try to get the echoed characters to appear at a suitable point on the screen). Input characters should be added to a buffer maintained by the EditText object. This input process should terminate when either a specified number of characters has been received or a recognizably distinct terminating character (e.g. 'tab', 'enter') is input. (The dungeon program can use such a more generalized EditText object by specifying that the input operation is to terminate when a single character has been entered). Often, the calling program will need to know what character terminated the input (or whether it was terminated by a character limit being reached). The input routine can return the terminating character (a '\0' could be returned to indicate that a character count limit was reached).

The EditText class would have to provide an access function that lets a caller read the characters in its buffer.

The class declaration for class EditText is:

class EditText: public Window {
public:
	EditText(int x, int y, int width, char *label, short size);
	void	SetVal(char*);
	char	*GetVal() { return fBuf; }
	char	GetInput();
private:
	void	SetLabel(int s, char*);
	void	ShowValue();
	int	fLabelWidth;
	char	fBuf[256];
	int	fSize;
	int	fEntry;
};

In addition to the data members inherited from class Window, a EditText owns a (large) character buffer that can be used to store the input string, integers to record the number of characters entered so far and the limit number. Like the NumberItem, an EditText will also need a record of the width of its label so that the input field and the label can be kept from overlapping. What does a NumberItem do?

The constructor for class EditText completes the normal initialization processes of class Window. The auxiliary private member function SetLabel() is used to copy the given label string into the background array. The inherited PrepareContent() function loads the current array from the background and adds the frame. The buffer, fBuf, can be "cleared" (by setting fBuf[0] to '\0')..

The only member functions used in most programs would be GetInput(), GetVal() and ShowAll(). Sometimes, a program might want to set an initial text string (e.g. a prompt) in the editable field (function SetVal()).


29.2.3 DungeonItem hierarchy

Class Monster is meant to be an abstraction; the real inhabitants of the dungeon are instances of specialized subclasses of class Monster.

Class Monster has to provide the following functions (there may be others functions, and the work done in these functions may get expanded later, this list represents an initial guess):

The example implementation has three specializations: Ghost, Patrol, and Wanderer. These classes redefine member functions from class Monster as needed.

A Ghost is a Monster that:

Class Ghost needs to redefine only the Advance() and CanDetect() functions. Since a Ghost does not require any additional data it does not to change the Read() function.

A Patrol is a Monster that:

The patrol route should be defined as a sequence of points. These will have to be read from the input file and so class Patrol will need to extend the Monster:: Read() function. The Patrol::Read() function should check that the given points are adjacent and that all are accessible (within the bounds of the dungeon and not blocked by walls). Class Patrol will need to define extra data members to hold the route data. It will need an array of Pt objects (this can be a fixed sized array with some reasonable maximum length for a patrol route), an integer specifying the number of points in the actual route, an integer (index value) specifying which Pt in the array the Patrol is currently at, and another integer to define the direction that the Patrol is walking. (The starting point given for the Patrol will be the first element of the array. Its initial moves will cause it to move to successive elements of the Pt array; when it reaches the last, it can retrace its path by having the index decrease through the array.)

Wanderer is a Monster that:

A Wanderer will need to remember its current direction of movement so that it can keep trying to go in the same direction. Integer data members, representing the current delta-x, delta-y changes of coordinate, could be used. Commonalities between class Player and class Monster

There are similarities between the Monster and Player classes. Both classes define things that have a Pt coordinate, a health attribute and a strength attribute. There are similarities in behaviours: both the Player and the Monsters read initial data from file, get told that they have been hit, get asked whether they are still alive, get told to draw themselves (and erase themselves), have a "move" behaviour that involves erasing their current display, changing their Pt coordinate and then redrawing themselves. These commonalities are sufficient to make it worth defining a new abstraction, "active item", that subsumes both the Player and the Monsters.

This process of abstracting out commonalities can be repeated. There are similarities between class Collectable and the new class ActiveItem. Both are things with Pt coordinates, draw and erase behaviours; they respond to queries about where they are (returning their Pt coordinate). These common behaviours can be defined in a base class: DungeonItem.

The DungeonItem class hierarchy used in the implementation is shown in Figure 29.4.
[29.4]

Figure 29.4 DungeonItem class hierarchy.



29.2.3 Finalising the classes

Completion of the design stage involves coming up with the class declarations of all the classes, possibly diagramming some of the more complex patterns of interaction among instances of different classes, and developing algorithms for any complicated functions.

Class Dungeon

The finalised declaration for class Dungeon is: 

class Dungeon {
public:
	Dungeon();
	~Dungeon();
	void	Load(const char filename[]);
	int	Run();
	int	Accessible(Pt p) const;
	Window	*Display();
	Player	*Human();
	
	int	ValidPoint(Pt p) const;
	
	Monster *M_at_Pt(Pt p);
	Collectable *PI_at_Pt(Pt p);
	void	RemoveProp(Collectable *pi);
	void	RemoveM(Monster *m);
	
	int	ClearLineOfSight(Pt p1, Pt p2, int max, 
			Pt path[]);
	
private:
	int	ClearRow(Pt p1, Pt p2, int max, Pt path[]);
	int	ClearColumn(Pt p1, Pt p2, int max, Pt path[]);
	int	ClearSemiVertical(Pt p1, Pt p2, int max, 
				Pt path[]);
	int	ClearSemiHorizontal(Pt p1, Pt p2, int max, 
				Pt path[]);
	void	LoadMap(ifstream& in);
	void	PopulateDungeon(ifstream& in);
	void	CreateWindow();
	
	DynamicArray	fProps;
	DynamicArray	fInhabitants;
	Player		*fPlayer;
	
	char		fDRep[MAXHEIGHT][MAXWIDTH];
	Window		*fDWindow;
	int		fHeight;
	int		fWidth;
};

The Dungeon object owns the map of the maze (represented by its data elements fDRep[][], fHeight, and fWidth). It also owns the main map window (fDWindow), the Player object (fPlayer) and the collections of Monsters and Collectables. Data members that are instances of class DynamicArray are used for the collections (fInhabitants for the Monsters, fProps for the Collectables).

The Load() and Run() functions are used by the main program. Function Load() makes uses of the auxiliary private member functions LoadMap() and PopulateDungeon(); these read the various data and create Monster, Collectable, and Player object(s) as specified by the input. The auxiliary private member function CreateWindow() is called from Run(); it creates the main window used for the map and sets its background from information in the map.

Access functions like Display() and Human() allow other objects to get pointers to the main window and the Player object. The ActiveItem objects that move are going to need access to the main Window so as to tell it to clear and set the character that is to appear at a particular point.

The ValidPoint() function checks whether a given Pt is within the bounds of the maze and is not a "wall".

The functions M_at_Pt() and PI_at_Pt() involve searches through the collections of Monsters and Collectables respectively. These function return the first member of the collection present at a Pt (or NULL if there are no objects at that Pt). The Remove... function eliminate members of the collections.

Class Dungeon has been given responsibility for checking whether a "clear line of sight" exists between two Pts (this function is called in both Wanderer:: CanDetect() and Patrol::CanDetect()). The function takes as arguments the two points, a maximum range and a Pt array in which to return the Pts along the line of sight. Its implementation uses the auxiliary private member functions ClearRow() etc.

The algorithm for the ClearLineOfSight() function is the most complex in the program. There are two easy cases; these occur when the two points are in the same row or the same column. In such cases, it is sufficient to check each point from start to end (or out to a specified maximum) making certain that the line of sight is not blocked by a wall. Pseudo code for the ClearRow() function is:

Dungeon::ClearRow(Pt p1, Pt p2, int max, Pt path[])
	delta = if p1 left of p2 then 1 else -1
	current point = p1
	for i < max do 
		current point's x  += delta;
		if(current point is not accessible) return fail
		path[i] = current point;
		if(current point equal p2) return success
		i++
	return fail

Cases where the line is oblique are a bit more difficult. It is necessary to check the squares on the map (or screen) that would be traversed by the best approximation to a straight line between the points. There is a standard approach to solving this problem; Figure 29.5 illustrates the principle.
[29.5]

Figure 29.5 A digitized line.

The squares shown by dotted lines represent the character grid of the map or screen; they are centred on points defined by integer coordinates. The start point and end point are defined by integer coordinates. The real line between the points has to be approximated by a sequence of segments joining points defined by integer coordinates. These points define which grid squares are involved. In Figure 29.5 the squares traversed are highlighted by ¥ marks.

The algorithm has to chose the best sequence of integer points, for example choosing point (2, 1) rather than (2, 2) and (8, 4) rather than (8, 3) or (8, 5). The algorithm works by calculating the error associated with different points (shown by the vertical lines in Figure 29.5). The correct y value for say x=8 can be calculated; the errors of taking y = 3, or 4, or 5 are easy to calculate and the best approximation is chosen. When the squares traversed have been identified, they can be checked to determine that they are not blocked by walls and, if clear, added to the path array. The algorithm is easiest to implement using two separate versions for the cases where the change in x is larger or the change in y is larger. A pseudo-code outline for the algorithm for where the change in x is larger is as follows:

Dungeon::ClearSemiHorizontal(Pt p1, Pt p2, int max,
	 Pt path[])
	ychange = difference in y values of two points
	xchange = difference in x values of two points
	if(xchange > max)
		return fail
	
	deltax = if x increasing then 1 else -1
	deltay = if y increasing then 1 else -1
	
	slope = change in y divided by change in x
	error = slope*deltax
	
	current point = p1
	for i < abs(xchange) do
		if(error*deltay>0.5)
			current point y += deltay
			error -= deltay
		
		error += slope*deltax
		current point x += deltax
		if(current point not accessible) return fail

		path[i] = current point
		if(current point equal p2) return success
		i++
	return fail
Class Pt

It is worth introducing a simple class to represent coordinates because many of the functions need coordinates as arguments, and there are also several places in the code where it is necessary to compare the coordinates of different objects. A declaration for class Pt is:

class Pt {
public:
	Pt(int x = 0, int y = 0);
	int 	X() const;
	int	Y()	const;
	void	SetPt(int newx, int newy);
	void	SetPt(const Pt& other);
	int	Equals(const Pt& other) const;
	int	Adjacent(const Pt& other) const;
	int	Distance(const Pt& other) const;
private:
	int	fx;
	int	fy;
};
Most of the member functions of Pt are sufficiently simple that they can be defined as inline functions.
Classes WindowRep and Window

The declaration for class WindowRep is

class WindowRep {
public:
	static WindowRep *Instance();
	void	CloseDown();
	void	PutCharacter(char ch, int x, int y);
	void	Clear();
	void	Delay(int seconds) const;
	char	GetChar();
	void	MoveCursor(int x, int y);
private:
	WindowRep();
	void	Initialize();
	void 	PutCharacter(char ch);
	static WindowRep *sWindowRep;
	char	fImage[CG_HEIGHT][CG_WIDTH];
};

The size of the image array is defined by constants CG_HEIGHT and CG_WIDTH (their values are determined by the area of the cursor addressable screen, typically up to 24 high, 80 wide).

The static member function Instance(), and the static variable sWindowRep are used in the implementation of the "singleton" pattern as explained in the implementation section. Another characteristic of the singleton nature is the fact that the constructor is private; a WindowRep object can only get created via the public Instance() function.

Most of the members of class Window have already been explained. The actual class declaration is:

class Window {
public:
	Window(int x, int y, int width, int height, 
		char bkgd = ' ', int framed = 1);
	virtual	~Window();
	void 	Clear(int x, int y);
	void	Set(int x, int y, char ch);
	void	SetBkgd(int x, int y, char ch);
	int	X() const;
	int	Y() const;
	int	Width() const;
	int	Height() const;
	
	void	ShowAll() const;
	void	ShowContent() const;
	void	PrepareContent();
protected:
	void	Change(int x, int y, char ch);
	int	Valid(int x, int y) const;
	char	Get(int x, int y, char **img) const;
	void	SetFrame();
	char	**fBkgd;
	char	**fCurrentImg;
	int	fX;
	int	fY;
	int	fWidth;
	int	fHeight;
	int	fFramed;
};

The declarations for the specialized subclasses of class Window were given earlier.

DungeonItem class hierarchy

The base class for the hierarchy defines a DungeonItem as something that can read its data from an input stream, can draw and erase itself, and can say where it is. It owns a link to the Dungeon object, its Pt coordinate and a symbol.

class DungeonItem {
public:
	DungeonItem(Dungeon *d, char sym);
	virtual ~DungeonItem();
	Pt		Where() const;
	virtual void	Draw();
	virtual void	Read(ifstream& in);
	virtual void	Erase();
protected:
	Dungeon 	*fD;
	Pt		fPos;
	char		fSym;
};

Since class DungeonItem is the base class in a hierarchy, it provides a virtual destructor and makes its data members protected (allowing access by subclasses).

A Collectable object is just a DungeonItem with three extra integer data members and associated access functions that can return their values. Because a Collectable needs to read the values of its extra data members, the class redefines the DungeonItem read function.

class Collectable : public DungeonItem {
public:
	Collectable(Dungeon* d, char sym);
	int		Hlth();
	int		Wlth();
	int		Manna();
	virtual void	Read(ifstream& in);
private:
	int		fHval;
	int		fWval;
	int		fMval;
};

An ActiveItem is a DungeonItem that gets hit, gets asked if is alive, moves, and runs. Member function Run() is pure virtual, it has to be redefined in subclasses (because the "run" behaviours of subclasses Player and Monster are quite different). Default definitions can be provided for the other member functions. All ActiveItem objects have "strength" and "health" attributes. The inherited DungeonItem::Read() function will have to be extended to read these extra data.

class ActiveItem : public DungeonItem {
public:
	ActiveItem(Dungeon *d, char sym);
	virtual void	Read(ifstream& in);
	virtual void	Run() = 0;
	virtual void	GetHit(int damage);
	virtual int	Alive() const;
protected:
	virtual void	Move(const Pt& newpoint);
	Pt	Step(int dir);
	int	fHealth;
	int	fStrength;
};
(Function Step() got added during implementation. It returns the coordinate of the adjacent point as defined by the dir parameter; 7 => north west neighbor, 8 => north neighbor etc.)

A Player is a specialized ActiveItem. The class has one extra public member function, ShowStatus(), and several additional private member functions that are used in the implementation of its definition of Run(). A Player has extra data members for its wealth and manna attributes, a move counter that gets used when updating health and manna. The Player object owns the NumberItem and EditText windows that are used to display its status and get input commands.

class Player : public ActiveItem {
public:
	Player(Dungeon* d);
	virtual void	Run();
	virtual void	Read(ifstream& in);
	void	ShowStatus();
private:
	void	TryMove(int newx, int newy);
	void	Attack(Monster *m);
	void	Take(Collectable *pi);
	void	UpdateState();
	char	GetUserCommand();
	void	PerformMovementCommand(char ch);
	void	PerformMagicCommand(char ch);
	
	int		fMoveCount;
	int		fWealth;
	int		fManna;
	NumberItem	*fWinH;
	NumberItem	*fWinW;
	NumberItem	*fWinM;
	EditText	*fWinE;
};

Class Monster is just an ActiveItem with a specific implementation of Run() that involves the extra auxiliary functions CanAttack() etc. Since instances of specialized subclasses are going to be accessed via Monster* pointers, and there will be code of the form Monster *m; ... ; delete m;, the class should define a virtual destructor.

class Monster : public ActiveItem {
public:
	Monster(Dungeon* d, char sym);
	virtual ~Monster();
	virtual void	Run();
protected:
	virtual int CanAttack();
	virtual void Attack();
	virtual int CanDetect();
	virtual void Advance();
	virtual void NormalMove() { }
};

Class Ghost defines the simplest specialization of class Monster. It has no extra data members. It just redefines the default (do nothing) CanDetect() and Advance() member functions.

class Ghost : public Monster {
public:
	Ghost(Dungeon *d);
protected:
	virtual int CanDetect();
	virtual void Advance();
};

The other two specialized subclasses of Monster have additional data members. In the case of class Patrol, these must be initialized from input so the Read() function is redefined. Both classes redefine Normal Move() as well as CanDetect() and Advance().

class Wanderer : public Monster {
public:
	Wanderer(Dungeon *d);
protected:
	virtual void	NormalMove();
	virtual int CanDetect();
	virtual void Advance();
	int	fLastX, fLastY;
	Pt	fPath[20];
};

class Patrol : public Monster {
public:
	Patrol(Dungeon *d);
	virtual void	Read(ifstream& in);
protected:
	virtual void	NormalMove();
	virtual int CanDetect();
	virtual void Advance();
	Pt	fPath[20];
	Pt	fRoute[100];
	int	fRouteLen;
	int	fNdx, fDelta;
};
Object Interactions

Figure 29.6 illustrates some of the interactions involved among different objects during a cycle of Dungeon::Run().
[29.6]

Figure 29.6 Some of the object interactions in Dungeon::Run.

The diagram illustrates aspects of the loop where each Monster object in the fInhabitants collection is given a chance to run. The Dungeon object will first interact with the DynamicArray fInhabitants to get a pointer to a particular Monster. This will then be told to run; its Run() function would call its CanAttack() function.

In CanAttack(), the Monster would have to get details of the Player object's position. This would involve first a call to member function Human() of the Dungeon object to get a pointer, and then a call to Where() of the Player object.

The diagram in Figure 29.7 illustrates the case where the Player is adjacent and the Monster object's Attack() function is called. This will again involve a call to Dungeon::Human(), and then a call to the GetHit() function of the Player object.

Figure 29.7 illustrates some of the interactions that might occur when the a movement command is given to Player:Run().
[29.7]

Figure 29.7 Object interactions during Player::Run.

The Player object would have had to start by asking its EditText window to get input. When EditText::GetInput() returns, the Player object could inspect the character string entered (a call to the EditText's GetVal() function, not shown in diagram). If the character entered was a digit, the Player object's function PerformMovementCommand would be invoked. This would use Step() to determine the coordinates of the adjacent Pt where the Player object was to move. The Player would have to interact with the Dungeon object to check whether the destination point was occupied by a Monster (or a Collectable).

The diagram in Figure 29.7 illustrates the case where there is an adjacent Monster. The Player object informs the Monster that it has been hit. Then it checks whether the Monster is still alive. In the illustration, the Monster object has been destroyed, so the Player must again interact with the Dungeon object. This removes the Monster from the fInhabitants list (interaction with the DynamicArray is not shown) and deletes the Monster.


Implementation details in second part.
Last modified March 1996. Please email questions to nabg@cs.uow.edu.au