Polygonal Map Generation For Games

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

by santadays • 14 years ago

263 32 14 years ago

www-cs-students.stanford.edu

andywood• 14 years ago

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/

jamesaguilar• 14 years ago

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.

lbotos• 14 years ago

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.

rcfox3• 14 years ago

What do you mean by soulless exactly?

alecbenzer• 14 years ago

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.

scott_s2• 14 years ago

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.

Natsu• 14 years ago

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.

groby_b4• 14 years ago

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

daeken• 14 years ago

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.

roqetman• 14 years ago

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.

vibrunazo• 14 years ago

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.

th0ma5• 14 years ago

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

jbattle• 14 years ago

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)

smlacy• 14 years ago

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.

lclarkmichalek• 14 years ago

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

jfb• 14 years ago

This is unbelievably cool. That is all.

DanBC2• 14 years ago

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?

MartinCron• 14 years ago

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.

Negitivefrags• 14 years ago

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.

joshu• 14 years ago

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

roryokane• 14 years ago

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

tripzilch• 14 years ago

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!

Polygonal Map Generation For Games

Related Stories