Master Object List

Archived from groups: rec.games.roguelike.development (More info?)

Hi,

I'm new to the scene and haven't posted any topics here. I have a
'rogue' in development and would like some advice on what I should do.
FYI : I'm using C++ and pdcurses on a windows machine.

I have an engine that makes random levels and uses a single game
object, the player, who can move around within the bounds of the level.
The player has a field-of-view and the screen scrolls to center the
player in the screen as he moves. Now I want to add more objects to the
game, like pillars, and monsters and gold ...

My question is : How should I go about handling the storing and
accessing of objects in my game?

I was thinking about using a 2-d map, or something like maps within a
map. I could access the main map with the coordinates of a tile, then
access the objects on each tile individually with a name or ID. Each
tile needs a way to store many objects, so I can make piles of treasure
on a single tile.

Is there a 'best way' to do this? I really don't want to waste time.

Also, I understand using an object-pointer-abstraction layer is a good
thing for saving the master object list when a player saves the game.
Should I be thinking about this as I make my objects?

Thanks for any help. I'll be honest in saying I've been stuck on this
for a while now and can't move forward until I know these answers. I
can't decide for myself what I should do, so I'll ask the best.

Sincerly,

Andres

Archived from groups: rec.games.roguelike.development (More info?)

Hail Jeff,

About the Tiles, how do you store them as a single int? Is it that the
first 16 bits are used for coordinates and the last 16 are used for
flags?

What would you recommend I use for the object list, a map?

What about the pointer layer, just another map? And does each object
have an 'PointerID' to use this layer?

And finally, is there any critical arguement to using object lists in
levels? I can think of one bad thing : what if you want to teleport an
object between levels? Like the player can summon a unique game object
....


Thanks for your help.

Andres

P.S. I have a 'dungeon' object that holds the 'level' objects. The
player resides in the dungeon object.

Archived from groups: rec.games.roguelike.development (More info?)

Dnia 10 Jun 2005 18:51:05 -0700,
Andres napisal(a):

> Is there a 'best way' to do this? I really don't want to waste time.

Definitely there's no 'best' way. It all depends on your preferences, the
way your algorithms work, the way you draw the map on the screen, count
FOV, determine next move for the monsters, etc.

I can tell you about my approach. There are 4 kinds of elements on the
map:
* Terrain -- every square has one;
* Objects -- like doors, traps, etc., those are pretty rare on the map;
* Items -- these can be moved around and there can be many of them on
a square;
* Monsters -- these will usually move around all the time, and there is
only one per square most of the time;

Since every square has it's terrain, I store it in 2d array of ints, every
int contains the index into the array of terrain kinds. You don't need
to store the positions there -- you never need it at this level.

Now, the Objects, Items and Monsters are pretty sparse on the map, and on
top of it will move or change it's state easily (open/close door). On top
of that, you can have many of them per square. Storing them in the square
directly is a waste.

So, there are lists of Objects, Items and Monsters on the given level.
Every element of these lists must also store the position. Every time
you want to know what items lie on given square, you have to iterate
trough the list of all items and take the ones with proper position set.
It might seem slow, but you won't have to do it often.

Now, to the operations you'll want to do on the map. Here's a short list:
* calculate FOV
* display on the screen
* check whether movement is legal
* check items/objects/monsters around monster
* pick/drop items
* open/close doors (and generally change other objects)
* move monsters

It's not a full list, but these are the most common operations. You'll
have to make them fast -- at least the ones that happen often.

Displaying the map on the screen seem to be important here, but it doesn't
really occur that often. In fact, it's very rare -- it only occurs once
per player's turn -- provided you refresh whole screen every turn.

Now, FOV and legality of movement are important. Calculating FOV is
already slow, and you don't want to slow it down further. Legality of
move (is this square blocked) will be done often in your AI routines. You
want them fast. But both of them depend not only on terrain, but also on
the objects on the map. Looking up objects is slow, so you don't want to
do it.

You can use a 2d array of flags. Again, if you use ints, you can fit more
than enough flags there. For start, let's have HAS_OBJECT, HAS_MONSTER and
HAS_ITEM flags. Then you don't have to do lookups for every square -- only
for the squares that really contain something, and these are pretty rare.
Every time you add/remove anything form the square, you update the flags.

But you want those operations to be even faster. FOV code would still have
to check the kind of object if there's one, and it's state (open doors
don't block light, closed ones do). So, you can add more flags.
BLOCKS_LIGHT, BLOCKS_MOVEMENT are probably a good choice. You have to
update them on the square every time you open/close door, or tunnel trough
wall, etc.
Now, your FOV and path-finding only use this array of flags. If your
monsters are supposed to be able to open door, you might consider adding
an OPENABLE flag for the path-finder.

If your game is player-centric, you can also add IS_VISIBLE and IS_MAPPED,
to mark which squares are in the player character's FOV and which are
remembered on his map. Monsters can use IS_VISIBLE to check whether they
can see the player character.

Moving items and monsters, and modifying the objects is straightforward --
just change appropriate values in their objects. But you have to remember
to update the flags both on the square you're moving from and on the one
you're moving to.

Checking the monster environment has a trick to it. Normally you'd
probably scan a part of map around the monster and check the
items/objects/monsters there. This is bad with our structure, because
you're doing multiple lookups. And you scan awful lot of empty squares,
which is unnecessary.

Instead, just iterate trough the lists of items/monsters/objects
(depending on what you're looking for) and select the ones that are close
enough (calculate the distance using their stored positions) and are of
the interesting kind (monsters will probably just ignore most of them).
Then, for the items that are left, just calculate LOS to see whether
monster can see it. You can use IS_VISIBLE if the monster you're looking
at is the player character, otherwise just draw a line and see whether
it's blocked.

This approach is much faster than scanning even on large maps.

The last thing is displaying the map. You can have it done in variety of
ways, I'll describe two of them.

The first one is similar to checking monster environment. First, scan the
area to be displayed and show all the terrain (you can skip the squares
that have HAS_* flag set for now). Then iterate trough the lists and put
the missing elements. Check whether they are visible first (just look at
their position and the square's flags). This procedure plays nicely with
all sorts of 'detect monsters' spells and telepathy.

The other way is more traditional. Have yet another 2d array, in which you
store the looks of the squares (again, probably just an index to the table
of all possible looks). You update this array every time something changes
on the square. Then you just display the array on the screen when needed.
(ok, if you had no scrolling, you could use the screen directly, without
the array).

Now, it's only an example of one possible way to do it. I hope you get
what I mean -- you have to design your data structures with the operations
you're going to do on them in your mind. Don't copy blindly what
I described here -- just look on what you want to do and design your own
approach (ok, if it comes up identically as mine, you can copy it ).

Whew, this was a lot of typing. Shall I put it on the wiki?

--
Radomir `The Sheep' Dopieralski @**@_
(Uu) 3 Sigh!
. . . ..v.vVvVVvVvv.v.. .

Archived from groups: rec.games.roguelike.development (More info?)

Andres wrote:
> Hail Jeff,
>
> About the Tiles, how do you store them as a single int? Is it that the
> first 16 bits are used for coordinates and the last 16 are used for
> flags?

Why do the tiles need to know their cooridinates? The coordinate is
implicit from where they are stored in the map.

I actually store tiles in POWDER as a single char. The value of a tile
is an index into a list of generic tiles. Thus, the one "Grass Tile
Definition" might be index 10, so any tile with a value of 10 will
share this definition. You can see this in code in You Only Live Once.

Flags are stored separately in my design, but nothing is wrong with
having a 16 bit flag and 16 bit tile index.

Note that even if you want unique tiles, this system still works. You
just use a copy on write semantic to allocate new tile indices when
needed.

The vast majority of tiles in a roguelike are exactly the same. All
floor tiles are equivalent, so why create a new structure for each one?

Some argue that you want to store "Amount the person has dug down" or
similar meta data. I would argue that this can be handled
transparently without making tiles standalone classes. POWDER has
smoke effects which can wander the map and decay. I merely store the
fact that tile has smoke in its flags strucutre. The data for the
smoke is stored in a separate structure, so I only need a copy for
every tile with smoke, not for every single tile.

> What would you recommend I use for the object list, a map?

The operations you want to perform on an object list is:
1) Loop over all objects
2) Find all objects at (x,y)
3) Find all objects within distance r from (x, y)

Some form of spatial partitioning tree would be ideal. However, this
is all overkill for roguelikes. A lowly linked list of objects works
as a first approximation. Optimize later.

> What about the pointer layer, just another map? And does each object
> have an 'PointerID' to use this layer?
>
> And finally, is there any critical arguement to using object lists in
> levels? I can think of one bad thing : what if you want to teleport an
> object between levels? Like the player can summon a unique game object
> ...

You remove the object from one level and add it to the next.

oldmap->dropItem(item);
item->setPos(newx, newy);
newmap->acquireItem(item);

> P.S. I have a 'dungeon' object that holds the 'level' objects. The
> player resides in the dungeon object.

Opinions vary on whether the player should be the same as a monster.
This format is good if you want the player to be unique. If you want
them to be the same as monsters, you might want the player inside the
level object.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

Archived from groups: rec.games.roguelike.development (More info?)

The Sheep wrote:
> Dnia 10 Jun 2005 18:51:05 -0700,
> Andres napisal(a):
>
> > Is there a 'best way' to do this? I really don't want to waste time.
>
> Definitely there's no 'best' way. It all depends on your preferences, the
> way your algorithms work, the way you draw the map on the screen, count
> FOV, determine next move for the monsters, etc.

Good writing! This is an excellent summary of how to approach this
problem.

> Displaying the map on the screen seem to be important here, but it doesn't
> really occur that often. In fact, it's very rare -- it only occurs once
> per player's turn -- provided you refresh whole screen every turn.

One note: Your map needs to be refreshed everytime you wait for player
input.

This is almost the same as what you say, except includes the case of
when --more-- prompts come up.

Theoritically on an infinitely fast machine this is identical to always
refreshing (assuming no animation).

> Whew, this was a lot of typing. Shall I put it on the wiki?

Yes. This is a common enough FAQ that it would be nice to have
somewhere to direct people.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

Archived from groups: rec.games.roguelike.development (More info?)

Thanks for the contributions. I now have a good idea on how to approach
this.

I just went into my Tile class, deleted references to row and column
and recompiled my project fine. I guess they were leftovers from a
previous build. Now my Tiles are atomic, in that they only contain a
flag int.

Right now, I use inheritence with a base 'Object' class: an Object just
contains 2 ints and getters/setters methods for them. I wanted to make
is so that, "Everything in the game is an 'Object'." That way,
everything can be contained on one master list. I am now thinking I
have to add a 'flags' int to the Object class too, so that I can
iterate through the master list of Objects and I can find what I'm
looking for(As The Sheep was saying). Also, I'll need this flag to
identify what kind of downcast to use on the Object pointer. The next
level of classes in my game, the classes that directly inherit the
Object class, are MaterialObject and ImmaterialObject. And so, a Player
and Monster are just MaterialObjects. I hope this is making sense,
because it does to me. But I'm relatively new at programming too, so
please bare with me.

Jeff also mentioned animations and refreshing the screen. I'm wondering
: If I want to make a fireball that travels some tiles, hits the target
and is followed by a conflagration, do I make this animation with using
a Timer?


Thanks again for your input,

Andres