Print

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

[telarin]

Different kinds of terrain should modify movement speed of creatures somewhat. For instance roads and smoothed floors should have a slightly higher movement speed then rough floors. This is not only realistic, but gives some incentive for smoothing corridors and building roads other than simple aesthetics.

Additionally, entities that normally ignore your traffic designations (such as caravans) should take into consideration the faster movement rates of roads when pathing across the map.

[peskyninja]

With the way time works in DF this change would be very hard to see if you want to stick with realism.

[Neonivek]

Right now we have to wait until attacking and moving are two seperate things.

Otherwise just being on sand is going to make you swing more slowly.

[NW_Kohaku]

I don't feel like digging up the quotes right now, but Toady has talked about how he plans to put in things like "underbrush" which do exactly this.

He said he doesn't want to make a "movement bonus" for specific terrain types, but rather, a penalty for different kinds of rough floors.  (So, for example, a wagon might be sensitive to tangled underbrush in a shrubland or forest, and a road would make good sense then.)

[Gotdamnmiracle]

I wouldn't mind seeing rough floors and types of brush that carry a [UNSURE_FOOTING] token which makes it so they can be walked over normally (not counting penalty) but that when dodging they give a small chance of making the dodger fall over.

It is pretty difficult to be very agile on a rough hewn anything, really. Especially in heavy metal or leather boots.

[dwarfhoplite]

I totally support. Moving on deep snow, for example, is very clumsy.

[King Mir]

I do support the idea, but I should point out that this would hurt pathing FPS, because dwarves would want to path around hard terrain. This would make them path longer routes, which takes longer, and look for speedier alternative paths on smooth ground, even when there aren't any, which also takes longer.

[NW_Kohaku]

I do support the idea, but I should point out that this would hurt pathing FPS, because dwarves would want to path around hard terrain. This would make them path longer routes, which takes longer, and look for speedier alternative paths on smooth ground, even when there aren't any, which also takes longer.

True, however, traffic designations that give tiles a pathfinding weight of greater than 1 already do this, and the default traffic designation weight is 2. 

One of those "reclaim some FPS" tricks is to either set a huge number of "High Traffic" areas in the hallways, and set restricted or the like to bedrooms you don't want pathing into, or else to just set the default pathfinding weight to 1.

[King Mir]

I do support the idea, but I should point out that this would hurt pathing FPS, because dwarves would want to path around hard terrain. This would make them path longer routes, which takes longer, and look for speedier alternative paths on smooth ground, even when there aren't any, which also takes longer.

True, however, traffic designations that give tiles a pathfinding weight of greater than 1 already do this, and the default traffic designation weight is 2. 

One of those "reclaim some FPS" tricks is to either set a huge number of "High Traffic" areas in the hallways, and set restricted or the like to bedrooms you don't want pathing into, or else to just set the default pathfinding weight to 1.

As per the last thread in which we agrued this very point, setting default traffic designations to weight 1 has no effect if all tiles have that weight. Only differences in traffic weight make a difference.

You are correct that traffic designations have the exact same slowdown potential. However, traffic designations are placed by the player and so can be placed smartly. Hopefully a player who bothers with traffic designations is able enough that the designations are a net speedup. Rough terrain, on the other hand, is not placed specifically to provide a speedup and is forced on everyone. The net effect will be a slowdown. How much of a slowdown is an open question.

In particular, I would expect high traffic rough to smooth boundaries to be problematic.

[NW_Kohaku]

As per the last thread in which we agrued this very point, setting default traffic designations to weight 1 has no effect if all tiles have that weight. Only differences in traffic weight make a difference.

But the thing is, just because I stopped arguing the point there didn't mean it was because I agreed with you.

Again, however, only at the lowest possible values the heuristic will expect will preclude "testing" nearby tiles for a lower-weight route.  Yes, as soon as the game recognizes they all have a weight of 2, they will go with the most direct route, but before they do that, they will test every one of the adjacent directions, and will do so on every tile they step upon.  Checking the weights of nearby tiles takes a memory fetch to see what weights they have.

Only a weight of 1 (for this heuristic) will tell the game to simply give up on trying a lower-weight alternative without having to check.

[King Mir]

As per the last thread in which we agrued this very point, setting default traffic designations to weight 1 has no effect if all tiles have that weight. Only differences in traffic weight make a difference.

But the thing is, just because I stopped arguing the point there didn't mean it was because I agreed with you.

Again, however, only at the lowest possible values the heuristic will expect will preclude "testing" nearby tiles for a lower-weight route.  Yes, as soon as the game recognizes they all have a weight of 2, they will go with the most direct route, but before they do that, they will test every one of the adjacent directions, and will do so on every tile they step upon.  Checking the weights of nearby tiles takes a memory fetch to see what weights they have.

Only a weight of 1 (for this heuristic) will tell the game to simply give up on trying a lower-weight alternative without having to check.

That is simply incorrect.

The algorithim will always test all nearby tiles, in order to obtain the weight and if it's passible in the first place. This weight depends on distance as well as traffic designation, and so is not the same for every tile. The distance portion could be computed without querying the tile data, but the passibility and traffic designation cannot, even if it is 1. Algothimically, an impassible tile is identical to a tile with traffic designation infinity. Then the algotithim tries the tile with the lowest weight, and will test the weight of all adjacent tiles to that, expect the ones already tried. It will keep trying the tile with the lowest weight, untill it reaches the goal tile, which should have weight 0. The algorithim internally tracks how it reached each tile, and upon reaching the goal can backtrack to the origin, thus determining the path.

This description of DF pathing is based on Toady's statement that pathing is essentially A*, and my undertanding of the A* algorithim and how it could reasonably be modified.

[NW_Kohaku]

That is simply incorrect.

The algorithim will always test all nearby tiles, in order to obtain the weight and if it's passible in the first place. This weight depends on distance as well as traffic designation, and so is not the same for every tile. The distance portion could be computed without querying the tile data, but the passibility and traffic designation cannot, even if it is 1. Algothimically, an impassible tile is identical to a tile with traffic designation infinity. Then the algotithim tries the tile with the lowest weight, and will test the weight of all adjacent tiles to that, expect the ones already tried. It will keep trying the tile with the lowest weight, untill it reaches the goal tile, which should have weight 0. The algorithim internally tracks how it reached each tile, and upon reaching the goal can backtrack to the origin, thus determining the path.

This description of DF pathing is based on Toady's statement that pathing is essentially A*, and my undertanding of the A* algorithim and how it could reasonably be modified.

I believe you are confused with how the heuristic works. 

Toady uses modified A* with a Manhattan Heuristic that is also modified to work 3d. 

The heuristic guides where A* tries to path to first, but it does not change the weight of the tiles, the weight of the tiles is compared to the heuristic's expectations.  If the heuristic's expected path is at or below the weight it expects in a shortest possible path, it will simply follow that path.  If the weight is higher than what it expects, it will start reading and testing other tiles until it cannot find one that actually saves it distance compared to the heuristic's guess.  Having a lowest-possible weight prevents the game from testing the weights of adjacent tiles.

If you have a straight horizontal walk from point "A" on the west side of the screen, and a point "B" on the east side, then with all weights being 1, the game will push all the tiles around "A" into the "open list", but not actually read anything but the one tile directly east of it, since heading directly east is the heuristic's best guess.  When it hits this east tile, it will push the locations of the three newly adjacent tiles into the "open" list without having to read them at that moment. This will continue until you hit "B".  You functionally have to push three times as many tiles into the open list as you have to actually travel, but do not have to actually fetch the data on weights for more than those tiles you need to walk on.

If you have a uniform weight that is higher than what the heuristic expects, however, then the heuristic will see that the path due east will take longer than the heuristic expected, and so try to read the northeast and southeast tiles' information to see if they are going to be weight 1.  If the weight is higher than that, they may start searching all the other directions, as well.  Each time the game searches these tiles for their weights, all their adjacent tiles get added, as well.  This means that even with a weight of 2, you are adding 5 times as many tiles as you actually need to walk on to the open list, and you are searching 3 times as many tiles for their actual weight information. 

[King Mir]

That is simply incorrect.

The algorithim will always test all nearby tiles, in order to obtain the weight and if it's passible in the first place. This weight depends on distance as well as traffic designation, and so is not the same for every tile. The distance portion could be computed without querying the tile data, but the passibility and traffic designation cannot, even if it is 1. Algothimically, an impassible tile is identical to a tile with traffic designation infinity. Then the algotithim tries the tile with the lowest weight, and will test the weight of all adjacent tiles to that, expect the ones already tried. It will keep trying the tile with the lowest weight, untill it reaches the goal tile, which should have weight 0. The algorithim internally tracks how it reached each tile, and upon reaching the goal can backtrack to the origin, thus determining the path.

This description of DF pathing is based on Toady's statement that pathing is essentially A*, and my undertanding of the A* algorithim and how it could reasonably be modified.

I believe you are confused with how the heuristic works. 

Toady uses modified A* with a Manhattan Heuristic that is also modified to work 3d.

I believe you there.

The heuristic guides where A* tries to path to first, but it does not change the weight of the tiles, the weight of the tiles is compared to the heuristic's expectations.  If the heuristic's expected path is at or below the weight it expects in a shortest possible path, it will simply follow that path.  If the weight is higher than what it expects, it will start reading and testing other tiles until it cannot find one that actually saves it distance compared to the heuristic's guess.  Having a lowest-possible weight prevents the game from testing the weights of adjacent tiles.

If you have a straight horizontal walk from point "A" on the west side of the screen, and a point "B" on the east side, then with all weights being 1, the game will push all the tiles around "A" into the "open list", but not actually read anything but the one tile directly east of it, since heading directly east is the heuristic's best guess.  When it hits this east tile, it will push the locations of the three newly adjacent tiles into the "open" list without having to read them at that moment. This will continue until you hit "B".  You functionally have to push three times as many tiles into the open list as you have to actually travel, but do not have to actually fetch the data on weights for more than those tiles you need to walk on.

If you have a uniform weight that is higher than what the heuristic expects, however, then the heuristic will see that the path due east will take longer than the heuristic expected, and so try to read the northeast and southeast tiles' information to see if they are going to be weight 1.  If the weight is higher than that, they may start searching all the other directions, as well.  Each time the game searches these tiles for their weights, all their adjacent tiles get added, as well.  This means that even with a weight of 2, you are adding 5 times as many tiles as you actually need to walk on to the open list, and you are searching 3 times as many tiles for their actual weight information.

No that's not what happens. Scorring happens after a tile is read, not before. Inpassible tiles are not scorred (or are scored as infinate). As described by the source you linked to, the score is the heuristic plus the weight of the tile, there following the formula F=G+H. Nowhere in the A* algothithim is a threashhold computed. So on a clear unobstructed (and equal traffic designation) path, east to west, A* will always queary each tile along the path AND each tile dirrectly adjacent to that, a total of 17+9*N, tiles, where N is the distance in tiles.

A different algorithm than A* could have a more grid based aproach as you describe, but A* is not a grid traversal algotithim, it is a graph traversal algorithim. It has no notion of traveling east, only a notion of exploring the tile with the lowest weight or "score" (labeled F in the pages you linked to). But to find the weight it has to query the graph.

EDIT:I'm confusing the terms heuristic and score here, but the resultant point is the same. It still has to query the weight each time.

EDIT 2: Fixed the confusion.

[ravaught]

The problem could be somewhat solved by making it a fatigue factor instead of a movement speed factor. Pushing through deep snow or thick underbrush is more taxing physically than walking on a clear paved street. I am not sure exactly what he is using to determine when a dwarf takes a break or lays down to sleep, but I think implementing a fatigue management system would do for starters if tackling the pathing issues is too much. On the plus side, it will only be improved when he finally does get around to improving the pathing to the point where it affects movement speed, because at that point you will be saving your Dwarfs time AND energy.

[knutor]

I got lost in that code talk.  Are you guys saying speed isn't modified by Agility and Backpacks?

What can a player do to increase blip speed?