Print

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

[Dienes]

It depends on the estimates the programmer is using for distances, I wouldn't say that the DF pathfinding is bad, it can just have a lot of little tricks done to it to decrease the amount of cpu the pathfinder uses, such as only recalculating when you need too and so on. Most modern games use the A* with a whole buch of tricks to get them to run smoothly and quickly.

The fact a dwarf will take a much longer route if a doorway is occupied for a moment is not only absurd but it suggests dwarves repath every time anything gets in their projected path. So if a dwarf is trying to walk across a busy hallway he will recalculate his path every time another dwarf walks through the intersection. That could be dozens of times before he gets anywhere near the intersection. It gets even worse if there is heavy traffic north/south and east/west, several dozen dwarves could have to recalculate each time someone steps into the intersection.

[Putnam]

It depends on the estimates the programmer is using for distances, I wouldn't say that the DF pathfinding is bad, it can just have a lot of little tricks done to it to decrease the amount of cpu the pathfinder uses, such as only recalculating when you need too and so on. Most modern games use the A* with a whole buch of tricks to get them to run smoothly and quickly.

The fact a dwarf will take a much longer route if a doorway is occupied for a moment is not only absurd but it suggests dwarves repath every time anything gets in their projected path. So if a dwarf is trying to walk across a busy hallway he will recalculate his path every time another dwarf walks through the intersection. That could be dozens of times before he gets anywhere near the intersection. It gets even worse if there is heavy traffic north/south and east/west, several dozen dwarves could have to recalculate each time someone steps into the intersection.

Which means that the amount of operations required for pathfinding is quadratic?

[Beeskee]

There's a whole ton of bugs on the bug tracker, it's gotten to the point where it's not fun for me to play any more, knowing that I'll just have to deal with the same issues over and over.

[ColdSpiral]

Plus a lot of things that we've probably stopped looking at as bugs or even oversights - like having no straightforward way to muddy/irrigate a surface. If I want to pour water onto the floor, I shouldn't have to dig a hole through the roof.

[peskyninja]

or waste one year of your life creating a bucket brigade.

[Beeskee]

There's some major overall item-related bug that causes multiple problems: Food getting left on the floor to rot, clothing not being worn or piling up on floors/chests while dwarfs run around naked, pets not always getting properly buried despite tons of coffins. I submitted saves to the bug report threads for all these issues. The inability to dump owned items only makes it worse.

Then there's military issues. It got so frustrating that when I do play, I play with invaders disabled. The inability to assign a civilian outfit adds to that. Even if I have enough leather armor to build a tower to the moon, dwarfs can't wear it unless I draft everyone which would make the military screen impossible to use. Inability to custom name squads only makes that worse.

It makes me sad because DF is one of my favorite games. I just can't bear to play it any more, knowing I'll see the same bugs that I reported ages ago.

The bug tracker feels like decoration now. Does it even get looked at by anyone other than the moderators marking things as duplicates or asking for saves?

[Dienes]

Which means that the amount of operations required for pathfinding is quadratic?

Well if its A* it should be O(N logN) each time it needs to recalculate. If each creature only recalculates when it needs to move and the path it had planned on is blocked it would have at most N recalculations which should be O(N^2 logN). But we know demons will recalculate every tick if they can't reach any buildings; I would hope this is only because they have no current path but only Toady know. So maybe a dwarf will recalculate each tick if its planned path is blocked which in a worst case would give T * N logN where T is the number of ticks it takes to reach the destination. That's still o(N^2 logN) but with bigger constants.

[IronValley]

Which means that the amount of operations required for pathfinding is quadratic?

Well if its A* it should be O(N logN) each time it needs to recalculate. If each creature only recalculates when it needs to move and the path it had planned on is blocked it would have at most N recalculations which should be O(N^2 logN). But we know demons will recalculate every tick if they can't reach any buildings; I would hope this is only because they have no current path but only Toady know. So maybe a dwarf will recalculate each tick if its planned path is blocked which in a worst case would give T * N logN where T is the number of ticks it takes to reach the destination. That's still o(N^2 logN) but with bigger constants.

I guess we could develop some sort of estimate.... Use a system of pressure pads and bridges/locked doors, making access to a room impossible, while leaving a bunch of dump designated items in said room.... Do the test with increasing number of dwarves, and watch how the FPS behaves....

This would ofcourse require an embark designed to perform just this task, with no other tasks/calculations going on...

[Makbeth]

The bug tracker feels like decoration now. Does it even get looked at by anyone other than the moderators marking things as duplicates or asking for saves?

I know how you feel.  It seems to me that Toady gets bored with old stuff very quickly and moves on to new stuff because it's more exciting for him.  I fully expect that when he gets all the features in and it's time to go back through and make them actually work, he'll lose interest in the project and start designing a new game.  Hopefully when he does that he will make it open source so that the modding community can do what it does best: make the game playable.

I wouldn't expect any of the longstanding issues to get fixed.  Most likely there will simply be a parade of new features that almost work.

[Rafal99]

The bug tracker feels like decoration now. Does it even get looked at by anyone other than the moderators marking things as duplicates or asking for saves?

I know how you feel.  It seems to me that Toady gets bored with old stuff very quickly and moves on to new stuff because it's more exciting for him.

It is not surprising new stuff is more exciting, and that it is best to concentrate on one area at once, but Toady eventually revisits old stuff and we can expect some annoying stuff to be fixed in the future.
Toady seems to make either a feature release or a bugfix release, but doesn't mix the two, except small exceptions.
We had several bugfix releases before the current release started being worked on. These releases fixed TONS of bugs, just look at the bugtracker - about 300 issues fixed in these releases, most of them being unique bugs. And these weren't only the new bugs, a lot of old bugs from version 40d and before were fixed too. I am sure we will get a few bugfix releases too a after the coming version, because new bugs will appear for sure, and I bet some old bugs will get looked at too.

Also please do not speak about unplayability. The current version of DF in very playable compared to the some of the old ones. Yeah there are some annoying things I would rather see fixed but these are to be expected in a game that complex. There were worse bugs in the past and there will be another ones in the future after the current ones get fixed. Learn to live with it. DF needs patience, it always had and it always will. 

[Xen0n]

The bug tracker feels like decoration now. Does it even get looked at by anyone other than the moderators marking things as duplicates or asking for saves?

I know how you feel.  It seems to me that Toady gets bored with old stuff very quickly and moves on to new stuff because it's more exciting for him.

It is not surprising new stuff is more exciting, and that it is best to concentrate on one area at once, but Toady eventually revisits old stuff and we can expect some annoying stuff to be fixed in the future.
Toady seems to make either a feature release or a bugfix release, but doesn't mix the two, except small exceptions.
We had several bugfix releases before the current release started being worked on. These releases fixed TONS of bugs, just look at the bugtracker - about 300 issues fixed in these releases, most of them being unique bugs. And these weren't only the new bugs, a lot of old bugs from version 40d and before were fixed too. I am sure we will get a few bugfix releases too a after the coming version, because new bugs will appear for sure, and I bet some old bugs will get looked at too.

Also please do not speak about unplayability. The current version of DF in very playable compared to the some of the old ones. Yeah there are some annoying things I would rather see fixed but these are to be expected in a game that complex. There were worse bugs in the past and there will be another ones in the future after the current ones get fixed. Learn to live with it. DF needs patience, it always had and it always will. 

Thank you.

Remember:  We're not actually a paying userbase, or even a fanbase.  We're alpha-testers.   

[Dienes]

I know how you feel.  It seems to me that Toady gets bored with old stuff very quickly and moves on to new stuff because it's more exciting for him.

I don't think its as bad as you make it sound but yeah its always more fun to make something new and exciting than maintain something that is old hat.

I wish Toady would take on some interns or something who would just focus on fixing bugs and optimizing code. I know there are a lot of very capable programers that would be happy to contribute so they would have real world experience for their resume.

Even better would be if he did some sort of community code review and contribution, even if it wasn't GPL style open source. There are licenses that allow others to access his code without him giving away ownership or control, and he could make it a requirement that any contributors give him full rights over any submitted changes.

Pretty much anything that let Toady focus on interesting development stuff while still having bugs and other issues resolved would be great.

I guess we could develop some sort of estimate.... Use a system of pressure pads and bridges/locked doors, making access to a room impossible, while leaving a bunch of dump designated items in said room.... Do the test with increasing number of dwarves, and watch how the FPS behaves....

I'm not sure how we would be able to actually test if recalculating is done every tick or only when a dwarf is about to move. It would require being able to reliably have the path be interrupted every tick for many dwarves to have a noticeable impact on FPS.  Considering how hard it would be to setup its probably easier to take a debugger to the code and step through it as a path is blocked a few times. Sadly that's beyond my debugging abilities.

[IronValley]

I guess we could develop some sort of estimate.... Use a system of pressure pads and bridges/locked doors, making access to a room impossible, while leaving a bunch of dump designated items in said room.... Do the test with increasing number of dwarves, and watch how the FPS behaves....

I'm not sure how we would be able to actually test if recalculating is done every tick or only when a dwarf is about to move. It would require being able to reliably have the path be interrupted every tick for many dwarves to have a noticeable impact on FPS.  Considering how hard it would be to setup its probably easier to take a debugger to the code and step through it as a path is blocked a few times. Sadly that's beyond my debugging abilities.
[/quote]

I was just thinking about the mathematical part of it, and if the estimate of o(N^2*log(N)) was correct....

[Tharwen]

I think the problem comes from the fact that creatures and solid objects are treated as the same when choosing a path. If the pathfinder just assumed that a creature would move and kept the path the same anyway, it would solve a lot of problems. If the creature isn't moving already, it could be made to wander one tile away to get rid of it.

[HungryHobo]

so... does it recheck each and every tile in the creatures entire path every step or every few steps?

I notice dwarves sometimes keep walking for 5 to 10 steps after a path has been blocked so probably not every step.

I'd probably accept slightly more realistic pathing in favor of better fps.

Have the dwarf pick his path and then have him insist on trying to follow it.
have him only re-path if one of the tiles within 5-10 steps is blocked rather than checking every tile he's going to walk across every few steps.