Previously I visited a really simple and terrible way to render voxel terrain.  It involved stepping along a ray at uniform intervals, and simply sampling the height map at whichever texel the current point along the ray falls into to.  Its crude, but it works.  I would have liked to use my previous ray casting code to step along each ray, but the algorithm prohibits this.  That is because the old algorithm steps along in the x-axis intervals until it hits something and saves it.  Then it steps along the y-axis intervals until it hits something.  Finally, it takes the real hit point as the closer of the two hit points found.  That is simple and efficient when we only want to know the first intersection point, but useless when we need to step in order through a height map.

To improve the voxel landscape renderer, I needed to write a better raycast algorithm.  A requirement for its intended purpose is that the algorithm will visit each tile of the map in the order in which they are hit.  Something like a straight line algorithm (Bresenham’s) would do this, sure, but I also need to know exactly where each intersection takes place, and extra information on top of that, so a better solution had to be found.

I also should point out that I took every opportunity to ensure that this ray-cast method wouldn’t be only applicable to voxel landscape rendering.  It can be used in exactly the same fashion as my previous ray-caster, only this one should be more robust, and has a few nice additional properties.

It can return the exact tile that was hit, the exact location of the intersection and a code representing the side of the tile that was hit.  Also I needed to ensure that a hit would not be registered from the tile that the origin lies in.  This requirement is for other uses, such as light mapping, and radiosity calculations.  A demo I badly want to make would be 2D a radiosity light mapper using a photon vomiting approach.  Therefore I needed to ensure that I can find a normal ray intersection point, and later compute a reflected ray around that point, to simulate light bounce.  An issue I worried about and previously had trouble with was when the origin of a ray lies essentially touching a blocking tile.  This is an issue I hope has been resolved now.

The above image was generated in a stress test for the new algorythm where all rays are traced from the origin radiating out evenly in a circle.  In this case the origin is obviously the blue circle.  Lines are then drawn from the origin to the intersection points, which gives the appearance of a light source when a sufficient number of rays are used.  The stress test shows that the algorithm appears stable at all angles of ray, and was fast even when spitting out > 500 rays.  The new algorithm can be found below, but please give me some credit if you use it for anything.

RayCast.cpp

Since voxels seem to be all the rage these days I feel like I may as well join in too since I don’t want to miss out on all the fun.  While I have been learning about procedural generation and noise functions, I realized that I also needed a way to visualize height fields somewhat more intuitively then just drawing a 2D top down projection.  I decided to explore the illusive technique of software rendered voxel landscapes,  not the minecraft type of voxel which uses octal trees to store a true 3D representation.  Most of these octal tree voxel techniques convert each voxel into a 3D polygonal representation so that the graphics card can render it quickly.  This method seems a little more pure then that, since its all voxel and all software.  The basis of this method is really just an extension of the ray-cast that I have explored before, but in actual fact I implemented a horribly naive ray-cast for this quick demo for the sake of simplicity.  A great tutorial covering the entire technique is best found here:

http://www.flipcode.com/voxtut/

During my experience writing an editor for my Chaos Engine remake I fell in love with C#’s property grid since it is like the ultimate Swiss army knife of data manipulation.  The property grid can be seen below:

From my understanding, you send the property grid a structure, it accesses C#’s internal representation of that structure and makes all of its members available for manipulation in their native data types.  Even things such as enums are correctly handled, and alone it can form the greater part of a powerful level editor.

My current focus is the re-implementation of something similar in C++, which will form one of the cornerstones of my level editor.  Since there is no way to ask C++ what the layout of a structure is, I need to give this information to my property grid in addition to a pointer to the structure to be modified.  These representations can be programmed at compile time and included in the static data section, and the beauty is that we can use the same representation for all objects of the same type.  As always, I like to make a mockup before I start to program so that I can first focus 100% on the visual layouts, and then later focus 100% on the programming side of things.  If I were to do both at the same time the final design may be unfocussed and rushed.  My mockup is designed to match the scripting art for nice consistency.  I hope to have this finished in the next few days.

There hasn’t been much visually to show of my latest developments despite constant progress.

I showed my game on the TIGSource forums where I accidentally posted a scaled image of Dungeon Trap, however, many people seemed to like the “Ghetto Blur” as it was referred to that came from the scaling.  I began playing around with some methods to achieve something more intentional, reminiscent of a really misaligned old monitor.

My preferred method of rendering in the Tengu engine is to draw the game to an off screen buffer at 1:1 size, and then perform a very fast scaled Blit to the screen to blow this up to 2x to 4x the size.  At this stage I could also apply a dirty filter to mess with the colours, effectively offsetting each of the colour channels a little.  A mockup of this effect can be seen below:

Also I realized that I really want to commit to using procedural art generation in the level creation process.  The basis of each level is really just the position of the ladders, floor tiles and dynamic entities.  If you look at the mockup from the previous entry you can see that most of the fluff in the background is a regular pattern, distributed semi randomly, tending to hug the ladders and floor tiles.  This could be generated procedurally instead of the normal method of creating a limited set of pre-made tiles that are to be placed by hand during the levels creation.  The same applies to the pattern inside of the floor tiles, that is also a good candidate for being generated procedurally.  Eventually I want to be in a stage where I can just place two tiles, one to signify floor position and one to signify a ladder, then at the press of a button I can have the procedural algorithms kick in to generate all the required tiles to form a unique and complete map.  All that would be left for the designer is to place the entities and finally script the level.

On the subject of scripting, I have spent one hell of a lot of time designing a really unique and what I hope will be a fun scripting system that was born from my studies of digital logic design.  My plan is something like this; every entity in the world can have a variable number of virtual inputs and outputs, inputs being things that will effect the entity, and outputs being products of the entities internal state.  The signals that these inputs and outputs process will be purely binary however, just high and low states.  For instance a lever in the game will output HIGH when it is pulled to the right, and LOW when it is pulled to the left.  It could be linked to the input of a door which will open when that input is HIGH and close when that input is LOW.  With one link, the lever now control the door in a natural way.  With the addition of standard logic gates, some very complex interactions can be scripted between entities.  The beauty is that digital logic at a basic level can be extremely intuitive and a bonus would be that no script programming would required, however the complexity of the scripted events could be pushed as far as you want; Theoretically, an entire computer could be simulated from a digital logic design in the level.

For this to work however the scripts must be easy to make and edit, so I have been working on a visual editor as an extension to the level editor.  Here is the visual design for each of the in build logic gates for the scripting system, left side shows the inputs and right side the outputs.

These two areas will be my main focus for the foreseeable future, the level editor and the scripting system.  Other minor plans are to integrate the level editor as part of the game itself, allowing fast design and play test turn around, and to encourage user level creation.  One of my goals is to allow entire levels to be output as small encoded text strings that could be shared on any website or by any standard means.  The only other game I know that had this feature was N, by metanet software.

As I started to think about this dungeon generator it got me thinking more and more about the possibilities of procedural game generation.  I wondered what would happen if a similar technique was applied to generate the levels for a platform / dungeon crawl hybrid game of sorts.  I can envision controls similar to Flashback and Abes Odyssey where the player can only move one grid unit at a time, using some set jump actions and movements to navigate the world.  I made a mockup for this, which I have given the codename DungeonTrap, which can be seen above.  The pixel art above only uses 4 colours, which is a modified version of the original game boy palette.  I a large chunk of the animations already made, a few of which for the player can be seen below.

I had original planned to make only 1bit graphics, so only black or white, but my girlfriend was critical and suggested that it needed more depth.  Unfortunately, some aspects of the games visuals and animations that I can imagine can be shown in a static screen shot alone so until an interactive demo has been made, they must remain in my head.  I plan however to make use of all the previous programming work I have done to experiment with dynamic lights, so that the player can carry around a torch and also integrate light as a fundamental tool of the player into the game-play.

This is day one of my quest to re implement the random dungeon generator that was shown as part of the kick starter for TinyKeep.  I managed to implement a large portion of the generator today after considering a few alternative strategies for its implementation.

The original algorithm generates a large number of random rectangles without regard for any overlap between them, since in the next phase they are all separated.  Forces push each rectangle apart and so out of overlap, and after a few iterations leaving a tightly knit bed of scattered rectangles.  An alternative I came up with was to randomly place a small rectangle in a region of space known to be free and then inflate it until it reaches a per-determined size limit.

From this messy list of rectangles, a few are chosen to become large rooms of the dungeon.  The exact manner of room selection is still not something I have investigated in the original demo, but in my implementation I merely select the largest of the rooms so far generated.  I could also randomly select rectangles until one is found that matches some size threshold, and only then will it be added to the room list.

The next stage is to find out what rooms can be linked together.  In the original demo, a link is formed between rooms when it will not intersect any other room in the process.  To achieve this myself I needed to program a Ray-Box intersection algorithm.  I also know this will come in handy in the Tengu Engine, so it is worth my while choosing a good one to implement.  I found one in the front of the book “3D Games, Real Time Rendering and Software Technology” by Alan Watt and it was easy to code up a version from the description he gave.

Also since it was hard enough to find a decent 2D RayBox intersection routine on the web, I present my implementation here:

intersect.cpp
intersect.h

Each potential link between two rooms is tested for intersection with any other rooms, and those links that have intersections are discarded.  Thus I now have a list of random rooms, a bed of non intersecting areas to select from, and an edge list linking all of the rooms without intersection.  The only hard task left is to find the minimum spanning tree from these edges, and then to turn that reduced edge list back into corridors.

I made a video of my progress so far: