Friday, April 15, 2011

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.

Friday, April 8, 2011

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?"
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.

Tuesday, April 5, 2011

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 {
WallDigFilter() {
smart = true;
virtual void OnFail(Point3D aP) const {
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 {
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.

Friday, April 1, 2011

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.