Planet 4 - Part 01 - Making a Mesh

Introduction to this series is here.

Phase 1 is initiated.  I will adhere to a keep-it-simple approach during development.  So setting up the window went very quickly; no config files, no nothing.

The first step was to create the nodes in a spherical arrangement.  I divided the space into unit cubes and looped through them.  Where the innermost and outermost vertices of the cube was on opposite sides of the surface, I placed a node.

Each node represents a surface of about 128m×128m.  Since they're neither square nor uniform the area differs from node to node.  I experimented with different sized planets a bit and decided that radius 60 makes a medium-sized planet.  The circumference is about 48km, which is definitely much further than I have ever traveled in Minecraft.  What's the point of an infinite world, then?

Fig. 1: Radius 60 Sphere - Each node represents a 128m×128m area

Next I move the nodes so that they are no longer on the sphere, but rather arranged in a grid.  This will make noticing and understanding bugs much easier.

Fig. 2: Nodes are now aligned to a grid for debugging visualization

I reduce the size of the planet to radius 5, implement an algorithm for finding their nearest neighbours and link them up.  Ideally, I would have used Delaunay triangulation, but I decided to keep it simple instead; I have never done Delaunay triangulation before.  So I looped through the nodes and checked adjacent grid points for neighbours to link to.  The first time I only checked in the positive directions.  Figure 3 shows the inadequacy of this optimization:

Fig. 3: Added node-to-node links - My first bug is apparent

A simple fix is to just check the negative directions as well.  This does slow it down a bit though.  There is a faster way, but it is complicated, so I stuck to the simple way.

Fig. 4: Fixed the links bug

While my current algorithm does find every node that will contain a part of the sphere's surface, this causes some foreseeable problems, in that the double layer in some regions will stop the erosion algorithm from working correctly.  I take a cross section to see what it looks like (Fig.5) and see two possible solutions.  I could get rid of all diagonal links, or I could remove the extra layer before linking up the nodes.

Fig. 5: Cross section shows double layering

I decided to implement the node removal method, since this will simplify the eventual creation of the zones.  Each node that has three axis-aligned neighbours that are closer to the center is removed.  The cross section looks okay, so I switch back to the full sphere view:

Fig. 6: Removing the extra layer is not working as intended

That's no sphere!  I tried a few different techniques, with no positive results.  Eventually I realize the problem:  When I remove a node I change the circumstances of the surrounding nodes.  Near the axis-aligned planes that pass through the sphere's origin this causes that some nodes will no longer be removed.  The solution is to keep a set of nodes that need to be removed, and only remove them after all have been found.

Fig. 7: It works now

And finally I put the nodes back into their original spherical arrangement.

Fig. 8: Off the grid and back to a sphere

Planet 4 - Part 00 - Introduction

Suddenly, I'm working on making a planet.  Again.

The first attempt was based on an article I read about a R.O.A.M.-based level-of-detail algorithm.  I focused so much on the data structures that I never got to the graphics, and so I lost interest.

The second attempt was to take a square grid, stretch and fold it into an octahedron and tesselate it into a sphere.  Though I managed to create an undistorted heightmap with continents, when I got to erosion I decided that distortion is too complicated.

The third attempt was to create a Minecraft-like flat world of cubes that wrap around at the edges, instead of being infinite.  At the time I was planning on adding "seamless" space travel.  I spent a lot of time working on finding a transformation that would allow the planet to be flat when you are close, but round when you are flying through space.  All the possible transformations had the flaw that the space-space had a two-to-one mapping to the planet-space; I.e, when you take off from a planet you end up in two locations in space.  What a mess!

In this new attempt, the fourth, the planet will be round and made up of voxels, using a technique called dual-contouring to allow diagonal and curved shapes.  The same technique was used by Miguel Cepero in his Voxel Farm engine, which is a component of the ForgeLight Engine being used in the EverQuest Next games.

My plan of action for Phase 1:

1. Get the basic framework up and running, so that I can debug right from the beginning.
2. Make a spherical mesh with reasonably evenly distributed vertices/nodes.  Each node represents a cuboid zone of voxels (a.k.a. a chunk).  Each edge represents a connection between adjacent zones.
3. Implement large-scale emulation and simulation procedures to generate the zone generation parameters.  E.g. continents, plate tectonics, water erosion, formation of rivers, lakes and oceans, temperature, prevailing winds, rainfall, and seasonal effects.
4. Serialization and deserialization of the zone generation parameter mesh.
5. Implement generation of zone voxel data from parameters using emulation and simulation of small-scale processes.  This is only triggered when the camera comes close enough to the zone.
6. Alteration of the voxels.  E.g. digging, building, explosions, eruptions, fluids.
7. Serialization of differences between the current zone voxel data and the procedural voxel data.
8. Automatic loading and unloading of zones.
9. Phase 2: Fancy graphics.

Next post: Part 01

2-D Tiles Renderer - Introduction

I got caught up in the Starbound hype, so I've decided to make a series on creating a 2-D tile-based renderer with procedural textures, normal mapping, pre-multiplied alpha, dynamic light and occlusion.  I guess you could think of it as a fan project.

Being a project of at least moderate size, it's a good idea to plan ahead, and to divide it into a set of smaller projects.  After some deliberation, I came up with the following parts, for a start:

• Render to multiple layers, combine them, and post-process for gamma-correction and dithering.
• Texture loader that can call generation procedures when a texture does not exist yet. (Maybe)
• Texture generation procedures.  They output all seam types and orientations with multiple variants.
• Tile renderer that uses instancing and hardware buffers.  It probably divides the map into patches.
• Fast/parallel occlusion checking function.  Output format must match input format, for recursion.  Final output needs to be filterable. (e.g. feathering)
• Background diorama renderer with parallax and altitude effects.
• Planetary parameters object that can output the necessary rendering parameters; e.g. lighting and atmospherics.
• Many more pieces that I'll think of later.

I probably won't finish the whole thing, but, if I end up with something useful, I'll release the source code.

I also intend to make this series of posts informative, but I have failed at that in the past.  I'll try harder this time.

I made a game!

For Ludum Dare #26, having the theme 'Minimalism', I made a game that I call 'And Then There Were None'.

It's a puzzle game where you have to make all the colored blocks disappear.

Blocks with the same symbol, but opposing colors (i.e. red vs. green or yellow vs. blue) cancel out when you push them against each other.

Blocks with different symbols have different effects when pushing against them.

Your cursor's color determines which color blocks you can move.  Beware, it usually sticks to the block that you are moving.  Moving your cursor over a dot will change its color.

Download it from my dropbox.

Dividing by Zero

Usually, dividing by zero is a problem.

Like most problems, it can be solved if you put your mind to it:  Start at the beginning and take it one step at a time.  Such is the beauty of mathematics:  If each step is correct, and each prior true, then the result is also true.

The definition of division is that it is the inverse of multiplication, so, to understand division, we must first study multiplication.  Multiplication may be represented as a function:

mult(x, y) ≡ x × y = z

This maps a two-dimensional domain onto a one-dimensional co-domain, causing degeneracy.  If we invert multiplication, this mapping is reversed, and each point of the inverse's one-dimensional domain maps to an at-least-one-dimensional subspace of its co-domain.

mult^-1(z) = {x, y} with x × y = z

For mult^-1 to be usable as a function, we must add a constraint, reducing the co-domain's dimensions by one.  This is why division has a second input:

div(z, y) ≡ z ÷ y ≡ mult^-1(z) with y constrained to the given value.
i.e. div(z, y) ≡ mult^-1(z) | y

However, if y = 0, then z = 0, independent of x, and the constraint fails to reduce the co-domain's dimensions.

In essence, the problem is that multiplication by zero causes information to be lost.  The salient solution is then to keep the information for as long as possible.

Because multiplication is associative, there is a simple methodology; simply remove the following axiom:

x × 0 = 0, for all x

Further investigation will need to be done to determine whether this solves all the problems (e.g. tan(π/2) = ?), whether this arithmetic is a useful abstraction of reality, and how it fits in with Aleph-null, Peano arithmetic, and other such mathematical concepts.

Space War: The New Frontier

Recently, I suddenly realized that creating a game similar to Spacewar, or rather Star Control, would be pretty simple in GameMaker Studio.

Unfortunately (wink), I discovered that it now has a built-in 2-D rigid-body physics engine.  Cue lots of experimentation:

 Fig 1: Plasma beam fired while spaceship is rotating.

Fig 2: Ship rotating because of recoil from firing mass driver.

 Fig 3: Experimenting with graphics effects.

Physics Trouble

As you might have noticed, I made some changes to the first post of my physics sequence, and although I had posted a second post, I removed it after a few days.

The reason is that I have been re-evaluating some of the decisions that I made, and doing lots of mathematics.  Pages and pages full of equations.  It's ridiculous, it's not even funny. ;^)

I have managed to write the potential-field function in matrix form, and this has shown me several further possibilities on how the physics engine can be used, and also some ways to optimize it and to adapt it to run on the GPU.  And, furthermore, it could run as a part of the graphics rendering pipeline without slowing it down.

So, my physics sequence is on hold until I have managed to organize my thoughts and tested them mathematically.  If you're getting bored, go play Path of Exile. :^J