To contact the author via email (until June/July 1996):
Though this text is not shareware, if you find it worthy of a donation, I will gladly accept any amount of money you offer (since I am a starving programmer looking for an employer).
This document will cover graphics in the style of Ultima 6 (presumably Ultima 7 as well, but I have never played it-- read on). I will also discuss many of the same techniques that Greg Taylor covered in his Tile-Based Games FAQ. That is one reason that I have composed this document, because I found the information in Greg's FAQ to be somewhat disappointing. I hope to present some ideas that will advance those he overviewed. Granted, he covered lots of things I won't cover here (roof tiles, hidden map areas, palette shifting), but there are so many fundamentals that could be implemented in a better way, I had to put out an alternate solution. Oh yeah, it is presumed that the reader has a solid understanding of C programming.
While Mr. Taylor tended to emphasize the 640K barrier, I think that everyone should get a 32-bit, protected mode compiler. Let's face it, the small overhead of running a DOS extender with your protected mode program is negligible in the face of the benefits gained. I feel it's a fair assertion to assume that people who play games have at least 4 megs in their machine. Catering to the lowest common denominator (i.e., 286/640K) is a good thing as long as that denominator isn't too low. I think nowadays, a 486-33/4meg is a decent denominator. The hassles of EMS and conventional memory simply disappear when protected mode is used. I've never been more frustrated by this situation than when I couldn't get Ultima 7 to run on my snappy Pentium because I had to create a boot disk and still couldn't free the conventional memory required (without purchasing a commercial memory manager). I own U7, but I've never played it. That kind of annoyance can be avoided by simply using a "modern" compiler, with the added bonus that most of the time, it will run in the increasingly popular environment, Windows 95. (Sorry to be ranting but that's another reason I'm writing this document :)
Note: I am assuming that you are interested in CRPGs since they are the most
common game genre to employ this sort of graphics. Of course, the techniques
can be applied to any game or genre (ie, a strategy game).
Clipping. This is limiting the plotting of a tile to within an arbitrary boundary (the screen edge, for example). If the tile's graphic imagery crosses this boundary, it is "clipped" or trimmed so that only the area within the boundary gets drawn.
Masking. When a tile is draw to the screen with masking, all pixels of a predetermined color are not plotted so that the tile will only cover the background where the shape of the graphic dictates. No big, blank boxes around the graphic imagery.
NPC. Stands for Non-Player Character, or anyone that the player cannot directly control.
Object. I refer to these in this document not in the sense of OOP, but as an independently defined data structure that describes something in your game universe (a person, an item, or a map entity).
Tile. Also called an icon, a bob, a sprite. It is, simply, an arbitrarily
sized bitmap (though commonly 16x16 pixels).
Let's look at a typical way of implementing a map: arrays. Good ole arrays. When we all programmed in BASIC and arrays were all we had, sure, use them for your maps. Simply declare map and there you have it. Want multiple layers? Okay, map. There!
Well, here's what I suggest. Keep the first declaration. But what we want to achieve is massive flexibility. We don't want to be limited to 3 layers or waste memory when we need less. (Side note: efficiency is _always_ of utmost concern! I don't care if your target platform has 32 terabytes of memory, always optimize for space and speed!) So how do we get unlimited layers while using only as much memory as required at any given moment?
About the time you take Pascal in your CS cirriculum, they'll teach you about a thing called a linked-list. Perhaps already you can guess what I'm about to explain...
If we define our _entire_ map as map, then for each element in that array, we define a list header. Yep, each element is a linked-list. You might be thinking, "But what about space optimization? Won't 10,000 linked lists be wasted memory?" Below we'll talk about ways to access the map incrementally, which will solve this huge array problem. As it stands, the answer to your question is still "No."
Remember that we had map, which (at minimum) is 30,000 bytes. Granted, a linked list header may be 8 bytes itself which means map is 80,000 bytes. Yes, it's bigger, but even without special techniques for accessing only part of the map at once, the payoff in flexibility and graphic enhancement makes it worth the size. This is another reason for using a protected mode compiler-- when you absolutely have to, you can have these huge structures without worry of hitting any stupid 640K limit.
Okay, so you accept what I've said so far? Okay, then, on to the map
representation. How do we use these linked lists to achieve multiple layers?
This will require some sort of map "object" definition.
I would advise that you follow some conventions.
With this in mind, we commence with map specifics.
This is our map definition. We have a separate linked list holding all NPCs that are active and their relevant information.
In Ultima 6, if a character went in a doorway, the character appeared under the archway. The characters were further obscured by tall signs, and the like. This is a very cool and realistic effect. (Though I haven't done benchmarks on any of the mapping techniques here, I suspect that what I'm building up to will require a fair amount of horsepower. Hopefully our common denominator 486-33 will suffice.)
To achieve this obscuring effect, I would flag each map_tile as either "under" or "over" (thus, the need for the bitflags field in the map_tile structure). The bottom layer (ground) will definitely be "under" since all tiles get plotted over these regardless. Things like trees, walls and open doorways should be "over" since the player could potentially appear obscured by such objects. For best efficiency, sort all these tile lists so that "under" tiles come before "over" tiles.
Here's how the plotting algorithm should work:
That is, unless you want to center small tiles in the 16x16 pixel space. That's easy enough.
So now we see how a larger tile can obscure those in adjacent locations. A very tall tree would do this. This ain't Ultima 4 anymore! Let's get out of the 80's technology and at least catch up to early 90's.
With this outline, hopefully you can exploit the possibilities yourself.
Imagine the flexibility over the "old" array technique. Instead of drawing
millions of tiles for each piece of scenery like a plain wall, another wall
with a torch on it, etc, you simply draw the plain wall, draw the torch,
then stack the picture tile on the wall tile. You can reuse the torch for
different wall types without drawing a new wall with a torch on it. Again,
this saves storage space by having fewer graphics but with more variety.
All you really have to do is have a main item list, call it all_items. This list will hold each and every item that exists in your world from a bedroll to a candle to a ration of food. It's handling this list safely and cleanly that presents the major problem. And if you have a solid knowledge of lists this is not much of a problem. I suggest that you build a list library of common functions (ie, insertion, deletion, creation, destruction) or find a library that already exists and works reliably. Then apply these concepts.
But now, let us aside to something else of relevance to our all_items linked
The main barrier, then, is the storage format. How do we store a map when it's a huge array of linked lists and link nodes? Well, there are many possibilities. One is to encode the data with "identifier" bytes. There are several variations of this.
For each map location (map[x][y]), we write to disk the number of nodes in each list at that location (minimum 1, because we have to have a ground tile). This is very simple. To retrieve it is the tricky part.