I thought of putting this in the earlier post under "Rendering methods for Tile based map?", but it was getting long and confusing so I''ll post separately. The setup of the map is the same as the previous post - 640x480 resolution and 32x32 pixel cells. The effect I''m trying to get is that of classic 2D console RPGs, as referred to in the last post. The question is, is it Best to separate NPC structures and Map structures? Or how about, say, Map structure (as in array of cell structures) containing a NPC structure? To illustrate what I mean, should I do: ------------------

struct MAP_STRUCTURE
{
   int ID;
   int type;
   .
   . // all other cell variables, like *next pointer for layered cells
   .
   SPRITE_STRUCTURE *npc;
}

MAP_STRUCTURE map[size]; /* whatever the size of the array is, Or use pointer and dynamic allocation. */

------------------- I can see a prob with this if I were to ever fiddle around with these NPCs very often with or without map... but if there are large number of NPCs present at once, having a completely independent NPC structure would mean a LOT of scanning and sorting at render time. Or, perhaps I should just store the ID of the NPC in Map structure. I guess one might say "It depends"... as always. But like I said, what I''m trying to achieve isn''t complex. If in doubt, please think of those RPGs I listed in my previous post. Like Snes FF games. Of course, extending those ideas are good, but for now I want to know Everything that everyone else thinks of these bog standard principles and techniques. Pure and Simple... (sorry to all the UK popstar viewers if that made you puke) Please fire away with all your ideas and experiences, if you would. Thanks again.

I''d say store your NPC seperately in a linked list.

Create your map with two layers.
layer one is always below NPCs.
layer two is tiles that are always above NPCs.

Draw routine is
1) draw base layer.
2) draw sprites/npcs
3) draw overlayer

Some tiles will have to be divided to work, i.e. a tree''s trunk is a solid tile and might be overlapped by a NPC graphic, but the branches/leaves area always drawn on top. Doing this can also allow you to use different top/trunk combinations for variation is you want to. Anything that can both over-lap and be overlapped has to be stored with the NPC/sprite list.

NPC''s should have their own movement routines. When moving you need to check the base layer one tiles to see if they are clear and check intersections against all NPC''s on the map. Each map should have it''s own list of NPC. Or you could just maintain a list of the NPC''s on screen and only update those. You can have seperate lists if you like an on screen and a master list. Only the on screen list gets drawn, they both get updated (so NPC''s walk or do whatever offscreen). In most cases you also only need to update onscreen characters.

This is the simplist and brute force method. Works well as long as the maps do not have an excessive number of NPC''s.
You can update fairly long list of NPC''s on a per frame basis.

If NPC''s can overlap then you have to keep the list sorted properly, which is relatively simple.

Hope this helps/makes sense.











mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com

I'm not sure about overlapping sprites, since I'm doing a side-scroller, but my map structure was originally designed for an RPG, so it should work.
First, you have the map, which is an array of layers. Each layer is a grid of tiles. Then you have an array or entity pointers (usually 256 just cause that's simplest), and use new to allocate only the entities you actually need (a linked list might work better though). Then each entity has a pointer to the map it's on (mainly for collision detection), and a layer index, so you can have entities on different layers if you want. When drawing your map, loop through for each layer, drawing the tiles first, looping through the entity list drawing any that are on the current layer, then going on to the next one.

Hopefully I'm not telling you a bad way of doing it, since I made that up myself, and I usually don't have the best ideas^^

---

-Deku-chan

DK Art (my site, which has little programming-related stuff on it, but you should go anyway^_^)

Edited by - DekuTree64 on May 11, 2001 12:10:29 AM

Well, I was actually referring to the "relationship" between sprite and map Structures in terms of design... rather than the principle behind achieving multi-layered map. I admit the initial post was confusing though - I was going to put it in the other thread under "[] Rendering methods for Tile based map?", but I decided to post it separately to avoid a single message from becoming too long. I''m sorry if posting this way caused a confusion. This post is more like a *sequal* to the other thread I made.

Anyhow, thank you both for replying, I appreciate the efforts

Now, about the actual problem I presented in the first message. If I can''t come up with anything better for this, I''ll take the "middle way", I think. That is, I''m going to have the Sprite Structure independent of Map Structure... then have a pointer in the Map structure to point at the individual Sprite Structure elements. That way, I can just scan the map to find NPCs, at the same time as having the actual Data container of NPCs separate from Map data. I''ve known that this would solve it well enough. But, IMHO, I think this is a bit of an overkill for this sort of "simple" game. Afterall, they were 8 bit and 16 bit console games They can''t be THAT complex, I think. And so I decided to ask people here if you guys have a better idea, which is also simple (at the same time as achieving same effect).

I''ll appreciate any further comments though, if anyone comes up with some

Hrmm, here''s what I''m doing.

I have a map, which is a two dimensional array. This map holds pointers to drawables that are stored in an array elsewhere. These drawables represent TILES. Then in a separate 3D array (non-cubic) I have drawables that represent NPCs and PCs (basically anything added to the map that isn''t part of the main map.) The drawables in the map array never move. The drawables in the second array are referenced by their position in relation to the map array. This means that an NPC is position [0][4][x] in the second array would be in tile [0][4] of the map. The [x] position just says which number in a list it is in, in the second array (hence the non-constrained,non cubic 3D array.)

Of course at this point you have to come up with a fancy filtering algorithm to do object detection, as in, does an NPC see a character and does a character see an NPC. Now if your game doesn''t need to do any AI stuff like this then you won''t need to worry about this.

Well, my explanation is confusing even me, so I''ll stop there. As far as simplicity goes, don''t shoot yourself in the foot later by taking shortcuts now. It is the worst mistake you can make as a programmer/designer. On the flip side, learning when to take shortcuts is the most valuable skill you''ll get as well.

RandomTask

I hate to contribute what may be a poor choice, but I have a one class for the NPCs (state data) and a map with a 2d valarray of NPC pointers.

The built in slice and gslice routines keep my drawing code clean.

Then I''ve got a 2d valarray of bool, same dimensions as the map, that simply tracks ''an NPC is here''. This is mostly for larger sprites that sometimes need a single reference point, but it makes it easy to produce a list of all sprites by slicing the pointer array with the bool array.

It''s not finished yet, so I can''t comment on speed performance. But it''s an option.

Here''s something similar to what I''m doing:

struct TILE
{
int x, y;

...

NPC *npc;
};

struct MAP
{
TILE *data; // acts as a 2-d array after allocated by new
int width, height;

...

LinkedList npc_list;
};

Basically, each tile on the map contains a pointer to an NPC, but all of the NPCs are stored in a linked list. This way, you can cycle through all of the NPCs quickly and perform the AI, etc., and you can also detect if a certain square has an NPC quickly.

Hi again, PugPenguin!
Well, how can we mixture maps & NPCs... let''s see: These''re the problems i have in my CRPG & answers:
1) How can i access ONE NPC in a single map/tile?
- Every tile-> pointer to an NPC structure.
(I don''t use exactly this method, but it''s one of the best, i think)
2) How can i access to ALL my NPCs without using Linked-Lists?
- NPCs: saved in a "linked-array-list" struct. linked-array-list"???
In Pseudo-Code:
[START_PSEUDOCODE]
Record LAL:
Array[0..255] of Pointer; // To an NPC structure
NextLAL: Pointer to LAL;
End;
[END_PSEUDOCODE]
... So i achieve fast access (is better an array access than a linked list access) "compressing" ^_- the linked list.
3) How can i access to ALL VISIBLE NPCs?
- Using "linked-Array-List" with adding/deleting NPCs in the boundaries of my screen when i walk.

Hoping to be useful
RRC²Soft

Alright, thank you everyone.

I''m seeing a pattern here, basically all models use separate NPC structure, with some or no relationship between it and MAP structure.

I guess I''ll go back to my original model of having NPCs stored separately, and then use a pointer in each MAP element to point at the NPC who is currently occupying the cell. I do know this is basically the better model for flexibility. But like I said, I somehow feel that it''s a bit of an overkill for NES/SNES RPG clone. Perhaps I''m wrong... but those consoles didn''t have that much memory I think... so I thought perhaps there was some clever "trick" involved in it.

I think rrc2soft talked about Tales of Phantasia once. That game was so well programmed. I don''t know how SquareSoft managed to squeeze that all in, but most of all, what surprised me was how smooth it was despite the amount of graphics load. The actual layering seems to be the same as all other big name RPGs, but there are little details like pigeons and fish, flying and swimming... those pigeons would take off in a flock when player approach them. And fish jumping out of water and diving back down again with a splash. They must be some NPC objects, from programming point of view. Even now, I ask myself from time to time how Snes managed to run that truck-load. Hence the Wonders of well coded engine, isn''t it.

Talking about Tales of Phantasia, try it using an emulator like ZSNES and play with the layers (using numeric keys). You will see how some NPC techniques are implemented.
I.E.: Fish. It''s an NPC, but it''s written below the blue translucent layer, so it seems that it''s inside water. And when it jumps out of the water, goes to the upper layer (non traslucent) and then falls below that layer again.
And BTW, Tales of Phantasia is not from Squaresoft. It''s from Wolfteam & Namco ^_-.
And...yes, it was veeeeeeery good programmed (please look how implement things with the layers, it''s amazing) _