• Advertisement
Sign in to follow this  

(Super) Smart Pointer

This topic is 1289 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Imagine an RTS game, you have 20 marines shooting at one building and it blows up. All the marines have AI pointers "targetedEnemy" pointing at the building. The building blows up and is removed from the world and deleted.

Is there any good design for this?----> Updating the 20 marines "targetedEnemy" pointers that is to be NULL so they can go looking for new enemies?

shared_ptr doesn't seem to work because that is reference counted. It WOULD work if I decide that the marine AI checked their enemies health and if health < 0, call reset on the pointer. After the 20 marines all call reset() then the object would officially be deleted.

The other option I thought of was creating a new pointer type (unless one exists), where anytime I deconstruct a copy of the pointer, it has maintainted a list of people pointing to it and sets all pointers in the list to NULL.

Something like this:

 

template <class T>;
class SuperPointer

{

       T*  data;
       vector<T**> owners;
       ~SuperPointer(){ // loop through owners setting them to NULL };

};

Anyone can essentially delete the data, it will update all respective pointers who are pointing to the data. Maybe there is a better way to think about this or there is some other pointer that does this?

Edited by dpadam450

Share this post


Link to post
Share on other sites
Advertisement

All the marines have AI pointers "targetedEnemy" pointing at the building.

 

A good programming practice would be for the AI to check if the enemy exists (not just attributes of the enemy.) If it doesn't exist, the AI should handle that.

 

For each object that needs it, you can provide a pointer to a pointer to the "enemy." When the enemy is destroyed, set the pointer-to-enemy to NULL. Then the pointer-to-pointer will return NULL.

Enemy *enemy = new Enemy;
...
AI::Enemy **aiEnemy;

for each AI( AI.aiEnemyPtr = &enemy; )
...
AI::CheckEnemy() { if (*aiEnemyPtr==NULL) Change_AIBehavior(); }
...
when (enemy->killed ) { delete enemy; enemy = NULL; }
Edited by Buckeye

Share this post


Link to post
Share on other sites

To check if it exists, it would have to go into a list of objects in the world to see if it is in that list still.......?

If that is what you mean, I definitely don't want to iterate through all the objects in the world for each of the 20 marines to see if their enemy is still in some world list.

Share this post


Link to post
Share on other sites

As Buckeye says, make it the AI's job to work out if the target is still there.

 

You can also have fun with it when you work this way.

 

A berserker that keeps firing at his target until he runs out of ammo, regardless of the state of the target. "Dance MF ..DANCE!"

 

A target that plays dead, then comes back to life to attack when least expected. (Nice hammy animation, "Mutter ich bin Todd".... etc. Just think of the worst overacting you have every seen and animate it smile.png )

 

Switching targets when you lose line of sight.

 

Switching targets based on percieved threats

 

Loads of things you can play with.

Share this post


Link to post
Share on other sites

 

As Buckeye says, make it the AI's job to work out if the target is still there.

Right, but that's what I'm saying, I'd rather not iterate every object on the other team to determine if my target is dead or not. In that case, each 20 marines is pointing to say the last object on the enemy team. If the enemy team has 1,000 objects, then

//Do this 20 times?
marine.ComputeAI() { // loop through to see if enemy exists in list........has to loop 1,000 objects}

 

 

^^^ Was this the original solution to the problem? I didn't get what the solution being suggested was. I think it was this. I guess if I finally partition my world objects, then I wouldn't have to search through that many objects and that would be ok.

Edited by dpadam450

Share this post


Link to post
Share on other sites
Then loop through the list of marines and set enemyPtr to NULL if enemyPtr==building. That only has to be done when something goes out of existence. Edited by Buckeye

Share this post


Link to post
Share on other sites

I probably wouldn't have any of this information inside the soldiers or the enemy. I'd probbaly have the GamePlay class store maps of soldiers to targets and a reverse of that map and then each frame (or at some other more appropriate time) have the GamePlay class evaluate the situation and update the maps based on targets going down or so on.

 

Just do it the easiest way you can because when you come back to debug it in 6 months time you won't be stumped.

Share this post


Link to post
Share on other sites

Read Buckeye's original post again. If the AI has a pointer *to the pointer* to the enemy, they can all see whether the enemy object exists/NULL or not with a single if-statement. No looping. The AI just sees a lack of enemy next time they get updated.

Share this post


Link to post
Share on other sites

We call this a "Weak Reference".

I don't have examples at hand, but that's the term you want to search for smile.png

 

Edit: What BitMaster said. std::weak_ptr

Edited by Daivuk

Share this post


Link to post
Share on other sites

 

 

As Buckeye says, make it the AI's job to work out if the target is still there.

Right, but that's what I'm saying, I'd rather not iterate every object on the other team to determine if my target is dead or not. In that case, each 20 marines is pointing to say the last object on the enemy team. If the enemy team has 1,000 objects, then

//Do this 20 times?
marine.ComputeAI() { // loop through to see if enemy exists in list........has to loop 1,000 objects}

 

 

^^^ Was this the original solution to the problem? I didn't get what the solution being suggested was. I think it was this. I guess if I finally partition my world objects, then I wouldn't have to search through that many objects and that would be ok.

 

 

Also as an aside to the whole pointer stuff.  You might want to use a hashmap instead of a loop.  If for example, the marine ai just hold a handle instead of a pointer, then they could just do a simple lookup, instead of iterating over a list.  (Or use an array and store the index)  No world partitioning required at that point.  (That's more for when you need to iterate first, to find out who is within X or whatever, so for an attack move ai, spatial partitioning would be helpful)

 

The other option is to have an event system, and have a "Building X has been destroyed" event go out, and all the AI can go and look and act on that event, possibly setting their targets to null if it was the building.

Edited by ferrous

Share this post


Link to post
Share on other sites


//Do this 20 times?
marine.ComputeAI() { // loop through to see if enemy exists in list........has to loop 1,000 objects}
 
 
^^^ Was this the original solution to the problem? I didn't get what the solution being suggested was. I think it was this. I guess if I finally partition my world objects, then I wouldn't have to search through that many objects and that would be ok.

 

Partitioning and prioritizing is the correct answer.  The question to be answered is, how do your marines theoretically decide what target to attack next?  Is it purely proximity based?  Then a spatial data structure for targets is the answer to the problem.  If there is some other prioritization, such as the type of target, then some form of sorted/prioritized data structure is the answer.  If it's a combination of both, then an additional heuristic needs to be applied.  None of that really has anything to do with the type of pointer used to track the targets themselves, smart or otherwise (though the more data structures you rely on to track things, the more beneficial some form of smart pointer becomes).

Share this post


Link to post
Share on other sites

 

shared_ptr doesn't seem to work because that is reference counted.


Or of course simply a weak_ptr.

 

 

shared_ptr and weak_ptr are entirely the wrong mechanisms here -- both express a particular flavor of ownership (potential ownership, in the case of weak_ptr), but the marines discussed here don't 'own' their target. Any pointer they do hold to their current target should be raw (raw pointers are the preferred mechanism for non-owning semantics) and probably const-appropriate; above all, it should be viewed not even as an implementation detail of the AI, but an implementation detail of a particular optimization (e.g. "its likely that the thing I was interested in last frame still interests me.")

 

It sounds to me that the root of OPs problem here is that entities effectively become tightly-coupled when they interact. It sounds like there's direct-dealing between the sides, mediated by some AI/logic processes that are coupled to one or both of the participants. A solution is to move towards having more autonomous agents who make observations about their environment, and then perform some action as a result (possibly spawning a new autonomous agent) that achieves what they want ("fire my gun at my enemy"), but its hands off between the marine and his target.

Share this post


Link to post
Share on other sites

@Ravyne

 

You mean the target-pointer shouldn't persist between frames, but the unit should decide every frame which one is the current target?

Edited by Madhed

Share this post


Link to post
Share on other sites

I would go with an event approach.

 

Maybe right now your only requirement is to check if the object exists (which weak_ptr would solve very easily, even though what Ravyne said stands), but in the feature you may want your marine's target to look somewhere else even if the target still exists (maybe the enemy has applied a stealth "power up").

 

For maximum flexibility I would implement an event/observer pattern where your marine could register to the enemy's events and listen for a "destroyed" event, and possibly more events.

void Marine::SetTarget( const ITargettable* target )
{
   if( _currentTarget )
      _currentTarget->RemoveListener( this );

   _currentTarget = target;
   if( _currentTarget )
      _currentTarget->AddListener( this );
}

void Marine::OnTargettableEvent( const ITargettable* target, const TargettableEvent& event )
{
   if( event.type == TargettableEvent_Destroyed ||
      event.type == TargettableEvent_StealthApplied )
   {
      SetTarget( nullptr );
   }
}
Edited by mdias

Share this post


Link to post
Share on other sites

@Ravyne

 

You mean the target-pointer shouldn't persist between frames, but the unit should decide every frame which one is the current target?

 

It depends -- if you engineer your system to support it, then you can keep it around between frames and possibly use it as an avenue to short-circuit the AI routine ("If my target hasn't been destroyed, just keep attacking it, don't consider other options"). But you're right that you can't keep it if there's no mechanism to identify when an object has been removed from play, and simply deleting that object from memory doesn't cut it. Using weak_ptr would work, but its not a good solution for reasons I'll get into below. Another solution would be for destroyed objects to post a message, and that game entities would subscribe to that message, whereupon they could clear the pointer. Another solution would be to have a system of entity 'slots' that persistently occupy the same memory location, combined with an enemy ID -- you could keep the pointer around between frames, along with its ID, and check whether the slot still corresponds to that ID. Yet another would be to temporarily exist in a destroyed state for some extra frames, so that everyone has a chance to notice its been destroyed (in practice, this can work well as there's often an animation cycle associated with the object or entity being destroyed/killed).

 

Also, although I'm using the word 'pointer' I don't strictly mean a memory address; It could be any kind of handle that resolves to a specific object reliably.

 

 

The trouble OP has is that things become tightly coupled when they interact. The result of this is that it creates this false appearance of ownership semantics -- to be clear, the need for shared ownership semantics in the system OP describes is real, but the ownership is necessitated by the implementation rather than the requirements. Ultimately this is a code-smell.

 

shared_ptr and weak_ptr are quite thin -- thin enough that you should instinctively reach for them when they fulfill your requirements -- but they are not so thin that one should consider using them to compensate for design flaws. Its implementation dependent, but if you ever look into the guts of how share_ptr and make_shared work, you can get yourself into situations in which just one extant weak_ptr (and no extant shared_ptr) disallows a significant block of memory from being freed because the control block is not deallocated until there is no extant weak_ptr (as when make_shared decides to embed the allocation block into the control block for objects up to an implementation-defined size) -- its always the case that the object is deconstructed and that the resources it holds are released when the shared count reaches 0, but its not always the case that the memory for the object itself is freed. I believe its common that this kind of combined control/allocation block can be as large as 32 or 64 bytes, which can add up quickly. Furthermore, use of make_shared (but not share_ptr) necessarily implies that the objects are non-contiguous and can't be used with pooled allocation (because you can't use a custom deleter) which could disallow significant optimizations in other parts of the code.

Share this post


Link to post
Share on other sites

Okay, I see where you are coming from.

 

Pointers are so pervasive in C/C++ that one often doesn't realize that there are better ways to refer to entities.

 

Refering to units by memory address is very low level and implies that they are not relocated between calls, or deleted.

So something like a uid handle might be better. This would also make it possible to serialize the state of the unit, for network replication for example.

 

The handle itself could be an intelligent type that keeps an "automatically" updated pointer to the unit as an implementation detail.

Share this post


Link to post
Share on other sites


I would go with an event approach.

 

I like this approach too - usually if you want to perform a specific reaction to something happening (like the target dying) then event based solutions are hard to beat.  Your original brute force search approach is akin to polling for a certain state to occur, while if your units register with the target when they acquire it, then they can get easily notified when the target gets deleted.  You could make this part of the units themselves, or have a mediated subsystem in between that would manage the monitoring of the objects and perform the notifications - either way, you just want to be notified when the event occurs, not poll the status to see if something already happened!

Share this post


Link to post
Share on other sites

As a general rule, architect your solution around the concept of ownership.
 

  • unique_ptr implies direct ownership.
  • shared_ptr implies shared ownership.
  • weak_ptr implies no ownership (though is perhaps more correctly seen as a no-ownership complement to shared_ptr)
  • raw pointer is no ownership to objects that are supposed to exceed your own lifetime (though perhaps more correctly just "general non-ownership")

Your pointers are just links between entities, used for referencing.  Neither should be in charge of deleting the other.  Ergo, just use raw pointers.  If you need the complexity of ensuring things are destroyed, do that in a more proper place, and bolt some simple logic onto this subsystem if you have to (e.g. target storing a ref count of things shooting at it, so some other system can destroy it at 0 && target "dead").

 

That said, I tend to agree that event systems are better solutions entirely.

Edited by SeraphLance

Share this post


Link to post
Share on other sites

shared_ptr doesn't seem to work because that is reference counted.
The other option I thought of was creating a new pointer type (unless one exists), where anytime I deconstruct a copy of the pointer, it has maintainted a list of people pointing to it and sets all pointers in the list to NULL.

Or of course simply a weak_ptr.
shared_ptr and weak_ptr are entirely the wrong mechanisms here -- both express a particular flavor of ownership (potential ownership, in the case of weak_ptr), but the marines discussed here don't 'own' their target. Any pointer they do hold to their current target should be raw (raw pointers are the preferred mechanism for non-owning semantics) and probably const-appropriate.

A weak_ptr expresses no ownership at all; it expresses using an object that may have a shorter lifetime than you.
It's also the exact "unless one exists" class that the OP was about to reinvent.
 
A raw-pointer expresses that the used-object's lifetime is longer than the user-object's lifetime. In this case, if the building can be deleted before the marines, then a raw-pointer isn't valid (without reinventing some kind of notification system, a la weak_ptr). Yeah, maybe the building/marines shouldn't be getting deleted at all, but that's another kettle of fish! wink.png

Share this post


Link to post
Share on other sites

IMHO it is a design flaw if the deletion of a scene object is used to "steer" AI. If an object is dead or destroyed w.r.t. the game mechanics, then it is still existing in the scene. It may have to play a role (ruin, corpse, for looting, ...), some of them already mentioned in posts above. The target should be in the scene at least as long as any other game object is referring to it, simply because it is "in use" if being referred. Deletion is a low level mechanism; it could be run if higher levels are done with the object.

 

Running the AI every now and then has to be done anyway. What if the marines are attacked after they begun raiding the building? Do they react only after the building is destroyed? Hardly, I would say. So the regular checking for "is the currently followed plan still valid" will detect the destruction early enough. Hence there is also no real need to notify the marines as soon as the building collapses. It would look even artificial if 20 marines stop firing in the same millisecond.

 

AI need not be run on every frame for every unit and in full depth. Using a layered approach allows running the short tests more frequently, and computing higher layers only if the lower one has failed or finished. Also, ways exist to reduce the AI computations of a party by running full AI on a leader only, and letting it more or less directly control the other party members (this doesn't mean there must be an officer; the leadership can be as abstract as a concept of the party itself).

Share this post


Link to post
Share on other sites

The other way to do it is to have the object know at all times what lists it is stored in, and upon being deleted from the master list, fully removes itself from the other lists. This technique requires a lot of care in that you don't want to be iterating over a list containing the item, somewhere higher up the call stack, for example.

I would consider using the shared + weak pointer method first.

Share this post


Link to post
Share on other sites

shared_ptr doesn't seem to work because that is reference counted.
The other option I thought of was creating a new pointer type (unless one exists), where anytime I deconstruct a copy of the pointer, it has maintainted a list of people pointing to it and sets all pointers in the list to NULL.

Or of course simply a weak_ptr.
shared_ptr and weak_ptr are entirely the wrong mechanisms here -- both express a particular flavor of ownership (potential ownership, in the case of weak_ptr), but the marines discussed here don't 'own' their target. Any pointer they do hold to their current target should be raw (raw pointers are the preferred mechanism for non-owning semantics) and probably const-appropriate.
A weak_ptr expresses no ownership at all; it expresses using an object that may have a shorter lifetime than you.
It's also the exact "unless one exists" class that the OP was about to reinvent.
 
A raw-pointer expresses that the used-object's lifetime is longer than the user-object's lifetime. In this case, if the building can be deleted before the marines, then a raw-pointer isn't valid (without reinventing some kind of notification system, a la weak_ptr). Yeah, maybe the building/marines shouldn't be getting deleted at all, but that's another kettle of fish! :wink:

Well, it seems that we can agree that OP's solution is the wrong thing, and I'll also agree that that weak_ptr does that wrong thing exactly. There certainly is no need to reinvent it.

But I do have do respectfully disagree that weak_ptr only expresses using semantics. The thing still has to be managed by a shared_ptr, and you have to convert weak_ptr to a shared_ptr before you can use the thing, so really I think its more accurate to think of weak_ptr as expressing 'potential ownership', and there really should be no kind of ownership relationship at all between the entities here. Using weak_ptr in this context instead of shared pointer doesn't really make anything better, and its just as heavy.

Share this post


Link to post
Share on other sites
Back from vacation, and seemingly just in time for this thread. :-)

An alternate technique, which I am mildly shocked has not appeared yet, is the use of handles.

With regards to the original problem of marines attacking a now-eliminated building, they can request the object belonging to the handle. The handle lookup returns NULL, lookup time is nearly-nothing, and the marine can proceed to find something else to do.

There is no linear-time search or log-time search as has been proposed. Since you own the handle you control the lookup which can be constant time with a perfect hash. There is no ownership semantics for the marines (or any other game objects). The game engine owns the objects referred to by the handles. If the handle becomes invalid for any reason the game object can quite easily handle it in script. The game objects have no reason to maintain a reference count to the object, no reason to have a weak pointer, or any smart pointer at all at the game object level. It isn't exactly zero time but it can boil down to about four or fewer indirections which are the slow part, which on modern hardware is roughly 30ns. Best case is around 7ns for a single indirection. As far as today's hardware is concerned, such a handle is very inexpensive and all-but-free. Far cheaper than reference counts trying to stay in sync between processors, or searches of slower containers to find the object in the haystack of other world objects.

As bonus features handles can persist easily through serialization, they can be shared across networked machines, they can even survive objects getting moved in memory without any serious problems. Handles can do some cool stuff that even the proposed "(Super) Smart Pointer" doesn't, like providing you with dummy objects or proxy objects or other alternative solutions without needing a real object in the game world. Handles are very versatile in this regard.


Every time through the update processing you look up the pointer for the handle with a constant-time (fully inlined) function, along the lines of GameObject *ptarget = World::FindByHandle(buildingHandle); If ptarget is not null you do whatever you want with it. If ptarget is null your object has died without you knowing it, and it is time for the script to do something different.

Handles are good for a great many things. This is one place they are a perfect fit.

Share this post


Link to post
Share on other sites

I prefer to do physically based solutions for things like this.

 

What would a marine do in the real world?

 

He'd look at the target, decide it's dead, then start looking around for something else to kill.

 

This is easy to implement in a game, but often they go for a "programmers" solution. 

 

You use some clever data structure that means a marine effectively knows were every other unit is at all times. So they kill one, then instantly target the next.

 

Then they realize this is crap, and add some code to make it more realistic.

 

I would rather work the other way around, 

 

The marine kills a target, he goes into a START_LOOKING state. 

 

Next frame he changes his point of view a few degrees in a random direction, and enters a LOOK state.

 

The look state runs for a maximum amount of time, I like having a raycast system and limit the number of rays.

 

If it doesn't find anything, it changes view direction and stays in LOOK state.

 

The look state can be interrupted if the marine is shot at, the view direction changes to the direction the incoming round came from.

 

Then you can re-use code as well, when the marine is moving, he's still looking for targets, so you call the same code but just limit the number of rays. You can even have a sprint mode were the marine put's his head down and runs for it.

 

Coding this for me is always quite easy. You store all your targets in a quad tree (you do need a neighbor list in the tree though) which makes building a potential target list easy. I generally group objects into units so the group can produce a potential target list for all the individuals in the group. 

 

The individuals within the group then have a much smaller subset of targets to parse.

 

I also limit update of this group list. Sometimes I trigger an update only when targets move , other times I trigger an update at a fixed time rate. It depends on the effect I want in the game. If you have a lot of movement you may want to use a fixed time rate.

 

I try to avoid any type of FindByName subroutines. It can get very expensive very quickly. As Frob mentioned, hashmaps are your friend.

 

Using this approach, you can build lot's of game effects very easily.

 

An elite soldier will still look for targets while being shot at (just at a reduced ray cast count), a rookie will kiss the ground and see nothing.

 

You can use the quad tree to work out a general bearing to a target and have the marines fire suppressing fire in that general direction without aiming and if that fire does come near a target, it actually has an effect.

 

It's fun to play with the parameters and see what happens.

 

When it comes to hanging references, it's easy to handle. You just a have an extra "DIEING" state (you should have this for the animation anyway) and drop references on dieing. When the entity moves to a dead state you should have no references left to it (easy to check with an assert) and you can move to a dead state or delete the object safely.

Edited by Stainless

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement