Polygonal map generation (attn Telarus)

[Triple Zero]

Thought you might find this interesting:

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

it's kinda scarce on the algorithms behind each step, but I seem to understand what they're doing in the majority of them.

assuming you're familiar with the concept of Voronoi cells? if not, cool stuff, look into it. Also how they're the dual of delauney triangulation, makes them even cooler

[Telarus]

Super interesting! Thanks Trip!

[Triple Zero]

well wtf ... apparently I only skimmed that article the previous time, because I just spent the afternoon reading it with great interest as it got linked on HN, and then I figured "I should post this here, for Telarus, let's see I believe there was already another thread about map generation ..."

And then it's the same bloody article!

Anyway, I don't know if you read the entire article either, but you might definitely want to take a look at the very last section, the Appendix, which contains a LOT of links to references, not only real technical computational geometry resources on Voronoi cells and Delaunay triangulations and algorithmic map building, but general stuff for broader audiences about RPG/geofiction map building, and then right back to Science with biological tables for determining realistic biomes and Geology references for plausible terrains and even a site about how to do relief-shading on topographical maps!

[Triple Zero]

BTW this guy's whole site is amazing. He's got an enormous amount of very well written explanations of all sorts of game design and game programming related topics (I just read a whole bunch of stuff about A* path finding, for instance--but I'm going to have to come back later this week and see what else he got )

Check it out http://www-cs-students.stanford.edu/~amitp/gameprog.html

[Telarus]

Bad ass.

I've actually been reading about 2 decades worth of research papers out of the Oregon GeoVizualization Dept on relief shading. I'll have some stuff to show off in that area here in a few months.

[Triple Zero]

Cool! Curious to see it!

Here's another bunch of articles I read yesterday evening:   

The Death of the Level Designer: Procedural Content Generation in Games - Part One (click for parts Two to Six)
Proceduralism: Part One (Revision) (goes up to Part Eight, hints at a Ninth part but either he hasn't written it or I haven't found it)

Together these form a very interesting discussion on the ideas of Procedural Content Generation in Games. He explicitly steps beyond procedural graphics and texture generation (Perlin noise, etc) because that territory is rather well covered, rather discussing procedural generation of a bit higher level content: procedural levels, worlds, items, storylines.

He mentions a lot of game titles, but I'm only familiar with a few of them, dunno if I missed much by that. I get the idea that especially the first series might be a bit dated cause it's written 5 years back, but mostly in the sense that he makes some predictions that haven't come true yet and some things about Spore.

Apparently the type of game that currently implements the most advanced Procedural Content Generation, is the "Roguelike" game. And as far as I can judge, apparently that is a genre of games that look like NetHack ... Or maybe I'm mistaken? How hard could it be to use some graphical tiles?

He doesn't go into a lot of technical detail about algorithms, unfortunately. But in one of the later articles, he argues that most game designers developing and building procedural content engines, generally tend to re-invent the same rough types of general tool sets (such as fractals, genetic algorithms, markov chains, simple weighted random templates, etc). So in order to prevent game developers from re-inventing the same wheels all the time, he built a motherfucking bad ass Procedural Content Generation Wiki:

http://pcg.wikidot.com/

I haven't really dug into this one yet, but [url=http://pcg.wikidot.com/category-pcg-algorithms]the page on Algorithmic categories (for PCG) looks promising, and I would especially like to recommend checking out the differentiation between teleological and ontogenetic procedural content generation (as far as I understand, every PCG algorithm is either one or the other).

"Hey Trip, so why are you suddenly reading all these articles on Game Design?"

Well for starters because they were there and and being super interesting and addictive like fucking TVTropes Wikicrack the whole weekend

And because I sort of decided to try and see if I can get back in democoding. But I'm still sort of in exploratory mode about this. I'm not sure whether I want to return to coding 4Kb demos (like I used to do last century) in x86 assembly or C or something, partly because I kind of got spoiled by higher level programming languages such as JavaScript and Python, partly because it's kind of nice to have stuff that runs cross-platform, partly because it's kind of nice if your best production (Meuk, 2nd prize at Mekka & Symposium 2000) would still run at all on any modern OS (which it doesn't, but with a special type of virtual DOS-box emulator, it "sort of" does, with choppy sound) (it might be filthy distorted noise core beats, but it wasn't supposed to be choppy) ANYWAY also because maybe I don't have the patience to fuck around with assembly code anymore So maybe I'm just going to try and create interesting eye candy, which should be generative because it'll be a while before I caught up on nearly 10 years of 3D gfx and shader technologies, but generative stuff I can probably excel in. Or maybe I'm going to make soft synth DSP effects, which afaik hasn't changed much and is still mostly CPU-based. Or maybe something else!

But currently I'm poking around in Javascript. While Python has some nice libraries (PyGame for basic stuff, PyBox2D for a cool 2D physics engine I'm probably going to play with sooner or later anyway), JavaScript has the advantage that it can run in everybody's browser, so I can easily show it off to many people. And showing off is of course the main drive for any democoder

Additionally, the kids at the Young Researchers centre, when making games using GameMaker (which is actually a pretty nice tool, mostly for kids, but possibly even for rapid prototyping of 2D tilebased maze/dungeon games), they want to put their games online, on a website. Funny thing how it's not at all obvious to a modern kid that there's quite a difference between running a standalone executable (which is what the free GameMaker version can provide) and running a web application within a website (be it Flash, JS or Java applet). Anyway, the basic system of GameMaker seems pretty simple (sprites, objects, events and collisions) so I'm going to have a stab at building a basic JavaScript framework so a kid could (hopefully) port their game to it. If it ends up being too complicated, at least I'll have some cool looking shit to show off :P

[Telarus]

Very cool Trip, I'll have to dig into some of that research.


As to modern games with procedural content, I'd keep an eye on Torchlight 2... all of the oudoor environments (i.e. not towns or dungeons) will be proceduraly generated. I'm looking forward to it myself (bonus.. only $20 per copy and it comes with LAN play.... yes, old-school LAN play not over a virtual network w/ internet connection.. though it will have that too).