Tricks of the 3D Game Programming Gurus/gurus.iso/Articles/TileGraphics/Tilegraphics.txt

Text File | 1999-05-15 | 25.8 KB | 554 lines

You have to call him!!!!

===================
  Tile  Graphics
  Techniques 1.0
    April 1996
-------------------
 By Jason McIntosh

Tile Graphics 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 (until June/July 1996):
    [e-mail]
This is a friend's account.  He let me use it for this text and any responses
I might (hopefully) get.  I should have my own account in August 1996, and I
will release an update at that time.

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).
    1427 Fairlane Dr.
    Richmond, KY 40475
    USA
This is my mother's address, since it is effectively permanent.



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 :)

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 dword 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.

    +--+
    |  |
    |  |
    +--+ <-- there's the "base" point

  +----+
  | +--|
  | |  |
  | |  |
  +----+ <-- the larger tile aligns to this point

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...

    +--+--+--+
    |  |  |  |
    +--+--+--+
    |  |  |  |   The player is always located in the center area
    +--+--+--+
    |  |  |  |
    +--+--+--+

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.

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
[e-mail]

Greets to Ed Mackey and Roy Millican (both Amiga guys who probably won't ever
see this).

And hello-nice-to-meet-you to Mark Feldman: where's PCGPE 2?  I'm a willing
contributor.  :)

It's after 4am!  I've got to go to bed!