| 1 |
The first reason is that the costs are invalidated rapidly once the game actually starts. Buildings, blocking features, features added by featureplacer, etc all invalidate the cached costs since those only account for map terrain.
|
1 |
The first reason is that the costs are invalidated rapidly once the game actually starts. Buildings, blocking features, features added by featureplacer, etc all invalidate the cached costs since those only account for map terrain.
|
| 2 |
\n
|
2 |
\n
|
| 3 |
The second reason is that the cost calculation is really only something like [quote]10 * (slope/maxSlope)[/quote]
|
3 |
The second reason is that the cost calculation is really only something like [quote]10 * (slope/maxSlope)[/quote]
|
| 4 |
\n
|
4 |
\n
|
| 5 |
which is extremely trivial to calculate. Accessing the slopemap or a cached cost array on the other hand typically costs about 200 cycles because the array access is essentially random and not amenable to hardware prefetching. Accessing the slopemap plus a map representing crush resistance of features and such is still 200 cycles since the separate accesses can be performed out-of-order, except that it takes less memory than storing that plus a bunch of cached cost arrays (that will be shortly invalid anyway).
|
5 |
which is extremely trivial to calculate. Accessing the slopemap or a cached cost array on the other hand typically costs about 200 cycles because the array access is essentially random and not amenable to hardware prefetching. Accessing the slopemap plus a map representing crush resistance of features and such is still 200 cycles since the separate accesses can be performed out-of-order, except that it takes less memory than storing that plus a bunch of cached cost arrays (that will be shortly invalid anyway).
|
| 6 |
\n
|
6 |
\n
|
| 7 |
There's also a third reason why cached costs are stupid, which is that it's only caching based on movedefs when pathing is also affected by crush strength (which in turn mainly affects features which are not cacheable). Even if you could cache for both crush strength and move defs the memory cost would become untenable and defeat the purpose.
|
7 |
There's also a third reason why cached costs are stupid, which is that it's only caching based on movedefs when pathing is also affected by crush strength (which in turn mainly affects features which are not cacheable). Even if you could cache for both crush strength and move defs the memory cost would become untenable and defeat the purpose.
|
| 8 |
\n
|
8 |
\n
|
| 9 |
It's technically possible to cache entire paths from commonly-used points on a map, but that also assumes that the map is static and that it's actually possible to choose sensible points to cache paths to and from, neither of which applies to spring. If spring sorted units that needed pathing calculations by unit type it would technically be possible to cache path costs on a per-unit-type basis, for one frame only, and then erase it when a new unit type is encountered, but that's all the caching that really makes any sense.
|
9 |
It's technically possible to cache entire paths from commonly-used points on a map, but that also assumes that the map is static and that it's actually possible to choose sensible points to cache paths to and from, neither of which applies to spring. If spring sorted units that needed pathing calculations by unit type it would technically be possible to cache path costs on a per-unit-type basis, for one frame only, and then erase it when a new unit type is encountered, but that's all the caching that really makes any sense.
|
| 10 |
\n
|
10 |
\n
|
| 11 |
I guess I should mention that it's also stupid to use a coarser grid for long-distance pathing, since that can lead to incorrect paths, as in this case, or no path at all even if a valid path exists (which btw happens on stronghold). I've read some things that hint that it might be possible to speed up the calculation of similar paths by calculating them together, but I haven't actually read any papers explaining how that works so I don't know if that's even true or not, but if it is then that would be a more sensible way to save cycles.
|
11 |
I guess I should mention that it's also stupid to use a coarser grid for long-distance pathing, since that can lead to incorrect paths, as in this case, or no path at all even if a valid path exists (which btw happens on stronghold). I've read some things that hint that it might be possible to speed up the calculation of similar paths by calculating them together, but I haven't actually read any papers explaining how that works so I don't know if that's even true or not, but if it is then that would be a more sensible way to save cycles.
|
| 12 |
\n
|
12 |
\n
|
| 13 |
EDIT: Something relevant to this bug though, is that the lower-res slopemaps it's using might be bicubic interpolated rather than taking the max slope value in a given cell. This has similar tradeoffs though; bicubic gives incorrect paths, max value may not find valid paths. Lower-res slopemaps would actually be more appropriate for pathing for large units anyway, rather than for long-distance pathing.
|
13 |
EDIT: Something relevant to this bug though, is that the lower-res slopemaps it's using might be bicubic interpolated rather than taking the max slope value in a given cell. This has similar tradeoffs though; bicubic gives incorrect paths, max value may not find valid paths. Lower-res slopemaps would actually be more appropriate for pathing for large units anyway, rather than for long-distance pathing.
|
|
|
14 |
\n
|
|
|
15 |
EDIT: No, there are no good ways of speeding up pathing for similar paths. Plain-old A* is still king.
|
B396051 2 on Bandit_Plains_v1 (Multiplayer)