DirectX10 Tutorial 10: Shadow Mapping Part 1

I’ve had some downtime lately and seeing as I wrote a basic shadow mapping demo, I figured I’d write a short tutorial on the theory and implementation of shadow mapping. Shadow mapping is one of those topics that tends to get explained in a overly complicated manner when in fact the concept is rather simple. It is expected that you understand the basic of lighting before attempting this tutorial, if you want to learn more about some basic lighting models please read my lighting tutorial. The figure below shows a sample scene with a single light illuminating a cube.

How shadows are formed

Read more of this post

Experiences with Interviewing So Far

So I’m currently looking for a job in the game industry, location and salary are secondary to the work at this point. I kinda just want to get out of South Africa and work on something cool. I’m still young enough not have to worry about supporting a family, stability or dealing with crunch time, I kinda just need a chance. I’ve spent the last few weeks sending applications, writing programming tests and interviewing. And to be dead honest, I’m kinda starting to lose a bit of faith in myself and my chances of landing an entry level game dev job without any game experience.

Now before I carry on with this post, I need to just say that I, in no way regret any of the interviews I’ve had, I’ve learned something from each and every one of them. It’s actually been kinda fun even though I felt like a complete idiot a couple of times (I tend to be really hard on myself). The programming tests were a lot of fun and one plus is that I’ve passed all the tests I’ve written. Read more of this post

Optimizing the A* algorithm

So I’ve recently completed my MSc thesis on video game pathfinding and I guess it’s a little weird for someone who spent the last year focusing on game AI and pathfinding to not actually spend much time blogging about it. I figured that I spent the time today and write a short post on optimizing the A* algorithm. The A* algorithm pretty much sums up video game pathfinding as a whole. Even advanced techniques like hierarchical pathfinding algorithm make use of A* in searching the various abstraction levels.  So today I’m going to just discuss optimizing the algorithm, not a low level implementation but rather the some of the high level issues. I’m assuming that readers will have some degree of familiarity with the A* algorithm so I’m not going to waste time explaining it.

A*’s computational cost is primarily divided between two components, the heuristic function and the open list and so these are the components that I’m going to focus on. Read more of this post

Completed Undergraduate Computer Graphics Course Slides

So I finally managed to complete the undergraduate course slides. I know I wanted to get them completed by the end of December but things didnt really go according to plan.

The slides are available here:

These slides cover the entire graphical pipeline from start to finish in detail. They are intended for a modern computer graphics course using the D3D10 API and HLSL. The amount of information contained within the slides is quite significant and to my knowledge there isn’t a single other place online with a more comprhensive coverage of computer graphics theory.

So whats the point of putting up these slides, well they are catering for two types of people:

  • Lecturers – if you wish to modernize your undergraduate computer graphics course or are tasked with presenting such  course, these slides are a great starting point. Hell, if you want just rip them off completely. ;)
  • Hobbyist Graphics Programmers – if you want to learn more about how computer graphics are programmed, GPU architectures or the basics of texturing and lighting.

Anyways, I hope you find the slide useful. This is my last semester as a computer graphics lecturer nd so I figured that there is no point letting all my work go to waste when someone can still get some sort of benefit from them.

Enjoy :P

Final Simulation Results

Final Simulation Results for BGMAPS benchmark

Final Simulation Results for Custom RTS Maps

I recently posted about some preliminary results for my prototype algorithm, I now have the final results for both BGMAPs and my own set of RTS style game maps. Both sets of maps were sized at 512×512. The RTS maps are simple island style maps which I made more complex that the average RTS map found today just to increase the difficulty of the problem. In increasing the complexity I’ve also reduced the length of straight line paths available at which my prototype excels in that way I’ve handicapped it a little. Even so on RTS style maps my silly algorithm kills A*, furthermore there the memory costs are over 10x lower than required by A*. Unfortunately my RTS maps are artificial and so I cannot state that my approach will work beyond a doubt in real world RTS maps (even though I’m pretty sure it would ;) ).

The initial prototypes I presented had some flaws and were not complete algorithms in the sense that they wouldn’t always return a solution if one existed. My new versions are complete in that sense. There was a lot of tweaking, prodding and changing necessary to achieve this and the search times have gone up marginally.

The performance of the prototypes isnt bad on the BG maps test set but unfortunately the graph doesnt show the full picture, there are certain rare cases in which the solution returned by my approach is GROSSLY sub-optimal (over 100% suboptimal in fact) and the time take to find this “amazing” solution is nearly double the time needed for A*. This poor behavior is due to the spatial layout of the BG maps, which focus on numerous dead end winding tunnels.

I would like to investigate the efficiency of the algorithm within real world RTS maps as well as on FPS maps so if any game devs reading this post can send me some top down JPGs of their game levels I would really appreciate it. I now just need to finish writing up my last chapter of my thesis and submit it. I will be posting the full thesis on this blog which will include all the necessary info on my prototypes which I’m naming the Spatial A* algorithm.

PS! it is necessary to mention that these results are pre-smoothing and so the path optimality will be greatly improved with a post-processing smoothing step.

Preliminary Pathfinding Results for my Prototype Algorithm

The preliminary results of my prototype pathfinding algorithm - run on a basic set of 8 BG maps.

It’s been a while since I’ve posted about anything pathfinding related. I’m currently wrapping up my thesis and once I finish work on this prototype algorithm all I need to do is write up my results and my thesis is complete.

My prototype algorithm is based on a pretty stupid premise so I wont go into much detail here ;) sufficed to say its basically an abstract search without an abstraction layer. I have three versions of the basic algorithm:

  • P1 – this is the naive version (the same one I showed at GDC)
  • P2 – performs basic trimming on the refinement step as discussed at the AI dinner (thanks Alex, Marc and Joel!!)
  • P3 – attempts to improve path optimality by picking a new end goal for the search and using that to reach the final goal.

These are the results of a very basic run on 8 Baldur’s Gate 2 maps scaled up to 512 x 512 (around 10000 search problems). My algorithm makes use of the exact same A* implementation it is compared against. There is still one problem with the P2/P3 variants that needs to be corrected and a P4 variant is also in the works. I hope to have all 4 variants complete by the weekend and all my simulations completed by next week monday. That gives me a week to do the final write up and submit my thesis! :)

The path optimality listed is pre-smoothing, with smoothing, the optimality greatly increases but so does the total time for the “pathfinding action”. I still have to find an efficient (read very very FAST) path smoothing algorithm before I can actually bother doing any smoothing experiments.

So starts the rest of my life…

I fly out to San Francisco tomorrow for the 2011 Game Developer Conference. I was awarded the Eric Dybsand Memorial Scholarship for AI Development this year and so am lucky enough to be able to attend the conference. Attending the GDC has been a dream of mine and now that I’m so close to realizing it, it’s made me start thinking about the rest of my life.

I’ve kinda been putting off these thoughts for a while since the whole topic is rather frightening. I’ve been burying myself in my work and kinda just avoided it but given the large amount of downtime I’ve had this week, its hard not to think about it.

So what am I blabbering on about? Well, at the end of June I need to start my adult life. I am nearly done with my masters thesis and my contract with the university expires then. Those were the last ties I had to South Africa and I am now finally free to emigrate and look at starting a career and a life somewhere. So basically, at the end of June, I’m unemployed and mobile. This means that I have a couple of HUGE LIFE CHANGING decisions to make. And well, I’m honestly terrified.

Now dont get me wrong finding a job in SA wont be a problem, hell I could probably be driving a fancy ass BMW in a year or two but it will be through a job that I know I’m not going to enjoy. I want to make games, I want to be challenged, to learn, to improve my programming skills. I dont really care about money or having a fancy car or living in a huge house, I just want a job that I will enjoy! Game development will enable me to do all that and sooooo much more.

This opportunity to attend the GDC is a huge one and if I’m lucky I can impress someone enough to offer me a job. I just need that first foot in the door. Unfortunately I’m a programmer meaning I’m not exactly the world’s most charming, confident and outspoken person. To add to the generalization: I’m also shy and a bit awkward around strangers. The thought of walking up to a stranger (probably some VIP) and giving them a confident 1 minute elevator speech about myself scares the hell out of me BUT its something I have to do!! Never mind just do it, I need to do it well!!

As I said I’m a programmer, my skillset and interests mean that I’m looking for any AI, engine, rendering programmer positions. I like getting my hands dirty with low level technical stuff. I’m hoping that I can meet someone at the conference that I can impress enough and that will give me a shot! AI and graphics ar my main interests and any job involving either of them will make me insanely happy! In addition to GDC, I’m going to start applying to game companies immediately when I return home and see what happens.

So what if I dont get a game industry job offer, well staying in SA is not really much of an option but rather a final resort. If I cant find a job in game development then I will look at the military sector, and try get some sort of defense contractor position doing robotic AI or missile guidance or something like that. Maybe even simulation software since that’s reasonably close to game dev and I might even get the chance to do some graphics programming :).

To be honest, the more I think about it, the location doesnt really matter  to me as long as I’m doing something I love. At this point I guess my career (well my future career) is all thats important to me. So June is going to be a critically important month for me, one that I guess I’m gonna deal with it once I get there. Till then I’m going to enjoy the hell out of the GDC and will be trying my best to be all memorable and impressive (LOL :P). So anyone reading this post, please hold thumbs for me! :)

Let WindowsXP and Direct3D 9 Die Already

So for the first time in months, I find myself with some downtime. I’m currently in Arlington, TX visiting my dad. the last few days have been spent reading my silly fantasy novels and watching GDC lectures from previous years (thanks Dave!). I watched a presentation on NVIDIA’s NSight tool which allows for in-depth GPU debugging and it kinda made me think about the state of current game graphics technology. I’m not used to ranting on my blog but I’m a little bored and figured that I would just write up my random thoughts today :)

Almost every game being released today on the PC platform still has a DX9 render path and games that do offer DX10/11 renderpath are simply DX9 ports with an added effect or two tacked on. I may be mistaken but as far as I know there isnt a single game on the market that has a renderer designed from the ground up tailored for DX10/11. DICE’s battlefield 3 is the first game I know of that WILL NOT be featuring a DX9 render path (UPDATE: Just Cause 2 seems to be the first PC game to drop DX9) and for that I am beyond thankful. BF3 is dropping support for WindowsXP and DX9, excuse my language but about fucking time! DICE is the only company that has had the balls to let XP just die.

Read more of this post

Debugging HLSL

A lot of guys have asked me for advice on developing and debugging shader programs. Well, it’s a tricky topic to deal with. Tto be able to fully debug shader programs you will need either a shader IDE like FXComposer or a GPU debugging tool like Nvidia Nsight. These are both complex tools and beyond the scope of a quick tutorial but what I can do if provide you a quick guide to aid you in writing shaders directly within Visual Studio. You will not be able to perform any sort of in-depth debugging, but it will help you deal with silly syntax errors. The first thing need is NShader. NShader is a shader syntax highlighting plugin for visual studio and helps with clarity when editing and writing shader programs.

The second thing is to create a custom build step within Visual Studio for your shader programs. This custom build step will use the MS shader compiler to compile your shader programs and notify you of any errors as well as tell you on which lines the errors can be found. To do this, we first select our shader file and right-click then select properties (see figure 1 below).

Figure 1: Shader Code File Properties

Doing so will bring up the properties windows, the first step is to ensure that the configuration drop down is set to “all configurations”. The select Item Type and choose “Custom Build Tool” from the drop down (see figure 2).

Figure 2: Enable Custom Build Tool Step

Click Apply, this will then show the custom build menu tab on the left hand side. Select the tab and you be presented with the following dialog window:

Figure 3: Set Custom Build Tool Parameters

Under the general heading, set the command line value to the following:

"$(DXSDK_DIR)Utilities\bin\x86\"fxc.exe  /T fx_4_0 /Fo "%(Filename).fxo" "%(FullPath)"

This will mean that every time the shader file is modified and the solution is compiled, the shader file will be compiled using the microsoft FX compiler (FXC). The /T flag specifies the type of shader file being compile (i.e. the HLSL version). the /Fo flag refers to the compiled output file and the %(FullPath) macro refers to the full path of the current shader file.

Also set the Custom Build Tool outputs to: $(filename).fxo , this is the same as specified in the FXC commandline. Click OK, and you are done.

The results of the this process is shown below, all HLSL errors will pop up in the Visual Studio Error Dialog, double clicking on the error will take you to the line of code that caused the error.

Figure 4: The results of the Custom Build Step

I’ve wasted a ton of time attempting to find silly syntax errors when developing shader programs, and this little custom build step has been a great help. I hope it helps you in some way as well…

Game Piracy and Leaks!

Ranting is not something I really do on this blog, but having both crysis 2 and killzone 3 leaked prior to their releases is something that annoyed me to a large degree. The crysis leak was particularly painful for the developers, mainly since it was an unfinished build that a lot of gamers are going to play and judge the final game on. Nevermind the fact that it was leaked nearly 2 months before the release date nor the fact that the game’s multiplayer master key was leaked with it. I honestly hope the person that leaked the game is found, fired and never gets another job in the game industry.

Now the response from Crytek/EA was very brief and to the point although their final statement ( “Piracy continues to damage the PC packaged goods market and the PC development community” ) was in poor taste in my opinion. Thanks to that one statement, every forum that I frequent has erupted in a frenzy of nerd rage and conspiracy theories, the most ridiculous one being that Crytek themselves leaked it so as to have an excuse to abandon PC development. Well, honestly I cant even imagine what the situation at crytek is at the moment. As much as I love PC gaming, I can totally understand crytek abandoning PC gaming (which i hope they dont). They work their asses off to have some jackass, slap them through the face.

I know a lot of people will justify the leak as a try-before-you-buy “demo” and claim that piracy doesnt result in lost sales but that argument doesnt really make sense considering the fact that a PC demo was on its way. Nevermind the fact that now the game may be further delayed to to the need to change the master key and so on (I have no idea what the extent of the damage caused by this leak is).

I’m not going to get into detail on my thoughts on piracy (this video pretty much sums up my views on the topic) but what I am going to say is leaking a game prior to the release is a whole new level of douchbaggery. Honestly the only thing these leaks have done is hurt the developer as well as the gaming community. There is absolutely nothing good that can come from this leak! NOTHING!

The killzone leak is not that serious as it is the full game, as well as only being a week early. Furthermore the leak can only be played on modded PS3’s, further limiting the impact.

As for the crysis 2 leak: GG, PC gaming community… Instead of helping the developer, you go and spit in their faces…

Even though the original Crysis wasnt one of my favorites, I’ve now gone out an pre-ordered Crysis 2 just to show my support. I recommend that anyone reading this do the same. The damage is done, so lets at least try our best to show that the PC community isnt just a bunch of thankless, entitled douchebags.