Print

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

[Jay]

If the pathfinding was improved, think of what people could do. Water elementals actually made of water and stuff

Umm, what?
That has absolutely nothing to do with the pathfinding whatsoever.
A water elemental still moves in exactly the same way as a fire elemental or an iron golem, obviously this extends to bronze colossi which are already in the game.
That's more of a problem with the actual game engine not being set up for water elementals, a fact that is changing next release.

All improving the pathfinding allows is for more creatures without lag.
That's it.
Doesn't change the types of creatures that we can path for, being that we can already pathfind for everything, basically.

[Apegrape]

It frees up a lot of power, therefore you can make more complex thingies.
I'm stupid. Sorry.

[Fieari]

Better statement: if pathfinding were improved, Toady could implement realtime lighting and LOS for all creatures, in dwarf mode not just adventure mode.

[Chandrasekhar]

When I saw the thread title, I figured it would be like a penis pill advertisement or something.  "Is your FPS small and impotent, not nearly as big as it was in your fortress's youth?  My FPS got over two times bigger by trying High Traffic!  Now my wife just can't leave my fortress alone!  Thanks, Savok!"

[PTTG??]

You don't need to go all over designating, either. Just go into init.txt and find the entry like this:
[PATH_COST:1:2:5:25]
And maybe replace them with this:
[PATH_COST:1:1:2:10]

I'm preeeeety sure that this will have the same effect.

[Faces of Mu]

Don't those figures say you'd need to go around designating all the low traffic areas instead of high? I'd rather be saying "go here" rather than "don't go here". More area in the latter than the former.

[Calculus]

Reducing the tile costs for all traffic areas in the init file should not speed up the game.

[Savok]

You're right.

But it did.

I do wonder why.

[Sinergistic]

Reducing the tile costs for all traffic areas in the init file should not speed up the game.

This does make sense though, since if I understand how the pathfinding algorithm works, if you designate all the traffic areas as high, the pathfinding alforithm will move twice as fast in these areas, and reach the destination much sooner.

[dreiche2]

I'm also of the opinion that designating *everything* higher shouldn't make a difference (equivalently, changing the init costs). It's not like the algorithm literally goes slower or faster in these tiles, the numbers just tell it how to weight tiles against each other in the calculations.

If it really does make a difference, then it might be a bug.

Now, as for only designating the whole fortress high traffic, not the whole map, I just realized this might actually make a difference *if* the pathfinding algorithm does take into account paths of iteratively increased length depending on their current cost and does not fully explore all paths. 

Basically, either it compares two paths from start two finish, calculates the total cost, and picks the cheaper one.

Or, it calculates the cost one tile at a time. Having found the cheap connection, it does not further explore any other paths that have at least the same cost. Then, in this case, having higher cost tiles outside your fortress would effectively stop the pathfinding looking for paths outside the fortress earlier when compared to paths within the fortress. Which would make sense as most pathing is within the fortress anyway.

Would be nice to hear from the almighty Toad about this...

[Sowelu]

Reducing path costs across the board in the init will make your game go faster!

THAT!  IS!  NOT!  HOW!  PATHFINDING!  WORKS!  AT!  ALL!

Spoiler: anger... (click to show/hide)

Let me make this even clearer.  In theory, in a well-implemented algorithm, there is literally NO DIFFERENCE between "every tile costs 1" and "every tile costs 2".  I am VERY, VERY sure that your experimental results are wrong.  Try bumping each cost up to 5 and see if it slows down.

If you CAN experimentally prove this, then there is a very serious (AND VERY SIMPLE) flaw in the pathfinding algorithm that can probably be solved with a cursory glance.  Hey, everyone makes mistakes, my pathfinding code has been wrong tons of times.  If such a flaw existed, then yes, fixing it would instantly speed things up across the board.  But I have a LOT more faith in DF's code than that.

So please.  Get right on that.  If you can control for all other variables and reproducably PROVE that lowering path costs globally causes ANY CHANGES, then do so, and everyone will benefit an enormous amount when that bug gets fixed really quick.

AND IF YOU CAN'T THEN SHUT UP because you are spreading MISINFORMATION AND LIES and CONFUSING PEOPLE with OBVIOUSLY, BLATANTLY WRONG INFORMATION.

Yeah, I'm pissed off.  You're really confusing people here, and making newbies suspicious.  But I'm serious, either prove what you're saying (in which case it's a bug that has an easy fix and a huge benefit) or shut the hell up.

I'm not aiming this at the OP, because yeah, even just minor CORRECT use of the path cost tool can have a huge help, and the OP did use the path cost tool correctly.  Use the path cost tool right, and it'll help you too!  But everyone who says that changing ALL costs across the board will do anything, is either on to something huge...or they are wrong.  Guess what my money's on.  Stop it, people.  Superstition is lame.
/flame

[Ignoro]

Using 100 cats (and nothing else) as embark equipment on a flat desert map, then designating a meeting area in the far corner with no wild animals in their path. This is on an original Athlon 32 bit with 400 Mhz (DDR1?) RAM.

#:#:#:#
Bolded # is designated everywhere. These numbers are eyeballed within 5 FPS of the actual.

1:2:10:25
3x3 Avg 75 FPS
6x6 Avg 55 FPS
9x9 Avg 30 FPS

1:2:10:25
3x3 Avg 80 FPS
6x6 Avg 60 FPS
9x9 Avg 35 FPS

1:1:10:25
3x3 Avg 90 FPS
6x6 Avg 65 FPS
9x9 Avg 40 FPS

The breakdown of speeds over larger map sizes seems fairly regular, so you can sort of project a guess at what it would be for the following tests on 6x6 and 9x9 (About 75% and 40% respectively).

10:10:10:10
3x3 Avg 90 FPS

1:2:1000:25000
3x3 Avg 100 FPS

1:99:999:9999
3x3 Avg 125 FPS

It appears they are relative to each other, as it should be. Bumping up the far end of the scale so far renders those heavy traffic designations near useless, so there is a trade off.
Those tests were horribly unscientific. I hope someone else will do a more official test.

[Eagleon]

Reducing path costs across the board in the init will make your game go faster!

THAT!  IS!  NOT!  HOW!  PATHFINDING!  WORKS!  AT!  ALL!

Spoiler: anger... (click to show/hide)

Let me make this even clearer.  In theory, in a well-implemented algorithm, there is literally NO DIFFERENCE between "every tile costs 1" and "every tile costs 2".  I am VERY, VERY sure that your experimental results are wrong.  Try bumping each cost up to 5 and see if it slows down.

If you CAN experimentally prove this, then there is a very serious (AND VERY SIMPLE) flaw in the pathfinding algorithm that can probably be solved with a cursory glance.  Hey, everyone makes mistakes, my pathfinding code has been wrong tons of times.  If such a flaw existed, then yes, fixing it would instantly speed things up across the board.  But I have a LOT more faith in DF's code than that.

So please.  Get right on that.  If you can control for all other variables and reproducably PROVE that lowering path costs globally causes ANY CHANGES, then do so, and everyone will benefit an enormous amount when that bug gets fixed really quick.

AND IF YOU CAN'T THEN SHUT UP because you are spreading MISINFORMATION AND LIES and CONFUSING PEOPLE with OBVIOUSLY, BLATANTLY WRONG INFORMATION.

Yeah, I'm pissed off.  You're really confusing people here, and making newbies suspicious.  But I'm serious, either prove what you're saying (in which case it's a bug that has an easy fix and a huge benefit) or shut the hell up.

I'm not aiming this at the OP, because yeah, even just minor CORRECT use of the path cost tool can have a huge help, and the OP did use the path cost tool correctly.  Use the path cost tool right, and it'll help you too!  But everyone who says that changing ALL costs across the board will do anything, is either on to something huge...or they are wrong.  Guess what my money's on.  Stop it, people.  Superstition is lame.
/flame

Er, it's not like people are being hurt by this. If it's true, and there is a bug that's eating cycles in the pathing loop due to the additions made by this feature (which I wouldn't be surprised by, as the path cost designations are a relatively recent addition, and fairly hidden for most players i.e, there hasn't been nearly as much testing), then it helps people to know this until it's fixed in a future release. It also alerts Toady to a possible issue. As far as I've seen, discussion has been pretty tame. No wailing and gnashing of teeth from newbies losing faith in Toady's great coding prowess, no religions being started (The Way of the Blanket Path?), and no one dying because they thought it'd cure their cancer.

TLDR: Calm down and chill out.

[Sowelu]

*foams at the mouth*

I can't argue with experimental evidence!

I have to question some of the results though.

On a 3x3 with 1:2:10:25, you got 75 fps.
On a 3x3 with 10:10:10:10, you got 90 fps.  I don't see any explanation for this behavior, and the difference between these two (15 fps) IS statistically very significant.

Also, I'm very confused why
3x3 1:2:10:25 (80 FPS)
3x3 1:99:999:9999 (125 FPS)
have any difference at all.  They both use a path cost of '1' designated everywhere, and I don't see any explanation in the current theory (high numbers = slower) for why this would happen.

The current theory says that if everything is designated with path cost 2, it will be slower than everything designated with path cost 1.  The current theory says nothing at all about assigning any other meaning to high/medium/low/restricted, and says nothing about the costs for things that aren't used.

Until we get a theory that does include those, I think I have to say our biggest margin of error in that experiment is 56.25% (two experiments that shouldn't have any difference), while the best 'signal' (a change from 2 to 1 that showed an improvement) is just 20%.

Also it doesn't say why increasing the cost of 'normal' from 2 to 10 gave a speedup of 15 FPS.

Ignoro, I do like your methodologies a lot, they are just giving weird answers!  Would you mind running multiple passes on each test?  Your methodology seems pretty sound but we need more data.

Control for all variables except for the cost of 'normal' designated everywhere...or, if you prefer, all variables except for 'high' vs 'normal' zoning.  Try running five with cost 1 and five with cost 2...but interlace them, so if your CPU is chugging harder at the end, it doesn't bias one scenario more than the other.

You will be my new best friend.  <3  And if we get statistically significant results we'll actually have a good reason to go to Toady about it.

EDIT, Eagleon responded while I was writing:  Eh, there is harm caused by people believing there's a bug when there isn't one.  It means more player effort for no reason, and it means development time spend looking for a bug that might not exist.  However, if we can prove the bug exists, then that is a great thing.  We just have to be diligent, and give good evidence!  Besides, it's a personal curiosity, and I want to know for sure now...The plural of 'anecdote' may not be 'data', but the plural of 'experiment' is!

[AncientEnemy]

it's odd, i seem to get lower FPS when i designate -any- traffic areas whatsoever. on my current fortress i've been experimenting with it.

with no traffic designations whatsoever: 60-65 fps
with high traffic in the main throughways: 50-55 fps
with restricted traffic in areas where my dorfs never go (magma pit, river): 45-50 fps

wat?