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.
June 10th, 2010 - 06:56
I thing you are over-complicating things again. In the above example, you state that for each action you would need to update a lot relations for each action taken by any character (be it the hero of an NPC).
However, in a realtime simulation (or even turnbased, based on your timespan), you would only need to update the relations as they take place. If the hero buys the sword, it would take time for the shopkeeper to go buy his food. After that it would take time for the next action to happen, because the NPC’s will actually have to take that action.
If you let them perform these actions, the relations will be updated on a one on one bases each time, as one character interacts with the next. Even if the miller goes out of business each person in the town will only be affected when they go buy bread (or if an other person tells them.)
This would make the system a lot more manageable and far less complex. Even if you have a lot of relations between character, the effect of any action would slowly spread as the character would interact with each other.
June 10th, 2010 - 07:54
real time updates wouldn’t be a problem if all interactions where one on one, properly distributed over time and containing limited information. If on a party (or Marketplace) something big happens then the amount of updates would be enormous, poorly distributed and most likely contain many (Redundant) information. Let me say that if the player is there at the moment in time no matter what kind of update you use, be it forward (real time) or reversed updates, you will have a performance hit.
But what if the player is nowhere near that place (another city)? Real time updates would cause a performance hit that the user will not be able to explain.
The idea behind reversed updates basically say: “We deliver only on demand and if there is no demand we won’t update and when we update we will have relevant information first available and less relevant information later”.
I will try and write out a scenario later which handles all cases (real time forward updates, delayed forward updates, reversed updates) including an estimation how much it would cost in terms of performance.
October 26th, 2010 - 02:12
I’d like to see if you could think of it in terms of path-finding, where an action (going forward) causes a series of consequences that are found using a pathfinding algorithm (Say A*, but that may not be best) – the first action causes a “ripple” that starts a series of events searching through relationships / events around the first, looking for a path that causes the best sum of “plot” or “benefit” and keeps causing ripples outward until the initial “importance” or “strength” is spent.
Might enable you to pull this idea off…
October 26th, 2010 - 12:14
That is actually quite a good idea. It does rise another issue, how would you give the plots a mathematical value? The plots are created by the computer (to find a solution for the current state of affairs).
There are actually quite a few solutions for this problem (story templates).
By the way I did find this paper: Story generators: Models and approaches for the generation of literary artefacts which might be of some interest to you.