tilegraphics.txt

3D游戏编程领域专家撰写的启迪性文章之一

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