In a recent game I noticed all my scouts explored to the west of their houses. At first, all houses were near HQ, of course; and all exploration was to the west of HQ. The sector covered about one-third of a full circle, from NW to SW. Later scouts, sent from distant houses, did the same thing: They all explored to the area west of where they started. This was a desert map, very largely barren sand -- which I think may be significant.
I began to rough out some pseudocode when I realized the desired behavior (exploring in a full circle) is not a simple feat. The immediate neighborhood of the scout tells nothing about the overall map state. In fact, I suspect that my first stab at the pseudocode is remarkably like the current actual code: I prioritized directions of travel based on "interestingness".
The trouble with that is, when the map contains little of interest in any immediate area, a deterministic method will always produce the same result. That is, if all six directions have the same degree of interestingness, a straight sort will always return the same choice. (Depending on the sort algorithm.) I guess I'm lucky each scout didn't follow the exact same path, dead west.
Obviously, the method used now to determine direction of scouting includes some pseudorandomness; this needs to be increased.
I'll do a little experimenting and post a test case.
Here's a test case: a scout in the desert supplied with food, nothing else. If you watch the replay, I recommend 200x speed; takes a little while for the scout to eat all the fish in the pond.
You'll notice three flags off by themselves in the SW corner of player's territory:
1) I placed the first flag when the pond was fished out; HQ is then well-stocked and the tavern keeps the scout going.
2) I noticed the scout take a very small slice of new area quite a ways along and placed the second flag.
3) The third flag comes when all food is eaten and the scout stays home; this also terminates the replay.
The replay may not be terribly informative, since replays begin with all territory visible. But I also include in the tarball a screenshot of the minimap by game end. You will see that the scout has explored less than half of a rough circle around HQ.