A random walker may not repeat the same cycle of 4 walks!

Topic Subject: A random walker may not repeat the same cycle of 4 walks!

Brugle
HG Alumnus

posted 06-05-08 17:15 ET (US)

The walk of a "random" walker has (as far as we've discovered) up to 3 phases:
1) Going to a tile selected by an algorithm that starts by looking 8 tiles to the NE, SE, SW, or NW. The walker (or set of walkers) cycles through the 4 directions in subsequent walks. This is described well in StephAmon's Ambulomancy, linked from Predicting Roaming Walks.
2) Wandering around for a while.
3) Returning to its building.
My assumption, until now, was that phase 2) was determined by the surrounding road network, even though we didn't know the details. Therefore, with a fixed road network, the walker (or set of walkers) from a given building would repeat the same cycle of 4 walks. That assumption is wrong.

I was investigating whether a "random" walker tended to go straight (or in a particular direction) at intersections during the middle ("random") part of a walk. I used a water supply (since it doesn't collapse or spontaneously catch fire) in the center of a road network that had long intersection-free dead-end roads running off in 3 directions and a grid of roads with lots of intersections running off in the 4th direction. Using Pharaoh without Cleopatra, I added such a road network to my Baki, and noticed that while the walks of the water supply's citizen did cycle through the 4 directions, when the citizen went into the grid he took different routes. I watched through several cycles, then ignored my original question and investigated this unexpected behavior further.

Using Cleopatra, I built such a road network in the Sandbox custom mission (as well as a few houses, a fire station, and an apothecary far away from the test network). Once again, the citizen followed different routes when it went into the grid. However, after several cycles through the 4 directions, the citizen started to always take the same route in the grid. I watched the citizen repeat the same cycle of 4 walks through perhaps a dozen cycles. Then I deleted the water supply, built a statue in its place, deleted the statue, and rebuilt the water supply. This time, the citizen always took the same route through the grid, and followed the same cycle of 4 walks that the original citizen had eventually adopted.

I restarted the Sandbox custom mission and repeated the test with essentially the same road network (although the houses and other stuff were probably not the same). Again, the citizen immediately followed the same cycle of 4 walks that the original citizen had adopted. However, when I exited Cleopatra, restarted Cleopatra, and repeated the test in the Sandbox custom mission, the citizen followed different routes when it went into the grid for several cycles (roughtly 10--I didn't count), but eventually adopted the same cycle of 4 walks. I once again tried restarting the Sandbox mission, and the citizen immediately took the same cycle of 4 walks.

Using Cleopatra, I added a similar test netowrk to my Itjtawy. I watched for around 15 years (50-60 cycles of the citizen), and the routes kept changing. (Sometimes the same walk in the grid would repeat for a few cycles, but never many.)

In summary, a "random" walker is likely to repeat the same cycle of 4 walks, but sometimes it may not. I don't have an explanation.

This has little effect on my design and play, since I don't depend on a particular behavior (other than not turning around) during the middle phase of a "random" walker's walk.

I've only checked this for Pharaoh walkers (actually, only for the citizen from a water supply), so I don't know if it applies to Caesar III walkers.

I apologize for all of the erroneous remarks I've made about a random walker repeating the same cycle of 4 walks.

I should have known better.

[This message has been edited by Brugle (edited 06-05-2008 @ 05:17 PM).]

Author

Replies:

Trium3
Pleb

posted 06-06-08 11:32 ET (US) 1 / 9

I might have guessed you'd be playing around with that after recent discussions in the other thread. So was I

Your findings are interesting, if perplexing. Rather than shedding light on how the middle phase of a walk is computed, they seem to further obfuscate it.

It would be interesting to see if your results can be replicated in Caesar 3. There are, of course, known differences between C3 walkers and Pharoah walkers (corner cutting, use of gardens (neither of which apply during pure 'random' mode)) and this may be another. All of C3's algorithms appear to produce consistent output if no changes are made. If you run a save for five years then repeat the excercise all walkers seem to end up in exactly the same places, fire risks are at exactly the same levels, etc.

In Pharoah there is more randomization - fire risks can vary. For example, the first time I looked at your Meidum I was very surprised when a library caught fire - it's not like you to submit a city with that sort of event uncatered for. I re-ran it several times without recurrence, but the fire overlay shows some buildings' risks getting scary, and the those buildings are different each time. This is despite the marshall's routes being constant.

It may therefore be that the algorithm used to determine choice at an intersection is more randomized in Pharoah than C3. Knowing whether your observations will hold for C3 would give an indication as to whether randomization is or is not causing your observed behaviour. At least one (maybe two) of your tests appears to hint that either the system clock or the lapse of game-time might possibly be used to randomize the algorithm (and those are the sort of things that a programmer might use to do so).

I am inclined to expect that it is not. A random element in the computation is likely to produce more variation than most players seem to have observed and is unlikely to settle down into a pattern after a few deviations.

I'd be interested in knowing more about your test setup - in particular what you mean by a 'grid'. In some of my tests I used dense grids in which every tile was a road, intending to give the walker complete freedom to turn where he wants when he wants, but I found that the game seems to treat such interconnected tiles as being almost like one extra-wide road and turns are not usually taken while in pure 'random' mode.

I'd also be looking at the phasing of that fourth walker. the precise frequency of his sorties will depend upon the length of walks in each direction (anything from 26 to 102 tiles) though I would expect that for any given setup the interval would be constant and invariable.

One other thing occurs to me - your tests use a citizen rather than a walker (mine too most of the time - it can interfere with the test to have to get the building functional) who has a specific objective - recruiting labor. Is it possible that the game somehow intervenes when it is known that so many journeys along a certain route have been unfruitful and tries another way? It wouldn't explain everything you observed, but it's a thought.

Brugle
HG Alumnus

posted 06-06-08 14:45 ET (US) 2 / 9

Quoted from Trium3:
It would be interesting to see if your results can be replicated in Caesar 3.

I hadn't planned to do so, but why not? So I ran some quick tests: in my No Trade Lugdunum on a missionary, and in my No Trade Valentia on the citizen from an engineer post and on a barber. All went straight ahead (in the original direction, which happened to be NW) in the grid until turning around to return to their buildings. I'd guess that all C3 random walkers are more predictable in the middle (random) part of their walks. (Of course, since I only tested a few C3 random walkers in one way, it is very possible that I missed something.)

To make sure that the citizen from a water supply wasn't a unique case, using Cleopatra I tested a dentist and an herbalist in the Sandbox custom mission. Both of them took different routes through the grid, like the water carrier.

By the way, I now have doubts that a Pharaoh random walker will settle into the same cycle of 4 walks eventually. When testing the dentist and herbalist, I saw each of them follow the same route in the grid through several cycles (perhaps 4), then start changing routes again.

Quoted from Trium3:
There are, of course, known differences between C3 walkers and Pharoah walkers (corner cutting, use of gardens

I wouldn't call either of them a difference between C3 and Pharaoh walkers, just a difference on which walkers are allowed to do those things. Some Pharaoh walkers can cut corners, just not when having to follow a road. When Cleopatra is installed, enemies can use gardens.

Quoted from Trium3:
In Pharoah there is more randomization - fire risks can vary.

I don't want to pick nits, but in C3 fire risks can vary too. I had a building catch fire in one C3 city after almost 200 years of no changes. As you know, the difference between the games is that if I repeated that C3 "free run" I'd expect the same building to catch fire at the same time, while I would not necessarily expect a Pharaoh "free run" to produce exactly the same result when repeated.

Quoted from Trium3:
I'd be interested in knowing more about your test setup - in particular what you mean by a 'grid'.

Most of my tests in the Sandbox custom mission were with a non-"dense" grid, with roads every 4th tile in a 7 by roughly 40 tile rectangle (3 long roads extending away from the water supply and maybe 10 cross roads). All of the other tests were with a "dense" grid, with roads everywhere in a 7 or 9 by roughly 40 tile rectangle. The roads in the other directions were placed more casually, usually straight (but sometimes straight for a while then a bend at an obstacle), and usually long enough so that the walker was in "return to building" mode before getting back to his building (but one of those roads in Itjtawy was short enough so that the citizen wandered into the grid for a few tiles, not always following the same route).

Quoted from Trium3:
I'd also be looking at the phasing of that fourth walker. ... I would expect that for any given setup the interval would be constant and invariable.

Since the length of the walk in "the grid" can vary a lot, the interval between the starts of successive walks in a given direction can also vary.

Quoted from Trium3:
Is it possible that the game somehow intervenes when ...

I doubt that the game tries to be that smart. But who knows? My guesses have been wrong lots of times.

street
Pleb

posted 06-06-08 15:14 ET (US) 3 / 9

I'm glad you guys have the patience to do these tests!

Are you a victim? Of anything? Become a survivor by working for change. If anyone else suffers less than I did, then my pain has served a purpose and I hurt less.

Try it http://c3modsquad.freeforums.org/!

Trium3
Pleb

posted 06-06-08 19:08 ET (US) 4 / 9

Quoted from Brugle-
I would not necessarily expect a Pharaoh "free run" to produce exactly the same result when repeated.

That is the point I was making, albeit clumsily. I did not mean to suggest that fire risk doesn't vary in C3, just that the variation is repeatable and therefore not 'randomized'. This is not the case in Pharoah.

Most of my tests have been in C3 though I do remember watching a walker twist and turn through a 'dense' grid in Pharoah in ways that I would not have expected in C3 (Perhaps my comments elsewhere regarding 'double width' roads were inappliccable to Pharoah and I will need to look again). In C3, as you found, turns are not usually made in such a grid, but if tiles are removed so as to separate parallel roads turns are made much more frequently. The removed tiles might have been ignored by walkers previously, and therefore one would have thought they would have no relevance, yet their removal causes different choices to be made. I have observed that the routes taken can vary if the test site is moved a tile or two, and that walkers on different quadrambles can make different decisions at the same intersection, but I have not observed what you report - the pattern, once established, does not seem to change (I'm still talking about C3, of course).

Since the length of the walk in "the grid" can vary a lot, the interval between the starts of successive walks in a given direction can also vary

Which may (or may not) be a further clue in identifying the factors which are taken into account at decision-making time. It does not seem unreasonable that timing would have a bearing.

By the way, I now have doubts that a Pharaoh random walker will settle into the same cycle of 4 walks eventually. When testing the dentist and herbalist, I saw each of them follow the same route in the grid through several cycles (perhaps 4), then start changing routes again.

That would suggest that the phasing relative to some game cycle is shifting, particularly if the pattern of settling then changing repeats cyclically. But I'm imagining your tests rather than running them, so I'm perhaps jumping to conclusions too readily. I'm actually building a city at the moment (for a change) so I'll have a closer look when I can (by which time you'll probably have it sussed anyway

)

Brugle
HG Alumnus

posted 06-06-08 19:59 ET (US) 5 / 9

Quoted from Trium3:
I have not observed what you report - the pattern, once established, does not seem to change (I'm still talking about C3, of course)

My C3 tests were very limited (for example, only on a "dense" grid), so I didn't mean to generalize much from them.

Quoted from Trium3:
by which time you'll probably have it sussed anyway

Not me. Unless an unexpectedly strange urge comes over me, I don't expect to investigate this any further. My main reason for posting was that I had made the incorrect assertion that a random walker would repeat the same cycle of 4 walks, which I wanted to correct.

joshofet
Pleb

posted 06-07-08 07:07 ET (US) 6 / 9

Because we don't fully know what factors actually contribute to the walker behaviour, it is hard to draw definite conclusions. In fact the only thing we know for sure is that the algorithm must be implemented in a finite size code, but that does not help very much either. It is surprising the same algorithm may not apply to all walkers, I guess it would be safe to assume it applies to all walkers from a certain type of building, but we cannot be sure until we know the code, and I doubt that will ever become available.

So you set up an hypothesis, and start looking for counter examples. Since probably some stochasticity ("randomness") is involved, it may last very long until you find one, so I do not see any need in making apologees for an earlier erroneous statement that only after further investigations has been identified as such. The only thing you should have known better Brugle, is to make any definitive statements at all

I'm not entirily sure what the present conclusion should be, but it seems that apart from a (short?) transient period after the game has started, water supply workers do indeed follow a fixed routine. Maybe after 10,000 cycles they do deviate again, you (we) haven't tested that long

. Other walkers appear to deviate earlier, in CIII (or Cleo, or Zeus/Poseidon or ERotMK) again it may be (a bit) different.

I have seen very few instances in these games where there is actual randomness in the sense of an external call to a system variable as the time or such. In most cases internal (pseudo)random variables are used, sometimes depending on internal variables such as game time, or number of buildings, or road networks. I would be surprised if the "random" walker phase was any different in this aspect.

Since as you say Brugle, it is very well possible to set up your city in a way that it is not or very little dependent on the outcome of the random phase, there is a practical solution for any player who is interested in deterministic behaviour of the city. There is no 100% guarantee though ...

Cantique
Pleb

posted 06-07-08 09:30 ET (US) 7 / 9

I would be inclined to feel that the random phase od a walker has nothing to do with conditions, other than road network. although this may not account for all the completely random paths that walkers appear to take. Pharaoh seems too well thought through to take variables and the like from outside the game (such as system clock etc.)

As for the ideas of the rest of the city affecting walkers (excluding road network) this seems odd too. Posts in the thread, Baki Observations, have stated that the game does not 'help' you by taking into account what state the city is in. this seems to make perfect sense. but to then apply that to walker behaviour seems strange.

my guess, although i have nowhere near the sort of experience that Brugle, Joshofet, and Trium3 have, is that walkers have set probabilities as to whether they will turn off at an intersection according to: how long they have been travelling in teh same direction for (in random mode) and, what distance type they are (ie. fireman 26 squares in the random phase of his walk - i think!)

[This message has been edited by cantique (edited 06-07-2008 @ 09:36 AM).]

joshofet
Pleb

posted 06-07-08 11:57 ET (US) 8 / 9

Test it!

Trium3
Pleb

posted 07-01-08 05:29 ET (US) 9 / 9

Those who follow the Caesar 3 Forum will probably know that the 'random' phase algorithm has now been found to boil down to a simple function of the number of tiles walked in random mode (cantique's 'Phase 2') and the random number 'seed' associated with the tile. It has also been discovered that, with a little experience, the random number seed is determinable either by deduction (observing behaviour of walkers) or by study of the landscape (the terrain graphic used also depends upon that random 'seed').
See reply #21 of this thread, the thread linked in replay #24 thereof and this thread for details.

I'm afraid all I can tell you about Pharoah is that it most certainly does not behave the same as C3. This is somewhat surprising since Phase 1 walks (Ambulomancv) appear to behave identically, walker 'endurance classes' (default walk lengths) are basically the same, building spawn/return algorithms are mostly identical, etc.

One difference in Pharoah that makes a tester's life difficult is that 'random' walkers are always confined to road tiles - no corner-cutting and no use of gardens. Although we can theorize about which mode a walker is in (which phase of his walk he is on) we do not have the visible confirmation we enjoy in C3 and it is very easy to make mistakes in supposing where a mode conversion should take place.

Another difference is that Pharoah maps the various grids stored in the game files to the screen differently. In Caesar 3 both the map and the grids which store elements of it run diagonally across the screen. In Pharoah the map is rotated 45 degrees relative to these grids, complicating the determination of the random 'seed' at a given point.

I must confess I have made little sense of what I have seen so far. I have actually observed, but have been unable to replicate, more than one example of a walker turning around (in an intersection) while still in random mode. On one occasion an architect and a firemarshall were a couple of tiles apart (executing the same 'quadramble' from spawn points a couple of tiles apart). Both followed the same path and both turned around in a 4-way intersection at the same point. Neither walker repeated this behaviour on subsequent cycles

Even if I could establish how the random 'seed' affects decisions it would not be so easy to visually determine that seed from the landscape. Pharoah automatically overlays lush greenery adjacent to water tiles, thinning out as the distance from the water increases. This overlay is impenetrable, so we can only poke holes with the delete tool in arid regions. In those regions the differences in the graphic tiles selected according to the random number seed are so subtle that it would be very difficult to say with confidence what seed underlies a particular tile.

Caesar IV Heaven » Forums » Pharaoh: Game Help » A random walker may not repeat the same cycle of 4 walks!

Top