Jump to content

  • Log In with Google      Sign In   
  • Create Account


(Super) Smart Pointer


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
28 replies to this topic

#1 dpadam450   Members   -  Reputation: 921

Like
1Likes
Like

Posted 11 July 2014 - 09:42 AM

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, 11 July 2014 - 09:42 AM.


Sponsor:

#2 Buckeye   Crossbones+   -  Reputation: 4588

Like
4Likes
Like

Posted 11 July 2014 - 09:44 AM


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, 11 July 2014 - 09:56 AM.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.


#3 dpadam450   Members   -  Reputation: 921

Like
0Likes
Like

Posted 11 July 2014 - 09:54 AM

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.



#4 Stainless   Members   -  Reputation: 903

Like
0Likes
Like

Posted 11 July 2014 - 09:59 AM

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.



#5 dpadam450   Members   -  Reputation: 921

Like
0Likes
Like

Posted 11 July 2014 - 10:03 AM

 

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, 11 July 2014 - 10:06 AM.


#6 Buckeye   Crossbones+   -  Reputation: 4588

Like
0Likes
Like

Posted 11 July 2014 - 10:06 AM

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, 11 July 2014 - 10:07 AM.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.


#7 Dave   Members   -  Reputation: 1504

Like
0Likes
Like

Posted 11 July 2014 - 10:12 AM

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.



#8 BitMaster   Crossbones+   -  Reputation: 3934

Like
14Likes
Like

Posted 11 July 2014 - 10:13 AM

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


Or of course simply a weak_ptr.

#9 beans222   Members   -  Reputation: 1075

Like
1Likes
Like

Posted 11 July 2014 - 10:15 AM

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.


New C/C++ Build Tool 'Stir' (doesn't just generate Makefiles, it does the build): https://github.com/space222/stir

 


#10 Daivuk   GDNet+   -  Reputation: 358

Like
0Likes
Like

Posted 11 July 2014 - 10:16 AM

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, 11 July 2014 - 10:22 AM.


#11 ferrous   Members   -  Reputation: 1942

Like
0Likes
Like

Posted 11 July 2014 - 10:40 AM

 

 

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, 11 July 2014 - 10:44 AM.


#12 jHaskell   Members   -  Reputation: 997

Like
0Likes
Like

Posted 11 July 2014 - 11:30 AM


//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).



#13 Ravyne   Crossbones+   -  Reputation: 7141

Like
1Likes
Like

Posted 11 July 2014 - 01:27 PM

 

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.



#14 Madhed   Crossbones+   -  Reputation: 2811

Like
1Likes
Like

Posted 11 July 2014 - 02:15 PM

@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, 11 July 2014 - 02:15 PM.


#15 mdias   Members   -  Reputation: 786

Like
1Likes
Like

Posted 11 July 2014 - 03:51 PM

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, 11 July 2014 - 03:53 PM.


#16 Ravyne   Crossbones+   -  Reputation: 7141

Like
1Likes
Like

Posted 11 July 2014 - 05:00 PM

@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.



#17 Madhed   Crossbones+   -  Reputation: 2811

Like
1Likes
Like

Posted 11 July 2014 - 05:32 PM

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.



#18 Jason Z   Crossbones+   -  Reputation: 4911

Like
0Likes
Like

Posted 11 July 2014 - 06:24 PM


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!



#19 SeraphLance   Members   -  Reputation: 1340

Like
2Likes
Like

Posted 12 July 2014 - 12:14 AM

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, 12 July 2014 - 12:15 AM.


#20 Hodgman   Moderators   -  Reputation: 29741

Like
3Likes
Like

Posted 12 July 2014 - 01:11 AM

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






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS