Posts Tagged ‘procedural’

Flood-filling for Procedural Wizardry

December 4th, 2012 Comments off

In case anyone is not a Temple of the Roguelike regular, I highly recommend reading through this thread discussing floodfill applications.  It includes simple code examples, discussions of problems/alternatives, and practical ideas on how it can be used for good content.  All excellent brainfood for anyone looking to use one of the best algorithms in the procedural design toolbox.

Procedural Tips

November 23rd, 2012 1 comment

So there’s a cool article on now with tips on using proc gen elements in your game.  Maarten Brouwer of procedural platformer Cargo Commander goes into some great details about how to use procedural content beyond just having random elements, but really going into making it balanced and interesting to the player.  Very similar to what I wrote about a few days ago in making the program design the levels, not just randomise them.  Go read the article – it’s got some great insights and practical advice.

A big “but also” I’d add is relating to his first point on not worrying about connectivity.  Worry about connectivity!  Floodfill is a miracle tool that can ensure everything is connected, whilst also being a golden technique for procedurally generating content in interesting ways.  It can be used to make 100% solvable lock-key puzzles for instance.  It can determine the optimum point to place enemies and items, and inform the AI about the right way to behave in that area.  It can detect dead-ends, which can then be removed, looped up, or transformed into something interesting for the player.  Best part about floodfill is it’s quite a simple algorithm at its base, easy for any basic coder to learn.

Some take the attitude that 100% connectivity isn’t important. Personally I think if a human designer would never make such a level, why should an AI designer? There’s no excuses in design faults like this, no matter how much you brush them over. There are a wealth of procedural tools out there to help overcome any design problem, it’s just a matter of using them right.

The Thoughts of a Procedural Level Generator

November 14th, 2012 4 comments

So earlier I blogged about how procedural is so cool and rad, etc, whilst also bemoaning that there’s not enough detailed procedural generators that tie different elements like monster and item placement together.  I’m as guilty of this as anyone else, partly because it’s so much quicker to use simple algorithms, but also I guess because people don’t expect any better.  Well, let’s have a look about how a good dungeon generator might think through the creation of a level:

1. Huh? What? Oh goodness, I oversleep()ed and now I have to crank out a dungeon level. Well, let me think, should I have a theme? Yes! And what should the theme be? It’s deep in a dungeon and there’s not been a forge level yet, so I’ll make one of those, yes? Active forge? Yes. Will there be a dominant monster type? Yes. Population? Orcs. 60% dominance.

2. Okay, let me think openly about the general shape.. .. .. .. .. My, that’s a lot of noise/BSP tree/cellular whatsits! I’ll shape that up here with some heightmaps / room space allocation / edge smoothing / whatever else. Ah, that looks much nicer now! Any extra decorations to shape I want for now? No, it’s good as is.

3. Hmm, better check it all connects together. Got a lovely floodfill for that… And whilst I’m at it I’ll check there are no lengthy dead ends by adding a heightmap to the floodfill and connecting up some of the maxima. Can’t be having our avid adventurers backtracking all the time, after all…

4. Should I have a river? Nah… Lava? Sure! Let’s spill it in the east side, let it burn down some walls, go under this corridor (now a bridge over lava) and carry on south-west. Island in the lava? Okay, and I’ll place a special item there for adventurous types to fawn after. Enemies in the lava? Sure, I’ll throw some fire drakes in. They have a lovely ranged attack they can use on anyone crossing the bridge.

5. Might put a small vault in the north of the level. Keep things connected as it’s placed. What monster type? I’ll follow the orc theme and choose some orc assassins. Artifact reward? Nah. Large gold pile? Sure. Trapped entrance door? But of course…

6. Since it’s a forge I’ll make a large central room into a forge room, with a forge inside and some relevant materials. And an orc weaponsmith, and some goblin slaves. Nearest room will be stockroom. I’ll make it 40% armour, 30% weapons, 30% consumables.  Artifact? Okay, medium grade. And a second low grade too. I should definitely place a guardian here – a nice big troll in fact. Doors to this room are locked – I’ll put the key somewhere else on the level which is definitely accessible from the entrance stairs (ah, floodfill, I love you so).

7. Any other special rooms? An altar in the west will suit. Include some scrolls. And a rabid orc priest. Followers? No, but we’ll give him a pet. Fantastical creature? Sure! We’ll make it a griffon. And I’ll throw in some griffon babies too. Aren’t they cute?!

8. Hmm, there’s a dead-end room in the west.  Any chance of a special item for here? Sure, a special potion. In a trapped chest. Guarded by… mages. Path to the dungeon entrance from here is to the north, so I’ll position them in a defensive formation near the door there, with a healer behind them.

9. Now, in the other rooms we’ll place some orcs and a couple of other creatures, with no more than 2 being higher than base level. We’ll give one of them a wolf pet as well. And in one corridor we’ll put an archer – everyone likes archers in corridors, right?  And a trap there too, but we’ll let the archer know not to trip over that. And we’ll have the archer carry a nice bow and dagger.

10. All done now! As a final touch I shall christen this level “Corpsefire Forge”.  Bon appetit, adventurer!

Looks very involved, yes? Kind of like the thoughts a real designer would go through? But that’s the point really – you want something almost as good as hand-made content, but with on-demand infinite generation and variety.  It needs some coding together and a good pool of input values.  The coding is not so hard as you might think – everything above has been done before to some degree in open source games, so at a push you could copy paste this generator together.  But the hard examples to draw from are a lot more work if you don’t want the same few combinations popping up over an over again.  I guess this is partly why big roguelikes are so popular – the larger content pool allows for greater variety in random encounters.

Some day I’ll make a cool generator like this.  Honest  ;)

Hate Random, Love Procedural

November 14th, 2012 5 comments

As roguelikes and games with roguelike mechanics get more mainstream success I’m seeing a bit of backlash against what is termed “too much randomness”.  I’ve seen a lot of this directed against FTL, but also against The Binding of Isaac and complaints of it in the latest X-COM.  Yahtzee wrote a good article on the topic earlier this year, and Craig Stern recently wrote in great length about the failings of random mechanics.  But I think it’s vital that we distinguish between randomised content and procedural content, as although there is some overlap the end implementation can have very different effects on play.  And for developers it’s important to understand the role of procedural generation, and why it’s not the same as “just random”.

I’ve always hated random mechanics in games.  Missing a weak enemy twice in a row because you got a bad dice roll can really ruin the feeling of a game.  Plus some developers seem to think having the ability to run thousands of dice rolls means they should have insanely complex systems that require intense study on a turn-by-turn basis to assess the probabilities.  If you need Wolfram open to figure out how many attacks on average it takes to kill that monster then likely the battle system is badly designed…

Chaos Plane in ADOM

This is random…

Dice rolls were popularised with D&D, where rolling that d20 and praying for a 17 or higher was part of the tension and the fun.  But a good DM knows that letting the dice rule the game is not so fun overall.  When role-playing you don’t want to be thinking about numbers all the time, and random chance can get in the way of a well-designed campaign.  The essential element of unpredictability should come from the imagination of the players.  However this history of dice in Dungeons and Dragons has made its way into many RPGs, with a lot of fantasy roguelikes in particular using numbers and dice ranges lifted straight from the Player’s Handbook.  Whilst drawing inspiration from their favourite sources they also blindly copied over these poor features.

I don’t want to get too much into why I hate randomness, especially when the two articles linked above go into plenty of detail.  If you’ve played Risk you probably know all the reasons.  Go play Small World instead and you’ll see how much more fun a deterministic system can be.  Feeling in control means you don’t feel cheated by the system, and you properly respect the winner for their skill in attaining victory.  Importantly in single player games a deterministic system means you have only yourself to blame for failure, and you are forced to learn to be a better player instead of blaming the game.  Instead of thinking “I’ll get lucky next time” you think “I’ll make better choices next time”.

I do sometimes use randomness in games though.  It has its place in providing variety, and in also giving the player the option of taking a risk on something.  Usually in my games when an option is open with random chance it’s a high risk, high reward decision; it’s part of my philosophy that power always has strings attached.  But when present it’s usually entirely optional – the default action is the deterministic one – and the chance of failure is made clear.  Another good (or at least acceptable) application of randomness is in providing bonuses instead of failures.  The assassin’s 1 in 4 chance of paralysing an enemy in Dungeons of Dredmor for instance.  You know you can’t rely on it, and you always feel good when it kicks in, yet it doesn’t dominate the play.  But I’m very much against randomness overshadowing the outcome of player choices.

So why do some games make heavy use of randomised results?  To stop them being linear puzzles, predictable from the very get-go.  To prevent you feeling secure in what’s going to happen next.  But this is where procedural content generation comes to the fore.  And it’s important to both consider how it creates content for the player, and for how that content changes over time (AI).

It should be stated loud and clear that procedural does not equal random.  It tends to use a random seed, yes, but it builds upon that intelligently to produce *interesting* content instead of just random content.  A perlin noise map is very different from a procedurally structured forest map populated with enemies, items and quest goals.  Your level generator should be more than just a form of terrain mapping – it should be its own AI, a designer following a ruleset with some random initialisation to produce varied content.  The rules and design it follows should produce intelligent and interesting content for the player that goes far beyond simple random patterns.

Jeff Lait's Smart Kobold

…and this is procedural – Jeff Lait’s ‘Smart Kobold’ with intelligent content arrangement

However if one does procedural content badly then it can degenerate into pseudo-random levels.  Unfortunately a lot of games using procedural techniques use them weakly.  Dungeon generation is separate from monster placement, which is separate from item placement, and monster and items tend to be spread randomly across the level without consideration for the player experience.  This is really not taking full advantage of what a well-designed procedural generator can do.  Of course writing such a generator is far from trivial…

But even poorly implemented procedural content is better than pure random.  It sets limits to ensure the game is completable, that the challenges can be overcome or avoided.  Floodfilling to ensure dungeon connectivity for instance, or restrictions on monster spawning to prevent them appearing next to the player – simple touches that make a big difference, removing the chance of perceived unfairness from the game.  A procedural generator provides a more structured experience, with patterns that the player can come to recognise and take advantage of / game.  It ends up forming part of the game rules that the player is working with and against, an integral part of the play.  And of course there’s the element of surprise – the turning round the corner to find something you haven’t prepared for, and thus having to react to the circumstance in novel ways.  This is different from a string of random misses in a random battle system, as it doesn’t take away any sense of entitlement and still leaves you feeling in control of whatever situation arises.

Procedural over time is another area that’s under-developed.  AI is a big part of this – mobile units that react to the player’s actions and present their own challenges.  These can introduce the complexity of interactions that normally other players add to a game.  Good AI is also tricky, but even simple behavioural patterns can create the components for emergent complexity.  What there really isn’t enough of though is procedural changes in the level over time.  A dungeon that reshapes itself, that reacts to your presence or the movements of enemies, can create an engaging environment to explore and forces you to constantly reassess your tactical surroundings.  A few examples of this are the ice levels in HyperRogue, the sand dungeon in Tales of Maj’Eyal, and the rather crazy dynamic levels in my own UNSTOPPABLE.  There can be more detailed control of content over time, like the famed AI Director in Left4Dead, and I’m hoping we’ll see even more novel stuff in future.

PCG for me has always been about crafting a player experience that is fun, engaging, and of course different every game.  Randomness, on the other hand, I find is rarely fun or engaging, and often ends up feeling very samey over time. One game of snakes and ladders feels very much the same as any other, and if you keep staring at perlin noise maps they quickly lose their novelty.  A really detailed procedural system can not only generate compelling content, it can also react to a player’s actions, crafting a uniquely tailored experience which only that player will ever see.  Achieving that is far far better than a string of natural 20s.