EmpireS - Merging Strategy and Tactics

Empire (III) had been in play, with incremental improvements for over a year. During that entire time I felt it was still lacking my original intention, that of simulating a culture in space. The first version was closer to my goal than this tactical shoot-em game; sure, it was fun, but I wanted it to have more.

Overview of Empire S Features:

• A strategic AND tactical game of
• Seven (7) teams plue a rogue team of
• a maximum of fifty ships, one ship per player,
• each shooting torpedoes and phasers
• up to 100 strategic players,
• each commanding a community (planet or starbase)
• in a huge 3D block of sectors (20-bit)
• with a display of varying resolution.

This version had eight teams: Zeroes, Creeps, Rogues, Klingons, Terrans, Phantasites, Zirconians, and Star Children (Age of Aquarius and all that).

I worked on ideas off and on during 1974 and got separate lessons space, -empires- and -tactics-, in which to develop the separate pieces. (I have no idea why I later overwrote Empire III until these were working!)

The idea was to have two separate lessons, one with the tactical interactions of space ships and planets, the other running the interface and engine of the strategic simulation.

A person could take on roles such as Starship Captain, Governor of a planetary system or star base, and others; I was looking for roles that allowed for independence from hierarchy so that one could realistically feel most actions taken were reasonable simulations.

I was considering ways of having a Starship command and had implemented a version of ELIZA with the idea of incorporating it in to the game. One sneaky addition I made to the Eliza interface was a back door, where a person could actually be driving the responses back. There were a bunch of pre-written responses to help make it appear as if response had-to-be from a computer because it was so fast; no one could type that fast!

Problem with the -segment- define and a solution

In the previous section I laid out how the -segment- define really helped increase what could be kept. This is one reason why the complexity of the game could increase with the fixed maximum (and small) amount of memory we had.

There was one BIG problem: it was VERY slow to access (relative to other operations). The reason for the slowness was that it required a division to determine which word to access and divides are slow on ANY computer. An occasional access of an array element is acceptable, but when trying to minimize processing required on a timesharing system in order to make the game playable, a divide can be a big problem.

I tried to optimize all loops by moving access of array elements out of inner loops as much as possible; access only when absolutely needed.

The systems programmers came to realize this and eventually came up with an even better way to slice the pie, the VERTICAL segment. Now the slice was down through an array of words rather than horizontally packing one word with the array elements. Access to a vertical segment array element did not require a divide, since the index pointed directly to the word the value was in. To get to the actual segment within the word just required the circular shift and the mask.

When the vertical segment came out in early 1975 it gave a lot of opportunity to do a lot more than earlier versions.

The first listing I have showing a vertical segment is from a March 24, 1975 Empire listing. It was in this timeframe that I was motivated to really expand the scope of possibilities for Empire.

Help Arrives

It was also about the time of the introduction of the vertical segment that local help showed up.

Gary Fritz started at Iowa State University in the fall quarter of 1974. He discovered PLATO in early 1975. There were two PLATO terminals at the Education building and later two had been installed at the Computer Science building. I stayed mainly at the Education building because it was closer to where I lived and I had a key and permission for 24-hour access.

One day, a tall lanky guy sat down at the terminal next to me. Not many people knew about the those terminals so it was unusual to have others in the room. Gary was very inquisitive and intelligent; it only took me once to explain the programming language, how to find help, and all. We became close friends and collaborators.

One night I had worked quite late and struggled back to my room to sleep. Out of a deep sleep my phone rang with Gary on the other end. Some change I/we had made during that evening was causing a problem; people were complaining. I seldom requested listings during this time frame and continued the habit of having the entire program memorized.

Gary described the problem, somehow without me even getting out of bed and still half asleep, I was able to tell him which blocks of code to go to and which lines and what to change the code to fix the the problem.

We both had a little more hair then.

Another Slice

When the vertical segment came out in early 1975 we did a lot of brainstorming and redesign. All of the arrays were now packed into vertical slices of memory.

 1          segmentv,obvecy=nc(objbase),1,9,s
 2          segmentv,obvecx=nc(objbase),10,9,s
 3          segmentv,obtype=nc(objbase),19,6
 4          segmentv,oby=nc(objbase),25,18,s
 5          segmentv,obx=nc(objbase),43,18,s
    

Here, each word of memory starting at objbase[1] has five different variables stored in it for each index value. These correspond to the object's x,y vector, object type, and x,y position. The ",s" following some indicate that the value is a signed value, so obvecy[x] is a 9-bit signed integer stored starting in bit 1 for 9 bits; obvecx[x] starts in bit 10 for 9 bits and so on.

Finding Our Way

The -findall- command was announced some time in the spring of 1975. I had not spent enough time understanding exactly what it did, but Gary had understood it and was explaining it to me; and he had just started on PLATO earlier in the year.

Think of the -findall- command as a single command entry that internally is a loop.

The object is what you are looking for in the list. -findall- makes a list of all matches by putting the index in an array (the location_list), with the count of the number of matches placed in the zeroeth element of that array. "inc" lets you specify how many entries to skip; default is 1. The "mask" is the most important part of this, in that it lets you specify a binary mask against which to mask the compared element before matching it to the object. (Was that confusing enough?)

    calc	ptr = 0
    calc	ctr = 0
    loop
    while	(ptr < length)
    .	calc	ptr = ptr + 1
    reloop ((list(ptr) $mask$ the_mask) != object)
    .	calc	ctr = ctr + 1
    .	calc	loc_list(ctr) = ptr $$ save the index to found element
    endloop
  

Now realize the power of this. The CDC Cyber (and subsequent Cray machines) can pipeline this entire loop inside the machine language, automatically pipelining in the array elements into the large high-speed buffers. It was FAST; VERY FAST.

Relating -findall- with the object structure in vertical segments shown above, try to make a mask and object such that if scanning down through each word of the object array, a list of ONLY the objects that match (within a variable range) is generated.

AHA!

When Gary explained it to me we had, as he put it recently in an email: "The AHA moment when we practically mind-linked and simultaneously thought up the findall search approach." This was one of those exciting creative times which help make it worthwhile to plow through long days and sleepless nights trying to conjure up the right approach to make Empire work work the best it could in the current environment.

We did replace search loops with -findall-; as an example, we used -findall- to search through the list of signons to see if your name was previously in the list.

The Redesign - Yet Again

Some time during the summer of 1975 we took down Empire III and started working on the 3D version of Empire (which ended up getting called Empire V) and also working on the strategic level game in multiple lessons.

Silas Warner, Gary Michael, Jim Bowery, and Gary Fritz were listed in the online design notes as working on the versions. We equally shared access to the code. This caused some difficulties since there was no such thing as source code control or remote coordination of development. Jim was variously in Iowa City, Iowa, and Chambana. Gary Michael was in Chambana. Silas was at U of Indiana at Bloomington, Indiana. Gary Fritz and I were at Iowa State in Ames, Iowa. Jeff Schramm had done the artwork on 3D line drawings of space ships and was based, if I recall, in Chambana.

With the ability to break down those 90,000 bits into many more meaningful smaller pieces we felt that a 3D space would make sense now. We could pack X, Y, and Z for an object into one 60-bit word with 20-bits that's a pretty big space to fly around in.

We also added more status flags, for example, on a ship we could track overall damage and shield status in each ship section (by quadrant: fore, aft, starbord, port or FAPS).

With the -findall- technique "just around the corner", the game would be flying faster and farther than ever before.

One problem was the technique hadn't surfaced, yet. It wouldn't until late Spring 1976 when we got a group of us together to bash on it. (See the Empire IV section and "Speeding It Up".