No Mr. GameObject, I expect you to die.

Newbie & Debugging Questions
#1

I am writing a simple space sim and I have various lists and references that a game object can belong to. For instance, I may have a CapitalShip. It may be in the list of ships in space, the list of ships of a given side, the list ships inside a nebula. References to that ship may also be held by other ships that have it as a target, etc.

The issue I am struggling with, is when a ship dies, is remembering to remove the reference from everywhere i need to so the object is gone. Right now I manually remove it from everywhere it might be, but this doesn’t seem like it would scale very well. I was thinking of adding an Active/Inactive flag that is checked whenever the list is iterated over but it seems like a hack to have to check every time you use a list.

How do other people make sure that objects that are “dead” are removed from everywhere they need to be? I think this is probably an easy problem where I am overlooking an obvious solution, but any advice would be great.

#2

[quote=“actual,post:1,topic:40000”]
I can think of a number of optimisations, which trade off one thing or another - but in the end you should keep it simple, unless it is actually slowing (you) down.

Does your game even need to scale very well? Keep it small, get things done, publish your game. You can always decide to multiply the number of units by factor 10 later, and worry about performance then.

#3

You could operate with listeners implemented by all reference holders, e.g.:

public interface LifeCycleListener {
   onGameObjectAdded(GameObject go);
   onGameObjectRemoved(GameObject go);
}

Or only keep unique numeric IDs instead of game object references and use not-so-nice global or local registries.

I use all kinds of listeners for such tasks. Which has the convenient advantage to have places to perform individual actions for those events.

#4

Well, for Objects, I usually would have one static reference to the list. People might think it is horrible to make a list of Objects a global field. I think when it comes to deleting it from multiple references, it makes the process much easier for me.

Now, I don’t use Objects anymore, and instead create an int for each Object. Then I just track the integers with a simple boolean (Object in [T], Object out [F]). With this method, I don’t need to use static references for anything and I just replace Objects in an array if they are “dead” in my integer list.

#5

[quote=“actual,post:1,topic:40000”]
Not at all. Just factor that out. Create a custom list class which wraps another list; its iterator should use the wrapped list’s iterator, but call remove() on any destroyed instance.

#6

It depends on the type of data structures you are using. For most cases trying to remove dead objects from anywhere they might be can be substituted for discarding dead elements as they are found. Sometimes searching for an object to remove is more expensive than leaving its corpse behind. Sometimes I deliberately leave the corpses behind so that planning and collision checking are done as if they were executed concurrently and then update and dispose objects in a second loop. Some data types (hash-tables, linked-lists, and this thing) make it much more efficient to remove elements given a handle to a data entry than a key or a value. If you’re going to iterate over an entire list anyway once a turn or once every few turns, then it makes the most sense to combine dead object removal with one of those loops.

If you have more complicated structures than Lists, Maps, or Sets, then it might be necessary to remove elements immediately. (An event based system would probably be easiest in this scenario.) But on the other hand it might be slow to remove things one at a time as they die. Deferred removal would save on slow one at a time removals or updates, but it’s basically the same strategy as removing during iteration and still requires corpses to stick around for a while.

If the data structures aren’t meant to be looped over and are used for something else (like discovering nearby neighbors or some other search operation) then the last strategy I can think of is keeping a Set of recently removed items. Then if a search for your 3 nearest neighbors included only one live object you could get the next two closest and so on until you found 3 live objects. That only works if you expect it to be more likely to return lists of live objects than dead ones and if removing elements were too slow.

By the way, it sounds like you’re using lists as your default data structure. If order is unimportant, then don’t use ArrayList or LinkedList. Chances are good that an array based bag or generic hash table could cover most scenarios and those are well suited for iterator based removal (the first strategy).

#7

Thanks everyone for the responses. What I’ve been working on is a hodgepodge of some of the ideas here. Everything that is updated each frame implements the Updatable interface which includes a method shouldUpdate() that if it evaluates to false if its dead. When I run through the list of Updatables, I remove anything where shouldUpdate returns false.

When a single object holds a reference to another (like a missile having a ship as a target), I am using Message passing to notify the holder when the receiver dies.

Riven,

When I meant scalable, I meant more from the sense of me being able to keep track of everything in my head rather than from a code performance standpoint.

ctomni,

I also tend to keep most of my lists as static members, in my case I keep them in a “GameWorld” object that makes things convenient.

pjt33, 65k,

I am thinking that I may create GameObject collections that have listeners built into them to simplify things.

Best Username,

You make a good point about paying attention to the distinction between killing things right away and removing it when you iterate the next time through. I was using “list” in more of a colloquial way instead of java.util.List. I’ve implemented an array backed Bag data structure that I am integrating into my code more and more where it makes sense.

#8

I would centralize removal and then remove things from everywhere they can be. If you have tons of references all over the place, maybe that is what is necessary for your app or maybe you can find ways to minimize them.

#9

Riven’s answer to another question got me thinking, I wonder if I can help solve this problem by using weak references. If for instance, the update list, was made out of weak references then I wouldn’t have to explicitly remove it, as long as I removed it from everywhere else.

#10

The problem with WeakReferences is that they will eventually be removed, not immediately. Your soon-to-be-removed object can still linger around, hours later, if your app/game produces barely any garbage.

#11

If you want to take that route, you just need to use a mutable wrapper class everywhere:

public class Wrapper<T>
{
    private T wrapped;

    public Wrapper(T wrapped) { this.wrapped = wrapped; }

    public void clear() { wrapped = null; }

    public T get() { return wrapped; }
}

But it doesn’t solve the problem of tidying up the cleared wrappers from the lists. All it does is make things fail harder, which isn’t a bad thing but falls short of what you could achieve with other approaches.

#12

“Java-Gaming.org” :point: Did you forget? No one relies on destructors outside of C++.

Serious part: This was a little confusing the first time I saw it. Let me see if I can explain it. WeakReferences will not tell you if an object is “garbage collector dead” (unreachable via strong references) or “0 HP dead” (a dead character in a game). An object may be gc dead, but there is no way of knowing that until the garbage collector can get around to that point. Most of the time 0 HP dead and gc dead objects may still be reachable via weak references; because they won’t be removed until the garbage collector has time to reach them. If at any time a weak reference is used to create a new strong reference it becomes gc live again, meaning it could stick around indefinitely.

But weak references alone should not extend the lifetime of an object if they are not accessed. On the other hand if you use weak references for much more than using a WeakHashMaps the way it’s intended to be used, then you’re basically using them as a strong reference.

Is this correct?

#13

You completely missed the point. The problem the OP is trying to solve is to get rid of references to ‘dead’ objects, not to-be-collected objects. If WeakReferences are still lingering around, his game-logic will encounter them (for an undetermined amount of time), which was exactly what he didn’t want. What that has to do with destructors…

Then you go on describing the problems of WeakReferences, which was exactly the point I was making.

It does extend the collection of the object to typically one gc cycle.

There is no way to use a WeakReference in a way that it becomes effectively a strong reference. Maybe you need to explain what ‘use for much more than their intended use’ entails.

#14

You missed the joke. See, it’s funny if you think how C++ programmers always… and you said… never mind. You were talking about Java, right? If so, you probably should explain what you actually meant about lingering objects. And if not, why is it bad that a one piece of garbage not get collected if that’s the only garbage created over a span of several hours?

#15

Lingering in the collections, not on the heap, mkay?

I assume that was overly clear, given its context (this thread): getting rid of objects in collections when said objects are ‘dead’.

#16

No object can linger in a collection longer than it can linger on the heap. That still does not explain the assertion “The problem with WeakReferences is that they will eventually be removed, not immediately. Your soon-to-be-removed object can still linger around, hours late.”

#17

:expressionless: I can only hope you’re just being argumentative.

I never said it would linger longer on the heap than in the collection. What I said was that they lingered as referenceable objects, while being logically dead and thus break logic that assumes the dead objects are no longer accessible to the game logic.

The OP wants logic that removes references to dead objects, and WeakReferences cannot be used to implement that, as WeakReference.get() can/will still return a non-null value long after the object is flagged ‘dead’.

I think the OP got that point, quite early in the discussion, and solved the problem either with:
[x] removing the dead object from every possible collection that might hold it (eager approach)
[x] using an iterator that ‘filters & removes’ dead objects, to access all collections (lazy approach)
[x] flagging an object as dead, and checking its state whenever the object is used (cumbersome approach)

#18

I am using a combination of 2 and 3

#19

I’m pulling your leg a little and trying to get you to explain your first assertion. So, I guess that’s basically being argumentative but for the sake of completeness. You’re pretty bad at explaining this, but I am fairly certain I get it.

The way you described it, it sounds like WeakReferences in general cause memory leaks. Not that WeakReferences can’t be relied upon to return null when the last strong reference is removed. Someone reading this might walk away thinking they cause leaks and/or not understand why this is a misuse of WeakReferences. My goal was to explain what you glossed over.

But you said: “There is no way to use a WeakReference in a way that it becomes effectively a strong reference.”
Response: o = weakReference.get(); Accessing the object you want requires creating an at least temporary strong reference. If you use a WeakReference to regularly access (in an update loop, for example) the object it refers to, then the garbage collection is going to see it was accessed and never clear the weak reference. (Effectively making it a heavy strong reference.)

I’m also not sure what circumstances would cause a weak reference to “extend the collection of the object to typically one gc cycle.” I doubt that’s correct, but it depends on whether you meant “to the end of the next gc cycle” (right, but true for most references) or “by one extra gc cycle” (wrong, as far as I know).

[quote=“Riven link=topic=27642.msg248805#msg248805 date=1351958804][quote author=Best Username Ever,post:13,topic:40000”]
On the other hand if you use weak references for much more than using a WeakHashMaps the way it’s intended to be used, then you’re basically using them as a strong reference.

Is this correct?
[/quote]
There is no way to use a WeakReference in a way that it becomes effectively a strong reference. Maybe you need to explain what ‘use for much more than their intended use’ entails.
[/quote]
I was asking about the entire post, not just the above paragraph.

#20

Ridiculous. If anybody else seriously got this impression, I’ll put some effort into explain what I said, for the 3rd time.