AI discussion

[joveeater]

I want to start some discussion around the AI, particularly about what we'd like to see from it in future. I typically don't play with NPC's on and I've no experience of basecamp stuff at all, but from what I hear they're cool systems in concept with a few big flaws. I've also seen goods ideas for going further like having them be more active on the overmap. Really the aim here is more to look at some of the broken behavior they have but I think the way to approach that depends on what's wanted from them. Ultimately they're never going to be smart, it's more about ensuring their stupidity isn't too obvious in the normal course of play.

If we only want to clean up the current problem behavior we could just do that. Ad hoc rules systems (or "messy" ai) tend to give great early returns but don't scale well. I don't think the current requirements are beyond what's plausible but going too much further could be. Past that, we probably want a neater system, with some guiding principles and modularity. I will write up a proposal for a goal oriented action planning based system and post it here when I'm done.

I'm not planning on doing anything about this any time soon. I only want to write it now so that there's something concrete for people to look at and comment on and a lot of time to collect opinions and reconsider. Whatever we end up with overhauling it will take a lot of work and even when that's done it's something we're all going to have to deal with in future. I think the real thing we want from any neater system is to free us up from worrying about the AI's other behaviors when implementing new ones.

But yeah, more generally let's talk about AI, current issues, possible solutions and anything you'd like to see out of NPCs, basecamps, monster AI or whatever.

[chaosvolt]

Personally I feel like getting existing behavior up to a basic level of competence would be a good first step, but it would likely depend on how easy it'd be actually flesh out the existing code to do other "smart things" we want vs. burning the spaghetti down and overhauling it wholesale.

[Coolthulhu]

If I were working on AI, I'd probably try to make it into a decision tree, with some heuristic to grade decisions, and heavy caching where possible.
GOAP would work as well, but starting with a simpler tree could "get it going" faster, while still keeping possibility of switching to GOAP later. I'd expect the most work-intensive parts to be the AI inputs, especially if we want our AI to retain some memory about the environment.

The hardest bit will likely be combat: if our AI is to be able to plan, it must be able to "imagine" consequences of its actions and actions of other entities (at least its target's). Our Creature classes are heavy and use globals, so we'll either need to replicate them in a simpler way (ugly, bug-prone, work-intensive) or de-globalize it and make it possible to query RNG ranges and not just individual, random results (work-intensive, design-intensive).
The problem will exist for other AI tasks as well, but combat is likely to be the most convoluted task.

[thelonestander]

I feel like once bleeding, and "npcs" feeling pain gets implemented, this will be one step towards making the ai actually respond to what the PC (player character) does to various NPC's. This is of course before any AI changes im sure but would help with making them feel more alive. IMO.

[joveeater]

Lots of good points. I touched on the idea that just fixing up the current problems is a viable long term plan. I also think it's a short term necessity. Any sort of replacement will be a long time coming. Even adding new stuff like a better pain response is worth it right now and will be for a long while. The real benefit of an overhaul is going to be new and complex behaviors like maybe taking care of their own needs or repairing damage to their house. If there's no drive to do things like that, it'll just be a lot of work for very little real gain.

I think a decision tree is a good idea. Going from a tree to goap would still be a complete overhaul but going from what we have to a tree, while still hard, is a lot easier. It's kind of an ad hoc tree already, so it's definitely something to consider for the short term and also I think the best long term option if we don't want too much extra from NPCs.

A lot of the examples of GOAP show it working through a crafting system just because everyone knows how crafting works but it's fine for combat. F.E.A.R was the first big game to use it and it's often used for combat only agents in FPS games and similar. That said, you've cut to the heart of one of the big conflicts in GOAP. You need to model your engine and you really don't want to. The trick, especially for combat, is not to model much. A model of "hitting things can damage them" along with a goal of "deal damage to enemies" and an attack action with a prereq that you're stood next to them and that's enough for a zombie. Even with a more realistic model, combat goals should be short. They aren't going to try to plan victory from the moment they see the enemy and it's ok that they only know something like "high stats=more damage" rather than the specifics of how much.

I will go into more detail when I write this up, but you're very right that it's the inputs (i.e. prereqs for GOAP) that are the problem. For the most part you can just check the game state directly. This won't be true of some core systems like moving and items but everything else you just check the state in prereqs and then have "action X might satisfy prereq Y" as the model, inaccuracies can be glossed over.

You do still need to filter the state for things the AI shouldn't know, which is where a memory system might come in, but I think that goes no matter the decision making process they use. It's not something I've given too much thought though it did occur to me that player map memory isn't ideal and there's some overlap there.

[joveeater]

Wall of text incoming.

Goal oriented action planning is a fairly common system for games and there's a lot of literature on it out there. Briefly, it involves each agent having a list of goals and actions. Goals are a list of prerequisites with a numeric benefit, actions are a list of prerequisites and an effect with a numeric cost. We're going to search for the chain of actions leading to a goal with the best cost/benefit ratio. The real key to this is the prerequisites and effects. We need to model our game world in terms of them and we want it to be good enough for the AI but not mean we need to model the whole engine in detail.

I'd like to use an idea of recursive replanning. Actions can have a vague set of prerequisites that are satisfied when the plan is made and then when they're executed they cause more planning to happen. As an example, a woodcutter might only ascertain that they have access to an axe before making a plan to chop wood. As part of executing that plan, they'll make and execute another plan to pick up the axe. This lets us spread out processing by making vague plans and filling in the details later, it means we don't have to worry details will have changed because they're not checked until they're needed and it gives us a seamless way to go down to the turn by turn level without melting the cpu. So a long behavior like pathfinding would be an action that looks more like a teleport at the planning stage but then repeatedly plans a single movement action when executed.

I think we want some core systems that we model well, probably moving, items and combat. They'll have reusable prereqs and effects that mean you don't have to worry about things like pathfinding and the AI will have a better understanding of any consequences of actions it takes. I'll go into this more later, but most things are modeled with just actions can satisfy prereqs.

The real question is how to compose prereqs and effects. For effects, I think we want a primitive set of effects that are roughly one keypress, one actual action from the NPC. These are only available through primitive actions that have proper prereqs like components for crafting. Then building on the idea that actions can be vague, we also let you make actions that just promise to satisfy some prereq. This makes it easy to see where that action will fit in when planning and means that the engine doesn't need to understand how the action actually works. For instance the wood cutting action might promise to create a few logs at the NPC's feet. Inaccurate but close enough for planning. There'll also be a prereq that means "primitive effect was performed last turn" that actions can use when making recursive plans.

This moves all the complexity into prereqs. Complex effects promise to satisfy a prereq and complex actions work by recursively planning for sub prereqs. It's important that we have some amount of composition here, so that the planner can decompose it, but I want to avoid a DSL or any sort of real solver. I think we can provide simple composition like all of, any of, none of, but beyond that just write a new prereq in C. In order for the planner to use it you'll have to make an action that promises to satisfy it, but you can decompose it how you like there and you have the option to wait until the action is executed when it's safe to examine game state.

Prereqs, because they're checked during planning, can have more problems with that. Usually it's fine, but if you imagine a very contrived and generally bad plan like all_of(wield_crowbar, pop_crate, wield_axe, cut_tree) and what happens when the NPC is already wielding an axe. A good model might take into account that wielding the crowbar unwields the axe but most of our models won't be good. They'll instead rely on error handling, in this case it would just detect that the prereq is no longer satisfied and make a new plan for it no problems, but GOAP always has problems with changing circumstances and there needs to be stuff for detecting when prereqs aren't satisifed or no progress is being made and then backing off from failing goals where everytime it fails it'll complete more and more other goals before it goes back and tries again. It'll also occasionally check all the prereqs in the plan and plan more or skip parts if they've changed.

There's also problems of performance, even with the vague recusive plans keeping the tree shallow it can take a while to make a plan. Most games are realtime and can just run it in a background thread and have the npc stand around for a few seconds and I think we could emulate that. If an NPC spends too long planning (i.e. searches too deep), they idle for a turn and continue next turn. I think we want an idea of in and out of combat that disables this, but also that swaps out the goal/action list.

Combat will be the hard part and we do swap out more of the action tree than you might expect. Common actions like pathfinding are different because the combat version does a more detailed cost analysis that takes into account danger. I'll go into how you'd write all this, but goals are split up based on the situation, so the planner ends up deciding between shoot the mi-go, wield an axe and hit the mi-go, shoot the dog, etc, all with different benefit values. Goals should end with either avoiding or inflicing a danger. If the character can use a strength buff, it will always be as part of a plan to melee something and always weighed against just attacking it without the buff.

The combat tree differs from the non-combat one in style. It doesn't use recursive planning as much and it tends towards shorter wider solves with lots of redundancy and pays a lot more attention to cost/benefit. There'll be a core set of goals and actions for basic things like doing damage and improvements should mostly focus on improving their cost/benefit rather than adding new actions. They should have a more hollistic idea of costs and benefits. So wielding a better weapon before attacking should reflect not just the extra damage but also the idea that you'll be better equipped. Actions should pay attention to how long something will take and how safe it will be.

In terms of how this will be used. NPCs will have a 3rd set of emergency goals like don't stand in the fire that are always active, but otherwise non-combat goals come from their faction. I'd also like to look at the faction ownership stuff and give NPCs implicit knowledge of their faction's stuff. This gives them a little bit of memory and teamwork, fits nicely with basecamp stuff and keeps everything consistent. Even a solo NPC has a solo faction rather than seperate personal/faction goals/belongings. They also need good "distraction" stuff so they reconsider when there's a threat.

I want to do a declarative, generative style. Goals are functions that examine state and produce a list of goals. So "damage enemies" becomes "damage that mi-go." Then actions are functions that are stored against the prereqs they might satisfy and they take the same arguments and return a list of relevant actions. So the melee action takes the mi-go and returns an action to stand next to it and hit it, this action has an effect which is the function that will be executed when the action runs. This function can return another prereq for recursive planning (e.g. the moved ne last turn prereq for pathfinding) or just declare itself done. So the tree is being generated out as planning happens, note that we cull most of the tree by using a lower bound for cost/benefit and use closures for transient state like pathfinding's path.

I said I'd go into more detail on this point, you do need some idea of considering the consequences of your actions for good models but, because it plans backwards, prereqs should always just check the state. It's actions, specifically primitive actions, that might invalidate a prereq that's already been checked. This needs to be something fatal to the plan before we care, error handling will work around it otherwise. To allow this, actions are allowed to examine the current plan. Some core stuff like maybe not trying to use the same plank for 3 crafts might want this but for the most part don't bother. Error handling is enough that it would just smash some stuff for more planks anyway and hopefully, so long as there is a completable goal it should eventually complete it.

I say hopefully not just because of the halting problem but also while there's no such thing as a typical GOAP implementation, this one is very atypical. It hugely deemphasises the solver and model aspect of things, instead focusing on this recursive lazy planning aspect. This lets us go down to a turn by turn level, normally pathfinding would be done outside of GOAP entirely, and makes it easy to just stop every time we hit a primitive action and continue next turn. The real advantage though is we can allow NPCs to use non-core systems without really having to model them. If you want a new behavior that is a new goal and nothing but custom prereqs/actions, go for it. You can be sure that if your goal is selected, nothing will interfere, and there's a simple cost/benefit for choosing between behaviors.

So yeah that is a not so brief rundown of what I'm thinking. I'll give it a few months at least, but if people like it I'll look at a concrete implementation and do interfaces and code samples etc.