Programming, graphics, games, media, C++, Windows, Internet and more...
# RegScript - my Scripting Language
Wed
30
Dec 2009
RegScript is my scripting language I've started coding yesterday. I'm not a guru in formal languages theory, but I'm quite fascinated with programming languages, parsers and interpreters. I don't know why but I felt I'd love to write my own programming language so I just started coding it, even if it doesn't make any sense. Maybe that's just because it's like being the creator of something that we, as developers, are usually only users. The language syntax is similar to C++. Here are features I've coded untill now:
-10, 0xFFFF, 0b1010, 1e-6f, false, true, 'A', "foo"
+ - * / % < ?: ! && || ~ & | ^ << >>
= += -= *= /= %= &= |= ^= <<= >>= ++ -- == != < > <= >= ( ) sizeof ,
sin, print, intrinsic constants: PI.
The implementation is not optimal yet as I don't generate any bytecode. I just execute statements and evaluate expressions from a tree made of polymorphic nodes dynamically allocated by parser. Sample program:
print("Hello World!\n");
for (auto i = 0; i < 10; i++)
print("i = " + i + '\n');
Comments | #scripts #compilers #regscript Share
# Generating and Compressing AVI Video Files
Mon
28
Dec 2009
Yesterday I've decided to share all my home code using Project Hosting on Google Code, so now everyone can browse my code online by entering project called blueway. I'll be very glad to hear your opinions and suggestions about it.
Today I've researched subject of generating video data as AVI file, compressed on the fly with codecs installed in Windows. After succeeding with that I've created simple class to support this task, called VideoCompressor. You can find it in Video.hpp and Video.cpp. Test code is in ProgramMain.cpp, line 2318. It generates a 5 second video with a white horizonal line moving from bottom to top.
Here are some technical details. Functionality needed to handle video files is already inside Windows API, described in MSDN Library. The AVIFile library contains functions like AVIFileOpen, AVIFileCreateStream, AVIStreamWrite. It supports reading and writing AVI files. You need to include <Vfw.h> header and link with Vfw32.lib file. AVI is actually a container file format made of RIFF data chunks identified by 4-byte FOURCC codes (if you ever loaded 3DS models, you know what I mean). It can contain multiple streams like video and audio, which can be coded in many different formats, compressed and decompressed by codecs.
Compressing and decompressing frames of video with installed codecs can be done with Video Compression Manager library. You can display standard, system dialog window to let the user choose and configure codec with ICCompressorChoose function. Then you can just pass subsequent video frames as uncompressed RGB images to a function like ICSeqCompressFrame and you get a piece of compressed data that you can save to your AVI file.
Comments | #video #winapi Share
# Writing Parsers is Easy
Sun
27
Dec 2009
Using binary file formats is easier as data can be read and written almost directly as they are in memory, but sometimes we have to use some text formats. Whenever it is neither a standard format like XML or YAML, nor it is so simple we can load it with std::cin or scanf, we have to write a parser to read it. Writing a parser - code that reads and interprets some text format (e.g. file format or network protocol) looks like very complex task, but here I want to convince you that's not true - it is actually quite easy.
Why do I think so? It may look like it is a very long way from reading characters from a file till interpreting them as data records containing numbers, strings and other meaningful information. My answer for that is to split this problem into three layers.
The lowest layer is called CharReader. All it can do is reading single characters. It provides a layer of abstraction over reading data from a real source so you can forget whether you read from a file (hopefully with some buffering - never do file reads byte-after-byte!) or just iterate over a string fully loaded into memory. You can also forger about encoding so you see you data as characters, not bytes. It's a good idea to keep last read character somewhere so it can be "peeked" (read without losing it) many times before going to next one. The interface of a simple CharReader may look like this:
class CharReader {
public:
CharReader(const std::string &filePath);
// Returns last read character as out.
// If cursor at end, returns false.
bool Peek(char &out);
// Moves cursor one character forward.
void Next();
};
Next layer is called Tokenizer. We need it because it's still complicated to interpret characters directly as some structured information. Data in almost every text format is made of multiple-character pieces of information like numbers, strings etc. so it's convenient to provide another layer of abstraction to see data as a sequence of tokens, not single characters. Here are some typical kinds of tokens that can be found also in programming languages:
Tokenizer uses CharReader to read chars and interprets these chars as tokens. Just like CharReader, it buffers and provides access to single token that was parsed recently so you can read it many times before anvancing to next one. It's also Tokenizer's responsibility to skip comments and whitespaces between tokens. Example interface may look like this:
class Tokenizer {
public:
Tokenizer(CharReader &cr);
enum TOKEN_TYPE {
TOKEN_END,
TOKEN_IDENTIFIER,
TOKEN_STRING,
TOKEN_SYMBOL,
};
// Returns type of the last read token.
TOKEN_TYPE GetType();
// Returns content of the last read token.
const std::string & GetContent();
// Moves cursor one token forward.
void Next();
};
And finally, when being able to see file as made of tokens, it's easy to code the third layer - Parser - on top of that. Parser reads subsequent tokens and interprets them as some meaningful data. For example, you can parse a Key="Value" pair by expecting token of type identifier and saving its content as Key, then expecting the (=) symbol and finally expecting a string token and saving its content as Value. Of course you also have to find a way to report errors on all these stages, including information about current row and column.
# Coloring of Fractal Flame
Wed
23
Dec 2009
My next step in Fractal Flames rendering was to enhance the way I give colors to pixels on the final texture. As positions of the points iterated through the function system are discretized to a 3D matrix, but before it's processed into the final texture, I've introduced a choice of matrix format (inspired by texture formats in DirectX).
The simplest one is MATRIX_FORMAT_DENSITY, as it has only one component per cell - a density, equal to number of points that hit this particular cell. No coloring is done here, so each pixel is just white and there is only density influencing its brightness through tone mapping.
Second format is MATRIX_FORMAT_COLOR_DENSITY. It works similar to what is described in The Fractal Flame Algorithm paper. Each processed point carries a "color" with it, but this "color" is just a scalar value in range 0..1. Every possible transform (transforms are chosen in random manner according to their probabilities) pushes the color towards its "desired" value, defined for each transform. Current point color is added to the matrix cell so that final color is an average of colors of all points that hit this cell.
To visualize this scalar "color", it's nice to process it through some lookup table, gradient, palette or however you call it. I seems easy to generate or hardcode one, but I prefer to rely on existing gradients prepared by more talented people, so I've implemented reading of two gradient formats so far: gradient from a single-row texture or from a "cmap.UGR" file shipped with Apophysis (nice, free Windows application that render fractal flames according to the paper mentioned above). I'm also planning to support "ggr" files with gradients from GIMP, but it's far more sophisticated and powerful format.
And finally there is the third way of coloring fractal flames that seems most intuitive to me - MATRIX_FORMAT_RGB_DENSITY. Here, full three color components are carried with points and saved to the matrix. Each transform pushes the point color towards its own "desired" RGB value. Thanks to this, each transform influences not only shape, but also color of the fractal in direct and observable way (like the scaling transform here, that shrinks points to the center, which is red).
Comments | #math #fractals #rendering Share
# I Render Fractal Flames
Sun
20
Dec 2009
Continuing my learning/research of fractals, today I've finally managed to render something that looks like Fractal Flame. AFAIK the most important paper on this subject is The Fractal Flame Algorithm by Scott Draves and Erik Reckase. According to this document, I've first added to my program the ability to use colors, so each point, as it has the position iteratively processed by some functions, also carries current color. Now I am able to render colourful IFS fractals:
Implementing logarithmic tone mapping and gamma correction significantly improved quality. Colors can help visualising internal structure of a fractal:
Next I've coded (almost) all functions mentioned in this paper, so now not only affine transforms are possible in my program. This allows me to mix traditional fractals with new functionality:
And finally to render something that looks like famous Fractal Flames. But it's not easy to achieve this. Modifying numeric parameters in a text file is not convenient, and even if I had an editor with real-time preview, it's not obvious what parameters give what results and whether they will degenerate to something like a single point. There are simply too many degrees of freedom :) If we had a continuous function Beauty(Params), we could use some optimization algorithms to find and render its local extrema :) Anyway, here are my first renders (more in Fractal Flames Gallery).
Comments | #rendering #math #fractals Share
# Few Words about Interactive Fiction
Thu
17
Dec 2009
My today Google-Wikipedia "research" was about interactive fiction. I've only heard about MUD-s before. MUD (Multi-User Dungeon) is a text-based, multiplayer game genre that precede current MMORPG games. Interactive fiction are also text-based games where player reads descriptions of things (like "You are in ... now. You can see ... here.") and types console commands (like "go west"), but they are single-player and more story-oriented rather than being about the mechanics of combat and magic.
The history of interactive fiction is older than me, as it started in 70's long before personal computers era. There have been some commercial games of this genre released in the past. Today interactive fiction is still alive thanks to the Internet community. (BTW: I didn't know before that the famous metasyntactic variable "xyzzy" originates from math, where it helps to remember the way of calculating cross product of 3D vectors :)
From more technical perspective, all sources I've read agree that it makes no sense to start coding a new platform for interactive fiction, as there already are some great ones out there. For example, there is this Z-machine standard (see The Z-Machine Standards Document) that is still in use despite being very old and has interpreter implementations for numerous platforms. One could think that it's kind of a description language like XML, but it's actually a virtual machine with opcodes etc.
It's also worth seeing some of the tools interactive fiction creators use. I've read a bit about Inform 7 - a free, multiplatform IDE with its own language to develop IF games (and also debugging functionality). Rules of this system remind me of Prolog at first glance. There is much built-in mechanics already available, like visiting rooms or taking items. But at the same time it's very flexible, so e.g. there is an extension available coded in this language that introduces metric units. The syntax of this language is totally weird as it looks like... English language. Just see manuals. Programming here is like writing a book (much like the Shakespeare Programming Language, but this one is not esoteric). Sample code: "The Gazebo is a room. The wood-slatted crate is in the Gazebo. The crate is a container.". Parsing player commands is also very sophisticated to resemble using natural language. Everything here is like reading or writing a novel - even compiler errors :)
I've always dreamed about writing a platform for text-based games that would be so general, flexible, powerful and would model the world so comprehensively. Now as it turned out that systems like this already exist and evolve for decades, there is not much to do here for a programmer like me. Especially as I don't feel like writing a novel, even interactive one. But anyway it's nice to know what interactive fiction is.
Comments | #history #web #games Share
# Releasing CommonLib 9.0
Wed
16
Dec 2009
After 13 months since previous release, today I want to share all who may be interested the new version of my CommonLib 9.0. As a reminder, it is a universal library for C++, created especially with game programmers in mind. I share it under GNU LGPL license hoping that at least some pieces of this code can be useful. Important links:
The new version contains massive amount of my recent code which proved to be useful to me and have been tested in my home projects. Among all these changes, bigger ones are:
For more information, see What's New in Version 9.0.
Comments | #libraries #productions Share
# Further Experiments with Fractals
Sun
13
Dec 2009
Today I woke up with an idea of inventing my own simple IFS fractal with four pieces sheared or rotated to form a hole in the center. I must admin that effects are not impressive :) What I've learned is that it's difficult to imagine how overall fractal will generally look like when you design affine transforms for a single step that will be processed recursively. But anyway I'll show my results, with single step on the left and final render on the right:
Shear transform which unexpectedly formed round shapes:
Rotation transform with boundaries exceeding -1..1 range:
Rotation transform bound in range (-1..1, -1..1):
Comments | #math #rendering #fractals Share
# Random Choice with Given Probabilities
Fri
11
Dec 2009
When we want to randomly choose one option from some possible items, we usually do something as simple as (rand() % numberOfItems). But what if we want to vary probabilities of these items? Here is an algorithm for this:
As input data, we have number of items and an array of their probabilities. Each probability is a nonnegative real number. I like to allow these numbers to be as big as I want, knowing that an item with probability 2 (or 200) is just two times more probable than the item with probability 1 (or 100). I will normalize them later.
// == Preprocessing step ==
// Input:
std::vector<float> ItemProbabilities;
// Output:
std::vector<float> ProcessedProbabilities;
// Algorithm:
size_t count = ItemProbabilities.size();
assert(count > 0);
// First pass: summation
float sum = 0.f;
for (size_t i = count; i--; ) // count-1, count-2, ..., 0
{
float p = ItemProbabilities[i];
assert(p >= 0.f);
// Optional: Delete items with zero probability
if (p == 0.f)
{
Items.RemoveByIndex(i);
// That's how we delete an element from std::vector by index :P
ItemProbabilities.erase(ItemProbabilities.begin()+i);
}
sum += p;
}
assert(sum > 0.f);
float sumInv = 1.f / sum;
// Second pass: building preprocessed array
ProcessedProbabilities.resize(count);
ProcessedProbabilities[0] = ItemProbabilities[0] * sumInv;
for (size_t i = 1; i < count; i++)
ProcessedProbabilities[i] =
ProcessedProbabilities[i-1] + ItemProbabilities[i] * sumInv;
The algorithm above does two things: It prepares ProcessedProbabilities array so that each probability is the item's probability plus the sum of probabilities of all previous items. It also normalizes them to range 0..1. As the result, the output array forms an ascending sequence, where the difference to the previous element is proportional to the item's probability in respect to full 0..1 range. For example:
Input: 100, 100, 200 Temporary data: count=3, sum=400, sumInv=0.0025 Output: 0.25, 0.5, 1
Now as we have these preprocessed data, generating random choices with certain probabilities is fast and simple. We just generate a random real number in range 0..1 and choose the first item for which ProcessedProbabilities[i] is greater than this. Additional optimization would be to use binary search here.
// == Random choice ==
// Input:
std::vector<float> ProcessedProbabilities;
// Output:
size_t choice;
// Algorithm:
choice = 0;
float randNum = RandFloat(); // 0..1
while (choice < ProcessedProbabilities.size()-1
&& ProcessedProbabilities[choice] < randNum)
{
choice++;
}
Comments | #algorithms #math Share
# Rendering Mandelbrot and Julia Fractal
Thu
10
Dec 2009
I've been playing recently with Mandelbrot and Julia sets. These are fractals rendered in the completely different way that my last experiments with IFS (Iterated Function Systems). In IFS I had a set of points with given (x,y) positions and I've been transforming their positions iteratively by some functions before I rendered them. I'll blog more about IFS another time. Rendering Mandelbrot and Julia fractals is more like writing a pixel shader - for every pixel on the screen with its (x,y) coordinates we do some computations to calculate final color. I didn't extend my framework to render such things yet, but instead I've been doing my experiments in EvalDraw (where I can freely pan and zoom the view) and AMD RenderMonkey (where I can write pixel shaders executed on GPU).
Complex Numbers for Game Developers :) Fractal is a mathematical concept and so there is lots of hardcore math involved in the foundation of these beautiful objects. But fortunately we don't have to understand all that stuff to be able to render them. Mandelbrot and Julia fractals are created using complex numbers, but for us they can be thought of just as float2/D3DXVECTOR2 2-component (x,y) vectors with some operations defined:
That's actually all we need to render Mandelbrot and Julia fractals. The general formula for both of them is: z = z^2 + c where z and c are complex numbers, c is a constant and z is recalculated many times through this function. It was a mystery for me for a long time how to apply this formula. Now it turned out that when we calculate it many times for each pixel with staring z_start = (0, 0) and c dependant on pixel position in range (-2..2, -2..2) and draw all the pixels for which z is bounded and do not go to infinity, we get the shape of the Mandelbrot fractal. Of course we are not going to iterate this function inifinite times in our computers like mathematicians do in their heads, so instead we do it several times and treat all pixels for which length(z_final) < 2 as being "inside" the shape. Here is a draft made in EvalDraw. Unfortunately we meet some limitations of floating point numbers here, like limited precision and infinites and that's why the space outside is white.
To render Julia set we do something similar, but this time we use pixel position as starting z and set c to some constant, like (-0.1, 0.7). Different constants make different images.
A question arises about how to render a fractal - how to map a complex number to pixel color? The algorithm I like the most is called Escape Time Algorith and it goes like this: recalculate z for several iterations, but only while the length of z=(x,y) vector is less than 2 (that is zx*zx + zy*zy < 2*2). If the loop reached the iteration count limit, this pixel is inside the fractal - draw in in black. If not, then color of this pixel depends on number of iterations done.
Here are my implementations of these fractals in EvalDraw and RenderMonkey. They are very simple so the whole source code is visible on the screenshots. You can also download the code here: Fractals_for_RenderMonkey.rfx, Mandelbrot_for_EvalDraw_1.kc, Julia_for_EvalDraw_1.kc, Multibrot_for_EvalDraw_1.kc. You can find more screenshots in my fractals gallery.
Some variations of these fractals have also been discovered. For example when we do absolute value of z components before every iteration in Mandelbrot fractal, we get an interesting shape called Burning Ship.
Alternatively, if we raise z to any real power instead of 2, we make Mandelbrot fractal "unfolding", having more and more "bulbs" as the exponent grows. It is called Multibrot set. Raising a complex number to power with any real exponent is a little bit more complicated, as it has to use polar form (HLSL-like pseudocode here):
float2 ComplexPow(float2 v, float n)
{
float len = sqrt(x*x + y*y); // Standard 2D vector length
float n_fi = n * atan2(y, x);
return pow(len, n) * float2( cos(n_fi), sin(n_fi) ); // scalar * vector
}
Comments | #rendering #math #fractals Share
# New Fractal Renders
Sun
06
Dec 2009
Continuing playing with fractals, I've improved my experiment framework so now I can render any IFS (Iterated Function System) fractals described by a set of affine transformations with subpixel quality. Here are my today renders (these with colors are processed with GIMP). You can find more in my Gallery / Fractals.
Where do I get information from? There is a great website with ready formulas for each of these fractals: Classic Iterated Function Systems by Larry Riddle from Agnes Scott College.