Tracking targets

[Krice]

1. npc is going towards an item, having its pointer or id stored
2. The item is destroyed

How to notify npc that the item is destroyed? I was wondering is it a good idea to include the list of targetters to the item's data directly? Or go through the list of npcs and check the target id of deleted item (could be slow)? Any ideas?

[anpd]

I would let the item have a list and notify all that have it as a target that it's destroyed. Check the observer design pattern http://en.wikipedia.org/wiki/Observer_pattern

[kipar]

I would use second approach (check the list when object destroyed) just because it is easier to code. I can always switch to first method if profiling will show that checking list of units cause observable delay.

[Ex]

This is a very intriguing question, particularly because although it's a somewhat rare situation, it usually shows up sooner or later. Anyway, I'd probably do it one of two ways. Either:

1. I'd loop over all the enemies whenever an object on the map is erased. If the enemy's target is the object to be erased, set the pointer in the enemy to NULL.
2. Or I'd use a "death" flag to specify that an enemy or item needs to be removed from the map. Assuming that this death flag is set before enemies are updated, the enemy could check to see if the item's death flag is set. If it's set, it would change it's target to NULL. Then, after the enemies have been updated, I'd loop over the items removing and deleting anything with a death flag.

Of the two, I'd more likely use the first because it's very easy to code. But, the second is convenient because often I already have a death flag implemented, in which case it's just a matter of having each enemy check during update if it's target's death flag is set. If some complicated situation comes up where neither are suitable, I'd definitely maintain a list of all references to each object (inside of the object's class), and on object deletion, I'd make sure that all the pointers referencing the object are set to NULL.

A lesser way to deal with the problem would be to work around it entirely. Such as, rather than storing a pointer to the target item, store it's coordinates and the intention of the enemy to get a certain type of item on those coordinates. Then you'd just need to periodically make sure that the given type of item still has those coordinates. Of course, I'd vastly prefer not to use this method because it's not a real solution, but I thought I'd throw it out there anyway

[corremn]

1. npc is going towards an item, having its pointer or id stored
2. The item is destroyed

How to notify npc that the item is destroyed? I was wondering is it a good idea to include the list of targetters to the item's data directly? Or go through the list of npcs and check the target id of deleted item (could be slow)? Any ideas?

At the start of the AIs turn, check if item still exists. EASY.

I think an AI should adapt to its surroundings, not have its surrounding inform it when things change.

Hmm, Generally I just have enemies update there goals on the fly, if the target disappears then it will cease to go for it next turn.
For my AIs that have a set goal that stays persistent over turns, they just checks if it is still a relevant goal at the start of its turn. I.e does destination still exist, can I get there, is the object I am going for still there?
I dont see the point of informing AIs that a object has disappeared prior to their turn, they should figure it out themselves.  Sounds like needless complexity. Simple is best.

[Bear]

What Corremn said.

If a mobile is tracking/targeting something, then the tracking/targeting state, as well as the ID number of the item/creature being tracked, is information that, IMO, ought to be stored as local state in that mobile's  AI.  

So, when the tracked thing disappears, it just disappears.  But the next time the mobile that's tracking it has a chance to move, its tracking/targeting function checks the ID number, finds no corresponding location for an item or creature, and reverts to a "figure out what else to do" state.

Bear

[Ex]

1. npc is going towards an item, having its pointer or id stored
2. The item is destroyed

How to notify npc that the item is destroyed? I was wondering is it a good idea to include the list of targetters to the item's data directly? Or go through the list of npcs and check the target id of deleted item (could be slow)? Any ideas?

At the start of the AIs turn, check if item still exists. EASY.

I think an AI should adapt to its surroundings, not have its surrounding inform it when things change.

Hmm, Generally I just have enemies update there goals on the fly, if the target disappears then it will cease to go for it next turn.
For my AIs that have a set goal that stays persistent over turns, they just checks if it is still a relevant goal at the start of its turn. I.e does destination still exist, can I get there, is the object I am going for still there?
I dont see the point of informing AIs that a object has disappeared prior to their turn, they should figure it out themselves.  Sounds like needless complexity. Simple is best.

I would assume Krice is going to use a pointer to keep track of the target for speed. You can't simply check to see if the item still exists if you only have a pointer. He could keep track of the item's ID and information, but that would require looping over all the items looking for the item with the given ID every turn to make sure it still exists. And unfortunately, that doesn't solve the problem of: how do you determine if an object still exists when you only have a pointer to that object?

Of course, rereading Krice's post, it seems he's okay with IDs, so as long as you don't mind looping over every item every turn for every monster, I suppose it's okay.

[Bear]

Don't be silly.  An object ID is an O(1) hashtable lookup, not an O(n) looping over every item. 

[Krice]

so as long as you don't mind looping over every item every turn for every monster, I suppose it's okay.

When the target is destroyed you only need to check out every monster in that level to see if it has it as target.

I'm using 'destroyed' state for objects and they are finally deleted after a turn, so nothing points to a deleted object during the turn. The target check could be actually made at the same time when deleting the destroyed objects...

I'm just wondering if it's worth it to create a link between the target and one who is targetting for faster checking when something happens to the target. Maybe it's premature optimizing, since objects don't get destroyed that often.

[Krice]

Actually all objects that are destroyed need to be check for all monsters (who have targets) so when more than one object is destroyed it can be slow.

The more I think this I'm convinced that having the object know that something is targetting it could be a good solution. It's also good for AI, because at least more intelligent creatures would then know that a monster is trying to attack (excluding the player, but that could be determined other way).

[Bear]

I still don't understand what the problem is.  Why do you have to iterate over everything?? 

Creature A targets or tracks creature/item B.  Okay.  We write B's ID into A's AI record along with a state number that means "targeting" or "tracking".  Now B is destroyed.  Okay. Mark B "destroyed".  Next time it's A's turn, it checks for B and finds that B is destroyed, so it ends its targeting/tracking state and erases B's ID from its AI record.  Where is the need for an iteration?

The only interesting bit here is how do you mark B as having been destroyed.  If you have the infrastructure (a hash table) to separate ID's from pointers, you can just deallocate B.  The next ID lookup returns a NULL pointer so code knows that there is no more B. 

On the other hand, If your ID is the pointer itself, you still don't have to iterate; just set a flag in B and note a pointer to B and the turn B ceased to exist in a FIFO reclamation queue.  When you're allocating a new item or creature, you go to the reclamation list first, and reuse the oldest record provided the thing it refers do expired more than N turns ago (a thousand, maybe). Otherwise you allocate a new record.  You may have a bug or two if something follows a very old pointer expecting to find a different item, but you won't ever have code following a pointer to deallocated space or wrong type, because you reuse within type and never deallocate.

But... there's never a need for iteration over creatures or objects!  The whole thing works in terms of getting things off the front of a queue, accessing a hash table, adding things to the end of a queue, etc.  All O(1) operations!!

[kipar]

On the other hand, If your ID is the pointer itself, you still don't have to iterate; just set a flag in B and note a pointer to B and the turn B ceased to exist in a FIFO reclamation queue.

I don't think it is possible if you use objects inherited from base class instead of just records. (e.g. TWeapon is child of TItem, TPotion is child of TItem, and they have different fields and different size in memory).

Using ID's instead of pointers eliminates the problem,  but imho pointers (= objects themselves in OOP) are more "intuitive" way then using IDs, creating hashtable and making a lot of wrappers or using unclear code such as

Code: [Select]

TargetID := B.ID;
...
if GetUnitByID(TargetID).Smiles then ...
instead of

Code: [Select]

Target := B;
...
if Target.Sad then...
Of course that's only my opinion.


Generally, my point is that O(N) isn't so bad while it isn't a bottleneck. Video output and complex AI algorithms will most likely eat more CPU-time.

[Krice]

Next time it's A's turn, it checks for B and finds that B is destroyed

In the current code a destroyed B will be deleted after the turn so I guess it's possible that a creature could still target it and in the next turn it's pointing to a deleted object.

[elwin]

I actually wouldn't have the NPC store any reference to the item it's tracking at all.  I'd have it look around every turn for items worth picking up.

My reason is that if monster A wants to pick up object B, indicating this by storing an id or pointer to B in A's data structure is duplicating information.  The level map contains the locations of A and B and implies that A can see B.  It implicitly stores the fact that A wants to pick up B.  Creating an explicit reference from A to B is storing the same information in two places.  If you do that, either they will fall into disagreement, or you will have to come up with a complicated method of making sure you always change them both at the same time.

Suppose, instead of getting destroyed, the item gets picked up by some other monster, or the player.  Or it gets teleported, or polymorphed into an item the monster isn't interested in.  Or the monster gets teleported out of sight, or polymorphed into something that can't pick up items.  There are just too many sections of code that have to work together.

[Krice]

I'd have it look around every turn for items worth picking up.

I don't know how it would be possible to travel to a specific target without storing some information about it, because making that evaluation in every turn would make the monster chase between two items, never reaching either one of them.