Forests, grass and how it can be done

[Ashia]

Hi!

I hope I\'m not just repeating someone else\'s ideas, but here goes:

FORESTS ... (I mean real forests where you can walk between the trees, not that road-which-you-can\'t-get-off-with-something-brown-and-green-on-the-sides) I also mean real trees, big ones, not those tiny potflowers.

GRASS ... If you\'ve ever seen what it looks like when there\'s grass modeled at least like 1 textured poly/clump, you know what I mean!

Why? Because forests are beautiful, a great place for villains to lurk etc. Plus you don\'t want all those hills to be bare, do you?

Now Yliakum is HUGE, forest = MANY trees, one tree = MANY polys, forest = many trees = TOO MANY polys = Gigabytes, Terabytes, Petabytes of HD space. (Not to mention the grass:)

Now this is just a suggestion, I know it can be quite difficult to use this in a game... but the magic word is \'procedural representation\' (do I hear dramatic chords?)

Ok, you can generate quite nice pseudo-random trees, this way you can generate e.g. tons of oaks, each looking a bit different than the other one.

You also don\'t need to remember where each tree is standing... the positions can be also generated on the fly...

In the end, a whole forest can be described mostly by using just e.g. one 32-bit number (random number generator seed)

Now to be able to generate everything in a given location FAST you need to have something like a GIS database index (but it is not stored, but generated on demand) - like a virtual tree.

The same thing applies to the grass, of course.

Oh and of course if the trees and the grass were to move in the wind..

Okay I here the \'but\'s already:
  - might look lame and uniform
  - big load on GPU even with a good LOD
  - it\'s mostly visual, so why care?

Ok I just think it would make the game look MUCH more alive

[zanzibar]

I\'ve suggested this in the past.... I think using a small number of tree models over and over and over again would still look good, especially if they\'re planted at different angles and heights.


But if we have a forest, we have to have sunbeams! :-D  The idea of a permeable forest is great.  You could make the area large, and it would seam much larger than open plains because you can\'t see as far.  It would be easier to get lost or turned around.  There would be plenty of opportunity to plant hidden wells, cabins, crypts, even NPC trainers such as witches, herbalists, and hunters.


Has anyone here played dungeon siege?  That game had some very well done forests.  The problem of course was that travelling through it couldn\'t be done in the 1st person, and also the path you could take was entirely linear.  Plus there was the thing with the trees fading out.

[dragonfire999]

It can be done by having adaptive distance and fog. Thus, you wont notice that the trees dont exist far ahead, because other trees would be blocking the view. The further you went, the same (low) amount of trees being rendered would stay constant

[LigH]

A randomized fractal-like (distorted L-system) tree would be no big problem, technically. Except for those outdated graphic cards like GeForce 2 which don\'t like a high triangle count (and I am one of those poor people who still can\'t afford a FX).

Somehow I liked the technology in \"Gothic\" - dense forest in the distance as one texturized plane, and close forest as single trees.

But to say so: Dense grass was not that big problem in \"Serious Sam - 2nd encounter\" either. And that was dense...
_

In PlaneShift CS, it is more annoying for me that specific OpenGL extensions don\'t work well with my card, therefore sometimes the textures are not correctly transparent for me. Sometimes, transparency makes not only the overlaying texture transparent, but everything down to the \"skybox\". I\'ll provide a screenshot of that effect, if desired.

[Seytra]

It is not possible to do it this way, because it involves a random factor. You cannot generate things randomly. Not if you will cross that area more than once. Also not if, like in an MMORPG, more than just one player crosses that area. You would end up with different clients having totally different randomly generated maps and thus the players cannot use the environment to RP at all. The problem of forests is that every client that is in the area needs to know at each instant where what tree or plant is.

The only way would be to not have random things, but formulas that generate the trees and the map. The exact same trees and map when the exact same (few) parameters are supplied. That way, the clients could generate the maps on the fly and the server would also have a copy, and by simply supplying formula ID and parameter numbers it would be kept in sync. Maybe it wouldn\'t even take longer than loading a pre-made map.

Edit: LigH, this problem appears on other gfx cards as well, but it has been fixed in some places, at least for me, without an update to gfx drivers, so likely it\'s problems of the maps or code.

[LigH]

You misunderstood.

A \"random number generator\" is a function that creates the next value in a numerical order. Each value in that order seems to be random. But if you always start with exactly the same \"seed value\", you will always get exactly the same numerical order starting with this seed value.

Therefore, only one 32-bit value is able to describe a tree uniquely and repeatably.

I even had once an idea for describing a whole planet surface with fractal detail using such a \"subdividing and displacement\" algorithm basing on one seed value.

[DaveG]

Originally posted by LigH
Therefore, only one 32-bit value is able to describe a tree uniquely and repeatably.

Seytra:  He\'s right.  In this case, he\'s exploiting the fact that there\'s really no such thing as \"random\" and an RNG will always output the same results if starting with the same seed.  Normally, you\'d seed an RNG with the time and/or other \"random\" stuff if you really wanted it to be \"random\".

Actually, this might be a good idea.  The only issue would be the potential for wasting processor load when generating the fractals.  Though, if we keep them simple... it could work.  I think this idea has potential.

[Seytra]

When I see \"random\" or \"pseudo-random\", I am aware of the fact that the algorithms aren\'t really random. However, they usually take in a lot of other things besides the simple seed, usually machine state. Probably a finite cascade of randomizing with different seeds including the one provided.

Be it as it may, \"pseudo-random\" to me means the intention to have something random or as random as possible, not something predefined.

Anyway, we agree, then.

[DaveG]

When a new plant is created, it would be given an random ID, 32-bits or so.  This ID would be saved in the db with the item, and would be loaded with it.  This ID would be the only seed into a special RNG to create the plant-life fractals, and because the RNG and seed are fixed, the resulting fractal is as well.  (I have used RNGs with non-random outputs from fixed seeds before.  It does work )  Thus, we\'ve used a simple number to define an entire unique tree.  The math involved would be fairly simple.  The coding to get the thing to actually render... would not be.    And, you wouldn\'t be able to just load the models from files, like you can now.  Without allot of new stuff, this would be a mess.  But, it is something to consider down the road.  

[Seytra]

Originally posted by DaveG
Thus, we\'ve used a simple number to define an entire unique tree.  The math involved would be fairly simple.  The coding to get the thing to actually render... would not be.    And, you wouldn\'t be able to just load the models from files, like you can now.  Without allot of new stuff, this would be a mess.  But, it is something to consider down the road.  

Indeed. This would even make on the fly changes to maps possible, and render large map files / updates almost unnecessary, while adding more variety and more more natural (or a different kind of unnatural) looks to things.

Edit: applying LigHs idea about the planets surface to PS would be a possible solution to the seamless / removal of zoning and the problem induced by flight and swimming: fractal depth could be reduced based on distance, so the need for actual clipping would almost vanish while the distance still resembles the actual map instead of a \"made to look mostly like what it should look like\" texture.

Also, AFAICS, this could more easily be dynamically loaded / rendered since the chunks aren\'t so large. Some screensavers do it, albeit obviously in a very much reduced way.

Edit: Furthermore, this would also facilitate the grass-growing (dynamic environmental change) server.

[LigH]

Just to add a small detail: Natural growing can be simulated by using the \"Fibonacci\" order for segment lengths, which can be calculated easily:

a[0] = 1
a[1] = 2
a[n] = a[n-2] + a[n-1]

This results in: 1, 2, 3, 5, 8, 13, 21 ...

[Ashia]

Wow!

I didn\'t think someone would actually take me seriously. ( But seriously now

LigH > Yes I think I heard something about using the Fibbonaci sequence... anyway I think there are quite many possibilities how to do that, I myself would try probabilistic context-free grammars... and build the tree along the structure of the derivation tree.

Yes and thanks for your comment on the random number generator! The correct name indeed is pseudo-random number generator.

To specify it more precisely: It generates a number sequence that is determined by the random number seed. Simple PRNG:

static unsigned seed;

/* set the random number seed */
void srand(unsigned init_seed) {
  seed = init_seed;
}

/* generate a random number 0..2^32-1 (if unsigned is 32-bit) */
unsigned rand(void) {
   seed = seed*CONST1+CONST2;
   return seed;
}

where CONST1 and CONST2 are wisely chosen numbers, typically big prime numbers. Now this is not a very good generator, but it works as an example.


Now about a simple example of how to generate the random number seeds for the trees efficiently:

Imagine dividing the whole surface by a grid (like parallels and equators) creating squares of say 50x50 meters. - or whatever, but the number of trees in one square does not exceed say 100.

The i-th tree (i=0..99) in the j-th square will have a random number seed Tj. Now we don\'t need to remember those and store them on the disk!

Let\'s say we are in the forest in the j-th square. We will call the seed for this square S(j). To get Tj[0]..Tj[99] simply do:

  srand(S(j));
  for(i=0;j<100;++i)
    Tj = rand();

Ok now we only have to remember one number for each square.. getting better...

Now let\'s build another level on top of those squares! On level 1 each square will consist of 10x10 level-0 squares ... 100 in total. Let the seed of j-th square on level k be called Sk(j). Ok so far? Now we just continue the process until we are left with but one square at the n-th level - the root (because we created a tree). (It\'s like a giant pyramid, actually).

Now to generate the seeds of nodes (squares) on the k-th level corresponding to a square on the level above, we do almost the same:

  srand(Sk+1(j));
  i0 = index_of_first_child_square(j);
  for(i=0;j<100;++i)
    Sk[i0+i] = rand();


Right now let\'s say we know a single number S = Sn(0) - seed value of the root. Let\'s say we are on some spot in the forest and we need to draw the surrounding trees.

What we do is that we descend from the root to the square where we are located and generate the seeds as needed.

Having n levels we would need to calculate in this case at most n*100 pseudo-random numbers (100 on each level). Keep in mind though that n is a very small number, because each level means 10x the length of square sides. Thus we will probably end having some 4-5 levels.

So it\'s quite fast. Moreover you typically don\'t move very fast so you can keep calculated values for later use.


Whoa... this was of course just an example - but I think it illustrates the basic idea.

Sorry programmers for boring you with obvious thins
Sorry others for boring you with uncomprehensible computer-science mumbo-jumbo

[Nikodemus]

Originally posted by LigH
Just to add a small detail: Natural growing can be simulated by using the \"Fibonacci\" order for segment lengths, which can be calculated easily:

a[0] = 1
a[1] = 2
a[n] = a[n-2] + a[n-1]

This results in: 1, 2, 3, 5, 8, 13, 21 ...

Actually you are wrong =P about the \"Fibonacci\" order
a[0] = 0
a[1] = 1
a[2] = 1
a[n] = a[n-2] + a[n-1]

so.... 0,1,1,2,3,5,8 ...

[DaveG]

Honestly, you guys are just confusing everyone else who reads this thread.    And, you don\'t need to explain the math to me, I\'ve done more complicated stuff before.  

However, as I said, it\'s not the math or programing, but the rendering that\'s the issue.  And, by rendering I wasn\'t referring to just displaying the polygons, but making a program to display them in the first place.  We would have to write that from scratch in all likelihood.  Everything before and after that is easy.

In addition to the seed/ID, the tree would also have a small designation representing the styles of leaves/bark and of size, stored in the db with it.  That would allow for different species.

If you really wanted to get fancy, you could have all trees spawn seeds in both the plant and RNG sense.  The seeds of trees would have seeds/IDs similar (as in producing similar fractals) to their parents, thus you could actually have a form of tree genetic material without much additional effort.

[Neryam]

This sounds awesome
So if you can get it to work..

I do agree with everything here, and it would definitely be cool to have those \"random\" fractual trees so you can actually walk in the forests..

And while we\'re at it, it would be cool in maps were all square and \"portals\" would be vertical planes, not lines. So we could walk anywhere and not fall off the world. We\'d need that to bring actual forests to their full potential, as well as plains and stuff..