Map generation..

I've been pondering about automatic map generation lately.. I started to approach map generation few months ago, at first through creating QT based tool, that would run lua scripts and generate world. The approach was to create 'workspace' xml file, that contains all the worlds setup properties (width, depth, height, water height... ), list of available lua scripts, and run configuration of scripts aswell as how many iterations should the script pipeline run. In theory this approach is sound, and all.. but the hazzle with QT Xml parsing made me loose my will to live/code/develop/'to remain inspired' and the project became doomed because of it.

After that I've been developing my game engine framework and during this the map generation thing has been itching me.. Yesterday I started sketching about generating the maps, with set of tiny command line executables. Now where to start? creation of the 'grid' of course.. err.. wait.. grids have this bad property of having non uniform distances between points, the hypotenuse in the middle is not same distance away from each neighbour vertex in a primitive shape (thinking this in 2D flat plane).. So, lets try triangles, they seem nice, they seem easy to use too, and should LOD into groups as nicely as quads (so if I zoom away from the triangle 'grid' I can take 4 triangles to make 1 bigger triangle)..

Triangle points are uniform distance away from eachother.

Why is this important? well as the points/vertexes are the data points in the map, I think of them as 'sensor' spots, and to measure area properties in each spot fairly, those measurement spots should be equal distance away from eachother, always. With quads, that is impossible. Also, I feel that this should reduce distortions with the map in the end, as the only source for distortions at the time will come from adding the height dimension to the grid.

So triangle grid, creation of it requires length of the side of the big triangle, aswell as length of small triangle sides.. the command line executable should then be:

• grid -create -bigsize 1000 ...

oh wait, what is 1000 ? meters centimeters ? millimeters? feets?
lets define it to be meters!

• grid -create -bigsize 100000 -size 0.5

Still missing something.. selected algorithm ? and parameters for that? min,max?

• grid -create perlin -bigsize 100000 -size 0.5 -dimension 256 -min 0.0 -max 10.0

Ok so now we have specified that we want to use perlin noise function to create the terrain and for the seed we use 256 sized random texture (256x256).
Initially I tried to create a triangular texture algorithm for this, but that just was too much work and inventing a new wheel, where just a regular rectangular texture would suffice. I decided that it is too complicated and does not really contribute to the project to invent triangle textures.
Also about the data organization in the file, I've decided that it will be 'sharp end upwards' approach, so that the highest point where the width of the structure is 1 is first. The datatype is 32bit floats, using the computers architecture (I am not going to bother with endianess etc. issues) as the theory goes that this is just seed data, the final map, will use this as a resource on this machine, and the output that it produces, is something different, that can take all the funny technical fubar things into account (json?xml?).
First results with parameters:

• grid -create perlin -bigsize 10 -size 1.0 -dimension 2 -min 0.0 -max 10

 Running create.
Generating perlin BigSize: 10 Size: 1 Min: 0 Max: 10 Dimension: 2
3.48882
3.21913 6.07814
-0.416768 3.48882 2.15854
6.07814 3.21913 6.07814 6.53172
3.48882 -0.416768 3.48882 2.15854 2.15854
3.21913 6.07814 3.21913 6.07814 6.53172 6.07814
-0.416768 3.48882 -0.416768 3.48882 2.15854 2.15854 2.15854
6.07814 3.21913 6.07814 3.21913 6.07814 6.53172 6.07814 6.53172
3.48882 -0.416768 3.48882 -0.416768 3.48882 2.15854 2.15854 2.15854 2.15854
3.21913 6.07814 3.21913 6.07814 3.21913 6.07814 6.53172 6.07814 6.53172 6.07814

not really what I expected, the negative values shouldnt be there.. Few fixes maybe needed.

update:
I had few bugs in the perlin functions, it added too many times, scaled wrongly and all.. after fixing that, the generation is more healthy looking:
Running create.
Generating perlin BigSize: 10 Size: 1 Min: 0 Max: 10 Dimension: 2
created random seeds: 5.44206 4.15723 9.79308 0.682089
5.10193
5.42672 4.76487
4.7618 5.10193 5.02163
4.20711 5.42672 4.76487 4.76487
5.10193 4.7618 5.10193 5.02163 5.10193
5.42672 4.20711 5.42672 4.76487 4.76487 4.76487
4.7618 5.10193 4.7618 5.10193 5.02163 5.10193 5.02163
4.20711 5.42672 4.20711 5.42672 4.76487 4.76487 4.76487 4.76487
5.10193 4.7618 5.10193 4.7618 5.10193 5.02163 5.10193 5.02163 5.10193
5.42672 4.20711 5.42672 4.20711 5.42672 4.76487 4.76487 4.76487 4.76487 4.76487
except, for random seed to be 9 and 0.6, i dont see much of those..

Continued the editing, and the perlin noise map looks a bit, odd xD

A bit buggy generation..

Buggy fixed, Still couple oddities.

scenegraph..

The scenegraph.. provides a common relational structure, to present blobs of things that move,scale, rotate and do other things together, as whole. When an entity wants to take a ride on a car, the entity is put as the vehicles child node, meaning that the entity now exists in the vehicle space and the vehicle exists in the world space, so any change to vehicles world space coordinates, affects the entity too.
The scenegraph is made of nodes, and the nodes, in Bolt will be made of Matrix4x4, the node can have all sorts of properties, camera, audio, image, shaders etc. from these we can derive the stuff that we actually do.. Inheriting the node and creating a camera node? nah, just attach camera property to the entity that the node is representing and done.. This way any and every entity can act as a camera, giving options and freedoms for creativity  and
nodes, create scenegraph, have child/parent reletations, contain spatialdata of Matrix4x4 for location and orientation.. maybe also matrix to denote acceleration/speeds..
colormodifications? no, for now pure scenegrap, to denote 3 dimensional relations.
What else? containing script nodes? entities? the physics? or should the physics be put on totally different abstraction level?
The entity system can probably encapsulate anything.. tight integration of the physics and the scenegraph?..

camera class.. and the tools

Development of bolt has slowed down a bit, as I've been busy at work, and pondering and prototyping the tools (mainly the map editor). I am using Trolltech QT.. some impressive extension to c++, tools and abstractions for fast development for the map tool. First thing I did was the main UI, that is just opengl canvas + a toolbar, Afterwards came the sketching of world classes (World + Tile), which encapsulates the vertexes and polygons for each grid. Each grid stores the polygon & vertex data, created with tools (heightmap tools etc, to ease the sketching of landscape).

At the moment I am trying to solve the camera abstraction.. Many have solved it with using gluLookAt style solutions ( LeoLol java engine, camera class , three.js src ), one UP vector, one FORWARD vector and one RIGHT vector, that can be easily used to rotate and move the camera. The nice thing about these vectors is, that strafing the camera, is as easy as to add the result from multiplying RIGHT vector with the strafing movement speed. This solution seems to be quite popular, it is even directly in some graphics api (M3G , glut) and, it works.. But for my needs, I see this kind of structure, too complicated.. 
First I was going to just store the camera as position (Vector3D) + orientation(Quaternion) + projection(Matrix4x4), this approach would make the properties self explanatory, no scaling, no skew, nothing complicated.. but after further analysis, Quaternion needs to be converted into matrix representation for camera strafe/view based movement and for almost everything, the only benefits for Quaternions are size and unbeatable rotation calculations. So because of this, I am leaning on to use of position(Matrix4x4) + projection(Matrix4x4), so that the position will save orientation and location for the camera.

Components entities properties and heightmaps..

Currently I am in process of creating Component/Entity based architecture, more precisely, a pure component model based architecture, with sugar coating on top.


Sugar coating goes as far as to creating classes, that inherit from Entity, and the functions being just wrappers, that call different properties, set them, initialize them, create them. 
What has gotten me worried lately, is the granularity of the properties; at the moment I have the location properties, scenegraph properties, text properties, name properties as separate things, this could cause locality proplems.. One thing would be to combine LocationProperty and SceneGraphProperty, and pack the data tightly, hopefully increasing locality.
But on the other hand, this sounds like premature optimization, if needed, I can merge properties later on, creating SceneLocationProperty.


Well anyways, I removed the depthbuffer problem..

Another thing that I am pondering about is the landscape rendering, how to do a heightmap rendering? I thought of loading data from images, but that is too limited, having only 8 bits per vertex for height just doesn't cut it. Next I went and thought of loading obj files packed in gzip files and using somesort of quad-tree to organize different pieces of the map together. But this too is a bit of limited. My current idea is saving n obj files logically, in a tiled pattern to disk. mapname_LEVEL_X_Y_Z.obj where LEVEL is the 'level of detail' level and X,Y,Z are the indexes of the tiles, LEVEL 0 tile size would be 10meters*10meters*10meters and if such file was not found, then that level of LOD is not supported. The LEVEL LOD works using n^2, so that level 0 is 10m, 1 is 20m, 2 is 40m, 3 is 80m .. etc.

For test purposes, I will first implement this using obj files, later on, when I see some results, I might create either my own filetype for the data, or use some, more sophisticated format, than obj.

The third thing that I wanted to share, was these few C++ patterns, that I've started using, quite a lot..

First, the templated Singleton, with this the classes do not need to specify a singleton inside the class (reinventing globals! :D.. with sugarcoating.). 

Second pattern is the Merge class, that can be used to merge, through multiple inheritance, two classes into one. The verdict, whether this is good idea, is still out, but I like a lot about the idea of having the ability to merge std::mutex with whatever the mutex is meant to lock. eg. Merge< std::vector<int> , std::mutex > myVector; and locking the vector by std::mutexlocker lock(myVector); , this way I use it in the Pipeline.

Continuing on bolt framework

Some refactoring... I received some comments about the use of exception specification in functions ( virtual void foo() throws (std::exception); ) ( http://www.gotw.ca/publications/mill22.htm ). 
With exceptions I tried to convey the idea, that the function throws exception at error, but in c++, if the function throws something else than the specified exceptions, the program will crash and burn. The crashing and burning would probably create sleepless nights and odd error situations in the end, so I've decided to conform to 'no exception specification at functions' style.


Another thing that seemed like a good idea, in the beginning, is the const variables, ( void fuu( const float bar ); ).. the idea behind this, was that at the end of the function, you could still trust the bar to be what it was in the beginning. Totally useless concept, trust the programmer to know what he is doing, polluting the code with useless const's (many tiny reasons.) adds to code bloat, possibly slower etc. Use const with references.


Otherwise, I have added first test of landscape rendering, rendering a quad on bottom, unfortunately I forgot to take out the depth buffer clearing, so the tiny cubes, seem like they are behind the landscape.

Blogging.. I've never really paid much attention to them, I got the idea to start blogging, from my brother, as a way to clarify my thoughts about the tech, patterns and architecture.. techs that I create and use in my framework for games. The tech is heavily based on open standards, with plattform independency in mind..

The long term goal is to create a rpg game, loosely based on Kalevala, but also taking heavy influence from modern fantasy literature, games and modern fantasy culture.. So even though, Kalevala describes people as village peons, without any glorious kingdoms, I think, that kingdoms et al will be added..

The currently used tech in Bolt framework is:

• OpenGL (3.1+, preferrably going to use gl4.x)
• OpenAL
• glew
• glfw 
• C++11 (std::thread, templates, stl)