Clustering

Download Alpha and Omega v2.7.1.18.0
Binaries as Win32 Installer (3 MB)
Download Alpha and Omega v2.7.1.18.0
Source as Visual Studio 2010 Solution (4 MB)

In the previous post we've modified the rotating sphere to a sphere with a maze projected on it. The maze will give the landscape generation algorithms hints to where it is allowed to create less accessible regions. This way we can easily create oceans, rivers, mountains and cliffs without having to worry that some chunks of the world become inaccessible. In this post we'll implement the clustering algorithm that will form the basis of dividing the planet in different biomes.

Clustering

We don't actually need to implement a real clustering algorithm like k-means or DBSCAN because we don't require a decent cluster-distribution. The only requirement we have is that each cluster needs to have at least one sector and all sectors within a single cluster needs to be connected to each other. We've kept the algorithm very simple:

  1. For every cluster we'll create: Pick a random sector (that does not yet belong to a cluster) and add it to the cluster
  2. While there are still sectors that do not belong to a cluster:
    • Pick cluster, if this cluster has still a sector in the fringe that does not belong to another cluster, add it to it's cluster.
We'll just rotate through all clusters until all sectors belong to a cluster. The fringe of a cluster are all sectors that are directly connected to the cluster, i.e. sectors that you can walk to from the current cluster without going through a wall in the maze.

All those fancy colors make the planet look like a tasty jawbreaker. It's too bad that all those sharp corners will make your mouth bleed when you try to suck on it. This is something we need to fix when we're actually creating biomes. Sharp corners and strait lines (as shown in the maze above) will not look very natural when we are creating the actual biomes. When adding smoothness we also need to think about fuzziness  Some area's should be designated as transition-areas that slowly transforms the terrain from one type of biome to the next. It's probably best if we'll use a local algorithm for smoothness and fuzziness, so it isn't necessary to have the whole planet in memory to determine how these transitions are realized.

Changes to the Project

It turned out that some computers were not able to run the executable because the video-card wasn't supported. This was clearly a bug because I was too lazy to check for compatibility and the program just crashes on start-up. XNA-projects can be build using one of two profiles, "HiDef" and "Reach". The HiDef-profile is the default and is used to create games for XBOX and most PC's. The Reach-profile is used to create games for older PC's and things like Windows phones. This profile is a simple compiler-switch, but switching to Reach will give you some additional limitations that you don't have to worry about when using HiDef (see MSDN for a list of differences). We've modified the project to use Reach (for now) so it'll be compatible with more computers. I've had to modify the pixel-shader that we used for the liquid simulation in the breakout-clone since Reach does not support multiple render-targets. The weird thing is that the modified pixel-shader works just fine in the HiDef-profile but not in the Reach-profile :(. The pixel shader is pretty simple, it only uses one render target at a time and limits itself to pixel-shader v2.0 (=old). I've got no clue why the pixel shader behaves differently in the Reach-profile.

HiDef, as it should be Reach, so cute, BUT IT'S WRONG!
 

I find it really strange that the shader is behaving differently in the Reach-profile. Nowhere online I've read that pixel-shaders will behave in a weird manner :(. This is something I need to figure out! I just can't forget about it. Is it a bug? Is it something obvious? I already know that it doesn't matter (we will switch to HiDef sometime in the future to use v3.0 shaders and fancy vertex-shaders), but having weird bugs without knowing what causes it gives me nightmares.

Planetary MazeProcedural Emptiness

line