Determining a destination walker path requires knowing where the walker begins his destination walk (the walk origin), where the destination walk should end (the walk terminus), and what types of tiles the path can use.

All C3 destination walkers cut corners. Many destination walkers will only make paths on road-like tiles: roads, bridges, gatehouses, the non-corner tiles of granaries, the N tile of warehouses, elevation change ramps, gardens, and the parade grounds of forts. (Gardens and parade grounds do not connect roads--ignoring a rare bug, a cart pusher will not deliver a good if he has to go through a garden or fort parade ground, but he will take a garden or parade ground short-cut to the same road.) Other destination walkers make paths on bare ground. Caravans and warehouse cart pushers getting a good will use a road-like path if one exists but will use a ground-like path otherwise. Enemies and wild animals do not make paths through gatehouses.

Pharaoh is more complex. Many destination walkers, who generally do not cut corners, will only make paths on road-like tiles: roads (including under roadblocks, the festival square, and entertainment venues), bridges, gatehouses, mastaba/pyramid construction platforms, and staffed ferry crossings. Other destination walkers cut corners and make paths on ground-like tiles: bare ground (including under the festival square), trees, marsh, and sand dunes. Caravans, storage yard cart pushers getting a good from another storage yard, hunters, reed gatherers, wood cutters, and monument construction workers will use a road-like path if one exists (almost never cutting corners) but will use a ground-like path otherwise (cutting corners). A destination walker who will cross a ferry stops being a destination walker when it arrives at the terminal, so it calculates a new path to its destination when it completes the ferry crossing. Immigrants and emigrants make paths through ferry crossings whether they are staffed or not and remain as destination walkers while crossing the river. Enemies and wild animals do not make paths through gatehouses or ferry crossings. Enemies make paths through gardens if Cleopatra is installed.


Destination Walker Path Algorithm

Part 1. Number the walk origin tile with 0. Repeat this step until the walk terminus is numbered: all unnumbered tiles that the destination walker path might use and that are to the NE or SE or SW or NW of any of the highest numbered tiles are numbered with the highest number plus 1. If a step does not number any tiles then there is no destination walker path, and various things might happen--for example, a random walker trying to return to its building disappears but a caravan that is trying to find a road-like path starts trying to find a ground-like path.

These are the directions used in Part 2, and the indication if the walk origin is that direction from another tile:

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

Part 2. Start at the walk terminus tile. Repeat this step until the walk origin tile is reached: go to the surrounding tile that has the lowest number, checking only the NE and SE and SW and NW tiles if the destination walker will generally not cut corners and if the walk terminus number is less than 500, and if that picks multiple tiles then select the direction of the walk origin (if that tile has the lowest number) otherwise select the first tile found in the table above (with the lowest number). The destination walker path is the reverse of the path just found. If the number of tiles found is greater than 499, the path is too long and the walker disappears.

Note: a destination walker who will use a road-like path if it exists but will use a ground-like path if necessary, such as a caravan, will disappear if the road-like path is longer than 499 tiles (even if the ground-like path is shorter than 500 tiles).

Note: 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.


Examples

An immigrant going from the entry point (the plaza) to the tile next to the house (with north up-left):

The bottom 4 rows of numbering look like this, with the path in bold:

4	3	4	5	6	7	8	.	.	.
3	2	3	4	5	.	7	8	.	.
.	1	2	3	4	5	6	7	8	.
1	0	1	2	3	4	5	6	7	8

In the first choice of Part 2, going from a tile numbered 8 to a tile numbered 7, the tile in the direction of the walk origin (W) is not numbered, so the first tile found with the number 7 (SW) is selected. In the other choices of Part 2, there is only one surrounding tile with the lowest number.


A C3 cart pusher delivering from a timber yard to a furniture workshop and returning (with north up-left):

Going to the workshop, the numbering looks like this, with the path in bold:

.	.	6	5	4	.
.	8	7	.	3	.
.	9	.	1	2	.
.	.	.	0	.	.
.	.	.	.	.	.

The path goes from one plaza to the other plaza.

Returning to the timber yard, the numbering looks like this, with the path in bold:

.	.	3	4	5	.
.	1	2	.	6	.
.	0	.	8	7	.
.	.	.	9	.	.
.	.	.	.	.	.

When finding the reversed path in Part 2, the first plaza is not chosen, so the path goes around the statue.


A Pharaoh cart pusher delivering from a gem mine to a jeweler and returning (with north up-left):

Since this cart pusher won't cut corners, the only significant decisions are made at the plazas.

When delivering to the jeweler, during Part 2 a plaza is numbered 22 and has 3 surrounding tiles that are numbered 21. The tile in the direction of the walk origin (S) is not numbered, so the first tile found with the number 21 (NE) is selected. The cart pusher delivers using the top path.

For returning to the gem mine, during Part 2 a plaza is numbered 18 and has 3 surrounding tiles numbered 17. The tile in the direction of the walk origin (NW) has number 17 and is selected. The cart pusher returns using the middle path.

[Edit: fixed the algorithm, changed the last example a little, and used the terms "walk origin" and "walk terminus".]
[Edit: included fort parade grounds in C3 road-like tiles.]
[Edit: included elevation change ramps in C3 road-like tiles.]

[This message has been edited by Brugle (edited 04-22-2018 @ 02:51 PM).]

Brugle

The algorithm you describe seems to be a fairly simple "breadth first" technique, much like the one described here except your Part 1 goes start-to-finish and not finish-to-start. I'd always assumed a more sophisticated algorithm (such as A*) was in use - this one so frequently fails to find the optimal route I'm surprised we've not seen a lot more reported anomalies.

I recall one of your Tarsus builds having a cartpusher route one tile longer in one direction than the other. 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.

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.

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.

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

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:

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.

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:

your algorithm traces the path backwards after the destination is found (as does A*) reminds me of StephAmon's comments (Ambulomancy, 2nd edition)

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.

[This message has been edited by Brugle (edited 01-06-2014 @ 07:56 PM).]

Quoted from Brugle:

I hope that you .... don't feel slighted.

Of course not! I only quoted StephAmon because your narrative brought it to mind.

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.

We'll see.

I wonder if you tried your jeweler example in C3 (with different buildings, obviously). I found that set up as illustrated walkers choose the bottom route both delivering and returning. If the deliverer is moved 4 tiles NE the top route is chosen outbound.

Of course, it is the location of the walk origin that is important, not particularly the position of the building (nor its type). By extending the approach roads as needed, it can be shown that any walk origin that is level with or to the NE of those junctions will utilize the top route while one that is further SW will utilize the bottom. By re-designing to stagger the junctions (so that they are not on the same Y coordinate) we can see that it is the position of the walk origin relative to the second junction (ie the first looked at while back-tracing) that is determinant in choosing top or bottom.

If the expected preferred route is made unavailable the opposite is chosen, but never the middle route. This is unsurprising, since back-tracing through the second junction will always prefer a diagonal route (ie a turn) to a straight-through.

For the return journey (again extending roads as needed) we find that the walk origin needs to be moved 5 tiles NE to produce a top-walker (in Pharaoh behaviour changed after moving four tiles). In other words, it must be NE of the further junction but not in line. This seems strange until you think about rotating the whole set-up 180 degrees - if the walk origin is in line with the junction the walker turns right in either case. If the walk origin is "left" of the line (from the point of view of a walker approaching the loop) the back-trace produces a left-turning walker. Turns out this holds for 90 degree rotation too.

That would suggest that directions are relative rather than absolute - however a simple rectangle test confirms that a walker going from any corner to the opposite one goes anti-clockwise unless going from North to South, bearing out your given preferred order for tie-breaking on back-tracing.

Bottom-route walkers clearly break your algorithm. I have only a vague explanation; 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. This would only apply when faced with two opposite directions - if the choices are at right-angles the turn would be preferred anyway.

Consider the following (North is left-up):




The plaza on the right are walk origins for cartpushers delivering to the garden tile on the left. Obviously, for the return journey the walk origin is the garden tile. Both walkers take the top route in accordance with the NE preference rule on the back-trace from the garden tile. Although there are two ways of getting to the garden tile there is no actual junction there.

On the return journey both walkers take the bottom route despite the preference rule because the garden tile is further SW than the junction through which the back-tracing is done. The back-trace therefore proceeds towards the garden tile.

Now consider this:





There are still two ways to get to the garden tile, and those converge on the same point as before, but this time the back-trace is through a junction. The lower walker takes the bottom route because the back-trace is biased in that direction. For exactly the same reason the upper walker takes the top route. As before, both walkers return via the bottom.

One more ...




The walker takes the top route due to the heuristic. This time, although the possible return routes converge at the same point, it is no longer a junction so normal preference rules apply and the top route is taken.

I have no idea what is going on in Pharaoh, but it clearly works differently. I suspect the pathing algorithm has been tweaked to explore possible routes from both ends simultaneously.

[This message has been edited by Trium (edited 01-31-2014 @ 04:00 PM).]

Quoted from Trium:

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.

We'll see.

You're right.

I had thought that perhaps the programmers put in something complex to make the algorithm more efficient, and I didn't want to search for that. But your data suggested that a modest change to Part 2 of the algorithm could fix it, so I did some experiments. I think I now know the correct algorithm, but I need to do a lot more tests.

By the way, did you look at my latest reply in Save files - buildings table?

I revised reply #1. It appears to predict all destination walker paths.

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

Very good.

Quoted from Trium:

what is going on in Pharaoh, but it clearly works differently

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:

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.

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):
Note: if the architect post is moved 1 tile either NE or SW (with a road tile added or deleted), the architect takes StephAmon's predicted lower path around the statue (since the walk origin is N or W of the plaza).

[This message has been edited by Brugle (edited 02-01-2014 @ 02:37 PM).]

I added fort parade grounds to the list of C3 road-like tiles in reply #1.

I added elevation change ramps to the list of C3 road-like tiles in reply #1.