Tile Graphics
Techniques 1.0
April 1996
By Jason McIntosh Tile Graphics
Author note: This is a very old article.
Re-Formated and Ilistrated by Greg Breland
Techniques 1.0 is copyright 1996 Jason McIntosh. All rights reserved. Freely
distributable if unmodified and in its entirety.
To contact the author via email:
What's This Document (Not) About?
I wrote a CRPG for my Amiga and got about 85% finished when I bought my
PC and dropped the Amiga project to learn PC programming. The point is
that while that game was/is really cool, I have learned and developed much
since then. Here's my (partial) full disclosure :)
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 :)
Update: I finally got it to work, but was never able to enjoy it as much as the old classic Ultimas.
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).
Vocabulary
For the uninitiated, here's a list of some terms I use and their meanings
relative to my conceptions of them.
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).
Plotting Tiles
The first task to creating a tile-based game is plotting the landscape
and its inhabitants. Well, I will assume that you have several routines
already:
A) Plot a 16x16 tile, without masking (which is faster than with masking).
B) Plot an arbitrarily sized tile, with masking.
C) Either of the above routines with clipping (though this is optional).
I won't waste time getting detailed about how to plot tiles, as there are many
good tutorials
available on the subject (get XLib and don't worry about the nuts and bolts
of it).
Maps and the Lay of the Land
Greg Taylor mentions multiple layered maps. He's absolutely right: you
will need multiple layers to get any kind of complex graphics in your world.
But, he didn't take the idea far enough.
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[100][100] and there you have it. Want multiple layers? Okay,
map[3][100][100]. 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[100][100], 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[3][100][100], which (at
minimum) is 30,000 bytes. Granted, a linked list header may be 8 bytes
itself which means map[100][100] 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.
struct map_tile {
struct map_tile *next; // pointer to next in list
struct tile_gfx *tile; // pointer to graphic imagery object
char type; // keep reading...
char bitflags;
};
For example:
map[0][0]
LIST_HEADER -> map_tile -> map_tile -> NULL
map[1][0]
LIST_HEADER -> map_tile-> NULL
...and so on. Using this setup, the first map_tile is the bottom-most
layer in your map. Each successive layer simply adds another map_tile to
that specific map position (ie, map element, ie, list). This way, you could
stack twenty tiles on one map position, while having only two on a tile
nearby-- with no memory wasted on empty spaces! That is the big payoff
for this technique.
I would advise that you follow some conventions.
A) The first map_tile in a list should be a ground layer (ie, grass, sand).
It should also be a constant 16x16 tile that should be plotted without
masking.
B) All map_tiles after the first can be variant sized (up to 32x32)
and should be plotted with masking. These successive layers will be trees,
rocks, walls, people, monsters, swords, treasures, and anything else.
If you're wondering how I intend to handle a 32x32 tile in a 16x16 tile
world, keep reading. Let's get the basics down first. In fact, let's drop
this for the moment and discuss some fundamental ideas about representing
NPCs and items for a game.
The Flesh of a Soul
I should explain that I delineate objects from their graphics. That is,
there are separate structures for objects and for their graphic imagery.
For example:
struct npc_object {
struct npc_object *next; // keep a pointer handy for later
struct tile_gfx *tile; // pointer to the graphic imagery for this guy
struct attributes atts; // str, dex, hp, inventory, etc.
char x_loc; // location on map
char y_loc; // may need to be an unsigned short if the map
// is bigger than 255x255 squares
};
struct tile_gfx {
struct tile_gfx *next; // always
char *imagery; // pointer to the actual bitmap data
char x_size; // size in pixels
char y_size;
char x_offset; // for handling those 32x32 tiles
char y_offset;
char bitflags; // 8 bitflags (ie, masked?, animated?, etc)
char align; // align to word boundary
};
So when a person or monster is plotted to the screen, the tile information
for each character can be totally different and referenced through the
NPC structure. Likewise for items. Remember that these graphics will be
drawn with masking so that the map background can still show through.
With this in mind, we commence with map specifics.
Plotting Map Layers
struct linked_list map[100][100];
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:
A) Plot all ground tiles (ie, the first tile in each list).
B) Plot all tiles flagged "under."
C) Plot all NPCs and items.
D) Plot all tiles flagged "over."
The plotting should go from upper-left to lower-right to appear correct.
The 32 Pixel Question
Now that the basic map structure and function is understood (it is, isn't
it?), we can get to the 32x32 tile question. Since all tiles have a 16x16
"base" anything over this size will simply be plotted with an
offset. The offset should force the lower-right corner of the tile to align
with the 16x16 pixel base.
A tile that is 20x17 would have an x_offset of -4, y_offset
of -1. This is calculated with (16 - x_size), (16 - y_size). If a tile
is smaller than 16x16 (a knife, for example), then it will have a positive
offset. Look: a 7x10 tile has +8 x_offset, +6 y_offset.
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.
Material Objects and Possessions
Handling item objects, if you want Ultima-level technology, requires that
each object be defined in a detailed way and managed much like NPCs-- with
a linked list. This is a little more complicated, but the enrichment of
the game environment is incredible. In my Amiga implementation, for example,
I defined objects that can be moved, carried, used, contain other objects,
etc, just like Ultima 6. This allows your universes to really come to life.
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 list.
Accessing the World Map Incrementally
Since I've mentioned Greg Taylor's FAQ previously, I will come to it again.
He suggests holding the entire map on disk and "paging" in only
the areas that are close by. That's exactly what I suggest. The only hairy
part is the nature of my maps. They are linked lists and this makes for
a complication when accessing them bits at a time.
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.
A) Read one byte. If it is zero, then we have no more nodes
for the current x:y position. If it is non-zero, we have to read that
many nodes from disk, building the list on the fly.
a) Keep reading nodes until the Nth node is finally read.
B) Repeat step A) until the entire section of map we want is read into
memory.
In code:
char c, i, x, y;
struct map_tile *mt;
x = current_x_position; // these will probably be assigned by a loop
y = current_y_position;
while (1) { // loop infinitely, so be careful!
c = fgetc(filehandle); // read our encoding byte
if (feof(filehandle)) break; // end the loop, we are out of data
// you'll also check to see if you've read all
// neccessary data and use break to exit the loop
for (i=0; i<< c; i++) { // read as many nodes as encoded
mt = newnode(); // remember to do failure checks and handle errors!
fread(mt, sizeof(struct map_tile), 1, filehandle);
addnode(map[x][y], mt); // put the new node in the map lists
}
// continue reading nodes until all map data is in memory
}
This code fragment leaves out quite a bit, like list details and deciding
what map coordinate range you need to read. At least you get to see the
principles in action. There is _lots_ of linked list juggling. You must be
very, very careful about memory leaks and such when programming this. Take
your time, comment your code, and _know what you're doing_! With this sort
of code, you need to plan out exactly what to do. Some more than others, but
everyone needs a plan.
Another method would require that you add two new fields to the map_tile
structure:
struct map_tile {
struct map_tile *next;
struct tile_gfx *tile;
char type;
char bitflags;
char x_loc; // store each tile's location here
char y_loc;
};
Now, when you read a tile, it has the location information in it. You simply
insert the read node into the according list in memory. I like the first
method better, though, because it uses less disk space since the encoding
only requires one byte, especially for maps > 255x255 that will need a short
for index reference. I leave the final decision with you, because there are
better ways to implement this, I'm sure.
Now that we can access the map at arbitrary points from disk, how do we decide
what to store in memory and when to load more? As Greg states, look at
the current map "chunk" as a set of 9 small areas, theoretical
boundaries actually...
Each small area might represent a 10x10 map chunk. As the player moves across
the middle boundaries, the map data is shifted (scrolled) and whatever
areas are "blank" afterward will be the ones we load from disk.
Refer to Greg's FAQ for more explanation, if you need it. Hopefully, it
is self-evident.
I will only say that you must remember to deallocate all
nodes no longer needed. This cannot be over-stated. You will find many,
many bugs lurking in this section of your program if you are not an alert
programmer. I learned this through tedious hours of memory leak chasing.
Tedious hours.
And What of Our Possessions
We come back to our discussion of the all_items linked list. Since your
world may be exceedingly large (my project included over 400 items at 85%
completion), you will not want to keep this whole list all the time. If
memory allows, sure, keep it in memory for speed. If not, then access it
from disk when needed. Elaboration follows.
Like the huge map, which only
comes into memory in chunks, we only need parts of the all_items list in
memory at any one time. Two reasons: 1) it is far less space consuming
than keeping 1000 items in memory all the time, 2) it is much quicker when
performing operations on the items (ie, searches, etc).
Point 2) is particularly
of interest since we will be dealing with those items closest to the player
the most often. Doesn't it make sense to keep only the necessary items
in another list, a "local" list? Of course it does.
Each time the player wants to manipulate an item (say, picking up a sword),
the program will have to find the item in question by searching the list.
Then it will
have to perform some operation(s) on it (ie, place the sword in the players
possession). This is not to mention the fact that each graphic update will
require searching the list of items to determine which are visible and
which are not. Now this makes perfect sense, right?
So we establish a secondary
linked list: local_items. This list will grow and shrink as the player
moves through the landscape. Items will get moved to and from this list
and the all_items list. all_items will hold items not currently used. I
would recommend holding all_items in memory when possible for speed issues
and issues of altering the game state-- that is, as related to saved games.
You see, if you want to save a game in progress, all object lists must
be written to disk. But if you are constantly writing over the all_items
list, and the computer crashes, that game state is ruined because part
of all_items was in memory, and not all of it was on disk since item in
local_items are literally removed from all_items. Follow?
The solution
is to simply store all_items, for game use, in a temporary copy of the
initial game state. That way, all previous information is preserved and
you safely work with a copy. But to avoid all this hocus, keep the lists
in memory at all times, only updating the disk image when a game is saved.
I hope all that soaked in. If not, re-read it in a couple days.
Straying From the Path
I seem to have gone off on a few tangents here. But I think that they are
all an integral part of the big picture. Now I would like to address some
of the problems from Greg's FAQ that this framework fixes (I'm not picking
on him, but I am hopefully building on his information), with direct references
to his work.
III: Walkability
To create a map space that cannot be crossed
by the player, simply use the bitflags to denote a barrier object. This
can be either a map_tile, a npc_object, or an item_object. If any one of
these appears in the location that the player is about to move into, then
movement is restricted. Simple and clean, and no need to make any limitations
on the map or objects.
In fact, I divide barriers into several classes.
One is a total barrier. Another only restricts movement-- but not things
like arrows or spells flying across them. Another only restricts arrows
and such, but not movement (for magical sanctuaries). This can all be achieved
by using those simple bitflags in each object structure.
For those of you who want to see code...
#define flag_BARRIER (1) // this blocks movement and missiles
#define flag_MOVEBARRIER (1<<1) // block movement only
#define flag_MISSLEBAR (1<<2) // block missiles only
Then, wherever your code handles movement...
if (map[x][y].bitflags & flag_BARRIER) // this checks for the bitflag
player_cant_move();
Of course, accessing the map data will involve checking each object in the
x,y location list in question for these flags, but you get the idea.
VI: the OBJECT layer
Greg has no autonomous objects. His maps hold object information, much
like Ultima 4 probably did. With my system, there is no such restriction
and no limitations. You can stack gobs of objects and hordes of people,
too, since they all exist independent of the map data.
So Close, Yet So Far
I could go on typing about different areas of CRPG making for hours, but
I want to limit this document to tile graphics related problems. I should
probably work all of this up into a book and include a demo and tons of
source code, but who would publish it? :) Potential future installments...
Using event flags to trigger changes in the game world (ie, when a quest
is completed or a decisive action made), the writing of "data compilers"
to create attributes for your objects in a script file (as I did with my
Amiga project), creating a map/object/graphics editor, implementing a system
of spells and using "reagents" to create them, character creation
routines, NPC speech system, NPC artificial intelligence-- especially combat
where NPCs intelligently arm themselves based on circumstances and resources
at hand (ie, close range weaponry, spells, abilities, etc), animating objects.
The list goes on. I have experience programming all of these things, and
I plan to put that experience to use and create a CRPG for the PC. I am
in college, so it will come slowly, but one will emerge. Why don't you
explore these subjects with me, and let's create some good games.
Update: Nine Plans Entertainment Software
If there
is sufficient interest, I might write up more technique documents. That
all remains to be seen. Give me your feedback. I want to discuss these
things with people, because nobody seems to want to. I suspect they fear
that people will rip-off their ideas. Let me state a fact, everyone: technical
achievement does not make a great game. If everything I said here you can
do better, you are at no particular advantage of making a better game than
me. The quality lies in content. So quit worrying about someone stealing
your techniques and algorithms, because even if they did, that doesn't
mean they will undermine your success as a game designer.
SPEAK UP! I would
love to hear alternate/better solutions to these programming puzzles.
And Now I'm Off, Dear Patsy
Please spread this to any technical forum and medium (unmodified, of course)
that you see fit. I don't have access to any commercial nets, so uploading
there would be appreciated. Spread me on the internet as well.
Happy creating!
Jason McIntosh
jmcintosh@iclub.org
Greets to Ed Mackey and Roy Millican(both Amiga guys who probably won't ever
see this).
It's after 4am! I've got to go to bed!