TIGSource Forums

Hi guys. There's much time since my last time here. I bought a programming book that teachs from scratch with Python and I'm taking it very well.

So I was thinking and had the conclusion that I want to fell a glipse of AI in games. Not a algorithm with three thousand lines, nor one with ten. But something that depicts the way AI work in a game. How NPCs take actions and how they "think".

Let's use english to create the algorithm not Python or other programming language, because I did not covered all its features.

Thanks in advance, guys.

AI is kind of broad, so it depends what kind of AI you want.
You said NPC, so I assume an RPG game. Well in most RPG games NPCs simpley have scripted dialogs. A scripted dialog is simpley a FSM(Finite State Machine).
A FSM is a set of nodes that are connected to each other. Each node in the FSM has "data", in our case that would be the dialog text. Each node also have conditions when and to which other nodes to move on when met.
For instance you want a dialog for a gate troll. The starting node would have a dialog:
"Me troll! Me want toll! 5 gold!
1) Pay 5 gold
2) Do not pay"
Now you get the player input. If the player chose 1 and he has more than 5 gold, the node will move to a new node which will have the dialog "Thanks! You can go!"
If the player chose 1 and he has less than 5 gold, you will reach a new node that has the dialog "Not enough! Me eat you now!"
If the player choose 2 it goes to a node "You no pay? Me smash you!"
So you see, the NPC dialogs are actually a sort of maze of nodes that are connected to each other with conditions. What are those conditions? You decide.

I wanted something more automatic without player intervention.

I mean: Lets say that the NPC has some stats and within those are included nourishment, hydration. And lets say that when they are low the NPC will look for food and water.

But how he will look for it, how he will find it and what will he do what will trigger his ability to see.

Lets suppose it's a 2D RPG.

Well, even for this you can use FSM.
Let's say the NPC is patrolling, so it's in a patrol state that tells him to patrol in some route. Now, this patrol node has a condition of if he sees something in his view he goes to the chase node. The chase node simpley chase the target. If he reach the target and it's hostile, it switch to the attack node. If not, it goes back to the patrol node.
For instance.
But those are just the decisions the NPC makes. In order for him to patrol and chase, you need to implement a steering behaviour. A steering behaviour is some function that helps the NPC navigate. It usually tells the NPC, go down, go left, go right, and etc.
For instance a chase steering behaviour might tell him to go right if the target is to it's right, go up if the target is above it, and etc.
A patrol steering behaviour would tell the guard to go left, right up or donw every step according to the route of the patrol.

So basically you need to mix FSM with steering behaviours.

So... lets say he needs to find the food, but it isn't with his view. How he would look for it. A random generated movimentation until he sees the food? Because a pre-programmed path would scape from being AI, woundn't it?

Also, I would like to give him the benefit of doubt. So he could actualy choose what he would eat if there are more than one type of food. With different characteristics of course.

Would this also fall under FSM?

There are multiple components of making such a thing work that would work well on their own as gameplay elements. Pathfinding, for example. Go look up A-Star on wikipedia (http://en.wikipedia.org/wiki/A*_search_algorithm). It's pretty straightforward to implement, particularly for a 2D tiled world.

Field of vision would be another one. There's different ways of doing this, depending on what type of engine you're using. Offhand, I would guess there is some type of raycast sweep involved, although there could be a more optimized way of doing it.

Other things I can think of would be knowing where the food and water is, as well as modeling "nourishment". I would suggest using a "static" approach at first, as that is way simpler than the "I see food, but I'm not hungry right now, so I'll add that to my database" approach. Having specific places in the game world where everyone just assumes is where the food/water are would be much simpler.

Of course, the specifics of how you decide to implement would depend on what the NPC is - a wolf, a person in a town, etc - they might be patrolling for some rabbits to eat or they might know that there's a great noms place down the street.

That's it. I could implement different behaviors to be used on the A* at each type of NPC as well different types of nourishment and vision, etc... All based on random generated characteristics, so the NPCs woundn't all act the same way.

A Finite State Machine doesn't have to take user input, but could take other inputs as well.

If an NPC's hydration drops below a certain level then it could perform a search for water.
The NPC could use a graph search (http://en.wikipedia.org/wiki/Graph_traversal) to try to find something, or could stop when whatever other end condition you may want is met.
There are many kinds of graph searches. In selecting a graph search one may want to consider:
Is the area bounded or unbounded?
What knowledge do we have of the area?
How much of the graph/area is visible/known?
Is the thing(s) being searched for plentiful, clustered, near or far?
Do we know the general direction and distance to the thing being searched for?
What are the costs/limitations on our search? ie. limitations on time, memory, area, cost to travel, etc.
Is the thing always up/down hill? ie water is down hill at trough/ditches/rivers/lakes/local minimums; snow is atop mountains, etc.

There are many types of graph searches one could perform:
Breadth First - exploring the nearest areas/nodes.
Depth First - If there are paths then we basically follow a path down until it ends, then explore all its forks and then we explore the next path all the way to the end and repeat.
Dijkstra's Algorithm - Find the shortest paths to all other areas from the starting area.
A* Algorithm - Like Dijkstra's but if we have a heuristic (an approximated distance to the thing being searched for) we could save some memory and perhaps time searching for this area/node. A* seems to be the primary algorithm to use for path finding in games.
Hill Climbing algorithms - always climb up hill until the thing being looked for is found, unless we get stuck at a local maximum, then we could use some kind of random walk to continue on from a local maximum to continue the search.
There are many others...

Supposing you have an AI that prefers to purchase some kinds of foods over others than you could have a priority queue (a sorted list of most favored to least favored) of foods he would eat. He would choose to eat the available foods nearest the top of the list. The NPC could make pseudo-random decisions if you don't want him to be too predictable (ie randomly chooses one of his top 3 foods).

If you want the NPC to make the best decision of what to eat to best meet his nourishment needs with limited stomach size then perhaps the knapsack problem is what you would want to look at. Knapsack problem algorithms could also be used to carry the most valuable items in one's limited 'knapsack'/inventory space.

A handy skill to develop is to be able to recognize related problems that can be solved using similar algorithms. To be able to abstract problems into more general cases where we already have algorithms to solve them.

Good luck Strelok.

Are there many games actually implementing this kind of AI? NPCs searching for food and etc... I thought maybe oblivion did that. But for the most part the player doesn't really see what the NPCs are doing in the world.

Thanks, looks like it'll take time till I fully understand everything that has been said here. But, given that, I'll look further to focus on that sort of thing. Now I know the right terms and I'll be able to sucefully search across the internet for tutorials.

I'll try to create a pseudo-code for this, and update it very often until I have something that can be really used.

I haven't had much experience developing games.
I'd imagine PompiPompi examples of FSM uses and TomHunt's suggestion of A* Search will likely serve many of a game developers needs as far as AI goes.

To be honest I can't stop thinking in what I can describe and name as "Caos Machine". It would be a "virtual world" where only NPCs lives. Every NPC would have its own characteristics and needs, as well as choices.

So a NPC could turn into a merchant while other would gather resources to use or sell to the merchants. It would lead to an incredible amount of choises, but if it would be even programmed it would just need a little push to start the whole machine.

I can't stop thinking about it. The wish to program something like this doesn't let me sleep some nights. I can see it working.

I can do this, I think. At least start with a little one like two NPCs in a little place, taking choices after choices so they can live and make their way until the local resources are gone. Then, if it works, I could add more NPCs and more choices, as well more resources until it become so big that it would be a real Caos.

I got to stop drinking cofee. :crazy:

I think tinkering with and modifying some simulations in NetLogo (http://ccl.northwestern.edu/netlogo/) could be a fun, quick way to see various mechanics and ideas working and prototyped within hours. Not saying to make a game or large project in it. But you could totally do some quick simulations of resource hunting, gathering and trading and get almost immediate feed back throughout the development process. You will be able to see what every little step of development does. Quite an approachable piece of software.

I'd suggest grabbing maybe one of the wolf and sheep models and modifying it to fit kinda what you want to test out. Perhaps add another kind of entity that can sell/trade excess food with wolves or something, you could have some wolves be more efficient hunters than others. You could add other resources, like berries, that could grow and be picked and traded or something.
 

FSMs tend to only be used for simple reactive AIs in action games and such. Although theoretically any AI could be expressed by an FSM, the complexity would explode very quickly in your case, so it's not a practical option. You need something more deliberative.

Game AI is dominated by two broad techniques these days: automated planners (http://web.media.mit.edu/~jorkin/gdc2006_orkin_jeff_fear.pdf), which work out plans to satisfy goals, and behavior trees (http://bjoernknafla.com/introduction-to-behavior-trees), which simply perform appropriate behaviors (the latter tend to be more reactive). You'll need to have your programming chops to implement either.

Prioritization of goals, and working towards them competently, will be hugely difficult for what you want to do. Even AI experts struggle in making AIs that have many needs and complex means of satisfying them. You can see this in the gap between hype and reality in open-world games, such as S.T.A.L.K.E.R. and Oblivion.

The best resource for game AI I've seen is Dave Mark's Behavioral Mathematics for Game AI.