Luke Benstead is a senior developer at Potato, retro-gamer-holic and a keen creator of games; he is also the author of Beginning OpenGL Game Programming a book about using an API designed for rendering 2D and 3D graphics. Here, Luke shares his experience of creating a somewhat incidental physics engine
The task ahead
It may be hard to believe now, but there was a time when many of the big-name game engines — that are commonplace today — either didn’t support deploying to a web browser or were not as liberally-licensed as they are now.
Around that time, Potato was asked to build a 2D web-based platform game. As always, we got stuck into the task ahead, learned fast and came up with solutions.
One of the first tasks was to pick a platform for development. After much deliberation we settled on the HTML5 port of Cocos2D-x as the platform for development. It seemed to tick all the boxes and in no time we got a scene with some basic physics up-and-running. We were optimistic.
The game we were developing was essentially randomly-generated, so we first focused on getting the logic behind the level generation correct – an essential task. We used placeholder sprites – a kind of temporary visage – while we waited for the artists’ creative input, and then began placing them in the level using what eventually became a reasonably complex algorithm.
Hitting the limits
Then we got to work on building player and enemy controls, based on the physics of Sonic the Hedgehog, what better inspiration than the iconic SEGA character?
However, despite all of our inspiration and enthusiasm, something then went wrong - very wrong. After making the levels larger, our game became jumpy and unplayable and managed to draw only a handful of frames to the screen each second. It was a problem that needed solving, and quickly. So we analysed the performance data and quite quickly found the cause to be the Chipmunk-js physics engine. When we went to file an issue against the Chipmunk-js project in GitHub, we noticed a small caveat in the project’s “readme” file:
I haven't implemented chipmunk's spatial hash, and I have no intention to do so.
A spatial hash is a way of dividing up a large game scene into chunks so you only test for collisions between objects that are near to each other. If you don’t have a spatial hashing algorithm then each frame, every game object is checked if it’s overlapping with every other game object – even if they are not close together. That’s a very slow thing to do!
Finding a new solution
We then tried using matter.js, which at first seemed promising; but we soon had issues with the game objects moving erratically and it used a different coordinate system to Cocos2D-x, which required us to manipulate positions and rotations constantly. It just didn’t work out. Like all good developers, we took a step back, got our heads together, and looked for a new solution.
Build it better, it’s what we do after all
A key part of getting things right is figuring out — and it may sound obvious — precisely what you need, and in our case, the discussion focused on the game physics. What we needed, and indeed, what we didn't need. For example, we didn’t need the physics to be realistic; objects didn’t need to roll or gain their own momentum, we didn’t need realistic collision response (e.g. rebound), and we didn’t need realistic friction.
What we did need, however, was a way to detect if two objects were overlapping; to be able to find out how far away an object was from another (ray casting), and a way of manually applying forces to an object. And it had to be fast.
With that in mind, we decided to build our own collision system, so we started by focusing on the static objects such as the ground and power-ups etc. and left the dynamic ones, such as the player and enemies, to Chipmunk-js.
We first created a spatial-hashing system, using a great article on gamedev.net as inspiration, to create a system of “bounding-box” tests. Essentially each frame did the following: went through each static object in the game, found the nearest neighbours using the spatial hash, generated a bounding box for each to see if any neighbours overlap our object. If so, it fired a signal to let the rest of the game logic know.
At this point we knew if two objects were overlapping. We then needed “ray-casting”, which allows you to draw an imaginary line from a starting point in a particular direction, to find out if anything is there. If there is, a ray cast will tell you how far along the line the object was, and the exact point the line hit the object. It is great for keeping objects from sinking into the ground, for example. You can “cast” a ray downwards and be told how far away the floor is and if the floor is closer than it should be, you can then move the object upwards so the player perceives that the object is sitting on the floor.
The ray casting functionality basically consisted of calculating a box that would completely surround the ray (line); it used the spatial-hash to quickly find all objects within that box, tested each object to see if they intersect the line and sorted them by distance and returned the one closest to the start of the line.
For a while we left things there. We could maintain two “rigid bodies” for the player and enemies (one for Chipmunk-js, one for our physics engine) and left Chipmunk to perform all the dynamic physics, while our “Potato Physics” managed all the static ones.
After a while, it was clear that even using Chipmunk for the dynamic physics was causing a slow-down so we finally took the plunge and added support for applying forces to our objects and ultimately dropped Chipmunk-js entirely.
Finally, we had high frame rates, which was a huge relief.
So close: perseverance pays off
Our homebrew physics engine increased the frame rates to a smooth 60 frames-per-second... well, most of the time.
The solution to the problem was try to allocate a bunch of memory at the start of the game, and then keep hold of it throughout the game rather than allocating memory at each frame. It is tricky to do, but eventually we reduced the garbage collection times enough so that the game remained smooth throughout.
Has anything changed?
If this situation arose today there may be other options. Unity, for example, is free to use and deploys to the Web. Even then, using a realistic physics engine for something non-realistic can be complicated or unstable, so many games build their own specific physics engine for exactly the reasons we did. So it seems as though rolling your own can sometimes be the right thing to do!
Follow Luke Benstead on Twitter