1
\$\begingroup\$

I am currently building a game focusing on AI for my university and this is my first time writing such a complex AI system.

Naturally, I ran into a little logic problem: In the game, the AI uses a hierarchical finite state machine and certain states have a pointer to a character as target for their logic (e.g. attack state has a target character to attack). Additionally, multiple characters might target this one character at the same time.

Now if that character dies, how should I go about telling the AI that the target is no longer valid? I can't just delete the character object, since that would result in invalid pointers and access violations, of course.

I thought about using an event system, where the characters are notified about the death, but how would I know, when all characters removed their reference, changed their state etc. and I could finally delete the object?

Would I have to resort to using smart pointers here? Or is there another good solution?

\$\endgroup\$
  • 2
    \$\begingroup\$ "resort to using smart pointers" - many experts would say "resort to dumb pointers" instead. This takes nothing more than std::weak_ptr. \$\endgroup\$ – MSalters Jan 13 '14 at 20:36
4
\$\begingroup\$

Instead of having the FSM pointing to the character instance straight on, you could have it pointing to a unique ID representing that character. The characters would be registered in a singleton manager class.

When the character dies, you simply mark it as deceased (in the singleton manager). Later on, when (and if) the FSM reaches a state in which it should interact with that character, a simple query to the manager will be enough for the FSM to identify that it has died and the character can be ignored (or that more appropriate actions shall be taken).

Also, if you have multiple NPCs targeting the same character, you might have to handle the update of the character's deceased state in a thread safe fashion.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. Would a constant lookup using an id not take a lot of processing time, if it happened several hundred times per AI frame? \$\endgroup\$ – Chris Jan 12 '14 at 21:53
  • 3
    \$\begingroup\$ When the singleton manager stores the character objects in a data structure optimized for searching (like a std::unordered_map), the overhead should be minimal. Anyway, wondering about this is premature optimization, and when it becomes a problem you can still see where you can avoid lookups and use a cached value. \$\endgroup\$ – Philipp Jan 12 '14 at 22:03
  • \$\begingroup\$ Easy. I think @Philipp's remark is well put. If characters in your game must be referenced by several sources, you definitely need some sort of management mechanism in between. As you progress in designing it, you will eventually come up with the best ways to balance performance in the context of your needs. \$\endgroup\$ – Luiz Vieira Jan 13 '14 at 0:47
  • \$\begingroup\$ Okay, I solved my problem now like this: I now have a global handle table, which is just a pointer array at the size of the maximum number of characters. Characters are now referenced using handles (CharacterHandle), which stores the handle index to the array and the character id. The handles can be created from a character object. When retrieving the character from the handle, the handle checks the handle table, gets the pointer value using the handle index, makes sure that it's not null and then compares the character ids to make sure that it's not a wrong character due to index recycling. \$\endgroup\$ – Chris Jan 15 '14 at 4:17
2
\$\begingroup\$

You could use the observer pattern.

The observer-pattern in a nutshell:

  • There are Observers (like your AI enemies) and Observables (the objects they target)
  • Each Observer can register itself to one or more Observables
  • Each Observable keeps a list of those Observers who registred on it
  • When an important event happens in an Observable (like its death or its deletion through the destructor), it notifies each of the Observers in its list by calling a notify-method on them.
  • When an Observer is either no longer interested in an Observable or ceases to exist itself, it unregisters itself from all Observables it observes so they don't try to notify an object which no longer exists or doesn't care anymore.
\$\endgroup\$
  • \$\begingroup\$ This good but simply reaching the conclusion that x has died by checking a bool value is fine too since the Observers in this case don't appear to need to do anything special like arrange a wake once x dies. The Observer pattern is more suited when an immediate response from the Observers is required, no? \$\endgroup\$ – wolfdawn Jan 13 '14 at 12:17
  • \$\begingroup\$ I mean that the lazy approach is better here: en.wikipedia.org/wiki/Lazy_evaluation \$\endgroup\$ – wolfdawn Jan 13 '14 at 12:26
  • 1
    \$\begingroup\$ @ArthurWulfWhite The question is about what happens when the observed object gets deleted. After the object got deleted, checking a flag on the object will cause a segmentation fault. But when you use the observer-pattern and put a notify-call into the destructor, you can safely delete the object and all observers are notified automatically so they can null their references. \$\endgroup\$ – Philipp Jan 13 '14 at 12:40
  • \$\begingroup\$ I honestly wonder what would happen in a case where several large groups of creatures observe one another. Lets say a bomb AoE attack is used and all creatures die. Now you free group A and notify Groups B, C .. N, correct? Alright, now you need to free group B and notify group A? Would that not cause a seg fault? Even if you work around this (it's possible), a group death like that would cost you O(N^2). It is just very rigid and may not be optimal for performance. While we are answering his question, should we keep in mind that others may read it too with similar questions? \$\endgroup\$ – wolfdawn Jan 14 '14 at 21:38
  • \$\begingroup\$ @ArthurWulfWhite The destructor of an Observer must of course make the Observer unregister itself from all Observables it registred to so they don't segfault when they try to notify the no longer existing observer (updated the answer). Yes, a group-death costs you O(n²) when every object observes every other object, but 1. this is a rare event, 2. unless you kill hundreds of objects in one go it won't be a notable hickup and 3. why would every object have to observe every single other object? \$\endgroup\$ – Philipp Jan 14 '14 at 21:44
-1
\$\begingroup\$

Ii think there is a point missed here, the state machine should not assume the character is alive. Characters should probably have a bit (bool) stating if they are alive. The dead could be placed in a pool(once they die) and should not be freed from the heap and could instead be recycled. The FSM needs to check if the character is alive and still meets this and other properties required for the desired action. if not, it needs to do a look-up for another character that does meet these properties.

You can also use a counter to see how many pointers point to that character if you wish to avoid smart pointers.

There is no need to "spare" memory by freeing every dead if performance is important.

\$\endgroup\$
  • 2
    \$\begingroup\$ Recycling dead objects looks very bug-prone to me. How do you want to make sure that when an instance is reused that no other object still has a reference to the one which was using the instance before? When there still is, it will now reference a completely unrelated object. That could lead to really obscure and hard to reproduce bugs. \$\endgroup\$ – Philipp Jan 13 '14 at 12:44
  • \$\begingroup\$ That is why I said the FSM needs to check if "the character is alive and still meets this and other properties required for the desired action". If you check that and it was recycled, it will not meet the required conditions and the pointer will be released organically. Also methods used to resolve the ABA problem could be applied here like adding a stamp to the character and the pointer. \$\endgroup\$ – wolfdawn Jan 14 '14 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.