A few of my tutorials are posted on external websites, one of those website is www.sgtconker.com which was managed by @Conkerjo unfortunately updates were stagnating because the work pressure Conkerjo was under so the website is now under new management. ‘Mad Ninja Skillz’ the developer behind EZMuze has taken over management. To reflect this the website has been renamed MadGameDev.com. So… what does this mean for you?
Well unfortunately they are having problems forwarding the visitors from sgtconker.com to madgamedev.com so any links on this blog that link to articles and files on sgtconker.com are currently broken. However all the articles are there and available at madgamedev.com. If they can’t get the forwarding issue fixed within a week or so I’ll go through all the articles and fix the links myself, but since that would involve skimming through all links in 120 posts I’ll wait a bit to see if the situation will resolve itself.
Today I finally finished my thesis. It’s topic was to count the number of upper sets in partially ordered sets Which is quite a hard problem since it’s in the complexity class #P-Complete (that’s the class of counting the solutions to the decision problems in NP-complete). All and all I’m quite pleased with the result. Although the upper bound is still , (can’t quite get under there without solving P=NP and winning a million dollars) I’ve manged to find a solution that has a best case of both in time and memory complexity. With a particularly large data set the brute-force algorithm took over 2 hours to complete while my algorithm took 0.025 seconds. Now that’s what I’d call a speed gain (and yes it was a real life data set, no tricks here). You can see this for yourself in the graph at the bottom of this post the ‘naïeve algoritme’ is the brute force approach, the ‘Familiealgoritme zonder uptrie’ is the first version of my algorithm, the ‘Familiealgoritme met uptrie’ is the final version of my algorithm. It uses a trie like data structure to speed up searching and uses a lot less memory. Note that the graph has a logarithmic scale.
Unfortunately for most readers my thesis is in Dutch, but I’ve translated the abstract to English:
Counting the number of upper sets in partially ordered sets gives us a unique number that can be used to compare sets. This number is like the fingerprint of a set. Until now there isn’t, as to my knowledge, an efficient algorithm to calculate this number. This meant that the number had to be calculated either by hand or by using a brute force approach. Using a brute force approach leads quickly to problems, even for trivially small data sets since this means that you have to generate 2^n subsets and check each of these subsets on upwards closure. When calculating by hand you can use symmetry but this menial process can take a lot of time and is error prone. In this thesis I present an algorithm that can calculate exact, and usually fast, the number of upper sets in a partially ordered set.
You can download my thesis here: Upper sets in partially ordered sets (Bsc thesis Roy Triesscheijn) as I’ve said before the text is in Dutch, but the proofs and attached code should be readable enough. If you’ve got any questions feel free to ask below!
A scripting engine is a useful component in any game-engine. It allows you to execute modified code (aka scripts) in real time while your game is running. This gives you immediate feedback, allows for easy debugging of scripts and gives you true rapid prototyping abilities.
Scripting engines are also easier to work with than a full blown programming language, an error in a script is easy to recover from and because the scripts aren’t compiled it’s easy for the script interpreter to give helpful debug information. Even better: you don’t have to compile the script and the game keeps running so immediately after you fix the bug in your script you can see the result.
Script engines gives opportunities for ‘other’-programmers (gameplay, leveldesign, animator, etc..), they might not wish to delve into the intricacies of the programming language and frameworks you’re using for the game engine but they will be more than willing to write some script to modify the behavior of that new enemy.
All the wrapping and magic happens in the JintXNA project. The code, as it is now, works fine on Windows but Windows Phone and Xbox 360 support isn’t there yet out of the box since JINT is targeted at the full .NET 4.0 framework. However there is a port of JINT which targets the .NET Compact Framework which should run on WP7 and the 360, I haven’t tried this yet though.
You can download the full source code of JintXNA here this package includes the JintXNA project, the IDE and a sample project and script as seen in the video.
Nathan Bixel has written a short guide on how to add your models to Catalin Zima’s deferred rendering engine (my XNA 4 port is located here). You can see his manual in this thread on the XNA Game Programming Adventures website. In case it goes down, I’ve also made a small PDF print of it:
Thanks Natah! It’s wonderful to see other people helping to make this content more accessible.
Anyway the tutorial is posted here.
The end result:
Recently I’ve been quite busy working on my thesis (which is coming around nicely) and with a lot of work related things. For a temporary exhibition we where working on implementing Mimbo, this cute robot we found on mashable there was only one problem. It requires an iPhone, which is quite hard to secure in an unsupervised exhibition, and all our systems are Windows based. So we came up with using an iPad (larger, so more fun to look at) and an iMac to control it, but this would require securing a blu-tooth connection, and all sorts of problems. So the last few days I’ve been working on re-creating Mimbo in my spare time. This proved to be easier than I thought, using the excellent Luxand API which I just happened to come across. So after a bit of C# code to interpret the data, and some WPF to make a cool robot face this is the end result:
Man it’s fun to step out of your comfort zone sometimes and do something completely different. Well anyway, I might release all the code as open-source, under the MIT license or something, but since I can technically use this at work I’ll have to sort out what happens with it there first.
I hope the next time between posts isn’t so long and that I can finally create some time to post the tutorials ideas I’ve been having, but it’s crazy busy lately.
Edit: after popular request: here is the source code
I always feel kind of obliged to make at least a post a month here, unfortunately I wasn’t able to post anything useful since the end of September (shame on me). Actually I haven’t been doing much programming at all lately. My main focus now is finishing up my Bsc in Computing Science, just one more course to go and of course the dreaded thesis. To everyone’s surprise, including mine, I will be doing a thesis about a topic picked by one of my professors who specializes in “intuitionistic propositional logic”. Hell I don’t even know what that means. Luckily for me I’ll be only dealing with a small sub-problem related to calculating the number of ‘upwards closed subsets’ (I’m not sure if this direct translation from Dutch to English makes any sense academically). Anyway it will mean I can visualize and think a lot of lattices.
So back to that tutorials thing that should be going on here. Don’t worry I’m not stopping or even formally postponing anything. I even have a few code files and some word documents laying around about adding ways to tint models programmatically so that you can give models more diverse looks without much more work. However I can’t promise when I get around to publishing it, hell I’ve got a new computer and it hasn’t even got XNA on it yet! Although I’m seriously considering switching to something else.
I would also like to add a tutorial or two on graph layout algorithms, both from my internships and the lattices that I’m going to visualize for my thesis.
Meanwhile while you wait, why not pick up the new Trine 2 which is a really good Indie game, man it looks absolutely perfect and the first 30 minutes already promise a lot more fun than Trine 1. *Not an advertisement, I’m just hyper excited about it *.
As you might know I once wrote an A* sample for C# more than 2 years ago. The first version worked but was very slow because of a bug. The second version was faster, and a third version (made by one of the readers of this blog) was even faster.
Btw did you know that the excellent game Dysomnia shipped with (a modified) version of my C#/A* code? Ok it’s just a few lines to get people started but it’s really cool to see how people use this little start for their cool projects!
Anyway, back on topic: during my internship at Nixxes an interested co-worker (thanks Marcel!) tweaked the heuristic, removed some unnecessary checks, and added a faster way to check if a tile was processed yet.
There is not much else to say, it’s still A*, it supports 2D and 3D, it uses a MinHeap and is faster than ever! (Note: this is a pure C# solution, so it doesn’t require XNA, but it will work nicely with XNA even on WP7 and the Xbox360).
Older relevant blog posts about A* (from older to newer)
I tried to do a weekly update during my internship at Nixxes, but I never got around to finish a single post. However since Post-Mortems are hip these days I decided to write a simple post-mortem about my internship.
Let’s start with the beginning. In the first week my mentor at Nixxes was still on vacation so a co-worker set me up with a new computer (a shiny i7) and helped me set-up the development environment. I was handed a few drafts from another co-worker who a few years back wrote a proposal for the tool I was to build. So I tried to arm myself with knowledge and put my education to the task by writing things like inception documents and prototype proposals. Although this was a bit formal for the team (they only do a light scrum + two person commits) it helped me get a good overview of what I had to do. I also played a lot with their technology (trying to give good old Lara Croft green hair in a test-level of TR:Legend).
The tool I was to build had a simple enough goal and had to do with their automatic shader generation. I had to make a tool that gave artists insight in how different settings on materials would create different shader configurations. It was not to give technical insight inside the shaders (you wouldn’t want to bore artists with that) . But to let them reduce the number of actual shaders by simplifying material.
In the next few weeks I started searching for existing tech, testing and prototyping. I needed tools to show large complex graphs with a lot of cross-nodes. So I started searching for layout algorithms (In the end I combined two layout techniques and wrote code myself, but it’s always good to check if you’re not reinventing the wheel, and it gave me some great insights).
I also had to familiarize myself with WPF, which I really enjoyed (the learning curve for WPF is much shorter than for WinForms and the performance and ‘nice-ity’ of WPF greatly outclasses WinForms).
After a few prototypes we decided on a work-flow for the program and refined the core questions the program had to solve. It’s really helpful to write those down because a goal might be too abstract/far away so these core questions help you refine your way to do the goal and give you some work flow hints. (It’s also good to have these in your help file).
Because of the limited time there was only one week of feedback from real artists but of course I was surrounded by techies to help fill this void.
In the end we refined the work flow once more and tied in the program with existing tools. (Up until now I was just parsing raw data). I hooked into a content-service using C++/CLI. This C++/CLI program also hosted my C#/WPF frontend, and to my surprise this worked really well and was easy to do!
In the end I left behind a well document and finished product and because we had a week to spare there was even quite some polish (the last week was used to add in some background workers and nicer progress bar, I also added cancellation support to the layout algorithm).
During my internship I also experienced the release of Deus Ex: Human Revolution, of which the tech and pc-port was done by Nixxes, so it was really great to see the game get an 8,9 on meta-critic!
The end-talk with my mentor was relaxed and pleasant. I knew I had done pretty well but I was quite surprised when he gave me a final grade of 9 out of 10! Yay!
All in all I had a great time, and I’ve learned a lot of new techniques (C++/CLI, WPF, Graph Layout Algorithms, Data Binding). I also finally got to experience a real hands-on approach where everything gets prioritized because resources are finite. On the university it’s really a rare thing to experience this, so this was really an eye opener. I feel like I learned more valuable skills in these two months than I would have doing 3 more courses (Thanks to a helpful dean I could replace 3 courses with this intern shop)
I would like to thank everyone at Nixxes for a great time!
One of my co-workers again sped up my A* code after peeking at my blog. I have his code and am trying to add a nice visualizer to it this time before posting it, so expect it up soon.
This summer I’ll be doing an internship at Nixxes Software in Utrecht, the Netherlands. They are a group of highly experienced game technology programmers who are independent but work mostly for Ubisoft Montreal. Their latest projects includes work on “Lara Croft and the guardian of light”, “Deus Ex: Human Revolution”, and “Kane & Lynch 2″. They mostly develop on the engine used for these games, and tooling. It’s not yet sure what I’ll be doing but it will probably be a tool that too measure where performance can be increased, it will probably written in C# with interop-ed with C++/CLI.
I’m not yet sure if I’ll be working under an NDA (probably) and how much info I can release on what I’ve been doing, but I’d like to write a sort of development diary here. I’ll probably not be writing tutorials for the coming 2 months because I won’t have much free time.
Anyway I’ll be back after 2 months, so stay tuned and enjoy your summer vacation (I hope it will be more of an actual vacation for most people ).