Print

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

[shadow_slicer]

movement flags.

Storing that many movement flags per tile would be a huge amount of data, relatively.

If you think about it the amount of memory needed to store an entire embark square is already huge. Toady uses some optimizations such as not storing empty space or areas that haven't been modified since they were generated.

In any case, there's no real reason we need to store the movement flags at all. They can likely be calculated on the fly based on the data Toady already needs to store about the terrain.

[Shades]

movement flags.

Storing that many movement flags per tile would be a huge amount of data, relatively.

Movement flags could easily be a bitset, if the unit pathing has the appropriate flags it can use that link if not it can't. Ideally we can link directly to the map anyway. You have to specify some form of system to allow pathing under different conditions. Either that or have a whole node map for each set of movement types, which I imagine would be more space.

[Teiwaz]

Movement flags could easily be a bitset, if the unit pathing has the appropriate flags it can use that link if not it can't. Ideally we can link directly to the map anyway. You have to specify some form of system to allow pathing under different conditions. Either that or have a whole node map for each set of movement types, which I imagine would be more space.

Why would you bother? Just get the information from the adjacent tile. You only need connectivity data for a simplified node network (pathing zones, TCZs, reference points) and there would be several orders of magnitude fewer nodes on the path network than there are tiles in the game, so memory wouldn't be an issue.

[Shades]

Why would you bother? Just get the information from the adjacent tile. You only need connectivity data for a simplified node network (pathing zones, TCZs, reference points) and there would be several orders of magnitude fewer nodes on the path network than there are tiles in the game, so memory wouldn't be an issue.

You need to know if your allowed to path to the adjacent tile, as mentioned linking directly to the map is the best option but we do need some way to tell.

[tylor]

1. If mobs are going to go somewhere together (like invaders, or dwarf detachments, or someone's pets), then there should be one (leader) pathing to the destination, and other pathing to leader. If leader is accessible for them.
Non-military dwarves should also rely on their designated leader if possible for tasks like mining and hauling. It will encourage to stick miners and haulers in groups (with military screen) even if player is not planning to fight with them.

2. Pathfinding should not affect FPS. Everyone has processor allowance for pathfinding. Followers can transfer their allowance to leader. If something can't find it's path soon enough, let it wait.

[smokingwreckage]

Would it be feasible to "stack" units, in the spirit of tile-based strategy games? So, a group would all jump in the same tile as their leader or other assigned pathfinder, path once and all move simultaneously to the destination, then de-stack on arrival?

[Shades]

2. Pathfinding should not affect FPS. Everyone has processor allowance for pathfinding. Followers can transfer their allowance to leader. If something can't find it's path soon enough, let it wait.

Of course it will effect FPS, it uses cycles and you only have so many. Any taken up with pathfinding can not be used for other things. DF is CPU heavy so it's not like we are waiting on the graphics card (unlike most modern games)

Would it be feasible to "stack" units, in the spirit of tile-based strategy games? So, a group would all jump in the same tile as their leader or other assigned pathfinder, path once and all move simultaneously to the destination, then de-stack on arrival?

Feasible, and relatively easy, however I'm not sure the amount of saving you'd get would be worth the special casing. The majority of pathfinding is fairly independent. Certainly worth trying though.

[Andir]

2. Pathfinding should not affect FPS. Everyone has processor allowance for pathfinding. Followers can transfer their allowance to leader. If something can't find it's path soon enough, let it wait.

Of course it will effect FPS, it uses cycles and you only have so many. Any taken up with pathfinding can not be used for other things. DF is CPU heavy so it's not like we are waiting on the graphics card (unlike most modern games)

It doesn't have to though... it's much more realistic to have a dwarf pause for a while than it is to abort fluid simulations.  (I'm referring to the frame calculation time.)

I tend to agree with tylor on this.  Pathfinding can be a secondary event in a closed loop game engine.  IMHO, pathfinding should be given a finite time to complete and if it's not complete in that time, further processing should be deferred until the next round.  All that looks like to the player is that their dwarf is planning their trip.  Maybe they "pull out a map and draw a route."  Not many people care if that takes more than one frame to complete.  Of course, minimizing this is important, but I feel that making the game wait while one dwarf decides what direction to take is a little asinine.

Personally, I'd love to have the actor mechanic shoved off to another thread that is independent of the world processing.  The main thread has enough tasks dealing with the proper placement of fluid, calculating cave ins, lever actions, and other minutia that forking AI into one or more threads would make the game feel more visceral even if the dwarf did take a second longer to calculate a path.

[Shades]

It doesn't have to though... it's much more realistic to have a dwarf pause for a while than it is to abort fluid simulations.  (I'm referring to the frame calculation time.)

It still has to be processed, it will effect FPS, it uses cycles and you only have so many.

You can limit it only so many calculations an update if you like and that will cause the dwarf to pause briefly but don't think that means it's not effecting FPS. The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.

[Draco18s]

The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.

Which is preferable in 99% of cases.

[Shades]

The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.

Which is preferable in 99% of cases.

I agree completely, although with DF I don't get that many spikes myself so I'm not sure how bad this problem is. Spreading the calculations across multiple turns only works if you get spikes of requests. Either way it still effects the frame rates.

[Exponent]

To what degree are people committed in their speculation to sticking with a deterministic simulation?  Many of the suggestions about pathing in background will kill all determinism, especially when running a fort on a different machine, or on the same machine with a different set of applications running simultaneously.  (E.g., what happens when you can normally run a 200 dwarf fort at 100 FPS with nearly instant pathfinding, but if you're compiling something in the background, dwarves end up taking an entire game-month just to figure out how to get to the nearest bit of food?)

There are ways to keep determinism while pathing in the background, but the efficiency improvements would probably be limited, and would come almost entirely from the presence of multiple cores.  And the code would probably become significantly more complicated in the process.

[Andir]

The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.

Which is preferable in 99% of cases.

I agree completely, although with DF I don't get that many spikes myself so I'm not sure how bad this problem is. Spreading the calculations across multiple turns only works if you get spikes of requests. Either way it still effects the frame rates.

Have you ever used the "All dwarfs except military are forbidden outside" at all?  When you trigger that, lock a major door in your fort or several other things that cause a mass recalculation there's a spike in processing (or in the case of DF, a severe drop in FPS.)  If not that, try assigning all dwarfs to military duty once.  They will path somewhere and stop.  Your FPS will skyrocket.  Heck, even in the current build all you have to do is designate an area to be ramped out and you can watch the pathfinding throttle your fortress or forbid/allow collecting stone outside.

I'd much rather have a consistent game/simulation FPS than have pathfinding impact general performance.

[qwertyuiopas]

The problem would mostly be what happens if/when the pathing changes mid-calculation.

One relatively simple solution would be to only calculate some number of paths per frame, based on laziness of the individuals and length of the paths, so that a few will be delayed a frame rather than drop the framerate.

Also, when finding jobs like mining, maybe a short-range flood fill might be useful? As mining often runs in veins, checking the nearest 5 tiles for further jobs and skipping pathing entirely would be a great improvement, both in expected behaviour and overall speed. Some similarily clustered jobs could also benefit from such a system.

[Richards]

From a technical standpoint I think the performance issues of dwarf fortress is the greatest limiting factor in the game for the future. I like the idea of a new separately-threaded path-finding routine but all this talk won't go anywhere unless Toady gives some kind of foundation to build an path-finding routine on.