Movement possibilities

I was going to discuss the possibilities for keeping track of the possible moves of objects. Sometimes it may be easier to do this than to refigure them from the beginning. But which involves more overhead in time, memory, and programming requirements does not appear to be clear in advance. This is something I would have to experiment with.

I also wanted to mention the possibilities, when there is more than one actor in a given time step, which one moves or acts first. In two player games, these tend to alternate. It is often possible to have more than one duration of time; with some events taking place in a short period, and others in a longer period. In a chess game, this might be Move 1 white, Move 1 black. Other variants are also possible.

At this point, there are several topics I would like to discuss, but don't have time for everything. Among the more immediate possibilitys are compound objects, movement rates, and limited life.

Object Interactions

I mentioned before the possibility of having two objects occupy the same space, and that, at least for now, I'm not permitting it. However, when object attempts to move onto the space occupied by another, or when two objects are adjacent, it is possible for these two objects to interact. For instance, there is the capture of an opponent in chess, picking up an item, landing on a trap or colliding with a monster, in adventur-type games. There are any number of rules that describe what happens when objects interact, and in a virtual world, action at a distance is also allowed. Typical examples include when one or both change their state or properties, and when one or both is destroyed, or even when one is created. An important type of interaction is the collision. I'll deal with this in more detail later, but wanted to mention it along with other types of interactions.

Actors

Before I go much more deeply into the mechanics of world-building, I'd like to consider another element that goes into games and worlds. As I will use it, an "actor" is someone or something that is capable of originating an event. Players are considered actors. Single-player games and solitary worlds can be interesting, but games involving two or more actors are considered more so. These actors typically represent animals (such as monsters), or people. Usually, one or more of the actors is controlled by the computer and there is a set of rules determining when or how each of them acts. Some are intelligent, some not so; some have complicted behavior, others are quite simple.
The simplest form of action is autonomous: every time step, actor a (does action_1). The next is conditional: If (somecondition_1) then actor a (does something_2). More complicated conditions and more complicated actions begin to go into the subject of artificial intelligence, which I'm going to dodge for now.

Of the games I've mentioneed,

Single actor games: Pong, Lunar Lander;
Two actor games: Tic-tac-toe; Spacewar; Baseball;
Multiple actor games: Oregon Trail, Star Trek, dnd, and Dungeon.

In the history of games, I've reached 1976. Video games included Breakout, probably inspired by PONG, and Night Driver. ADVENT, sometimes called Adventure, sometimes called Colossal Cave, was the progenitor of a whole series of interactive fiction or text-adventure games.
Also in 1976, Creative Computing magazine began publication, and for a few years published a series of "The Best of Creative Computing", which include even more samples of computer games.
For the past few days, I've been reworking a classification of the games published in BASIC Computer games, (see the sidebar). All these give me enough of a variety that I'm going to set history aside and take a closer look at the different farieties, since some of them will be more closely connected to my purposes than others.

Distance

One of the basic quantities that's needed to work with a virtual world is some notion of the distance between two points. There are two principal variants on this. One of them ix the usual Euclidean distance, D = sqrt((x2 - x1)*(x2 - x1)+ (y2 - y1)*(y2 - y1)). Another one is called the Manhattan, taxicab, or city-block distance; D = abs(x2 - x1) + abs(y2 - y1). There are various others possible, but these are reserved for more advanced work.

Pushing the historical studies of games for a moment, I find the history continuing in 1975, with another, apparently independently developed game called Dungeon, written by Don Daglow. I find that he was also the author of Baseball, which I mentioned and passed over earlier.

Structure of space

The structure of space has to do with which points are considered adjacent or neighboring. In a square plane space, any point has 4 or 8 immediately adjacent points, depending on whether the diagonals are considered adjacent. But other structures are possible. Many games choose to employ a "Wrapping" mode, in which points at the boundaries are considered to be adjacent to those at the opposing boundary. In others, the rows or columns are offset slightly so that a point is surrounded by six others. These are typically used in maps that use hexagons rather than squares. Still others, such as Hunt the Wumpus, use a finite space in which each point, or location is numbered, and described as "adjacent to" three specified others. In the original version, these were the vertices of a dodecahedron, but any number of other spaces can be constructued and have been.

Continuing with my historical look, in 1972, PONG came out as an arcade game, and was quickly copied for computers. A couple of versions of Star Trek were also developed, and Hunt the Wumpus was written. In 1973, a game called Lunar Lander was also written for the DEC 10, but a verson without the graphics display can also be found. Although only a few of these games are mentioned in the Wikipedia history, that same year David Ahl came out with 101 BASIC Computer Games, which is a sampling of what had been written and could be found on various systems around this time. I intend to use this, or rather the 1978 version, for some source material, but hope to move beyond it. Of the games I've mentioned so far, only a version of Star Trek and Lunar Lander are found here.
In 1974, Daniel Lawrence wrote the first of the computer adventure RPG games, dnd, based on Dungeons & Dragons, which is considered the grandaddy of role-playing games. Some of its descendants are a bit easier to study, so I will consider them later.

Movement

Although there are some games and some virtual worlds where change takes place without movement, worlds become much more interesting when there is movement.
A movement is an event, in which the position of an object is changed, and is usually described by the initial position, final position, object moved, and time.

This suggests a new property for objects in addition to being removable or destructible, and non-removable or permanent. They may be either fixed or movable.

The possibilities for movement of objects also need to be considered and limited. it should not be possible to move objects outside the space, which brings up behavior at boundaries. Permanent, nonmovable object may be treated as boundaries and barriers and in effect create irregularly-shaped spaces. Whether movement is connnected (one location to an adjacent) or may take place in jumps also needs to be considered. Interactions between obects also may occur.

I've fallen behind on my design of a program that illustrates these principles I am outlining. The addition of movement makes it possible to consider games such as checkers or chess. There are several ideas I would like to explore further, including rate of movement, connectedness of space, relations among objects, and I'm not quite sure which ones I want to explore next.

As I mentioned at the beginning, this blog is not solely intended for game-playing. There are elements of scientific simulation and education involved. I believe that games should not be purely entertaining, but ought to include an element of education, and the more elements of reality a game can successfully incorporate, the better its educational vaue. Nevertheless, there is a great deal that can be learned about the creation of virtual worlds from games and game programming, so for a time, these will be a major source. I'm going to follow the history of computer games as discussed in Wikipedia, in the hope that I can borrow the best elements from old-style games into the virtual worlds I am constructing. I can't hope to compete directly with major companies that can pour hundreds of designers, artists, and programmers into MMORPGs
(Massive Multiplayer Online Role-Playing Games), so I'm not going to try...but there are some good ideas that they have overlooked.

With that in mind, I'm going to start small, with a variety of tic-tac-toe such as
OXO, first done in 1952. I'm going to skip over Tennis for Two (1958) and Spacewar (1962) for now, although I may come back to them later. Starting in 1971, there were new computer games every year. I have little interest in Baseball, either the real-life version or the computer version. Rather more to my taste are Oregon Trail and Star Trek I was playing this on the computer lab in high school around 1973. As part of my self-education in C programming, I managed to ported a later version of Star Trek from BASIC to C, sometime around 1992.

Events

Events are changes in the virtual world. They are generally associated with a time, a place, objects, and may be of several kinds. Not all events need to be noted, but for tracking purposes or reconstruction purposes, it may be useful to follow them.

Possible attributes of an object might be removable, and non-removable.
The addition and creation of objects, changes in their properties, and changes in the properties of space are some of the possible events. These are simple events, but more complex events involving multiple objects, attributes, positions, and times are also possible. For now, I want to keep them simple.

With the elements so far considered, it's possible to consider part of a game of tic-tac-to, with Xs and Os as non-removable objects. I haven't yet considered turn-taking victory conditions, or strategies of play, but it's possible to construct the mechanics of play in at least a crude form. There are a few others of this type. Most interessting games and universes, though, require the next feature I want to consider...movement.

I've been looking at the history of computer games, and when I have more time, I'd like to consider some of these as adding important elements to the possibilities of
Virtual World Building.

Object types

When objects are represented as classes, there are at least two ways to represent different kinds of objects. The easier one is to simply specify a data member that is different; for instance, color = BLACK, or color = WHITE, which serves to distinguish black pieces from white pieces. The other is when there is something about the structure or constraints about the object is different.

I decided to consolidate and rewrite my code a little to account for the various added concepts. I'm not including it here, but so far I've considered:

Space. This contains a number of cells or points, and a number of objects. I've flip-flopped on whether or not to explicitly include the points, and I've decided for now to include them.

Points. I'm using an aray to represent these. So far, these consist of a generic atribute and a pointer. This pointer points to the object that is in them. If I ever have multiple objects at the same point, I could make this a list of objects.

Particles. I'm including these in a list. Each has a position and one other attribute that I can make generic. Since the number of particles in space is rather arbitrary, I'm going to make a linked list, with add and remove operations.

Position: This is a number, pair of numbers, or triple of numbers depending on the definition of the space: for now, I'm making it a pair. The position of a point is implicit (It's related to space), but the position of an object is given as part of its data. It should be obvious that these must match: If I specify a location for a point in space, and there is a particle at that point, then the position given for the particle has to correspond to that point.

Position Coordinate. I've thought about making this an abstract class, because I want to include bounds-checking here. The coordinates must't be located outside the space, and there is no reason the bounds on the x-coordinate have to be the same as those on the y-coordinate.

Time. This works as a simple unsigned (positive) variable, so far.

Back when I was in school studying computer programming, I started but didn't finish a course on Windows programming. I did some study of it on my own, but I'm blurry on some of the technical details. I may include some of my observations on what I find here.
Input and display of positions, space properties, and object types is an important subject I can't ignore forever, but can push to the background for now. The next subject I want to consider is events.

Objects.

As I've said before, an empty universe isn't very interesting. There needs to be some kind of object or objects in it. Since "object" is such a generic term, I'm going to start with a simple one with only one property; it's position.

class Particle
{
private:
int x_pos;
int y_pos;
public:
Particle(int x, int y);
set_position(int x, int y);
};

This can be related to other topics already discussed.
I haven't considered the possibility that space itself may be expanding or contracting. It's an interesting notion that I will have to set aside.
I also haven't considered the possibility of considering parts of space versus the while of space, but will gave to set this aside.
If particles positions or other properties do not change with time, they may form a static, unchanging universe. Most generally, it is useful to have some objects that are static, and some that can move, but motion will be discussed later.
It's necessary to consider whether a particle is actually in the space. In placing or moving it, the position has to be within the range of possibilities for the space.
For now, I am limiting the consideration to particles that have only one position. The larger the space, the more particle-like a body will seem. Extended bodies will be considered later.
Also, for now, I am adopting a rule of exclusion: Only one particle may occupy a given position at a time. There is the possibility of having overlapping bodies, but this is another topic that has to be set aside.
For now, I am considering whether particles can be created or destroyed; added to or removed from a space. If they can, the space represents an "open" world; if not, it represents a "closed" world. Most games include, at least implicitly, open worlds.
I can also consider whether the universe is "full" or "empty". For a finite universe with non-overlapping objects, there are no more objects possible than members of the space. If they can overlap, there is no upper limit to the number of objects.

This gives rise to the question of whan and how objects are placed in this artificial world. Establishing an initial configuration of objects that cannot be moved within a game or simulation is a very common procedure and is typically done by a separate editor program. This is typically done in order to set up a "map" of space
In order to add, or remove objects, it is necessary to have some means of specifying the position, and if the objects do not overlap, whether there is something already in a desired position, plus what happens if there is something in a desired position.
For simple spaces, it can be useful to describe each point in space, whether or not it is empty, and perhaps which object is there. For larger spaces, this becomes impractical and it becomes more useful to maintain a list of objects and their positions. This may require techniques for handling lists of unspecified length, and to determine whether a given position is empty or not may require processing the list of objects, the "map" of space, or sometimes both.
All this requires a little more programming than I have done so far, and still not produced anything useful. But at least a non-empty universe is more interesting.

Space Properties

I've indicated that a cell is the basic unit of space. For very small spaces, this is appropriate terminology, but as the size of the space, or number of cells increases, individual cells behave more and more like geometric points, so I may also refer to points in space. It's not possible, given a finite number of points, to fully represent geometric continuity, which includes among other principles that between any two points there is another. But it is possible to come close.

It's often appropriate to give each point of space some kind of property. One example might be a checkerboard space, and each point has the property "Red" or "Black" which has the properties "red" or "black". Physical spaces may have properties such as "electric field" or "magnetic field". Any number of variants can be considered, but the most common pair of properties is "empty" and "occupied".

A space may be completely empty, but thse aren't usually very interesting. Spaces with objects are more interesting. But before I go into these, I want to consider how to set up a space.

In Object-Oriented Programming, the universe, or space, can be represented by a class. In C++, an appropriate declaration for the universe I have so far described might be:

const int EMPTY = 0;

class Space
{
private:
int cell [Y_MAX][X_MAX];
public:
int x, y;

Space();
void display();
};

This defines the space to be an array of integers. I've chosen to make the array itself inaccessible from outside the class, but the coordinates of a given cell are accessible. There are two member functions, the constructor, which sets up the space, and a display function.

These functions would implimented as:

Space::Space()
{
for (y=0; y <= Y_MAX; 1)
{for (x=0; x <= X_MAX; 1)
{cell = EMPTY;}
}
}

The display function would be as described earlier; but containing a line something like:
if (cell[x][y]== EMPTY)
[print (" ")];
or whatever function you are using for display, and however you want to represent empty space.

So, now going back to the program mentioned earlier, in the initialization where time is set to 0, you would include the line:

Space game();

At this point in the program the constructor is called and the space set up as empty. This is the only time the constructor is called. Then, in the time loop, where I have [other stuff], it's now possible to say:
game.display();
and now, the program repeatedly shows empty space.

I may have omitted a few technical details, but these depend on the particular compiler and operating system that are being used. Next time, I'll discuss putting something in space.

Position

It's easy to represent a one-dimensional space on a computer screen: Simply begin at the beginning and show the cells in the space one at a time, left to right.
It can be a bit trickier for a beginner to represent a two-dimensional space. The usual convention is to represent a position with a pair of numbers, each one called a coordinate. The starting point, the origin, is usually given the coordinates (0,0). In mathematics, the convention is that the first number, X, gives the distance going horizontally from left to right, while the second number, Y, gives the distance going from bottom to top.
The way arrays are represented in computers and on the screen are different.
In this case, the first number usually represents the row, and the second, the column, and numbering increases from top to bottom.

However, it's easy to interconvert these representations.
Calling your space coordinates (X, Y), and the corresponding screen coordinates, SCR_X and SCR_Y, the proper equations are:

SCR_X = Y;
SCR_Y = X_MAX - X;

This is a special case of what is called a coordinate transformation.

For beginning and simple cases, without going into graphics programming, it's possible to go back to the origins of computer graphics and use text characterers to represent the cells of a small space.

A simple routine to display a simple space wmight then be:

for (scr_x = 0; scr_x <= X_MAX; 1)
{
y = scr_x;
for (scr_y = 0; scr_y <= Y_MAX; 1)
{
x = X_MAX - scr_y;
display_cell (x, y);
}
begin new line;
}

But so far, I have only talked about space and time. I haven't talked about either the properties or contents of space.

At the beginning

I'm used to seeing titles on my blog posts. but this time I'm not getting them. Anyway...
The next part that's needed is some kind of space for things and events in the virtual world. Like time, space in a virtual world has to be finite and bounded, and discrete, rather than continuous. A computer can only handle a finite number of divisions. I'm going to call a unit of space a space cell.

While time requires only one number to describe it, space may require one, two, or three. One dimensional spaces, or linear spaces, aren't very interesting, except for introducing elementary concepts; such as the boundaries: X_MIN and X_MAX might as well be names their names. It's typical and conventient to set X_MIN as zero, but there is no particular reason it can't be some positive or negative whole number. The number of cells in the space is one more than the difference X_MAX - X_MIN, a common source of programming errors.

A two-dimensional space is more interesting. Here there are two coordinates, X and Y, and as well as X_MIN and X_MAX, the boundaries would be Y_MIN and Y_MAX. The size of the space would have to be the x-size times the y-size.
One of the simplext common games, tic-tac-toe, can be said to take place in a 3x3 space. Most more complicated and more interesting games, of course, take place in larger spaces.

A three-dimensional space is even more interesting, but these are much more difficult to represent on a computer screen. Various methods of representing them are possible, but I'm going to have to leave this as a more advanced topic.

Even higher dimensional spaces can be described mathematically, but I can only point to these as a direction of further research.

It's typical, but not always necessaty, to set up space as an array of some kind, and give each cell some kind of attribute. There's not much point to doing that if space is empty, or there is nothing in it, but before I discuss what is in space or what it is like, I want to discuss position.

Virtual World Building is the subject of building computer models or simulations of the world. This is on the border between serious scientific modeling and the simulated environments of games. It's intended to be educational and exploratory.

I've been an avid reader of science fiction and fantasy, a player of computer games and a little bit role-playing, and have some education in the sciences, mathematics, and computer programming, and a taste for individuality as well as improving on different things. What this qualifies me to do is not clear, but world-building and simulation are some of my passions, and so I hope to open a discussion of some of the techniques.

I'm assuming readers have an elementary knowledge of C/C++ computer programming, but since my computer and programming manuals are in storage some distance away, I can't easily check my work or try techniques. Suggestions and corrections are invited.


To begin with, a virtual world needs time. Simulations do not have the luxury of being open-ended; they need a beginning and an end of some kind. It's probably not possible to make time pass continuously as in the real world. What can be done is to divide it into arbitararily small increments, to create the illusion of continuity. Due to motion pictures and animation, this may be an obvious and trivial idea, but it's fundamental enough that I will be coming back to it time and again.

A practical problem is determining the appropriate size of step. Something that is appropriate for modeling nuclear reactions is going to proceed far slower than the reactions themselves, and trying to model the development of the universe on this scale will take longer than the expected lifetime of the universe. On the other hand, if the time step is too long, so many changes take place within it that it will proceed in an extremely jerky fashion. The choice of an appropriate time scale has to be refined by experience.

A minimal C/C++ program is:

const int FIRST = 0; // Typically time begins at 0
const int LAST = ???;
const int TIMESTEPSIZE = 1;
bool the_end = FALSE;
int time = FIRST;

while (!theend)
{
[other stuff]

time += TIME_STEP_SIZE;
if (time >= LAST)
the_end = TRUE;
}

The "other stuff" may include processing of an event generated by a computer timer, or a user input, and it may include an output to indicate that indeed time is passing.
Variants on this include a timeless world (there needs to be some other way to set the_end true); an open-ended one (likewise, there needs to be some way to set the_end true, and the time variable may overflow); and one where time is reset (like the open-ended one).

Next up: Space