Showing posts with label pre-alpha. Show all posts
Showing posts with label pre-alpha. Show all posts

Saturday, September 3, 2011

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



Thursday, August 18, 2011

pre-alpha-3 – A* updates

Phil was kind enough to point out a link on the forums about A* and I also did some extra research, and I realized that obtaining the fastest A* algorithm is a very complicated task that depends on your exact needs. While the core of the algorithm is always the same, the small implementation details and data structures that are used count a lot. So I would have to rewrite everything form scratch and I don't want to do that right now, since my A* optimization was just so that I could fix the issues I talked about last time.

But I did do one more round of optimizations: I optimized the central node container. The recommendation is to use a priority queue but I do not think there is a name for the thing I am using. Anyway, I won't bore you with all the numbers. Suffice to say, that in release mode, with 700x700 maps, the algorithm finds a path in 45-50 ms with any kind of map: empty, maze or just random. Nice improvement. I'll leave it at that. At normal map sizes, it takes at most 10 ms and the average time over the usual distances is 3-4 ms.

This is when I realized that there is a huge bug in my algorithm that has been there from the start. I tried to fix it, but the fixed A* is about 8 times as slow as the broken one. My algorithm shouldn't even work. After some testing and experiments, I think my algorithm degrades to a very quirky version of Dijkstra's algorithm. This is probably why the performance degraded so much when the explorable region was big with my less then optimal container implementation.

I really should prove my conjuncture that my A* degrades to a Dijkstra's, but with the current performance I won't bother with it now. I'll leave it to when I do not have anything else to do.

Wednesday, August 17, 2011

pre-alpha-3 – Day 17 - More Stone Power

The polishing process continues.

I started by tackling the floor operations, fine tuning panels, adjusting skills, balancing, testing filters, etc.. This is the floor operations panel:


And this is the tool tip:


Short as always, but hopefully informative and enough to give you a starting point if this is the first time you pick up the game.

You may notice that the beatify option is not present for floors. I added the beautify options for walls to combat the frequent forgetting to issue an engrave action after a smooth action when engraving is the end result you are after. But I realized that this system is silly and adds complexity without adding depth. Combating such poor interface choices is one of the reasons why this project exists after all! I can already imagine the conversation between the expedition leader and a worker:
"Hello Myorlin! Do you see that wall over there?"
"Sure boss!"
"I want you to engrave it!"
"Can't do that boss!"
"Why?"
"Because it is not smoothed yet. You see, that wall has a very rough surface. A fellow dwarf was in a hurry to dig out a passage. I need a smooth surface to carve into, smooth as my bottle, that be the way how smooth it be must."
"Can't you smooth it first and then engrave it?"
"Sure I can! I can do anything! But you need to ask me to beatify the wall! You asked me to engrave it!"
"Beautify? What does that mean?"
"I take the wall, I engrave it, making sure that I smooth it out where needed. It is really efficient! It will even take me less time to do than first having to smooth it all and then engrave it! Alas, you asked me to engrave that wall. And listen to me: there is no way I can engrave it without it being smooth. If only you asked me to beatify it!" 
"You are an idiot!"
As you can see, any justification or rationalization can be thrown out the window: why can't you just give an engrave order, and if the wall is smooth the dwarf will start engraving, and if it is not, he will adjust the time needed to engrave dynamically based on the amount of work needed for the smoothing operation. This is what I did for floors and also applied the same principle to walls. So now engrave works on all non engraved walls, having a duration of 100%-130% based on now fast that dwarf could finish the operation. This is a perfect case where thinking stuff through and streamlining without loosing depth really pays of. I think the new system is even deeper.

But you may ask: if the engrave operation does not take a lot longer than a smooth, why would anyone smooth? Because smoothing and engraving have different outcomes. It is hard to see, but here we have a sample of some smooth floors arranged in a rectangular pattern:


And here we see the result of engraving:


Ah yes! Remember these patterns? These engraving patterns are actually the content of my first two third party mods. A while ago I asked for some engravings and this is what I got. It is a little bit hard to tell, but I used engravings to create the text "HELLO FROM DH!". The official engraving patterns will be slightly better suited for the visuals of the game, but the important thing is that I am running my main mod and two third party ones.

Another thing I have noticed is that the walls/floors duality inherited form DF can seem awkward at some moments. In DF it is less apparent, because floors are abstract and have no real height. But in an engine like mine, where floors have actual height, taking a short chunk of rock and calling it a floor and taking a higher chunk of stone and calling it a wall does not make that much sense. I'll think long and hard about it, but I can imagine a system where these chunks have different heights, and a floor is nothing more than shorter chunk. In this system different height blocks could be freely mixed.

Now on to bigger fish! With most systems greatly improved, there is but one system that I did not touch upon: A*. Now my A* is probably not the fastest out there, but it is fast enough. But it does have one huge disadvantage: the performance degrades direct proportionally not only to the length of the path (which is normal), but also based on the number of obstacles the algorithm can handle. These obstacles don't even have to be around the path. It would be great if I could improve this situation.

In order to properly test this, I'll create some custom worlds specially for A* testing:


Ohhh, look how cute and small it is! A single dwarf starts in one corner and I will give an order to dig something in an opposite corner. I just created a small map so you can see the shape.

I will be testing with 700x700 worlds. At such high map sizes A* is certainly a resource hog. Let's see some results where I measure the time it takes for the algorithm to do the path finding, in debug mode:

387.2084301 ms
388.3904938 ms
386.1530586 ms

So around 387 ms. It may be a resource hog, but it reasonably fast. It is going to be hard to improve it. I probably need to do tests on  a slower computer. I'll try a more complicated layout, forcing the dwarf to walk a long path though a simple maze:


Let's see the results for this pattern, but with a 700x700 map:
141.3050402 ms
141.6633958 ms
147.1755488 ms

OK, OK... I may be fast enough. It is even faster this way, because while the path may be longer, it does not have enough place to explore. A* depends a lot more on the total space it explores until it finds its target than on the length of the path. Still, let's try and optimize it, but using the simple straight forward empty map, on which path finding takes around 387 ms.

The result is around 350 ms and for the maze map around 125. An OK improvement and now the engine can handle any number of obstacle types without affecting the performance. In case you are wondering, in release mode, on a 700x700 map going from one corner to the other on empty map the time is 210 ms and on maze map around 45 ms. I am really curious what the performance of the top A* algorithms out there is. Any hint would be appreciated!

These tests also revealed a few big bugs, like some visibility functions being able to go outside of the map. I hopefully fixed these bugs and I added some extra asserts to these functions and added a new map sanity check pass after map generation.

The A* chapter is not finished, but today's experiments certainly helped make DwarvesH a lot more stable.

Tuesday, August 16, 2011

pre-alpha-3 – Day 16 - Stone Power

Cheers to another very fruitful day of polishing and bug fixing!

*CHUGS DOWN A BOTTLE OF DWARVEN ALE*

I have slightly redesigned the editor: using the menus was very cumbersome because you had to swap a lot between all the tabs. I removed the menu and added a vertical toolbar that nicely takes advantage of today's widescreen predominance:


The icons are not that pretty, but they are fairly self-explanatory, have tool tips and are diverse enough to be easily memorized if all else fails. Now I can easily switch between the tabs and I'm thinking of assigning keyboard shortcuts to all the tabs.

This was a usability/cosmetics change. Now for the real deal: two of the action groups are now fully realized, being 100% parameterized with the appropriate skills and pretty much ready for QA. In my previous examples explaining task filters, you may have noticed that tasks used to depend on some field from a class called EngineParams. But there is a better place to define these constants: in the skill editor!


Here you can see that the mining labor from the miner skill gives 100 experience points, has a duration of 7200 seconds and consumes 0.01666666667 task specific energy (a second). Skills now gain XP, but I'll wait with actually implementing leveling up until I balance the game. Speaking of balance, the game is pretty poorly balanced right now. It will take a lot of play testing on my behalf and others until the balance improves. Just to give an example: two hours raw dig time is not a good value. The difference in energy and time between a novice and master miner is pretty much negligible. If you are not under attack you have plenty of time to use an inefficient dwarf for digging or take another dwarf from another task to finish quicker. With two hours, the game does not incentivize you enough to use the best dwarf for the job and thus you won't appreciate and get attached to your top workers. And you won't miss them when they die gruesome deaths. After a little play testing, I think that a duration of 6-8 hours is more aproriate for a skill 5 dwarf, and every point could knock off 20-30 minutes from that. This way your master miner will do a lot more wok than a novice. What do you think?

Here is another sample skill:


Stone detailing is still physical work, so you get an energy penalty, while in the case of gem setting you do not. The durations will get increased.

I also redesigned the skill system and now, for the first time, it is capable of handling any skill, not just a few that have their logic implemented in the game engine. There is one caveat though: these skills must be production skills, i.e. take any number of items, any workshop you wish (official or from a mod) and must produce some goods. With this new system, it is possible to create a mod that adds a new skill and a new industry to the game, and your dwarves will be able to learn and level up that skill.

With the skill system in place and task filters from the first two task categories using the system to its fullest, I went in and updated the interface for these categories.

This is the new "wall actions" panel:


Oooooooooops!!! This is the new "wall actions" panel:


Carve options have been removed and we have two new actions. These actions are not planned for 0.1, but they will be part of the final game, so I though I should add them now. But what do they do? Let's see if the popup helps a little:


"Fortify wall" is an operation with which you use a wooden log to better support the wall and the ceiling. In the future I'll implement wall and roof collapsing. I don't want this to be to stressful, so for average size rooms you won't need to fortify walls. But for huge rooms, you will probably need to. But you will still be able to use it anywhere, even if it is only cosmetic.

"Decorate walls" will allow you to place things on walls: wall carpets, metal plates, paintings, flags and what not. And in the far future, when steam punk mechanism, logical gates and "circuit boards" will be implemented, you will be able to place triggers on walls with this action. Until then, this option will serve only a cosmetic purpose. The difference between this and engraving is that engraving is a action that carves out small pieces out of the wall to form a pattern, while decorate takes a finished item and nails, glues or otherwise attaches it to a wall.

Carve options have been moved to their own panel:


The entire carving system has been greatly cleaned up. Only chairs and "cests" are passable. Some spell checking is still pending! And a couple of option are still missing. In a future version I'll replace these buttons with an icon grid, because some items can have multiple angles, like stairs.

And finally, the quick dwarf inspector now uses obscure three letter words to show you what dwarves are doing:


I hope I did not forget anything, like I did in the last post. I forgot to document how map caching now takes up to two multiplication less per tile, bringing the grand total to zero multiplication per tile. This should improve performance a little.

Monday, August 15, 2011

pre-alpha-3 – Day 15

Let me start by thanking again everyone who donated! Your help is greatly appreciated!

You may have noticed that this pre-alpha is longer that the previous ones and the number of altered subsystems and overall polish is higher than usual. One of the reasons why it is taking longer is graphics. During the last 10 days I spent a lot of time trying to find the best way to give DwarvesH a new and original look. During this process I tried several things, including outsourcing, and right now I'm not exactly sure with which artistic direction to continue, but soon you'll see some new samples.

But the main reason is that I have changed the way I work and what I do in such a phase. The initial plan was to go over the 0.1 feature list and make sure that as much as possible is working well and then to adjust the next feature set plan. But I changed this approach to one in which I try to make sure that every single feature that is on track to make it into the final design of the game is perfect and fully implemented, without using any placeholders. I have a vision for most of the features. The implementation of said features varies from zero (combat as an example) to placeholder implementation that will probably be drastically changed (weapons and weapon skills are already in the game, but I am not advertising this because I know that the system will be changed) to good implementation that might lack some depth and polish to finished features that will probably make it 1.0. If one one these finished but lacking polish features is something that I want to have in the final game, during this pre-alpha it will get finished and extensively tested.

In consequence, version 0.1 will have less features, but almost everything will be near final implementation and bug free.

So next time you will see the final shape of the plant system (and a little bit even today).

I am in a hurry to write this post because Firefox is driving me crazy with its Blogger bugs. Using the WYSIWYG editor has been lately a huge pain. I can barely insert an image without everything getting messed up and I can't use bullet points.



Added error reporting
During game start up, if something goes wrong, the game will print some messages on screen. This dialog is probably not the best looking thing out there, but it sure beats the game crashing, freezing or otherwise misbehaving:




Visually countable harvested plants
Now you can tell by looking at them how many harvested plants are left in a square. The graphics are just placeholder right now, and food stockpiles do not yet have this feature:



IPS improved
The Incremental Proxy Storage is my home brewed method of storing maps in a relatively very small space without sacrificing speed. Unlike other methods of squeezing out every single possible byte, this method still maintains an OOP interface to map access and thus is still pleasant to use. But it does have some disadvantages too: it is fairly verbose to create an object inside IPS for the first time, it is not too easy to change properties, it is very hard to change structure and it is vulnerable to order and count changes. The last two points relate to saving the map as a save game. I tried to fix these vulnerabilities: creating items is now very short, changing properties remains at the same difficulty, but now this difficulty applies also to changing structure. For the last two, I need to explain the save system.

I have separated the save file into two files: the first is the ruleset and IPS for your game and the second is your raw map, saved and compressed. DwarvesH is a complex game that is getting more and more complex, thus there is no way for me provide compatibility between save games from different versions. This is where the split into two components helps. If you want to migrate to a new version, you need to create a new map under the new version, copy over the new saved IPS together with only your old raw map from the previous version to a new location, and with a bit of luck, everything should work. This is the maximum level of compatibility that I can provide. Making a save game importer for all versions would be an extremely difficult task.

IPS has an item order vulnerability when doing the above method of updating a save game from a previous version. If you change the order of some items from the same category, this order will cascade and apply to all your derivative items creatable from the original items involved that have changed order. So let's say you have a version 0.3 save game on which you played for weeks. Version 0.4 comes, the IPS migration happens, but version 0.4 has swapped the order of blackberries with a mushroom. When you load, all blackberries will be mushrooms and the other way around. So too will be all the items that have as a base material one of the two items. There is no way around this and this misfeature is not that bad: it is a lot better to be able to load your fortress on which you have worked a lot and risk a few small changes then having to either restart the fortress on the new version or be forced to keep both versions installed on your disk. It is perfectly fine if some people choose two keep more versions, but you shouldn't have to be forced to. So this vulnerability of IPS can not be fixed.

The count vulnerability is similar to the previous one, but this time the number of items changes, either because the new version added some new items, or because you are trying to change the mod loadout on a saved fortress. This vulnerability is fixed, but it does have some limits. IPS now intentionally has "holes" to accommodate more items. I added generous padding, but it is still possible to grow over its limits. This is a mechanism that protects fairly well against accidents, not against intention.



Reimplemented world generator
The old "incline hill" map generator was one of the first things I did with world generation. The code was old and not that easy to change, so I redid it in a way that hopefully bridges the gap between it and the random landscape generator. I still need some testing before I can start using the random one regularly. The new implementation also fixed an old and ugly bug.



New reachability algorithm
Ah yes: this is the star change of this post! As said in the past, A* is a poor choice for determining if two points can be connected by a path. If you know that at least a path exists between those two points, then A* is great not only at finding a path, but the shortest one. Maybe too good. It is sometimes weird to to see dwarves move with near clairvoyant path finding on an optimal path. Back in the day I added a little noise to it to provide a less "robotic" and a more "human" feel to it. Here I go again, ranting. So I use another algorithm that can tell me if two points are reachable and which caches this information for the entire map. I changed the algorithm itself to be faster and limited to the area that dwarves can explore at the current moments, so you can have any number of hidden enemy caves that have yet not been discovered without pathfinding taking a hit. Then I replaced the backbone worked of this algorithm: I went from a "vanilla" flood fill algorithm to a very fast scan line fill algorithm. The end result is that the new system uses barely any memory (while the old one ate it like crazy), and the speed in the reference interval for normal maps went from 35 ms to 8 ms.

As a test, I tried it out on a 6000 square meters map: again, barely any memory used and 270 ms speed. Pretty good! Wait... 6000 meters? That is more that last time. Well, all the performance, memory use and stability improvements that went into this pre-alpha had an indirect effect on the game, and the old limit of 4500 square meters is now exactly 10440 square meters! Again, I do not want to create such large maps. This is only a stress test. But it is good to know that without actively working to achieve this goal, the engine can now run maps with an area 5.3824 times as large as before. And the best part is that while last time I could not go over 4500 square meters area because of a weird segfault, this time the engine fails with a simple out of memory error. This error can traditionally be fixed by installing more RAM, but my case is different because I am near the limits of a 32 bit executable.

Wednesday, August 10, 2011

pre-alpha-3 – Day 10

Not every post can have something exciting in it. This goes double for posts in pre-alpha phases, when often you must do the low level fine tuning. The devil is in the detail, as they say.

Changelog: 

  • Coordinate system fully 3D now. Regular readers may be familiar with the fact that I already switched over to a 3D coordinate system for tasks. Well, this is a long and tricky process, and last time I made sure that interfaces were using 3D points and also the implementation was, when needed, but the really low level internals would still drop the Z coordinate. Now, the entire game uses 3D coordinates! Even the A* implementation takes such coordinates and returns a 3D path, but the actual path finding is still limited to a 2D plane. Trust me, having the game fully take advantage of all the Z levels will be a major announcement, not a small point in a changelog.
  • Task lists now actually use lists. Another pending internal change. This should be more efficient and better suited for task lists, where items constantly jump around.
  • Cleanup of DHCore continues. This package is starting to look pretty good and soon will be better suited as a general purpose library, rather than a single purpose (serve my game) library.
  • New action: beautify walls. Even when testing this has happened to me: I want to engrave some walls, give the smoothing command, get side tracked and realize later that I forgot to give the actual engrave command when smoothing was finished. This will undoubtedly happen in a real game for a lot of people. So I added the beatify command, that can only be applied on natural non-smoothed non-engraved walls and is basically a smooth combined with an engrave action, but executed as a single task. It also costs only 80% of the time it would take to first smooth and then engrave. Just a little quality of life thing. PS: The wall option panel is getting very crowded. It is probably time to separate the carve options to their own menu.


  • Started modularizing tasks resolution. Gah, I can't find a way to explain that in the language of mere mortals.
  • Implemented a high resolution timer. I have been having this problem for a long time: most timer objects, including Irrlicht if I am not mistaken, use this little thing: GetTickCount. A very useful function, but as said also in its documentation, it has a resolution of 10-16 milliseconds. This is great for most tasks, but sometimes it makes this function unusable. Let's say you have an A* implementation that takes 30 ms to find a path, and you would like to optimize it to only take 20. With a 10-16 ms resolution, you are utterly incapable of measuring such an improvement. After scouring the Internet, I put together a high resolution timer that is even less portable than the above Windows API function. This timer is even capable of using multiple CPU computers to improve the precision of the measurement. In theory. In practice I have no way of telling that. I ran a few artificial benchmarks to test it. In these tests I ran a test 10 times: wait 30 ms and measure the precision of the timer, logging the absolute difference between the 30 ms known interval and the measurement, and determining the total and average deviation. Here are the results, first for a average test:


As you can see, the high resolution times is extremely precise, while the normal timer, during ten tests, accumulated a  total error almost equal to the duration of a single test. Once in a while, you get lucky and GetTickcount returns quite an accurate results:


But the HR timer still has it beat and is very predictable. I do not know what resolution the sleep function I am using has, but if the HR timer is to be believed, it is quite accurate. Using this timer I am going to try and greatly improve the A* and reachability calculation algorithms one last time during this pre-alpha phase.
A long long time ago, in a galaxy far far away, somebody on the Internet thought that such massive changes to the task system went over without causing any bugs. And he was wrong! Surely there are a few new bugs that will get squashed. On the other hand, the new system also probably fixed a few existing bugs, like when you give the same order on two different Z levels.

And if you still want something exciting, later today I should be introducing the donation system!

Tuesday, August 2, 2011

pre-alpha-3 – Day 2 – A GUI without licht

Regular readers of my blog may be aware of the complicated history of the GUI backend in DwarvesH. Right now I am using a mishmash of regular Irrlicht widgets and widgets from my own custom lightweight GUI system created specially for the game.

Such a system is not going to cut it for release, and I removed all references to Irrlicht GUI code. The entire game now uses my own custom set of widgets. These widgets only rely on Irrlicht for drawing primitives and reading the user input, so it is very easy to port it to any toolkit under any platform.

Changelog:
  • Irrlicht no longer used for GUI.
  • Custom GUI system received a focus handling system. It is very rudimentary, but it does the job it has to well. Testing will iron out bugs and maybe I will expand upon it a little.
  • A fairly competent keyboard event handling system is in place to send key codes to widgets. It is slightly held down by the subpar focus system implementation in cases where key presses must be sent to the currently focused control
  • ListBox new custom widget, replacing the Irrlicht one. It handles item operations and responds to keyboard and mouse events. Does not have a scrollbar yet.
  • Dropdown combobox Irrlicht widget removed and it will not be replaced with an equivalent custom widget. I evaluated my GUI and right now I do not need this widget. I was using the Irrlicht one simply because it was available, not because it was needed. The layout for some windows was adjusted, replacing dropdowns with listboxes.
  • Rudimentary EditField custom widget added, replacing Irrlicht one. It is rudimentary because it does not yet handle the plethora of keyboard commands it should and does not support copy and paste.
  • All widget classes now have proper final names. Custom and Irrlicht widgets names sometimes clashed, so I had classes like Label and Label2. Now there is only one set of widgets and names no longer end in "2".
  • Mystery bug updates. DwarvesH has a special run flag that allows you to skip all world setup and dive directly into a random generated map. This is what I use for testing. Surely you do not believe that I click though N windows before I can dive into the game, do you? This flag is almost always turned on for me. But when I turn it off, the main menu is displayed and I can create a custom world. I noticed that when running the game with the flag off, once I get to my map, there is a steep FPS drop (around 100). Some resource must remain active during these menus that is a real performance bottleneck. I repeatedly failed to find the bug. Now, with the new GUI system the bug seems to have disappeared by itself. The map renders at the same speed with both setting of the flag. On the other and, I am experiencing a flat 20 FPS drop in both modes. I must investigate further. Something is still fishy around here.
  • INI file has new field for bits per pixel and vertical sync. The Irrlicht documentation claims that it can ignore the vertical sync flag silently. And so it does. Maybe it respects the flag only in fullscreen mode. Or maybe I must buy it flowers first. Take it out to a nice dinner. More investigation is required. Bits per pixel seems to be respected, not way to truly tell.
  • Removed the awkward top level control "activation".
  • Classed associated to top level windows no longer have a widget member variable to host all children widgets. These classes inherit now from the TopWindow class.

Except for that strange bug and Irrlicht not doing what I tell it to, I am very happy with the way the GUI code is progressing. The code is much cleaner now that only one widgets system is in place. It still needs a lot of time to mature, but by version 0.3 I'm sure it will suit my needs perfectly. That is if I do not change the widgeting system! Again!

I'll leave you with a single screenshot of the GUI without Irrlicht. Notice the look of the widgets and the layout, not the generally outdated content of the window that has not been updated wit the new design for the game (but will be during theis pre-alpha phase):




Monday, August 1, 2011

pre-alpha-3 – Day 1

Since I just posted post number 50, I am only a few post away from the next pre-alpha and today is August the 1st, I decided to get started on the pre-alpha a little-bit early. I will also add a few new features, but in pre-alpha posts I'll just refine existing features and in normal post I'll add new ones. There is also going to be extensive testing. This is the final pre-alpha before 0.1, so by the end of it everything needs to be perfect. Or at least as perfect as a huge ham.

These posts may not seem that interesting, since a lot of the content is going to be a slightly detailed change log.

One thing that may be more interesting is that I am redesigning the old API from the support library. DwarvesH consists off three projects: a library, the game and the editor. The library was designed to only be used by myself and not to be made visible. The new design dictates that the library should be written as to allow any client to use its features. I'll try and make it public in the future. With this library anyone (with talent, skill and a lot of time on their hands) could implement a lot of features that are present in my game and the two would be compatible. And third party tools would have the advantage of never falling behind the official game, since all that would be needed is a recompilation once a new version of the library comes out. So the library must be very well designed, but at the same time must never sacrifice performance, even if it has to sacrifice readability.

The above paragraph for people familiar with Dwarf Fortress and the tools from that community: you do not need to reverse engineer the map format or write a tool like DFHack. DwarvesH will provide these for you though an API. The plan is to make this API public and write very little documentation for it. But C++ is very readable so you'll have no problems there. I may change my mind if a good reason comes up not to make it public (legal, hackers, greed, etc.). No deadline for the public API.

Changelog:
  • Map size is the same as advertised. If you are a programmer and are used to working with matrices, you may be familiar with the concept of bounding borders. The idea is to insert a dummy border with invalid data around you matrix, so you can compact bound and validity checks for points that are adjacent to your current point. It is both a performance, robustness and quality of life thing. The problem is that your matrix is a little bigger. Or in my case, a little smaller, since my 300x300 maps had an effective usable area of 298x298. This is corrected now and maps are created to compensate for this border with a plus 2 to each dimension.
  • The map is not dynamically allocated and structured as planes. Believe it or not, the map used to be statically allocated. The map is accessed so often that the only viable solution was to make it a global statically allocated entity. A new API has been introduced to give access to cells and floors. The whole game now uses the new API. The API uses natural coordinate orders, so we have x, y and respectively z, rather then the hardware memory layout dictated order of z, y and x. This was a huge change, and while things seem stable right now, there is a good chance I broke something. A positive side effect of this is that clients of the library, like the editor, no longer consume memory in order to store a map (unless they ask to), so the memory consumption of the editor has been drastically reduced.
  • Removed some outdated non-OOP style methods from the map handling API: TileIsEmpty, TileIsWalkable, FloorIsValid and FloorIsGrass. Proper OOP API is available.
  • In order to better prepare for beta testing and better simulate computationally intense maps, the map is always allocated as 700x700x100 (7002x702x102), even if you choose a smaller size. You can only use the size you selected (you do not know how much was actually allocated). This way I can test the game using a lot more RAM than needed. If it runs well while using a lot of RAM, it will run well when it uses less too. New RAM consumption for test phase is 320 MiB.
  • Rule set serialization code cleanup. -49 LoC.
  • The internal namespace that I was using was called "World". Now that the API is changing its format, the new namespace is called "DH". This may seem problematic, since I am changing the name of the game, but the engine is still called DwarvesH, DH for short.
  • Reachability cache moved into DH namespace.
  • MapGen class that stores the map creation parameters chosen by the user has been improved, moved to DH namespace, has its own source files and supports serialization. Once the overhauled save system is done, world creation parameters will be also saved into the savegame, even though they offer no practical purpose.
  • Removed extremely outdated snow code. Snow and snow remove operations have been removed from version 0.1. Initial biomes won't have appropriate temperature during winter to trigger snow fall.
  • Misc stuff moved to "util" module.

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

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 {
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.


Monday, February 7, 2011

pre-alpha-1 – 2 – I can has update?

Yes!
Back from a break and I sure have updates.
But first let us talk a little bit about the evolution of DwarvesH and the idea behind it. Long story short, I wanted to see if I can take the formula of such an involved city builder and make more accessible without taking away the depth. I have been getting quite a few negative comments on YouTube. People seem to be split up relatively evenly between people who like the new interface and graphical perspective and people who are calling this a Dwarf Fortress clone. I don’t want to debate that right now, but DF’s take on the city builder is severely underrepresented. Maybe we need more there.
But I am getting side tracked. In order to make everything more accessible, I went from top down 2D engine to isometric engine. But isometric has a few disadvantages.
-          Walls and other high tiles tend to obstruct your view. There are numerous workarounds, like making tiles transparent if the cover something, making walls half-height, drawing extra borders,  allowing 90 degrees rotate on map and others. But the end result is the same: you will have some level of obstruction that is unavoidable.
-          Isometric graphics are hard to produce. Because of that angles you have in such an engine, getting smooth transitions between tiles is harder. Not a problem for an experienced graphical artist (which I am not).
-          Modern graphic cards are not that good at old-fashioned 2D bliting. So you need to be careful with the number of draw operations that you make. You can’t just say “Hey, this card pushes out 100000 polygons, I’m sure it can handle 1000 blits”. The numbers are arbitrary, but the truths is that you need a lot of precomposed tiles, by either composing them on the fly and caching the results, or just have them precomposed on disk and load them as such.
-          And others that I forget.
I’m sure you know where this is leading, especially since I talked about my prototype 3D engine. So after finishing a few important tweaks, I started working on the 3D engine and preparing it for full time service.
At first I had a lot of difficulty, but then remembering my future plans, I greatly simplified the math and made the camera less flexible. You can tilt, rotate and zoom, but there are constrains on these operations. I am aiming for a Warcraft III type engine, with a good default camera angle for overview and some rotation capabilities, but no absolutely freeform camera where you can zoom in and see one of your dwarves’ toes from underneath.
This is not the best time to introduce a new engine. You know, the alpha consolidation and polish phase. But I can’t really delay it, since further efforts in isometric engine are going to be wasted effort. I do not have the resources to keep both engines running.
This also raises some accessibility concerns. Event thought the engine offers better view point, with almost top-down default perspective, but 3D aspect ratio and camera management, it does mean that I am cutting away people without 3D capabilities. I’ll do my best to make the engine as scalable as possible. And I feel bad for retiring the isometric engine, which was extremely polished. Oh well…
So let us review the changes.

New 3D engine

Read the rant above to find out what this is about. The new engine is in no way optimized, but as the weeks pass and I learn more, it should even be faster that the old one. The problem is that I am lacking the assets right now. All the 2D tiles are represented as cubes with the tile applied as texture. I am working on inserting real meshes here, but it is going to take a period of time. Also, a lot of things are not textured yet; they just have a bland color. These two elements combined make the new engine look uglier than the old one, and this is the reason why I won’t post a screenshot yet. Maybe next time!

Optimized A*

It is very hard to benchmark the A* algorithm, because it depend a lot on the start and end position, map structure and obstacle distribution. But while keeping these parameters as constant as possible on a random map, I managed to get a good test bed for various implementations. The new A* is between 5 and 9.75 faster than the old one, depending on scenario.

Other stability tweaks

There are tons of small fixes that just go under the good-old bug-fixing umbrella-ella-ella-ella-ella.


And with that, I’ll declare pre-alpha-1 done. The period got cut short a little, but I am wary of making very specific niche case optimizations now with the new engine in fear of them becoming obsolete. I’ll continue according to plan, adding the wood and stone products with their respective industries. I’ll also patch up the new engine as time goes by, but not as a concentrated effort. As soon as I have enough assets for one of the biomes I’ll start posting visual again.
There are a lot of questions that 3D raises that have no correct answer. What should be the default view angle? How far is the camera placed? What FOV should it have? How big should the landscape chunks be? What format to export the 3D graphics? I’m hoping these answers will come to me slowly.