Print

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

[FreakyCheeseMan]

Anyone know how pathfinding in DF actually works- like, the specific algorithm?

And anyone know how it could be made better- like, maybe with specific checkpoints the player adds? (So current pathing algorithm just gets you to the nearest player-defined node, which knows/can quickly compute the path to all other nodes, bringing you to the node closest to your target, and from there uses normal pathfinding again.) Would increase the amount of work the player had to do, but...

[Mason11987]

Anyone know how pathfinding in DF actually works- like, the specific algorithm?

And anyone know how it could be made better- like, maybe with specific checkpoints the player adds? (So current pathing algorithm just gets you to the nearest player-defined node, which knows/can quickly compute the path to all other nodes, bringing you to the node closest to your target, and from there uses normal pathfinding again.) Would increase the amount of work the player had to do, but...

Although it isn't really a complete answer to your question, Toady almost certainly uses some variant of A*.  I think the idea of player placed nodes to improve path finding is interesting though, and I could see how that could be useful.

[existent]

There's also the traffic designation, although I've never used it myself.

[Helmaroc]

There's also the traffic designation, although I've never used it myself.

It can be useful if you have 3 or more tile-wide hallways. Designating high traffic to the middle can sometimes help prevent confusion.