Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[TurnpikeLad]

As a budding programmer but long time DF fan, the more I venture into writing multithreaded programs the more I've been ruminating about pathfinding and multithreading in dwarf fortress.

Sorry if this is rehashing discussions of the past.  I was wondering what people thought on a couple questions:

* Imagine we attack the problem of pathfinding by starting a new thread for each creature every time they need to path to a new place.  How much information must that thread have access to?  Seems to me the minimum amount of data the thread needs is a starting location, an ending location, and a linked network (each node corresponding to a tile on the map) that it can search to find the shortest distance.  If so, that's the only data which needs to somehow be made threadsafe.

Is that enough data that it is prohibitively expensive to make a copy and pass it to the new thread each time a creature has to pathfind?  I'm imagining that the main program saves a map network every ten frames or something, and each thread takes its own copy of that updating-every-10-frames network so that it can keep working even across refreshes.

* If it turns out that the network is too large to copy for each thread, how plausible do you think the following solutions might be:
- The main program saves a copy of the map network and starts all pending pathfinding requests as new threads.  It only saves a new copy once all threads have completed, however many frames that takes.  This allows all threads to access the same unchanging copy of the map network, preventing us from having to create a new copy for each thread.  Pathfinding requests that come up during the process are started as new threads in the next cycle.
- The main program starts a new thread every x frames (10?) that will handle all pathfinding requests that cropped up in that time period.  That thread is passed its own copy of the map network.  If it takes longer than 10 frames to finish processing all the requests, no matter -- a new thread will be started to handle the new requests.  This way we aren't held up for a long time if, say, 200 dwarves all want to pathfind at once.
- All pathfinding happens on a single constantly running pathfinding thread that is always dequeueing from a list of creatures that require pathfinding (only enqueued by the main thread.)  Every x frames (10?) it gets a request from the main thread to stop after finishing the current pathfinding task and update its copy of the map network.

* How long is too long when it comes to pathfinding algorithm execution time?  If the main game logic were running on a different thread from pathfinding, how many frames of game time are too many between a creature starting to pathfind and obtaining the correct route?  What's the failure mode if it takes too long for dwarves to find a path?  I imagine one danger is that the map might change, but it seems to me that if that happens it isn't too hard to detect that the path isn't connected anymore and start a new pathfinding thread.

I personally would not be too upset if dwarves took ten or so frames to "think" about their destinations, as long as the game isn't running so slowly that those ten frames take longer than a couple seconds.  Sure we'd get a lot of path cancellations because the dwarves are running on old map information, but I would be ok with that if it meant general speed improvements.

[Halnoth]

I think this belongs in the suggestions or general forum. This is not something that can be done through modding. Maybe DFhack but I doubt it. Even if DFhack could do it, I suspect that the lag and errors generated by the amount of data being pulled from dwarf fortress and fed back in would probably crash the game. Naw this is something that Toady would have to do.

[jecowa]

Maybe he thinks Dwarf Fortress modding involves modding the source code.

Maybe DFhack but I doubt it.

Yeah, I kind of doubt that the DFHack API has calls for that.

[TurnpikeLad]

Just thought that modders might have more experience with programming than people in DF general.

[milo christiansen]

In my experience, no. Most modders can't be bothered to learn even the basics so they can use DFHack more effectively.

That said, even if we all knew how to program it wouldn't help much for this topic, as no one has access to the DF source code.

Now some problems with your first post:

... starting a new thread for each creature every time they need to path to a new place.

A very bad idea. You end up losing lots of time creating and destroying threads. It would be much better to have a fixed size pool of pathfinding thread that are reused as needed.

Is that enough data that it is prohibitively expensive to make a copy and pass it to the new thread each time a creature has to pathfind?  I'm imagining that the main program saves a map network every ten frames or something, and each thread takes its own copy of that updating-every-10-frames network so that it can keep working even across refreshes.

When you have a problem like path finding you don't want to work with a copy of the data, you work with the data itself concurrently with something that does not need to change said data. In this case it would be better to save "change commands" listing what needs to change during the update phase, and flush them all in one go after locking the map structure.

Basically you run the pathfinder in one or more threads, and the functions updating units, etc in other threads. Once all the update threads are done you  lock the map and resolve all changes. If possible you do this several times so you pathfinding doesn't have to wait for items to finish, etc. Basically each thread does it's thing, then locks the map and flushes all of the changes it needs to make all at once. This way different update functions block each other as little as possible.

You haven't done much with multithreading have you?

How long is too long when it comes to pathfinding algorithm execution time?  If the main game logic were running on a different thread from pathfinding, how many frames of game time are too many between a creature starting to pathfind and obtaining the correct route?

1 frame, because if it takes longer than that to find a path you are doing something wrong. Remember, the whole point to multithreading is concurrency, path finding should happen at the same time as the other stuff. Games can be designed to allow path delays, but it wouldn't work well with DF because the map can change and destroy all your work, wasting time. Better to get it right the first time.

Multi threading a game like DF results in it being split up something like this:

* Start updating everything that does not change the map, which is just about everything except units, water/magma, tree growth, and a few other bits and pieces. This would be a long running thread that basically consists of a loop that starts the next iteration at the beginning of every frame and runs until it finishes one update cycle (the frame cannot end until it is done).
* Start a thread updating the units. This should do a quick pass to queue up path requests first, then go back and do a more detailed update when the path request part is done.
* Update that map tiles. This is done in the main thread, as it must be done before pathfinding can begin. Keep in mind that units are queue path requests and any non-map stuff is updating while this happens.
* Wait for the unit thread to signal that path requests are all ready. Hopefully this is just finishing.
* Tell the path thread(s) to go ahead. Paths are calculated ignoring units, as they are handled later.
* Wait for paths to finish.
* Start moving units, if a unit will move through another unit try to run a very short path finder to see if he can go around to rejoin his original path (no more than ~5 steps), if this fails just crawl over/under each other. This is done in the main thread. BTW: you should keep track of how many times the "avoid unit" pathfinder triggers for a specific path, if it gets to 3-4 times in quick succession then try to move half way along the detour and recalculate (this would have the effect of allowing units to walk side-by-side if possible.
* Go to the next frame (waiting for the non-map update thread(s) first of course).

[Quietust]

How long is too long when it comes to pathfinding algorithm execution time?  If the main game logic were running on a different thread from pathfinding, how many frames of game time are too many between a creature starting to pathfind and obtaining the correct route?

1 frame, because if it takes longer than that to find a path you are doing something wrong. Remember, the whole point to multithreading is concurrency, path finding should happen at the same time as the other stuff. Games can be designed to allow path delays, but it wouldn't work well with DF because the map can change and destroy all your work, wasting time. Better to get it right the first time.

In theory, pathfinding can be deferred by however many frames it takes the unit to move one step (i.e. it decides that it's going to walk to a particular destination, then ~10 frames later it takes its first step toward that destination).

[Halnoth]

In my experience, no. Most modders can't be bothered to learn even the basics so they can use DFHack more effectively.

I realize this is not meant as anything other than to inform the OP.

However, to be fair if it was easy to learn "the basics" everyone would be able to code. Just using myself as an example. I have two BS, one in chemistry and one in chemical engineering, and a masters in science education: physics. I've worked as an engineer and relied on my EE and CS counterparts to do anything coding related. They didn't expect me to know how to do it and I didn't expect them to know how to design or manage a nuclear reactor. Likewise as a science teacher, I certainly would not expect my students or even most adults to understand basic science before I teach them. Just because something is easy for someone who is trained does not mean that even "the basics" are easy for someone else who has a different skill set and training. So, it isn't necessarily that they can't be bothered. Rather, it is that the concepts, however basic they may be, are foriegn and in many ways incomprehensible. Just throwing that out there in defense of us coding illiterate types for whom "the basics" look like alien hyroglyphs.

All that said, thank you for your work on rubble.

[Reelya]

You could possibly build your own simple prototype in C++, get multi-threaded pathfinding working. It's not really relevant to DF development as Toady is on top of all that stuff already.

One problem with multi-threading pathfinding would be synchronization. e.g. it's always nice if an algorithm gives the same result every time. With pure multithreading and system stuff going in the background, splitting off threads could easily de-sync stuff that's going on. which is a big no-no as far as I am concerned. One way that could be mitigated would be if Units planned one move ahead. That way during the number of ticks while they are doing their current job, another thread can be calculating their pathfinding for their next task. They are then ready to roll on the very tick that their current task finishes, and/or there can be a set amount of "rest" frames each dwarf takes after finishing a job, and then game can stall if any more time is needed: it would still be much smoother than single-threaded pathfinding. The game could run a main thread at full speed mapped to a single core, and cram pathfinding into the other cores that way, without causing any sort of synchronization issues.

For making anything multi-threaded worthwhile, you probably also need to know about how memory-read ahead and cache works, so you can design data structures that work well. e.g. whenever you read from memory an entire cache line is actually loaded, which is ~64 bytes, and takes about 200 clock cycles. So you want to make sure there's no extraneous data mixed in the cache line for the task you're doing. That implies that for path-finding, the map should be stored in bits, with rectangular "regions". e.g. you use a 32-bit number to represent a horizontal "strip" of "tile passable" values. Then you pack these lines vertically. That means that a single cache line holds the passable values for 32 x 16 tiles, which means you don't have to jump to as many cache lines, and more of the cache is free to store the other path-finding info you're working with. Obviously, this implies you're not doing anything clever with higher-level clumping to speed up path finding however, in which case you could probably vastly decrease the memory requirements and up the speed.