Friday, October 24, 2014

That Which Is Graphlike

Procedural content generation (PCG) is the hallmark of roguelike games, the crucial feature that make every play-through unique and extends replayability into the stratosphere.  However, roguelikes have a problem: their levels lack much in the way of meaningful structure, causing them to compare unfavorably in many ways to games with hand-crafted content.  Roguelikes are largely unable to even attempt many things that traditional, non-PCG games have always been able to take for granted, due in large part to this lack of structure.

Even such a simple trope as the lock-and-key puzzle, for example, has only lately been explored, e.g. by forward-thinking games such as Brogue.  These are laudable efforts, but fundamentally rooted in the same old ideas about level generation.  Some folks have keyed into the idea of finding the graph of a level once it's been generated, and you can do a lot with that, but it's not the same as being able to create the structure you want from the ground up.

Graphlike, a roguelike library project, is about creating something different.  The core precept of Graphlike is to start with the structure you want, and build a level out of it.  Structure is expressed as a mathematical graph (a planar graph, to be precise -- no edge crossings), along with specifications for room shapes and sizes.  The Graphlike algorithm figures out how to create a dungeon satisfying the given structural constraints, providing an environment with properties you can count on to open up new horizons in dungeonbuilding.

Here's an illustration of the basic idea:

So... what's it good for?  Well, I've got some ideas, but my real hope is that if I put this tool in the hands of creative people, they'll show me uses for it that I never would have considered.  I believe the possibilities are vast.  Here are some of the ideas I'm looking forward to exploring, though:

  • Player control flow: pinch points and defined branching paths.  Make sure that a player has to pass through room X on the way to room Y, or that there are exactly three ways to get from A to B.
  • Control over pacing and tension.  When playing a level designed by a human, we experience intentional pacing.  Challenge can be carefully regulated to provide a satisfying tension curve.  We can fight three mini-bosses on our way to the main guy (or gal).  Resources can be provided at dramatically appropriate moments.  With Graphlike, choices in the construction of the level graph grant detailed control over all these elements.
  • Environments that look more like real places.  You enter a great hall, dozens of paces across.  The room is ringed with doors leading to tiny alcoves.  A great archway leads onward into the heart of the fortress.  Room sizes and shapes can vary widely, as can the number of connections they have.  These building blocks create a much richer toolset for constructing environments that don't just look like a bunch of boxes hooked together with hallways.
  • Structural and spatial puzzles.  Graphlike can help create arbitrarily complex lock-and-key puzzles, as well as other forms of puzzles involving movement between rooms.
  • Dungeons with moving parts.  Graphlike's algorithm works dynamically -- you can grow the graph incrementally, and watch the updates to the dungeon in real time.  With some additional work, the same mechanics will be able to support dungeons that move, grow, shrink, etc. in real time.  You could even have a level that starts with almost nothing, and grows depending on what you do.  I feel certain that game designers can find cool ways to use this.
  • A stage on which to set a play.  I have some aspirations involving procedural narrative generation as well, and being able to create structured environments to support a generated plot figures centrally in them.
  • Not just roguelikes.  By removing so many restrictions that have applied to roguelikes and PCG historically, I hope to show that many familiar genres can incorporate the advantages of unlimited content without sacrificing the mechanics that define them.  Whether or not Graphlike succeeds in making this point to a broad audience, I believe in this idea and want to see it in action.

Graphlike was originally an idea for a game, rather than a game library.  I was even publishing a development blog about that game-in-progress for a while.  As I focused my attention on this central problem, though, and spent quite some time exploring various other approaches before settling in on something viable (I'll write more about the algorithm soon), the rest of the game fell by the wayside and I decided that the best thing would be to just solve the graph problem really well and make it into a tool anyone can use.  Once I've got it to the point where it's worth sharing, I'll make the library public and start working on games to show what can be done with it.

I'm not making any promises yet as to when it will be available.  I started all this several years ago, and life hasn't always been cooperative.  I have a successful proof-of-concept prototype that I feel good about now, though, so I decided it was time to start documenting my progress again (the old blog sort of degenerated into a series of hopeful but failed attempts, and became a little depressing to update).

I'll post more soon with more about the Graphlike algorithm and some screenshots that will get the idea across better.  Thanks for reading, and I look forward to sharing more when I'm able.