LL3DLGLD – 1 – Brute force

Welcome to LL3DLGLD (Let’s learn 3D like good little dragons) my new (hopefully) short (because I learn fast?) series in which we learn together to create a high performance but probably rudimentary 3D engine capable of displaying a DwarvesH map in real time.

Hopefully I will be able to both demonstrate what issues arise and how to fix them, or at least compromise until we reach something playable.

At first I will be doing my research with pure Irrlicht, with the new nascent engine not being aware of DwarvesH.

In the first phase I’ll create something capable of rendering the complex geometry of a map, but without plants, trees and other decorations. Just the raw shape of a map. I will also be skipping on floors to simplify the initial complexity of the problem. So, our problem in its integrity: given a 3D boolean matrix, where the value true represents the presence of a block, and the value false represents the absence of one, render it using 3D polygons. Performance must be as close as possible realistically to the best performance you would get if you would feed the optimal polygon list to the hardware on each frame, disregarding computation times. We can simplify the problem even more by considering the matrix a set of planes one on top of the other.

A naïve implementation would say: “Cubes? No problem! We’ll just create a cube for each cell in the plane if it is set to true”. But this won’t work for too long.

Without further ado, here is a textured cube without lighting created with its center in the origin of the coordinate system:

This looks like a top down 2D mode, but since it is polygonal and hardware based, there are a few things to consider, like how the texture used is absurdly high (1024x1024), yet the framerate is over 700 and most importantly, one can swing around the camera:

The hardware is also capable of applying textures in a non ugly fashion with different filtering options and does some funky stuff to reduce its workload as the parts of the object are farther away from the camera:

Now that we have one cube, let’s create one for each cell in the plane. For starters, we’ll consider the plane to be 11x11 cells and I’ll show you a few screenshots showing the slab from different angles:

I don’t know about you, but I am starting to get lost. From what angle were these screenshots taken? How does the 3D coordinate system work? Let’s try and create a few helpful markers:

The block with the “-5 -5” texture has the X and Y coordinates of -5, the block with the “5 5” texture has the coordinates of 5 and the one in the middle zero of course, with all Z coordinates being 0. We are using a left-handed Cartesian coordinate system (I don’t know if one can change this to right-handed). Supposing that we are looking exactly at the origin like in the screenshot (point 0, 0, 0), anything to the right of the center has positive coordinates and the same for anything above it. As we get closer to the camera the Z axis decreases and the space between the camera and the origin has negative Z coordinates. It is very important to be extremely comfortable working with this system and to have a good mapping from logical map coordinates into real 3D coordinates. In my case, I will probably have to start at a point in the positives on the Y axis, and decrease it going to the same value in the negative. Now we can add a few extra blocks on top of this plane using a skipping pattern, so we’ll add the cubes at a Z coordinate of -10, using a darker texture:

One thing that is immediately apparent is that the FPS camera from Irrlicht is not facing the way I want it. It would help a lot if I can use this coordinate transformation convention, but the camera is centered on the Z axis and I would like to be along the X or Y axis. I do not know how to fix this yet, but it is not important right now.

So why won’t this approach work? Let’s ramp up the number of cubes by adding 20 cubes to the X and Y dimensions:

Wow, check out that framerate drop. Now let us consider a realistic map of 300x300, but with its height reduced to only 2 (from the default of 60). So not that realistic actually:

The framerate dropped down to 3 and the camera refuses to zoom out even further. This is the core of the problem, the reason you can’t just place object on the scene like you would do in a 3D program: if you have a fair amount of objects, the number of objects becomes a lot more important than the number of polygons. To give an inaccurate example in order to illustrate this system: if your graphics card can run at a smooth frame rate with one object with 100 million polygons, it will have a considerably lower framerate when rendering 100 objects with 1 million polygons each, even though the total number of polygons and their location is identical. One cannot even use normal LOD techniques: the objects I am rendering are cubes! How do you expect to lower the level of detail even more than a cube? The answer is you can’t and you need both to cheat and actually do not render some objects that should be visible and also find ways to recreate the same scene visually, but by using fewer objects.

We’ll ignore the added little darker cubes and try to create a map geometry renderer capable of rendering the entire plane with a good framerate, using only a few objects. This is what we are hoping to get, but with a framerate of at least 400:

54 – Sandy doom

This post is probably going to have some unhappy conclusions, so in order to compensate I’ll have a few Lolcats open in a browser window while I write this post.

I have been working on a system to allow for dynamic zoom levels, not just the fixed ones. There are two causes for me wanting this. First, while I was experimenting with getting new graphics and talking to third parties, the gravity of tile size choice become apparent. Doing isometric graphics that look good is hard. Working with small tiles is hard. Isometric tiles edges have very special rules. Combine these and we get quite a difficult task. Artists complain that there is not enough space. Due to the rules you cannot scale tiles up easily and scaling them down is also a lot harder than necessary. And due to these difficulties, asking for the same tile in two different sizes often doubles the cost. So if I want tiles designed by artists, I need to stick with one, at most two sizes. This wouldn't be a problem. I always had one size and the zoom levels were generated by dividing the size with 2 and 4.

Here is where the second problem comes in. 32 pixel tiles are too small for modern monitors. With 1080p monitors becoming quite common, you would have to be really close to the monitor or squint you eyes to see what is going on in the game. On the other hand, if you do not have such a large monitor, the large size is a disadvantage. There is no one size to rule them all. Zooming is a must. 3D engines do not have these problems because you do not work with pixels and it is fairly simple to keep the same proportions.

So I tried to create a dynamic zoom system, where both shapes and content for tiles can be created procedurally and for cases where more is needed, 2D textures can be applied on the surface of these shapes. Using these techniques I created an algorithm that created the entire tileset for the game (leaving out some stuff for now).

But this approach has a whole lot of flaws:

• Applying textures is ugly. It will take a lot of time (if ever) before I can improve this. Probably need to use a software trilinear filtering inspired by 3D graphics.
• Procedural generation is not that easy. Every shape needs a separate algorithm. Sure, after you do it once and start to pile up on algorithms that you can combine, it starts to become easier and easier.
• Procedural generations is slow. The total tileset for all size will take minutes even on strong machines. So you can not generate them on the fly, i.e. every time you zoom. You need to cache them on the hard disk.
• I could not find a way to edit textures with Irrlicht. Or at least tell it to use/convert an in memory bitmap. Irrlicht actually has extremely poor 2D image manipulation capabilities if I am not mistaken, and I think this is intentional. So I need to create the procedural graphics with U++, save them to disk and load them with the Irrlicht API. Making slow things even slower.
• You cannot cache them in RAM. It is not easy to tell, but even now, DwarvesH has thousands of tiles. By the time it will be done it will have at least 3 times as many tiles (adding buildings, animals, ores, gems, …). With PNG compression, the cached tileset occupies right now 105 MiBs of disk space. Of course, one cannot store PNGs in video memory. In raw bitmap/texture format, the tiles occupy 240 MiBs, and this only with 24 bit colors. I can’t even imagine how much space these tiles would occupy with 32 bit colors. The math on that would be really crazy. *snark* Do you see how my game looks like? There is now way I can say with a straight face: “Yes, this game requires 512 MiBs of video RAM.” So I must load from the disk only as much as needed.
• Even if you load as much as needed, the large number of tiles means that a lot is always needed. At big tile sizes, loading all the needed tiles from disk takes a while. Not that much, but enough so you do not have smooth zooming like you see in some games, where you touch your mouse wheel and instantly everything has zoomed.

I think these are the major disadvantages. Sure, 2D isometric is passé, but my engine is quite impressive technically, if I do say so myself. I’m sure it can be improved and there are other people out there who can write at least as good of an engine as mine, but this does not change the conclusion: my engine is very good and very fast. It can be ported in hours to any API that can draw a portion of an image to given set of coordinates. I could easily do a SDL, Allegro, pure DirectX or any other hardware accelerated graphics platform out there. It is quite fast in software mode too, but software is always going to be slower than hardware, pretty much by the definition of dedicated hardware components.

But the new dynamic zoom my engine does not feel that good any longer. It feels less capable technically speaking, even though it is smarter. I uploaded this first video, where you can see it action:

In this video I have some strange stutters and generally speaking I am not that happy with it. I spent over an hour trying to find the cause of the stutter, only to realize that it was not the fault of the game. After hours of working on the engine, with the IDE launched, countless compiler sessions, Opera, Firefox and Chrome launched, FRAPS and VirtualDub launched, my system stability and load was not at its best. After a restart of windows, the stutter disappeared. I did a second video, without stutter and at a higher resolution:

I do not know exactly how to proceed. The old engine is good. Dynamic zoom is challenging, but in the end good, but it will always be too slow.

But the thing that bothers me the most is that this highly tuned 2D engine that does so much is still technologically inferior to a half-assed 3D implementation.

I guess I really need to go with the 3D one. Polygons are more powerful than the pixel. I have repeatedly failed to create a good 3D engine. Without prior experience, one cannot sit down and just write a 3D engine. Which is surprising, since one can just sit down and write a DF inspired game.

So this new try with a 3D engine needs to be different:

• I will be working very slowly on it, taking time to learn the ropes first. Primary development will be centered on the 2D engine.
• I will be using some third party 3D engine, no longer creating something from scratch. Probably in the first phase, I will be retrofitting an existing project to be capable of displaying maps from my game.
• In the first phases I won’t care about speed. If I can create a good 3D engine that feels right, but is too slow, I won’t mind. Things can be improved latter.
• I won’t be afraid to ask help!
• It will look ugly! OK, this part won't be different then :P.

So in conclusion, 2D development will continue, only a little bit slower while I dedicate some resources to 3D. If someday the 3D engine becomes primary, I would hate having my effort in the 2D engine go to waste, so I need to figure out a way to keep it alive and useful. Suggestions are welcome.

Ohh, one more thing. I missed the 3rd of September window, but I promise that I won’t miss the 4th of October window. For this date I had scheduled the first version of the editor to be made available and I’ll stick to this plan, even if I have to use RapidShare. Sure, things will be launched a little bit out of order, as the editor by itself is not that useful. I need to release after at least a tech demo so you can load up the stuff from the editor.

Anyway, baby steps.

Screens of the day 17 - Cats

Today we are going to combine the two new tehniques: creating dynamically sized shapes filled with a procedural pattern and converting a 2D texture to an isometric texture that can be applied on the before-mentioned shapes.

Let us take this random grass texture that I found by googling "grass texture":

This is not a good texture to use because it is big and detailed and my result will be small, thus dropping a lot of detail. Still, let us try an see what we get:

Not bad! It looks like it is gaining detail rather than scaling up, but I am still not 100% happy. Let's try another random grass texture:

Converted, it looks like this:

Something is not right there. Look carefully! I'll try a more distinct texture to better observe the behavior:

The conversion result is clearly wrong (except for the GIF pallet; GIFs use 256 colors and my images do not use pallet optimization and dithering to compensate for that). I'll illustrate this by using this cute cat:

Aha! We can only see the head. There is a bug in the scaling algorithm. Let me fix it:

Normally I'd go back and fix the previous sample images, but since this blog is a lot about documenting, it is OK to document the bugs too.

The process works of course for larger sizes too: 

This is why I wanted to try a 3D engine again. It comes with great flexibility and you get a lot of things for free. But I guess I will be sticking with the hard way.

The final step is to take these techniques and create the first prototype of the new and experimental Flexy engine!

Screens of the day 16 - Texturing

Right now I am experimenting with procedurally generating the entire graphics in order to try an almost pseudo 3D like capabilities engine, or more precisely flexibility, but done fully in 2D. 2D engines generally can't do a lot because of the constrains of isometric tile sets and I am aiming to eliminate some of these limitations.

Some tiles can be procedurally generated and some tiles only need to be resized with some special filter to preserve edges and contrast with the background. But it is inevitable that some tiles must be hand drawn at multiple sizes. And doing isometric tiles is kind of hard. So I am experimenting with converting 2D "textures" into isometric tiles. This way you need one texture with a fixed size and maybe you can generate the isometric tiles you need by using layers and coloring.

So let's take some 2D textures. These textures are actually obtained from isometric tiles that were converted to 2D textures and now I am converting them back. The process is going to be lossy. You know what they say about a copy of a copy...

I'll take this generic pink rock pattern and apply the conversion:

The shape is correct, but it does not look that great. Using a slightly less monotone texture gives better results. From this:

We get this:

This is much better IMO. You can see that it is the same pattern.

But doing such smooth patterns tends to hide the problems. Te real challenge is having a conversion that handles very high contrast textures. The kind JPEG compression usually ruins. Let's take this simple pattern:

And convert it: 

Hmmmm. Not that bad. Some ugly vertical tearing, but generally still recognizable.

Keep in mind, I am making up all of these procedural generation algorithms. Those who study such things before hand probably get a lot better results. What do you think about the entire procedural generation of graphics thing?

Screens of the day 15 - More procedural trials

I adjusted the algorithm a little bit, and here is a possible sand cube:

And of course, we need floors too:

Progression seems smooth enough but I'm curious how it will work in game.

Here is the first interface element, a stockpile marker:

The algorithm is not that good yet, because it messes up with at least the color red:

Screens of the day 14 - Pulse

I am a little late with the entire IndieDB operation. I did not anticipate correctly the amount of administrative and otherwise not codey tasks that need to be done. Oh well, a couple of weeks delay won't be the end of the world.

Meanwhile, I took a new swing at the 3D engine thing and I failed again. First I tried to do a 2D isometric engine, but with the world drawn with the help of 3D polygons. It was fast and seemed promising, but I just couldn't figure out a way to make it not ugly. Then I tried a traditional full 3D engine, but with an orthographic camera. I may have failed both tries, but I did learn some important lessons, and now I can tell with a reasonable amount of certainty that DwarvesH, because of its inherent complexity and requirements for the engine, will have a 3D engine if and only if all of the following condition are met:

• I acquire very good theoretical knowledge about 3D worlds, the math behind it and the practical implications.
• I have worked extensively with a 3D engine for at least a year.
• I have spent at least 3 months doing nothing else on this project except implementing the 3D engine.

So this task is put on hold, maybe forever.

The whole 3D revival was due to some events that happened while I was trying to get new graphics. I should post a collage with all the experimenting here soon so you can see how much friking work it is try and give a good look to such a game .

Anyway, I am in the process of adding a few more features to the 2D engine. Take this cube as example:

"My what a pretty cube! Did you draw it yourself?" is what a sarcastic reader might say. I know it is ugly and I did draw it myself. Procedurally! It is actually supposed to be stone, but it turned out more like sand.

This is not the first time you see something procedurally generated here and this process still has the same properties, including slight differences at every generation so nothing looks exactly the same twice. But the new feature is that this time the resulting size is no longer fixed. I can generate such cubes at all size, but due to the way isometric tiles work, multiples of 4 are preferred. Here is a animation demoing the generation process:

Two of each

Wow, not only did I switch over to Google Chrome because Firefox was just full of bugs when working with Blogger, but Blogger has offered me the option to switch over to a new interface and now I can't find anything. Oh well, maybe this new interface will prove to be better. Blogger is not as good as WordPress IMHO, and I am starting to regret having created the blog on Blogger and not on WordPress.

Anyway, getting sidetracked.

I've been kind of busy, yet I think we can call pre-alpha-3 finished. I looked over the planned feature set and except for snow, buildings and crafting, everything is done. Instead of these MIA features, we have some new ones that were not planned. I'll probably post and updated feature list, but the important thing I need to talk about is that this model is not working.

Choosing a feature set that seems like a good idea and working for months to complete this list, while my plans for the game evolve naturally, often invalidating the list, is not a good idea. I would probably work if there was and organized developers team, but it is just me.

Instead, from now on I will set smaller goals that can be designed, tested and implemented in 1-6 weeks. The goals will also be able to be developed in fair isolation, so that the code base feels like getting and add-on, not a rewrite. Since there seems to be no escaping the subject of Dwarf Fortress anytime soon, I'll add fuel to fire and call these goals arcs. There are two types of arcs. The first type is meta arcs, that have no real content of their own, but consist of a lot of normal arcs. These meta arcs try to bring a big feature to the game, and the division into small arcs helps with developments and tracking.

Currently, I will be tracking four meat arcs:

1. "Take". This arc consists of all the operations that involve a dwarf, a tool and doing one single action that changes the environment, often taking or modifying natural world resources. This is what I have been largely working on up until now and consists of all the operations one can do on walls, plants, stockpiles, etc. This meta arc is largely finished, but one last pass must be done on floor and wall building from boulders and bricks. Also, the carve list is not customizeable with the editor, which seems like missed potential.
2. "Build". This meta arc consists out of one functional component that serves as the framework for defining and building structures and one arc for each building. I will be executing this meta arc based on plants: for each produce for a plant I will add the necessary workshops, checking of arcs as I go.
3. "Wear": a meta arc governing a very complex wearable equipment and clothes system for dwarves.
4. "Fight": the fighting model. I am not sure yet, but I am starting to feel like combat is going to be turn based. Think Heroes of Might and Magic, but with fights on the entire map and each dwarf having special attacks based on their weapon skill. An untrained fighter will just try his best to make contact. A trained fighter will have the option to try and take advantage of holes in the opponents defense and hit sensible spots, causing extra effects with a greater chance.

These four meta arcs are actually the post "Stoneage" version of the game. Rather than having to worry about the entire feature list, I have small goals that I can try and implement one by one.

I'm hoping this system will be easier to manage.

As for the IndieDB launch, I am working on it right now, but it won't be up today. Maybe not even tomorrow. Should have not scheduled something like this for the weekend.

PS: I am starting to like the new design for blogger. Still a bug or two. Give it more time...