Print

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

[deek0146]

No1: No thats not neccessary, the point of this algorithm is that it calculates all of that for you. The scene graph generation isn't based on heuristics, but its detailed enough that it doesn't matter.

[No1]

No1: No thats not neccessary, the point of this algorithm is that it calculates all of that for you. The scene graph generation isn't based on heuristics, but its detailed enough that it doesn't matter.

Sorry I misunderstood the algorithm, I've now read the article and I like the idea. We now only have to get Toady to consider this for the game, I know he prefers to add content over optimizing current content (and who doesn't like to implement new stuff rather then changing already working stuff).

To make it viable I guess the algorithm should do the first pass to create clusters at embark (more loading time) and then each time a tile changes "blocking state" by something static (tree growing, wall built or mined out) the cluster should be updated. I do not think the increase in memory usage would be such a big impact because as my computer science lecturer said: "RAM is cheep".

[deek0146]

Lol your lecturer is right ><
The biggest thing that helps dwarf fortress in terms of memory usage is its simple 2d graphics. That also helps the speed of the game but not by as much.
The problem is Toady's reluctance to use other peoples code and to show his code to other people really.

It wouldn't noticeably affect loading times, obviously the node generation algorithm is quick enough to be run constantly (whenever the environment changes) so it has to be able to execute in a few microseconds.

[Farmerbob]

  I'm not a compsci person, so I don't know the lingo, but I've always wondered if it might be easier to program DF to path like a real person would path - by landmarks.

  This would allow you to create a reasonably small number of different precalculated paths.

  If every stockpile, workshop, or dedicated room had it's own node, then dwarves could look around to see what the closest node is to them at their start point, then the same at their finish point, and use precalculated paths for what is more than likely going to be the most complicated part of their trip.  Instead of calculating one long path, they would calculate two short paths on either side of a precalculated path.  Stairwells & ramps would probably need to be counted at nodes.

  This would lead to fairly organic & reasonably efficiently calculated pathmaking, a lot like a human might manage in a similar situation.

[deek0146]

FarmerBob: The best (and often most efficient) AI algorithms always try and model real human behaviour :p

That system is very similar to what most people suggest, with chacing popular paths, but I think a heirarchical modelling of the entire map is a better method than trying to pick and choose smart locations

[Fuco]

  I'm not a compsci person, so I don't know the lingo, but I've always wondered if it might be easier to program DF to path like a real person would path - by landmarks.

Indeed it is possible, the data structure used is called http://en.wikipedia.org/wiki/Navigation_mesh and it is used probably in every "big" game.

I would certainly not rule out the possibility of using this as a viable pathing strategy in DF. But in some respects, it's very similar to the hierarchical pathfinder suggested earlier.

[thvaz]

It is known if the largest drain in CPU is the pathfinding? I seem to remember someone made tests and discovered  that it was in fact the ammount of objects in a map. Maybe I'm wrong, though.

[Caldfir]

Yeah - someone had recently run a trace on processor time spent on various tasks, and "move creature" (or something) was eating the processor time more than anything. 

Another good idea might be to make use of the GPU for pathfinding calculations in dwarf mode (the idea has been bouncing around in my head for a long time).  The effectiveness of such an approach hinges on the fact that the GPU is built like a CPU with a bunch of super wimpy cores.  Most manufacturers now have a C++ based API for accessing the GPU for mathematical tasks now. The actual improvement to calculation speed is heavily dependent on careful implementation, and due to memory caching on a large map, pathfinding in DF might not be a problem well-suited to such an implementation, but still, the ability to access ~200 effective cores to calculate pathing data for multiple things simultaneously (which dont actually require any floating-point calculations) sounds like a pretty tasty chunk of optimization.  If it works

[No1]

Yeah - someone had recently run a trace on processor time spent on various tasks, and "move creature" (or something) was eating the processor time more than anything. 

Another good idea might be to make use of the GPU for pathfinding calculations in dwarf mode (the idea has been bouncing around in my head for a long time).  The effectiveness of such an approach hinges on the fact that the GPU is built like a CPU with a bunch of super wimpy cores.  Most manufacturers now have a C++ based API for accessing the GPU for mathematical tasks now. The actual improvement to calculation speed is heavily dependent on careful implementation, and due to memory caching on a large map, pathfinding in DF might not be a problem well-suited to such an implementation, but still, the ability to access ~200 effective cores to calculate pathing data for multiple things simultaneously (which dont actually require any floating-point calculations) sounds like a pretty tasty chunk of optimization.  If it works

The main problem with using the GPU is that the number of available instructions is not anywhere near the number for a regular CPU so I wonder if you really can do a path-finder that runs on the GPU. A first step should probably be to optimize the algorithm and just keep it on the CPU for now.

[kotekzot]

Pretty sure GPU instruction sets are turing complete, so there's no impassable obstacle.

[No1]

Well being turing complete is not really that much of a merit, even a sandbox with a couple of stones is turing complete (http://xkcd.com/505/).
I know that nvidia got CUDA but what does ATI have?

[kotekzot]

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

[No1]

However how is the SDKs for the cards? Had a quick look on CUDA and that seems to be very much like coding in C/C++ but what about ATI?

[kotekzot]

DirectCompute and OpenCL support nVidia and AMD GPUs, so there shouldn't be a problem.

[No1]

Besides the problem of creating a thread safe pathfinder, the use of locks could make it safe but there is a great performance loss when using locks.

I agree that if programed really well a pathfinder that utilizes the GPU will be efficient but the work to make it work might be to much for Toady, so I still thinks the implementation of a hierarchic pathfinder is a more realistic achievable goal.