Bay 12 Games Forum

The intro to "Six Degrees of Inner Turbulence" by Dream Theater. The whole song is 42 minutes long

Covers a wide variety of Dwarven situations, from peaceful farming to glorious combat.

The somewhat poor quality version on YouTube:
http://www.youtube.com/watch?v=7Am_guS7WFM

The good quality live orchestral version on YouTube:
http://www.youtube.com/watch?v=tpK4HZegTD8

Or anything on "A Night at the Opera" by Blind Guardian. I mean, come on, look at the album cover.
The song "And Then There Was Silence" from the album is good for an epic HFS fight.
http://www.youtube.com/watch?v=snwvpJ7DxyY

And then there's "Harvest of Sorrow", also by Blind Guardian, appropriate when your fort is crumbling to its end because you pulled the irrigation lever without first sealing the farm up.
http://www.youtube.com/watch?v=lWXlHn4aKOQ

As much industry attention as DF is getting, I wish a company would throw a bunch of money, programmers, and artists at Tarn and Zach to expedite development.

Oh well, a man can dream.

Trying to multithread DF's pathfinding isn't going to work without almost a complete rewrite of how DF works, I'm afraid. That's something for T1 to attempt in DF 2.0, what we need now is route caching. Not only is it easier to implement, but it will provide a greater performance increase for all but a few trivial cases.

Multithreading isn't as hard as you think. In many cases, making an algorithm run parallel is as simple as a few function calls to the appropriate library.

If A* pathfinding is implemented in DF like I think, it would not be hard at all to spread the pathfinding load between processors with little effort. That's what I'm working on right now

Also, I was thinking of splitting the map into a quadtree.  The quadtree algorithm can be summarized as follows:

• Take a region with dimensions 2^n x 2^n, where n is any integer
• If contents of that region are not uniform, divide it into four new regions and repeat for each of the four regions.

Since the map is already represented as 16x16 blocks, it is possible to split up a block like this:

The red shaded areas are regions that are blocked, and the green shaded areas can be walked on. The red outline denotes the four regions under the central node, the green outlines denote the regions under that region, etc. The good thing is that giant expanses of similar regions can be stored as a single node in a tree, saving memory and processing time.

I dunno, I think you guys are looking too deep into this. The way I'm working on it, the main thread creates (n - 1) worker threads, where n is the number of threads requested. The main thread does its share of computation no different than the worker threads. For example, on a quad core, the main thread would compute a fourth of the paths and the three worker threads would also compute a fourth of the paths.

As much as I love credit, I think you mean "Baughn and Kardos." I have been absolutely worthless in this thread. Though that is mostly because that while I understand the basic concepts involved in what coders like yourself are talking about, the implementation makes my head spin in five different directions. But keep on keeping on!

Whoops, yeah. Stupid confusing topic summary box!

Baughn and Kardos, those are really good suggestions and similar to something I had in mind:

Toady mentioned that the map is broken down into 16 x 16 x 1 sections of tiles. If each section could keep track of what other section it is linked to through open tiles, ramps, or stairs it would be possible to calculate which sections creature must go through before it worries about what tiles to go through. The only issue I can see with this is that though section X might be linked to section Y and Z, it may not be able to go from section Y to section Z through section X on the tile scale, if that makes sense.

Another optimization I had in mind is breaking the fort down into a tree, which is pretty much the same as the node idea. Most forts are subdivided into smaller sections (rooms, halls, burial grounds filled with noble warriors struck down by the HFS). Still thinking about the best way to do that, though.

Anyways, I've begun coding a little benchmark I'm calling "Cat Fortress." (Why cats? If you're asking this question, go allow cats to breed in your fort a while and come back to this thread when you're frustrated ) It will allow you to place tons of cats and have them path to random points or points you select. You will be able to manipulate the walls, floors, and stairs of various z-levels... basically a really, really, really, really, really, really, REALLY primitive DF. The map will be adjustable and size, and will pretty much present the basic problem of pathing in DF minus flows, enemies, etc. The hope is that I will be able to implement multi-threaded CPU pathfinding and CUDA pathfinding, which would pretty much eliminate the problem of pathfinding lag for GeForce 8, 9, and 200 card owners.

Hopefully I'll finish by the end of next week. After that, I might flow on over to optimizing something else

Great, fish are going to scratch up my couch and leave presents under my bed now too?