Print

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

[Sunken]

Agree with Shades on the above: all effort should be spent on improving the algorithms rather than low-level optimization such as re-writing things in C. Until the algorithms are perfect it will yield more bang for the buck, and using C means making the code harder to change and maintain, meaning that Dwarf Fortress will take longer to arrive - which is even more important than the dorfs arriving at their destinations quickly

[Jifodus]

I highly doubt you'll be able to optimize the algorithms any more than what they currently are now.  For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.

For additional optimizations that would likely be beneficial is to look at path caching and picking inefficient paths using path caching vs finding the optimal path every single time.

Side note, using C++ may lead to inefficient implementations.  I'm really looking at the word "classes," because if you're already thinking of multiple classes you've already made it inefficient.  And unless you're planning on using template programming to create precompiled optimizations you'll probably do worse using C++.

[Impaler[WrG]]

People can quite wasting time discussing the language to be used, were using C++ it's practically universally known and is a fast compiled language and its what Khazad is written in which is serving as our platform for development.  Also no one who is actually writing code has suggested we use anything else and I'd only even consider such a change if they wanted it.  Keep the debate on the design of the Pathfinder.

[Sunken]

I highly doubt you'll be able to optimize the algorithms any more than what they currently are now.  For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.

Apart from the arrogant tone, I agree with the potential of letting the players help. TCZs can already utilize what is already in place - doors - to let the player influence the shape of zones. Waypoints is one possibility, surely. But would players bother?

[Slogo]

5: It might be a good idea to work in parrallel on other objects that require a path such as liquid or gaseos flows, as well as siege mechanics, allowing catapults and ballista to fire in varying degrees of rotation in both the horizontal and verticle plan

Liquids and gases don't path so there's no work to be done there. Toady's algorithm is already pretty slick for that type of calculation other than not allowing stability for partially filled containers of water.

The general path finding can definitely be optimized, I believe Toady is just using an A* algorithm at the moment which is slower than A* using a hierarchy. Even if it can't his path finding is a closed source solution, ours will provide a usable library for other projects and games.

[zwei]

I think you are spending too much time doing analysis. This way, you will likely never begin and your inital construct will be overcomplicated to degree of not being maintainable. Simply, things like multitile creatures, different movement methods, being abstract enough to be configurable to path anything etc ... they are nice to have, but they are not goals and can wait for later. Even after DF started using this to path mundane ground-tied, one-tile wide dorfs and cats.

First thing you need to have is interface: "Test client" and "Protype". Prototype does not even need to implement anything better than good old flood fill pathing algorithm. Primary goal being to agree on interface and to implement it and to use it ... so that any implementation relevant problems are discovered right away.

So, I guess typical usage will look like this:

Spoiler (click to show/hide)

[Ampersand]

I remembered something, that may point to an obvious inefficiency in the current code. The normal traffic weight for an open space is two. Experiments have demonstrated that reducing the normal weight on the entire map down to one produces a marked benefit in terms of frames per second, as dwarfs manage to determine paths faster.

[zchris13]

Less for loops and more while with some ifs.

[Silverionmox]

I highly doubt you'll be able to optimize the algorithms any more than what they currently are now.  For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.

Apart from the arrogant tone, I agree with the potential of letting the players help. TCZs can already utilize what is already in place - doors - to let the player influence the shape of zones. Waypoints is one possibility, surely. But would players bother?

They will do it automatically when defining rooms. Especially the new burrows will be useful in that regard (they will also reduce the length of the average path that needs to be found, and that will potentially mean huge FPS gains). Burrows will typically be defined functionally by the player (eg. the farming burrow, the kitchen and pantry burrow, the residential burrow, etc.) and that means most of the movement of a typical dwarf between burrows can be predicted. That opens perspectives.

We'll have to look what the player wants sooner or later, if we want to make something that allows the player to realize his wishes more effectively in the game on the computer. The easiest way to do that is to look at things he'll need to do anyway (defining burrows, rooms, placing doors, ...) Placing a door is usually a big flashing sign: CHOKEPOINT HERE. After that, why wouldn't the player want to tell his dwarves that 'that is the main corridor' and 'that is the main entrance' etc., instead of seeing every hauler queuing through the maintenance tunnel because that way it's one square shorter?

I remembered something, that may point to an obvious inefficiency in the current code. The normal traffic weight for an open space is two. Experiments have demonstrated that reducing the normal weight on the entire map down to one produces a marked benefit in terms of frames per second, as dwarfs manage to determine paths faster.

Changing it in the init settings doesn't make a difference apparently (129 dwarves and a fair bit of tunnels).

[Slogo]

Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.
Objects like doors should naturally be along any hierarchy divisions. Not because there's a door there but because it's a narrow chokepoint giving us a well defined region with limited routes to neighboring regions.

[zchris13]

Also, it is a convenient division.  Locking the doors would just clip the connections between the branches, which only works if there is a border there.

[Silverionmox]

Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.

Designing the Universal 3d Based Path Finding Algorithm might be a little too ambitious. If that's the goal, a lot more factors will have to be taken into account and as a result the project will become larger and less focused. That requires more work, more persons involved, more coordination and all that for less tangible and slower improvement in DF. If recruiting happens elsewhere too, fine. If it doesn't, the project will flounder due to overextension. I think it's better to develop a library primarily useful for DF, that's also useful for other projects, rather than a universal library that might also be useful for DF.

[Starver]

If we want to stick with 7 movement types, I'd drop "jump".  It's a cool idea, but I think it'd get too complicated, especially because if you wanted things to jump different heights you'd need a different movement category for each height.

I'm not married to 'just' seven types, they were just the seven that occured to me.  And another one nicely gives fills 'flag' byte.  Not to mention that I quite like the Build Destroyer routing possibility.  (Although had I also missed the Pet Passable possibility (being unintentiaonally alliterative, there)?)

As to "jump" (maybe partner with "climb", as jumps should will only ever be level/downwards, and climb only[1] upwards) and the limitations, the pathing could (similar to pathing with horizontal clearances) cull routes from with sequences of climb/jump-type pathing segments greater than the [TAG]-allowed amount for a creature of that size/ability.


Sorry, spent too much time on another project, at the weekend, to bash away at parctical implementations/demonstrations of my own ideas.


[1] Ignoring "climbing across an underhang" being similar to "jumping into/across a gap that happens to have an underhang above it".

[Starver]

I highly doubt you'll be able to optimize the algorithms any more than what they currently are now.  For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.

I think there's two different Optimisations at stake here:

• Writing an established algorithm in better code, by one or more measures of 'better' (neater, quicker, less memory intensive, easier to use, whatever)
• Actually using a "better algorithm" that is optimised for what the code is used for.  A bit like the DFMap-thingy system optimises BMPs far better (non-lossily) than even PNG, given the expectations of the image being in cells and of limited cell types, or the way that JPEG's lossy compression is 'good enough' for smooth/photographic images even if it causes artefacts if misused/badly tuned to its subject, and gives a smaller footprint.

There's possibly a third, but right now I've still got some more thread-reading to do, so I won't complicate matters.

[Slogo]

Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.

Designing the Universal 3d Based Path Finding Algorithm might be a little too ambitious. If that's the goal, a lot more factors will have to be taken into account and as a result the project will become larger and less focused. That requires more work, more persons involved, more coordination and all that for less tangible and slower improvement in DF. If recruiting happens elsewhere too, fine. If it doesn't, the project will flounder due to overextension. I think it's better to develop a library primarily useful for DF, that's also useful for other projects, rather than a universal library that might also be useful for DF.

Well obviously that's why we're keeping it focused on Dwarf Fortress, I just don't think we should rely on things ultimately DF specific so the game can keep a broader application to other tile based rogue-ish games.

For example doors, or more generally dynamic open/shut tiles (in DF's case this would also mean floodgates, bridges and hatches) are a good criteria for breaking up regions. It's something that would likely apply to other games. Something like stockpiles, room definitions, zones, or burrows on the other hand are very DF specific and would likely pose problems for applying the game to other applications. Even with DF these are a bad idea, how are you going to optimize pathfinding based on room definitions in Adventure mode?