In a campaign where everybody knows your name, the random encounters may not be so random in-fiction. This is a procedure for random encounters with groups that already have intentions regarding the party. If the party has a leader or highly-ranked PC, use their reaction for these rolls.
Every encounter has a goal, a force, and an origin.
Specifically relates to something of the party's— their enemies, their allies, their assets. On a positive reaction roll, the encounter is likely to be helpful to the party, such as by attacking their enemies, swearing themselves to their allies, and enriching their assets. On a negative roll, the opposite is true. In the neutral reaction result is where the interesting decisions need to be made. Perhaps they seek to learn more about an individual who is an enemy or ally of the party, or have a treasure to trade for something the party possesses.
d6 Goal Target
1. Party's enemy
2. Party's asset
3. Party's ally
4. Party's identity (species, social class, etc.)
5. Party's territory
6. Party's goal
The creatures that constitute the encounter. Consider, based on their goals, whether there are any noncombatants attached to the force, such as laborers, family, or guides.
The force's originating hex and any base or lair therein. If the encounter has a notable outcome, you may wish to add the base to your hexmap key to track its status.
To demonstrate this (and in unholy combination with TVTropes for flavor), here is a generator for the Rebelia region of my Byzantine project: