Ron Hiler's Plan File

April 15th, 2000

The programming phases of MD can essentially be broken up into five parts. The interface work, the globe, the main map, the artificial intellegence, and everything else. These were essentially, though not quite, done in the order they are listed, with the possible exception of the last one, which was done throughout the life of the project.

Chapter 5: Would you like to play a game?
Early on, when we were still calling the game "The History of Warfare", I designed a couple of the interface screens for the game. This is a neccesary and vital first step. The user needs to interact with the program, after all, and the program needs to deliver all the important information back to the user. In a perfect situation, information delivery and the ability to act on that information is both easy and intuitive. If both of these are not true, it can ruin an otherwise great game (just ask anyone who has ever played Ascendancy).

Because this is such a critical stage, very often, when designers do this, they create the screens on paper before sitting down to actually put the interface on the computer. In our case, however, we didn't do that. I am using Borland Builder to write Manifest Destiny, and one of the great strengths of Builder is that you can set up an interface within a few minutes. This allows prototyping right on the screen. If you don't like a particular button, you can just move it, or delete it. It's really quite nice. The first two screens that were designed were the main screen and the unit design screen, followed shortly after by the research screen. Designing these screens took very little time (a week or so) and they really haven't changed much since their inception.

Thus, the start of the coding of Manifest Destiny was underway. It didn't do anything much, except display a couple of screens. With a few minutes of work, I was even able to switch back and forth between them at will. Now it was time to add some functionality.

Chapter 6: The Globe
One of the first improvements made to "The History of Warfare" was the addition of a spherical world. Unbeknownst to us at the time, this was to be a defining moment in Manifest Destiny, one which would cause no end of problems, almost causing the death of the game, but, in the end, turned out to be one of it's greatest acheivements.

The first thing we wanted to do in connection with having a spherical world was put up an overall globe map (in the upper right corner of the main screen, for those of you familiar with the game). The initial step was to set up a display engine, for which we used Direct Draw (which is nothing more than a bitmap display tool). Once Direct Draw was working, displaying a plain black bitmap over the desired area, we needed to add a globe to that bitmap.

The first attempt at a globe went something like this. Consider an orange. Now make horizontal slices of that orange, a whole bunch, as thin as you can. What you end up with is a bunch of cirlcles. If you keep them in order and stack them on top of each other, you get back your spherical orange. Now, take one slice, make a small cut, and carefully unwrap the peel. You have a small strip of peel now. If you do that for all of the slices, you have many strips of peel, of varying lengths. Draw your terrain on those slices, fold them back into a circle, stack them, and there you have your globe! That is essentially what we did. We drew each strip onto a cirlce, and drew each circle (from back to front), until the entire globe was displayed. If you rotated each circle in synch, you could even rotate the globe around quite nicely.

It was a good idea. And it works, to an extent. There were two problems with it, though. The first was that many calculations had to be made for each pixel of the globe, and it wasn't exactly fast. The second was that it suffered from Epsilon errors (errors caused by the rounding of floating point numbers into integer numbers). This was especially bad as you rotated up to the poles, where pixel sized holes would appear in the display.

So we scrapped it. Instead, we switched to using Direct3D. D3D has a lot of parts to it, but essentially you take a skeleton of a model, in our case a sphere. Then you wrap it with a bitmap. Creating the bitmap took some modification to our current design, but we were able to use our "strips" to create it (so the initial design was not a total loss). When this was finished, we had a much faster, much nicer looking globe on the screen. No holes!

Around this time, several other things happened. The words "Manifest Destiny" first appeared, replacing that horrible working title we were using before. Game creation became an issue, because we needed landscape to put on our globe, so terrain generation routines were written, and implemented within the game creation routines. This also precipitated beginning work on game files, since we needed to save the information the generator was creating. The unit design screen started to become functional, as well as the research screen. We also had started prototyping the rest of the major screens, including the race design section, the city screen, and the front screen. A lot of different stuff was being done!

Chapter 7: The Main Map
At the point where we began to consider the main map, we were at an all time high. Quit a bit of functionality was in the game, and it was starting to look a lot like everything was coming together. The one major thing missing was a playfield.

Our high was not to last. I can't begin to tell you guys the number of designs which were considered and rejected for display of the main map. We came up with a tiling system, using a hex based grid, and a blending scheme, which would soften (though not entirely eliminate) the harsh look of hexes on the map. This is a good system, and we still use it to this day.

And then things began to go wrong. The difficulty lies in that spherical world we had designed. The basic problem was that you simply cannot tile a sphere with hexagons. We knew this from the start, but had several deformation ideas in mind which would make it possible. There were several designs which were started, and then rejected as we determined there was some problem with them. We lost about two or three months in this stage. Finally, we came up with a method which we were pretty sure would work. In this attempt, we simply layed down a series of hexagons and stretched the entire thing horizontally, like a peice of rubber, until each part lined up as we needed it to. It took roughly six months to get this right, and some very complex calculations. Intermediate stages of the engine did some very psychadellic things! Finally, in the end, we had a working system, but it was terribly slow. Every pixel on the main map was being put through a whole series of calculations before being displayed, and by the time you put everything together, the frame rates were abysmal.

When I realized I had just spent six months writing an engine which wouldn't be able to display as fast as I wanted, I was ready right then to toss the whole project. Considering the number of attempts we had already tried, and the amount of time spent, the thought of trying to start over again was daunting. At that point, I fully understood why a spherical world had never been used in a strategy game before. I began to immerse myself in other work while I considered the future of Manifest Destiny.

Then, someone (Peter, I think it was) suggested that we use D3D. It would do most of the trickiest deformations for us, it had the added advantange of being able to use hardware acceleration, and, by using this method, most of the really complicated calculations would not be needed. Certainly, it would be fast enough. Of course, I had considered this approach before early on in the planning stages of the main map. It was natural, considering we already had it set up for the globe. But it had been rejected because the memory requirements for such a huge model were prohibitive. But, given that every other method we had tried ended up with display problems at the poles, or was too slow, and that D3D was designed to handle both of these difficulties, I began to turn my attention to solving the memory problems. Rather than have the program handle the memory on it's own, and try to solve the very difficult display problems, I decided to let the program handle display on it's own, and solve the not quite so difficult memory problems. This turned out to be a much better approach. What we ended up with was a system that is exactly the same as the globe map, only much bigger. If you consider the globe map, zoomed way in, you have the main map (more or less). At one point, before I put limits on the zooming function, it was possible to zoom out of the main map until you could see the edges of the world, and eventually it looked just like the globe map.

As it turns out, the large map is the biggest memory hog in the game, though we reduced it a fair amount from the origial estimate. We did this with a combination of dropping the resolution of the textures, and cutting down the number of overall textures being used. Still, it's a pretty big chunk of memory that is being taken up. I have since come up with a few further ideas on how to drop the requirement, but they'll have to wait until we have a working game before I delve into them (for one thing, they will complicate the unit movement routines!).

Chapter 8: Artificial Intellegence
When the main map was completed, we were once again on top of the world. There was only one last peice of major coding left between us and a working version of the game. The AI routines.

There are actually several different AI's in MD. There is one to control unit movement. Land units, for instance, shouldn't be allowed to move across water, they have to go around. And they probably ought to try to pick the best route there. Another AI will control the computer opponents, who, if we do this right, will NOT cheat, and will give the players some challenge. Another AI will control combat manuevers. Direct combat control will not be handled by the players. Like any general, you will give your fleets orders, and the units will carry them out. Once entered into combat, a general can but sit back and hope for the best!

There are a couple of other AI proposals in the works, but those are the major ones. As I write this, AI is in production right now. We have yet to see signs of intellegent life, but we are hopeful! The movement routines will be handled by an algorithm called A* (A Star). A* is a well documented and proven algorithm for pathfinding, and I expect no difficulties when we get to that set of routines. The computer opponents will perhaps be the most diffcult and complex AI to work with. There is nothing easy about teaching a computer to play your game, especially one as complex as MD is, and teaching them to play without cheating, and well enough to challenge the human players, ought to be tricky. For the initial Alpha release, the computer opponents will not be functional. There is a reason for that.

We have something of a practice AI to code in preperation for the computer opponent AI. That is the combat AI. They will use exactly the same methods and algorithms (a combination of expert systems, fuzzy logic, and neural networks). The combat AI, however, is more focused on a single task. This will, in theory, make it easier to get working.

Chapter 9: The Kitchen Sink
That should about do it for the major tasks. Of course, there's a myriad of little stuff left to do before we have a playable game, and about a million improvements I want to make after the first Alpha goes out. I think the it's all the small details that are some of the funnest and most interesting parts of programming the game. The big tasks are important, certainly, but they can narrow your focus sometimes. I really think I have the most fun when I am writing four detail type things into the game per day. They aren't big, but they end up having a big effect.

Okay, enough for now. Next week will be last in our series, where I will talk about what I think every independent game developer ought to know, and why I'm even qualified to talk about it!

Take care...

- Ron Hiler (Lead Programmer)