Dangling pointers and saving references to file in C.
MBrenaman
really didn't want to make this post, but here we go...
I have a problem with the roguelike I'm currently programming in C. As
you can probably tell by the title, it pertains to dangling references
and saving references to file.
The first problem is dangling references. For instance, an actor (an
actor is a data structure used for the player or his/her friends and
foes) poisons another actor. A reference to the poisoner most be
maintained so that experience points can be given to the poisoner if the
actor who received the poison dies (from the poison specifically). Or if
the player dies from a poisoner that he/she kills before he/she is
killed from the poison, how will I put together the high score string
"... was poisoned by a giant poisonous spider."
A second example is with summoning minions. The minions must maintain a
reference to their leader so they know who to follow. If the leader is
killed and cleared off the map's actor linked list, there will be yet
another dangling pointer.
Another problem I have down the same vein is how to save such pointers
to file and restore them properly. I suppose I could use unique ID
numbers for each actor and restore the pointers saved after every actor
has been loaded from the save file, but I'm not sure about this.
I read what I could find on reference counting, and I am unclear about
the best way to implement it for my situation. Also I'm still unclear as
to how to restore actor references that exist within an actor.
Only actors would need reference counting. All actors in use on a map
are kept in a linked list within the map structure. I'm not really sure
what to do about reference cycles, which could potentially occur.
In any event, I was seeking advice from anyone who has tackled these or
similar problems and could offer help, advice, or at least some
reference material.
Thanks in advance,
MBrenaman
Perdurabo
Caveat: the following applies to Delphi (i.e. Object Pascal), not C,
so I don't know how useful it will be to you.
In the old version of Kharne, and its an architecture I'll likely
carry across to the new version, I solved this problem in a slightly
lazy but highly effective manner (its one thing I did get right with
the old version). As a bit of background, I stored monsters (well,
TCreature classes) in a TObjectList (the rough equivalent of a Vector
in C++ I guess) - but I didn't use pointers at all (after a few years
of C and C++, I'm now allergic to them), but rather stored the
absolute index value of related monsters.
I'll give you an example to make it clear.
Let's say Monster A, in position 12 in the list, summons monster B,
who being newly created, is in position 19 of the list (there was 18
monsters in the list before B was summoned). The monster class
contains a "Parent" member integer, and this, for Monster B, simply
stores the index of Monster A, e.g. 12. *Even if Monster A dies*. Its
then easy to check the status of its parent and react accordingly. The
constructor for the Monster Class sets the Parent to -1 by default
unless the Parent is specified.
Now, this isn't terribly memory-efficient, in that the monster list
grows over time, and is largely filled with dead monsters. At periodic
intervals however, dead monsters are effectively scrubbed from the
list and replaced with mimimial placeholder obhects, to ensure that
the IDs are consistent. This does mean however, that eventually, the
monster list will, should the game last long enough, contain say, a
bunch of placeholder entries and then from positions 456 to 490 the
live monsters, but on modern Windows systems (where Kharne was
targred), a few bytes extra aren't noticed.
This system is exceedingly fast however (ridiculously fast in fact - I
suspect the Delphi compiler converts this to pointers during
compilation), as all accessing to the ObjectList is done via absolute
addressing, and is quite easy to serialise also.
In the new version, I might add additional housekeeping to effectively
refactor the IDs on occasion to improve the performance even further.
Best,
P.
uschkinre...@gmx.de
You don't need to have any reference counting. Just use a basic object
(e.g. GameObject or Entity) and give it a Id. The Id is static within
the class and is incremented for every instance. Now you can save the
Id of the object for every pointer. For loading the data, you first
have to load and create every object with the proper id, and then you
go through each id for a pointer and set it to the proper object.
There is no magic involved :-)
You just have to keep track, if the actor who poisoned someone is
still alive; otherwise it's no more valid. There comes reference
counting into play (you could store a list of pointing actors for each
actor, and if the actor is deleted you set every pointer to null), or
use a table outside the actors (as i did in c++).
Greetz
GreenNight
Several ways.
1) double link.
In this case it would mean that poisoners, bosses and other special
creatures should have one (or more) list of creatures affected by
them. Need to clear the parent creature? First go to each child and
clean it (set the pointer to NULL or 0), then delete the parent (free
its memory).
2) counter.
Parent creatures have one (or more) counters to count how many
creatures are affected by them. If the parent has the dead status and
its counter's value is 0 you can delete it. If you are on a child
check the parent, in case of a dead parent decrement the counter and
clean the pointer. Just keep the game running and eventually you'll
free the parent's memory.
3) time intensive.
When you want to delete a register go through the whole list of
monsters and check every pointer to see if it points to the parent, in
that case clean the reference. After finishing the list clean the
memory.
Option 2 would let you do things like "Player was killed by a giant
spider that was already dead", but with a little effort you can add
that effect to any other of the methods.
Keep the good work.
Brog
It might be worth keeping a list of the ids you free up when you
"scrub" and then reuse those for the next few objects created.
Perdurabo
<snip>
>
> > Let's say Monster A, in position 12 in the list, summons monster B,
> > who being newly created, is in position 19 of the list (there was 18
> > monsters in the list before B was summoned). The monster class
> > contains a "Parent" member integer, and this, for Monster B, simply
> > stores the index of Monster A, e.g. 12. *Even if Monster A dies*. Its
> > then easy to check the status of its parent and react accordingly. The
> > constructor for the Monster Class sets the Parent to -1 by default
> > unless the Parent is specified.
>
> > Now, this isn't terribly memory-efficient, in that the monster list
> > grows over time, and is largely filled with dead monsters. At periodic
> > intervals however, dead monsters are effectively scrubbed from the
> > list and replaced with mimimial placeholder obhects, to ensure that
> > the IDs are consistent. This does mean however, that eventually, the
> > monster list will, should the game last long enough, contain say, a
> > bunch of placeholder entries and then from positions 456 to 490 the
> > live monsters, but on modern Windows systems (where Kharne was
> > targred), a few bytes extra aren't noticed.
>
> It might be worth keeping a list of the ids you free up when you
> "scrub" and then reuse those for the next few objects created.- Hide quoted text -
>
> - Show quoted text -
Could be, but I don't think its that big a deal. Its next to no extra
memory usage, and not reusing IDs prevents any possible corruption.
Best,
P.
Pfhoenix
> memory usage, and not reusing IDs prevents any possible corruption.
But I wouldn't consider keeping absolute indices into an array a good
design decision at all.
Adeo manages reference serialization (which is what we're talking
about here) as such : every class that needs serialization at all
(which includes all gameplay relevant classes) subclasses Object,
which has a string UniqueObjectName. The UON gets built by
concatenating the class name with a randomly generated unsigned int.
When it comes time to serialize, references are saved by UON, and when
a map is loaded, after the entire map is loaded, the engine does a
reference clean up that provides all objects a chance to lazily
restore references by matching up against UONs.
I've gone through 3 major revisions of Adeo's serialization subsystem.
It's quite robust at this point, fast, and works rather well. It's a
bit more complex than you may need, since it's possible for maps to be
referenced and loaded like any other object (and some gameplay objects
reference objects on other maps entirely, like telepads), but if you
go with "every map is an island", it gets simpler and is about perfect
for what you need.
- Pfhoenix
http://adeo.pfhoenix.com
Nathan D. Jerpe
"MBrenaman" <mbre...@gmail.com> wrote in message
news:g13h12$f5s$1...@registered.motzarella.org...
> Hello everyone. I'm a second time poster, long, long time lurker. I really
> didn't want to make this post, but here we go...
>
> I have a problem with the roguelike I'm currently programming in C. As
> you can probably tell by the title, it pertains to dangling references and
> saving references to file.
>
> The first problem is dangling references. For instance, an actor (an actor
> is a data structure used for the player or his/her friends and foes)
> poisons another actor. A reference to the poisoner most be maintained so
> that experience points can be given to the poisoner if the actor who
> received the poison dies (from the poison specifically). Or if the player
> dies from a poisoner that he/she kills before he/she is killed from the
> poison, how will I put together the high score string "... was poisoned by
> a giant poisonous spider."
>
Could you use a blackboard? Meaning, instead of requiring all this linkage,
have the poisoner post his accomplishment to the blackboard?
Later on if your hero dies, they can go to the blackboard to find out why.
Cheers,
Nathan
Perdurabo
> > Could be, but I don't think its that big a deal. Its next to no extra
> > memory usage, and not reusing IDs prevents any possible corruption.
>
> But I wouldn't consider keeping absolute indices into an array a good
> design decision at all.
Heh. I didn't say it was perfect, but it does the job, does the job
quickly, and it meshes well with my chosen collection object: Delphi's
TObjectList (which isn't an array, although it can be accessed as
such).
>
> Adeo manages reference serialization (which is what we're talking
> about here) as such : every class that needs serialization at all
> (which includes all gameplay relevant classes) subclasses Object,
> which has a string UniqueObjectName. The UON gets built by
> concatenating the class name with a randomly generated unsigned int.
> When it comes time to serialize, references are saved by UON, and when
> a map is loaded, after the entire map is loaded, the engine does a
> reference clean up that provides all objects a chance to lazily
> restore references by matching up against UONs.
I actually do/am intending to do something similar with items. Each
item has its own unique identifier that allows me to recreate the
object (and all its properties) from a simple string - since my item
classes inherit from the same base class as my monster classes (and
share the same interfaces), it would be possible to extend this to
monsters, but I've held off from doing so due to the amount of
variable data that monsters store (much more than items).
>
> I've gone through 3 major revisions of Adeo's serialization subsystem.
> It's quite robust at this point, fast, and works rather well. It's a
> bit more complex than you may need, since it's possible for maps to be
> referenced and loaded like any other object (and some gameplay objects
> reference objects on other maps entirely, like telepads), but if you
> go with "every map is an island", it gets simpler and is about perfect
> for what you need.
*nods*.
I expect to rewrite this sort of functionality in Kharne many times.
Its the nature of the beast, isn't it? At the moment, dungeons are
stored as simple multi-layered arrays of ints/booleans.
Best,
P.
Pfhoenix
> item has its own unique identifier that allows me to recreate the
> object (and all its properties) from a simple string - since my item
> classes inherit from the same base class as my monster classes (and
> share the same interfaces), it would be possible to extend this to
> monsters, but I've held off from doing so due to the amount of
> variable data that monsters store (much more than items).
There are one or two classes that serialize out to a single string
(LightSource does, as it's only 5 ints in total), but they are
essentially utility classes. All other serializable classes write out
to full blown XML-like blocks of <property=value> lines (in plain text
right now; later on, the files will get encrypted). If you store
objects in single lines, how do you handle referencing one object in
another without duplicating the object in memory?
- Pfhoenix
http://adeo.pfhoenix.com
Gerry Quinn
says...
> Hello everyone. I'm a second time poster, long, long time lurker. I
> really didn't want to make this post, but here we go...
>
> I have a problem with the roguelike I'm currently programming in C. As
> you can probably tell by the title, it pertains to dangling references
> and saving references to file.
>
> The first problem is dangling references. For instance, an actor (an
> actor is a data structure used for the player or his/her friends and
> foes) poisons another actor. A reference to the poisoner most be
> maintained so that experience points can be given to the poisoner if the
> actor who received the poison dies (from the poison specifically). Or if
> the player dies from a poisoner that he/she kills before he/she is
> killed from the poison, how will I put together the high score string
> "... was poisoned by a giant poisonous spider."
>
> A second example is with summoning minions. The minions must maintain a
> reference to their leader so they know who to follow. If the leader is
> killed and cleared off the map's actor linked list, there will be yet
> another dangling pointer.
>
> Another problem I have down the same vein is how to save such pointers
> to file and restore them properly. I suppose I could use unique ID
> numbers for each actor and restore the pointers saved after every actor
> has been loaded from the save file, but I'm not sure about this.
I recommend this. In fact, consider avoiding pointers altogether and
just using index numbers.
There are 'safe pointer' options available too, but sticking to indexes
is simpler. It will be efficient enough if you are not doing too much
searching through lists.
> I read what I could find on reference counting, and I am unclear about
> the best way to implement it for my situation. Also I'm still unclear as
> to how to restore actor references that exist within an actor.
>
> Only actors would need reference counting. All actors in use on a map
> are kept in a linked list within the map structure. I'm not really sure
> what to do about reference cycles, which could potentially occur.
>
> In any event, I was seeking advice from anyone who has tackled these or
> similar problems and could offer help, advice, or at least some
> reference material.
All my actors in Lair live on C++ vectors, and are accessed by indexes.
One downside of this is that you will need a periodic clean-up cycle or
the vector will grow indefinitely, consisting of mostly dead monsters.
But most roguelikes can handle this easily by just clearing everything
when a new map is entered.
That said, I don't hold any sophisticated references either. If you
poison a monster you get a message, and subsequently the monster has a
'poisoned' status. Killing doesn't give experience, so nothing special
happens when it dies except a message if it's in view. If experience is
the only criterion, you can award it for any death unless your actors
are always killing each other independently of the player's actions.
My minions are basically just wired to kill enemies. They don't even
follow their master! But if they did, it would be by looking for a
particular index, which would be either a living or dead monster at any
time.
- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>
Gerry Quinn
@c65g2000hsa.googlegroups.com>, perdu...@googlemail.com says...
> Let's say Monster A, in position 12 in the list, summons monster B,
> who being newly created, is in position 19 of the list (there was 18
> monsters in the list before B was summoned). The monster class
> contains a "Parent" member integer, and this, for Monster B, simply
> stores the index of Monster A, e.g. 12. *Even if Monster A dies*. Its
> then easy to check the status of its parent and react accordingly. The
> constructor for the Monster Class sets the Parent to -1 by default
> unless the Parent is specified.
>
> Now, this isn't terribly memory-efficient, in that the monster list
> grows over time, and is largely filled with dead monsters. At periodic
> intervals however, dead monsters are effectively scrubbed from the
> list and replaced with mimimial placeholder obhects, to ensure that
> the IDs are consistent. This does mean however, that eventually, the
> monster list will, should the game last long enough, contain say, a
> bunch of placeholder entries and then from positions 456 to 490 the
> live monsters, but on modern Windows systems (where Kharne was
> targred), a few bytes extra aren't noticed.
That's what I do. But when you change level, the vector is cleared, so
it never grows all that much.
- Gerry Quinn
Perdurabo
Ah, I should have explained further. The unique IDs are used for
stacking purposes as well, but I intend to, for serialisation, to
write out their position in the objectlist as well as the Unique ID.
Also, items, unlike monsters, are self-contained - they don't need or
use or contain links to other items..
Best,
P.
Jeff Lait
> Hello everyone. I'm a second time poster, long, long time lurker. I
> really didn't want to make this post, but here we go...
>
> I have a problem with the roguelike I'm currently programming in C. As
> you can probably tell by the title, it pertains to dangling references
> and saving references to file.
Which both can be solved in the same manner.
> The first problem is dangling references. For instance, an actor (an
> actor is a data structure used for the player or his/her friends and
> foes) poisons another actor. A reference to the poisoner most be
> maintained so that experience points can be given to the poisoner if the
> actor who received the poison dies (from the poison specifically). Or if
> the player dies from a poisoner that he/she kills before he/she is
> killed from the poison, how will I put together the high score string
> "... was poisoned by a giant poisonous spider."
A C++ solution is boost::shared_ptr and boost::weak_ptr, but I
wouldn't recommend it in this case as you want to solve the
serialization problem anyways.
> A second example is with summoning minions. The minions must maintain a
> reference to their leader so they know who to follow. If the leader is
> killed and cleared off the map's actor linked list, there will be yet
> another dangling pointer.
>
> Another problem I have down the same vein is how to save such pointers
> to file and restore them properly. I suppose I could use unique ID
> numbers for each actor and restore the pointers saved after every actor
> has been loaded from the save file, but I'm not sure about this.
Why not use the unique ID numbers *always*? Never store creature
pointers, store creature IDs. Ie, creature ID #53 poisoned me.
> I read what I could find on reference counting, and I am unclear about
> the best way to implement it for my situation. Also I'm still unclear as
> to how to restore actor references that exist within an actor.
You have a table which maps unique id to object pointer. Attach to
that table the reference count in addition to the pointer. Every time
someone stores a unique id, they increment the relevant reference
count.
The only sane way to do this with C++ is to use a special "monster
pointer" which stores the unique id internally. It can then handle
all the house keeping in its constructor/destructor/assignment
operators and remove most sources of bugs. Another advantage is you
can overload -> to have it *act* like a monster pointer.
All that gets complicated quickly, might be best to just not bother
with reusing data and just deleting the monsters when you are done
with them. Whenever you access a unique id, you can discover that the
underlying pointer is now null, so decide to clear out the unique id.
I do this in POWDER because I aggressively delete monsters before all
their references are cleared. However, any stale references will
automagically go null as soon as they are referenced. You can see the
code in mobref.cpp.
> Only actors would need reference counting. All actors in use on a map
> are kept in a linked list within the map structure. I'm not really sure
> what to do about reference cycles, which could potentially occur.
For C and C++ it is very useful to think of there being a "real"
pointer to an object and then many "weak" pointers. The real pointer
*owns* the object. The rest just refer to it. In this system, the
real pointer is the one that decides to allocate or delete, the weak
pointers start seeing Null as soon as the real pointer is deleted.
> In any event, I was seeking advice from anyone who has tackled these or
> similar problems and could offer help, advice, or at least some
> reference material.
Switch to unique ids. This is, ironically, a step back to how ancient
C roguelikes worked. The trick to avoid the problems they had are:
1) Abstract looking up an id to get a pointer. Never write
global_monsters[uniqueid]. Instead, lookupMonster(uniqueid). By
having only one spot that deals with the translation, it is trivial to
make the array variable sized, or replace it with a hash table, or
whatever.
2) Typesafe the id. Don't pass around foo(int uniqueid). Make the
unique id its own type - it isn't an integer and should never be
exposed as such to the rest of the program! Doing so results in
embarrassing calls like foo(53).
3) Don't reuse ids. You *can* do this if you build the appropriate
framework to do reference counting automatically (never do reference
counting by hand as it is too error prone). However, I'd not
recommend it unless you have only 256kb of memory. Save yourself the
heartache and make them unique over the lifetime of the program. (One
interesting time you can easily reap ids is after a load....)
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
zai...@zaimoni.com
> Hello everyone. I'm a second time poster, long, long time lurker. I
> really didn't want to make this post, but here we go...
>
> I have a problem with the roguelike I'm currently programming in C. As
> you can probably tell by the title, it pertains to dangling references
> and saving references to file.
In summary of what others have posted.
> The first problem is dangling references. For instance, an actor (an
> actor is a data structure used for the player or his/her friends and
> foes) poisons another actor. A reference to the poisoner most be
> maintained so that experience points can be given to the poisoner if the
> actor who received the poison dies (from the poison specifically). Or if
> the player dies from a poisoner that he/she kills before he/she is
> killed from the poison, how will I put together the high score string
> "... was poisoned by a giant poisonous spider."
The reference to the poisoner is a *means* to the end of correctly
allocating experience.
In any case, a raw pointer is a rather obnoxious choice -- you'll need
some way of globally reviewing your
data structures before deleting the pointer.
> ....
>
> Another problem I have down the same vein is how to save such pointers
> to file and restore them properly.
In general, you don't restore pointers properly from a file. Not even
smart pointers.
Save something else that you can properly restore from a file.
> I suppose I could use unique ID
> numbers for each actor and restore the pointers saved after every actor
> has been loaded from the save file, but I'm not sure about this.
What are the disadvantages to this for your specific project?
Both unique ID numbers, and positional indexes into a linear data
structure, work.
Unique ID numbers should be more robust once the infrastructure is
implemented.
> Only actors would need reference counting. All actors in use on a map
> are kept in a linked list within the map structure. I'm not really sure
> what to do about reference cycles, which could potentially occur.
This is your real problem: it denies fast access (no worse than O(log
n)) to any item in the structure by one of position, or particular
sorting index.
Writing a savegame is reasonable, but will not scale well:
* save the linked list first (fine)
* convert all pointers to linear indexes from the list beginning, as
you save the pointers into the linked list. (non-performant, may want
to explicitly trace from the linked list beginning to identify
pointers not actually in the linked list). You will need to reserve
an index for NULL pointers.
Reading in the savegame is routine, as the linear indexes can be
converted back into linked-list pointers.
Ray Dillinger
> In article <151f5ad8-2e2b-4cba-a92c-164017091fb6
> @c65g2000hsa.googlegroups.com>, perdu...@googlemail.com says...
>
>> This does mean however, that eventually, the
>> monster list will, should the game last long enough, contain say, a
>> bunch of placeholder entries and then from positions 456 to 490 the
>> live monsters, but on modern Windows systems (where Kharne was
>> targred), a few bytes extra aren't noticed.
>
> That's what I do. But when you change level, the vector is cleared, so
> it never grows all that much.
I dunno... that may be perfectly true in your game, but if you
want to support tactics like what the nethackers call 'pudding
farming' you may wind up with a situation where that list is
not just hundreds, but millions of entries long. Some players
camp on one level indefinitely, farming breeding or summoning
monsters, especially in games that give a per-monster reward
(eg, gaining divine favors by sacrificing the monsters, having
them drop potentially useful stuff when they get killed, or
awarding useful experience indefinitely).
If you're an anti-farming kind of gamemaster, you may institute
rules like: breeding monsters never have death drops, Gods aren't
pleased by overly repetitive or easily-killed sacrifices, and
after you've killed your thousandth foo, you stop getting
experience from foo killing. But if you want to keep a wide
variety of legitimate strategies, including farming, open in your
game, you may have literally millions of things on that list,
all while the player has not left the level.
That said, a million pointers is only 4 megabytes on a 32-bit
machine, or 8 megabytes on a 64-bit machine, so odds are the
technique still works -- just on a larger scale than you may
have been thinking of.
Bear
MBrenaman
> Hello everyone. I'm a second time poster, long, long time lurker. I
> really didn't want to make this post, but here we go...
>
> I have a problem with the roguelike I'm currently programming in C. As
> you can probably tell by the title, it pertains to dangling references
> and saving references to file.
>
Thank you everyone for your valuable input. It has been extremely
helpful to me and hopefully to anyone else who encounters the same
problem and can not come up with a solution.
The advice about hard and soft pointers (Jeff) in C/C++ was a bit eye
opening as well. I didn't have a very good CS teacher...
Anyways, I'm in the process of writing out in detail how my system will
work and will post it after I'm done. That way, anyone here can poke
holes in it if they feel like it *snickers*.
But seriously, thank you all again for being so helpful and polite about
this,
MBrenaman
Gerry Quinn
says...
In Lair most of those are the case: spawned or summoned monsters have no
drops, and killing monsters gives no experience or other benefits. In
fact only a fraction of monster types have drops at all. With no health
and mana regeneration either, running my vectors out of memory would be
a pretty impossible challenge :-)
> That said, a million pointers is only 4 megabytes on a 32-bit
> machine, or 8 megabytes on a 64-bit machine, so odds are the
> technique still works -- just on a larger scale than you may
> have been thinking of.
Indeed. One could always compress the data periodically. Or you could
simply have a two stage death marker. After a monster dies and a
certain time elapses, it is considered eradicated, and its space may be
taken by another monster.
You could be lazy and implement this without checking for references, if
you know that your references will expire within a fixed time, or at
least that old references will do nothing terrible if they point to the
wrong guy.
It's a kludgy way of doing it, but probably workable enough.
jot...@hotmail.com
but will probably save you later a ton of code and maintenance hours.
Of course, if you're into the learning experience of creating your own
serialization system (like most of us do/did :), you already have some
pretty good answers so I won't go there :)
It's the Boost Serialization library. You can grab a tutorial here:
http://www.boost.org/doc/libs/1_35_0/libs/serialization/doc/tutorial.html
I'd say it's pretty easy to follow, but of course your mileage may
vary. In a nutshell you just tell it what variables you wanna save/
load for each structure and it will handle all the dirty details,
including pointers.
Jotaf