Category Archives: Programming

Improved Furnishing

warehouse storeroom

click to enlarge

 

Recent work on Free Company has been focusing on improving the look of the randomly generated rooms by subtly shaping the way the objects are laid out to conform to more human norms of laying out rooms. For example shelves in the game are now no longer empty instead they are filled up with appropriate small objects . The objects as redetermined by the procedural generator-wide tagging system. Objects have tags; levels, monsters and rooms have tags; the generator attempts to assign them to each other using probabilities based on how closely the tags of each align. The way the objects are placed on the shelves is determined by three different algorithmic approaches that attempt to mimic general human behaviour as regards shelves: filling up from the left hand side, from the right hand side and alternately from the left and right hand sides. The quantity of objects on each shelf is determined by a normal distribution linked roughly to the dimensions of the shelf to ensure that the average shelf is about 90% full .

That’s one example, other new strategies have been employed to shape the placement of the shelves themselves and other objects to create the hopefully more believably storeroom like rooms you see in the screen shots on this page. To support these new furnishing algorithms I’ve also been making a whole pile of new objects, almost doubling the number of them in the past week. Some of these can also be seen  in these two shots.

 

click to enlarge

 

The basic warehouse layout and furnishing algorithms are probably done about as far as I am going to take them for the first release all the rooms now look passable and I expect I can reuse the same algorithms for a few other environment variants like the crypt and a new library layout once I create a few more objects to support them. I still have plenty more ideas for algorithmic level generation though and I’d love to revisit this area to try and  make even more believable and varied layouts in the future.

The other new things I’ve done  recently are a few minor cosmetic buffs. From feedback to my last post (thanks Stian!) I’ve switched out the general game font for a more serif ridden fantasy one, I’ve fiddled with a few of the most frequently seen textures to try and make them a little less bland (still a work in progress) and I’ve implemented a more flexible system for testing out lighting changes quickly in game (hit a key to rebuild the lights from the theme data .xml files). The last thing (which just went in today) has allowed me to fiddle with small lighting changes and see the result in a couple of seconds rather than the many minutes it was taking before, so I updated a few of my lighting themes with some tweaks too.

 

Anyway, as usual let me know what you think about the Storerooms or anything else in the post in the comments below.


HUD improvements & Memory leaks

click to enlarge

This fortnight has been spent plugging all the memory leaks that had built up in the Free Company code base since the last time I went through and plugged them all. The work was considerably eased this time by the use of a new tool I discovered called Visual Leak Detector which makes the process of pinpointing where the leaks are happening fairly trivial by providing callstacks. It also runs fairly quickly in the background so I can leave it on permanently in debug builds to continue passively identifying new leaks as and when they spring up. VLD is super simple to integrate into any project as well so if you are still struggling along with C++ out there I recommend adding it to yours immediately. The only thing it doesn’t catch are Direct X memory leaks for which a more traditional approach, and the debug runtime, is still needed.

Once all leaks were deftly disposed of it was on to a HUD tune-up, something which is still ongoing and probably will be right up until the release. You can see some of the results of the changes in the screenshot above. I was aiming for less numbers & more visual ways of showing what is going on, as well as adding more widgets to give you better control over your whole party of mercenaries. The portraits added back in January now provide a handy way to select a particular mercenary and jump to his current position in the world, and they will  also soon contain a shrunken down overview of the bars on the main HUD for each merc. There are now special pointers for all of the various ways you can control the camera which possibly only I care about. Finally, I spent a bit of time tweaking the colours of various elements to tie the buttons into the HUD better, improve consistency between different elements and generally reduce the ‘primary’ nature of most of the colours I was using before. I’m still not very happy with the layout of the bottom HUD area ( a lot of spare/wasted space, the elements are a bit boring) nor the fairly crappy skill icons but it is coming along all the same.

click to enlarge

While I was fiddling with the HUD I also went through and ticked off a whole heaving heap of bugs with the skill system so that the handful of currently implemented skills now actually work properly all the time and give slightly better feedback when they are being used to boot. Implementing a host of new skills and improving their feedback is one of the big upcoming tasks so I wanted to have the ground prepared for when that is started. And as a final thing I’ve just now tweaked the post effects again to add a vignette.

To give a sort of general picture of where the game is at I have about a week or so’s more tasks listed on my current ‘polish’ to do list to get through before I start on one of the big three remaining tasks pre-alpha release. Those big tasks are; skills, AI & real-time play between combats. I’d welcome any feedback on the changes/look of the HUD in the comments. Or really, any comments at all. Speak your brains internet.

 


Lightmaps, ESM & Fog of War

Click to see giant version

Progress on Free Company continues at a steady pace here in the shed, unfortunately I’ve been pretty lax about reflecting that progress on the blog but no more for today I come with tales of newly implemented features, bugs fixed and graphical systems steadily improved.

First up is the new fog of war system. I spent a fairly long time with the implementation of fog of war sitting at the bottom of my many & various scrawled to do lists. I knew I wanted it in the game but I wasn’t quite sure how to get it working and running at a decent speed. The first problem is that there was no obvious example to be ‘inspired’ by, most games that I could find using fog of war were either fully 2D or they didn’t combine it with a fully rotate-able 3d camera. I needed a solution that obscured a given hex from all possible angles when none of the mercenaries could see it. I also wanted to be able to have a semi transparent view of areas that the mercenaries had already visited.

Anyway, as you can just about see above I managed to figure it out by using sort of hexagonal cages that are rendered over the top of the level geometry, and then using a complicated blend mode to do the semi-transparent version without showing the sides of all the neighbouring cages. It isn’t quite perfect as there is only a subtraction operation available to do the ‘transparency’ rather than the normal multiply but it works passably enough and most importantly isn’t horrifically slow.

The blend modes look like this:

 HR(g_d3dDevice->SetRenderState(D3DRS_ALPHABLENDENABLE, TRUE));
 HR(g_d3dDevice->SetRenderState(D3DRS_SEPARATEALPHABLENDENABLE, TRUE));
 HR(g_d3dDevice->SetRenderState(D3DRS_BLENDOP, D3DBLENDOP_REVSUBTRACT));
 HR(g_d3dDevice->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_DESTALPHA));
 HR(g_d3dDevice->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_ONE));
 HR(g_d3dDevice->SetRenderState(D3DRS_SRCBLENDALPHA, D3DBLEND_ZERO ));
 HR(g_d3dDevice->SetRenderState(D3DRS_DESTBLENDALPHA, D3DBLEND_ZERO ));

…just don’t ask me to explain them because I did it a month or so ago now.

After I got the fog working I spent a fair bit of time improving the intuitiveness of some of the UI elements so now the sliders and scroll bars work more like proper scroll bars with live updates (change the music volume in terrifying real-time!!) and the buttons have proper embossing so they look like buttons. I also fixed a whole bunch of tiny pixel offset problems with things like the text and the basic ui rectangles that were causing some slight (but noticeable) visual problems.

Next up was implementing a new lighting technique called light mapping. This was a bigger project than I’d hoped at first glance to fix a small visual problem but now it is done and as a result I have a bit more flexibility with lighting. The basic problem I had was that my static geometry (which covers all the walls, floors, shelves and so on) could only support being affected by three lights simultaneously. On older graphics cards I wanted to support there was simply no way to physically pack any more lighting data into the vertex buffers or into the shader instruction count if I switched back to slower dynamic lighting.

At first, I’d tried to alleviate this problem by keeping the lights in any given generated room under three which worked to an extent but inevitably the random generation meant that occasionally a light from a corridor adjacent to a room would  push the number of lights affecting a mesh over three and there would be obvious lighting discontinuities. I tried implementing a range of simple ‘light blockers’ to reduce this problem further but those didn’t really help as they had no way of dealing with a mesh that was lit from more than one side (such as the very frequently used room corners). So, I either had to put up with the lighting discontinuities (they were of variable severity but in the worst case there was wildly different colour lighting and brightnesses on each adjacent wall mesh) or I had to come up with a new lighting scheme.

There are two basic approaches, the modern and the retro. The modern approach involves using deferred rendering for basically everything and is slowly becoming the approach that all modern engines are moving towards as it has the most flexibility and the least disadvantages. Unfortunately, in my case this problem was being caused by trying to support older graphics cards in the first place. It isn’t much of a solution to switch to deferred shading and cut out all those old GPUs which don’t have the necessary oomph to do deferred shading. So I was left with the retro approach, which is lightmapping.

click to show giant version

Lightmapping isn’t an ideal fit for my game because it is principally a pre-computed technique and gets most of it’s advantages from being able to take advantage of known geometry arrangements in the data building stage and then spend as long as it likes crafting really fancy lighting setups for them. However all my geometry layouts are generated on the fly each time the player starts up a new level. I don’t have the time to do a expensive set of ray-traced lighting calculations while a player is sitting there waiting for the level to load. Luckily however, you can make the lighting calculation as simple as you like when generating light maps so I set the dial to ‘super-simple’ and set about getting them actually working.

Lightmapping as a technique actually contains several smaller problems that need solving;

  1. generating light mapping UV coordinates.
  2. packing lightmapping UV coordinates of all the instances proportionally to the surface area being lit.
  3. interpolating the positions & normals of all the mesh instances.
  4. generating the actual lighting data
  5. rendering with lightmapping.

The last part is the easiest, if you’ve done it all right you can just read in your lighting from a texture with your specially generated UV coordinates. The other parts, were not so simple.

For the first part I decided to create my lightmapping UVs as part of my models’ mesh data rather than algorithmically generating them. Mainly because this is one of the few steps I could take ‘off-line’ but also because I, perhaps foolishly, thought it might be easier to make them this way. I used blender to generate my UVs and if you do the same let me give you the most useful tip straight off; the blender ‘lightmap UV’ generation script is pretty much useless for complex geometry. By which I mean any curved surface, if you don’t have infinite space on your light maps you are going to want those curved surface UVs stored contiguously in your lightmap so that the sampler can smoothly interpolate across the surface. The blender script, by contrast, breaks up every face into separate uv ‘islands’ and then tries to pack them in any old order, bah.

Anyway, I also had another problem to overcome with UV coordinate generation, mainly that the only decent .x exporter script I managed to find for blender 2.49 didn’t have any support for multiple UVs and secondly the .x format itself makes it very difficult to work out how to cram extra data beyond the basics into your meshes. Once you do work it out it is excruiciatingly difficult to convert the data into the required (DWORD) format in python. You will need this piece of code:

def convertFloatToDWORD( self, float ):
 pF = ctypes.pointer( ctypes.c_float( float ) )
 pDw = ctypes.cast( pF, ctypes.POINTER( ctypes.c_uint ) )
 return pDw[0]

(from here) if you want to have a chance.

Part 2 of the lightmapping problem wasn’t quite as difficult, I used a very simple rectangle packing algorithm on the basis that that would probably be fastest and scaled each instances UV rectangle by the surface area of the asset calculated during loading. Make sure to keep track of the calculated UVs somewhere as you’ll probably want to pack them into your static geometry when you batch it up.

Part 3 was more tricky and after stumbling around with the semi-missing code at flipcode for a while I hit on barycentric coordinates as the interpolation method of choice which seemed to produce the nicely smoothed normals I was looking for and was a whole lot less code too:

//calc normal
 D3DXVECTOR2 edge0 = faceCorner2uv - faceCorner0uv;
 D3DXVECTOR2 edge1 = faceCorner1uv - faceCorner0uv;
 D3DXVECTOR2 edge2 = uv - faceCorner0uv;
// Compute dot products
 float dot00 = D3DXVec2Dot(&edge0, &edge0);
 float dot01 = D3DXVec2Dot(&edge0, &edge1);
 float dot02 = D3DXVec2Dot(&edge0, &edge2);
 float dot11 = D3DXVec2Dot(&edge1, &edge1);
 float dot12 = D3DXVec2Dot(&edge1, &edge2);
// Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
 float w = 1 - u - v;
worldNormal = (faceCorner2normal * u) + (faceCorner1normal * v) +
 (faceCorner0normal * w);

So use those for everything interpolation related.

The lighting code I already had, though it is worth bearing in mind that by implementing lightmapping the sum total of your lights will probably be saturated from 0.0 to 1.0 by the necessity of texture storage. Which doesn’t sound like much of a big deal but it can make a pretty noticeable difference when you are summing up the influence of multiple point lights and then multiplying that by other lighting terms in your shader.

Anyway, eventually after a lot of careful hand crafting of UVs that was all finished and now I can have as many lights as I like per room without fretting too much and all the discontinuity artefacts are gone. Aces.

Next up on my lighting refactor mission was the shadow mapping code. It’s been working OK for a while now but has always showed some ‘shadow acne’ at certain camera angles and, worse, the acne shimmered whenever the camera was moving immediately drawing your eye to it. I spent some time tweaking the current code and fiddling with bias values and resolution but no matter what I could never satisfactorily remove the shimmering acne. So, I figured there must be another way by now.

Of course, some careful googling later introduced me to the world of Variance Shadow Mapping (VSM) and Exponential Shadow mapping (ESM). This blog was a great summary of the best places to learn about each technique and really they aren’t dramatically different from shadow mapping. Once you have basic shadow mapping setup in your game it is no more than a morning’s work to try out both VSM and ESM I would recommend everyone struggling with shadow mapping artefacts give it a go and then probably settle on ESM because, at least for me, the light bleeding artefacts with VSM were pretty obvious and just as bad as shadow acne. ESM however immediately worked great and cured my shadows of acne, tedious bias tweaking and shimmering. I do have one difference with the blog linked above in that he mandates keeping the over-darkening parameter to between 0.0 and 1.0, I found by contrast that the original range specified in the nvidia example worked a lot better in my game so don’t be afraid to crank that term up.

Lastly, the past day I’ve been fiddling with improving the SSAO term. I’ve not totally settled on a method yet but so far I’ve replaced my basic box blur with a ‘bilateral’ version that respects normal and depth discontinuities and had a stab at sticking this new fangled FXAA on top of that so it’s jaggy edges don’t completely ruin my lovely regular MSAA rendering. Not totally sure that the FXAA is completely working but eh I might come back to it later.

Anyway, that is probably enough lighting stuff for now as I’ve reached the bottom of the lighting to do list. Next week I’ll likely start by tackling a whole range of bugs and minor polish problem and then it’ll probably be back to either skills & related UI improvements, better AI routines or realtime group movement between battles.