Adapting this planning technique to a graphical MMORPG

[Jotaf]

Hi, first of all, congrats on these series, they haven't been updated for a while but they discuss some really interesting stuff, and for anyone developing a game (not just MUDs!).

The part that caught my attention immediately was the planning/quests system you describe. It's so simple that I don't know why I've never seen it before, yet it's really powerful when it comes to making any game that relies on characters to feel more "alive".

Anyways... I started making plans in my head for how I'd implement it in my MMORPG. Actually I think it's much better if new characters with simple plans ("gotta work and sell my wares at the market", "gotta find someone to rescue my daughter") are created when the server is not too stressed, and removed smoothly when their main goal is achieved =)

There are a couple of issues when dealing with a graphic environment, specially with the positions of objects and stuff like that. I also took the opportunity to satisfy only the conditions that are really needed so the code is cleaner (if it already moved to y, it can assume that the npc is at y so maybe the next action won't tell the npc to go to y again). So, I made up a simple goal for an npc (milk a cow and sell the milk at a market stall, it's not too reallistic but it's ok for my little simulation =) it has to deal with using a bucket to transport the milk, locating the market, stuff like that =)

I know it looks a bit confusing at first, but if you follow these simple rules and keep in mind that all the "something is something" can be implemented using "if (something == something)..." directly, you'll end up with the same result:
1) Loop trough all the conditions of the goal.
2) For each one, see if it's already satisfied - I used simply (yes) and (no) in front of the conditions.
3) If it's a (yes), do nothing (the condition is satisfied).
4) If it's a (no), you must find an action with an effect that is the same as this condition (my game has a pre-calculated list of pointers to actions that contain each condition, so it's easy to just choose one at random).
5) Basically you'll have to run another loop like this for each condition of the selected action! When all conditions are satisfied, add this action to the plan.

It's probably almost the same as your list, but I didn't bother looking it up sorry ;)



goal: to have a bucket of milk at the npc's market stall (first,
the npc must carry a bucket near the cow, milk it, and then carry
the bucket of milk to the market stall)
preconditions
-type of x is bucket of milk
-type of y is market stall
-position of x is y



variables of the npc: only x and y are necessary for plan execution
-x (pointer to an object)
-position of x (pointer to an object)
-type of x (object type)
-carrying x (boolean)

-y (pointer to an object)
-position of y (pointer to an object)
-type of y (object type)
-carrying y (boolean)

-me (pointer to an object - self)
-my position (pointer to an object)



milk cow y with bucket x: replaces object x with a bucket of milk
preconditions
-type of x is bucket
-type of y is cow
-position of x is y
-my position is y
effects
-type of x is bucket of milk

find object to x, bucket/cow/market stall: finds an object of that
type and sets x to it
preconditions
-none
effects
-type of x is bucket/cow/market stall

find object to y, bucket/cow/market stall: finds an object of that
type and sets y to it
preconditions
-none
effects
-type of y is bucket/cow/market stall

drop x at y: drops object x being carried near y
preconditions
-carrying x is true
-my position is y
effects
-carrying x is false
-position of x is y

pick up x: picks up object x
preconditions
-type of x is carriable
-my position is x
effects
-carrying x is true
-position of x is nothing

go to x: moves so the npc is near x
preconditions
-none
effects
-my position is x

go to y: moves so the npc is near y
preconditions
-none
effects
-my position is y



process:
type of x is bucket of milk? (no) -> milk cow y with bucket x {
type of x is bucket? (no) -> find object to x, bucket {
(no preconditions)
} [1]
type of y is cow? (no) -> find object to y, cow {
(no preconditions)
} [2]
position of x is y? (no) -> drop x at y {
carrying x is true? (no) -> pick up x {
type of x is carriable? (yes)
my position is x? (no) -> go to x {
(no preconditions)
} [3]
} [4]
my position is y? (no) -> go to y {
(no preconditions)
} [5]
} [6]
my position is y? (yes)
} [7]
type of y is market stall? (no) -> find object to y, market stall {
(no preconditions)
} [8]
position of x is y? (no) -> drop x at y {
carrying x is true? (no) -> pick up x {
type of x is carriable? (yes)
my position is x? (no) -> go to x {
(no preconditions)
} [9]
} [10]
my position is y? (no) -> go to y {
(no preconditions)
} [11]
} [12]



result:
1. find object to x, bucket
2. find object to y, cow
3. go to x
4. pick up x
5. go to y
6. drop x at y
7. milk cow y with bucket x
8. find object to y, market stall
9. go to x
10. pick up x
11. go to y
12. drop x at y



Yeah it's a bit too big for something this simple. But it's a bit more low-level and that's the whole point of it - this one you can translate to real code without thinking too much :p
Notice how the NPC would try to find a way to make the object carriable if it wasn't. And how smooth the resulting plan is - 2 different actions require that it moves to y, but it's already there when it reaches the second action so it doesn't try to move there again. It *would* move if it was somewhere else.

Looking forward to hear your opinion (and to read another one of those excellent articles too =)

[Jotaf]

Hmm I thought about it again and I think that, since I'm already using a "A == B" system for the preconditions and effects, I could just use a "carried item" variable and then set it to whatever object type is being carried... I forgot to mention that most of the player's attributes/properties can be used like this... like, in that "type of x is carriable", this should just check if a property of the object type "type of x" is "carriable". Hmm... right now I can't really see any other issues that might arise when trying to implement your system, can you? =)

[Richard]

You seem to have got the hang of it, yes.

The approach you're taking is basically a depth-first search. The main problems with this are that you might find a very inefficient solution (something that has 20 steps rather than 2) and that you might get into an indefinite loop (walk to A, walk to B, walk to A, walk to B etc.). There's also the general point that if you have many, many operators available to your planner it will slow things down more than somewhat.

If you're at all interested in this stuff, the thing to do is to go to the AI literature directly. You probably don't need the advanced stuff, as that doesn't translate well into the explicit plan structure you need for the "give me a quest" player action. However, there's still a lot of good material in the not-so-advanced stuff.

Take a look at some AI textbooks in your local university library/bookshop; they usually cover basic planning techniques as it's fairly fundamental to AI.

Richard

[Richard]

[Can someone delete this please? I hit the "Submit" button for the previous message twice. Thanks - Richard]

[Jotaf]

Thanks for your reply. There seems to be a LOT of different AI planning methods on the net, can you please point me in the right direction? Like, the name of another search method (instead of depth-first). Oh and I don't think it's possible to make the operators even simplier, I'm just comparing values...

[Richard]

Originally posted by Jotaf
Thanks for your reply. There seems to be a LOT of different AI planning methods on the net, can you please point me in the right direction? Like, the name of another search method (instead of depth-first). Oh and I don't think it's possible to make the operators even simplier, I'm just comparing values...

Well the main alternative to depth-first is breadth-first. With depth-first, you explore a branch to the end before you backtrack and try the next branch; with breadth-first, you expand each node in the order it was discovered (which means you need to keep a "frontier set" of nodes to be expanded). Breadth-first will always get you a shortest path, but it can be hideously inefficient when there are many easy-to-find solutions in a very bushy (ie. high branching) tree.

A good compromise is a directed search, whereby some weighting can be derived that can be applied to each node in the frontier set to determine which is most likely to lead to a solution; the A* algorithm (usually applied for route-finding searches) is an example of this.

Planning is not all about search, though. There's a combinatorial explosion when you have more than a few operators and have goal states that differ greatly from the starting state. There are other issues, too, such as the possibility that the world can change while you're planning, and that you may be interacting with other planners who are planning based on how they think you're going to act. Various techniques have been developed to address each of these.

So in the planning literature you'll see references to means-end analysis, meta-planning non-linear planning, hierarchical planning, action and goal regression, dependency-directed backtracking, truth maintenance, resource planning, opportunistic search, typed preconditions and (in an obscure 1988 PhD - ahem!) cross-level planning.

There are others, but I'm not up-to-date on the latest ones.

If you were looking for something about it on the net, I'd start with a search for "introduction to planning". Since you'll get a ton of stuff about urban planning in that, add either (or both) of "problem solving" and "search".

Richard

[Jotaf]

I'm just going to ignore most of those issues, mostly because of the nature of my game, but also because, even though the subject is cool and got me interested from the first time I read about it, I have so much to do that I don't want to waste a lot of time with this =)

Since the NPCs are created with a simple goal and then destroied, it's not critical that they find an optimal solution every time. For example, when you arrive at a town, if the server is not too busy, it will start creating a plan for an NPC with a specific goal; so if it's taking too long or it's impossible, it can just discard the NPC and move on to another one. When the conditions for an on-going action are not met, the NPC will simply make a request for another plan... wouldn't this solve most problems with interference from other characters? And if no one is looking and the NPC is really stuck, I just remove it! (Yeah I know, I cheat a LOT, but I don't need a perfect plan, it's a game, I just need to make the NPCs have some goals and look like they're on their daily lives' routine)

When an NPC needs to get a specific sword, it is created for it. If 2 NPCs in my above example have to fight for a bucket that they selected at the same time, the first one will take it, and the second one will re-plan so it will just look for another bucket.

Or maybe I got the whole thing wrong =p what do you think?


BTW when I searched for "non-linear planning" I got lots of links about urban planning and stuff, so thanks for the tip =)