Print

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

[Caldfir]

My comment was more of a "wouldn't it be cool if" type statement.  I agree it would be hard to implement, and it isn't obvious that there would be improvements vast enough to support such effort. 

In any case the first step would be to come up with a multithreading strategy for pathfinding, the most obvious being simply giving every creature their own thread. 

Anyway, I like pathfinding discussions. 

[No1]

Yeah this discussion is really what DF needs, just hope Toady sees it and start thinking about some way to improve it. I know there been countless of these threads and do not think they had any significant impact sadly.
On the multi-threading I do not think every entity should get one thread as the overhead for threads might be to much if you have 200 threads. But just be able to run on two cores should provide around 60-70% improvement in performance if the way the data is kept thread-safe is not draining to much performance.

There have been lot of complaints on Toady that he holds the code secret but I can not blame him for that, the amount of time he has put on DF is a good enough reason to do that. However I think he should release some specifications on the interface the path-finder should use.

That way a outsider could code something using those specifications and let Toady try it, it's not much thats needed. The path-finder needs a way to represent the map, it's probably a three dimension matrix with "tiles". The tile has a state, blocking or unblocking, a cost (the traffic zones).
The return value of the algorithm is most likely a linked list of tiles specifying a path.

I would happily code something like this but I'm not comfortable enough with C/C++ but I think we have a lot of people here that are.

[Xgamer4]

I'm not saying it's much, I'm saying it's enough.

But it's not. GPUs are incredibly specialized pieces of software. Assuming I'm remembering correctly, GPUS are very good at performing simple, massively-parallelizable, instructions. Anything beyond this and they start to stumble, and as soon as you ask them to perform any kind "if-then" statement, or something similar, you've murdered every performance gain you'd hope to gain, and then some.

Just going off what I've heard, admittedly, but it makes sense.

[Caldfir]

On the multi-threading I do not think every entity should get one thread as the overhead for threads might be to much if you have 200 threads. But just be able to run on two cores should provide around 60-70% improvement in performance if the way the data is kept thread-safe is not draining to much performance.

Ah, yeah, for a CPU implementation that's true, but "threads" on a GPU are a little different (they aren't really threads) and have less overhead. 

One step in the right direction would probably be to at least slap the pathfinding (all of it) on a separate thread from the main DF process.  Like was already mentioned, however, tou end up needing to let creatures pause for a frame or two while they wait for pathfinding instructions, which might get annoying depending on the implementation. 

I'm not saying it's much, I'm saying it's enough.

But it's not. GPUs are incredibly specialized pieces of software. Assuming I'm remembering correctly, GPUS are very good at performing simple, massively-parallelizable, instructions. Anything beyond this and they start to stumble, and as soon as you ask them to perform any kind "if-then" statement, or something similar, you've murdered every performance gain you'd hope to gain, and then some.

Just going off what I've heard, admittedly, but it makes sense.

Well, the nice thing is that if you're just going off a straight BFS or Dijkstra then you're just adding nodes to a set, which doesn't necessarily require substantial control flow bottlenecks (again you would have to be clever about it). 

The bottom line is that I don't think anyone has ever even tried to do it, so we don't really know if it can be done or how good it could be if it was implemented efficiently.  It really is a bit of a pipe dream at this point. 

[Farmerbob]

On the multi-threading I do not think every entity should get one thread as the overhead for threads might be to much if you have 200 threads. But just be able to run on two cores should provide around 60-70% improvement in performance if the way the data is kept thread-safe is not draining to much performance.

Ah, yeah, for a CPU implementation that's true, but "threads" on a GPU are a little different (they aren't really threads) and have less overhead. 

One step in the right direction would probably be to at least slap the pathfinding (all of it) on a separate thread from the main DF process.  Like was already mentioned, however, tou end up needing to let creatures pause for a frame or two while they wait for pathfinding instructions, which might get annoying depending on the implementation.

Just add a new job "Getting Bearings" and make it take a minimum of a couple steps.  This will also help debug the new pathfinding.  If you have dwarves standing around doing nothing with the job "Getting Bearings" you know it's likely a pathfinding glitch.  It sortof makes sense to have dwarves stop a second or two and think before they run off to grab and carry things.  I mean, it's not like as if they are computers, right?  They are dwarves.  Lol.

[kotekzot]

I'm not saying it's much, I'm saying it's enough.

But it's not. GPUs are incredibly specialized pieces of software. Assuming I'm remembering correctly, GPUS are very good at performing simple, massively-parallelizable, instructions. Anything beyond this and they start to stumble, and as soon as you ask them to perform any kind "if-then" statement, or something similar, you've murdered every performance gain you'd hope to gain, and then some.

Just going off what I've heard, admittedly, but it makes sense.

I was answering the point that GPUs don't have enough instructions to execute a pathfinding algorithm, not arguing that it would be terribly efficient, as that is beyond the scope of my knowledge.

[No1]

One step in the right direction would probably be to at least slap the pathfinding (all of it) on a separate thread from the main DF process.  Like was already mentioned, however, tou end up needing to let creatures pause for a frame or two while they wait for pathfinding instructions, which might get annoying depending on the implementation. 

If the game is allowed to run at the same time as the pathing occurs then there will be consistency problem of the data for the threads. One way to make sure the pathing thread is not affected by the main thread is to make a complete copy of the map but that will be incredibly slow and memory inefficient. One approach could be to just ignore the fact that a node that already has been visited can be changed and let the entity handle the problem if it arise. I think it is how the pathing is now (ever seen a dwarf path to a locked door and just show a "?" and then path around it?)
The danger with multi-threading is that if something bad can happen it will happen and the result will be lots of angry people having crashes in their game and due to the fact that it is multi-threaded it is very hard (read almost impossible) to pinpoint the problem.

[Niseg]

My sumulator covers quite a few concepts but let me go over the complexity so you know what kind of slope you need to scale when pathfinding.

This little star represent the number of directions you can go without diagonal z movement.

\ | /
-U D-
/ | \


There are 10 directions to pick from. With diagonal movement there are 26 potential nodes. This means the growth is at a rate of about k/2 per step  of A* which is probably around O(min(Nmax,(k/2)^N )complexity  . As far as I checked there is a major penalty to visit a node . After numerous tests with my simulator it's not uncommon for A* to look at 50% of the accessible nodes before it finds a path. A* works well when there are no walls on its way. When there is no path to the target it would go through each and every accessible node.

I already implemented a hierarchical system which relies on a Breadth first search collider . It adds a bunch of evenly spaced nodes to a BFs queue and outputs a map of "visited nodes" with markers. it also figures out all the access points between rooms (I only save one) and this information is used to generate a "room graph". A path search consisting of a room to room search path search (on the edges) and then A* to the access point and then A* to the next access point until the destination is reached.

Raw results show that only 3-4%  (not much more than necessary) The smaller paths can be distributed between the frames and when there is no path the search fails with a minimal penalty rather than maximum.

My current code is JS but it can easily get converted to C. The algorithms are super basic . This project is currently on halt because of other distractions .

If you are brave you can try my  128X128 version with the map I tested ( I recommend google chrome, if you change the maze click "Recreate wp rooms "). My algorithm is called "advanced room no path cache" . My regular version is 32X32 or so and you can find examples on the thread in my signature.

Be aware I optimized the A* so it takes 100 thousand iterations instead of almost 200 million  . This made the difference between the room pathing . My A* still has almost 20 times more iterations than my algorithm because it's directly related to the number of nodes you visit during your search ( O(log n) insert  and O(1) search for min).

You can upgrade your horse to pull the cart up the slope but the longer you go the steeper the slope until you hit a wall and your FPS hit 0.

[thvaz]

Yeah this discussion is really what DF needs, just hope Toady sees it and start thinking about some way to improve it. I know there been countless of these threads and do not think they had any significant impact sadly.

Maybe it is because this thread didn't got to "Toady sux at coding!1111" as so many others.

It is a nice read, by the way, for those like me who have only superficial knowledge about pathfinding algorithms.

[deek0146]

Heh well this has kinda become a large discussions :p

The main things people seem to be arguing about is two things: How should it be implemented (GPUs vs CPUs, algorithmic improvements vs multithreading improvements etc), and what should Toady do (release his pathfinding source, rewrite it himself?), either way its certain that everybody agrees on the fact that something needs to be done, and the sooner the better as dwarf fortress is only going to get more and more intensive.

With consumer level hardware reaching a clock limit of around 3.4Ghz, and expanding to multiple cores instead, he can no longer depend on improvments in hardware to counter the effects of a more detailed world simulation without utilising multithreading. Its only a matter of time before dwarf fortress is laggy on embark on even the best computers available.

[Lord Urist]

ok, so I know extremely little about programming and computing, but an idea's occured to me (for you to subsequently rip apart and point out why it won't work):

make use of the high/medium/low/restricted path designations such that when searching for a path, it at first only tries to path through 'high' tiles. If it can't find a path, then it tries to path through all tiles that have either 'high' or 'medium' designations. If it can't do that, then it tries using 'high', 'medium' or 'low' designations.

A few things with this:
-it doesn't use restricted tiles. Obviously it could be extended so that it would try that after the high/medium/low one didn't work, but it would be a nice way of effectively telling the dwarves THAT THEY CAN'T WALK THERE - for all intents and purposes it is a wall.
-this would only work for dwarves, they're the only ones who care about the designations
-doing this wouldn't slow it down from having to add up the 'value' (determined by whether it is high/medium etc.) of the tiles and work out the best route, as I vaguely understand it does presently. It only needs count the number of tiles.
-if there is a very long 'high' designated route, they will prefer that to a very short 'medium' designated route. But then you designated it as 'high' for a reason, right? So it wouldn't be too much to expect for the player to lay down a few 'high' routes, and if nothing else it gives you more control over where the little blighters try to go.
-it requires multiple checks, first for high, then for high/medium etc. I don't know if this is sufficiently bad to make this inviable, especially because if you just lay down some 'high' pathways you don't have to worry there.
-perhaps mark every place your dwarves mine or build as being 'high' automatically? (this could be configurable in an option menu) This would save a lot of micro when laying down 'high' pathways, because in most cases your dwarves will largely do it all for you.
-anything impassible (water/lava/walls etc.) could be automatically marked as 'restricted', so it doesn't have to check for both restricted designations and natural obstructions.
-if there is no path then it goes through all 3 iterations. My lack of programming knowledge comes in here, but is it possible to quickly check if there is ANY path? If it is quick then that could be added before it checks for a 'high' path.
-if a dwarf is completely hemmed in by 'restricted' designations, and then something nasty comes along like lava or a zombie whale, he won't budge an inch to save himself.

Anyway, done.

[No1]

ok, so I know extremely little about programming and computing, but an idea's occured to me (for you to subsequently rip apart and point out why it won't work):

make use of the high/medium/low/restricted path designations such that when searching for a path, it at first only tries to path through 'high' tiles. If it can't find a path, then it tries to path through all tiles that have either 'high' or 'medium' designations. If it can't do that, then it tries using 'high', 'medium' or 'low' designations.

I did not read all that you wrote but just pointing out something, it does in fact search in the high traffic paths first sort of at least. What it does if it has the choice between high speed tiles (cost 1) and restricted (cost 100) it will choose 100hundered high speed before even trying the restricted tile. That is how weighted path finding works. Hope this clears things up.

So if you want your dwarfs to path a little better, put lots of restricted tiles around (set the cost high) and make some high speed highways.

Do not take this as a "OMG WTF YOU DO NOT ANYTHING" I'm in fact glad that this thread is getting lots of response even from the non programmers. Who knows some idea might come from a non-programmer even.

[Lord Urist]

I already knew that much 
My suggestion is that the different levels have no weighting in the algorithm as such, but define the algorithm - first iteration it effectively considers everything but the high-designated tiles as impassable, then the next iteration effectively defines everything but the high- and medium-designated tiles as impassable, etc. Because there would be fewer high-designated tiles than every other tile, then if you take the time to use the system it should significantly cut down the time needed to figure out paths in the majority of cases.

So it kind-of becomes the player's job to define the routes which the dwarves can use, but they'll still manage if you can't be bothered as it'll just find a route in the second iteration.

Having said that, there might be some additional things that can be tacked on regarding weightings to get dwarves to take more optimal routes, but that's beyond my knowledge.

[No1]

Well I think that it would not make it faster. Consider the worst case scenario where the goal is on the last searched group of tiles, in this case the algorithm will go through the first group n times, the second n-1 times etc to the last until the tile is found. As I said the use of weighting will produce this functionality, because the algorithm will go through most of the highspeed tiles before even considering one restricted tile but it does not start over.

[Lord Urist]

...are you saying if the goal is on, say, a low-designated tile? Then I guess it'd have to automatically cut to that part of the algorithm, or perhaps consider trying to find a nearby high-designated tile, and then trying to get there by crossing a few other tiles.
I didn't follow your explanation, but I just figured if you, the player, could designate some 'approved' ways then it might make it quicker as it can take advantage of our intelligence to figure out a good route that it can then copy. But idk, the most programming I've done is design a 2d maze game using ascii characters () so down goes another idea, I guess.