Hacker News Reader

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...

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.

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.

I was just reading about a bunch of weird bugs found in dwarf fortress. For instance, someone found all the cats were throwing up all over the place from alcohol poisoning. They looked into it and found the dwarves were spilling alcohol on the floor of the tavern. The cats didn't drink it though. No, they walked through it and got it on their fur. Then when the cats went to clean themselves, they ingested the alcohol. The game then calculated their blood alcohol content to be very high and gave them alcohol poisoning. Because it counted it as one standard of unit of alcohol, and the cats have much smaller body mass than dwarves.

All sorts of amazing, um, features, have been found in that game.

Here's a neat dwarf trick:

  1. Obtain a vessel capable of holding liquids.
  2. Drink from the vessel until it has one unit left.
  3. Empty the vessel onto the ground.
  4. Refill the vessel to its maximum capacity from the puddle you just made.
  5. Drink from the puddle.

The problem was that puddles and spatter and liquid coatings did not have a volume.

So you can also quench your thirst by swimming in a river, then drinking the coating of water stuck to your own ear.

So the cat thing was exactly the same problem. An infinite number of cats could walk through one puddle of spilled alcohol, and then ingest enough alcohol to get poisoned by licking each body part. Lick first toe of right foot? That's a shot. Lick second toe of right foot? Another shot. Lick third toe of right foot? We're having a party now!

On the one hand, it seems like there should have been some additional effort there. But on the other, the game actually simulates that when you dunk something in water, it gets wet, and then stays wet until the water evaporates. I don't know of any other game that not only does that, but also handles dusts and powders, and things falling from the sky due to weather, and even getting diseases by inhaling vaporized droplets of a contaminated liquid.

You would think that with all that incredible detail, the pathfinding AI would not kill the framerate just from two dozen pastured sheep all trying to find their next clump of grass to eat.

It's crazy that the game simulates spilled alcohol, and that you can get it on you by walking through it, and that cats clean themselves by licking, and that they ingest whatever they lick, and that it computes blood alcohol content and simulates the effects of alcohol poisoning... DF is insane.

The pathfinding is pretty inefficient because it's entirely invented by the guy who wrote it. Who doesn't know anything about pathfinding algorithms. Also it's entirely single threaded.

> You would think that with all that incredible detail, the pathfinding AI would not kill the framerate just from two dozen pastured sheep all trying to find their next clump of grass to eat.

Dwarf Fortress is kind of the ur-example of passionately solving the wrong problem.

It's a fantastic game, and it's heartbreaking to me how much more fantastic it could be if the author adjusted his priorities a bit.

I don't see the bug there. Maybe you mean that the cat simulation is not accurate enough: cat's wouldn't walk through puddles if they could avoid it.

I think the bug was that it counted as "one mug of alcohol" on the floor, and the entire thing stuck to their fur, which wouldn't happen in real life.

One lick of alcohol soaked fur was the same amount of alcohol as a full tankard of beer. There was only one "unit" of alcohol. Hence dead cats.

Unintended behavior would be more accurate.

Maybe you don't realize just how much dwarves drink :v

Sounds like the kind of thing I'd read on The Strange Log [0]

[0] https://twitter.com/thestrangelog

That is hilarious. I can't believe I haven't heard of this before.

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.

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.

> 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.

> 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.

I've been thinking on these lines recently too, and maybe the game could be to allow others to experience the fun you're having in building these rules and watching the outcomes? Letting them author the rules, and watch the outcomes. Or letting them manage and upgrade the bots, sorta like an overlord who doesn't actually chop wood etc.

This is kind of a nebulous idea (and definitely not new), but spawns from the fun I've been having the past few weeks in writing a bunch of simple rules for cities to attack, ally, trade with each other. Watching kingdoms evolve, alliances form and break, funny situations like a rock shortage eventually triggering a massive war among all kingdoms, was fun. It might not be as fun for a passive observer, but as the author of the rules, the feedback loop of making changes and watching the emergent outcomes was pretty neat (kinda like programming, heh). But it is a scary path to go down, if the intention is to market it as a game, because it doesn't look or sound like any "real" game.

On a different note, Dwarf Fortress is ripe with such emergent outcomes. On another different note, Robocode is quite fun where you author bots and rules and watch how the bots fare against each other.

> funny situations like a rock shortage eventually triggering a massive war among all kingdoms, was fun.

I love emergent AI game situations like that! Even that feeling of seeing enemies in Doom fighting each other hasn't been surpassed by that much in modern games I feel. Spelunky had a few moments like that though.

> Watching kingdoms evolve, alliances form and break, funny situations like a rock shortage eventually triggering a massive war among all kingdoms, was fun. It might not be as fun for a passive observer, but as the author of the rules, the feedback loop of making changes and watching the emergent outcomes was pretty neat (kinda like programming, heh).

Sounds fun! Any more situations like that?

I tried another prototype where it was a text adventure in a single room containing NPCs where certain NPCs liked, loved or hated each other (which limited their actions), there was objects characters could obtain (like a gun to threaten people to do actions for you or money to bribe people), characters had attributes (like intimidating, gullible, jealous) and as the player you could ask characters to do things for you and they could do the same. It had the same issue of nonsensical things happening which were unintentionally funny. Huge state space explosion though.

So I gave a NPC the goal to make a sandwich from bread and cheese which two of his friends were holding. Instead of just asking his friends for the ingredients, he obtains a gun, threatens a NPC he hates to steal the ingredients from his friends then threatens him to make the sandwich and hand it over. A valid but inefficient solution in the search tree basically. You'd probably want some common sense logic that most characters want to achieve their goal in a way that doesn't impact their social standing. Same thing as before though, instead of making the NPCs normal humans you could come up with a story about why they don't act normal to sidestep the common sense issue.

You can also do procedural plot generation. It's pretty doable as long as you don't set your literary bar too high :)

You kind of need to get a feel or knack for navigating the so-called "edge of chaos" between order -- too many restrictions/rules = predictable patterns = boring -- and disorder -- pick everything random and it becomes the conceptual equivalent of the "rainbow puke" mush of random RGB pixels that is always infinitely different but always looks like the exact same flavour of static. Similarly if you pick random notes from a few octaves to make a tune -- in theory you should come across all the famous earworms like Axel F, Smoke on the water, Final Countdown, etc etc, in practice you get a different slice of the same warbly nothing 99.9999% of the time.

That is, in some sense, where the Infinite Monkey theorem seemingly breaks down, while at the same time it is also exactly where it derives its poignancy. It's a very powerful pulling force between two opposites.

Either way, read all about procedural anything generation for games on this great website: http://www.gamesbyangelina.org/

One very interesting idea, that has become quite feasible with modern computing power, is to use constraint solvers. Sure they are NP-complete but in practice they do a pretty good job. Imagine if you have a loose framework for puzzles, or challenges (maybe rooms with monsters and items) and it generates a beautiful wide variety of novel game play. Except, just like in real life, you can't always win. But you want it to, just like in a "hero's story", be just winnable, all the time. And you want your player to be able to trust that it is (it doesn't sound like a lot of fun bashing your head against a random-generated puzzle that turns out to be logically impossible). Constraint solvers can actually do this! There's a few articles on the Games By Angelina website.

I think that a constraint solver could very easily generate random Sokoban-levels that are guaranteed to be solvable. Now you need some (relative) measure of "difficulty" to sort them in order to create that feeling of progression and challenge. Which I also think is doable (amount of backtracking, "mental stack" required, etc).

Make it a VR game and the only way to truly win... is to take off the headset.

MGS2 already did that. A hostile AI orders you to kill someone, and knows you'll do it because the only way to not do it is to turn the console off.

There was also the Sega Genesis X-Men game. The whole game is supposed to take place in a hacked Danger Room, at one point you need to reset the computer and you do it by resetting the actual Genesis itself. The cartridge had to have a special battery to do this and it blew my mind as a child.

Don't forget Spec Ops: The Line, which plays on the idea of not having a choice in committing war crimes and justifying terrible amounts of violence, because you won't close the game.

Reinvented Stanley's Parable essentially... Except procedural.

you mean No Man's Sky? turns out it kinda sucks

Of all things procedural they refused to do stories and socities

> 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...

Haha, exactly, it was a really funny prototype. It took you by surprise by how much common sense knowledge you kept having to feed into it to stop it doing bizarre things e.g. knowledge like vending machines only contain small things, vending machines don't dispense the thing you put into them, large things aren't found in trees, ladders + trees + vending machines are large, vending machines are found on the ground... Even with all that it would put vending machines in the middle of a forrest, trees in an office and stack vending machines on top of each other so you would have to keep going if you wanted it to have some grounding in reality.

Also, if you're not careful you'd need constraint solving to make sure adding a new object into the world didn't short circuit a previous puzzle e.g. if you had an elaborate puzzle to obtain a coin but then added a second coin for another puzzle you could use the latter to skip the former puzzle.

> The kind of game like Bureaucracy that puts the player into some borderline absurdist rage that soon changes into laughter.

Yeah, I was wondering if you could treat the absurdity as a feature somehow instead of the hard work in trying to fight it. The major roadblock I was finding is it's hard to make the player care about what's going on if it's just a bunch of generic objects and puzzles. I've barely seen any advancement in AI in terms of interesting computer generated plots and characters which is what you could combine the above with.

Instead of better gun fighting AI and path finding, I'm really looking forward to games with complex AI characters where the gameplay involves you persuading them, befriending them, manipulating them, interrogating them etc. where the game has a plot that adapts to what's going on.

Games are all about shooting stuff and physical object puzzles right now. I'd like to see game equivalences of movies in genres like drama and thriller that revolve around complex character AI interactions.

Sounds like Gabriel Knight 3's cat-fur-mustache puzzle.

For those unfamiliar: You're trying to impersonate someone, so you use a convoluted trap to get some cat fur, which you use as a mustache. But the person you're impersonating doesn't have a mustache, so you draw one onto his ID with a marker.

> But the person you're impersonating doesn't have a mustache

That's easily the funniest part about that puzzle!

> 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.

I'm pretty sure you can find all of these in Japan.

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).

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.

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

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

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?

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

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.

When can I play this?

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.

I see a lot of people on Steam complaining that it won't run without AVX support... what exactly did you use AVX for?

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.

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.

It crashes? Can you email b.stolk at gmail the call stack? You should see a window with crash info if it crashes. Thanks.

This guy gets Marketing.

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

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).