I was thinking about entering PROCJAM this year, and thought about making something to generate random histories and myths. I wrote The Lives of the Kings of Cere to illustrate what sort of texts I wanted it to make, which you can read here.
My inspiration comes from the myth generator being developed by Bay12 Games, which Tarn Adams speaks about here. It starts with a single entity (a god, a cosmic egg, etc.) which proceeds to randomly spawn and interact with other entities (which spawn more entities, and so on). The result is a list of interactions and spawnings, which together make up a complete mythology.
Example output from Dwarf Fortress' Myth Generator
I'd like to take this approach further by adding more states to the entities, which will guide their interactions (and hopefully make them more sensible). I'd also like to use a scheduling system (developed for The Amaranth Saga) so that events can take place over anything from days to millenia (defined with probabilities like 1% per month or 1% per century).
The idea is that, as the generator runs, entities change state, altering what interactions and events they may have. Civilisations may enter periods of prosperity and decline, gods may become dormant and reawaken, etc. State can also give things personality. King Sturgyx may be tagged as violent, and become more likely to declare wars, whereas Queen Ihyrta may be tagged strategic and become more likely to win. Tags may be passed on to children, giving events more consistency over time.
I believe this approach can create fairly high-quality histories, and indeed there's precedent for this. Drawf Fortress' Legends more allows the player to browse through the history of a procedurally generated world, and it's full of interesting phenomena not directly added to the system. For example, in Dwarf Fortres histories, you occasionally see monsters and warriors racking up hundreds of kills in battle - this results from an underlying model where characters gain experience (i.e., state) from killing.
Example output from Dwarf Fortress' Legends mode
Now, Dwarf Fortress is not intended to generate texts - its histories are read by clicking links, similar to browsing Wikipedia. I propose to generate histories by focussing on particular subjects (like a particular nation), filtering out irrelevant events and information. The History of Elmshire (for example) might contain only events occuring in that place, whereas The Chant of Ibis may include events related to Ibis and their immediate family. Chapters of texts could cover particular time periods or side-characters, not always in chronological order.
Finally, having mythic histories spanning (potential) millenia raises interesting historiographical issues. If Abanas the Creator of All Things wanders the cosmic desert for a thousand lifetimes, we don't want to later say Emperor Such-and-such was born in the year 50000. Either dates could be left out, or we could use Regnal Years often used at the edge of history, like "In the 27th year of Queen Sangawe's reign". This might actually add to the final text, challenging readers to put events in their proper orders.