posted 01-05-14 15:21 ET (US)
[This message has been edited by Brugle (edited 02-01-2014 @ 03:15 AM).]
Direction | NW-SE Axis | NE-SW Axis |
NE | Same | Walk origin is more NE |
E | Walk origin is more SE | Walk origin is more NE |
SE | Walk origin is more SE | Same |
S | Walk origin is more SE | Walk origin is more SW |
SW | Same | Walk origin is more SW |
W | Walk origin is more NW | Walk origin is more SW |
NW | Walk origin is more NW | Same |
N | Walk origin is more NW | Walk origin is more NE |
4 | 3 | 4 | 5 | 6 | 7 | . | . | . | |
3 | 2 | 3 | 4 | 5 | . | 8 | . | . | |
. | 1 | 2 | 3 | 4 | 6 | 7 | 8 | . | |
1 | 4 | 5 | 6 | 7 | 8 |
. | . | 6 | 5 | 4 | . |
. | 8 | . | 3 | . | |
. | . | 2 | . | ||
. | . | . | . | . | |
. | . | . | . | . | . |
. | . | 3 | 5 | . | |
. | 1 | . | . | ||
. | . | 8 | . | ||
. | . | . | . | . | |
. | . | . | . | . | . |
[This message has been edited by Brugle (edited 04-22-2018 @ 02:51 PM).]
a destination walker who will generally not cut corners, such as a Pharaoh random walker returning to its building, will cut corners if the path that does not cut corners is longer than 499 tiles and the path that does cut corners is shorter than 500 tiles.That's intriguing (and unexpected). The 499-tile limit was one of the few that wasn't increased in Pharaoh (the number of paths was increased from 599 to 999, but not the maximum length). Perhaps the designers felt that preventing corner-cutting effectively reduced the maximum reach of a Pharaoh walker compared to C3 and sought to alleviate that.
Tie-breaking rule. The algorithm selects a
destination-mode path for a roaming walker by
starting at the walk terminus and looking backwards
along the path towards the walk origin. When two
alternative paths of equal length (shorter than all
others) can be traced from the walk terminus to the
walk origin, the algorithm chooses between the two
paths based on the directions they take from the
point at which they diverge, according to the
following order of preference: NE >SE > SW >
NW.
I'm not sure what you mean by "anomalies". If you mean that destination walkers do not always find the shortest path, that's been obvious to me since I first starting looking at the paths that immigrants or caravans used. (I remember, long ago, when someone stated that destination walkers take the shortest path, replying that the caravans leaving my Rostja do not.)Quoted from Trium:
this one so frequently fails to find the optimal route I'm surprised we've not seen a lot more reported anomalies
Yes, that was deliberate. I had a sentence mentioning that it was not the shortest path in my first draft, but removed it.Quoted from Trium:
I also note that even your very simple first example, which I've checked in-game, chooses a route 1 tile longer than the optimal.
I thought of mentioning that. I also thought of mentioning your report of the ordering of directions from NE around to N. But I decided not to, since I worked out the algorithm for cutting corners before I realized that it also applied to not cutting corners (and then checked Ambulomancy to make sure that it agreed), and I determined the ordering of directions with many tests. I hope that you and StephAmon don't feel slighted.Quoted from Trium:
your algorithm traces the path backwards after the destination is found (as does A*) reminds me of StephAmon's comments (Ambulomancy, 2nd edition)
[This message has been edited by Brugle (edited 01-06-2014 @ 07:56 PM).]
We'll see.Quoted from Brugle:
Since the violations of the algorithm are quite rare, and only seem to occur in contrived examples, I doubt that I'll investigate them any further.
[This message has been edited by Trium (edited 01-31-2014 @ 04:00 PM).]
You're right.Quoted from Trium:
We'll see.Quoted from Brugle:
Since the violations of the algorithm are quite rare, and only seem to occur in contrived examples, I doubt that I'll investigate them any further.
Very good.Quoted from Trium:
I suspect that the game is employing a heuristic which attempts to prioritize the direction which seems, based on coordinates, to lead towards the walk origin while back-tracing
In Pharaoh, many walkers usually don't cut corners, which can make a significant difference to destination walker paths. Other than that, it uses the same algorithm.Quoted from Trium:
what is going on in Pharaoh, but it clearly works differently
StephAmon's tie-breaking rule is not always correct. For example, this architect takes the upper path around the statue (instead of StephAmon's predicted lower path), since the walk origin is NW of the plaza (with north up-left):Quoted from Trium:
The fact that your algorithm traces the path backwards after the destination is found (as does A*) reminds me of StephAmon's comments (Ambulomancy, 2nd edition):Tie-breaking rule. The algorithm selects a
destination-mode path for a roaming walker by
starting at the walk terminus and looking backwards
along the path towards the walk origin. When two
alternative paths of equal length (shorter than all
others) can be traced from the walk terminus to the
walk origin, the algorithm chooses between the two
paths based on the directions they take from the
point at which they diverge, according to the
following order of preference: NE >SE > SW >
NW.
[This message has been edited by Brugle (edited 02-01-2014 @ 02:37 PM).]
Copyright © 1997–2024 HeavenGames LLC. All rights reserved.
v2.5.0