I was pretty happy with the sketching tool from last week but I wasn't sure whether it actually produced the data I needed. I connected several separate projects together to make the sketching tool guide the generation of rivers and elevation. These projects weren't coded to work together, so the page is rather clunky, but it served its purpose. I found that the sketching algorithm needed some tweaks, and the river and elevation algorithms need some tweaks too.

Example of generated rivers

I also extended the sketch demo to let you change the boundary points, which have elevation -1. By default they're at the borders of the map. By removing them from the borders you can get non-island maps. By adding them elsewhere you can generate lakes.

Example of generated rivers

The demo is here.

Labels: ,

The main reason I put the previous experiments on hold is that one of the major goals for the current project is for the game/level designers to have some control over the procedural generation. This week I experimented with a sketching tool that lets you draw mountains and coastlines.


It ended up being a fairly simple algorithm that's fun to play with.
The demo works on touch devices too.

Labels: ,

I had been working on generating mountains from rivers. I got some cool results, but put it on hold. I had been pursuing things based on what would be cool but had lost sight of the actual goals of the project. Some images:

And here's the writeup. Next time — something different!

Labels: ,

In my polygon map generator from 2010 I built the mountains based on the coastline, then made rivers flow down from the mountaintops. I’ve been exploring a different approach. Last week, I grew rivers up from the coastlines. My goal this week was to build mountains that matched the generated rivers.


I wasn’t able to make something that worked to my satisfaction, but I wrote up my notes, and will try again next week.

Labels: ,

In a normal procedural generator I would start with elevation, then figure out oceans by looking at where the elevation is low. For my procedural generator from 2010, I started with the oceans and then build elevation to match. Working backwards led to some cool maps. I worked forwards for rivers though, making water flow downhill, then calculating river drainage basins. I'm always looking for opportunities to solve problems backwards, so this time I'm trying to make river drainage basins first, then make the rivers flow uphill, then build the elevation to match. This paper is part of the inspiration. I'd also like to be able to place some of the rivers and have the system figure out where the rest of the rivers are.


I wrote my notes here.

Labels: ,

Most of my project use grids. I rarely work with polygon structures. When I worked on my polygon map generator project in 2010, I created my polygons thinking of graphs: nodes and edges. People who work with polygons have better ways of representing them, but I hadn't studied them until now.

For my new map generation experiments I'm learning about half edge, winged edge, quad edge, and other data structures. I wrote my notes here.

When I think back on my polygon map generator project from 2010, the word I associate most with it is voronoi. I used Voronoi diagrams for spacing the points and also for constructing polygons around those points. Seven years later, I'm revisiting this, looking at the ways in which Voronoi wasn't a perfect match for my needs, and looking for alternatives.

Voronoi and Delaunay graph diagram
I made my own polygons from Delaunay triangles and plan to use this for a future procedural map generation project.

Labels: ,

People ask me how I write my interactive tutorials. I can point at the HTML+CSS+JS but that doesn’t show the process. I decided to rewrite one of my interactive tutorials from scratch, documenting the process along the way.

I originally planned to use a very simple tutorial, but I decided to use line drawing instead. It's a medium sized project for me, with multiple diagrams, multiple layers in each diagram, draggable handles, and scrubbable numbers. I think it covers a reasonable set of the things I use for my tutorials. This tutorial shows how I put everything together.

This is an interactive tutorial about making interactive tutorials.

Labels:

Outside of games or even product development, there's a broad problem called global optimization in which you are trying to find the maximum of a function in some space. If we think about a “space” of all possible game designs, then we're trying to find good places in that space. Hill climbing is the simplest approach to function optimization — in each iteration you make a step to improve. The problem with hill climbing is that you run into “local maxima” — you are at the top of your little hill but there's somewhere far away in game design space that's even better. You can't see that far away so you never find those other game designs. Metaheuristics are different approaches to dealing with this for function optimization; some of these ideas also seem to apply to game development:

  • Simulated annealing says: start with big steps early on, make smaller steps later on. This already happens with many games, with early development making larger changes and post-launch being smaller changes.
  • Swarm optimization says: explore multiple places at once. Early on, you can prototype many different related games, and then see what works well and what works poorly. Later in development it's impractical to build many different games but you can explore small variants with A/B tests.
  • Genetic algorithms says: explore lots of places at once, randomly mutate them, and make copies of the best solutions. This seems like what the modding community provides. Let them explore many alternative sets of game rules, and then incorporate the best features into other mods or into the base game.
  • Variable neighborhood search says: alternate between making small changes for a while and then making a few big changes every once in a while. This could mean periodic patches and also bigger changes in the form of expansion packs.
  • Graduated optimization says: first optimize a simpler problem, then use the solution to simpler problems as a starting point for exploring a more complex problem. This happens in games that start small and grow more complex over time.

Are there other techniques you use to avoid your game design getting "stuck" in a local maximum?

Labels: