Author Topic: Advanced AI techniques in roguelikes (GOAP and HTN planners)  (Read 25730 times)

BirdofPrey

  • Newcomer
  • Posts: 31
  • Karma: +0/-0
    • View Profile
    • Email
Advanced AI techniques in roguelikes (GOAP and HTN planners)
« on: February 06, 2011, 08:57:44 PM »
I recently started to design the AI system for my big roguelike project. The standard roguelike AI uses finite state machines but those are not nearly expressive enough for my needs... I want the AI agents to make decently intelligent plans to carry out their goals and be able to re-plan in reaction to changing world states, and one of the main gimmicks of the game requires certain enemies to behave in a highly coordinated manner as if they share a singular consciousness.

The obvious choice is to spring for some kind of planning system, but after reading a bunch of dissertations on various planning systems it seems that each one on its own has some rather hampering weaknesses. My first choice, GOAP (Goal-oriented Action Planning), is pretty decent at planning and re-planning for individual units but has some issues, some of them being the inability to express compound actions (since all actions are considered 'primitive' actions that act directly on the game world) or to force certain actions to be performed in a certain order (which could lead to unwanted behavior like, for example, a creature advancing to melee range of their target BEFORE drawing their melee weapon, when the opposite order should always be enforced). It also seems to be less than ideal when it comes to coordinated group behavior.

The other method I've been looking into, Hierarchical Task Networks, solves all the aforementioned issues and is well-suited for group tactics, but seems to be fairly weak when it comes to reacting to a changing world state, and since it uses a top-down search instead of a regressive one it seems very difficult to make good cost estimates for a working A* search. I'm worried that using a simple depth-first search instead may make the resulting plans too deterministic.

I'm playing around with the idea of combining these two approaches: The HTN planner would be reserved for higher-level abstractions and group strategising, while the GOAP planner would handle the individual units. I think if I pulled it off correctly both systems could complement each other and could result in smart, coordinated monsters without being too difficult to extend its behaviors and goals. I'm having a hell of a time figuring out how to plan the actual implementation, however.

If there's anyone here with any kind of experience with these types of planners, do you have any advice for how I should go about things? In particular I'm wondering at what level of abstraction I should make the bridge between the HTN and GOAP system, and how exactly I can map HTN tasks to GOAP goals. I'm also kind of unclear on the replanning process. What is the best and least computationally expensive way to keep track of whether a given plan is still viable or not? Re-checking the preconditions of every action in the plan every time an agent's working memory changes slightly seems way too costly.

Any help/thoughts would be appreciated. Sorry if this post is kind of rambly/unclear, I still only have a rudimentary understanding of the way these planners work in actual implementation, and I imagine it shows.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #1 on: February 07, 2011, 01:57:08 PM »
Sounds like you plan too much. Just do it. Then check out what went wrong. If a generic AI theory doesn't fit in, don't use it.

willraman

  • Newcomer
  • Posts: 24
  • Karma: +0/-0
    • View Profile
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #2 on: February 08, 2011, 02:03:19 AM »
Sounds like you have something brewing already. In this case, why not expand your FSM into 2 HFSM loops? One controlled by a leader and one that is ran through for each NPC agent. The leader's HFSM decisions could be a sub branch of the NPC it leads.

The leaders HFSM might not necessarily have the same actions but are more goal oriented grouped actions. For example, KillTarget (follow target, switch weapon to range, attack), GuardArea (move to x/y, look for enemy, rest), etc. If you want a mindless NPC, put the leader's decsion at the top.

BirdofPrey

  • Newcomer
  • Posts: 31
  • Karma: +0/-0
    • View Profile
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #3 on: February 08, 2011, 08:40:13 PM »
Sounds like you plan too much. Just do it. Then check out what went wrong. If a generic AI theory doesn't fit in, don't use it.

I decided you're right, it's way too premature to try to plan out the squad aspects right now. Started a simple GOAP system that is currently correctly generating a basic 'move to player -> melee attack' plan, I'm just going to build up on it and see where it goes.

Still wondering about the replanning process though, if anyone has used these systems before.

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 805
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #4 on: February 08, 2011, 10:12:47 PM »
No matter how you do it, the devil is in the details. Planning in advance is good, but only as a means to be able to handle the things you couldn't plan for in advance. Similarly, exactly which solutions are best for your game, depends on exactly what the game is going to be like. (A game where armies clash in open fields demand a different AI engine than one where witches set traps and keep familiars.)

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

Serial Kicked

  • Newcomer
  • Posts: 9
  • Karma: +0/-0
    • View Profile
    • Grand Rogue Auto
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #5 on: February 16, 2011, 06:11:35 AM »
From what I gather from your post the player is against squads of enemies. This is a bit short to say the least. Knowing exactly what you want to achieve and the general combat mechanics would help a lot :)

More importantly the efficiency of an AI is usually depending on the map information / environment. Without knowing about it doesn't help providing any advice (and explaining those can be overwhelming to the reader anyway).

I have not dabbled into planning systems in any projects I have done before. From what I (think to) know they are more suited to strategical game than tactical ones, but I could be wrong. Still, here's a thing for you to consider:

Is the player going to see the difference between this (quite obviously) very long to write, test and debug AI system and a simpler model? As a programmer interested in AI, I perfectly understand that this is quite fun to experiment with, compare to other systems and so on. But if you're planning to publish it as a public/popular game, this may be not the most important factor to look for. Roguelikes (and most fps, tactical games) usually have somewhat modified FSM or Fuzzy Logic systems for combat mechanics, usually because they don't need more and because it's efficient enough.

I realize that this paragraph could be read as "don't do it". I apologize for that. On the contrary, I would be very interested to get updates from you on this game, or even the prototype and general logic you've put in it. If you're doing the project for yourself in priority, go wild with any idea you have, otherwise you may want to consider what users are expecting in priority.

This said, it probably won't help you much, but last time i had a try at squad combat I did something a bit different (that may be reused partially in my own project, GRA). There's probably an official name for it, but let's call it "dynamic terrain" for now. The concept is the following:

Each square of the map have a bunch of combat related variables that can be assigned to it like the amount of cover, the ability to shoot easily from this square, the level of sound made while walking on it, and so on.

Each time the player moves, all squares in a given radius around him recalculate those variables based on his position, and eventually the position of other NPC (if X is there then my cover will be better because he'll be shooting at the player). For example a square at a distance of 5 from the player with 2 squares occupied with crates or other furniture will have a high cover rating but a low offensive rating. Once calculated, you'll get obvious positions around the player for your NPC to hide (reload and heal), somewhat secure paths to flank the player, positions from where your NPC can get a ranged shot easily before going into cover again, and so on.

So each NPC depending on his stat / needs will choose the most appropriate square to go to without having to rely on anything else than a FSM/Fuzzy mechanism. The NPC look like they are coordinating an attack to the player's eyes when in reality the terrain is dictating where they should go to satisfy their current state.

But it really depends on the combat system here. If it's a regular roguelike with no possibility to run, burst shot, or well do at least 2 actions in a single turn, any advanced AI system is kinda pointless, IMHO.


Cheers,
SK.
« Last Edit: February 16, 2011, 06:15:26 AM by Serial Kicked »

BirdofPrey

  • Newcomer
  • Posts: 31
  • Karma: +0/-0
    • View Profile
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #6 on: February 16, 2011, 11:42:50 AM »
words

You're right, I didn't really give any details on the nature of the game. I haven't said too much about it outside of IRC yet, but I might as well spill the beans.

The basic premise is that you are an exterminator, and you must destroy a newly-created race of giant, telepathic hivemind insects before their numbers proliferate beyond control, dooming the human race. While the actual combat will be mostly roguelike-style (with lots of ranged combat ala doomrl), the various factions of the game will manage their resource gathering/usage and unit deployment in a more RTS-like fashion. Meaning if you fight your way through to various egg chambers and torch the eggs you'll be saving yourself some future pain and wasting hive resources.

A key mechanic of the game is that the hive insects are all mentally linked, behaving like 'fingers' of a singular consciousness. Therefore I need the hive to be able to coordinate pincer attacks and flanks, as well as hanging back and attemping to flush the player out of small corridors instead of piling up to be dealt with one at a time as is typical of roguelike AI. The hive will also learn from your actions; the first time you throw a grenade, they won't know what it is. The second time they will know to either run away, try to kick it back at you, or sacrifice a unit by throwing it on top of it to protect the rest.

It might seem that the game is overly stacked against the player, especially considering that when one of them sees you, they all know where you are, but there will be various ways the player can disrupt the hivemind. In order for the bugs' psychic link to penetrate thick layers of rock (floor to floor), there will need to be special 'transmitter' bugs in the area, acting as vertebrae in the spine of the hive. If all transmitter bugs are killed on a floor, the remaining insects will be disconnected from the hivemind and easier to pick off. This obviously makes them a prime target for players and an important asset for the hive to protect. Disconnected hive insects won't learn either, so killing off the transmitters and then throwing the grenades won't let the hive learn about them. There will also be shorter-term solutions, like EMP pulses that disrupt the psychic link for a temporary period of time.

It's not just the bugs that will be using this group behavior either. There will be waves of police/military coming down, who will be giving information and taking commands from commanders on the surface. The AI entity that oversees the laboratory area will also be an important character, and will control a sizable host of robots for offense/support/repairs as well as numerous cameras for information gathering and monitoring.

I think what I'm looking for requires more than FSM's to pull off, but if you can think of a way that I could make it work I would love to hear it. In general I prefer simpler solutions but it seems to me that what I want to do is somewhat beyond the realm of FSM's.

I like that concept of dynamic terrain, although it would complicate things if you added player allies to the mix.

edit - I guess I should mention a bit more about what I want combat to be like. As I mentioned it will probably seem somewhat like DoomRL, with an emphasis on ranged combat. Fighting humans will probably involve a fair amount of running and finding cover, while fighting the bugs will often come down to mowing them down as they attempt to overwhelm you with their numbers, though some will have ranged attacks too like acid sprays / poison barbs or whatever. Even the bugs simply swarm-rushing you will require some modicum of coordination though, since I would want them to form a group(s) together near the player before attacking all at once.
« Last Edit: February 16, 2011, 11:54:32 AM by BirdofPrey »

roguedjack

  • Rogueliker
  • ***
  • Posts: 70
  • Karma: +0/-0
    • View Profile
    • Rogue Survivor blog
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #7 on: February 16, 2011, 02:44:26 PM »
Is your game strictly turn-based or "real time" (eg: like dwarf fortress)? Just to be sure, as it can make a huge difference.

I know about GOAP and HTN but not used them.
This site has some stuff about them: http://aigamedev.com/
IIRC GOAP is more suited to individuals NPCs rather than squad AI?

I did some sort of planning for a Blood Bowl like Java project, not GOAP or HTN though.
Handling a team of players is kinda similar to squad behavior. The difference is a team act together in the same turn, while a squad is over severals turns each NPC acting on their own.
I implemented 3 AIs : a search based one, a planning+GA one and a rule-based one.
http://roguesurvivor.blogspot.com/2010/07/other-abandonned-projects-ii.html
All solutions kinda worked but had limitations and flaws.

With a planning solution, you could ditch altogether checking for re-planning conditions and just replan each turn.
For roguelikes I see more drawbacks in maintaining a plan over many turns and checking for replan conditions than simply generating new plans every turn. But that's just my opinion, SK seems to have implemented long term planning for his GRA roguelike.

For squad behavior, rather than top-down planning you could try the other way around :
(a) Top down : I want to encircle the player, how do my guys do that?
vs
(b) Bottom up: does this individual NPC action  contributes to the goal of encircling the player? if no, how can I improve that?

(b) is similar to my "beam ai" thing : you don't know who to write a good squad plan from scratch (very hard), but you know how to create a squad plan (easy), you know how to modify plans (easy) and you can recognize good from bad plans (moderatly hard).
Some sort of Genetic Algorithm on plans if you will.

Krice is right too. Just do a solution, and see what happens. Just make sure you can easily plug differents solutions with an abstract AI architecture (an AINPC interface or stuff like that) and have fun experimentating. I had lots of fun with my Bad Bowl retarded pet AIs.

Mmhh. i guess you're even more confused now sorry  :D

BirdofPrey

  • Newcomer
  • Posts: 31
  • Karma: +0/-0
    • View Profile
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #8 on: February 16, 2011, 08:24:03 PM »
With a planning solution, you could ditch altogether checking for re-planning conditions and just replan each turn.
For roguelikes I see more drawbacks in maintaining a plan over many turns and checking for replan conditions than simply generating new plans every turn. But that's just my opinion, SK seems to have implemented long term planning for his GRA roguelike.

This could work... it could be quite costly to replan for every active agent in the game, particularly since agents wont just 'freeze' if you go to another level, but I could compromise by replanning every turn for every creature within sight / general proximity to the player.

As far as the top-down vs. bottom-up,  I was going to do bottom-up (GOAP) for the individual NPC's, and top-down (HTN) for the groups to determine what the bottom-up goals should be. So the higher-level pincer attack task could translate to goals to form groups on both sides of the player and then swooping in, but the individuals' task of getting to their respective groups and the attack itself could be done in a bottom-up way. I'll certainly let you all know how it works out. Seems promising in my head.

edit - Oh yeah, and the game will be fully turn-based. Although, far far far in the future when this game is complete, I am contemplating a real-time RTS mode where you play as the hive instead.

roguedjack

  • Rogueliker
  • ***
  • Posts: 70
  • Karma: +0/-0
    • View Profile
    • Rogue Survivor blog
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #9 on: February 17, 2011, 07:27:05 PM »
You probably already know that but the FEAR SDK has a GOAP implementation for the AI will full source (C++)
http://web.media.mit.edu/~jorkin/goap.html
There was a source-only version on the site I linked in the previous post, but you need to register.

I was thinking about what you said about GOAP being limited to primitive actions, because acting directly on the game world.
Wouldn't it be possible to use compound/hi-level actions if you use GOAP on a more abstract search space.
For instance a GOAP "action" would be a selecting a specific tactic/behavior on a NPC, rather than concrete game actions. The said tactic/behavior implemented by FSM/whatever with actual game actions.
The GOAP search space would then be tactical features such as "X is near Y", "X is behind Y" etc... rather than concrete game states.

BirdofPrey

  • Newcomer
  • Posts: 31
  • Karma: +0/-0
    • View Profile
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #10 on: February 20, 2011, 07:24:49 AM »
You probably already know that but the FEAR SDK has a GOAP implementation for the AI will full source (C++)
http://web.media.mit.edu/~jorkin/goap.html
There was a source-only version on the site I linked in the previous post, but you need to register.

I was thinking about what you said about GOAP being limited to primitive actions, because acting directly on the game world.
Wouldn't it be possible to use compound/hi-level actions if you use GOAP on a more abstract search space.
For instance a GOAP "action" would be a selecting a specific tactic/behavior on a NPC, rather than concrete game actions. The said tactic/behavior implemented by FSM/whatever with actual game actions.
The GOAP search space would then be tactical features such as "X is near Y", "X is behind Y" etc... rather than concrete game states.

I like this... behavior implementation will be a good entry point to my scripting system. If a certain creature can control teleport at will, I can change its GOTO_DESTINATION behavior to change both how the behavior is turned into an action and I can also define it to have a much lower search cost to that behavior to simulate moving around being so easy.

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #11 on: February 21, 2011, 07:46:59 AM »
This sounds interesting.  I hope you eventually do it and produce something neat.

But first off, I will echo the sentiments of everyone here that says, the interface to your AI is more important than the AI.  Do the interface so you can plug in different AI as "modules."  But then do a simple effective AI - upgrade it at your leisure.

It sounds like what you want, what you're planning, involves having a monster intelligence named "HIVE" or something which doesn't have a specific body.  However, it has the knowledge/sight  available to all the bodies that are part of it, a certain level of memory, and the ability to designate groups and issue orders to those groups. Meanwhile, the individual buglets have sufficient intelligence to follow general orders and will keep track of what group they're assigned to and try to follow the orders for that group.  So when "HIVE" wants do do a pincer attack, it designates two task forces and directs them to attack the target from two different directions at a designated time. Perhaps it designates two additional smaller task forces whose purpose is to follow up the main forces but rather than having attack as first priority, they have blocking doors and passages to prevent escape. The buglets themselves each see what task force they are assigned to, then see the orders for that task force, and carry them out.  So you can have HIVE re-plan and update orders once every (say) ten turns, and the buglets learning what kind of local intelligence they must use turn-to-turn by reading their orders from HIVE.

Instead of going to such lengths, I think you could effectively simulate group tactics by allowing the buglets certain types of powers when they are "connected," such as enhanced mobility through squares otherwise blocked by each other, or when two or more engage the @, making coordinated attacks which are harder to dodge, etc.  IOW, instead of making them truly smarter, it may be a lot easier to just simulate some of the results of smartness. 

Bear

BirdofPrey

  • Newcomer
  • Posts: 31
  • Karma: +0/-0
    • View Profile
    • Email
Re: Advanced AI techniques in roguelikes (GOAP and HTN planners)
« Reply #12 on: February 21, 2011, 08:37:23 AM »
You've basically completely nailed what I'm planning. What you suggested will be a perfect stopgap for between my implementation of individual AI and group AI. In the end I'll want to have a general framework for hierarchy of command because certain other constructs will use it as well, most notably the AI personality that runs the lab branch.