Print

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

[Ghundio]

Another pathfinding thread... but I wasn't sure if people had seen this paper yet so yeah,

http://goo.gl/aKbz2: GPU Accelerated Pathfinding

Abstract
In the past few years the graphics programmable processor (GPU) has evolved into an increasingly convincing
computational resource for non graphics applications. The GPU is especially well suited to address problem sets expressed
as data parallel computation with the same program executed on many data elements concurrently. In pursuing a scalable
navigation planning approach for many thousands of agents in crowded game scenes, developers became more attracted to
decomposable movement algorithms that lend to explicit parallelism. Pathfinding is one key computational intelligence
action in games that is typified by intense search over sparse graph data structures. This paper describes an efficient GPU
implementation of parallel global pathfinding using the CUDA programming environment, and demonstrates GPU
performance scale advantage in executing an inherently irregular and divergent algorithm.

While this paper only shows the program running in the CUDA language which only works on nvidia GPU the concepts can be pretty easily transferred over to openCL which will run on all graphics cards.
The tests that they ran in the paper resulted in about a 55x speedup compared to the standard c++ implementation of A* with a handtuned compiler using SIMD intrinsic, which I don't is being used by df.

At this point its probably beating a dead horse asking Toady to implement multithreading but just wanted to give a example of an implementation that works so people would have an idea of how difficult or easy it would be to actually implement in dwarf fortress.

The only problems I can see with this is that the performance of the A* being run on the gpu goes up quicker with the more things that need to be pathed, so catsplosion would become something of the past and I'm not sure I want to live in that world.

[King Mir]

That's pretty neat. DF doesn't use the GPU for much, so this would be one place to change that, if only because many systems have powerful GPUs. It might be suitable.

On the other hand, although pathfinding is a major performance cost in DF, it is not the cause of most FPS death. Instead FPS death seems to be predominantly caused by large arrays of persistent objects that don't cache well.

[GreatWyrmGold]

Pathfinding is a big hit, though. It's why catsplosions are bad, why the population cap is only 200 

Anyways...for those like me who have no idea what you are talking about, what do you guess the plusses and minuses of this would be?

[King Mir]

Potentially it would mean faster pathfinding across the board. It would also mean that DF may benefit from a good GPU, instead of being entirely CPU and memory bound. If done poorly, it could make DF much slower on systems with poor GPUs, like laptops.

Thinking about it, separating pathfinding for threading purposes would kind of be a prerequisite to this.

[JanusTwoface]

Direct link to the PDF for those without a subscription to view original link.

Previous threads that have talked about pathfinding in general (and IIRC GPU pathfinding in specific):
- Improving Pathfinding. (Computer sciency)
- Spin the pathfinding off to other threads.

I think the two biggest problems with this would be:

1) Who would do it?

Toady One doesn't know how to do it and hasn't really expressed any interest in either learning how to correctly do multithreading (at least at the moment) or in finding someone else to do it for him. The idea of getting other people to help with the code has been discussed fairly extensively before and it seems like a no go, at least at the moment.

2) Would it actually work?

The method they presented in the paper is pathfinding on a much simpler structure than DF has with all tiles either being passable or non-passable, only two dimensions, and no dynamic features. Would it be able to cope with constantly changing pathing data (flowing water for example) and three dimensional data? I'm guessing not. One of the biggest costs of GPU algorithms is constantly moving data between the CPU and GPU.

Also, could the maps that DF uses even fit in a GPU texture? Even a 2x2 region has roughly a million tiles in it (~ 96*96*100). The largest example in the paper had only 340 nodes with 2150 edges between them. This could be somewhat offset by using some form of hierarchical pathfinding (discussed before), but then you'd have to constantly swap the data on the GPU between levels which would kill any performance gains.

[AutomataKittay]

I fear GPU-based pathfinding won't work very well, since, well, lower end GPU don't have enough memory to properly manage whole maps. Then there're those huge map lovers, which I'm sure is beyond all reasonable GPU.

And from my understanding of some attempts with GPU supercomputing, coding might even have to be GPU-specific, even more specific than a maker's lines, instead of being able to set up a general codeset for them all. That would cut out fairly huge percentage of DF players out.

Then there're the cost of learning how to do it, and cost of transferring information, which would be fairly high in both cases. You'd have to transfer the whole map and units' desired points over there.

And this GPU-based computation's nothing new, it's just becoming popular as people figure out how to tap them efficiently for massively parallel jobs.

In short, there're very little benefit for large amount of labor and probability of cutting off huge amount of player base.

There're a good reason that GPU computating isn't so popular, outside of supercomputing community, it's pretty hard to take advantage of to it's fullest.

[hermes]

I could be wrong, but in my experience this would not be viable.  I've had some rudimentary JCUDA experience and the type of computation required for GPUs is SIMP; Single Instruction Multiple Program.  Basically this means that the same code is executed at the same time over a data source.  The data must be stored within the GPU's memory to maximise efficiency.  For closed system models like the fancy real-time examples coders usually show, like water in a cup or something, this is fine.  But when you have to keep altering the map data, which is certainly the case with DF, then you have to shuttle data from the GPU to CPU memory and the time this takes kills any benefit you might have won.  Also, the nature of SIMP programming means that each 'entity' acts according to the same rules, the same instructions.  Again, fine for severely limited demos like thousands of drones wandering around an unchanging street, but not for a system as dynamic as DF.

Programmers tend to oversell what's possible.  The current use of GPUs for these kinds of secondary applications is extremely ad-hoc, but obviously does have potential.  We'll probably have to wait several years before more integrated systems come out that share memory with and have easier, standardized access to massively-parallel computing units.

[Starver]

Direct link to the PDF for those without a subscription to view original link.

Probably people found that this link didn't work, just thought I'd say, due to the way that the BBCode parser/encloser/converter deals with non-http:// URIs

For those that didn't find a way around it, try clicking the following 'bare' URL style link: ftp://ftp.niifaq.ru/local/57/6_term/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/GroupE/Avi_Bleiweiss-GPU_Accelerated_Pathfinding.full_paper.pdf (or, if all else fails, copy and paste what it says directly into the address bar).

The funny percent bits are because of the Russian characters, for those worried.  (Although always look out for strings such as "%68%74%74%70%3A%2F%2F", because that spells out "http://" and could be a redirection-based Phishing-style trap.)


On the subject of utilising GPUs, I'm wary of even assuming that a player's computer has a relevent GPU (yes, we can run a two-tier executable, where it can take advantage of one if it can take advantage of it[1]).  At some stage it's probably going to be a good assumption (as, perhaps, is 64-bitness), unless something else comes along to supersede that assumption, but I can't see an easy route towards this destination.

As already mentioned, multi-threading (making use of the still-not-ubiquetous multi-core nature of people's CPUs[2]) isn't really there (apart from the Baughn-bits of the graphics, if I remember correctly), and splitting more things onto more threads (including pathing) is probably the step to take, otherwise the CPU would just be waiting around for the GPU to do what it had previously undertaken, anyway.  Farming it as an entirely GPU thread (or whatever thread passes is is separate from and asynchronous to all else) lets the CPU do the other intensive things it needs to do.  Like liquid sloshing, or whatever.  (Actually, can we put liquid sloshing to GPU instead?  When we do have moving liquids, that seems to be the big constant slow-down item.)


[1] Although that's far worse, IMO, than running a program that "runs better on double a given amount of memory" before anyone wants to equivalise the two situations.

[2] Not so long ago, it was multiple-processors that was going to be the way forward, which is not to say that's been superseded, what with a machine not far from me with multiple multicore-processers.  Not tried playing games on that, though.  Yet.

[Niseg]

After looking at the problem a year or two ago I came to the conclusion the problem with DF is not the lack of processing power of the computer it's the complexity of the algorithm used for path finding.

A* is a very blind algorithm which doesn't see farther than it's next step. A* typically calculate the whole path ahead of time and when a dynamic event happen it will hit the wall and then calculate the path again.

What I was thought in the University is that if a problem is too complicated to solve it should be divided up into smaller problems. The Divide and Conquer approach does help reduce the complexity of path finding in a DF like environment.  What I did is use a modified breadth first search to create rooms and also saved their access points . This way the first path is decided between rooms and then there are many sub-paths that are calculated along the way to traverse the rooms. I didn't implement an update method and abandoned the project. You can check the thread about it for details and simulator. 

I think that the current world generator kind of goes around the problem by reducing the depth of the world(z). I'm still not sure about this because I haven't played DF for a while.