Polygonal Map Generation For Games | Hacker News Reader

Polygonal Map Generation For Games

www-cs-students.stanford.edu

263 pointssantadays32 comments

This is very cool. I recognized the website right away, because I've used Amit's excellent resources on pathfinding in the past while working on games.

http://theory.stanford.edu/~amitp/GameProgramming/

This is cool, but my big problem with games using techniques like this is that they tend to end up feeling soulless. I guess it would be fine for a game where the players create the soul of the game during the course of play (something like a Civilization game, or maybe an economic-focused RTS or MMORTS). But for games where timescales are short and you're not going to build anything yourself, map designers are better off, you know, designing.

These tools are awesome for generating

a) A first draft of a map. Just build _something_ so you can playtest. Shape it up as time goes by

b) Fleshing out all the areas the player is less likely to see. I'd say about 80%-90% of map space don't directly influence gameplay and are just there to give you a feeling of a complete world.

When I was futzing with that stuff, I used to call it "Computer-assisted content generation" instead of "automatic content generation" or similar. Bonus points: Communicates to the designers/map builders that you do the work to help them, not to get rid of them ;)

(Edit: fixed typo. Or grammaro, really ;)

I've long believed that procedural content is not the end people were thinking of it as, but a means. Rather than treating it as "the way content is created", it should be built into the tools used to create content.

Imagine this: You create a new area in your game tool. You're presented with a blank map. You generate a random terrain based on some parameters, then you go in and start painting. You paint some forests, some cities, etc. Then once you have the high-level map, you can zoom in and start painting trails in the forest, specific buildings in the city. Where there are forests, you'll see a random mix of trees, rocks, etc. Your trails cut through this and meander a bit randomly, send off some forks automatically. But you have the power to override this anywhere you want to, e.g. to put in specific things related to quests or story.

By mixing high-quality procedural generation with designer input and direction, I believe you can achieve great things. In fact, I think it's the only way we can reduce development costs while keeping standards of quality up; with the budgets involved in AAA titles, it's the only way I see forward.

Yes.

I like the way that Dungeon Crawl Stone Soup does it - they have a bunch of carefully crafted dungeons with procedurally generated stuff too.

(http://crawl.develz.org/wordpress/)

Spent quite some time working on something like that. (With a rendering backend that can only be described as insanely brilliant. Sadly, that was not my doing ;)

It's a bummer our studio got closed :(

What happened to the code?

If you're not doing anything with it, why not open source it?

Because I don't own it. Tends to happen when you work as an employee :)

As far as I know, if we're really lucky it lingers as a backup somewhere. I don't think anybody is actively using it, or even looking at it.

What about the rendering backend made it so brilliant? I'm a graphics guy and that piqued my interest...

Incredibly dense storage for incredibly large areas (10km^3), the ability to generate arbitrary levels of detail for terrain from the source data on the fly, and the ability to "patch" any level of detail with artist-supplied data.

I agree about being potentially "soulless" but a counter-argument is if you generate the landscape and then let a designer come in and make logical choices of where to place designed elements and the flow of the map I think it would be awesome. Like real life! :) I sometimes feel like designers just design one path or design a stronger single path but this approach lets it be more natural.

I understand what you mean, but I think it comes down to what level of detail gets generated. As an example, my kids and I are often amazed at the landscapes and other things generated in minecraft.

A computer program will only do what it's told. It's only as creative as the programmer. It is only as soulfull as him.

What do you mean by soulless exactly?

My favorite part about games is the ability to explore. I love the feeling of discovery. For reasons I have difficulty explaining, this feeling of discovery is dependent upon my assumption of intent in everything I see. If I believe everything I see is arbitrary, then I get no satisfaction out of discovery.

It's a fine line, because also important for the feeling of discovery is the illusion of being in a real place. So I want a place that is designed, but not constricting. Skyrim is great about this. When I discover something in Skyrim, I know that a human being decided to put it there - which means that if I think this thing is connected to some other thing in the world, then, yes, it probably is. Skyrim has little touches like this, where even minor caves and huts have a story behind them.

Perhaps another way of looking at it is that I'm discovering someone else's story, but I have agency the entire time. If everything I see is randomly generated, then there's no story to discover.

I know it's brought up again and again, because it really is the perfect counter example to this, but have you tried Dwarf Fortress? If you get past the ASCII art there's a tremendous opportunity for discovering really rich stories that just kind of bubble up out of the chaos of DF's various simulations going to work.

I think part of the reason it has been so successful (in its own way) is that people share these stories and retell them to other players, which results in something closer to collaboration between player, game engine, and game creator. It boils down to taste, but I find it much more interesting and awesome.

It's definitely different from the kind of purposeful designed stories that are hidden in Skyrim, but I think it's a promising place for game devs to explore, especially if a large team of writers and designers isn't in their budget.

Dwarf Fortress really lends itself to creating narratives. From the DF dev log:

I visited a tomb today as the adventurer Cadem Renownletter to see how well the game retains the position of skeletons and treasures as I move them around. During the process, a mummy boxed me in the ribs, broke my finger, bit my hand and shook it around until the hand came off. The mummy then animated the hand and they both attacked me. The hand scored the killing scratch, earning the name "Drippedsieged, Cadem Renownletter's left hand" and earning the tomb an additional defender against further testing. Its middle finger is still broken.

I have yet to try it. I was fascinated by the depth of the simulation back when I read this: http://news.ycombinator.com/item?id=2793615

But as you said, that's a very different kind of game. Part of the reason I have not tried it is that I would have to play it on a computer. When I play games, I want to sit on my couch, looking at my tv.

Skyrim (6 instance designers) is good to contrast with Oblivion (1 instance designer) because they're by the same developer in the same game timeline--Oblivion instances have a lot more pointless content, like a bridge that leads to a blank wall with no rewards. I think you can almost certainly procedurally generate "soulful" content, but we're not there yet.

Determining when a game has "soul" seems like a difficult trait to qualify objectively, but generally speaking, I think you can just sort of tell when games feel like they have that special touch put in by a human designer.

IMO, TF2 (and most other Valve games) demonstrate "soul-ful" level design pretty well.

I'm not quite sure, but I will say that big, procedurally-generated games tend to feel "empty." There might be small islands of uniqueness, but they're surrounded on all sides by areas that are bland and indistinct. But some execute this better than others. Freeing designers from having to figure out where to plant trees or how to do landscaping so that they can work on the story is a good thing. Watering down your game with bland, empty, cookie cutter content is bad.

I did a talk on the random level generator in Path of Exile if anyone is interested: http://www.youtube.com/watch?v=GcM9Ynfzll0

I'm not a great public speaker, so I apologise for the "Um"s and "Ah"s all the time.

We have two different generators and this video talks about both of them.

Brilliant handling of rivers. Everything I've seen in the past is either error-prone (rivers flowing uphill) or computationally expensive (needing to simulate erosion & deposition)

Would love to see this applied to generate much larger, more expansive worlds.

To me, "an island is an island is an island" and they all feel the same (mountain in the middle). More expansive landscapes with larger biomes and geologic process would be awesome.

Take a look at dwarf fortress and the map generator it contains.

Some of the most fun I've had writing code in a long time was doing something similar, but much simpler. My basic approach was to start with an existing coastline shape and just make more-or-less evenly shaped polygons inside of it. Example:

http://victorsunited.com/map/South%20Pole/board_game_rules

I didn't do any biome coloring or similar because the game displayed colors on the map to indicate which player was occupying it.

You can interactively play with a basic Voronoi diagram at http://mbostock.github.com/d3/ex/voronoi.html. The yellow polygon on the mouse shows the polygon that would be there if there had also been a point underneath the mouse cursor. That demo helped me get a feel for how they work.

If you're skimming, don't miss this article's Flash demo linked at the bottom, http://www-cs-students.stanford.edu/~amitp/game-programming/....

saw this the other day on Open Processing's Twitter feed "procedural dungeon generator" http://www.openprocessing.org/sketch/44400 (requires Java)

Be sure to not miss the final Appendix section, even if his Voronoi approach might not be the best approach for your particular map-generation needs (it really depends on your game IMO), there's a TON of links to great resources on various map-building topics: Technical things on Voronoi/Delaunay comp.geometry, general map building stuff for RPG/geofiction, Biological tables for determining plausible biomes, Geology references for plausible terrains and even a site on how to do pretty relief shading like is done on classic topographical maps!

A fantastic write-up, thank you.

> For the coastline, I wanted to make island/continent maps that are surrounded by ocean, so that I don’t have to deal with people walking to the edge of the map. For the mountains, I started with something simple: mountains are whatever’s farthest from the coastline.

You mention in "Impassible borders" that there are no cliffs yet. I'd be interested to see how that gets implemented.

I'd also love to see someone code a Roguelike for this - one polygon per move, maybe?

I needed something like this for a project I am hacking on!

This is unbelievably cool. That is all.

Reply on news.ycombinator.com