Print

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

[SeveQ]

I'm just curious... how does pathfinding work in DF? Is the algorithm repeatedly called for every single creature on every single frame? Or is there some kind of optimization, for example that the algorithm is only called again when a creature hits an obstacle on its last calculated path that wasn't there when the path was calculated?

Just curious... Thanks! 

[IronValley]

Judging by how the game slows down in regards to population number, general chatter on the forum, and some processor benchmarks some guy posted lord knows when, I'ts rather safe to assume that pathfinding in DF can be drastically improved

[Shrugging Khan]

http://www.bay12forums.com/smf/index.php?topic=56041.0

No need to thank me. Or that OP. Its already done, after all...ehm. Whatever.

[NW_Kohaku]

... I wonder if that thread should just be put onto the wiki, and be done with it... It's too useful a reference not to be.

[ILikePie]

Toady mentioned he uses A* somewhere. I think it was here.

[Shrugging Khan]

Oy Liker of Pies, that link is rather...brief :/

[ILikePie]

What? I have no idea what you're talking about, nope, not at all.

[SeveQ]

http://www.bay12forums.com/smf/index.php?topic=56041.0

No need to thank me. Or that OP. Its already done, after all...ehm. Whatever.

That's quite interesting. Needless or not, thanks. So, since I haven't read the whole thread, yet, I suppose it has already been used to suggest ways of optimization to Toady?

[Shrugging Khan]

I don't think toady will change something so fundamental anytime soon.

[SeveQ]

Well, I don't play DF since its first hour, but I suppose performance has always been an issue. If Toady knows what DF really needs and if he's not too much into new features (like I am, unfortunately, when it comes to software development), he should concentrate on pathfinding and, to mention that again, multi-core support. The latter is predestined for pathfinding.

Anyway! It's pointless to talk about what Toady should or should not do. It's his decision after all... it's late here. I'll go to bed now. Good night, folks!

[Huin]

Let's not forget that DF slowing down when the pathfinder is working harder to support more dwarves doesn't imply that the pathfinder is doing a bad job - it's just got more work to do.

No doubt it could be optimised some more, but let's not forget that pathfinding is an inherently expensive operation, and Toady's implementation has to deal with a difficult environment, and does it (I think) very well considering.

[Ratbert_CP]

Let's not forget that DF slowing down when the pathfinder is working harder to support more dwarves doesn't imply that the pathfinder is doing a bad job - it's just got more work to do.

No doubt it could be optimised some more, but let's not forget that pathfinding is an inherently expensive operation, and Toady's implementation has to deal with a difficult environment drunken, psychotic dwarven miners and does it (I think) very well considering.

Fixed...

[Shrugging Khan]

Problem is that the target-selection AND pathfinding are a little wonky, as far as I'm concerned. See that other thread, where masons travel across half the map to get some stone when there's exactly the same stones lying right in front of their workshops. And the pathfinding is refreshed far too frequently - it ought to reduce its frequency when FPS go down, not keep it constant when it slows the game to a crawl.