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.

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…

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

18 - Stockpile overload

What is a good use for stockpiles? Drawing it seems. I’ve added the general stockpile categories when creating a new stockpile:

There is going to be some tweaking to these categories, but you can use it to draw stuff:

Every stockpile has its own color. I could probably do a better job of picking the colors, but I use Microsoft Paint for my image editing needs and these are some of the default colors.

In the next image there is a lot going on. I have designated a large area for cutting down trees. As a new feature, every single log that has resulted from a cut down tree is visible by the tree trunk. They are removed one by one. Six dwarves are still busy chopping down trees while the last one is hauling logs from near tree trunks to the wood stockpile. You can see that he has a log in his hands and he has already placed two logs in the stockpile:

Once the cutting is done, everyone gets busy filling up that stockpile:

Alas, the stockpile is too small and I needed to add a second one so that all the logs could be placed:

This process took quite a while and I’m looking to speed it up. Generally, I am happy with the idea of time compression but not with the implementation. It is at the first iteration so no worries. You know what is not at the first iteration? The scheduling algorithm. I get the feeling that I rewrite the damn thing two times a day.

Besides the improved scheduler, there are some small performance tweaks. When enabling full map rendering you should get a few extra FPS (5 with software rendering at 720p on of my machines). Also some small interface improvements.

Next time: workshops!

Statistics S41:
DHCore: 1881 lines / 45.9 KiB / 10 files
DH: 2205 lines / 54.6 KiB / 12 files
DHEditor: 612 lines / 16.0 KiB / 13 files
Total: 4698 lines / 116.5 / 35 files

Official Twitter account launched

I’ve created a Twitter account: http://twitter.com/dwarvesh. Don’t worry, I am not going to be posting stuff like “It is raining”, “I like pizza”, “I am a dwarf”, “Buy my new t-shirt” or “I feel sad”.

But I will be announcing every post there. It is an easy way to post updates. It also has the advantage that sometimes I don’t have enough to say for an entire post but I could say a few words. Then you’ll get a short tweet. I wonder if there is a tool that allows you to combine and inspect your posting history from Blogger and Twitter as a common timeline.

In order to not have an empty Twitter, it would be easy to start spamming my backlog. But I won’t do that. Maybe.

Twitter widget is also available on the blog with the latest tweets.

17 - There is a Z in the title so I can has more views like last time? (Dragon)

The title of the post is a pun upon the fact that one of my posts, 11 – (Dragon) Plants and Z (level), got more views at the time than others. This could be due to the fact that the post was about a more interesting subject at least in theory, but maybe it somehow got associated to other subjects because of two keywords in the title. Dragon an Z. I’ll let you figure out the third key word.

I’m not ranting about titles just for fun. I managed to improve the Z layering, and now you can have multiple Z levels. Still only one level is playable, but I like the overall look and feel of the multiple levels. Of course, when turning on multi-level rendering FPS drops like a rock. Or a lazy dragon. Z! For now it is a mystery how people in the 2D isometric era of gaming managed to have such smooth framerates. Maybe they used really sophisticated algorithms. I have some in mind that would surely work very well, making the number of visible layers not count at all, but I get the feeling that I would be just reinventing what the GPU could do for me if I switch over to a polygon based engine.  Another new feature is the ability to have maps where the cliffs face at a different angle:

But Z level is not the big feature of this update. It is the new scheduler. Again! I just can’t leave it alone. But the new one is really great. It is a lot more powerful, faster and easier to use. It is really great quality piece code and there is little I can do to improve it in the future. Maybe adding LOS (line-of-sight) tie breakers to better simulate a way a sentient being would go on about these tasks.

The new algorithm is very general. Given a set of any tasks, it can choose a dwarf D and a task T that has the properties P. T will be heuristically the best (read most reachable) task from the set and there should be a path from D to T. If there is none, an action can be taken. In previous version of the algorithm, if you would choose a task that was not reachable, like a bush from a sealed off cave, the game would freeze. With this new algorithm, the task will be removed. The process is still very slow, but it is a lot better than freezing. Unfortunately, A* is a lot better at finding a path between two points than figuring out if a path exists (because you’ll end up exploring all reachable points). In the future I’ll add a constant time (and near zero) algorithm that can tell me if there is a path between the two points to know if it is safe to call A*.

Here is a video. At the end I also demonstrate the “remove floor” feature which I’ve never shown before. It is a little bit buggy, that’s why:

Disclaimer:
This video has been produced by using a version of DwarvesH and modifying it by applying the tiles form Stonesense (http://www.bay12forums.com/smf/index.ph­­p?topic=43260.0) only for the purpose of creating an early demo video. DwarvesH is not available in any form with the tiles from Stonesense by default officially or unofficially and does not assume any right to use them. The process can be repeated by anyone by downloading both applications and using a simple image editing tool to selectively change the tiles from DwarvesH with those from Stonesense or the tiles from Stonesense with those from DwarvesH.



Statistics S38:
DHCore: 1755 lines / 43.1 KiB / 10 files
DH: 2055 lines / 50.3 KiB / 10 files
DHEditor: 612 lines / 16.0 KiB / 13 files
Total: 4422 lines / 109,4 / 33 files

16 – Is that wood in your stockpile?

As you saw from previous screenshots, I am going with a fixed key/function system. “1” is always digging. The keys are going to change maybe and it is going to be hard to add all actions to easily reachable keys without overwhelming the player, but it is a good system. I think I should get rid of the right panel and go with something that takes less place though.

So I have a new action, “5”: wood stockpile. This will designate your selection as an empty wood stockpile. I have a hidden cheat key that places a single log in an empty stockpile. No, you won’t get to use the cheat key. It is only available in super secret God mode. I will demonstrate this with a video. Next step that is not implemented yet is to place the logs as trees are being cut down.

This time I captured my video with Fraps. It was slightly problematic because the captured video was 2.5 GiB and YouTube only allows 2 GiB files. But I downloaded a conversion tool and got it down to 93 MiB so no problem! YouTube took a few hours to process my video, so I waited with the post until it was done. I am not completely happy with the quality yet. And as you can see, the resolution is different now. I have added support to the INI file for resolution and full screen flag. You can give any resolution if you are not running in full screen. Someday this will be available in game.

There is also a new mini feature. The editor now allows you to customize the names of you skill levels and also the maximum value for skills. They are no longer hardcoded:

So now, without further a due, the video:

Same as the last time, I have added a disclaimer because I am still using Stonesense tiles for demo purposes, but I do have some original graphics mixed in there.

Disclaimer:

This video has been produced by using a version of DwarvesH and modifying it by applying the tiles form Stonesense (http://www.bay12forums.com/smf/index.ph­p?topic=43260.0) only for the purpose of creating an early demo video. DwarvesH is not available in any form with the tiles from Stonesense by default officially or unofficially and does not assume any right to use them. The process can be repeated by anyone by downloading both applications and using a simple image editing tool to selectively change the tiles from DwarvesH with those from Stonesense or the tiles from Stonesense with those from DwarvesH.

Statistics S34:

DHCore: 1522 lines / 37.0 KiB / 6 files

DH: 2034 lines / 52.2 KiB / 10 files

DHEditor: 613 lines / 16.1 KiB / 13 files

Total: 4169 lines / 105.3 / 29 files