1
\$\begingroup\$

I've recently discovered GOAP and interested in implementing it for the AI in a game I'm developing. Something I'm stuck on at the moment, is determining when to plan. I've read through an MIT paper on it:

http://alumni.media.mit.edu/~jorkin/GOAP_draft_AIWisdom2_2003.pdf

It mentions real-time planning and specifically:

The character follows this plan to completion, invalidation, or until another goal becomes more relevant

Should I then be planning every frame until a new plan is deemed better (lower cost)?

And if not, if I have multiple goals but pre-requisites for one goal are only met in the middle of a plan for another goal, when would be appropriate to re-evaluate?

\$\endgroup\$
2
\$\begingroup\$

It's pretty dependent on what your goals and planning are. If you look at the real-time case where replanning would create a new goal,

The character follows this plan ... until another goal becomes more relevant

The answer will depend on your goals and how often they change. If the goals change every frame, then it is reasonable to plan every frame. If your goals change rarely, then planning only makes sense when certain events occur.

I have multiple goals but pre-requisites for one goal are only met in the middle of a plan for another goal

This could be implemented by only doing the planning phase only at the time when a potential pre-requisite condition is met.

\$\endgroup\$
  • \$\begingroup\$ Okay, if the pre-requisite was something like "an enemy is within range", based on your answer that implies planning each frame. Is an alternative to have invalidation conditions? I.e. If a character is completing a WalkTo action, invalidate the action and re-plan? \$\endgroup\$ – Naxin Jan 23 '18 at 3:20
  • \$\begingroup\$ @Naxin, I don't know if it would be hard to do, but if you check the condition each frame (whether an enemy is in range) and do the planning when necessary (enemy has come into range this frame). \$\endgroup\$ – Jay Jan 23 '18 at 3:40
2
\$\begingroup\$

Planning every frame is almost certainly overkill.

So planning only when an action fails, or a goal changes makes sense.

However, I would also re-plan every few seconds, even if the goal did not change. This will make your AI react better to changes in the world.

If your AI is currently executing an expensive and complex plan to achieve something, it could be that an event in the world suddenly opens up a much cheaper way to a goal.

For example, an NPC wants to eat, and planned to drive across town, go shopping for ingredients, find a stove, bake a pizza, and eat it. But a few seconds later, a passer-by drops his uneaten hamburger. Not carrying out the original plan seems a lot smarter.

If you plan every few seconds, your AI will seem smarter for it, more flexible.

\$\endgroup\$
  • \$\begingroup\$ Apparently hygiene isn't considered in the cost calculation ;) Thanks for the answer \$\endgroup\$ – Naxin Feb 5 '18 at 2:59
0
\$\begingroup\$

I know, I'm late.

Game AI Planning update can be done anytime you want. For instance, the Killzone series AI Update is every 200 ms (i.e. 5Hz); this series of games (Killzone 2 and Killzone 3) uses HTN Planning (i.e. not GOAP). Transformers 3: Fall of Cybertron also uses HTN Planning and its AI Update is every frame.

GOAP implementations (F.E.A.R. games, Shadow of Mordor, Deus Ex, Tomb Raider, etc) generally update every frame.

Updating every frame means Planning runtime budget can fit in the AI-per-frame budget. What is yours? Then test your planner offline with problems from your games (as many tests as you can) and see whether this fits. If it doesn't, optimize your planner, as today, Game AI Planning is an established solution which can be called up to 50 times per frame (e.g. Shadow of Mordor).

\$\endgroup\$
  • \$\begingroup\$ Thanks for this insight. Your answer seems to imply that AI update frequency should be entirely an optimisation problem, would you agree? \$\endgroup\$ – Naxin Jun 26 '18 at 6:46
  • \$\begingroup\$ These days, the planners implemented in commercial games are highly optimized. When starting from scratch, it's a matter of bugdet per frame (how many ms allowed to your planner?) and a matter of game design (what do you want to see on screen?). It might be that an un-optimized planner is just fine for the game design you want (how fast you want your game to react? is it a tough situation for the player? do you want him to loose this fight? etc). \$\endgroup\$ – TheAIHedgehog Jun 26 '18 at 7:26

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.