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.
Information about Brick3
Brick3 is the third iteration of the grand project I decided to call "Brick" and I think I have mentioned it quite a few times before, but never gone in to detail, which is the reason for this post.
I'm from the IT sector and one of the things I thought myself early is that the computer should work for me and not the other way around. In the Netherlands IT used to be called "Automation" but I'm not certain if many people still know that or try to write programs by that principle.
In the game industry we have something called procedural generation (also known as procedural content generation) which is letting the computer generate the content in game. This can be music which changes depending on the amount of danger the play can be in (adding rhythmic drumming) or textures which are generated by the computer instead of an artist. Those are all examples of generating content by the computer instead of by human.
Any process can be fully converted to logic and any logic can be programmed. A computer can be used to execute any process as long as I'm able to convert the process to logic and program that logic.
-- Wouter Lindenhof
The above quote is mine. And what I'm saying is that in time a computer should be able to replace any human, although I don't that to happen in my lifetime (and I'm young).
However the above quote is what brick3 is all about. The earlier examples were all based on the fact the design was done ahead of the actual content generation. After all the music was composed and the texture that was generated was most likely done based on an algorithm. An example for the last one but then for a mesh can be found in this blog post Donuts! (Procedural Torus in C++).
Brick3 is a bit different as it wants to let the computer do the design instead of you. It tries to generate a flat and based on requirements (you don't want a toilet in your living room) it will place the location of rooms and places the objects (lamps, light switches, paintings, trashcans et cetera). If you would use that in game like for example Grand Theft Auto you would be able to enter every house and assuming everything works correct you would have a fully designed interior while as a programmer (or artists) you hardly have to do a thing.
Anyway since a picture sometimes says more take a look the following screenshots.
This screenshot shows the minimal graphical quality I want to have. Graphics are important as they play part in deciding whether or not to buy a game. Besides that it also says a lot about the level of finish and the dedication put in the product. Although walls appear to have depth, they are flat, but using some smart programming code an illusion is created and when you look at the next screenshot I think everyone will agree that high graphical quality is a requirement for this application.
This screenshot shows the current state of the application. You will see that everything has a dummy texture and you will notice that not all walls are attached (this is because that a door is not generated and once it is does it will show a nice door frame). Both rooms have the same function and the big room that is directly in front of the camera is a test room (it is 27 by 27 by 27 meters big).
Besides the obvious issues the application is reaching its completion. There are some minor issues with placement and I need to improve the performance at some points but after that I only need to add some new models (the furniture is not procedural generated) and I will give some extra requirements and the application should design a room according to my specification.
Although I have to admit it doesn't look like much at this point, I think many people will be surprised once the end result is ready. Not only will it be able to generate fully random interiors of flats, buildings and rooms but it will do so as if it was designed by a human and only I have to do is hit one key to generate a complete new result.