MildaIV wrote:

Patch

Attachments

• DistanceAxeDiag.patch (2.94 KiB)

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13144

fonsinchen wrote:

The comment is somewhat hard to understand. Maybe write "Gets the distance that a vehicle only moving along axes or diagonals will cover between the two given tiles". The name is probably not really english, either. My bad. Maybe make that "DistanceAxisDiag" (or ask someone who is actually a native speaker :/). Then you'll need to explain each change from DistanceManhattan to DistanceAxisDiag separately. For the link graph changes that's pretty easy to do by just providing one of your saves. You'll have a harder time with the order_cmd.cpp change, I think. Maybe leave that out for now.

Then there is the problem with the stopover penalty. 577/408 > sqrt(2) so if the calculations were exact we wouldn't have a problem. However, for each leg of a route it can lose up to 1 due to rounding. If you just increase the stopover penalty to 2 that should fix it. I don't think it would create any other problems.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13145

MildaIV wrote:

Yeah my english is terible, sry about that :(
I was thinking about rounding problem too. Increasing stopover penalty is good solution. Another solution is to simplify sqrt(2) to 1.5. Its not exact, but still shorten routes with diagonals movements, so they will be preferred. If we multiple distance by two to get rid of rounding we get distance 2 for one move by axis and 3 for move by diagonal. Resulting computation is than much simpler:
if (dx > dy)
return 2dx+dy;
else
return 2dy+dx;

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13146

fonsinchen wrote:

Using 1.5 won't actually help with the rounding, will it? The result will still be integer-truncated and you'll still need a higher stopover penalty to offset that. The simplification is of course nice, but you shouldn't just double all distances. Maybe divide the smaller one by 2 instead of multiplying the bigger one.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13147

MildaIV wrote:

Doubling distances introduce new problems, as its not comparable with other OTTD metrics :( Dividing smaller one keeps simplification of calculation, but you have rounding problem back.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13148

frosch wrote:

About the order_cmd change:
DistanceSquare does not return a distance, but the square of a distance. Comparing a distance with a squared distance makes no sense, you would also have to change AircraftCache::cached_max_range_sqr to not contain a squared distance (resp. remove it since there is already a non-squared value).

Anyway, changing that would certainly be a separate patch. But unfortunately it also breaks savegames, since the DiagAxe distance is always bigger than the euclidian distance, and as such planes would no longer be able to reach destinations which they could before. So, I wonder whether this is worth changing at all.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13149

frosch wrote:

Wrt. the sqrt(2) thingie. Would it make sense to use the same approximation as in Vehicle::GetAdvanceSpeed resp. GetAdvanceDistance? That is sqrt(2) = 4/3

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13150

MildaIV wrote:

Intention to use sqrt(2) = 3/2 was to eliminate rounding problem by returning double distance. If we avoided that, I dont see much benefit of not using more precise aproximation. Maybe reducing overflow problem for 1Mx1M maps :)
This algorhitm should be optionable somewhere in advanced settings, so it will also keep backward compatibility for older saves.
order_cmd - Ah my bad.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13151

fonsinchen wrote:

Actually, as DistanceSquare is not comparable to other distances either, having a "DistanceAxisDiagDouble" or similar only for link graph uses wouldn't be a huge problem. However, just increasing the stopover penalty to 2 wouldn't be a big thing, either. If you're wondering: That's added in mcf.cpp:268 . It is important that the approximation for sqrt(2) is greater than sqrt(2) as otherwise you may get accumulated rounding and approximation errors greater than 1.

With respect to savegame compatibility: The distances are saved and loaded. Having mixed distances in the link graph for a while would distort the calculation results a bit but wouldn't have really grave consequences. I think we can ignore that.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13153

MildaIV wrote:

So you think that its better to have simplified aproximation 3/2 or more precise one and
biger stopover penalty? I personaly tends to simplifed one as its more in old TTD style, but more precise one can in some rare cases on longer routes get better result.

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13155

fonsinchen wrote:

I'd go for 3/2, without doubling, and a stopover penalty of 2. Like that we can also use the new distance metric as drop in for DistanceManhattan in other places if necessary. And you can shorten the if/else clause above to "return dx > dy ? dx + dy / 2 : dy + dx / 2;"

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13156

MildaIV wrote:

Hmmm the proposed DistanceAxisDiagDouble is allready in OTTD - under name DistanceMaxPlusManhattan and is used only in TrackPathFinder::best_bird_dist. I think it means that we are going in good direction :)

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13157

MildaIV wrote:

I have created patch using allready existing code for discused metric.

Attachments

• linkgraph.patch (0.90 KiB)

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941#comment13159

fonsinchen closed the ticket.

Reason for closing: Fixed

in r26411

This comment was imported from FlySpray: https://bugs.openttd.org/task/5941