• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
dpadam450

(Super) Smart Pointer

28 posts in this topic

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
1

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.

0

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.

0

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
0

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
0

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.

0

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.

1

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
0

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
0

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

0

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.

1

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
1

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
1

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.

1

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.

1

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!

0

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
2

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.

0

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

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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0