April 19, 2013 | Dukus | 27 Comments
When I started this game, I knew AI was going to be a hard thing for me. I'm used to writing graphics code and low level system where the code execution paths are nearly the same every frame. For all the games I worked on in the past, I never looked into how the NPCs made decisions. I wanted the people in the game to do all manner of tasks. They'd live in houses, walk to their jobs, do the work, cut down a tree, go eat lunch, collect firewood, and go get a new shirt from the market. I had no idea how to make this happen or where to start. I tinkered with getting the AI to do simple things, and then built on that. I broke down all the things an AI could do into simple core tasks, which I call 'Actions'. These are tasks such as moving to a location, picking up an object, storing or retrieving something out of inventory, creating new objects, or playing animations. The AI then maintains a queue of actions to complete. Lets say I want to get an AI to collect food from storage and bring it to their home. The code would look something like this: Each item in the queue is executed until it finishes - MoveTo completes when the AI gets to the target. PlayAnimation completes once the animation finishes. Other actions like DepositInventory execute immediately and the next action is run. I call these chains of execution 'Behaviors'. The game has a lot of different behaviors, from how to hunt animals, to how to work at a building and use one resource to make another resource. Adding new behaviors and actions is easy. I could make two people walk toward each other, play an animation and play audio that shows they're talking to each other, then go about their business with just a few lines of code. (But I'd have to make the animation and audio first....) This came out as a very nice system and is very extensible. But then there is the hard part. How does the AI choose which behavior it should be using at any given time? Each AI has a set of needs that may or many not be urgent. They might need to stock their home with food or firewood. They might be sick and need a doctor. They might be cold and need to go home and warm up, or hungry and need to eat. They might have low health and decide to visit an herbalist. They AI might be a child and depend on parents for keeping the home stocked. In the best case all needs are met and the AI should just do some work so the town can prosper - if they have a specific profession and workplace this is easy - but if there is no work available they need to help around town with general labor. These things don't sound like nice programming tasks. This is where I ask myself if I've made too complex of a simulation.... But to deal with it I turned to something I do know. State machines. There are different states of working versus attaining needs, and there are different versions of each of those for when an AI is a child, student or adult. Each time the action queue is empty, it signals the AI to make a new choice or change states based on needs. The needs are prioritized based on severity - freezing to death is more important to take care of compared to getting a new tool. Deciding what job to work on is handled simply by ranking jobs based on urgency and distance from the AI. Each state is simple. Here's what the normal and attain needs states looks like: I implemented all this and then decided this wasn't really AI - it's a conglomeration of state machines, fifos, priority queues, and a few conditionals. But magically when hundreds of AI's are running the state machine and executing behaviors, it looks awesome and the town is alive with activity. This system could easily be extended to give the AI's more personality. I could have different states for lazy workers that idle more often than not, or people that won't work when their health is low or if they have to walk too far. But for now everyone is a well behaved, hard-working citizen.
// head to the storage facility or market
ai.AddAction(MoveTo(storageLocation, Animation_Walk));
// get something out of inventory and display it.
ai.AddAction(PlayAnimation(Animation_BendDown));
ai.AddAction(RetrieveFromStorage(storageLocation, foodType));
ai.AddAction(PlayAnimation(Animation_StandUp));
// go home
ai.AddAction(MoveTo(homeLocation, Animation_Walk));
// drop inventory
ai.AddAction(PlayAnimation(Animation_BendDown));
ai.AddAction(DepositInventory(homeLocation));
ai.AddAction(PlayAnimation(Animation_StandUp));
void State_AdultWorking()
{
// check to see if the ai is doing something
if (IsBusy())
return;
// do more work, idle, or change state
if (AreNeedsMet())
{
if (!GetNewTask())
ChangeState(AdultIdle);
}
else
ChangeState(AdultAttainNeeds);
}
void State_AdultAttainNeeds()
{
if (IsBusy())
return;
if (AreNeedsMet())
ChangeState(AdultWorking);
else if (IsFreezing() && CanAttainWarmth())
ChangeState(State_AttainWarmth);
else if (IsSick() && CanAttainDoctor())
ChangeState(State_AttainDoctor));
else if (IsHungry() && CanAttainFood())
ChangeState(State_AttainFood);
else if (IsUnhealthy() && CanAttainHealth())
ChangeState(State_AttainHealth);
else if (!HasClothing() && CanAttainClothing())
ChangeState(State_AttainClothing);
else if (!HasTools() && CanAttainTools())
ChangeState(State_AttainTools);
.... // lots more needs omitted.
else
GetNewTask(); // couldn't attain any needs! try doing work instead, will retry later
}
Wow - that's really elegant.Enjoying the updates - keepem coming 🙂
Can't wait to play the game, this sounds more and more awesome for every post I read.
If you need help with the AI part, I am studying computer science with specialization in artificial intelligence at the Norwegian University of Science and Technology - and I'm going to write my thesis next year (starting after summer). I was hoping to base it around a game, so feel free to contact me if you want =)
Me too i can't wait to play the game. It's look really good for every post i read !
Post more and more, this up my excitation =]
Awsome man! really like what you are doing here, keep it up!
Look into goal oriented action planning.
Goap.
https://github.com/stolk/GPGOAP
Actually, your AI is closer to AI then you would imagine. Take a look at Maslow's hierarchy of needs: http://en.wikipedia.org/wiki/Maslow's_hierarchy_of_needs
Basic psychology that generally humans abide by like based on needs/wants: water, food, bathroom, shelter -> safety (home security, family, defense) -> love -> esteem (respecting yourself and others) -> self-actualization (morality, creativity, etc). You can probably omit self-actualization, but keep love in there since you plan to have families and all that stuff in the game.
I BARELY understand anything about programming and this was even interesting to me, great update 🙂
Seems very lifelike
Looking good - Although this just confuses me completely, its has got to be a good thing that AI's do work and do it properly and promptly.
If you're in the game playing mood over the next few days, can you take some more background screenshots? Would love to see some of your updates in action (albeit a frozen photo action) and maybe a backdrop or 2?
Here's a thought:
When determining what weight each task has when deciding which to queue up next, have two items factoring into it. One is the individual's weightings, whether they are lazy, industrious, germophobic, etc. and one is society's pressures. You can have a person who is very lazy, but will be more motivated to work in a society of hard workers.
You won't be able to influence the individual's values, but society's values can be affected by how able you, as their caretaker, meet each need. If you have a lot of people constantly in idle states, society's work ethic falls. If you're prudent in dealing with disease, your society will prioritize cleanliness.
And another: each child born to parents inherits a randomized portion of their traits. If both parents are industrious, the child is more likely to be industrious as well. While each child is in their formative years, their values will change as society around them changes. This way, the player will have an indirect say in the direction their society takes. This will also go a ways into making sure there isn't one "best strategy" to keeping your village happy. Each will have their own needs based on its population.
The difficulty with implementing this idea is effectively communicating it to your players. If the effects of their efforts aren't felt, it may become tedious and unrewarding to try to cultivate a town to behave a certain way.
Interesting. Would not having those many else if statements running on 100s of AIs not lag the system? I would imagine there could be a more efficient method rather than running through a needs list each time.
Either way, you seem happy with the result and I can't wait to get my hands on this!
I would agree with Ray about Maslow - but if you want to introduce some better variability, you'll need to add probability to the state machine - weight the activities and use a RNG to select one of the outcomes. High priorities get a high score, and low get a low score, but still have a chance of happening.
You can't go wrong with State Machines - Easy to understand and quick to prototype. But if you plan to scale this up much more you may want to consider a more modern approach.
My team and I have recently given Behavior Tree's a go and they're really nice!
I think the other big bonus with BT's is that you can quickly and easily grab a lightweight template framework and get going really fast. If you're at all interested in revisiting AI a bit later be sure to bookmark a project like TreeSharp as something to look into: code.google.com/p/treesharp/
Regards,
Scott Richmond.
Lead Programmer @ War for the Overworld.
Awesome stuff.
A common issue with games is the "single mindedness" of the characters. Could you consider combining any of these tasks?
* buy multiple items from the market at the same time
* Combining tasks: take an item from the home to storage, pick up another item to take home
* task interruptions (safety concerns: a fire breaks out for example)
* optimizing tasks for alternate factors: time of day, seasons, to interact with other characters, etc.
Awesome! I'm really looking forward to playing this game, you've done great work.
@curiosity. I keep framerates high by having updates like this happen periodically - not all AI's update the same frame or every frame - twitch decision making isn't needed.
@Flammy: I know what you mean about single mindedness - but I also want players to be able to expect the people to do what they want. However the example I posted is slightly simplified - people will grab enough food for the family for a while, while a husband is doing that, the wife may go collect firewood. Task interruptions are implemented and can and do occur.
"It isn't really AI"
Well no, but then maybe it doesn't need to be? We're dealing with a game in which a player is managing a system in order to accomplish a goal (i.e. not die), as opposed to a game where the computer needs to make its own decisions. The latter is usually found in game formats where the computer takes the role of an opponent, such as an RTS game. In a game like this, I think a systematic approach to behavior is actually quite appropriate.
Very useful - I'm going to implement some AI in my own game soon, and I'm going to use some of your ideas for sure!
Hey man, really neat to see some insight on how AI for games is developed. Could I make a recommendation? In your "State_AdultAttainNeeds" function, you list out individually each state in a way so that it's essentially a priority queue via short-circuiting. Why not change it to do so dynamically? Maybe (since it looks like you're in Java?) an array of pairs that you iterate through and check.
Just a thought. It would increase maintainability, allow you to add future states fairly easily, and minimize code bloat.
By the way, really excited to see how this goes. Even without combat, I've been looking for a Stronghold-esque game and have been sorely disappointed.
-Alex
It would be great to have some "idle" animations for citizens who are not or don't need to be doing anything, maybe they could find some grass to sit on and read a book, or lay back and catch some rays or something?
Anyway, looks amazing! Thanks for the update!
Cool beans. Creating AI seems like a daunting task, so it's good to see that you have a handle on it as well.
Working off Alex' idea, you could have a state/modifier "DNA" for each citizen, where there are individual weights (or weight multipliers) for each action and/or action category.
Each individual could have their own little quirks and really bring the simulation to life.
It would fuzz the behaviour patterns, so that the player can't treat the people of your village with "hard math" to optimize resource use - you have to treat them as people with flaws, interests, talents, etc.
You could also go all out and mix this "DNA" when citizens have children.
On another note, I absolutely love that this game will be set in the same time period throughout the game - I don't really like it when I have to tear down my buildings regularily to build the same building from the next "age".
I think the AI in the Tropico series of games might be a good inspiration for this game. The AI in there seems to balance needs vs. work quite well. They do all the things you mentioned like buying food, going to work, driving if there is a garage nearby etc..
They also set aside a certain number of hours to work, and spend the rest on recreation which might be a good future feature for this game.
The control architecture you've used for your FSM is a simple version of subsumption architecture. It's probably the best solution for reactive control, but you're right it's not AI. That said. it doesn't need to be. Since each individual has a different controller, emergent behaviours should occur. I think where it gets difficult is when you want them to be conscious of each other - at what point should two nearby individuals stop and talk to each other? How likely are these two to want to do so (are you modelling relationships?)?
Oufff, I just stumbled on this little jewel of yours. You are are creating what I have dreamed of since years. I am a vivid Simcity, CIV, 1503AD, The Settlers, Northland, etc... Player and I love this stuff. What I have seen here pleases me a lot, this is actually just wonderful. Two thumbs up for the great work and I will now keep an eye on this. I'm a buyer, that is sure! 😉 I will link your site and and creations on SC4Devotion.com and Simtropolis.com in the next weeks.
mrb
Much of Game AI is considered "not really AI" but that doesn't matter. The goal is not to produce "intelligence" but a fun game. State machines are a fine choice! 🙂 Behavior trees and utility functions could also be interesting here but state machines are simple to understand and code, and that's the reason to start with them and only use something else if state machines don't work for you.
I agree with Dan on the idle actions, it bothers me that in many town/civilization building games your people are perfect little pawns with little to no quirks or personal actions/preferences.
It's the difference between running a town and running a military camp. Personally I find the idea of running a town full of imperfect townies more interesting. It's like in Crusader Kings when you get kings/wives with dodgy traits and you wonder how that's going to develop in the future.
Is there a reason you're using if/else instead of a switch statement? Are there advantages to this?