FSM, BT, HTN, Goap, other

GOAP was a big thing 12 years ago when it came out. However, it quickly ran into issues with scalability. Also, it can be terribly inefficient due to the constant re-planning that is done every time something in the game state changes. It doesn't do any good to construct a 12-step plan if every second you have to throw it away and find another plan. Now imagine doing that for dozens of agents. This is complicated a little further by having agents depend on the plans of other agents. You really have issues about who is planning what first.

HTN is better than GOAP. Guerrilla used it well in the KillZone series. There are some other uses as well, but planners of any type run the risk of stepping outside what designers want to have happen in the game.

Squad-based stuff is a complicated issue that goes beyond your choice of architecture, though. A lot of it simply has to do with marking up things -- the environment, actions, objects -- so that agents can know what their partners are doing. This represents a sort of "shared knowledge" layer. e.g. "Oh, my partner has tagged that cover spot as his best choice, so I should go to THIS spot to provide support... and I'll tag that one so the other guys (including the first) know what my plan is."

My suggestion is that you get used to using whatever architecture you feel comfortable with first and then figure out how to do advanced things in it.

23 hours ago, IADaveMark said:

GOAP was a big thing 12 years ago when it came out. However, it quickly ran into issues with scalability. Also, it can be terribly inefficient due to the constant re-planning that is done every time something in the game state changes. It doesn't do any good to construct a 12-step plan if every second you have to throw it away and find another plan. Now imagine doing that for dozens of agents. This is complicated a little further by having agents depend on the plans of other agents. You really have issues about who is planning what first.

HTN is better than GOAP. Guerrilla used it well in the KillZone series. There are some other uses as well, but planners of any type run the risk of stepping outside what designers want to have happen in the game.

Squad-based stuff is a complicated issue that goes beyond your choice of architecture, though. A lot of it simply has to do with marking up things -- the environment, actions, objects -- so that agents can know what their partners are doing. This represents a sort of "shared knowledge" layer. e.g. "Oh, my partner has tagged that cover spot as his best choice, so I should go to THIS spot to provide support... and I'll tag that one so the other guys (including the first) know what my plan is."

My suggestion is that you get used to using whatever architecture you feel comfortable with first and then figure out how to do advanced things in it.

I really liked that GOAP resulted in “novel” solutions, which may never have been anticipated by the players, often making for excellent anecdotes that players will re-tell but I was worried that it could become cpu-intensive. I really like the fact that it can step outside of what designers want to happen in the game but I think we could minimise the randomness. Also as you say squad based stuff sounds pretty complicated, we might not need it for our game but it could be interesting to figure it out, as you say I'd pick the architecture first, get comfortable and then go for that.

What issues does it have with scalability? I thought it'd be pretty scalable cause you can just add a new action to the pool and let the AI take care of the rest.

As far as I've read HTN could become faster because of trimming some of the tree's branches but it doesn't allow for novel solutions as the tree is created by the designer.

On 2/6/2019 at 8:28 AM, Tipotas688 said:

I really liked that GOAP resulted in “novel” solutions

You can get that from a lot of AI architectures though. If you do my IAUS system right (or even a BT for that matter), you get a lot of emergent behavior. The only key is breaking things down into situational reading and very atomic behaviors. That is, instead of a designer saying, "I want the agent to do A, then B, then C." you can specify that reasons for/against doing A, B, and C individually so that sometimes they will chain together like that but other times they may use them individually, chain only a couple together, or splice something else in there as appropriate (e.g. D). The only difference in GOAP, is that it puts together the entire chain -- but as I mentioned before, that may get completely invalidated the next think cycle.

On 2/6/2019 at 8:28 AM, Tipotas688 said:

What issues does it have with scalability?

As you add new behaviors, these are new potential nodes in what amounts to a "pathfind" over the potential state space. By adding behaviors, you are increasing that state space geometrically. That is, every single step (or potential step) has that many more things to search through. So if you had 100 behaviors to select from and increased it to 110, not only do you have 10% more things to check in the first step, but each of those 110 nodes has 109 other things to check... which each have 109 other things to check. That 10% increase in behaviors really cranks up the potential search space. Now imagine doing that every think cycle for every agent.

FEAR ran into this when the designers created more usable objects and behaviors in FEAR 2... it quickly got to the point where the were killing themselves computationally.

On 2/6/2019 at 8:28 AM, Tipotas688 said:

As far as I've read HTN could become faster because of trimming some of the tree's branches but it doesn't allow for novel solutions as the tree is created by the designer.

See above regarding novel solutions vs. hand crafted. It depends on how atomic your behaviors are and what the preconditions (to use the GOAP term) are. Those can be linked but don't have to be.

Now balance that with the fact that an agent coming up with "novel solutions" may be counter to what you want because it is coming up with solutions that aren't Fun (note capital "F" there... for a reason) or don't serve the purpose of the game. It's something you have to be careful with lest you run into things you don't want to happen.

@IADaveMark all that is amazing, I have been reading about all the above AI techniques for a week now and I couldn't find something as detailed as what you wrote for GOAP and BTs.

I was reading about utility based systems and that they are pretty good and less specific like BTs but they need to be reworked each time you add something to the "network" so I wasn't sure what to check next.

2 hours ago, Tipotas688 said:

but they need to be reworked each time you add something to the "network"

No they don't. With my IAUS architecture, I am able to drop a new behavior in and the agent immediately knows how/when to use it along with all the others. (Similar to GOAP's expandability in that regard.)

See: https://www.gdcvault.com/play/1021848/Building-a-Better-Centaur-AI

12 hours ago, IADaveMark said:

No they don't. With my IAUS architecture, I am able to drop a new behavior in and the agent immediately knows how/when to use it along with all the others. (Similar to GOAP's expandability in that regard.)

See: https://www.gdcvault.com/play/1021848/Building-a-Better-Centaur-AI

@IADaveMark I had your video in my to do list ( I had already read your culinary guide to AI ), now that I watched it all makes a lot more sense how AI evolved from GOAP to what we have now. I have to now watch a few more of the videos you have in GDC's website and schedule what's needed to build such a big AI tool but I think it's worth the effort given the benefits.

I don't know how you have time to build such amazing tools and answer to random guys like me but I hope that I do good by this information and build something interesting!!

@IADaveMark

A bit late to the party, but I'm wondering:

How would you best incorporate multiple decisions that have to be made in parallel into your IAUS architecture? Say my character can (at the same time, in parallel) move and do something else, like shooting, healing themselves, etc.? So could do something like run over to cover and on the way there either shoot at an enemy or ram a health injector into their arm until they've reached cover. They could also decide that instead of moving over to cover, they should try to reach and go up some stairs so they get to a higher elevation that gives them a combat advantage, and again can shoot or heal themselves on the way there.

Do you think it would be advisable to just have two separate decision making steps and evaluate the action to be taken for 'what do I do with my feet' and 'what do I do with my hands' (or whatever) independent of each other?

That would seem like a simple way to do it but then what if I want the two decision making processes to influence each other? A real person might decide that either (move up stairs + shoot) or (move to cover + heal) or (do nothing with feet + heal/shoot) are good decisions, not only are the other possible combinations are a terrible idea, there still has to be a decision making process which of the valid combinations is the best one to take (kind of bad example in my case but you get the idea).

The way I've done it (and isn't unique to me) is to identify things by their category through a tagging system of sorts. One way I've done it is simply treating movement and other actions separate. Another is defining actions as upper, lower, or full.

This allows you a number of things. For example, an upper body action (shooting, looking around, etc.) will not stop the movement. However, you can also limit things from even being selected if you are moving OR you can terminate movement for certain actions (e.g. an elaborate spell cast or a full-body emote such as a bow). The good news is that you can also decide to preserve the movement destination so that the agent will resume where it was going prior to stopping.

None of this is really IAUS-specific... it's done for a lot of stuff.

I am both a big fan of DaveMark, and, a fan of GOAP - though it has some severe limitations which Dave points out. I think of GOAP as a 'Dynamic Script Generator' - given a particular Goal, a GOAP routine will search through all possible strings of possible Actions to find the 'best' (as defined by the programmer) one to use in the current situation. There are ALOT of ways to make GOAP more efficient (mostly methods to reduce the exponential search space by pre-filtering possible Actions given the situation).

But....

I really like Daves' IAUS system, but I don't think that it is useful multi-turn action sequences, especially at the level that GOAP can do it. But, it might be possible to utilize some sort of hybrid which focuses on the best parts of each - during Combat situations, IAUS is an all-around winner... but when talking about more 'simulation' environments (general townspeople doing townie things), GOAP action plans (Dynamic Scripts) work well because they rarely get 'interrupted' and need re-planning.

your thoughts, Dave?