tilegraphics.txt

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

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!