pre-alpha-2 – 3 – Be done with it, would you kindly

I declare pre-alpha-2 done! Here is a short description of the cleanup process and two new features.

It has been a while since my last post. The primary reason is that the amount of work on DwarvesH was so much that I couldn't fit it in the Tuesday-ish posting window. The secondary reason is that this was a very busy week at work and in some days after getting home I was in no mood to do any kind of work.

The cleanup process went well and I have a healthy foundation with which I can boldly enter the final development stages for 0.1 version. The transition form 2D to 3D coordinates is 95% done. I am only going to be able to do the final 5% once I actually start doing 3D path finding. The floor system refactoring is not done, but I have abstracted it away so once I do it I will not have to modify the filters again. And countless smaller changes here and there, including a complete isolation of Irrlicht in a few key locations and the rest of the code is graphics library agnostic now.

The first new feature is a new time compression algorithm. The old one had a lot of problems. First, it looked strange. Second, it was far to aggressive. If you wanted to be very efficient you would have to pause the game and issue all the order that you would like to be executed at once or risk not having a chance to enter them again until a few hours of in game time have passed. Let us take the longest operation, sculpture sculpting, as an example. This takes 8 hours. but with the old algorithm, you had until your dwarf walks to the stone to enter new commands or pause and enter new commands. Because once the dwarf has reached his destination, if no other shorter task were queued and ready to be executed, there was a good chance that the task would be finished in a single frame render operation. So no time to react. The new system is still fast, but considerably slower and less aggressive. Long tasks are executed incrementally while still increasing the rate at which time passes. With the new system, sculpting a stone if this is the only task available does not take 10-20 ms, it takes around 9 seconds (plus the walking time). So you have plenty of time to react. Even if you do not reach fast enough, you will not loose 8 hours in which dwarves loose energy while idling, you loose a few minutes of in game time. The new system feels a lot better and you get a feeling for how long tasks actually take. Another advantage is that the old system was a love it or hate it algorithm, with its "feel" "hard-coded" in the specifics of the algorithm, the operations it was doing. The new system has several tweakable variables that it takes into consideration, and this will allow me to create a time scale slider in game. some people may like it fast, but others maybe would like to a very slow game that does not require pausing for any task. The slider will accommodate all these playing styles. Until I add the slider, I have defaulted the values to a fairly fast pace, but still manageable. There will a lot of trial and error before I figure out the right values for these variables so I am 100% happy with the feel of the game and its time passage. Also, the new algorithm allows a turbo mode, where walking happens at lightning pace (and everything else is very fast). This option is only useful on highly automated fortresses that are working on a mega project and you do not want to wait hours for your dwarves to finish.

I created a final stress test video. Here, I test path finding to fairly distant objects. In previous video, path finding was over short distances because stones were close to each other, and the only long distance walk was between to stones and the beds. But in this new video I am selecting every available plant, followed by every available tree for harvesting/cutting. I also test how much of a massive plant murder operation can be done with 150 dwarves in a day before they all need to go to bed. In this video I am using the new time compression algorithm. Please check it out and tell me what do you think about the new algorithm and the feel of time passage:

The second new feature is canceling. You can select an area, press "C" and all designated actions in hat area are canceled. This operation will not cancel task that are in progress, only tasks that are in the queue. So you can cancel a task only before a dwarf has started working on it. This is intentional. The operation is a little bit aggressive, as it will cancel everything. In the future I would like to add a window that pops up and asks you which taks do you want to cancel if the area includes several different task categories.

pre-alpha-2 – 2 – I like to move it

The polishing saga continues, but just to have some content I added one small but useful new feature. But I am only going to talk about it by the end. That's how I roll.

I went over major parts, refactoring left and right. There is still lots to do, but most of the 3D refactoring of coordinates is done. Except for floor actions. Floors are kind of awkwardly implemented and I need to find a new way to do that first.

Such major refining will unavoidably modify the total number of lines of code. How much of a difference does it make? I don't have the exact number, but it is at least 1000-1200 lines of code. But not up, down. Right now the project has about 1200 less lines of code, even with the new feature and the number will continue to decrease for a while. Same functionality, only much more robust and better structured. This is normally a good thing, but I am not that enthusiastic about it. I am known as normally a quality over quantity coder, as in I tend to write short and powerful pieces of code that tend to be a lot shorter than in someone else's hands if I am allowed to code in my style and with the tools of my choosing. I am always happy when I can reduce the number of lines of code and improve the quality at the same time. But not this time. A lot of people have a knee jerk reaction: quality and feature completeness is equivalent to the number of lines of code. It would be a lot easier to gain credibility if I had a large code base in the beginning that slowly increases. So I won't get such conversations:

"So, I heard you are working on Dwarf Fortress clone?"
"No, it is not a clone, it is..."
"Cool, how many lines of code have you written?"
"12..."

So the new feature is moving! Often you want to move an object from a position to another. There are some implicit forms of movement, like hauling to stockpiles, that do not count as moving. I mean more explicit forms of moving, where you choose the source and destination square and issue an explicit move order. The obvious example is when you move around a chair, but another example is when taking a bed from a stockpile or not and putting it in a room. This is called the placing operation. In DF, after you build a bed, you need to press 'b' to open up the building menu, press 'b' again for beds, choose the location and press enter. This will move your bed to that location and mark it a "constructed" or rooted in place so it will not be hauled away. In the future I might allow you to move something from the item browser, but for now I have condensed all move operations into one: you select two points, the source and the destination. One must be empty, the other must contain something. And then you select the move command and that's it. This is used for normal moving and also rooting stuff into place so they effectively become part of a room.

There are a lot of details that I still need to figure out. What if you select two squares that both have content and select move. Right now that does not cause an action, but maybe it should swap the content of the two cells? Right now you can even select a plant. Moving a plant is actually replanting it a new location. I think that this is better than adding a new option for replanting an item. But maybe there should be some limits. I'm sure plants don't like to be moved around that much. Selecting a square with a stockpile will move both the content and the stockpile. Maybe it should only move the content. There are arguments for both versions.

Here is a video showing the move action, because movement is best described by seeing the movement:

I gave a short description of the pre-alpha progress and described the new feature. So why am I still talking? Oh yeah, that's right. It is rant time!

Let me talk about stockpiles a little. Now this genre of games is very underrepresented. There are few games if any and one of my goals is to change that. But for such an underrepresented genre it still has its fair share of tropes and stockpiles are not an exception.

Let me list some common features of stockpiles and tell if you've heard of them before. Even better, tell me if you agree that they don't make any sense logically speaking:

• Stockpiles are magical entities that allow your characters to see things right in front of them. Have you ever encountered The Situation™ where you can't use an item because it is not in a stockpile? You cut down or produce something, an industry need is, but you can't use it until it is placed in a stockpile. While this is silly, I do get how it has come to this. Picking up stuff from a very specific space with fixed properties is a lot easier than picking up stuff from random locations. I mean coding it is easier. I'll have non of this nonsense in DwarvesH. As long as you have the resource, you can use it. Stockpiles are a tools, not a requirement.
• Stockpiles can only hold one item. So in one stockpile cell you have a mouse liver, and in another one a huge block of rock. both are full and can't accept more items. But if you bring a box or cabinet to a stockpile, it can hold more livers. Probably 20. This is again silly. In DwarvesH you will be able to pack the same amount of items in stockpiles with or without a container. This does cause the problem that containers turn out to be largely cosmetic. But I can still give some bonuses to stockpile accessing in time and things in a container can last longer. I'm sure your mountain of crafts that is lumped together on the ground is harder to access selectively and more detrimental to each craft when compared to the same amount of items arranged orderly on a shelf.
• I am sure there was a third and equally silly limitation that I just can't remember right now.

Eliminating these limitations also makes stockpiles harder to manage. To compensate for this, I'll change the type of stockpiles dynamically. If you fill up a square from your furniture stockpile with chairs, it will change from a general furniture stockpile to a chair stockpile and will only accept chairs until you move all the chairs out. I do not consider this a limitation as the ones above. It is a helpful tool, that is worth so much more with graphics when you can actually tell with a glance that you furniture stockpile has a square with chairs, one with table and one with beds. Not counting problems caused by the isometric engine where high cells cover other cells, you will even be able to count the chairs in that given square, again just by looking at it. Of course, you can click on it to get information that might not be available visually.

pre-alpha-2 – 1 – Yummy tasks

Right now I am at a moment where I am waiting both on people and on the results of some events so I can't really work on new features. Until these issues are resolved, I need to find something to fill up my time. So I thought this is going to be a perfect moment for pre-alpha-2. I'll just dive into it, without a great announcement announcing an even greater announcement where I announce that I have started working on the new pre-alpha.

Pre-alpha is stretching a little the meaning of the word. It is more a refactoring, polishing and straight Q&A phase this time. I am going over everything, checking if my designs were sound, rewriting when necessary and fixing bugs. I am not adding new features and rewritten code will do the same thing the old one did, only better. There is one exception though: I am making sure that all coordinates are stored and processed as 3D coordinates. Making the game use all the axes is going to be very difficult, and having everything use the extra Z axis even at this stage should make things easier.

Wow, this makes for a short post. I know! I'll fill the space by going into technical detail on the functionality of the scheduler, the part I'm polishing right now. How fun! I will even do something that I never did before: post some snippets of code.  This is the perfect point for people who are not interested in the technical details to stop reading.

Scheduling is the meat of such a game and thus it tends to be the most important component. And the most complicated one. Add path finding to the mix, and is very easy to create an unmanageable monster. To make things work, I have the scheduler which is a very complicated beast and I feed it several list of tasks, represented by points and several task filters. Every single task from tree cutting to item hauling across multiple stockpiles to making dwarves go to sleep when they are out of energy and continue their tasks once they have woken up is resolved by using these task lists and task filters.

Let's see how the task filter looks for the digging operation (excuse the formating but Blogger keeps ignoring my formating so I gave up)

class WallDigFilter: public TaskFilter {
public:
WallDigFilter() {
smart = true;
}
virtual void OnFail(Point3D aP) const {
World::Cell[aP.z][aP.y][aP.x].SetSelected(false);
}
virtual void OnSuccess(Dwarf& aD, Point3D aP) const {
aD.AddTask(Task::dtWallDig, aP, EngineParams::WallDigTime);
aD.Energy -= EngineParams::WallDigEnergy;
}
virtual bool IsValidSource(Point3D aP) const {
IItem& item = World::Cell[aP.z][aP.y][aP.x];
return (item.Is(Item::itWall) && item.GetData() <= 2) || item.Is(Item::itRamp);
}
};

Never-mind the structure of TaskFilter. Filters are created to build upon a fixed set of rules that were enforced by other components and they don't enforce these rules, so I can keep them short and readable. 

First we have the constructor, which only sets "smart" to true. A* is great algorithm, but since it needs to be very fast it has quite a few data structures that need to be set up. Over very short distances, this set up is a very costly operation. When turning on smart path finding, over short distances I uses a very fast but incredibly inflexible algorithm that only reads data and does not update any data structure except for the path if it has found one. Without it, several tasks that tend to benefit from this algorithm would be impossible to do as fast as they are done in my stress videos. Just setting smart to false, the default, would make digging reduce the framerate 2-3 times. Other actions do not benefit from smart path finding, and thus A* is always used.

Then we have the OnFail method. The scheduler takes the list of tasks associated to what it is trying to do, and goes over them using a heuristic algorithm to determine if it should try to find a path to it. This algorithm is very fast, but not very accurate. Several passes are done with different algorithms, and in the end we have a subset of the initial list of tasks that are possible candidates for scheduling. Unreachable cells are ignored until the shape of the reachable area changes so they can be taken into consideration again. This is why I can select half a mountain or the content of a closed off cave for a given task and there is no impact on the performance or framerate. But even so, once in a while we get to cell that should have been filtered out and deemed invalid, thus removed from all the list permanently, but due to a set of complicated conditions it is not. Such cells would remain in the system, reducing performance. Over time, once hundreds or thousands of such cells have cumulated over the duration of several game sessions, totaling probably days of game play in real time, the game may even become unplayable. To avoid this, such cells are culled and OnFail is the fail safe method that does some clean up. Digging is a self sufficient operation (except for the dwarf) and clean up is easy. Just set the selected property of the cell to false. Selected does not mean what you may think. These are not the cells you select by dragging the mouse. These are the cells that are highlighted in green meaning that you have given a task that includes them. So you select a region of the wall, give the order to dig and the region becomes highlighted in green. As tiles become reachable, more and more tiles will be dug out, while unreachable ones just sit there without consuming CPU power through scheduling. But when a truly unreachable tile is found, OnFail is called and the tile will loose its green color. You can select is again if you wish, but I'm hopping that seeing the tile change to green and back to its original color will make it clear that your intentions are futile and you should select a different cell/task.

Then we have the OnSuccess method. This is called when a task has been green-lit for execution and a path has been found to it. The dwarf and the point are passed as parameters. The implementation is very simple. We add a new task to the dwarf, giving the task type, the point where the task will be executed and the duration of the task. And we subtract an appropriate amount of energy. All other information is already in place.

Finally, we have the IsValidSource method, which again filters the list of tasks and acts as a failsafe. This method is used in the beginning of the process. It is called when selecting an area, so the GUI can count all cells that can be used for a task. When you bring up your dig window, you will see an option to "dig N walls".  Then it is used when adding the task to the appropriate lists. Then, it is used during the fast heuristic method of determining reachability. And for path finding. And finally as a fail safe. Normally, nothing unexpected happens, everything works according to plan and all algorithms are perfect. Perfect like myself. But if the impossible happens, you can wind up with an error or oversight. To give an example, maybe something caused a tree to be added to the next digging tasks. This will probably result in corrupted data or if you are lucky a crash. IsValidSource is used here again to test the validity at a few key locations and it will pick up on the presence of the tree were it should not and eliminate it silently from the list. The implementation is very easy. I check if the item is a wall and if its data is less or equal to two. This data represent the smoothness of the wall. And I check if the item is ramp.

You may think that calling this method so many times is slow or that having slightly paranoid methods that check just to make sure is not a good idea. But when having thousand of interconnected multi-phase tasks executed by hundreds of dwarves, such methods prove to be life savers. And the methods have short bodies that do little. The scheduler would not be as fast as it is right now if it did a lot in a single sitting. It is designed to take a few small decisions, but repeat the process in an incremental fashion. And the filter classes can easily be made to use template mechanism instead of virtual methods if I get desperate and need to inch out every single drop of performance, but I will not come to that.

Now let us see how we expand upon this class to add the wall smoothing operation:

class WallSmoothFilter: public WallDigFilter {
public:
void OnSuccess(Dwarf& aD, Point3D aP) const {
aD.AddTask(Task::dtWallSmooth, aP, EngineParams::WallSmoothTime);
aD.Energy -= EngineParams::WallSmoothEnergy;
}
virtual bool IsValidSource(Point3D aP) const {
IItem& item = World::Cell[aP.z][aP.y][aP.x];
return item.Is(Item::itWall) && item.GetData() == 0 && !item.IsSoil();
}
};

Very similar. OnSuccess does the same thing but with different numeric values, and the check in IsValidSource comes down to being a wall with data set to zero that is not a soil, because you can't smooth soil or already smoothed walls.

I wanted to show a third example about interconnected tasks, like hauling to/from stockpiles, but that is harder to wrap ones mind around and the post is getting long.

So basically this is it. I have one or more classes for each logical task that all feature very short and clear implementations, that build upon previous result both at a code level and as logical implications. If A implies B, that and filter called during the B phase will not check the conditions from A. This method has proven very robust. Adding a new task is very easy and this is the reason I managed to add beds, energy and sleeping very easily in a short period of time. The what I consider elegant implementation for filter classes is nicely contrasted by the scheduling algorithm, which is one scary monster with a huge number of lines of code able to do pretty much anything based on points and filters. There are many thing that I did not talk about. Filters have methods to test if a dwarf can execute a task (has the labor enabled, has the right tools once inventory system is fully implemented) and many more. The strenght of the system is in keeping it simple. You only implement the minimal amount of methods to achieve your goals.

35 – Miu

Meow meow. Meow meow miu meow meow meow meow meow miu meow. Miu meow meow meow meow meow meow meow meow meow miu meow, meow meow miu miu miu meow meow miu. Meow miu meow meow meow meow meow miu miu miu miu miu meow meow meow meow meow meow miu miu miu meow.

Miu miuuuuuu mrrrrrrrrr meow meow miu meow, meow meow miu miu miu meow meow miu. Meow miu meow meow meow meow meow miu miuuuu miu mrrroew.

Mew meow. Mowww:

Kjhgsfnklbfgxdlnkb nn lsxbfdljbdgf xfblkbgfnkllknjbdfxc bvcxnklxfcvbnlkbxckn, vxcn m,bxcvkjnbvxcklnjbnkxc,nmjbvxn, xcbvknxbnknlbxcnlnk bx knjbxvkln.

Miuuu meow meow miu meow, meow meow miu miu miu meow meow miu. Meow miu meow meow meow meow meow miu miu mew moew mi miu.

Meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow meow miu miu miu miu meow, meow meow miu meow.

34 – Performance woes?

There, fixed it for you! That's right: 120 FPS at 800x600 with Irrlicht software rendering at the highest zoom level with Z-levels 0 to 30 included in the rendering pipeline. This is the best result I am willing/I can achieve. I am tired of tweaking the rendering engine and this is the one that will be included in "Stoneage".

But even this performance is not enough. More precisely the performance is more than enough, but I can not consistently reproduce it. I have two main machines I do tests on, with three more weak machines for extra tests.  My first machine is clunky but has very powerful hardware behind it. It is a development machine and it does not have a good graphics card. The above screenshot was taken on this machine (and yes, I did wait a few seconds until the framerate counter showed exactly 120 since it does fluctuate a little; I can't get it up to 128 though). Using software rendering, framerate is very good at all zoom levels. Scrolling is slow at higher zoom levels, but it is good enough and I can't improve it more right now. As said, the GPU is trash on this machine. I will be slow but playable with DirectX, and completely unplayable with OpenGL. That is why it is good to have multiple backends.

The problem is that I can't get the same results on all machines. Performance does not scale linearly with the power of the hardware. On my second machine, a development/gaming machine with a 8800 GT GPU, I get less framerate (but not by much) with software rendering, but I get a lot more with hardware acceleration. Unless I increase zoom level. For some strange reason, my GPU drops in performance a lot once the number of tiles crosses over a yet undetermined threshold. I guess there are to many draw operations. And since the CPU is weaker, scrolling is even slower at highest zoom level.

So the simple solution of software rendering if you do not have a good GPU, hardware otherwise, becomes a lot more complicated. And even worse, there are computers out there that judging by the numbers should run good in software mode but in practice they don't. This is why developing for the PC is so hard. There is a huge number of hardware combinations that yield unexpected results and this without counting legacy systems.

As much as I would like to create something that works perfectly on everything, I am afraid it is impossible. There will always be people that will have a less than smooth experience.

These people will have to do one of the following:

• play at low resolutions, probably in windowed mode
• try every single backend combination. I'll add an autodetect option, but it will not be fail proof so some manual try and error will be needed
• use the new option for selecting the Z level ranges

I think it is obvious what the new feature from this post is: huge increase in framerate at all zoom levels, but it is only important for high zoom levels. But one feature and a wall of text does not a post make.

My second feature is the ability to select the number of Z levels that are rendered. Before I had two options: render from level 0 to current levels and render from zero to maximum level. So on a normal map, you would render 30 or 40 levels. With the new system you have a number that governs how many levels you get above and below your current level. Let's call it N. So you are rendering from current minus N to current or from current - N to current + N. Default will be N = 5. See how I am cheating? This way you will render 6 or 11 levels. Going by defaults, you will render 6 levels instead of 30. There is good chance that this will have zero impact on the number of tiles you need to render since I have a clever rendering algorithm that only renders as much as needed and I cache everything. But 5 times less Z levels will still requires 5 times less CPU power and make scrolling smoother. This is a fair compromise. People with weaker computers or strong computers that my engine does not like will get a better experience. People with strong computers will adjust N with PageUp/PageDown keys. In the future I'll add a GUI component showing you your current level and how much you are rendering.

I created a video showing things in action: a full on stress test. I have 150 dwarves digging out over 11000 wall at the highest zoom level on my computer that does not like hardware rendering at the highest zoom level. Keeping in mind that FRAPS reduces the framerate, things are pretty smooth but there are a few moments where the game struggles:

33 – I feel like there is an impenetrable brick wall between us

Why can't you open up to me? After all this time...

That's exactly what I am going to do: open up about this post's new features!

Creation of stone structures

I have added the possibility to create a stone structure out of the stone you have. You have to dig through stone walls before to get the stone. Here is the new menu:

Walls are similar to natural walls and come in two flavors: made out of stone chunks and made out of bricks. Right now the difference is purely aesthetic, but I'll try to differentiate between them. Brick wall could take longer to build because you have to take stone chunks and cut them down to brick size, but on the other hand they could be more robust. You can use these walls to make rooms or to draw something. Since I am far too lazy to clear out a section of the map removing all plants, I dug out a section of the natural wall and drew something with a mix of brick and stone chunks:

Next, we have fortifications. These are similar to walls but they will offer cover when using ranged weapons. I introduced them previously as an option when carving out stone blocks. Let me demonstrate the use of both chunk and brick fortifications:

And finally, we have stairs. These will allow your dwarves to reach higher Z levels, but I do plan to give them the ability to jump. Jumping is slow, makes you tired, you have to drop large objects you are carrying and you can't do it with a heavy backpack, but it should add a new level of strategy. Some creatures can't jump and the only viable defense is having walls higher than one Z level. Or a walls with fortifications on top so you can defend yourself. BOOOOM! HEADSHOT! Jump will be available only after multiple Z level walking is implemented and will have a largely passive skill associated to it. But back to our subject. Right now stairs are again just mostly cosmetic, but using these elements you can start and design something interesting:

OK, that was not that interesting, but I do feel like thing are starting to look promising. It would be great if I take these new options and combine them with stone carving and post a few interesting screenshots of some complex fortresses. Or a video. But not right now.

There are two thing I have not implemented yet. For starters, you can't select your stone. This will be done once I finally finish the new item browser. I said the same thing last time I talked about seeds and planting. Second, right now you can walk through these quite solid stone constructions. This is temporary, until I figure out a new algortihm for some technical problem I am having which is of no interest probably for most of you.

Tree trunks and roots can be removed

Here is a scenario you might be familiar with:

You cut down a bunch of trees and their trunk remains. It is not that easy to see, but there is trunk there between the logs. Even if you move the logs, the trunk remains. Am I the only one who feels a Metallica song coming up? DF has this feature where excessive deforestation will upset elven traders. I am not going to copy this feature but I do like the idea that some decisions in the way you structure your fort will influence your relation with other civilizations. Maybe you paint everything green to upset/entice all the green goblins? So you need to be able to do these small changes to your fortress, starting with the removal of logs:

This is the same map after you removed all the trunks and roots from ground. This is massive and time consuming operation. The root must be dug out and chopped into small pieces, then you need to cover the hole with soil and if you have logs around they need to be moved somewhere and back again. Your reward? Firewood. Smaller pieces of wood that are too small and strange shaped to be used as logs, but that are perfect as fuel and for crafting.

Condensed options for plant stuff

Like all other family of related operations, plant stuff now has its own window:

All separate options are gone. This is what I used to instruct my dwarves to remove the trunks and roots.

Optimizations for the map cache

I made several optimizations in the map cache code that have made scrolling smoother for zoom level 1. Unfortunately, it is still not enough for zoom level 2, but I'll continue optimizing. And I introduced some minor bugs. The map cache is also less memory consuming, but even so general RAM use has gone up by about 20 MiBs as the complexity of the world increases.

Screens of the day 05

Just a little filler while I work on other stuff: I decided to add a few skins to the editor. In the final version I would like to have them both use the same GUI skin, rather than the game having a skin and the editor using the skin of your target platform. I added a new menu to allow you to select the theme:

The first option uses the default skin from your operating system. The second and third options are based on Skulpture for KDE4, a theme I really enjoy created by Christoph Feck (skulptor). Here is a link if you want to check it out: Skulpture from www.kde-look.org. Check it out if you use Linux with KDE4! The skin does not look quite as good as the official KDE version, but I still like it:

The standard windows window frame does not fit well with the overall look of the theme. And there is a dark version, for people who do not enjoy a bright screen: