8 ms·

Polygonal Map Generation For Games

263 points by santadays 14y ago

jbattle 14y 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 14y 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 14y ago
  Take a look at dwarf fortress and the map generator it contains.
andywood 14y 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/ http://theory.stanford.edu/~amitp/GameProgramming/
jamesaguilar 14y 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.
- rcfox 14y ago
  What do you mean by soulless exactly?
  - alecbenzer 14y 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_s 14y 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.
    - spacemanaki 14y ago
      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.
th0ma5 14y ago
saw this the other day on Open Processing's Twitter feed "procedural dungeon generator" http://www.openprocessing.org/sketch/44400 http://www.openprocessing.org/sketch/44400 (requires Java)
jfb 14y ago
This is unbelievably cool. That is all.
DanBC 14y 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 14y 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 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 14y 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 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 14y ago
I needed something like this for a project I am hacking on!
himanx 14y ago
this is awesome. Some might qestion this put I am totally conveinced. http://technocharm.com/leakedjustin-bieber-and-selena-gomez-kissing-pictures/ http://technocharm.com/leakedjustin-bieber-and-selena-gomez-...
roryokane 14y ago
You can interactively play with a basic Voronoi diagram at http://mbostock.github.com/d3/ex/voronoi.html 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/polygon-map-generation/mapgen2.swf http://www-cs-students.stanford.edu/~amitp/game-programming/....
tripzilch 14y 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!

263 points by santadays 14y 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 14y 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 14y ago
Take a look at dwarf fortress and the map generator it contains.

andywood 14y 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/ http://theory.stanford.edu/~amitp/GameProgramming/

jamesaguilar 14y 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.

rcfox 14y ago
What do you mean by soulless exactly?
- alecbenzer 14y 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_s 14y 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.
  - spacemanaki 14y ago
    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.

th0ma5 14y ago

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

jfb 14y ago

This is unbelievably cool. That is all.

DanBC 14y 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 14y 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 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 14y 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 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 14y ago

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

himanx 14y ago

this is awesome. Some might qestion this put I am totally conveinced. http://technocharm.com/leakedjustin-bieber-and-selena-gomez-kissing-pictures/ http://technocharm.com/leakedjustin-bieber-and-selena-gomez-...

roryokane 14y ago

You can interactively play with a basic Voronoi diagram at http://mbostock.github.com/d3/ex/voronoi.html 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/polygon-map-generation/mapgen2.swf http://www-cs-students.stanford.edu/~amitp/game-programming/....

tripzilch 14y 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!