I’m currently working on a base building game. For context think Prison Architect or Rimworld, but where your base is actually a starship that can be moved around.
One decision I keep coming back to is how to best handle tasks - those “orders” given by the player that the AI agents carry out. An early decision was to track the tasks spatially so when an agent needs a task to do it can quickly and efficiently find one that’s nearby. The thinking was that it would be much more efficient if the agent wasn’t having to always move long distances to do things.
However, there is an amazing amount of friction involved with getting this to work right and deal with other task related things such as priority, targets of opportunity, and so on - things that would be completely a non-issue if the tasks were just all put in a single queue ordered by priority. The agent would then by default carry out the tasks in the order they were added to the queue. This seems like what most similar games do.
So what are your opinions of how tasks should be handled in this sort of game. Is it a set-in-stone expectation that tasks are carried out in the order the player adds them (with the ability for manual change in priority)? Or should an agent be able to make complex decisions about what to do next based on various criteria, such as proximity?
I think players will have expectation Unit will perform tasks one after another sequentially as they appear in the queue. Unless you added a checkbox option something like…
Perform tasks based on max efficiency
Or whatever you want to describe it (based on proximity, etc).
Then player is aware and knows why the Unit is not strictly following the order in the queue. Actually this would be pretty cool I think. Possibly a “selling point”. I have not played a modern base building game in a long time so maybe this kind of thing is normal these days. It wasn’t when I played.
If I were to ask a mechanic to replace a circuit board at the front of the ship and then recalibrate an emitter right next to her at the back of the ship, it would be frustrating if she walked all the way to the front and then all the way back. I think you’re right to consider optimizing the task plan.
Whenever the player adds a new task, you could run a simple utility function on the task list and do the task with the highest utility. The utility function could take these things like these into account:
NPC is currently pursuing this task (to reduce dithering between tasks)
Closeness to NPC
Urgency (e.g., extinguishing a fire is more important than scrubbing a toilet)
I actually used this for awhile, as well as goal oriented action planners. The problem I ran into was the whole target evaluation part of it. There are just so many possible tasks to evaluate by so many units - it quickly blossoms into a huge number of evaluations that can be taking place. I can see the value and (alleged) simplicity in utility systems, especially for FPS type games where there aren’t a huge number of things to evaluate, but I eventually decided it wasn’t as good of a fit for this type of game and switched to behavior trees. Perhaps some sort of combination of the two - filter down the possible targets in some sane way such as proximity, then run those through a utility function.
Part of the problem here is it’s not just the job that’s important. If a job needs a resource, would that resource also be on some queue to take? Otherwise you’re back to needing a search function, probably some dijkstra/breadth first search to find the easiest/closest to get resource. Basically don’t expect to get away without having to query space.
Right, searching for things is pretty integral to this sort of game so that isn’t going away. I’ve built up a nice tag-based threaded searching system for this which works quite well. Anything that needs to be searchable - including things like “relaxing, quiet area” can be added to the index and searched quickly and spatially. The tasks are currently handled that way too. I guess there’s nothing stopping me from keeping them in the index and also adding them to a priority queue. But that feels a little messy and error prone.
In theory, when evaluating the efficiency of a task we’d want to identify required resources, path cost to those resources and back, even some sort of optimum path through several resources and back. Utility functions seemed ideal for this sort of thing, but ugh. I think the agents don’t need to be that smart.
Utility functions and behavior trees go well together. A top-level utility function would determine what to do, and the behavior tree would specify how to do it. Good points about resources. You’ll also need to put reservations on resources so two janitors don’t go for the same mop at the same time. You can just factor that into the utility function, though, so it’s almost a freebie.
I’m with @TonyLi on this, in that I would expect my agents to have enough common sense to tackle the to-do list efficiently. So, a nearby task should take priority over a far-away one, all else being equal.
I’d just use a utiliy AI; those produce very natural, understandable decisions and are easy to tweak. For example, you could keep track of how long ago each task was assigned, and give more weight to older tasks. So, agents would sort-of do them in the order given, and sort-of favor working efficiently. Even an onerous task would always get done eventually, and an easy task at hand would usually get knocked off right away. Sounds good to me.
Instead of the checkbox option @GarBenjamin suggested, I would suggest some way to mark tasks as “Urgent!” The utility function could simply ignore all non-urgent tasks if there is an urgent one waiting to be done. So, the player can still force some things to happen right away, regardless of efficiency, when the need arises. But most of the time, the natural behavior should be fine.
There’s usually a difference though between jobs that are spatial and jobs that need explicit priority. There isn’t much of a reason why a crafting job has to be searched for outside of pathing to a bench, and the order of crafting jobs is usually pretty explicit. On the flip-side, mining and gathering are weightless, so the only issue is what is closest. After that it’s just a matter of getting the agent to determine what task they want to do.
It seems beautiful when talking about it. In practice there were two major scenarios I ran into which resulted in me switching to behavior trees.
If I have 100 agents and 100 tasks, that’s potentially 10,000 evaluations taking place. That is a lot, and when path cost and the like are factored in it becomes very problematic. Or I’m missing some fundamental concept.
I’m simulating pressurized rooms. When an agent gets a task that requires traversing a low pressure area they must first go get a pressure suit. It becomes kind of a chicken and egg thing - the utility of getting a pressure suit requires knowing about the utility of doing a particular task. It became something my old brain wouldn’t wrap itself around.
Both of these scenarios become much more manageable using behavior trees, at least in my brain.
You only need to evaluate when an agent gets a new task or its current task becomes blocked. And you can spread out the evaluation over multiple frames using threads or coroutines. Utility functions are usually pretty fast to compute. You only need to select/build a plan after the utility functions specify which goal to plan.
You could put that in the utility function – a quick check whether the destination is on the other side of a low pressure area. Or just add the number of crossed low pressure areas to the distance computation.
Yup! Always helps to have a sounding board here on the forum.
Therein lies the problem - this isn’t a particularly quick check. It requires coarse path finding to determine what lies between. It isn’t just a line of sight sort of thing, and since the player can make any sort of shape they want there’s not way to precalculate anything. I mean, I had most of this working, it was just mind-blowingly complex and felt very brittle. I’m not disagreeing with you - it’s very likely the right way to do it, but it just didn’t gel in my head enough for me to pull it off in a clean way given my current architecture, and I’m already on my 3rd complete AI replacement and not currently inclined to do a 4th.
If I decide to revisit I do have a single “evaluate task” behavior tree node that I can most likely just replace with a utility system. In fact, the game is fully moddable so someone could do that themselves if they were so inclined (supporting that adds another layer of complexity to the question as well). Maybe once everything else is in place I will be able to visualize that better and give it another shot.
Steering back to the original question, it sounds like we have the same two schools of thought I started with: The player expects tasks to be carried out in the order given; the player wants tasks carried out in the most efficient manner possible.
Rubber Ducking works for design as well I think, not just debugging, and forum people are at least as good as ducks.
When the player adds a new task, what about a quick check if the new task is very close and quick to accomplish? If so, maybe the agent can just get it done (i.e., add it to the front of the queue) and then resume its previous task. Otherwise add it to the back of the queue. I think this would be a good compromise. Game AI is “soft AI” after all; it doesn’t need to be 100% correct all the time. This is a cheap way to get rid of the really obvious dumb behavior, which is what I think players would mostly notice.
Oooh, that has some promise. Actually assign the task to a specific agent at create time when it passes a subset of the usual selection criteria. This goes well with the “target of opportunity” thing too where an agent will see multiple tasks near each other that require the same resource and will carry all of the resources at once instead of going back and forth for each task. Both of these require agent-specific job queues to allow assigning multiple tasks to an agent.
When I started this project almost 2 years ago I remember thinking that A* pathfinding would be the most complex bit. I was mistaken.
Always helps to have a sounding board here on the forum.