Multiple objects on a tile

Some things from Usenet:

Article 189584 of rec.games.programmer:
From: jack <jacko11@telegram.infi.net>
Newsgroups: rec.games.programmer
Subject: Tilemaps: linked lists versus arrays, Seriously!
Date: Wed, 03 Jun 1998 23:41:42 -0400
Organization: InfiNet

Recently I have seen some debate on the subject of linked-lists vs.
arrays in tilemap storage. I have no idea how widespread it is, but I am
concerned that some tile-coders might get scared away from linked lists
prematurely. I've looked at the issue, and decided that the argument
against linked lists presented in the "Linked Lists vs. Arrays" article
at Game Programmer's Galaxy is an argument that only works if you are
writing a very simple tile engine; that is, if your objects are all very
small (as small as one byte, as the article states!) and if you are not
*separating* your layers.

	The problem is: putting more than one object on a space in the object
layer in a tile based game. In the original "Tile Based Games FAQ 1.2"
by Greg Taylor, he uses an array that only allows for one object on each
space. However, he briefly touches on the subject of linked lists in
putting more than one object on a space. 

As you might know, tile maps can be arranged in layers like this, top to
bottom:

-------------------------------------------------
OVER LAYER (roofs, overhangs, special effects)
+
OBJECT LAYER (items, people, monsters)
+
FRINGE LAYER (trees, etc.) 
+
BASE LAYER (the ground)
-------------------------------------------------

	The "Tile Techniques" document, which came later, developed the
linked-list idea a little more and provided an example or two. I
recently visited the "Game Programming Galaxy" site
(http://www.geocities.com/SiliconValley/Vista/6774/) and on its "Tile
Based" info page, it lists the following as reasons for *not* including
the "Techniques" file:

********* QUOTED SECTION ***************************************
Oh, BTW: I won't put the TileTech article on this page, because the only
new is the use of variable size objects - and the extensive use of
linked lists is pure nonsense, memory wastement and makes the whole
thing a lot more complicated. Take a look at the "Lists vs. Arrays"
article, if you want to know more. 
********** END SECTION ***************************************

	"Memory wastement" :-) ?? I decided to investigate, as I am writing an
RPG tile engine. The "lists vs. arrays" article there briefly explains
the
machanics of arrays and lists, etc. It then claims that linked lists are
unneccesary and a huge waste of memory, since (among other reasons I
will deal with) a linked list map will waste 8 bytes per position if
there is only one object on that position (four for the head* and four
for the next*). But note that only *four* bytes are wasted on the *next*
object and every new object thereafter, since the header doesn't have to
be duplicated again. 

	The solution the "Vs" article presents is simple: use multiple object
layers; in essence, a 3-d matrix. But this "solution" is the starting
point that would have made the "problems" with linked lists disappear:
if *only* the object layer is stored with linked lists, much less memory
is wasted even if your objects are just 4 bytes (and I'll get to *that*
limitation). The BASE, FRINGE, and ROOF layers can be stored as simple
matrix arrays since those objects don't need to be stacked. By using
linked lists, you gain the flexibility of putting more than one object
on each space without wasting lots of memory on every 10-space array
that only has 1 or 2 objects in it. 

	The Vs. article states that "I guess the average map has at least 2
tiles per position". Well, everywhere has a floor or a ground; that's
one tile. But even in a world with *lots* of items, the typical position
is not going to have two objects. Yes, some will have five or more, but
not many. But *many* positions will have only one tile: think of the
ocean, the vast expanses of land that will be only partailly forested,
the stretches of desert, the item-less paths and roads in towns, the
corridors of castles that need only one tile for the floor.

	By splitting your map into layers that are *stored differently
according to usage*, you can move predictable bits off (floors, fringes,
roofs) into efficient arrays. The unpredictable object layer needs to be
flexible; we can't just limit it to 8 objects high everywhere, because
we might need more. And we can't waste all the memory of using *arrays*
8 levels high, since we will hardly ever actually stack that high.
Mostly, we'll have one or a few objects. Think of a treasure room in a
dungeon, with corners stacked high with gold and jewels and magic
weapons. Sure, we could hold it if every map position had 8 spaces built
in. But then we'd be wasting *7* spaces for *every* tile and every floor
space that didn't have any objects. 

	Now, the space wasted by using a fixed 3d array instead of linked lists
is fine for small objects. For instance, the "Vs." article states: 

**************** QUOTED SECTION ********************
"The average map has at least 2 tiles per position, giving you 12 bytes
for pointers and 2 (or 4) bytes for data = 14 (16) bytes. This would
allow you to store 14 tile layers for 1 byte, or 8 layers of word-size
tiles. And that should be more tha enough for even very sophisticated
games."
************* END SECTION **************************

	Okay. But who is using just one byte to store each tile in an RPG??
That would only allow 255 possible object types (one of them being a
placeholder for "no object.") I can't even see that happening in a
decent Super Mario Bros. type game. So how about 2 byte objects? That's
65,535 tiles, which should be plenty. But in an RPG, even a simple one
(let alone a "very sophisticated" one) the objects need to have local
attributes. Yes, things like weight and size are constant across
instances of an object, i.e., all #13 torches will weigh the same. But
for *each torch* we need to store how much time is left on that
particular torch, so they don't *all* burn out at the same time. For
armor, we need to store damage points. We need to know who owns some
objects, so that you can't just steal everything from a house without
the owner noticing. (In Ultima, people call *thief*! and the guards
come.) We need to store what animation frame something is in. Basically
we must store *any* attribute that differentiates instance X from all
other instances of that kind of object. This local data is going to take
space.

	Lets' assume that each numeric attribute (damage, quantity/quality
(torch time or magic charges), ownership) is one byte. That gives us 3
so far, and this is not a very big attribute list. Add another byte for
animation frame; that's four. Add that to our original tile ID, and we
get six bytes per object. ( Note that only objects *in the object layer*
need to be stored this way; having differently-stored layers allows you
this flexibility. In addition, things that don't need these extra local
attributes are most likely static tiles, or scenery that the player will
interact with very little. They can therefore be moved to the FRINGE or
BASE layers, stored simply as plain tile #'s in a plain, efficient 2d
array layer, in our scenario taking just two bytes per object. Only
objects that need to will be stored largely. ) 

	Let's do a pro and con analysis with a 64x64 tilemap. Using the
suggested "vs." technique (which I am *not* recommending!), we have: a
64x64x8 fixed array, that is, 64 high, 64 wide, and eight "layers" deep. 

	That's:
	64x64 = 4096 positions per layer.
	Multiply by eight layers: 32768. 
	Six bytes per object: 32768 x 6 = 199608 bytes for a 64x64 map.

	Note that this is the size regardless of whether the world has one
object, or 32768. Still, 192K is not bad. But it still has the drawbacks
I pointed out before: bascially the inflexibility and wasted space for
most maps. Let's try it with linked lists, which is a bit more complex:


	64x64 map. 4096 xy positions per layer.
	BASE, FRINGE, OVER layers: 2 bytes per object. 3 layers. 24576 bytes
(24K) total. Now for the object layer: in an empty state, it contains 1
pointer (as
a header) per position. 4096x4 = 16384 bytes = 16K.

	Let's humor the author of the "Vs." file and say that the average space
has two objects (which I already disagree with.) Let's overestimate and
up that to three objects on every position, *in the object layer*.
That's:

	10x3 = 30 bytes for three objects, plus four for the header = 34 bytes
per position, times 4096 xy positions in the 64x64 map = 139264 bytes,
or 136K. 

	Let's add it all together: 24K total for the BASE, FRINGE, and OVER
layers; plus 136K for a very unrealistically over-stocked object layer.
That's a total of 160K for the map, considerably less than the 192K for
the inflexible 64x64x8  scheme. And you get all the increased
flexibility of having variable numbers of things. 

	There's the crucial point; once the objects become larger than a
pointer (as they will often be in a complex game) it becomes much less
of a waste to use the pointers (and more of a waste to use too many
objects.) For instance, the linked list version uses only 4 bytes (for
the pointer) on an empty space in the object layer; using an array would
require a 6 byte object there even if there were no objects stored (that
is, if the object were assigned a dummy value.) It would still take up
the space. Adding objects only adds 10 bytes each object (6 + 4 for
pointer). Now *in practice*, since non-interactive objects have been
dumped in the other, 2-byte-per-object layers, we will not need to use
as many objects in the object layer; and hence, we will *save* memory
while *gaining* flexibility. For a simple game with small objects, by
all means use the fixed array; but for a RPG or really any game of real
complexity, look at linked lists as a possible solution.  

	Oh, and what about speed? Well, frequent pointer dereferencing is not
going to cost much on a modern machine, and not even that much on a
slightly dated one. I mean, it's pointer dereferencing, which takes a
constant time. So as processor speed increases, the time it takes to
dereference a pointer decreases as a percentage of total computing time.
It's nothing to worry about. The gain in flexibility is more than worth
a tiny speed hit.

- dto@iname.com
Article 189707 of rec.games.programmer:
From: Michael Duffy <mduffy@ionet.net>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps: linked lists versus arrays, Seriously!
Date: Thu, 04 Jun 1998 15:22:44 -0500
Organization: Studio Blue

jack wrote:
[big friggin clip]


Well, well, well.  What do you know.  Another intelligent thread.  This isn't
supposed to happen here people! (^_^)  (that's sarcasm for those of you keeping
score)

That was a good post, and one that I agree with.  I believe that since games have
become more complex, that entire background/object/fringe/etc layering scheme has
long outlived it's usefulness.

In my isometric tile engine, I am set up with four unsigned longs per tile, which
works out to 16 bytes per tile.  The first three ULONGS contain the tile ID (for
lookup), wall ID (if there is one), collision info, temporary A* algorithm
variables, display flags, and other miscellaneous info.  The last ULONG contains a
pointer to a linked lists of objects, roofs, triggers, spell effects, possibly
roofs, and whatever else might be in that location.  A 256x256 map takes up about a
meg of storage, which is fine on a 16 or 32 meg computer which is the norm these
days.  If your world is interesting, a 256x256 map is a lot of romping room, and
you can always load new maps for new locations.  My objects are stored in
structures, and have lots of variables associated with them so they can be as
complex as I need.

I would say it is more important these days to use a structure that allows for
complexity and features rather than one that fits on a 4 meg DOS based 386,
especially if you are working on an RPG.

Thanks Jack, I enjoyed your post.

Later,
Michael Duffy
mduffy@ionet.net
Article 189817 of rec.games.programmer:
From: "Paul 'Ozymandias' Harman" <ozzy@kasterborus.demon.co.uk>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps: linked lists versus arrays, Seriously!
Date: Fri, 5 Jun 1998 10:59:58 +0100
Organization: COLT Internet Services

Michael Duffy wrote in message <35770214.65B2853D@ionet.net>...
>In my isometric tile engine, I am set up with four unsigned longs per tile,
which
>works out to 16 bytes per tile.  The first three ULONGS contain the tile ID
(for
>lookup), wall ID (if there is one), collision info, temporary A* algorithm
>variables, display flags, and other miscellaneous info.  The last ULONG
contains a
>pointer to a linked lists of objects, roofs, triggers, spell effects,
possibly
>roofs, and whatever else might be in that location.  A 256x256 map takes up
about a
>meg of storage, which is fine on a 16 or 32 meg computer which is the norm
these
>days.  If your world is interesting, a 256x256 map is a lot of romping
room, and
>you can always load new maps for new locations.  My objects are stored in
>structures, and have lots of variables associated with them so they can be
as
>complex as I need.


I'm sure that everybody else is in on the big secret, and I have no idea
what I am doing, but...

Why have a linked list of objects at a particular location?

I can see it having benefits in "chess" like situations, where a particular
'playing piece' can only be wholly on one tile or another tile... but in
more free-form games where an object can be anywhere - as in platform
games - surely it's far more efficient to have a separate array of objects,
and the objects take care of their own locations?

i.e. rather than each tile knowing which objects are standing on it, each
object knows on which tile it is standing.

I can see benefits for drawing objects, and benefits for collision detection
I suppose... but I can't see the method working properly for 'free-form'
movement, like in a platform game, or a top-down "Super-Sprint" style racing
game.

    Ozzy
Article 189850 of rec.games.programmer:
From: Michael Duffy <mduffy@ionet.net>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps: linked lists versus arrays, Seriously!
Date: Fri, 05 Jun 1998 11:00:32 -0500
Organization: Studio Blue



Paul 'Ozymandias' Harman wrote:

> Why have a linked list of objects at a particular location?
>
> I can see it having benefits in "chess" like situations, where a particular
> 'playing piece' can only be wholly on one tile or another tile... but in
> more free-form games where an object can be anywhere - as in platform
> games - surely it's far more efficient to have a separate array of objects,
> and the objects take care of their own locations?

Well, that is a problem that is worth considering.  At first, I implemented a
system where all objects were stored in a separate linked list.  But then to
check the area around a tile or in a specific tile, I had to traverse the entire
list to find it.  That meant stepping through and checking every object on the
current map, and with an RPG that meant stepping over a LOT of objects.  So I
tried having one linked list per row in the map.  But that became a major hastle
when moving object vertically, because I would have to remove from one list and
re-sort into another.  Also, when it came time to draw the map, both of the
above methods became slow because I would have to check a LOT of objects that
weren't drawn in the current frame.

So instead I went to a linked list per tile approach.  Now, the world coordinate
system for my game is of a finer resolution than one tile.  A single tile is
actually 16x16 world measurement units in size.  To convert from world
coordinates to tile coordinates I just shift the X and Y postitions right by
four bits.  This way I can move my character in sub-tile increments, but it is
really easy to search the map for objects.

For example, I have Object A and I want to see what is next to it.  I take
Object A's position, and find the tile it is in by looking in my map array.  Now
I can add or subtract the map pitch and/or the tile pitch to the pointer to
Object A's tile to check the tiles around it.  When I have the address for the
neighboring tile, I simply get the pointer to the linked list, and look through
any objects in those linked lists.  I still have to check the distance between
objects if I need a fine measurement, but I'm only checking the several objects
that could possibly be in range, instead of all objects in the world.  Since my
engine requires a LOT of checking of objects, this seemed like the most logical
approach to me.

However, I also have all my objects sorted into two lists.  The first list is
the per-tile list as described above.  This is a simple single linked list.  I
also have all objects sorted into a red-black binary tree with each object's ID
as the key value.  Every object in the game has a unique ID that is assigned at
object creation (except gold coins which aren't treated as individual objects).
This way I can track individual objects without having to scan the entire map
for them.

Later,
Michael Duffy
mduffy@ionet.net
Article 189860 of rec.games.programmer:
From: "Paul 'Ozymandias' Harman" <ozzy@kasterborus.demon.co.uk>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps: linked lists versus arrays, Seriously!
Date: Fri, 5 Jun 1998 17:33:50 +0100
Organization: COLT Internet Services

Michael Duffy wrote in message <35781620.CE2D0656@ionet.net>...
>So instead I went to a linked list per tile approach.  Now, the world
coordinate
>system for my game is of a finer resolution than one tile.  A single tile
is
>actually 16x16 world measurement units in size.  To convert from world
>coordinates to tile coordinates I just shift the X and Y postitions right
by
>four bits.  This way I can move my character in sub-tile increments, but it
is
>really easy to search the map for objects.

Much as I hate to admit it, this method is growing on me... but I still
can't see it being perfect for side-on platform games. I mean, if the
character is curving in a jump-arc, that's a lot of nasty list manipulation
I'm gonna have to do.

But I do like the built-in proximity checking you get (from the point of
view of the collision detection algorithm)...

>However, I also have all my objects sorted into two lists.  The first list
is
>the per-tile list as described above.  This is a simple single linked list.
I
>also have all objects sorted into a red-black binary tree with each
object's ID
>as the key value.  Every object in the game has a unique ID that is
assigned at
>object creation (except gold coins which aren't treated as individual
objects).
>This way I can track individual objects without having to scan the entire
map
>for them.

So... You have an array of pointers-to-objects, and also each 'tile' has a
linked list of objects.

Hmmm.... there might be something in this...

    Ozzy
Article 189883 of rec.games.programmer:
From: Michael Duffy <mduffy@ionet.net>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps: linked lists versus arrays, Seriously!
Date: Fri, 05 Jun 1998 14:53:32 -0500
Organization: Studio Blue



Paul 'Ozymandias' Harman wrote:

> Michael Duffy wrote in message <35781620.CE2D0656@ionet.net>...
> >So instead I went to a linked list per tile approach.  Now, the world
> coordinate
> >system for my game is of a finer resolution than one tile.  A single tile is
> >actually 16x16 world measurement units in size.  To convert from world

> >coordinates to tile coordinates I just shift the X and Y postitions right by
> >four bits.  This way I can move my character in sub-tile increments, but it
> is
> >really easy to search the map for objects.
>
> Much as I hate to admit it, this method is growing on me... but I still
> can't see it being perfect for side-on platform games. I mean, if the
> character is curving in a jump-arc, that's a lot of nasty list manipulation
> I'm gonna have to do.

For a platform game where you only have maybe three or four dozen objects on the
map, keeping all the objects in a separate sorted linked list is probably a good
way to go.  For objects like powerups you could probably even put a bit flag on
the tile that says "something stationary is here", and then if you enter that
tile you check your object list for the object that is in that location.  For an
RPG where I am dealing with lots of furnature, objects, chests, triggers, etc,
my current scheme is proving to be pretty good.



> >However, I also have all my objects sorted into two lists.

> So... You have an array of pointers-to-objects, and also each 'tile' has a
> linked list of objects.

Objects in my engine are stored in the SBObject class.  This class has a
pobjNext pointer, which is used to sort it into a linked list, such as the
tile's list of objects or in another object's inventory.  I believe I also have
a pobjParent pointer in case the object is in an inventory and you want to find
out what is carrying it.  The SBObject class also has pobjTreeParent,
pbojTreeLeft, and pobjTreeRight pointers along with a flag ULONG, which is used
to sort the object into a red-black tree.  This is a binary tree which can be
balanced as you add objects to it.  I found the algorithm in Sedgewick's
"Algorithms" book.  The tree is sorted on the unique ID that each object has.
My SBWorld object contains the pointer to the object tree, as well as the
pointer to the map data.

When you create the object, you also create the needed pointers because they are
all part of the object.

Later,
Michael Duffy
mduffy@ionet.net
Article 189727 of rec.games.programmer:
From: lennart.steinke@uidesign.se
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps: linked lists versus arrays, Seriously!
Date: Thu, 04 Jun 1998 22:40:56 GMT
Organization: Deja News - The Leader in Internet Discussion

Hi!

Since I wrote the "Tiles vs. Arrays" article, I guess I can add
my 2 cent:

> for the next*). But note that only *four* bytes are wasted on the *next*
> object and every new object thereafter, since the header doesn't have to
> be duplicated again.

Since you have to store always a next pointer to NULL, you'll lose
8 bytes per position, regardless how many tiles (or other data) you
store at this position.
If you use 16bit per layer (whether they may be tile indices or attributes),
you have 4 + (6 * countLayers) bytes per position. If you have one
layer at that position, that would make 10 bytes... also 5 16 bit layers.
So, if you have less than 5 layers, you'll use always less space than
with a linked list aproach.
Since, you'll normally store more than one tile per position (you'll use
the basic and fringe/object layer relativly often), you can assume that
2 tiles per position are quite common.




>        The Vs. article states that "I guess the average map has at least 2
> tiles per position". Well, everywhere has a floor or a ground; that's
> one tile. But even in a world with *lots* of items, the typical position
> is not going to have two objects. Yes, some will have five or more, but

Yup. But a fringe layer, or a tree, etc.

> not many. But *many* positions will have only one tile: think of the
> ocean, the vast expanses of land that will be only partailly forested,
> the stretches of desert, the item-less paths and roads in towns, the
> corridors of castles that need only one tile for the floor.

If you take a look at commercial games (say LucasArts Desktop Series)
you'll see that most positions are two or three layers (object, fringe and
sometimes object).
Oceans shouldn't occupy lot's of space (because you cannot do anything
on them) and dungeons etc, use only less tiles, if you have lot's of different
tiles (stoneA, stoneB, stoneA_with_carpet, etc..)


> flexible; we can't just limit it to 8 objects high everywhere, because
>we might need more. And we can't waste all the memory of using *arrays*
> 8 levels high, since we will hardly ever actually stack that high.

Hm... 8 objects at a tile of 32x32? In most rpgs, you won't have that many
objects in one place. Since you need to _see_ what's on the tile....
And objects which can occur in masses (say coins) will usally be spread
over severak tiles (like in Diablo) or be stored as sprites (like in Zelda).

> dungeon, with corners stacked high with gold and jewels and magic
> weapons.

Hm... So, you step on one tile, and get 8 objects... :)
I've never played a rpg in which this could happen ...
But, the overhead involved in maintaing the lists (and loading
a map made of lists on the fly) is IMHO no accaptable for this
one treasure room....
And there's always the option of using sprites....

> (let alone a "very sophisticated" one) the objects need to have local
> attributes. Yes, things like weight and size are constant across
> instances of an object, i.e., all #13 torches will weigh the same. But
> for *each torch* we need to store how much time is left on that
> particular torch, so they don't *all* burn out at the same time. For

Hm... guess those items are in your inventory... and you should use
a list for that.
If you're talking about torches on walls... if they would stop burning
after a certain time, most  torches would be totally burned _before_
the player finds them.

> armor, we need to store damage points. We need to know who owns some
> objects, so that you can't just steal everything from a house without

That's done by a) Inventory stats or b) scripts for the houses.

> we must store *any* attribute that differentiates instance X from all
> other instances of that kind of object. This local data is going to take
> space.

Sure, but that space should not be stored in the MAP, because it's
an attribute of an object... which can be carried around.
If you take an object, you remove it from the map, and put it in
your inventory... there's no need to store in the map that there
has been an object before.
If you want to the people to call "thief", set a game flag if you steal.


>        Lets' assume that each numeric attribute (damage, quantity/quality
> (torch time or magic charges), ownership) is one byte.

There's no reason to store this data in the map...
Why should a grass tile have a "torch" value?
Okay, you could now argue, that you could use a union
approach (storing a type attribute per layer, and then
cast the pointer accordingly) but that isn't the best way
to do it...


> animation frame; that's four. Add that to our original tile ID, and we
> get six bytes per object. ( Note that only objects *in the object layer*

So, _every_ object needs a torch, hp, and animation attribute?
I don't think so. I wouldn't like to store those values for a chest,
or a key...


> BASE layers, stored simply as plain tile #'s in a plain, efficient 2d
> array layer, in our scenario taking just two bytes per object. Only
> objects that need to will be stored largely. )

If you want to start your player to push an object, it has to be on
the object layer (or you start allways pushing if the player contionus
to go in a "non_walkable" direction).



>        64x64 map. 4096 xy positions per layer.
>        BASE, FRINGE, OVER layers: 2 bytes per object. 3 layers.
>        24576 bytes (24K) total. Now for the object layer: in an empty state,
>        it contains 1 pointer (as
>       a header) per position. 4096x4 = 16384 bytes = 16K.

So, you store BASE, FRINGE, OVER as an array. This makes 3 x 2 bytes per
position.
Now add 4 bytes for a pointer. That's 10 bytes. But only because you
didn't use a list for the the other three layers.

>        Let's humor the author of the "Vs." file and say that the average
space

[..]

>        10x3 = 30 bytes for three objects, plus four for the header = 34
bytes
> per position, times 4096 xy positions in the 64x64 map = 139264 bytes,
> or 136K.

Yes. But...
Say you have an average of 2 objects... that's 5 layers. 5 layers need
5 * 2 bytes = 10 bytes per position.

If you assume 2 objects in your solution, you have
3 * 2 bytes  // Object, Fringe, Roof
3 * 4 bytes // Pointer to 1st object, 2nd object and NULL
-------
18 bytes

If we assume only 1 object on a average tile, that would be 14 bytes.
14 bytes would allow 7 layers.
And as stated before, I don't think you need more than 7 layers.

>        There's the crucial point; once the objects become larger than a
> pointer (as they will often be in a complex game) it becomes much less
> of a waste to use the pointers (and more of a waste to use too many

Correct.
If you store all information which should be in the object in the
map, you're right. But a map should only indicate where things are,
not what they are.

> all means use the fixed array; but for a RPG or really any game of real
> complexity, look at linked lists as a possible solution.

Yes, as I said in my article, lists are a fine thing- but not for tile maps,
and definatly not in the way described in the tile techniques... because
it uses lists for every layer, not only for the object layer.

> It's nothing to worry about. The gain in flexibility is more than worth
> a tiny speed hit.

It's not only the derefferencing. Although the need to derefernce several
time in your inner drawing loop should not be taken easily. It adds
at least one comparison ( if (object !=NULL) ) and one derefernce.
And then logic to check for another object, etc. And that in your
_inner_drawing_loop_ .

And, since your maps are no longer of a fixed size, it's very hard to read
in certain parts of the map directly from the HD. Your code is harder to
maintain.

And, as I said in my article, linked lists are a fine thing.
I just don't consider them usefull for tile maps.
They're great for inventories, sprites, etc. But a since
room is limited, it makes sense to limit the room in
a map also. Small objects like coins will not be
stored seperatly on a position (you'll use a stack
of coins, like in diablo instead). Larger objects,
like chests will occupy at least one tile.
If you try to put several objects at the same place
in diablo, they will roll sooner or later to an
adjected tile. If you try the same in Zelda style
game, it's simply not possible.

The approach suggested here (using an array
for all layers but object) is a nice idea, and it's
hell of a lot better than the one described in the
TileTech. In fact, I wouldn't have written the
"vs." article, if this approach would have been
used in the TileTech.
On the other hand, I would have surly commented
the habit of storing a "torch" value for every
object :)

Happy coding,
Lenny
----------------
Lennart Steinke
http://www.geocities.com/SiliconValley/Vista/6774/

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
Article 190263 of rec.games.programmer:
From: "Paul 'Ozymandias' Harman" <ozzy@kasterborus.demon.co.uk>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps in RPG's
Date: Mon, 8 Jun 1998 12:17:41 +0100
Organization: COLT Internet Services


jack wrote in message <357972FF.5B0A8B55@telegram.infi.net>...
>:-) Yes! You've made an *excellent* point, and it illustrates that I
>should have clarified the scope of my original argument. (sorry to dump
>this on you, but it has to go somewhere! :-) :-) ) I should have
>made it more clear that I was really talking about RPG tile engines
>specifically. My criteria for evaluating the flexibility (pros and cons)
>of certain approaches were influenced by the fact that I'm writing an
>RPG engine, and I tailored things to that outcome. My results, then,
>might not be applicable to, say, a Super Mario 2d tile game. An even
>bigger apples-and-oranges example: comparing the "Ultima 7: The Black
>Gate" engine with that of "Quake". Which is better? Who knows? They're
>meant for different things.


<snip absolutely loads>

Yes, I can't agree more. Use The Right Tool For The Job. The "tiles know
what objects are standing on them" approach is great for RPGs and probably
for Civilisation-style games, and "objects know where they are" is probably
better for fast-moving side (or even top-down) scrollers.

    Ozzy.
Article 190708 of rec.games.programmer:
Newsgroups: rec.games.programmer
From: palm@netcom.com (Palm Computing)
Subject: Re: Tilemaps in RPG's
Followup-To: roger@palm.com
Organization: Netcom
Date: Thu, 11 Jun 1998 00:44:51 GMT

In article <2061CEBD9141D1118CEF080009DE1692E83825@sun.panews.press.net>,
Paul 'Ozymandias' Harman <ozzy@kasterborus.demon.co.uk> wrote:
>
>jack wrote in message <357972FF.5B0A8B55@telegram.infi.net>...
>>:-) Yes! You've made an *excellent* point, and it illustrates that I
>>should have clarified the scope of my original argument. (sorry to dump
>>this on you, but it has to go somewhere! :-) :-) ) I should have
>>made it more clear that I was really talking about RPG tile engines
>>specifically. My criteria for evaluating the flexibility (pros and cons)
>>of certain approaches were influenced by the fact that I'm writing an
>>RPG engine, and I tailored things to that outcome. My results, then,
>>might not be applicable to, say, a Super Mario 2d tile game. An even
>>bigger apples-and-oranges example: comparing the "Ultima 7: The Black
>>Gate" engine with that of "Quake". Which is better? Who knows? They're
>>meant for different things.
>
>
><snip absolutely loads>
>
>Yes, I can't agree more. Use The Right Tool For The Job. The "tiles know
>what objects are standing on them" approach is great for RPGs and probably
>for Civilisation-style games, and "objects know where they are" is probably
>better for fast-moving side (or even top-down) scrollers.
>
>    Ozzy.
>
>


With this interesting thread wrapping up a bit, I thought I'd share some
differences in my code which may be interesting.

In my game Reptoids for PalmPilots, an action game, I handle collisions
by placing all objects in a two dimensional array of sectors, where a 
sector is n pixels.  Checking for collisions amounts to checking against
all objects in the sector.  If the object overlaps another sector (or 
four for the corner case) those sectors are also checked.  The two things
I haven't seen mentioned so far though are that I completely redo the 
sector array each game cycle, just like I completely redraw the video 
frame.  Since most of my objects move, redoing the list simplifies 
the movement code and there really isn't a speed hit.  The other thing
I want to mention is that objects are limited to twice the sector size.
This limits the number of sectors to search.  Reptoids doesn't have
tiles, but for a Super Mario 2d tile game a sector could be n tiles
big.  Creatures bouncing around in arcs or crazy patterns are no problem!

I also have a RPG and a strategy game which basically share object and
map code.  My map is essentially a two dimensional array containing 
the tile type (floor, wall) plus a flag if an object is present.  I don't
store a pointer to objects.  Instead, I retrieve all objects in the tile
by hashing the coordinates and looking in a hash table for the object.  
The hash table is sized so that generally the first spot contains the
object.  At a slight speed hit I save a lot of memory.  In fact my tile
size is one byte!  I of course don't do layers.

Someone earlier mentioned unique ids for objects.  I too have found them
incredibly useful for objects which track other objects. In my structures
I keep my objects compacted to avoid wading through dead objects.  I'm
not sure this is the best decision (comments?), but does mean objects
move and pointers can dangle.  Unique IDs let me recover the pointers.
They also simply saving the game's state.

One last thing is that I'm always amazed/amused when people make doors
be tiles.  I treat everything other than dirt as an object.  In fact, 
when you tunnel into a magma vein in search of gold, I create a magma 
vein object with a quantity value, and the object looks just like a 
magma tile.  This is how I handle damage to tiles.


-Roger Flores
roger@palm.com
Article 190449 of rec.games.programmer:
From: "Rick Craik" <NOSPAMrcraik@ntl.sympatico.ca>
Newsgroups: rec.games.programmer
Subject: Re: Tilemaps in RPG's
Date: Tue, 9 Jun 1998 13:19:46 -0400
Organization: iSTAR internet Incorporated

Hi Jack;

    May I butt in? I am working on Tilemaps in Strategy and have been
following your thread of postings. A strategy game has a lot of features in
comon with the RPG, like tiles, terrain, units/monsters, and a maybe a few
objects. The main difference would seem to be what goes on between turns, or
in a time slice.  In a strategy game each game unit must do some processing,
where in RPG, each monster is only activated when appropiate.
    While reading your posts, on Tilemaps in RPG's, I thought some of the
storage strategies might not be appropiate for a Strategy game. I understand
your scope was RPG games, but if possible, could you expand a bit to include
Strategy games?

    What are the implications of:
    1) Strategy games usually have smaller world map.
    2) Computer opponents need to analyse tile information often.

    I believe your arguments for linked lists apply to Strategy games:

[snip]

>Basically, I'm trying to use the right tool for the right job, according
>to needs. Our current question is: how much data do we need to store
>along the Z-axis, and how flexible does it need to be? The answer of
>course depends on what you are doing.

[snip]

 The Strategy game designer should watch for performance hits that access
tile info often. A small map, for example, should allow the designer to
avoid disk accessing methods.

Thanks for your attention,
Rick
Article 191523 of rec.games.programmer:
From: Michael Duffy <mduffy@ionet.net>
Newsgroups: rec.games.programmer
Subject: Re: Tile Based vs Non Tile Based
Date: Mon, 15 Jun 1998 23:32:18 -0500
Organization: Studio Blue



John Mancine wrote:

> >
> >I'm seriously considering implementing a z-buffered sprite engine that uses a
>
> >single image for the background (well, multiple non-overlapping tiled
> images),
> >and then z-buffers the character and object sprites in.  I've been putting
> some
> >thought into it since looking at how nice Final Fantasy VIII's screens are
> and
> >thinking that it will probably be easier to do good graphics as a single
> image
> >rather than in individual tiles.  Also, my artists are not too thrilled with
> the
> >entire tile idea, and tiles are tough to do in a 3D rendering package.
>
> I know exactly what you are saying. My 3D artist hasn't liked doing the iso
> tiles at all either. Simply because you can't really dive into the details
> as much as you can if you have more of a canvas to work on.
>
> One thing I don't get about not using tiles is how is the scrolling of the
> screen handled? (not even thinking about doing 'paged' scrolling... that is
> pretty cheap looking IMO)
> How would it work? Would you have the whole 'world' divided up into
> 1000x1000 sized "chunks" of images and then load these on the fly? Obviously
> you can't load them all at once.
>
> Can you elaborate a little more? Because I am very interested in doing this.
> And it would be the perfect time to do it in my project.
>
> Thanks,
> jrm



Well, these have been my thoughts on the subject so far:

* z-buffering.  No matter how you look at it, software z-buffering is slow.
However, since you will only be z-buffering in a few sprites into a pre-rendered
background as opposed to 3D where you would z-buffer the entire screen, it
should be fast enough.  You will store your background image as a 16 bit color
image with a 16 bit z-buffer.   You'll probably want to keep these as separate
arrays (instead of packing the info in an unsigned long) because you may keep
the graphics in video memory.

I haven't written a z-buffer sprite routine yet, and the way you approach it
will depend on the flexibility you want and how you draw sprites.  You can
either store the z-buffer info for each pixel of the sprite, or give the entire
sprite the same z-depth.  The latter approach would be faster and would have
less memory storage requirements.  However by doing this you give up the
opportunity to do depth tricks like having your sprite merge through walls or
have some sort of fog effect where the farther pieces of the sprite dissolve
more into the fog.  Since these effects are not likely to be used all the time,
the tradeoff might not be worth it.  Of course you could always store the sprite
z-buffer info and then have your sprite routine draw either a per pixel or a per
sprite z-buffered sprite in different situations.  I'll likely just do a
per-sprite z value.

* paging in BG graphics.  My thoughts here are still a bit underdeveloped since
there are sooooooo many ways to approach this problem.  Here's what I'm thinking
so far:

You have a 640x480x16 DirectDraw surface with back buffer for page flipping, and
you store this in video memory (1,228,800 bytes).  Then you have a say
1024x1024x16 background image buffer in video memory for holding your background
(2,097,152 bytes).  This is a double axis buffer, which means the info in it
will be written to the actual back buffer with up to four block copies.  The
actual "tiles" of your background image are 128x128x16, so they tile 8x8 into
the background buffer.  You keep a duplicate of the background buffer in system
memory for when you have to look up colors for alpha blending.  You also have a
1024x1024x16 buffer in system memory that contains your z-buffer info.  Both
these buffers in system memory are double axis buffers, and they match up to the
background buffer in video memory.

So now when you build your scene you will decide where the upper left corner of
your visible image falls in the background buffer and blit from they video
memory background buffer to your back buffer with up to four separate blits.
Note these are not block blits, but rather line by line blits of up to four
different rectangles.  Then you draw your sprites into the back buffer (not the
background buffer), using the z-buffer in memory to decide how to z-clip the
sprites.  If you are doing blending effects with the sprites then you use the
colors in the background buffer copy in system memory to calculate the blending.

Now, how do you scroll this puppy?  Well, scrolling little amounts is covered by
using a different starting offset in the background buffer when you blit to the
back buffer.  Once you reach the edge of the background buffer, you will have to
copy in a new row and/or column of your 128x128 background image tiles.  The
worst case scenario is when you move diagonally through the corner of the
background buffer, in which case you will have to copy both a row and a column
of tiles.  A single 128x128 tile is 32k (32,768 bytes).  A single row or column
is 32k x 8 tiles, or 262,144 bytes (256 k).  Both a row and a column together
makes 491,520 bytes, which is still less than a 640x480 screen.  You can even
break this blitting job up over several frames if you use the next to the
last/first row/column as your boundary line for when to update the background
buffer.

Anyways, the new info you use to fill in these rows and columns can be stored in
memory compressed or uncompressed, read from disk, or whatever.  To scroll you
just update your axis in the double axis buffers, obtain the new info, write the
new info into the system memory z buffer, the system memory background buffer,
and the video memory background buffer.  If your data is compressed, you can
decompress into the system memory  background buffer, and then blit the
uncompressed image into the video memory background buffer.  If you don't plan
on doing any alpha blending, then you can eliminate the system memory background
buffer and just work directly with the video memory background buffer.

The fun part comes when you try to add animation to the background tiles.  I
haven't figured out exactly how I'm doing this yet, but it will likely entail
writing the sprites of animation directly to the back buffer from sprite data
stored in system memory.  This is only one of several ways to approach this
problem.

* tile based movement and collision detection.  Since your graphics will be
built from 2d panes of graphics instead of tiles, you will need to store the
tile and collision info separately.  Essentially what this means is creating a
separate tile map that contains collision info instead of graphic info.  This
will also be where you store your object info.




...

That's what I'm thinking of so far.  I'll likely take a stab at implementing it
after a week to a week and a half, and I figure it will take about three weeks
to convert my current tile based engine over to the new graphic approach.  Then
of course there are still other issues such as front wall removal, etc.  Also,
I'm considering storing the background graphics as large sprites instead of
128x128 tiles, and I will simply draw clipped sprites into the background buffer
when it comes time to create new columns and rows.  Don't know how well this
will work though...


It's late, I'm tired, and I doubt I'll make much more sense tonight (if indeed
the above makes sense to you in the first place (^_^) ).

Later,
Michael Duffy
mduffy@ionet.net
Article 191492 of rec.games.programmer:
From: "John Mancine" <jmancine@voyager.net>
Newsgroups: rec.games.programmer
Subject: Re: Tile Based vs Non Tile Based
Date: Mon, 15 Jun 1998 20:45:13 -0400
Organization: A poorly-installed InterNetNews site


>Baulder's Gate draws the graphics one screen at a time instead of one tile
at a
>time.  The movement system is based on an invisible hex (I assume hex) grid
laid
>over the graphic.  Passing behind walls can either be accomplished by
breaking
>individual scene elements out at different layers, and using them to
overdraw
>characters that pass behind them, or the engine can have a z-buffer for
each
>image and use that to composite the characters into the background.
>
>I'm seriously considering implementing a z-buffered sprite engine that uses
a
>single image for the background (well, multiple non-overlapping tiled
images),
>and then z-buffers the character and object sprites in.  I've been putting
some
>thought into it since looking at how nice Final Fantasy VIII's screens are
and
>thinking that it will probably be easier to do good graphics as a single
image
>rather than in individual tiles.  Also, my artists are not too thrilled
with the
>entire tile idea, and tiles are tough to do in a 3D rendering package.


I know exactly what you are saying. My 3D artist hasn't liked doing the iso
tiles at all either. Simply because you can't really dive into the details
as much as you can if you have more of a canvas to work on.

One thing I don't get about not using tiles is how is the scrolling of the
screen handled? (not even thinking about doing 'paged' scrolling... that is
pretty cheap looking IMO)
How would it work? Would you have the whole 'world' divided up into
1000x1000 sized "chunks" of images and then load these on the fly? Obviously
you can't load them all at once.

Can you elaborate a little more? Because I am very interested in doing this.
And it would be the perfect time to do it in my project.

Thanks,
jrm
Email me at redblobgames@gmail.com, or tweet to @redblobgames, or post a public comment: