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.