Lander - Dev Blog 3 and a bit

So the last week or so of work has been in fits and starts, with RL interruptions and Easter holidays and all that jazz, but this is the first update with actual vehicles in the game! There's a set of different "tools" now which the player can scroll through (for digging, placing blocks, building vehicle parts, etc), I've been making more tweaks to the player movement and voxel loading, and you can place launch clamps and vehicle parts (just fuel tanks for the moment). So, without further ado, the summary screenshot:

The launch clamp serves several purposes - from the game's perspective, it's the join between the dynamic, mobile vehicle model and the static terrain, so I don't have to be constantly checking if the player's done something daft like removed the bottom part and left a vehicle floating in mid-air - or at least, there's only one place I have to check. It also gives somewhere for the player to move and rotate the vehicle while they're working on it, rather than pretend the player is some sort of superhuman that can lift and rotate spacecraft at will. Finally, any interface activities the player needs (like saving or loading vehicle designs) will happen through the launch clamp.

The next chunk of work is to develop the vehicle object so that it's more than just a set of parts - mechanically it needs to merge all the parts into a smaller set of render & collision meshes, add up all the fuel tanks, mass and engines so it can simulate the actual flight, and possibly track more complex details like which areas of the vehicle are air-tight.

Lander - Dev Blog 2.5

Alight, this is Friday's and Monday's update rolled in to one...

My original plan was to get planet terrain rendering out to the horizon (with a sort of adaptive scaling as you gain altitude, or move around the map) but for a plain, flat heightmap, and then get the vehicle building interface working over the weekend; but it ended up making more sense to work on the terrain generation so that it scaled both in first-person view, and also up to continents and land-masses. There's a bit of bodging in there to get it just right, but you can see that the local terrain's come out pretty nicely:

You can also see a Mercator projection of the planet map (about the size of Earth), so it's distorted around the poles but you can see the continents pretty clearly. That's one continuous scaled heightmap, so the current terrain is smack in the middle of that map.

Most of my weekend went into that, and a bunch of optimising the voxel generator so it loads the current scene (262,144 voxels) in ~0.36 seconds and ~7Mb, which is good enough for the load I'm putting on it right now. I'm partway done on the heightmesh - in theory, it's just a surface mesh heading out to the visible horizon, scaled so it fits into the camera's clipping planes and follows the same heightmap (at a lower resolution) as the voxel nodes - but I've a few ideas to try out for it, based around how to progressively load it into the scene as the player walks or flies around the map.

Objective for Wednesday, then, is the launch clamp - a special "voxel" which you attach to the ground, and onto which you build your vehicles.

Lander - Dev Blog 1

I'm actually in my fourth week of development on Lander (excluding a week's holiday), but 90% of the work done so far is reworking the 3D coordinate system to work on an interplanetary scale, so there's not been much by way of shareable images.

But no more! I'm finally getting stuck in to actual gameplay mechanics, and the basic voxel engine is working:

You can walk around the surface, pick up and put down blocks, and the whole thing is correctly positioned 6371km above the centre of a spinning (though presently invisible) planet that's whipping round a distant sun every 365.25 days (hence the shadows). You'd be surprised how complicated that last bit actually is (here's the Wikipedia summary).

I'm polishing the digging/inventory/placing mechanics tonight, then for Friday's feature I need to extend the terrain model out to the horizon - using voxel nodes (like the 10x10 square you can see) out to about 1km, then a height-mapped curvature mesh out to the visible horizon, in a way that will adapt as you fly into the upper atmosphere.

Patreon - Dev Notes, the First

So, for the past few weeks I've been working towards an inaugural game for the Patreon page I'm aiming to set up; it's one part demoing to patrons how much I can deliver in the 4-6 weeks I expect each game to take, and two parts showing myself how much I can get through in 4-6 weeks. The longest (unpaid) projects I've actually run to completion are 48hr game jams, and as those usually involve less than an hour's sleep a day, they're probably not the best yardstick...

The current project is nicknamed "Lander", having started as a remake of the classic Atari arcade game Lunar Lander and spiralled into the illegitimate lovechild of Minecraft and Kerbal Space Program.
Long story short, it's a sandbox game in which you build rockets, fly into space and explore some PCG planets; but unlike (for example) KSP, you do everything from a first-person perspective - the terrain is a big, voxelly map that you can rebuild into scaffolds and launch pads, and (if I hit enough milestones) convert into resources for building your rockets. I think the lack of central build & launch location (unless you make one), with the ability to build & rebuild vehicle wherever you are, should give this a very different atmosphere to some of the existing space flight simulators.

The plan is to get a workable feature finished every Monday, Wednesday & Friday (with corresponding blog update) to stop me getting lost down a rabbit-hole of quaternions like I have with Lander - anyhow, that's the quick intro, next up is the current progress report.

Ludum Dare 26

It was Ludum Dare 26 last week - wasn't terribly keen on the theme of "Minimalism", which seemed to push people in three directions - a literal interpretation, with minimalist art & music; token gestures, where they did whatever the hell they felt like and put "minimal" in the title; and abstract, where minimalism was a feature of the game setting - e.g. the villain you're fighting is a minimalist. Didn't see many where the theme inspired a novel game design; especially annoying is that they've already had this theme for a previous LD.

Anyhow, my offering can be found at http://www.ludumdare.com/compo/ludum-dare-26/?action=preview&uid=8404

I also wrote a quick post-mortem here http://www.ludumdare.com/compo/2013/04/29/ludum-dare-26-post-mortem/

Algorithm for Dividing a 2D Space into Convex Polygons

I'm writing this down mainly as an aide-mémoire, and because I can't find the solution online anywhere - I can't imagine it isn't out there, because I'm trying to solve a fairly basic problem, so I'm possibly using the wrong terminology in my search.

In any case, I have a simple engine for moving a player character round a 2D game map which is split into convex polygons/cells linked by portals/doors; I'm also working on a game that, in essence, allows a player to build and walk round their own spaceship. To fit these two together, I need an algorithm that will take the outline of an area of the ship (itself a convex polygon), a set of walls that the player has added (straight edges within that area) and divide the outline into a set of convex cells such that none overlap a wall, and that any edges between cells that are not walls are marked as portals between them.

My five-minute, scribbled on a PostIt note algorithm is:

• Every wall lies along a line that bisects the outline area into two parts. Filter out all walls that bisect the area such that any other wall overlaps both parts.
• For each remaining wall, select the set of walls that most evenly divide the other walls (from the full set) between the two parts.
• Pick a wall at random from that set and split the outline area into two new areas, adding portals along the dividing line where appropriate, and group the remaining walls from the full set into each area.
• Repeat this algorithm for both new areas with their reduced wall set.

Notes:

There are two special cases - where two walls are in line with each other, and two walls directly intersect. The latter case is probably easiest to prohibit, and the former case is handled by only including one of the two walls in the selection process, but remembering to include the second wall as a non-portal edge when splitting the area.

The Social Graph Pt3: Inversion of Control

(This post is part three of a series: here's part one & part two)

Okay, I've had my rant and ramble about the current situation with Web 2.0 social networks, what I think the Social Graph is and why I think the existing implementations don't match up to the reality; so now I'm going to propose my idea for where we should go next.

The core of this idea is that a social network is comprised of many different services, each of which is atomic¹ (though potentially inter-dependent). The central, quintessential service is the identity provider - a service that can vouch for you, presenting an online identity. When you use Sign In with Twitter or Facebook Connect, that's an identity provider in action.

An extension of the identity provider is the claims provider; this service handles the permissions that you give to the services you use. For example, a service may wish to send you notifications (via a notification service), but to do so it requires permission from you. So that it doesn't have to contact you every time to ask permission (which would just be ironic, given that it's asking permission to contact you in the first place) that service can contact the claims service and be issued a claim token (a digitally signed piece of data essentially saying "Service X may perform action Y") that it keeps hold of and presents to other services (like the notification service) to prove that you gave permission back when you registered. This is the same as the permission options that you get for Facebook apps, allowing an app to post on your timeline, send you emails, read your profile data, et cetera. In essence, the claims service controls which other services can perform tasks on your behalf or access your data.

This leads on to some of the other requisite services for a functional social network; you'll need a profile service that shares your personal information (given appropriate permissions, of course); a notification service that feeds information back to you via SMS, email or in-app notifications; a contacts services, which stores your list of friends, follows, "circles" and so on, acting as a claims service but for other identities, and as a routing map, saying who can see what parts of your profile, follow your feed or receive updates from you (storing the structures of the Social Graph); a feed/publishing service, that lets you share those statuses and updates; a photo-sharing/file-sharing service; a tagging service; and so on.

Of course, none of this is especially revolutionary, and already exists explicitly (as in Facebook) or implicitly (as in the ecosystem around Twitter). Where it gets interesting is when we consider the case of services interacting with each other in the abstract terms above.

Let's say I sign up to one of the newspaper apps that seem to have sprung up on Facebook recently. The app wants to know who I am, presumably to track my usage and which articles I read, so I type in my identity name (an example might be my email address, or my blog URL) then click the big sign-in button; it goes off to the identity server and verifies my identity (using an established process like OpenAuth or OpenID), then lets me in and I can go read articles. However, the newspaper app also wants to contact me; perhaps to let me know when new articles are published, or that someone has replied to a comment I posted. To do this, it needs to know how I want to be contacted; in this example, we're using the notification service which holds information about my contact details and preferences - the notification service I'm using (in this example) batches up my notifications and sends them in an hourly email. Someone else, using a different notification service, signs up to the newspaper app; they receive their notifications as SMSs. Both notification services implement a standard NotificationAPI v1.0, so all the newspaper app requires from me and the guy who prefers SMSs is the URL of our distinct notification services, and we then each get our customised notification behaviours. This is not unlike the drop-down in TweetDeck that allows me to pick which photo-sharing service I want to use (as mentioned back in part 2).

The downside to this approach is that every time I sign up to a new service or application, I have to configure it with all the different services in my customised social network that it happens to need; if it depends on a lot of services, this would be a nightmare. Equally, if I decide that actually, my notification service provider sucks and want to switch, I'd have to go round all my other services & reconfigure them. This leads, logically, to the need for a service provider service (mmm, metaservices) which keeps track of the different services that I use for different purposes. My identity service will likely know which service provider service (and claims provider service) I use, and all the other services I sign up to can then find out, via the identity service, which other service to use for each different purpose. In our newspaper app example, the app would contact my identity service to verify who I am & find out where my claims service & service provider service are; contact the claims provider to get permission to contact me; then contact the service provider service to find out which service to use for notifications. All of this happens entirely out of sight of the user, excepting the specific moments when user input is required - when the identity service needs the user to input their password, and the claims service checks with the user that the newspaper app is legit.

In a general sense, again, none of this is revolutionary. This pattern is already commonly used in software development - see dependency injection and inversion of control; and it's that latter concept that I think is so important. By controlling the injection of dependencies (e.g. providing your own choice of notification service) into the applications & services you're using, control of your social network switches from the service providers (Twitter, Facebook, Google, etc.) back to you. With interoperability via an open, published set of API standards, by returning control of each user's social networking platform to the user, it is possible to produce a free (or, at least, freer) market of services that users can combine to suit their needs and preferences; and diminish the barriers to data flow through the Social Graph.

There's plenty more detail to the design than that, of course; how different types of service can be described and denoted, how evolving standards (does your notification service support NotificationAPI v2.0?) are handled, how we bootstrap new users without presenting them with a hundred drop-downs (which notification service do you want? And your file-sharing service? And your URL shortener? Which flavour of sommelflange takes your fancy?), but I've covered the core of the concept. The next stage is to build a proof of concept, a small ecosystem of services from which you can devise your own social networking platform - another item for my long list of projects - so I'll update as that matures and hopefully have something to demonstrate as summer progresses. Feel free to get in touch if this sounds like something you'd like to help with, as there's plenty of work to do... ;-)

[1] Atomic in this sense meaning that a service is not coupled to or bundled with another service; and that it provides one (type of) service only. A service host might provide multiple services, but there's no requirement to use them all if you only need one. e.g. a photo-hosting service just hosts photos - it doesn't provide tagging, and a separate photo-tagging service is required for that.