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