Print

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

[Willfor]

So we are getting graphical optimisations to help older computers run DF faster, and now (possibly) pathfinding optimisations to help newer computers run DF faster? I am liking how the future of DF is looking recently. A lot.

[Optimizt]

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

[Willfor]

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!

[Optimizt]

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!

[nagual678]

I was thinking, perhaps something similar could be done with liquids ? I'm sure I'm not the only one getting pretty bad slowdowns when activating the latest typically convoluted feat of dwarven engineering involving tons of pumps etc

[Tormy]

I was thinking, perhaps something similar could be done with liquids ? I'm sure I'm not the only one getting pretty bad slowdowns when activating the latest typically convoluted feat of dwarven engineering involving tons of pumps etc

Well with multi-threading, that part of the game can be "speeded up" also...but if that won't happen, even the multi-threaded pathfinding would mean a major FPS boost.

[Mu.]

Nothing kills my DF framerate quicker than entities pathing between z-levels.  I'd love to see something done about it.

[Rysith]

A* on the graph should be nice and fast. You could probably even get away with only updating the graph on path-changing events, like cave-ins, constructions, etc., and let everything assume that its path was fine unless told otherwise, which would reduce the paths that needed to be found.

For the multithreading, you'd need to pause all the pathfinding during update events, but traversing the graph with independent entities should be fine regardless of how many processors you throw at it. You'd need some hacks for tracking moving objects, especially across node boundaries (like the liason tracking down your baron), but that should be doable, and not the general case. You'd also need a way to be informed of state changes in your target (pathing to a now-rotten food item), but the ticks give you a nice way to do that.

You'd also likely have to fall back to normal pathfinding within nodes, but since those will be short paths it shouldn't be time-intensive at all.

[bhelyer]

I was thinking, perhaps something similar could be done with liquids ? I'm sure I'm not the only one getting pretty bad slowdowns when activating the latest typically convoluted feat of dwarven engineering involving tons of pumps etc

Actually, an example game using DF's liquid handling code could be pretty cool...

[Footkerchief]

Since pathing optimizations that don't involve threading are being mentioned, here's some relevant past threads:

Path caching by sir monko
Route caching by Ogantai

[Veroule]

I was actually just thinking about this in vague general terms earlier, before reading this topic.

My rough thoughts are:
1. All path finding should be done in seperate threads.  This requires sectioning for the connectivity map and the actual map.  When sections lock then the main thread can't update either of these.
2. In order to keep sectioning from putting us right back into a single threaded mode each thread would have to lock, copy, and release the needed data.
3. Pathfinding may then occur on outdated data, removing the some of the omniscience of creatures.  This is good.
4. When something wants to find a path it should start flashing a thinking icon.  DF already has a mechanism for this, but it is very rare to see.  Then it would put its path request into a distinct thread, and await the reply.  Each path request would be a completely seperate thread in order to simulate that specific object thinking.
5. Pathfinding threads must be created as a lower priority in order to see a speed gain in the main thread and naturally extend the 'thinking time' of path requesters.
6. Extending #4 and #5 we can have the thread sleep early or use a higher priority based on the inelligence of the path requester.  Further simulating the intelligence by speed of deciding where to go.

The sum of the thoughts I had earlier would result likely result in higher FPS with dwarves doing less per frame.  I think that from a design perspective it is the correct concept.

[Andir]

I was actually just thinking about this in vague general terms earlier, before reading this topic.

My rough thoughts are:
1. All path finding should be done in seperate threads.  This requires sectioning for the connectivity map and the actual map.  When sections lock then the main thread can't update either of these.
2. In order to keep sectioning from putting us right back into a single threaded mode each thread would have to lock, copy, and release the needed data.
3. Pathfinding may then occur on outdated data, removing the some of the omniscience of creatures.  This is good.
4. When something wants to find a path it should start flashing a thinking icon.  DF already has a mechanism for this, but it is very rare to see.  Then it would put its path request into a distinct thread, and await the reply.  Each path request would be a completely seperate thread in order to simulate that specific object thinking.
5. Pathfinding threads must be created as a lower priority in order to see a speed gain in the main thread and naturally extend the 'thinking time' of path requesters.
6. Extending #4 and #5 we can have the thread sleep early or use a higher priority based on the inelligence of the path requester.  Further simulating the intelligence by speed of deciding where to go.

The sum of the thoughts I had earlier would result likely result in higher FPS with dwarfs doing less per frame.  I think that from a design perspective it is the correct concept.

The only problem I see with this is if you have hundreds of dwarfs on a really slow computer, you may have dwarfs that think so long they get nothing done because they'd get hungry/tired before finishing and then have to calculate a path to their bedroom/dining room and sit in the queue again waiting to die.

Of course, if your processor is so busy that this happens, you probably have other issues besides thinking dwarfs.

[Veroule]

The only problem I see with this is if you have hundreds of dwarfs on a really slow computer, you may have dwarfs that think so long they get nothing done because they'd get hungry/tired before finishing and then have to calculate a path to their bedroom/dining room and sit in the queue again waiting to die.

Of course, if your processor is so busy that this happens, you probably have other issues besides thinking dwarfs.

Yes that is exactly what would happen.  If the FPS_CAP was set high enough the main thread would churn along at that rate and starve the pathing threads of processing time.  Because the main thread keeps going the dwarf gets hungry, thirsty, and sleepy while awaiting a path.  Then has to cancel that path thread and start another.  Things like this are part of the reason why multi threading hasn't been done.

[MuonDecay]

I was actually just thinking about this in vague general terms earlier, before reading this topic.

My rough thoughts are:
1. All path finding should be done in seperate threads.  This requires sectioning for the connectivity map and the actual map.  When sections lock then the main thread can't update either of these.
2. In order to keep sectioning from putting us right back into a single threaded mode each thread would have to lock, copy, and release the needed data.
3. Pathfinding may then occur on outdated data, removing the some of the omniscience of creatures.  This is good.
4. When something wants to find a path it should start flashing a thinking icon.  DF already has a mechanism for this, but it is very rare to see.  Then it would put its path request into a distinct thread, and await the reply.  Each path request would be a completely seperate thread in order to simulate that specific object thinking.
5. Pathfinding threads must be created as a lower priority in order to see a speed gain in the main thread and naturally extend the 'thinking time' of path requesters.
6. Extending #4 and #5 we can have the thread sleep early or use a higher priority based on the inelligence of the path requester.  Further simulating the intelligence by speed of deciding where to go.

The sum of the thoughts I had earlier would result likely result in higher FPS with dwarfs doing less per frame.  I think that from a design perspective it is the correct concept.

The only problem I see with this is if you have hundreds of dwarfs on a really slow computer, you may have dwarfs that think so long they get nothing done because they'd get hungry/tired before finishing and then have to calculate a path to their bedroom/dining room and sit in the queue again waiting to die.

Of course, if your processor is so busy that this happens, you probably have other issues besides thinking dwarfs.

You would definitely have other issues besides that, yes... there are good reasons for having "minimum requirements", too... so people know that they won't have a fruitful experience if using that sort of hardware that's simply incapable of handling the load and still playing properly.

And to the OP, if you can succeed at this you will have done a really useful service to DF and we'd all be grateful. Judging by the recommended requirements I'm starting to see on games the CPU market is likely to be shifting more towards multiple cores rather than faster cores. Considering that, in coming years a lot of people are going to be a lot more likely to have, say, a 2.13ghz dual-core like mine... than a 4ghz single core, which would probably run DF a lot faster than it runs on my own system. I'm likely to upgrade to a 2.4ghz quad core in fact... and one thing that really bothers me is knowing that DF would only wind up running on one of those cores and that despite dropping $190 on a new CPU I would expect that DF would only run incrementally faster on the new one despite the remarkable increase in net processing power available.

That would otherwise have produced an unfortunate quandary where DF would run at its best in a hardware configuration that's unlikely to be ideally suitable for playing mainstream games, and players like myself would suffer for it.

[Andir]

Don't get me wrong, I'm all for threading.  I do it in my work for projects that require processing tens of thousands of files every night.  I'm just interjecting that priority based thread handling has some pretty ugly side effects.