a technical blog

Archive for the ‘Uncategorized’ Category

7DFPS – Day 3: Collision Detection/Response

leave a comment »

Today I focused on getting a simple physics simulation running. The main work consisted of creating a collision detection system based on the BSP tree. I went for the well described approach from this thesis I have been using previously. I have to say that I don’t like the result yet. There are occasional slips where it seems to miss a polygon. Also slopes and stairs I did not care for yet. Jumping around the world is good enough for now. If I have time, I might go for this more solid “sweep”-based approach.

I also today implemented the split-plane algorithm/metric for the BSP tree generation. It is a very hard problem (actually it is NP-hard :-)) to find a good metric for the tree to be balanced and with minimal number of polygon splits. Currently, some rooms are completly covered in one convex leaf of the tree, but others are split because the algorithm sometimes has to favor a balanced split. I might try on improving the algorithm and add some additional weight if a split produces a convex subregion. This should then cater for all simple convex room to end up in their own leaf.

Here a screenshot of a room in the world, were each color represent one leaf in the BSP. Note how the whole room, because it’s convex, has ended up in a single leaf.


Oh; and I started on the portalizing of the world for the culling algorithm. I am not sure yet if I will be precalculation potential visibility sets on the BSP leafs or just portal-frustum-clipping approach during runtime. Even though I have a powerful laptop, I am always suprised how high the fillrate of modern graphics cards is. I am rendering thousands of polygons and don’t see any performance penalty yet. Ok, I don’t have any complex fragment shaders (using fixed-function pipeline API currently), but anyway…

Written by 38leinad

August 12, 2013 at 10:02 pm

Posted in Uncategorized

7DFPS – Day 2 – Binary Space Partition

leave a comment »

After all the coding for Day 1 i actually was a little exhausted and my brain still needed to digest some of the reading. So, I started the day of with a nice bicycle ride. That actually helped a lot. I had my moment of zen regarding Binary Space Partition on the bike: I think now i get how it will later help me for the static visibility calculations; i.e. Potential Visible Sets.

Anyway; the day again consisted of a lot of reading:

  • BSP Tree generation and how it can be used for visibility calculations, lighting and physics is really nicely described in this thesis. At the moment it is my main source of information on BSP and even though it is mentioned nowhere, I cannot help but wonder how closely the concepts are to what quake is using. But no mention whatsoever…
  • Some tips on BSP tree details are described in this rather simple txt file.
  • And before I forget it: My first introduction to BSP tree was from Michael Abrash’s Graphics Programming Black-book. It describes the concepts in 2d, but the above mentioned paper gives the full details on how to do it in 3D with all the necessary operations on Points, Planes and Polygons to actually classify faces and cut up the world.

My first result of a BSPed world that actually looked like this:


Turning of the z-Buffer, it actually rendered the world correctly in back to front order. Reason enough the algorithm is correct. But obviously, the world was partitioned to much. All the detail architecture like stairs and boxes contributed to the world partition. Which is not what e.g. Quake 2 is doing. There is a distinction between structural and detail architecture. The BSP is generated from the structural architecture alone and then the detail architecture is justed pushed into the leaves of the BSP tree. If the choice of the split planes is good, the partitions of the world should end up in almost each convex room of the world ending up in a leave of its own.

The main problem I found out that the map editor Trenchbroom is for Quake 1 and it did not seem to have supported detailed brushes yet. So, no way to set this property. Also I was already thinking about texturing the world; and as all the map editors are inherently tied to id softwares WAD file format, I decided to switch to Blender for modelling the map. There already exists an export plugin to the .map file format and some great introductions in how to use Blender for modelling levels for this format. Check here and here.

The Blender export plugin actually also did not support detailed brushes but I knew enough about the python API to add this feature. Here a better split:

bsp_detailYou can see in the screenshot that the room is still unnecessary split. That’s because my split plane algorithm is rather naive and just takes a random face/plane.

What I still wanted to do but will push until tomorrow is the algorithm and the metric for choosing a good splitting plane in the BSP creation and visualization of the AABBs of the BSP tree leaves for debugging purposes. As all that will come next relies heavily on the BSP, this might be a helpful debugging tool…

After that, tomorrow consists of collision detection and simple physics or the visibility/PVS algorithm.

Written by 38leinad

August 11, 2013 at 8:54 pm

Posted in Uncategorized

7DFPS – Day 1 – Constructive Solid Geometry

leave a comment »

csgI decided yesterday to finally participate in a game jam again. Not just for one/two days but the 7DFPS which lasts a whole week. I am no big fan of the First Person Shooter genre from a gameplay perspective but highly interested in the technologies used to make this visual worlds possible. With id Software’s John Carmack as one of the celeberties in the field and pusing the technologie for the past 20 years, I decided on challenging myself to have a deeper look at some of the concepts that make up the quake engine. Used by a hugh number of successfull games. Starting with id software’s in-house titles Quake 1 to 3. I will take this as a learning experience and not so much as a task to create a playable game at the end of the week. In case it will happen, I won’t be disappointed though…

The core idea behind the quake engine family (id tech 1 to 3; used in Quake 1 to Quake 3) seems to have stayed quiet constant. Mainly: Using Binary-Space-Partition (BSP) and Constructive Solid Geometry (CSG) to create the game world and define solid and empty space of the world. Querying the world database for visibility calculations, lighting calculations and physics is done via the BSP tree structure. The BSP tree itself and visibility (Potential Visibility Sets are built and attached to the BSP) and lighting (shadows/lights are baked into static textures that during runtime then just blended with the standard diffuse textures of the world) are calculated as am expensive prepossessing step. During runtime of the game, the BSP is then used mainly for rendering, physics, dynamic light calculations.

You can get a light introduction to the core engine from Fabian Sanglard’s great source code reviews of Quake 1, Quake 2 and Quake 3. I did so again to refresh my understanding.

From there, the first day mainly consisted of reading articles and papers on the core technologies used by quake’s graphics engine; Binary-Space-Partition Trees (BSP Trees) and Constructive Solid Geometry:

To be able to build a BSP of the world, all the individual solid entities the world is made up of (lots of blocks) have to be merged via a CSG Union operation. This will lead to a set of solid and closed surfaces. No two polygons/faces intersect each other. I read up on some CSG approaches over at flipcode. From there, the Laidlaw paper on CSG is a good next step as it seems like this was also the main approach used within quake’s CSG tools.

From there, I started to get more practical: Let’s try to create a simple world, load it, CSG it and BSP it. Obviously, I needed a fast way to create this world, define some export format and load it. As I am on the track of Quake, I decided to use the .map file-format that is also used by all the level editors for the quake engine family. Trenchbroom was the editor of choice because it runs on windows and Mac OS. For the .map file-format itself there is a great article available describing not only the structure but also some alternative approaches for the polygon-creation and the CSG process.

I also tried to read the QBSP tool (which is part of the quake-engine’s asset creation pipeline; i.e. loaded a .map file and does the CSG, BSP, Visibility, Lighting etc) to get some help on implementing the CSG algorithm. It is really hard to read code with alot of shared state and confusing names. Fabian Sanglard’s commented repository clone helps a little to understand the interwoven codebase.

So what’s did I do expect reading? I implemented the loading of the .map file (Java + LWJGL) and that’s the result of today (as you can see in the screen shot in the top-right): A loaded .map file, CSG’ed and rendered. The colored faces show nicely how the actual source polygons for the walls and floors have been slip up into smaller regios to have one closed surface for the whole room.

Tomorrow comes the BSP.

Written by 38leinad

August 10, 2013 at 5:06 pm

Posted in Uncategorized

HTML5 Game Development

with one comment

20130226_233917After 2012 being “the year of the cloud”, HTML5 is currently catching up to be the new buzzword of what “we need to have in our application”. So, at work I have been doing a lot of research on technologies revolving around HTML5 and JavaScript. In my industry sector most HTML/JavaScript developers still code in a procedural fashion, produce interwoven JavaScript and HTML-code and use alert for debugging. I am finger pointing at myself here too. While doing research though, I have become a big fan of JavaScript for it’s good parts. Functions as first-class objects and closures to only name two. Also, frameworks like angular.js teach you to code in a very structure fashion that has been common at the server-side for years, but now is also finding it’s way into the browser (the buzzword is dependency-injection).

For my game development hobby projects I have been using Java for most things (libGdx is great for android). It is a great language with amazing tooling/IDEs (eclipse, IntelliJ). I espacially like hot code-replacement. Espacially in a run-loop of a game this can be very handy to do rapid development and immeditely see your changes take effect. It might not be on the level of what Bret Victor envisions, but it is a first step.

Anyway, I have been wanting to try out WebGL for a long time now; last time, after finding this WebGL port of one my favorite rendering engines. The context at work now gave me enough of an understanding for the surrounding technologies to actually try it for one of my game projects. I was hoping to directly jump into the actual game content and not have to learn a new language and environment from the ground up. And it actually worked out quiet fine.

Also, I wanted to go in the direction of using the web for future games anyway; the burden to start a browser game is much lower then to either download and start a game or even run a Java-applet based game in the browser. This can be crucial for a high exposure rate of your game during a game competition like the Ludum Dare.

I decided to join the “One game a month” initiative (#1GAM) and make a February game based on HTML5 technologies. The result is a simple retro-style jump-and-run ala Commander Keen and named “Agent 386”. You can find it here.

What technologies have I been using and what are some of the take-aways?


  • On the one hand JavaScript is missing the classical inheritance model in an easily useable fashion and instead exposes a prototypical inheritance model, it is so powerful, that you can define the classical model yourself. I picked up the proposal by John Resig and basically copied the code over in my project. Voila: Classical Inheritance with “extends” and super-calls. This somehow reminds me of the amazing strength of Lisp; …just that it is actually widely used outside of academia.
  • I have become to learn that for me the function-scope of local variables (instead of proper block-scope) paired with closures is a really huge stepping stone and one of the baddest parts of Javascript. I have been making this mistake over and over again and really dislike the omnipresent “var self = this” solution.
  • WebGL is just great! Instead of having to write a lot of boilerplate code just to get one triangle on the screen, in WebGL it is just so easy: Create a canvas, get it’s 3D-content and you are ready. Also the code to load a shader is quiet straight-forward if you include the shader-code in a script-block in the HTML page. As WebGL, just like OpenGL ES 2.0, does not come with a matrix stack, the glMatrix library is indispensable.
  • WebAudio I only got working in Chrome as it seems Firefox does not support it yet; nevertheless, in Chrome it is working great (I first had some issues with the sound beeing distored but it went away and never came back) and you can easily load and play an Ogg-Vorbis encoded audio-file in a few lines of code. Wait until Firefox fully supports it and over are the days of flash. Well, the days of flash are already counted but a flash-based sound plugin was one of the last useful applications I could think of.
  • The LocalStorage API is great for storing save-games and high scores.
  • Now comes the greatest part: Gamepad API! I bought an XBox 360 game controller (the “for Windows”-version) and hocked it up to my macmini (see this controller driver to get it running). I have the mac connected to my TV running mainly XBMC as an entertainment system. But, it also has chrome on it. Perfect place to try out my jump-and-run and actual enjoy a few entertaining minutes in front of the TV (german TV is crap; I usually try not to turn on the TV; except for listening to some music television). It worked like a charm; and I imagine there is a huge potential and market for casual browser-based games in the living room. Playstation 4 has already blown it (what indie game developer can afford to publish a game on that platform?) and Microsoft might do as well with the XBox, but there still could be a new gold-rush for indies and gaming in the living room. Apple TV might be the winner here just as on the mobile market (100$ annual developer subscription and  a 70/30 revenue share; that was needed to start the gold rush and is all that’s needed now). But I digress…
  • Require.js: I have started to do some experimenting with it at work and liked to not have all my scripts/classes in the global scope and be a little more structured. No long lists of script-tags in your HTML-file. Instead, state the dependencies of each JavaScript file locally and let require.js take care of resolving the dependencies. Kind of like imports in Java and includes in C; even more. I was hoping that the require-calls will also function as an easy visual clue for the dependencies each of my JavaScript classes has. But, due to the dynamic typing it happens to be that a lot of classes might not be listed as a “require”. I.e. types of function parameters that flow into my methods don’t need to be listed; only if I instantiate a type or reference static attributes, I have to include a require-call. Actually the problem is no real problem as it is part of the nature of JavaScript; but I took it as a point anyway because by this require.js basically fails to be useful in a game project of the scale I am using. Async script loading is nice but rarely needed. Just list all your scripts and let them get loaded in the beginning and you don’t have to care about script loading anymore. And managing the dependency-graph manually is also doable if you have a good architecture. It works for Quake as well…
  • Zepto.js: JQuery is a quiet heavy and big framework but without discussion it is indispensable in almost any web application. Just for the simple DOM-manipulates of a WebGL game, this might be overkill. Creating or querying a canvas (and loading the shaders from script tags) is no reason to include JQuery. Zepto.js is an implementation of the JQuery API without all the legacy browser support et al. Making it lightweight and a reasonable include.
  • Duck-typing: This is one thing of Javascript I really started to appreciate. I have never been doing a one-man game-project in a scripting language before so this might be obvious to scripting language users in general, but duck-typing is just great. I can define a function “distance(a,b)” do calculate the distance of two points and all “a” and “b” need to define is parameters “x,y,z”. The type is irrelevant. I can calculate the distance between the player and some other game object with having an explicit Vec3 type or similar; which I find overkill in smaller projects. Especially in a game jam.

IDE, Browser, Runtime, etc..

  • I have a license for the Webstorm IDE at work. So, I naturally chose to use it for my game as well. It has a great debugger integration. And setting breakpoints in your code is a big plus. I don’t want to do this in the debugging panel of Chrome. But the missing hot code replacement is really a disadvantage. For developing with angular.js et al WebStorm comes with a great Chrome plugin to do immediately swap in  code changes in the browser. I think it is similar to a page refresh with a little bit of additional stardust; because of that is is useless for me in a WebGL context. Make a code-change and basically the game is reloaded. Maybe I am also missing something; because I have been reading that you CAN do hot code-replacement in Chrome if you change your files directly in the Chrome Developer panel (“does the WebStorm plugin maybe work in a similar fashion?”, I am just now thinking…) but it did not work for me. I think I will be trying Sublime text 2 for my next project as the lightweight feeling and responsiveness might make up for the non-present debugger integration.
  • I have used Chrome for the most part of development. And I only started to test in Firefox and Safari when I was already well into the development and almost 50% finished. I was surprised that the game immediately ran in both browsers without needing to do any modifications. Firefox without sound (I coded the access to WebAudio defensively as it is the one HTML5 API that the game does not have to rely on to function) but still impressive. I tested it quickly in Chrome on my android phone and it did not work out of the box. But I also did not really care as i don’t like the feel of Jump-and-Run games on a touch-screen. The game controller with haptic feedback is the homezone of these kind of games. Disabling cross-site scripting checks in the browser (–disable-web-security for Chrome) was also a big plus for loading config files and resources via Ajax and not needing a webserver for the development.

My takeaway from this journey is that I will stick with HTML5 for future projects. It has all that’s needed in a nice sandbox and the runtime environment  is omnipresent environment (the browser). Everybody has a browser everywhere and can enjoy a casual game. Let’s wait for Apple-TV and Steam Box and we will have the living room gold rush; and HTML5 taking a front seat!

I also have my asset-creation and development toolchain set up and ready for bigger projects now. As I wanted to learn, I did not go for Impact.js as the game library but created the framework from scratch and myself. Sprite-creation, spritesheet conversion, audio-file conversion to ogg, etc are set up in a make-based automated process. So, compilation of all the assets, obfuscation/minification of the code and deployment to the web-server is only one “make deploy” command. For the first time I have been trying to rely on a lot of good tools that already exist instead of doing everying myself. The tools I used for Agent 386 are:

  • Tiled for creating the tile-based levels (before, it was usually Paint.NET; just “draw” a map into a PNG)
  • TexturePacker for creating spritesheets (commandline interface included!)
  • ASEprite aside of Paint.NET for the actual creation of animated sprites (it helps to see the animation immediately instead of starting up the game and checking there)
  • oggenc for converting WAV files to Ogg Vorbis
  • Bfxr for sounds

The only thing left for me to say: Try out WebGL for game development and if you are in the mood, check out Agent 386 on your big-screen TV with gamepad and enjoy. For me it was certainly an interesting journey and with only 3 weekends of almost full-nighters, I am proud to have been able to get something finished.

Written by 38leinad

February 28, 2013 at 11:42 pm

Posted in Uncategorized


with one comment

It has been a long time since my last post. From a technical side, I have been involved a lot in researching on computer graphics and game development. Since participating in the last Ludum Dare with Shit it’s evolving I have regained my old interest from university in doing computer graphics. For this, I have been reading an implementing a lot. During the Ludum Dare I have been playing with a raycasting-based software renderer ala Wolfenstein 3D. The next step was to actually implement a full 3D renderer in software. I have mainly taken the legacy fixed-function pipeline OpenGL API and implemented the rendering underneath in software. Implementing perspective projection, clipping in homogeneous coordinates and the actual scan-conversion of the polygons all by hand, helped a lot to gain a deeper understanding of the pipeline. I will write about this in a separate post once I have time.  Just as a quick hint if you want to to something similar. This book is the holy grail!

It might not look like it, but trust me: it is pure gold!

Next to that I have been reading a lot of Id software source code. I think it cannot be appreciated enough that they put this stuff up on github for everyone to play with. My main focus was on the Quake 1 sources. In combination with Fabien Sanglard’s source code review and Michael Abrash’s Graphics programming black book (available for free online) which contains some chapter on core Quake engine topics, it was a surprisingly easy read.

After working on all of these topics, I decided to get my Ludum Dare entry on the Anroid PlayStore. After doing a first port of the game to android, I quickly noticed that software rendering is to much of a burden on the CPU of a mobile device and I would need to leverage the GPU. At that point I basically threw away all I had and completely implemented the engine using OpenGL ES and libgdx (really nice framework that allows to develop android games on the desktop for the most part without actually touching a device or simulator). As everything is new and looks now much more polished now, I decided on a new title and will try to make my first steps as an indie game developer with it. It is called Boskovice and the landing page with the current progress can be found here. I plan to make to make it into a casual first person shooter for the android platform with a strong retro-feel. Even though I hate most of today’s games (haven’t played a triple-A game title in 5 years) I still like to play the old Id Software, 3D Realms and Apogee titles. This is the feel I am aiming for. Let’s see how it turns out.

If you like the idea of a casual retro-style first person shooter for android let me know in the comments. I will also be looking out for beta-testers shortly. So, if you are interested, post in the comments or hit me on twitter.

Written by 38leinad

November 19, 2012 at 9:27 pm

Posted in android, graphics, opengl, Uncategorized

Tagged with

Writing to a Windows File Share for iOS

with 3 comments

Just also added writing to the tango API as it is quiet analogeous to reading once you get what the different parameters mean… find it on github.

Please not that I am not keeping the Objective-C API up to date (was only for testing) as well as the Test-App. If you want to use tango in your app, please use the C-based API; a stable Objective-C API might come later, but is not available at present!

Written by 38leinad

March 23, 2011 at 6:11 pm

Posted in ios, library/framework, Uncategorized

Tagged with , , ,

Reading files from a Windows Share for iOS

leave a comment »

Used the last few evenings to finally get the reading of files on a Windows File Share running for iOS. It is part of my lightweight SMB library called tango and can be found on github. Feel free to use it in your own iOS projects.

As a side-node: The main API is C-based and the Objective-C API was only written in a hurry for testing. So, you might want to write your own Objective-C wrapper around the C-API to be on the save side… 🙂

Maybe I will use the next weekend to get also the writing of files running…

Written by 38leinad

March 23, 2011 at 6:11 pm

Posted in ios, library/framework, Uncategorized

Tagged with , , ,