7 ms·

I've been using Orkin's Goal-Oriented-Action-Planning (GOAP) in my own game development. Let me tell you an amusing story of how an AI agent outsmarted me, the

by stolk 10y ago

I've been using Orkin's Goal-Oriented-Action-Planning (GOAP) in my own game development. Let me tell you an amusing story of how an AI agent outsmarted me, the developer. So I had set up a test scenario, with an agent that could travel, buy stuff at shops, use axes, cut trees, and so forth. When I ran this test, I had set a goal of procuring timber. What I expected the agent to do: 1. Go to shop 2. Buy axe 3. Go to forest 4. Cut tree 5. Drop axe 6. Pickup timber. So I ran my GOAP test, and saw what the agent came up with: 1. Go to forest. .. When I saw that step 1, I was disappointed, because the agent clearly should not be going to the forest when he has no axe yet. But then, as a proud parent of my AI, I saw what the agent had actually planned: 1. Go to forest 2. Pick up firewood 3. Go to store 4. Sell firewood 5. Buy axe 6. Go to forest 7. Cut tree 8. Drop axe 9. Pickup timber Hooray! I simply forget to give my agent money. But GOAP made him smart enough on how to get some money on his own. I had of course equipped the agent with 'sell' action, and I had placed firewood in the forest, which I promptly had forgotten about when writing a test scenario. I was so proud of that smart little agent! Cool stuff, that GOAP!

JoshTriplett 10y ago
Nice! I'm curious about "8. Drop axe". Did your system have the constraint that the agent could only hold one thing at a time? Or was the goal to carry the maximum amount of timber, in which case it's completely sensible to leave the axe in the woods and pick it up again when you return (assuming no other constraints, like competing agents or weather).
- stolk 10y ago
  Indeed. So in GOAP, actions have pre-conditions and post-conditions (effects.) pickup-item was defined as: PRECONDITIONS: HANDS_EMPTY==1, NEAR_ITEM==1, HAVE_ITEM==0 POSTCONDITIONS: HAVE_ITEM:=1 HANDS_EMPTY:=0 Which makes it so that agents carry one thing at a time, indeed.
Rapzid 10y ago
I can only hope you are creating an Ultima 7.5. True world building seems to have been left in the 90's.
seanwilson 10y ago
I love examples like these but where lack of real world or common sense knowledge gives funny results. I tried writing a text adventure game generator once that would combine puzzle templates you gave it like "object X you need is in a tree and you need a climbable thing Y to get it" and "object X is in a vending machine and you need a coin to get it" to create basic chains of puzzles. Without more constraints it would do silly things like create a vending machine containing ladders, vending machines in trees, vending machines containing other vending machines and trees, and vending machines that gave you a coin for a coin.
- lloeki 10y ago
  Ok there must be something here as I just laughed at this picturing a game where there's that vending machine containing a ladder that's stuck up a tree, and to get at it you'd have to get a tree from that other vending machine, which turns out to be stowed inside another vending machine, and for that you'd have to get a coin from a dozen or so vending machines that would mostly give you some that don't match the coin you need. The kind of game like Bureaucracy that puts the player into some borderline absurdist rage that soon changes into laughter.
  - IanCal 10y ago
    I think there's a wonderful game in this. You are trying to escape from a virtual reality world created by a computer that doesn't understand how our world works. Make it procedurally generated and allow people to share the best ones they find.
    - seanwilson 10y ago
      > I think there's a wonderful game in this. You are trying to escape from a virtual reality world created by a computer that doesn't understand how our world works. I think so too but couldn't work out how. It needs something extra on top to give you a reason to work through the puzzles I think. So games like Sokoban where you could generate random puzzles don't need much of a reason behind them but all good text adventures are tied together with a plot of some sorts unless you can think of any examples. I binge read text adventure walkthroughs for puzzle ideas and the same generic puzzles felt surprisingly common (e.g. grate + crowbar, key + door, vampire + garlic, coin + vending machine, tree + ladder, spade + grave) but a game composed only of these would probably be dull. Actually "virtual reality world created by a computer that doesn't understand how our world works" is the plot of the VR game Job Simulator I think.
salakotolu 10y ago
When can I play this?
- stolk 10y ago
  Playable right now. It's a free download from Steam. Look up `Children of Orc.' The player can give assignments to the other Orcs, and the action plans for those assignments are displayed in-game. The Orcs are smart enough to find cheap plans. When tasked with procuring stone, e.g. they will see what the quickest way is. Sometimes scavenging for discarded stone may be cheaper, other times, with pickaxe in hand near a quarry, quarrying is the way to go of course. They adapt. But whatever plan they come up with, it is communicated to the player in an info-window.
  - BlytheSchuma 10y ago
    This guy gets Marketing.
  - dr_zoidberg 10y ago
    I see a lot of people on Steam complaining that it won't run without AVX support... what exactly did you use AVX for?
    - stolk 10y ago
      AVX is used for exactly this: GOAP. The search space for the plans is ridiculously large, so testing pre-conditions needs to be insanely fast. With AVX, you get to test up to 256 boolean preconditions in one go! To give you an idea about search space: the Orcs have a repertoire of 115 possible actions. Stringing together a plan of let's say 12 actions (some plans are longer), gives 115 12 possible plans. That is a scary big number: 5350250105473711181640625 A* helps guiding the search through this space, but can only do so much. So every A* operation needs to be as fast as possible.
  - Y_Y 10y ago
    I gave the game a try and it's pretty fun seeing the details of how the figure out what to do. If the orc models were less ugly and the controls were better and it didn't crash so much I'd even pay money for it. Thanks.
septimus111 10y ago
I'd like to try implementing a toy program that incorporates some planning. Any ideas of games that would be suitable for this?
- and0 10y ago
  Roguelike would probably be the simplest, since you don't need to worry about creating visual assets, and time / space is mathematically simpler (turns & tiles).
edejong 10y ago
Sounds very familiar. I once made a planning AI for the xlockmore / xscreensaver Pacman. It was never included since it would require too much CPU on low-end machines. Nevertheless, it took me quite some time to debug a strange behavior while writing it. The planning system would plan around 50 steps ahead, minimizing the risk of being eaten by a ghost while maximizing the number of dots eaten. Strangely enough, it would continually decide to go towards the ghosts, instead of evading them. Every time I saw this happening, I decided to stop the game and debug my code. Looking through it for the umphth time, I became weary-eyed and let the simulation run for a bit longer. Awe-struck, I saw what Pacman was planning all along: have the ghosts closely follow behind him. This would minimize the probability of being fenced in by the four ghosts. And this reminds me, I wrote that code 12 years ago, and I still want to incorporate it (with a switch) into the xscreensaver code, but never came to it...
- talmand 10y ago
  That's why the original ghosts had some somewhat random behavior centered around a corner of the maze for each ghost. If I remember right, at random times a ghost will head to its own corner in its own specific way. There's an article or two out there about it, it's an interesting read. Plus, the ghosts are faster than you when you are eating dots.
LordKano 10y ago
I only have a passing interest in game development but GOAP sounds amazing. I just started reading about it. Thank you for this.
dclowd9901 10y ago
Is there any room in GOAP for weighting certain actions over others? Like, could I imbue a character with personality traits that would direct them to do one thing over another?
- Jtsummers 10y ago
  Per the GOAP paper [0], yes. You can weight different actions. The example used is: Order pizza (to satisfy hunger) cost of 2, make a pie (to satisfy hunger) cost of 8. If the actor only satisfies the preconditions for one, that's what they do. But if they satisfy the preconditions for both, they take the cheaper one. [0] http://alumni.media.mit.edu/~jorkin/goap.html http://alumni.media.mit.edu/~jorkin/goap.html
- stolk 10y ago
  Yes, all actions have a cost associated with it. You can use it in different ways: like you describe: have some agents prefer certain actions, different from the preferences of other agents. The way I use it is to adapt to the environment. For instance, I make walking over to let's say an apple, less costly if the closest apple is near.

by stolk 10y ago

JoshTriplett 10y ago

Nice! I'm curious about "8. Drop axe". Did your system have the constraint that the agent could only hold one thing at a time? Or was the goal to carry the maximum amount of timber, in which case it's completely sensible to leave the axe in the woods and pick it up again when you return (assuming no other constraints, like competing agents or weather).

stolk 10y ago
Indeed. So in GOAP, actions have pre-conditions and post-conditions (effects.) pickup-item was defined as: PRECONDITIONS: HANDS_EMPTY==1, NEAR_ITEM==1, HAVE_ITEM==0 POSTCONDITIONS: HAVE_ITEM:=1 HANDS_EMPTY:=0 Which makes it so that agents carry one thing at a time, indeed.

Rapzid 10y ago

I can only hope you are creating an Ultima 7.5. True world building seems to have been left in the 90's.

seanwilson 10y ago

I love examples like these but where lack of real world or common sense knowledge gives funny results. I tried writing a text adventure game generator once that would combine puzzle templates you gave it like "object X you need is in a tree and you need a climbable thing Y to get it" and "object X is in a vending machine and you need a coin to get it" to create basic chains of puzzles. Without more constraints it would do silly things like create a vending machine containing ladders, vending machines in trees, vending machines containing other vending machines and trees, and vending machines that gave you a coin for a coin.

lloeki 10y ago
Ok there must be something here as I just laughed at this picturing a game where there's that vending machine containing a ladder that's stuck up a tree, and to get at it you'd have to get a tree from that other vending machine, which turns out to be stowed inside another vending machine, and for that you'd have to get a coin from a dozen or so vending machines that would mostly give you some that don't match the coin you need. The kind of game like Bureaucracy that puts the player into some borderline absurdist rage that soon changes into laughter.
- IanCal 10y ago
  I think there's a wonderful game in this. You are trying to escape from a virtual reality world created by a computer that doesn't understand how our world works. Make it procedurally generated and allow people to share the best ones they find.
  - seanwilson 10y ago
    > I think there's a wonderful game in this. You are trying to escape from a virtual reality world created by a computer that doesn't understand how our world works. I think so too but couldn't work out how. It needs something extra on top to give you a reason to work through the puzzles I think. So games like Sokoban where you could generate random puzzles don't need much of a reason behind them but all good text adventures are tied together with a plot of some sorts unless you can think of any examples. I binge read text adventure walkthroughs for puzzle ideas and the same generic puzzles felt surprisingly common (e.g. grate + crowbar, key + door, vampire + garlic, coin + vending machine, tree + ladder, spade + grave) but a game composed only of these would probably be dull. Actually "virtual reality world created by a computer that doesn't understand how our world works" is the plot of the VR game Job Simulator I think.

salakotolu 10y ago

When can I play this?

stolk 10y ago
Playable right now. It's a free download from Steam. Look up `Children of Orc.' The player can give assignments to the other Orcs, and the action plans for those assignments are displayed in-game. The Orcs are smart enough to find cheap plans. When tasked with procuring stone, e.g. they will see what the quickest way is. Sometimes scavenging for discarded stone may be cheaper, other times, with pickaxe in hand near a quarry, quarrying is the way to go of course. They adapt. But whatever plan they come up with, it is communicated to the player in an info-window.
- BlytheSchuma 10y ago
  This guy gets Marketing.
- dr_zoidberg 10y ago
  I see a lot of people on Steam complaining that it won't run without AVX support... what exactly did you use AVX for?
  - stolk 10y ago
    AVX is used for exactly this: GOAP. The search space for the plans is ridiculously large, so testing pre-conditions needs to be insanely fast. With AVX, you get to test up to 256 boolean preconditions in one go! To give you an idea about search space: the Orcs have a repertoire of 115 possible actions. Stringing together a plan of let's say 12 actions (some plans are longer), gives 115 12 possible plans. That is a scary big number: 5350250105473711181640625 A* helps guiding the search through this space, but can only do so much. So every A* operation needs to be as fast as possible.
- Y_Y 10y ago
  I gave the game a try and it's pretty fun seeing the details of how the figure out what to do. If the orc models were less ugly and the controls were better and it didn't crash so much I'd even pay money for it. Thanks.

septimus111 10y ago

I'd like to try implementing a toy program that incorporates some planning. Any ideas of games that would be suitable for this?

and0 10y ago
Roguelike would probably be the simplest, since you don't need to worry about creating visual assets, and time / space is mathematically simpler (turns & tiles).

edejong 10y ago

Sounds very familiar. I once made a planning AI for the xlockmore / xscreensaver Pacman. It was never included since it would require too much CPU on low-end machines. Nevertheless, it took me quite some time to debug a strange behavior while writing it. The planning system would plan around 50 steps ahead, minimizing the risk of being eaten by a ghost while maximizing the number of dots eaten. Strangely enough, it would continually decide to go towards the ghosts, instead of evading them. Every time I saw this happening, I decided to stop the game and debug my code. Looking through it for the umphth time, I became weary-eyed and let the simulation run for a bit longer. Awe-struck, I saw what Pacman was planning all along: have the ghosts closely follow behind him. This would minimize the probability of being fenced in by the four ghosts. And this reminds me, I wrote that code 12 years ago, and I still want to incorporate it (with a switch) into the xscreensaver code, but never came to it...

talmand 10y ago
That's why the original ghosts had some somewhat random behavior centered around a corner of the maze for each ghost. If I remember right, at random times a ghost will head to its own corner in its own specific way. There's an article or two out there about it, it's an interesting read. Plus, the ghosts are faster than you when you are eating dots.

LordKano 10y ago

I only have a passing interest in game development but GOAP sounds amazing. I just started reading about it. Thank you for this.

dclowd9901 10y ago

Is there any room in GOAP for weighting certain actions over others? Like, could I imbue a character with personality traits that would direct them to do one thing over another?

Jtsummers 10y ago
Per the GOAP paper [0], yes. You can weight different actions. The example used is: Order pizza (to satisfy hunger) cost of 2, make a pie (to satisfy hunger) cost of 8. If the actor only satisfies the preconditions for one, that's what they do. But if they satisfy the preconditions for both, they take the cheaper one. [0] http://alumni.media.mit.edu/~jorkin/goap.html http://alumni.media.mit.edu/~jorkin/goap.html
stolk 10y ago
Yes, all actions have a cost associated with it. You can use it in different ways: like you describe: have some agents prefer certain actions, different from the preferences of other agents. The way I use it is to adapt to the environment. For instance, I make walking over to let's say an apple, less costly if the closest apple is near.