Reverse updates
It has been a while since I last posted something, but that is because I have been busy with my graduation (in case you were wondering).
Anyway, today, while I was walking the dog, I suddenly realized how to fix a bottleneck for a certain game idea. The game idea was that the hero can interact and affect lives of other characters in the game directly, the bottleneck however was that each character affects another character, which affects another character and so on. A simple example would be if you decide to buy a weapon or not. If you do buy a weapon the merchant will be able to stay in business, buy some bread. When he buys bread, the baker will be able to buy the next shipment of grain from the miller and the miller we be able to pay the farmer and everybody will be happy. Now if you don't the miller might not be able to some bread (he needs to eat also) which means that he goes out of business. Since he is the only miller in the entire region, there will be no more bread for quite some time and everybody dies from the hunger.
The problem with that game idea is that if you even simulate a small village (say 25 people) you will have a lot of relationships to go through. Even if it goes in one direction it will still be 1 hero times 1 person times 25 people times 24 people times 23 people et cetera. The total amount of relationships within the village would be 1.6E+25 (16 with 24 zeros behind it). Even if we say that any action will have not have any affect after 7 relationships that would still be 2.4 billion relationships that are affected. If we limit the amount of relationships to 7 for each person (so 7x7x7x7x7x7x7) it will be 823543 of relationships that need to be updated when the hero does something. And maybe one of those persons affected will need to perform an action that affects the community which means the entire process starts over again.
Of course the game is real time and the other people in the village don't require you to perform any action so if you have 3 or 4 villages you will have almost a constant rate of large social updates. Until this morning it was my firm belief that the above game idea should be hard if not impossible to execute unless you have some monster system.
I always thought in forward direction, what happened now dictates the future, until I thought about reversing the flow, the past is dictated by the future.
Lets take the previous example of buying a weapon or not. Although this is a fact now by the player, the game does not have access at that information at the current time. Let's say you meet the miller and find out he is alive. No matter what happened in the past, the future dictates past events that no matter what the miller survived and kept his job. And the only way that he has kept his job if the baker bought his grain and the only way that the baker could buy his grain was if some paid for his bread. If you made a major investment by buying a weapon (say a gold weapon) then he might credit you for it. If you weren't the cause something else must have happened for the influx of money that allowed the community to stay alive.
Now lets take the same example but the miller is dead. The past generated from that point on could dictate that the hero not buying could have caused it. Or if he did buy the past could credit something else (disease, war, bad crops et cetera).
So what is so different about the reverse update compared to the forward update that it allows us to compact information in such a manner that the above game idea is possible?
Simply put: Forward updates are simulations, calculating exact future behavior, while reverse updates are emulations, imitation of past behavior. A forward update always has one cause (generally the hero) but has many effects (the merchant, the baker, the miller and the farmer). A reverse update has one effect (the baker) and will look for one cause for its current state which is a linear path.
I'm not certain if the solution always works as the past needs to be consistent (you can't undo the past) and certain actions always have a forward update, but for now the game idea seems possible again.
Procedural story
A little while ago I was meeting a good friend of mine and we had a lot of things to talk about. For one he had just returned from Kenya and he had a lot to show and tell and the things he told me where amazing. But as the day went one, we almost always seem to come back to one subject: Games and developing of games. Funny enough the two of us have almost had the same kind of ideas.
Both of us are developing games in our free time and both have the idea of trying to make as much as possible procedural generated. One of the things we are both interested in is creating the story. While I look for an infinite solution (where the player can play forever and has an interesting storyline) he has a more pragmatic approach.
As we discussed procedural generated stories he pointed out that a story teller needs to tell his audience what happens where and when (not to be confused with why). This triggered a thinking path I had not yet explored. Until then I had simply assumed events happen in a certain order. When a user is playing a computer game he will grow a certain emotional attachment to the player. Emotions in a story are important. For example Romeo and Juliet is a story about hate between families, love between two person and has a lot of betray. Romeo and Juliet is considered one of the classic romantic stories and by some it is considered one of the most romantic stories ever written.
So after the talk and some thinking a procedural story generator could be written as a system that tries to move from emotion to another emotion both for individuals as a culture. To give yet another example: The player gets betrayed by a general and while he was betrayed the general does end the war (and the country he fought for sees him as a hero), while at the other side (the defeating side) wants to see the general death. You now have four elements: The player, the general, the winning country and the losing country. The player is angry as he is betrayed. The general is content and pleased as he is being seen as hero. The winning country feels superior to the losing country and the losing country feels disgust towards all other elements. See the diagram.
At this point the computer needs to "write" the next part of the story. The computer could now plot a new scheme by just adding or removing some story elements. The player could for example become the leader of the rebellion or he could join the general as one of his right-hand leaving his feelings of betray or he could kill the general and become the new general. In this case I want to add another character say the princess of the winning country and make the player the leader of the rebellion. The princess finds out that the generals betray and for some reasons she encounters the player and they fall in love with each other. Yet they can't be with each other as one country hates the other ruler. The general at this point hates the player. The graph might be clearer.
Moving forward we arrive at a point in the story where the player and the princess are married and they rule both countries. The general is now hated by all. And here is another graph.
For the story generator the only thing is how the possible futures of all elements could be. Once he knows the possible futures all it has to do is create "story chapters" which move the story toward the possible features. If needed a chapter could have a branch which excludes one of the possible features, for example the player kills the general before the princess was able to find out about the betray of the player so she never finds out the wrong he did and therefore never encounters the player.
Of course a lot more thought needs to go in this, but it solved for the procedural "writers-block".