Topia: Landscape Finger Painting and Collision Hell

Since the day we started on Topia, for Josh it's all been about painting the landscape with your finger. For me it's been about other things like the pseudo-spherical tech, playing with shaders and getting as many NCPs moving as I possibly could.

I've been working on Topia for several months and each time I make a version available with a new feature I can judge how cool Josh really thinks it is by how long it takes him to ask when the landscape painting is going in. Anything over 30 seconds means he must be impressed...

Last week Josh's nagging got to the point where I decided to actually try to get it working. I'd been putting it off for several reasons. some of these reasons were valid, there were more important features for those early demos but it was also, if I'm honest, because I was slightly scared of the maths. The problem is, the world in Topia isn't actually a sphere, it's an Alan Wright pseudosphere: A simple repeating square 2D world draped over a quadratic bump. Basically Z=-(X*X+Y*Y)*0.005.

This creates a fairly convincing globe while being almost as easy to work with as a flat surface as most of the work turning it into a 'sphere' is done in the vertex shader. The downside is that it's a total nightmare to cast a ray into for collision purposes and of course that is exactly what's needed if you want to convert a 2D screen touch coordinate into a 3D world position in unwarped space.

Basically a point on the screen is a line in 3D space. For a normal, sensible, unwarped world you would simply need to figure out the point where the red ray from the eye intersects the landscape:

With Topia's curve I needed to calculate it for this:

But the problem was, my world is stored in non-curved space so I effectively needed to cast a curved ray into the landscape like this:

which was obviously going to be a nightmare. I spent a few days trying to work the maths backwards, cursing Josh under my breath to myself. I even tried to talk him out of the need for direct landscape painting alltogether.

Eventually I got so desperate that I started explaining the problem to anyone who would listen, even those with no real understanding of the maths or programming until I heard myself saying to my girlfriend "All I have so far is a row of dots which represents the shadow of the ray projected onto the ground"and then it stuck me, all I had to do was warp the ray though the same maths the shader used and I could effectively cast the curved ray into the flat world. Iterating along it I could, in maybe 20 lines of code, compare the height of the point on the curved ray with the height of the 'shadow' beneath it and home in on an extremely accurate 3D position for the collision. This isn't rocket science, I was actually a bit of a dick for not spotting this simple solution months ago but in hour later it was working and a few hours after that, I'd tied it to some pretty simple code for placing bumps in the landscape:

The new painting thing works incredibly well. If you hand the game too a small child they tend to try to drown all the animals by removing all of the land and refuse to hand the iPad back. It gets a fairly similar reaction from a group of half drunk game developers in the pub.

'AI' and Moore's Law: What happened?

My phone is well over fifty times faster than The STs and Amigas I started coding games for, the iPad2, faster still. Back at Bullfrog we made four games on those old ~8Mhz machines with several hundred NCPs, all 'doing their own thing'. They were of course just drawn with sprites and the 'AI' was just a few hundred lines of assembler or painstakingly optimised C, which can be pretty much the same thing if you're obsessive enough about looking at compiler output.

With a few notable exceptions, none of which I've played as they all look a little to fiddly to be my idea of fun, the number of NCPs just hasn't gone up like Moore's law says it might have. There are several possible reasons for this:

1. People like to see extra processing power spent on more realistic models, proper physics etc.
2. 10x the NCPs can require far more than a 10x speed increase: 100x100 = 10,000, 1000x1000 = 1,000,000 so could require a 100x speed increase.
3. Over the last 20 years, vast amounts of that extra processing power have been pissed away on heavyweight C++ or, worse still, scripting languages.

Right or wrong we're pretty much ignoring all of these with Topia because we believe:

1. If they are small enough on screen, characters don't need to be high-poly models. Physics doesn't need to be via a completely realistic, generalised system if your game doesn't require it.
2. There are ways round the ' N squared' problem, pretty oldschool ways but they still work. There are almost certainly trendy new ways too but I'm not the sort of programmer...
3. It's still possible, even in C++, to write this stuff in an optimal way if you resist the temptation to use all of it's cool features. That said, it could all be done in a higher level language on a bigger machine but we're aiming at phones and tablets here.

So Topia is a weird mix of old and new coding styles and, because of this, is doing a pretty good job of supporting several thousand NCPs, even on the iPhone 3gs.

Right now I'm in the middle of a rewrite of collision and physics systems that means everything can now react to everything else. The herd movement is a hell of a lot cooler than the last video, herds now flow around trees and scatter for predators. Video coming soon but here is a screen grab from earlier today: