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.
Large scene rendering
There is one thing I don't like about floating point and integers and that is that they consist out of only certain amount of bits. An integer is at least 32 bits (on 32 systems at least). A float is also 32 bits. A double is 64 bits.
Since I'm currently thinking about a space game, I was wondering how to create a huge battle field (a whole solar system) in real time while having all the precision I need.
Doubles are not fast and take a lot of space and although I don't worry about space, speed is a bigger issue. If I want a huge battle and here I'm going to throw some numbers: One side can have as maximum 85 huge ships, 3010 fighters, makes 3960 weapon slots, which makes 19800 bullets flying around. And that is only one side. Since I need two sides for a war, I need to double the values (190 ships, 6020 fighters, 7920 hardpoints, 39600 bullets). Lets say that everything is represented by one location (which a 3D vector) it would mean 53730 locations. 53730 locations times 3 would be 161190 and that times [cci_cpp]sizeof(double)[/cci_cpp] would be 161190 * 8 bytes = 1289520 bytes (about 1MB) which is a lot to start with even if you ignore the fact that the problem is more that I have a lot than the doubles are bigger.
As I was considering the problem I realized something else. When I'm rendering, I will need to use floats. DirectX 9 requires floats and although I could send doubles it would half my data bandwidth. So what ever I choose, in the end I will need to use floats unless I want to have some penalty.
Using doubles for vertices are is a bad idea for the sake of precision alone.
But then I started thinking...
I don't need to render using doubles, I can simply render everything with floats and to ensure that precision is maintained. If something is not within the safe area of floating point rendering (let's say floats can have a maximum of 1024, and yes I now it can be a lot more) but the object in question is 2048 units away, I still want to render it. You can't simply let a sun disappear because it is beyond the range of your numbers, that would be weird.
Instead everything that is more than 1024 units away will be rendered first (farthest away first) and the distance also scales it down. Than I clear the Z buffer and render everything in the 1024 range.
[cc_text]
Sun has a size of 100
Sun is 2048 units away
Sun needs to be rendered.
To render it but maintain the correct look:
Scale sun down so that at 1024 it would have the same
size on screen as if it was rendered at 2048.
[/cc_text]
It was so simple that I thought it was silly I never thought about it. How you scale it however depends on the view and projection matrix.
I'm still not certain if I want to use doubles, but for my second problem I have a solution. Now I need to find one for my first.
Marketing and fuzzy distribution
I have mentioned fuzzy logic and random distribution before but I think that it is also being applied in some marketing strategies.
A supermarket chain in our country is giving away collectibles in the form of images of football players (soccer for the Americans). For every, Oh… I don’t know, € 5 , you spend you will get 5 random pictures.
At lunch my mother, who collects them, was going over a list of friends seeing if they have a picture she doesn’t have or the other way around and she noted that certain images nobody seems to have.
If you think about it from a marketing perspective it makes a lot sense why she doesn’t have certain images. The marketing strategy is all about making you willing to pay a certain amount or attract customers because you want those pictures. Once you have them, the marketing strategy will no longer have affect on you. It is in interest of the marketing company to try and keep you as long as possible under the effect of the marketing strategy.
One way of doing it by doing an imbalanced distribution: Certain pictures will not be distributed in certain locations. That way the customer under the effect of marketing will keep buying. Of course this won’t hold in the long run, so what you do is slowly slide the distribution.
Sliding random distribution:
A distribution whose content is randomized will only distribute a small subset which moves over the entire distribution so that in the end the entire content was equally distributed, however if a moment in time was used only a small subset would have been available.
If you have trouble understanding think of it as traveling from the north pole to the south pole visiting every restaurant you can find. At every stop you will select one random soup on the menu. Each place has different flavors and as you go more and more south you will encounter different flavors. However because your are “sliding” you will often encounter the same soup.
Anyway if that wasn’t clear here is it in code:
[cc_cpp]
#include
#include
#include
#define MAX_AMOUNT 100
#define SLIDER_SIZE 5
/* Uncomment the next line to see the values in random order */
#define USE_RANDOM_ORDER
class SlidingDistribution{
int m_Values[MAX_AMOUNT];
int m_SliderBegin;
int m_SubPos;
public:
SlidingDistribution() : m_SliderBegin(0), m_SubPos(0) {
for(int i =0; i < MAX_AMOUNT; ++i)
{
m_Values[i] = i;
}
#ifdef USE_RANDOM_ORDER
std::random_shuffle(m_Values, m_Values + MAX_AMOUNT);
#endif
}
int GetRandomNumber(){
m_SubPos += 1;
if(m_SubPos % SLIDER_SIZE == 0)
{
m_SliderBegin = (m_SliderBegin + 1) % MAX_AMOUNT;
m_SubPos = 0;
}
return m_Values[(m_SliderBegin + (m_SubPos % SLIDER_SIZE))%MAX_AMOUNT];
}
};
int main(int argc, const char** argv)
{
SlidingDistribution distribution;
int amounts = 0;
do{
int alignCounter = 0;
while(amounts)
{
std::cout << std::setfill(' ') << std::setw(3) << distribution.GetRandomNumber();
alignCounter++;
if(alignCounter >= 14)
{
std::cout << "\n";
alignCounter = 0;
}else
{
std::cout << " ";
}
amounts--;
}
std::cout << "\n" << "How many values do you wish to see? (type 0 to quit)\nLoops: ";
std::cin >> amounts;
} while(amounts);
return 0;
}
[/cc_cpp]
STL algorithms
UPDATE@2010-Feb-23 22:11: Thanks to Arseny Kapoulkine (his blog is : http://zeuxcg.blogspot.com/ ) I discovered that there was a bug in the code I showed. I have fixed this bug
I'm not a huge fan of the STL library (you know [cci_cpp]std::vector[/cci_cpp]and it's relatives) as I don't like the syntax and the naming of some functions and yes, I'm well aware those are mood points but then again I'm always looking for perfection. But there is one part of the STL library I really love which is STL algorithms.
For example, let's say we have the following code
#include <vector> /* ... * Somewhere in the code * ... */ std::vector<int> numbers; numbers.push_back(1); numbers.push_back(2); numbers.push_back(3);
And we want to remove the number "2" from the vector, sadly [cci_cpp]std::vector[/cci_cpp] is lacking a remove function. It does have an erase function but that would require an iterator. We could switch to [cci_cpp]std::list[/cci_cpp] who does have a remove function. Without STL algorithms we would write something like this:
/* Written for readability
* And it only removes the first one it finds.
*/
template <typename T>
void RemoveFromVector(const T val, std::vector<T> vec)
{
for(std::vector<T>::iterator begin = vec.begin(); begin != vec.end(); ++begin)
{
if(*begin == val)
{
vec.erase(begin);
return;
}
}
}
/* ... And here we call it */
RemoveFromVector<int>(2, numbers);
The only thing I can say about it is that it looks ugly. Now let's use stl algorithms and see how that looks like.
/** * Previously the code was: * std::remove(numbers.begin(), numbers.end(), 2); * But that only removes the number, but keeps the same size. std::remove instead * returns an iterator which holds the end. (numbers.size() would give the same * result before and after the above code. * Thanks to Arseny Kapoulkine this has been corrected and the good version is * now here available. */ numbers.erase( std::find(numbers.begin(), numbers.end(), 2) );
One line of code and that's all. Well, it's still one line of code, but two rather simple functions. The [cci_cpp]erase[/cci_cpp] function takes an iterator as input (which [cci_cpp]std::find[/cci_cpp] returns for you). However keep in mind that if [cci_cpp]std::find[/cci_cpp] can't find a result (for example "2" was already missing, your application will crash.One thing I always hate was when I stored pointers in an object that needed destruction
#include <vector>
#define SAFE_DELETE(p) if(p) delete(p); (p)=0;
class StorageObject1;
class StorageObject2;
class StorageContainer
{
std::vector<StorageObject1*> m_Objects1;
std::vector<StorageObject2*> m_Objects2;
public:
~StorageContainer()
{
for(size_t i = 0; i < m_Objects1.size(); ++i)
{
SAFE_DELETE(m_Objects1[i]);
}
for(size_t i = 0; i < m_Objects2.size(); ++i)
{
SAFE_DELETE(m_Objects2[i]);
}
}
};
The above example is rather tame but if you have a lot of different objects it quickly becomes ugly to look at. However with a bit of ingenuity you can become a lazier programmer. Here is the same example but then easier to read
#include <algorithm>
#include <vector>
#define SAFE_DELETE(p) if(p) delete(p); (p)=0;
template <typename T> void SAFE_DELETE_FUNC(T* object) { SAFE_DELETE(object); }
class StorageObject1;
class StorageObject2;
class StorageContainer
{
std::vector<StorageObject1*> m_Objects1;
std::vector<StorageObject2*> m_Objects2;
public:
~StorageContainer()
{
std::for_each(m_Objects1.begin(), m_Objects1.end(), SAFE_DELETE_FUNC<StorageObject1>);
std::for_each(m_Objects2.begin(), m_Objects2.end(), SAFE_DELETE_FUNC<StorageObject2>);
}
}
Of course you can make the function even a bit smarter so that you don't have to write the start and end iterators, but I prefer it like this. Here you can find the other versions of STL algorithm: http://www.cplusplus.com/reference/algorithm/
Donuts! (Procedural Torus in C++)
Recently I got a mail through the contact form of my website about texture mapping on torus (a donut) who said that [cci_cpp]D3DXCreateTorus[/cci_cpp] didn't not provide texture coordinates. The reason why DirectX and OpenGL (and GLUT) don't provide texture coordinates with these function is best seen when you generate a cube. A cube has 8 vertices, however when you add texture coordinates it will increase because otherwise they will share the same texture coordinate. With normals it is no problem (in fact you would prefer that) but if you have a dice (from 1 to 6) than each vertex would use a single texture coordinate for three sides. Just draw an unfolded dice on paper where each edge is connected, but does not cross another edge. It is simply not possible. These complexities are the reason why those procedural mesh functions are so simple. Adding these functionalities would increase complexity of the function and requires you to explain it. On top of that the developers have no idea how you are going to use that function. Maybe you don't want to use the legal texture range [0...1] but [0...3].
Anyway I have decided to take it on and here is the result. You can download the source code here: TorusDX.zip.I have not commented it, but it is pretty straight forward. The texture that I used is from Dilbert.
