Physics and many other things…

While I’ve been lazy and not bothered to blog about progress in the last month or so, that doesn’t mean I’ve not made a huge amount of progress since the last post. In fact, I’ve got way too much to write about so I’ll just give a brief run down then go into detail on one topic.

The last time I posted I had finished up with the rendering side of my Map Exporter and was able to output my map to a custom file format, however I could not yet load the map into the game. Since then a great deal has changed. First of all I got the map loading in place which surprisingly went smoothly first time. After map loading I started working on more basic functionality for the engine such as input and GUI rendering. With the help of a rather neat little tool called TexturePacker it was increadably easy to get a quick and easy to use GUI renderer with Texture Atlas functionality.

From here it made sense to start working on getting Entity management in. I’ve chosen to go for a “component” based system whereby an entity consists of multiple components. Each of these components descibe a single peice of functionality – Rendering, Movement, Health Management, etc – and allows for as little duplication of functionality as possible. For example it would be possible for all entities which can die to share the same Health Management component rather than having each Entity handle its own health.

In addition to this I’ve also added skybox functionality to the engine, lighting management and numerious performance improvements. After all this I proceeded onto the last task I’ve been working on, and the one I Intend to talk more in detail about: Physics.

Physics Engines are something I’m no stranger to, having based my honours project on the development and optimisation of one. Due to this i decided to build one from scratch rather than using an out of the box solution. The main reason for this was that I do not need a fully functional realistic physics engine, nor do i want the performance overhead that comes with one. I do however want some basic 2D physics, and an efficient system to handle it. This lead to the following specs for the engine:

• Accurite collision between circles and rectangles.
• Ability for complex objects to be built out of combinations of these shapes.
• Two different types of object: Static, which will never move or itself collide with other objects, but others CAN collide with it; and Dynamic, which can collide with anything and will inact a response.(Note: there is a potential third: a Trigger. This would be similar to a static object, however which a dynamic object collides with it, it would not bounce back.)
• Objects can be bundled into groups, and can choose which other group it can collide with. E.g. The players bullet can choose not to collide with the player, only enemies.
• A realist collision response, but with no rotational component for the sake of performance.
• Collision callbacks, so that objects can define their own response. E.g. A bullet killing an enemy.
• System wide point and directional forces for explosions, vortexes and “space winds” (for want of a better term :P).
• No runtime allocation of memory.
• And of cource, as efficient as possible.

All of this is now in place (with the exception of the Trigger object) and working well. Efficiency has been the focus of this and as such some corners have been cut. For example, a collision between a circle and a rectangle will only respond realistically if the center of the circle has not intersected the rectangle, instead it will only be a very rough approximate. Of course the system also does not handle the situation where an object has completely passed through another in the course of a frame, again becuase of performance… and also becuase I’m too lazy to implement that :P

In any physics system one of the main ways to increase efficiency is through coarse collision checks. Coarse collision is the process of ruling out objects which are clearly not in collision prior to performing a proper collision check on them. Obviously this greatly helps as if you have 1000 objects in the scene there would be 1 million collision checks without course collision. By ruling out all objects that are definately not in collision, this can be reduced to a tiny fraction of that.

I spent quite some time researching differing methods of course collision, considering Quadtrees, Binary Space Partioning and Spatial Hashing. I eventually decided on spatial hashing as this seems to me to be the best one for dynamic objects. Rebuilding of the trees each frame in the other methods simply sounded way too slow.

Spatial Hashing works by converting the positional data of an object into a linear table. This is acheived through a hashing function. A hashing function takes in data and converts to a a seemingly random ouput – however it only seems random, If you supply the same data you will always get the same output. What this means is that all objects which are in the same position (or rather the same cell in a 2D grid) will be placed into the same slot in the table. It can then be presumed that any objects which are NOT in the same slot are not in collision. The hashing function I’ve used is an integer hash called “FNV-1a” which is free to use and can be found here.

The use of spatial hashing (plus several other physics and rendering optimisations) has seen huge improvements in the number of objects that can be in a single scene. My test scene consists of roughly 3-400 Static objects. Prior to these optimisations I could have arround 80 dynamic objects at arround 15 FPS. Now with the same framerate i can have over 1 thousand! :D I also remain at a stable 30FPS up until arround 650 dynamic objects. This is fantastic as I had been aiming for 150-200 dynamic objects in any one level.

Anywho, this has been quite a wall of text so I’ll leave you with a screenshot! :-)