a lazy cowboy culls the herd

Late Sunday’s a good time for an update. For a while I wasn’t certain what the new game was going to do, but it’s back on track.

Despite my peon to symmetry, I’ve ditched the tumbleweed approach I mentioned a few posts back in favor of something more chaotic-looking. They’re still space weeds, but they’re arranged in clumps, like clouds, which grabs me better. Clouds were, in fact, the visual inspiration for the game–those “artist’s renderings” of life bobbing around the atmosphere of Jupiter.

That one’s from Carl Sagan’s Cosmos, a personal favorite. It looks nothing like what I’ve created but that’s just as well. Copyright, you see.

So, I have thousands of weed clumps to render. It’s early days, so the objects are just sitting around in a display list. At some point I’ll whip up an octree or something that might pass muster in a CS course, but for now, they’re fine. Of course, I can’t display all of them at once. Drawing objects is expensive. What to do?

Well, I can start by only drawing stuff that’s close by. That cuts down the number in a big way, as they’re distributed more or less at random through the map space. Now, instead of drawing thousands, I’m drawing hundreds. It runs, but it’s slow. What else?

How about only drawing the stuff that’s right in front of the camera? That’s called frustum culling and it’s a great way of cutting down on what you have to draw. I don’t have a native culling object in my toolbox. I was going to hack one together today, but I decided to try something else first. It worked so well I thought I’d share it.

It’s lazy frustum culling. It’s so lazy it doesn’t even use a frustum. Instead, we use a little vector trick. Geometrically speaking, weed clumps are just a center point plus a radius. For now, drop the radius and just worry about the center.

// iterate through all the clumps
for (i = 0, il = this.node.length; i < il; i++) {
	n = this.node[i];
	// dir is a scratch vector object
	// derive a vector from the camera to the center of the clump
	dir.copy(n.center).sub(camera.position);
	// if it's very close, just draw it
	if (dir.length() < 100) {
 		n.object.draw();
 	} else {
 		// normalize the vector
 		dir.norm();
 		// take dot product between camera's front vector
 		// and the vector to the clump. less than 1-half?
 		// draw it
 		if (dir.dot(camera.front) > 0.5) {
			n.object.draw();
		}
	}
}

The dot product between two vectors is the cosine of the angle between them, so it’s equal to 1 if they face the same way, -1 if they face in opposite directions, and 0 if they’re perpendicular. Using 0.5 gives us an angle of 60 degrees, which is close enough to the view angle I’m using on my camera. Any vector that produces a larger angle doesn’t get drawn.

It works just fine. One caveat: if the camera is “inside” the clump (distance is less than the clump radius) we just draw it without a look at the dot product. Otherwise, the clump will vanish as the camera spins, because the center point will rotate behind the camera.

Sure, it’s not a proper frustum cull, but it’s simple, easy, and fun. I couldn’t ask for a better waste of an afternoon.

who moved my cheese-y avatar?

My past games all used a first-person camera. For the next one, I’m using third person because I think it will help the player better understand who they are in the game world.

Yes, you’re a beach toy with wings. My apologies.

When I switched to the third person, the first thing I noticed was how jittery all the model motion became. I’d drag the mouse across the screen to change the yaw and all of my models would shake as if they were trying out a new dance step.

I traced the cause to how I was handling mouse events and camera rotation. My original first-person code established a mouse move event handler, which rotated the camera directly.

mouse: {
	x: 0,
	y: 0,
	down: false
},

onMouseMove: function(event) {
	var dx, dy;

	// if the left mouse button is down (i.e., mouse is dragging)
	if (mouse.down) {
		// generate mouse deltas
		dx = SPIN_RATE * (event.pageX - mouse.x);
		dy = SPIN_RATE * (event.pageY - mouse.y);
		// rotate camera yaw by dx and pitch by dy
		camera.turn(dx, dy);
	}
	// store off last mouse position
	mouse.x = event.pageX;
	mouse.y = event.pageY;
	return false;
}

Note that the degree of camera rotation is determined solely by the change in the mouse position. There’s no attempt to synchronize the rotation to the animation timings. This seemed to work okay in first person, but third person perspective reveals its flaws–very likely because now I have a fixed object sitting in front of the camera to compare the rest of the scene to.

The new code splits things up a little. Now, the mouse move handler only tracks changes to the mouse position.

mouse: {
	down: false,
	last: {
		x: 0,
		y: 0
	},
	next: {
		x: 0,
		y: 0
	}
},

onMouseMove: function(event) {
	// if left mouse button is down (i.e., mouse is dragging)
	if (mouse.down) {
		// store off "new" mouse position
		mouse.next.x = event.pageX;
		mouse.next.y = event.pageY;
	}
	return false;
}

In the player update function–which is called on every animation frame–I actually rotate the camera.

update: function() {
	var dt, dx, dy;

	// calculate number of seconds elapsed since last animation frame
	dt = SOAR.interval * 0.001;
	// calculate mouse deltas based on position AND time interval
	dx = 0.5 * dt * (mouse.next.x - mouse.last.x);
	dy = 0.5 * dt * (mouse.next.y - mouse.last.y);
	// rotate the camera
	camera.turn(dx, dy);
	// store off "new" position as "old" position
	mouse.last.x = mouse.next.x;
	mouse.last.y = mouse.next.y;

	... player position update ...

}

Camera rotation is much smoother. It’s still slightly clunky, as I’m computing deltas based on integer mouse positions rather than receiving them directly from the mouse driver. Hopefully, Mozilla’s Pointer Lock API will enter general usage before long.

how to thicken a tumbleweed (in space)

So, I’m working on a new game, and it takes place in an “open” world for a change. No more underground ruins, moon caves, or pastel factories for this cat.

We’re hanging some hundreds of kilometers above a gas giant world here. (Don’t worry, we can float.) To one side, we have a space tumbleweed.

I generate the weed using Brownian motion. I have a point and a direction vector. Inside a loop, I add the direction vector to the point, then apply a slight random error to the direction vector, and normalize it to keep the distance constant between iterations. I also constrain the point to remain within a spherical radius, and maintain a direction vector at right angles to the direction of motion. Some rough code is below.

// p is our point undergoing Brownian motion
var p = SOAR.vector.create(24, 0, 0);
// f is our direction vector
var f = SOAR.vector.create(0, 0, -1);
// r is a right-hand vector for generating the strip
var r = SOAR.vector.create(-1, 0, 0);
// d is a scratch vector
var d = SOAR.vector.create();

for (i = 0; i < 30000; i++) {

 	// this is a triangle strip, so generate two points on either side of the point
 	this.mesh.set(p.x - 0.05 * r.x, p.y - 0.05 * r.y, p.z - 0.05 * r.z, i % 2, 0);
 	this.mesh.set(p.x + 0.05 * r.x, p.y + 0.05 * r.y, p.z + 0.05 * r.z, i % 2, 1);

 	// move the point
 	p.x += f.x;
 	p.y += f.y;
 	p.z += f.z;

 	// add a random error to the direction
	f.x += 0.5 * (Math.random() - Math.random());
 	f.y += 0.5 * (Math.random() - Math.random());
 	f.z += 0.5 * (Math.random() - Math.random());
 	f.norm();

 	// add a smaller random error to the right angle vector
 	r.x += 0.01 * (Math.random() - Math.random());
 	r.y += 0.01 * (Math.random() - Math.random());
 	r.z += 0.01 * (Math.random() - Math.random());

 	// this is a trashy, hacky way of insuring that the
 	// right angle vector remains at right angles to the
 	// direction vector.
 	r.cross(f).cross(f).neg().norm();

 	// if the point strays outside the sphere, generate a vector
 	// that points back toward the center of the sphere, and add
 	// it to the direction vector. the point's path will gently
 	// curve back around.

 	if (p.length() > this.MAX_RADIUS) {
		d.copy(p).norm().neg().mul(0.5);
		f.add(d);
	}
}

However, if I draw the mesh, I get a rather anemic-looking thing.

Now, I could increase the number of iterations, and that’s what I tried at first, but it’s a problem for two reasons. First, I want to be able to generate this in real time when the game starts up, so too many iterations means the web page will be unresponsive for more than a few seconds. Not good. The second issue is the sheer size of the object in video memory. Running in a web browser is lovely, but it keeps me mindful of the fact that I’m sharing resources with loads of other programs. I want to keep GL objects as small as possible.

There’s also a slight aesthetic problem. It’s a random tangle of stuff. I’d prefer that it look more like a product of Nature and less like a discarded shoelace.

Enter symmetry. I generate my anemic tangle as specified, but at display time, I rotate the mesh through eight successive angles and draw each one.

// rotor is just a wrapper around a quaternion.
// see https://github.com/wordsaretoys/soar/blob/master/rotator.js
// and check out the freeRotor object
this.rotor.rotation.set(0, 0, 0, 1);
this.rotor.turn(0, 0, 0);

// SYMMETRY is set to 8
for (i = 0, r = SOAR.PIMUL2 / this.SYMMETRY; i < this.SYMMETRY; i++) {
	gl.uniformMatrix4fv(shader.rotations, false, this.rotor.matrix.rotations);
	this.mesh.draw();
	this.rotor.turn(0, r, 0);
}

The vertex shader only has to multiply one more matrix, and GPUs are great at that kind of stuff.

attribute vec3 position;
attribute vec2 texturec;

uniform mat4 projector;
uniform mat4 modelview;
uniform mat4 rotations;

varying vec2 uv;

void main(void) {
	gl_Position = projector * modelview * rotations * vec4(position, 1.0);
	uv = texturec;
}

Now, I have a thick tumbleweed. There’s a performance penalty, of course, but it doesn’t seem to have affected my frame rate. As a bonus, some lovely patterns arise from the chaos.

Symmetries occur all over the natural world, and they’re a useful way of giving the appearance of structure. (Not to mention the appearance of doing more work than you actually did.)

random thoughts on the last thing I did

Easy Does It either took two months or one to complete, depending on whether you count the time spent thumb-twiddling, waiting for an idea to take root. All I knew at the start was that it would take place in a cave (which was ultimately translated to “an underground ruin”). If you trawl through my blog archives you’ll also find a load of posts concerning googly-eyed NPCs called “paddlers” that never made it into the game. (Not this one, at least.) Some ideas take. Some don’t. I never know which is which until it’s all over.

Every time I had an idea, I drew up a design document for it. I found these useful, not as requirements or contracts, but as arguments. Poor arguments tended to vanish.

I wish I’d started writing the script earlier. I left it for the last week of development, and wound up with a set of one-liners that start repeating early on. Does it matter to the game? Possibly. If I’d started earlier, I could have given each ghost a history and a story to tell, or at least something original to say.

Originally, the game ended in one of three ways. You accumulated enough will to leave the ruins on your own, or enough luck to find some powerful artifact that Easy had missed, or enough money to set yourself up for a while. On the last day of development, I decided this didn’t really work for me, because it didn’t address Easy, and it seemed so oddly triumphant for a game that’s all about the little people of the RPG world. So, that’s why the ending is what it is.

easy does it

If you’ve ever wanted to spend some time creeping through a vast underground ruin in search of dead people to argue with, have I got a game for you.

I explained the general idea behind Easy Does It in the post just below this one, but to reiterate: the game was inspired by my Skyrim experience of running into ruins to kill people and take their treasure. I could just imagine them lying there dead wondering, what the hell was that all about? And I could just as easily imagine hiring some dope to come in after me and tidy the place up. You know, burn the bodies, clean up the broken furniture, make sure the ghosts (and their gods) don’t harbor any grudges.

You, my friend, may just be the dope hero I’ve been looking for.

Enjoy.