Bay 12 Games Forum

Please update the links in the OP to reflect the new location of Dwarf Fortress File Depot at http://dffd.bay12games.com/file.php?id=2354

I looked at the chroot stuff...  and it just said "then you build the kernel as usual".  I never did that (installed Ubuntu from an iso), so I don't really know what to do.  I'm not sure I'm Linuxy enough to accomplish any of these methods.

This reference might help: https://wiki.ubuntu.com/DebootstrapChroot

It would be good advice, if there was actually a multiple clock cycle difference in ops by register width. But there is not. Most integer ops are single cycle these days, regardless of operand size.

I just checked the latest version at http://www.agner.org/optimize/instruction_tables.pdf and am happy to see that only some old AMD models have that backwards speed hit, and then only on MOV. Of course that makes me feel really old. It is nice to be able to intentionally forget things because the knowledge is obsolete. Thanks.

Using chroot on Linux is definitely one of the easier ways to setup independent compile environments. This page provides a very detailed step by step for having multiple chroot environments.
http://forge.ryzom.com/wiki/Building_Ryzom_Client_On_Debian
It was written based on Debian which is almost entirely identical to Ubuntu, the things to change should be easy to spot. If you go with such a setup you should be able to get the compile part down to one command.

I really strongly recommend using explicit sizing whenever possible. 64bit processors have been around long enough, and with core speed and die limits being what they are, the move to 128bit is not too far in the future. Taking the time to shift to specific sizing now can make the next transition painless. See http://en.cppreference.com/w/cpp/types/integer When you use the type intptr_t or uintptr_t you will always get a size that matches the register size of the architecture and that will have the highest speed. There is a small speed loss on some operations on 64bit architecture when working with a 32bit integer, the same is true of 16bit on 32bit architecture. Making sure counter variables are sized to match the registers will keep the speed from being lost.

Conceptually it is not that difficult to split path finding off into separate threads.
1. Assume the current modified A* continues to be used.
2. Each path finding calculation is done in its own thread.
3. Creatures initiate path finding, and display a thinking symbol until their path thread completes.
4. Creatures that change their mind about needing that path can do so since their thoughts and actions are still being processed on the main thread.
5. A creature that changes its mind sets an abort signal for its path finding thread.
6. The main thread will have map changing actions, some of which are of a significant enough level that all path finding should be held while the change occurs. The mechanics of this are not difficult. The main thread must know how many path finding threads are running. An atomic flag is set to tell each of the threads to pause, each thread responds to that pause with an increment to an atomic counter. When the counter is equal to the number of active path finding threads the changes can proceed, then the flag is cleared to allow the threads to continue.
7. Each of the threads on continuing increments its own internal counter for how man times the map has changed during its calculations. Each location that is added to the A* calculation would record what value that map change counter was at when it was added. When considering adding further locations from a given spot the counter would be checked. If the current change count is higher than that location the validity is checked and if the location is no longer valid all potential additions from that location are removed. This can lead to an incomplete path failing to reach its destination, and would start over from the source spot with the change counter reset to 0. If checking connectivity is fast enough then can be done with each map change or only when a starting over. This can result in some sub optimal paths when map changes occur during calculation, and so what dwarves do dumb stuff involving lots of extra walking all the time.

I think that covers all the basic conceptual components of switching path finding to multiple threads. I barely touched on implementation. The implementation would involve major changes. Among the first of which is to assure that any map changes that occur will not invalidate any pointer or array index held by the path finding calculations. The next major implementation hurdle is changing the creature behavior so that the main loop has a periodic check for did the path finding complete. The list of implementation details which can decide whether speed is gained numbers in the hundreds, if not thousands. If you look at what I said in conceptual item 6, you might notice that I am describing peeling apart a mutex structure into a combination group mutex and semi semaphore. Writing implementation details like that only comes from years of experience working with multi threading. Without that experience a programmer will tend to select from an existing mutex or semaphore and may even have the execution time that a user can perceive increase (it looks slower).

Overall, I think there is very little noticeable speed to be gained by splitting path finding off in this fashion. Threading would make a difference at specific moments when many path requests occur all at once, but at all other times the apparent gains would be minimal. Writing multi-threaded code has a steep learning curve and add whole new layers of complexity to debugging. While the path finding is a good candidate for asynchronous calculation, doing so would likely require Toady to share some portions of his existing code with a programmer that is experienced with the pitfalls of threads. Toady could then get a least enough advice to avoid some of the pitfalls. It would be a good experience for Toady and might lead to him recognizing other areas of DF that are good candidate sections for multi threading.

Toady does have a little experience working with others. BHeyler made the first SDL port, working from the Battle Champs source which Toady released specifically for that reason. That port lead to Linux and Mac versions by becoming a separate library section the source of which is included in every DF release. Baughn optomized the openGL code in that port. I recognized that the keyboard and mouse connections were a major time sink and rewrote them. Most of my code was ultimately scrapped because of style issues and availability to debug, Baughn wrote a replacement for what I had done with a similar design basis. Coordinating specific code would be difficult for Toady, but getting advice on how to do some things might not be as tough.

The food system has been broken since the 2D days. You can still make your dwarves cook alcohol if you know what your doing, so food is easily unlimited. Start with a good supply of turkey hens, since they have the highest egg count. Bring lots of plump helmets. Place your kitchen, brewery, and nest boxes such that the brewery is between the kitchen and nest boxes; then allow cooking the drinks. Ideally your brewery is directly next to the kitchen. Finally do not use any stockpiles for drinks so that they stay in the brewery and place the meeting area on the kitchen side as insurance against interrupted cooking tasks. Place a meat and fish stockpile anywhere farther away from the kitchen and meeting area than the brewery; I tend to use this same pile for the finished meals.

It took me 6 years (my miners got distracted by all the metal on the way) to set up a melting zone on a glacier so I could bring water to the spot I wanted to make a farm. In that time all my plants were obtained from trade, and prepared meals were my primary trade supply. When I got the farm started I had 600 drinks and 4000 meals available. I had to start throwing the meals down the volcano so I could train my cooks to be better.

The first suggestion in this topic is really the bottom most layer in solving the problem of dwarfs doing what people think they should be doing.

I have tried to figure out for years an easy way to tell the dwarfs what I really want them to be doing at any given moment. The complex solution allows a user to declare the intent to build things at specific places with specific materials, and the dwarfs would then place a higher priority on jobs to create the required items. That idea is a completely unrealistic goal.

The recent priority values on designations is quite helpful, but I have noted that a dwarf may choose a 'priority 7 remove construction' job over a 'priority 1 detail floor' job. This is a little problematic as I would expect the priority value 1 I set to have the highest precedence for all jobs. I have also noted that 'construct building' jobs and 'store item in stockpile' always have a higher priority than designation based jobs. Workshop activities also seem to have a higher priority than designation based jobs.

I would like to suggest that all jobs should use a single comprehensive priority schedule. Workshops as part of their profile could set a priority from 1-7, default is 4; and that value would be used for the jobs that they order. Designations already have a priority setting available to the user. Building and destroying buildings would default to 4, but could be helped.

You could add a new designation for priority that would work much like traffic, any jobs spawned within a region designated as priority X would have that priority, or existing jobs would be adjusted as the region is set. This sort of designation should affect building, destroying, stockpiling, and even dumping. The more I think about it, the more I realize that a user could use such a system to set their food region as priority 1 and most everything else would default to priority 4. This would satisfy nearly all complaints about priorities rather rapidly.

The addition of a priority designation also allows the player to point out that they really want all the stuff in a particular spot done ASAP. The only things I am certain that would require special redesigning are the code to select what item to: 'bring to a stockpile' or 'throw in dump'. Obviously, selecting items should attempt to use priorities instead of total random. What I am suggesting is a little bit of a coding nightmare when there are many different priority regions. I think part of the best fit solution is to do each priority in order from 1 to 7; using random selection of items within that priority, and if enough items within that priority region fill all the slots then there is nothing else to calculate.

The next part presses on to the more complex priority issues of what happens when you have a new job created in a high priority region.

Jobs should be replaceable, which is actually a huge fix. There is no reason to cancel a job when an item moves. There is little reason to refuse to complete a job because an item must be moved; when the item is Forbidden it is understandable, but when tasked to another job it is not understandable. There is no reason to cancel a job because the dwarf can't stand at the spot it planned on standing, or its path to a spot became blocked; try to find a new spot, and a new path. There is no reason to cancel a job because it's set items have moved, the items are unchanged and their new location is known. In all those cases an attempt should be made to not trouble the player; sometimes the dwarf would have to wait a few ticks because another dwarf is holding the desired object. Most of those cancellations are reported because jobs have a rigid location structure, and in many cases that justs gets in the way getting the jobs done. All of these cases appear to require a job replacement in the current system; and in most cases that replacement does not require player notification, in some cases it can even be done without the dwarfs being aware of the change.

How replacing plays into priorities is that when a new job is created it should be able to remove existing jobs of the same class that would have a lower a priority. Jobs already make an effort to not schedule a huge amount of tasks when there aren't enough dwarfs to cover those tasks. Being able to remove an already scheduled task and put in a higher priority task is a necessary step to any sort of job priority system.

I know there is a huge topic on this subject, and some strides have been made towards solving the idea that dwarfs just aren't doing the things we want them to do. I thought it best to make a new topic since I am suggesting a very simple measure that could make a huge difference, and I think it might be nice for it not to be instantly lost.

Now that dwarfs have an opportunity to pick their jobs, the simple solution is pick the job that can be done by the fewest dwarfs. The only additional information that must be built and stored is a count of how many dwarfs have a specific labor enabled. These values only change on user input, dwarf death, immigration, and child aging; making them easily built during load and updated as needed.

The dwarf when picking a job would look at all available jobs, hopefully designation based job are recognized with a simple boolean for 1+ available. Looking at the required labor for each job, if the number of dwarfs with that labor enabled is less than the last selected job's labor count then record that count and job. At the end of the loop the recorded job is the winner and the dwarf should do that, selecting a specific location if needed. Since jobs are already sorted nearly by labor type there may be some speed shortcuts available. Breaking the jobs list into multiple lists by labor type would offer the greatest speed, but would add the most effort to coding the changes.

The simplest part, selecting based on fewest possible dwarfs, would significantly help users in small fortresses and at the beginning when they have to enable many secondary labors on key dwarfs so those dwarfs can fill in when not busy, by causing those dwarfs to automatically prefer their specialized labor. It would also continue to be of benefit in larger fortresses so long as the user has dwarfs specialized.