Friday, December 17, 2010

21 – Hollow Earth, part two

After the lengthy explanation from last time let us jump right in, and only draw front-left and front-right sides for floors only when they are needed. The world becomes quite black:

Turning on multi-level rendering we can see how few tiles need to get rendered. Keep in mind that there is on layer that covers everything like a sheet on a bed that is not visible right now:

Then, for the first time ever, we draw the top side of floors:

And then of walls:

Dwarftastic!!! Everything looks like it looked before and the frame rate is pretty much the same. But, if we turn on multi-layer rendering and scroll to the side of the map where it is the thickest, we get this result:

The thing to note is the FPS in the title bar: 91! This used to be around 20. And with single-layer rendering, we get 108. The actual numbers are not important, since they change a little based on the content of the map and a lot based on the hardware that you are running it on. What is important is the relative difference between them. Going from 100 to 20 is very bad. Going from 100 to 90 is negligible. So it seems that all the effort put into this algorithm has paid off.
One thing that you will notice is that there are black squares where I dug out the floor. This is because in the past, it was only an illusion that we are not on level 0 but on level 1. I used some tricks and faked and extra level when needed so that I didn’t have to render another floor. Now I removed this hack and we are on level zero, so there is nothing below it when digging.
Since we now have this great engine that is capable of drawing multiple levels fast, let us change from level zero to level 10 for now. That is 10 extra levels. The problem is that I have hard-coded zeroes everywhere in code. After changing that in a long and arduous process that I am not going to talk about any more, we get this:

Perfect! And this is with levels zero through 10 drawn. There is no longer the distinction between single- layer and multi-layer rendering. Now you can choose between levels 0 and your current level and rendering of the full height of the map. This also means that you can lower your current level to underground, and become completely lost because everything is uniform rock. This is also a problem in Dwarf Fortress. You can get lost so bad that you need to zoom over to your expedition drop point. You do know the keyboard shortcut for that, don’t you? Fun times...
So let us scroll over to the side of the map, enable full-map rendering and check it out:

Pretty thick. That’s what she said! The new rendering engine is not quite map height agnostic, but it is lot faster than before. And there are a lot of performance tweaks to be made yet, especially since I was quite in a hurry with the implementation. Anyway, this is not a game in which you will need hundreds of FPS. Going up to you screen refresh rate is fine, but there isn’t a lot of benefit in going further than that. The tricky part is getting the required FPS on old hardware. Right now I am only rendering worlds of 300x300x20. I would like to increase that if possible. Horizontal dimensions are easy to increase, they only eat up memory. Vertical dimension increases have negative effects on FPS.
This concludes my two part mini-feature on the new rendering engine. The code is written in such a way that later I can replace the drawing of a side with the placement of four vertexes in a vertex buffer and I already have all the visibility factors computed for a relatively painless transition to a true 3D engine when the time calls for it.

Thursday, December 16, 2010

20 – Hollow Earth, part one

As said last time, the only way to speed up rendering still left is to draw fewer tiles. But in a multi-layered 2D isometric game, where a wall tile is a single sprite, determining when something covers something is both difficult and costly in CPU power.
So let us suppose that we have a 3D world. While this world is not made up entirely by cubes, floors and walls are made up by rectangular 3D shapes that we can abstract as cubes. So how would we proceed in a 3D game? We would use one of the well-used and documented methods, like octrees. Octrees are basically cubes that are divided recursively into 8 cubes. These have interesting properties that are useful in 3D rendering engines. Or so I’m told. I never used them and I can’t write an octree implementation of the top of my head. I could with a little bit of study. But let us try something different.
Coming back to our 2D game, the idea is to split up the single tile of the walls into multiple “polygons” like you would do in 3D, and only draw the ones that are adjacent to a free space. We only draw the “borders” of the world. Hollow out the world. This should greatly speed up full multi-layer rendering, where all Z levels are drawn and which currently is unplayable, having with all optimizations a FPS of less than 20 while on the same computer single layer rendering is well over 100.
I’ll proceed and visually walk you through the process since this is not a technical blog. So let us start with a normal world, where walls are drawn by a single sprite:

Now, since the “camera angle” is fixed, we don’t have to worry about all sides of our cubes. At most, only three sides are visible, that is the ones in the front. We have one on the left, on the right and one on the top. So let us draw only all the ones on the left: 

Where is the gain in this? Well, first we need to only draw the sides that would actually be visible, not all of them. If we do that, everything will disappear. While all other sides are not drawn yet, they still would cover the ones on the left. So I cut out a small corner where two of these sides are seen:

Actually, let us cut out a few tunnels, so we can get a better look. All black parts are not rendered and should be invisible since they are covered by top layers. When enabling single layer rendering, the top sides of walls will be forced to render, but we’ll talk about that another time. This is the result:

Something you may notice is that floors seem to be drawn in a strange manner. This is due to a previous optimization in the rendering engine, which would enable some floor tiles that are covered to not be rendered. So don’t mind these. Now let us enable all right sides of the walls:

Then we will do the same thing, that is draw only the ones that should be visible. To better illustrate this, I managed to cut out a few extra tunnels:

If it is not clear what I am doing, maybe it will become clear when I apply the same process to top sides of walls and floors. Basically, the black part is and should be invisible. Theoretically no processing power is wasted on them. This only applies to multi-level rendering, but single level is fast enough.
But this post is way too long. I even broke the five pictures per post rule J. So I’ll split up this post…

Wednesday, December 15, 2010

19 – Not dead

Good news everybody. I am not dead and neither is this project. The huge break in posting is due to me having a busy period right now. It is December and in December you spend half the month on holyday and the other half preparing to go on holyday. Also, there was a launch of a high profile game that I am not going to name here that had occupied a lot of my free time.
But the main reason for having a hard time getting work done on the project is that I’ve gotten stuck on the scheduler. In the beginning it was simple but it got very complicated. I could stop here and formulate the entire task in a formal language so you can see how complicated this was, but that would take a lot of space and I am way behind. Enough to say that I hate it when a game is perfectly fine, but it has some serious but not game breaking flaws. A lot of games have camera problems for example. Why did not the developers fix it? More often than not the answer is that it was very hard. There is not a fixed formula that you can apply and have a perfect game camera that never obstructs your view. Making it perfect would require maybe huge resources. But still, I’ll have a perfect scheduler and I am getting close.
So now let us talk about the new features that were almost done at the beginning of December, but yada yada yada things written above.
So workshops? Yes! Quite a few of them:

Selecting a building type will result in a marking on your map. Here your building will be built. As with stockpiles, these markers are not physical objects. They are just something to help you in the game:

After that, a single dwarf will go and build the workshop tile by tile. While the process is animated and scheduled fully, the resulting building is underwhelming:

In the future you will be able to tell all building apart. Right now only the frame is placed. As this will be only a cosmetic feature, I will not rush to implement it.
This is all I promised for next post last time, but luckily I have more given the huge break. Now, when harvesting plants they will appear on the map in a small sack. These sacks are free. Just consider that your dwarves love sacks and brought 3000 of them on this expedition:

Creating food stockpiles will result in your dwarves hauling them there, like they do with logs, only this time their movement speed will not be affected. Logs are big and heavy, but a sack of food is not that much for a sturdy dwarf. Here they’ll combine the content of sacks so they take up less place and left over empty sacks will magically disappear only to reappear when needed. Here you can se the dwarves as they haul food and fill the stockpile: 

So let us say this is two posts worth of features? Not really…
Luckily, I have one more: map saving and loading. This is way over due. Now I can continue to develop the same map and I am not forced to start from scratch each time. It is maybe a little bit buggy, but I’ll fix it. Saved maps are huge, almost 3 MiB, so I use Z compression to get them down to a few KiB.
And there was also the last round of rendering speed improvements. This is it. Things can’t get any faster than this. The only way is to draw less. I have some ideas about “hallowing” out the map, ideas that could lead nicely to a future 3D engine.
For the rest of December, I am not going to have so much time, but I’ll still squeeze out a post or two. But in January everything should get back to normal.

Statistics S45:
DHCore:  1875 lines / 44.8 KiB / 11 files
DH:  2533 lines / 63.8 KiB / 13 files
DHEditor: 612 lines / 16.1 KiB / 13 files
Total: 5020 lines / 127.4 / 37 files