Pathfinding Thesis Complete

WOOT! My thesis, the bane of my existence for the last 2 years, is finally done! Its basically a review of the video game pathfinding field as well as presenting a novel grid map search technique: the spatial grid A*. The version linked below is the final draft that is being submitted to my faculty.

A Robust Explosion Hit Check Technique

In a recent technical interview I got asked the following question: “if an explosion occurs i.e. from a grenade, how would you determine which characters in the game are affected”. This was a question that I couldnt answer at the time which annoyed the hell out of me and it’s been sitting in the back of my head for the last few weeks. So I decided to discuss it (and my proposed solution) on my blog as an “academic” exercise. I would really appreciate any feedback or comments on this discussion. This is far from being a solved problem for me and while my solution may potentially work quite well, there may be a simpler technique available which I don’t know about.

Coming back to the question. Well the naive answer to that question is to simply do a collision detection check with the explosion area of effect/blast radius (sphere) and any nearby characters’ bounding boxes. Continue reading “A Robust Explosion Hit Check Technique”

DirectX10 Tutorial 10: Shadow Mapping Part 2

This is the second part of my shadow mapping tutorial (find part 1 here). I am going to discuss some of the issues of the shadow mapping technique as well as some basic solutions to the problem. I’m also going to attach a demo application, in which you can play around with some of the shadow mapping variables and techniques. I do have to mention that the demo was a very quickly programmed prototype. It serves its purpose as a demo application but I dont advise cutting and pasting the code into your own projects as a lot of the techniques used arent exactly optimal. Not to mention that I did take a few shortcuts here and there. Continue reading “DirectX10 Tutorial 10: Shadow Mapping Part 2”

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

Continue reading “DirectX10 Tutorial 10: Shadow Mapping Part 1”

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. Continue reading “Experiences with Interviewing So Far”

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. Continue reading “Optimizing the A* algorithm”

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: http://takinginitiative.net/computer-graphics-course-slides/

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 😛

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…

I’m going to GDC 2011!!!!!

I’ve been putting off this post for a while cause it still feels like a dream! I’ve been awarded the “Eric Dybsand Memorial Scholarship for AI Development” by the IGDA Foundation as well as a GDC scholarship by the International Game Developers Association.  What this means is that I will be attending the Game Developers Conference this year!

Attending the GDC has been a huge dream of mine for the last few years, as you can see from the banner on the right hand side, financial restrictions have prevented me from attending in the past. In addition to attending the conference, I get to be introduced to various industry VIPs and shown around at the conference by seasoned industry professionals. This is the single biggest opportunity I’ve had to get into the game industry and I am sooo excited!!!

The GDC scholarship provides me with a all access pass to the GDC, so I can attend the talks as well as the expo and career seminars. The “Eric Dybsand” scholarship is an AI specific scholarship which afford me the chance to network and meet a lot of game AI programmers and an opportunity to attend the AI game programmers guild dinner! I’m crazy excited about being able to attend the AI summit especially since the list of speakers is practically the bibliography of my thesis, and as weird as it sounds these guys are like rockstars to me. I’m quite intimidated by the thought of actually meeting them in person. I really hope that I dont make a fool out of myself haha…

I’d just like to thank Neil Kirby from the IGDA foundation as well as Gordan Bellemy and Jack Bodgan from the IGDA for giving me this chance! I really really appreciate it!!!

So whats happening at the GDC this year:

  • The AI summit – 2 days of discussions regarding the key issues in game AI
  • 25 Post-mortems on classic games by the developers (games include Pac-Man, Prince of Persia, Bejeweled, Populous, Doom, Pitfall, Maniac Mansion and more)
  • A game design talk by Cliff Bleszinski of Gear of War Fame
  • Battlefield 3 Unveil (OMG!!!)
  • Keynote address by the president of Nintendo – Satoru Iwata!!!
  • and sooo much more!!

I really cant wait!!!! This has made my year!!!!

PS. I am responsible for all my accomodation and food expenses so if anyone feels like they wanna help me out by donating please feel free to do so.

Currently the total for donations I’ve received over the last ~3 years is $1…

DirectX10 Tutorial 9: The Geometry Shader

This tutorial is going to cover the basics of using the geometry shader stage present in DX10+. The geometry stage is extremely useful for rendering sprites, billboards and particles systems. This is the first part of a three part series which will cover geometry shaders, billboards and particles systems.

The Geometry Shader

The geometry shader stage was introduced in DX10 and people initially assumed that it would be useful for tessellation purpose (which is true) but it’s more useful for use with particles systems and sprite rendering. The geometry stage sits between the vertex and pixel shader stages and its primary use is creating new primitives from existing ones.

Just to recap, vertices are sent to the vertex shader within a vertex buffer that is stored on the GPU.  A draw call issued to the API, sends a vertex buffer down the pipeline.  Each vertex first enters the vertex shader where it is transformed as necessary, and its vertex data is modified (if necessary). Once vertices have been processed and outputted by the vertex shader, they get combined into primitives during the primitive setup stage of the API. The type of primitive created from the vertices sent through the vertex buffer depends on the primitive topology set (points, lines and triangles).  Normally, once a primitive is constructed, it moves on to the screen mapping and fragment generation (convert triangle to pixels) stages before reaching the pixel shader stage and finally being drawn to the screen. Continue reading “DirectX10 Tutorial 9: The Geometry Shader”