ID:40900
 
Keywords: ai, design

I recently started implementing an AI for NPCs in Scream of the Stickster: Volume II, since many of the games available in it are team games and would be fun if you could play them even without waiting for your friends to show up. The project is quite large and probably won't be finished by the time the game is ready for release. However some of the techniques involved are applicable to anyone wanting to implement NPC AI in their own games.

AI is a tricky business for a lot of reasons, but there are two big things that any good AI should handle: complex decision-making and knowledge management.

State Machines

While the guts of the decision-making process are outlined more below, it's helpful to first take a look at how most AIs operate. In most game AI, the algorithm is usually some form of state machine, which means at any given time the logic is locked in a certain "state"--which has some kind of goal--and takes actions based on that state. The state can be changed by different circumstances like timing, or the attacker suddenly becoming powerful (think Pac-Man), random chance, or even a primitive emotional system that can feel fear and aggression. The simplest state machine has two states: Pursue and flee.

For a moment imagine a space combat game where your ship can rotate freely in a 2D field, and so can all your enemies. An enemy could do well with a small set of states:

  • Flee player and scatter
  • Flock: ignore player but seek to join a formation
  • Phalanx attack: still keeping formation, alter course to attack player
  • Circle attack: try to attack player from a direction away from other units

Flocking is a whole different subject, but it's pretty clear why this kind of enemy would be dangerous. Their tendency to attack in groups would make them formidable foes. As long as more than one enemy remained, the flocking option would be available to them. A formation could come at you in a wide group and some could break off, trying to outflank you. The decision to change tactics could be made mostly at random.

The decision-making process explored here is a little more complex than that, but it comes from the same family. That will be discussed more in a bit, but before an AI can make decisions, it needs something else: knowledge.

The Basics of Memory

The players' enemy, the Stickster, is more or less omniscient. He knows the whole maze, including any changes to it (like a wall breaking down) that he wasn't around to see. His AI is actually tweaked to make him more likely to run into temporary barriers and such, which he might not otherwise do. The Stickster knows everything because in this environment, knowing everything is easy; you just have the language look up any info you want. Knowing nothing is easy too, though without info your AI won't get very far. But players don't have the luxury of omniscience, so why should NPCs?

My NPCs so far have a few basic lists that keep track of everything they know. These are:

  • Open spaces and what the wall structure is around them
  • Walls
  • Ladders
  • Other objects

As the AI progresses in development they will also be made aware of other things, like clues in a scavenger hunt. They should also be able to know anything a player would normally see: the Stickster's relative location, info on a target in Stick Tag mode, etc.

Every time an NPC moves, a function called See() is called that updates what they know. That means spaces could be added to the list (even ones that used to be walls), and objects could appear or disappear from view.

Knowing Space

The list of known spaces is not simply a list of turfs, but an associative list. It also carries one important piece of info: the direction flags, when the AI last saw them. Every open space in the game has flags saying which directions are walled off. The NPC remembers what these flags last were--so if you break down a wall and the NPC isn't around to see it, they'll think it's still there.

The known spaces and turf lists come into play as the NPC tries to find a path from point A to point B. They use simple A* pathfinding, but it only explores about 100 turfs and gives up, just bringing the NPC closer to their goal. Diagonal moves are allowed, but only from spaces that are known to allow movement in that direction.

Every turf in their pathfinding routine has a cost to it. Spaces are the lowest cost of all. If a crayon barrier is known to exist in that space, the AI will remember it and add to the cost if the barrier is one they can't cross. Walls have a higher cost, but not severely high; NPCs can shoot through them. Finally, any unknown turfs are given a cost that's about 1/3 the cost of a wall, with the idea being that's roughly the amount of walls a player can expect to encounter in an unseen area; this may be on the high side but further experimentation will help.

Once the pathfinding routine runs, a path is created from the NPC's current location toward their goal. But that path only runs as far as the known spaces; after that it is chopped off. The idea is that once the NPC sees more of the map, they'll know more so they can calculate a new path that's even closer to their goal.

Ladders and Z Levels

Ladders are permanent objs on any map. They don't move, so once they're seen they can be remembered very easily just by keeping a list of them. (What's more, if you've seen one side of the ladder, you know where it goes.) They're needed to cross from one z level to another.

If an NPC decides they want to go to a spot on a different z level, they have to use ladders to get there. That means there are three possible choices: 1) If they're at a ladder going in the right direction, climb it. 2) If they've seen ladders going in the right direction, head for any of those ladders. 3) If they haven't seen any such ladders, explore the current z level until some are found.

I haven't touched on the exploration process much yet because that's more of a decision thing than a knowledge thing, but basically the idea is to pick a turf at random from the map that is not yet "known", and head there. Once the turf has been seen, it is considered "explored". This is just the smallest of several goals the NPC has. The top goal is to get to a certain location. The second goal is to get to the next z level. The third goal is to find a ladder, and the fourth is to try to find one by going to a specific spot. If an appropriate ladder is found at any point, the third goal has been met (which means the fourth is also met), so the NPC then chooses a new goal: Go to that ladder.

Items and Memory

The real heart of the knowledge system is here: object memory. Basically the NPC needs to remember that it has seen certain types of objects, excluding decorative objs like bones. NPCs need to remember the locations of barriers, weapons, scavenger hunt items, and flags. Barriers can be destroyed; any of these other items can move. Unlike ladders, these objs can't be kept in a simple list.

Why not just use a list, though? Because the objs in it can not only move, they can disappear entirely. A weapon, item, or flag can be picked up, and destroyed if used. The objects could also move to a new location, if the player carrying them dies and drops them. If the NPC has just a list of these objects, then it also automatically would know two things: 1) that the object still exists, and 2) where it is. When we remember things we remember not just what we saw, but where we saw it. We also don't remember which specific object--out of a bunch of identical ones--we saw unless it has some sort of identifying info. If I saw a green pillow on a couch and someone swapped it for a different green pillow, when I returned I would never know the difference. But if the green pillow is put through a wood chipper, I shouldn't have knowledge of that unless I saw it happen; for all I know the pillow is still where it was.

For realistic AI, NPCs should have this same limitation. If they only keep track of which object they saw, they rely on the omniscient system to tell them where it is and if it still exists at all. If they keep track of the object and where they last saw it, the system will still give away when the object has been destroyed. The AI won't be aware of this as such; it will simply forget the item ever existed. So an NPC needs to keep track of what type of object they saw, any specific details about it that are relevant, and where they saw it.

My solution here was to create a datum. This datum stores info about the type of object but not any specific reference to the object itself. So if an NPC sees a boat, a new "memory object" datum is created saying the NPC saw an /obj/item with icon_state="boat". If the NPC sees a barrier, it will remember who the barrier belongs to--since players can pass through their own barriers. But if at any point the NPC sees that the turf that held these items doesn't hold them anymore, or holds different items, the datums are updated. This is what the datum looks like:

ai_obj_memory
var/turf/loc
var/objtype
var/info // may be icon_state, team, owner, etc. depending on object

var/gone
var/ai_obj_memory/next

The last two vars deserve some mention. When I'm checking a turf for new objects that have appeared, I'm also looking for old memory objects to delete. Before I look for new objs I set gone=1 for all the old ones. If I find a new obj that matches something already in memory, I reset the var to gone=0; otherwise I add a new memory object. After that, any objects with gone set have either been moved or destroyed, so those memory objects are deleted.

The next var helps me keep these objects organized in a linked list. Instead of just keeping one big list of memory objects, I organize them by turf. known_objs[turf] points to a memory object and that points to the next one in the chain, and the next, etc. There are other ways you could organize this of course, but this system seemed to make the most sense considering how often I need to loop through every object in a turf (like during See(), when all this info is updated).

Goals and Distractions

The way NPCs get where they need to go is based on a series of nested goals. If an NPC has no current goal, it chooses one based on the circumstances. As a fallback if no better choice is available, the goal will be to explore an unseen or random part of the map. Once this goal is set, another proc determines if it can take any direct action to accomplish that goal--like laying out a path to follow--or if another goal is required to achieve it.

Goals are kept in a list, with lower and lower priority as they pile on. The lowest-priority goal is the one the AI tries to pursue at any given time, but as soon as any goal is fulfilled, any of the sub-goals beneath it are dropped. Some basic goals that are available now are:

  • Go to a certain z level
  • Explore until a specific location is seen
  • Go to a specific location
  • Explore until a certain type of obj is found
  • Hunt down a specific target (given rough info on their location)

Now let's run that through a hypothetical scenario. If the NPC is on z level 1 and wants to go to a spot on level 3, that's the first goal. Because the NPC isn't on the same z level, a sub-goal has to be made: Climb a ladder if one is at hand, go to a known ladder, or find a ladder. If this NPC is new, the goals look something like this:

Explore to 21,8 on page 3
Go to page 3
Explore until a ladder to page 2 is found
Explore to 35,29 on page 1

Here the AI has decided that it wants to visit page 3 (in the game a z level is called a page), which means first it needs to find a way to actually get there. Getting to page 3 is the secondary goal. To get to page 3 it must first get to page 2. With no known ladders, the AI has to go on a search for some; this is the third goal. In order to explore, the AI needs to pick yet another random unseen spot to visit. Because the NPC is searching for a ladder, it restricts this exploration to the page it's on. Picking a random spot on the same page is the fourth goal in the chain.

As soon as the NPC sees a ladder, the third goal has been fulfilled. Once again the AI is in this state:

Explore to 21,8 on page 3
Go to page 3

Now that a ladder has been found, a different sub-goal can be chosen:

Explore to 21,8 on page 3
Go to page 3
Go to the nearest ladder to page 2

Once the NPC reaches a ladder, this new sub-goal expires. At that point the obvious thing to do is to climb the ladder in order to get closer to achieving the main goal, so the NPC will do so. Now the NPC is on page 2 instead of page 1. The second goal has not yet been fulfilled, so new sub-goals are added to get the NPC to page 3. Eventually the NPC will reach page 3, fulfilling all but the first goal:

Explore to 21,8 on page 3

At that point, the NPC can use the pathfinding algorithm to try to find the fastest way to the designated coordinates. Once that turf is in sight, the main goal has been fulfilled.

Because there are situations where the AI may want to temporarily override their goals, the AI is allowed to look for and pursue "distraction" goals. The AI will actually try to find any appropriate distractions unless it's already "distracted". A typical distraction is to pick up an item that is currently in view.

The Loop

Now that all the theory is down pat, let's take a look at the core loop that handles all of this:

proc/DoAI()
if(KillEnemies() || FollowPath() || owner.nextmovetime > world.time)
spawn(max(owner.nextmovetime - world.time, 1)) DoAI()
return
var/ai_action/action = SmallestGoal()
if(!action)
ChooseGoal()
action = SmallestGoal()
if(!action)
spawn(10) DoAI()
return
PursueGoal(action)
spawn(max(owner.nextmovetime - world.time, 1)) DoAI()

Without knowing exactly what goes on in those procs, you can probably pick out the gist of what they do. In the first part of the loop, the AI makes a priority of attacking any enemies it has a clear shot at, or otherwise following any path that has already been laid out by the A* pathfinding algorithm.

ChooseGoal() is, naturally, a major powerhouse. This exists only to choose the "top" goal, which may vary based on the NPC's situation and personality. If nothing else is found to do, the NPC will explore or wander to a random spot. Then SmallestGoal() looks for any completed goals and chooses the lowest-level sub-goal to act on.

PursueGoal() is also a major proc. It has several possible outcomes: 1) find a distraction, 2) create a sub-goal as needed, 3) take immediate action (like climbing a ladder), or 4) use the pathfinder to build a new short path to follow.

Obviously this loop obscures a lot of complexity in the AI system. This is just the simple core that farms everything out to other procs that make the real decisions. Those procs are still fledglings themselves, and this loop is subject to change, but the basic concept seems to be working so far.

Speed Boosts

This AI could potentially be used for several NPCs, so it's crucial to keep it fast. A few tricks are employed to make this algorithm speedier than it might otherwise be, and those same tricks can work in any system you develop.

I mentioned above that the known_spaces list is an associative list; the known_walls list is too, so I can set known_walls[turf]=1. It might make sense down the road to combine the two lists, so if known_spaces[turf]==0 that means the turf is a wall, whereas a null value means the turf isn't in the known list at all. But I digress. The reason associative lists are used here is that BYOND has a fairly efficient internal way of looking up items in them. By contrast, an operation like (turf in known_walls) is slower because it has to run through the list item by item to find the turf. For the same reason, if you can set list[turf]=null instead of using list-=turf, you've saved the engine a lot of time.

The pathfinding algorithm, too, is based on a concept of taking short hops nearer to a destination. The algorithm currently only explores a small number of turfs, so it doesn't try to find the ideal path to a target--it just tries to find a path that's good enough. The AI can get away with this because it's possible to shoot through walls.

Use view() and similar functions as sparingly as you can. Calling this repeatedly will just make BYOND do a lot more work. If you need to access this a lot, cache a copy of it temporarily. This is much kinder on BYOND because not only are you not repeatedly asking it to do the same calculation, but you're also not asking it to create and destroy lists all of the time.

Another important thing, and this I've mentioned before, is that if you can at all avoid using the del() function, do so. Let the garbage collector delete anything you can, by simply dropping all references to a datum or whatever. BYOND is smart enough to know that if you've stopped using something, you want to get rid of it. Using del() forces the engine to look for any stray references and delete them. Although this process is often fairly fast, it's nowhere near as fast as an object simply falling away into oblivion.

The Results

The ability to break down goals into smaller goals allows for some fairly complex actions to be handled much the same way that any human player would. Having a "memory" for the AI that doesn't rely on magic omniscience means the NPCs are limited to the same kinds of info a real player would have. The result is an NPC that can act more or less like a person. There are always limitations of course. The ability to plan ahead or predict others' actions require higher-level intelligence. And AI is a little more predictable than humans and can't necessarily adapt to every circumstance. But when it works well, it's remarkably effective. Even in relatively simple tests so far this algorithm has proved to be quite smart, and adding new tasks is relatively easy. In a game as complex as Scream of the Stickster: Volume II, being able to add new actions is extremely important.

Lummox JR wrote:
The real heart of the knowledge system is here: object memory. Basically the NPC needs to remember that it has seen certain types of objects, excluding decorative objs like bones.

If they recall bones, they could alter their goal to return or avoid the area. As a player, if I come across bones, I know either the Stickster is around, or another player is. Depending on my inventory, and how far the Stickster is, and how far my own goal is, I may choose to camp and kill the Stickster, camp and ambush a player returning to the area, or to flee to the goal, or to flee to known items to fulfill my original goal, or the distraction provided by the bones.

I'm not sure how you are doing personalities, but I imagine it's something like like general player types of Explorer, Achiever and Griever, or more likely, some mix of the three in each NPC.

An explorer would probably ignore or avoid bones all together, while an achiever would secure any immediate goals and move on. A griever would likely camp the spot hoping to take out a player and steal their items. Grievers would probably flee the Stickster along with explorers, though achievers might wait it out and go for the kill.

I just think bones should have some sway over NPC decision making, based on the NPC's personality profile. As a player, I take bones very seriously. It's a clear indication of recent activity in the area, and may indicate that my goal is either foolish, or perhaps not even possible, in the case of item scrounging or player killing.

If I have invisibility, I usually turn it on when I come across bones, especially if those bones are near my goal. I would not want my progress hindered by a sudden Stickster attack, or by stumbling upon an enemy or ambush.

Also, how's the PC/NPC coordination working? It would be most beneficial, especially in Feud mode, if player actions could have some deterministic outcome on NPC behavior.

For example, if we're just starting out, and I as a player take a very different route than my NPC teammates, they will follow their own goals as usual. However, if I deliberately follow an NPC, they should recognize me as an extension of themselves, and act accordingly, sticking by me, providing cover fire or support, leaving items for me to pick up if they already have one, and generally looking out for my welfare in addition to their own.

It could get pretty complex, but I think your goal system would allow for some fairly complex interaction without much work. Just having the NPCs be aware and empathetic to their teammates might be enough. It would suck if your team is handed their angle because your NPC team mates couldn't work together towards a shared goal.
I might make bones in immediate view something of a factor once I build in a means for NPCs to have a sense of danger. That's needed for any logic telling them to use Typo-flage. Likewise I've considered an approach like this for the Stickster, making him want to avoid any places where he had previously been killed. As an extension of that, a camper who thinks they've got the drop on him in some narrow corridor may be surprised that he doesn't always try to come in the same way.

Leaving item pickup to teammates is definitely a good idea, since if I'm stunned in my own base my NPC teammates will greedily pick up any stuff I drop. There probably needs to be a reasonable limit like deciding who's closer, etc. At the moment I don't have AIs set up to do much more about their teammates than avoid shooting them, but when I came up with the personality idea, an "escort" mode was definitely one I had in mind.

One thing I will be expanding on for sure is in-team communication. In partially setting up stuff for scavenger hunt mode I've already got teammates telling each other if they've found the item in the clue. It probably wouldn't be too hard to come up with a communication scheme where one AI decides to form a raiding party like in CTF, and another decides to join them.
You are a genious. I like the context and the actualy fact that someone cares of true AI in these simple Byond Games...
It's a lot better to see NPCs that actually do stuff instead of like 10 line coded NPCs that only know how to respond to movement near them or the simple Click and Talk kind of thing.
Two Thumbs Up in the virtual world!
wow this is some amazing stuff i just don't understand it i wish i could put this into my game, i tried copy/paste but that don't work and altering it its just too advance for me to do but really this is good
Black_Plaegue wrote:
wow this is some amazing stuff i just don't understand it i wish i could put this into my game, i tried copy/paste but that don't work and altering it its just too advance for me to do but really this is good

Copying and pasting is BAD!. Read the DM guide etc. then come back to this article to learn, not copy and paste.
Of course copying and pasting wouldn't work. Unless a piece of code is specifically designed to work in just about any project, copying and pasting seldom works at all. That code relies on procs and vars that don't exist unless you actually write them. It's a sample of specific code that works in a specific project, enough to give you an idea of how to create similar code yourself.
Hello, i was wondering if its possible how are the procs in DoAi are made?

If possible could you send them to me?


Also the variable
var/turf/loc gives an error.
Making_AI_smarter.dm:3:error:loc :duplicate definition (conflicts with built-in variable)