Faction

[Swingfirst]

Why not divide barbarian cities into different factions. Each faction might have their own number of cities, and their own enemies or allies. They may also give quests (take three enemy barb cities, etc) when you attack a barb you gain faction from their enemies and lose faction from their allies. They may also attack you if their faction gets too low.