Hi everybody

[socram8888]

• Name: Marcos Vives Del Sol, also know as "socram8888"
• Social: https://github.com/socram8888 and https://twitter.com/socram8888
• From: I am from Valencia, Spain
• Skills / Tools: I know a dozen of languages, ranging from JavaScript to Microchip assembly (and yes, I've also coded in brainf*ck), but the ones I prefer, and therefore tend to use more, are Java, for full-fledged programs and Bukkit plugins, mostly because of its crystal-clear syntax and lack of those damn headers of C++; and PHP, actually not for web development, but as a quick prototyping language. I use Notepad++, a simple text editor for Windows, and Maven as the compiler frontend for Java.
• Found via: I heard about Terasology when I were looking for Minecraft alternatives, and this was the one I liked more because of its higher quality graphics and great terrain generator.
• Interests: I still have to get a bit more used to Terasology, so I can't really say were I am going to focus the development. Well, actually I would like to work more on terrain generation. Maybe adding some new trees, large sequoias I think would be awesome.

 

[Skaldarnar]

Heya and welcome!

We had some terrain generation progress before Nym Traveel had to pull back. Maybe you can catch up with his climate simulation approach. I think Marcin Sciesinski has tinkered with tree generation...

Just to give some starting points

 

[Cervator]

Hey socram8888 welcome to the forum!

Yep, plenty of space in terrain generation. Would love more tree variety. Next up: World badge

Let us know any time if you have questions

 

[socram8888]

Hmm, I would like to modify a bit the tree generator, removing the depth counter and maximum depth, making the probability linear. Therefore trees would be more variated, relying on the probability value only to stop recursion. This will also add small probabilities of creating extralarge or miniature trees.

I would also like to move the LSystemRule to the generator package, and add to it modifiers for trunk size (fat, like the ones generated now, and narrow ones, for axial branches in tall trees, for example) and leaves (allowing the generator to create branches without leaves)

I've tried to add sequoias but the trunk is way too fat to create the axial branches that these kind of trees have, and I need these branches to have no leaves at the start.

By having these modifiers I could make trees have variable height, by using a rule like:
rules.put('A', new TreeGeneratorRule("FFFA", 0.8f, TreeGeneratorRule.LeaveType.NONE));
Because of the randomness, some trees may recurse very few times, creating short trees, or recurse a lot of times, creating very tall trees.

If you like the idea I'll start coding it tomorrow

 

[Cervator]

Is the question modifying what we've got, or making more generators? I figure we'd want to keep the current trees as one type, then make others as well, like sequoias, placing different types in different biomes. Would all that fit in the same system / same generator? I get the feeling L-Systems alone cannot generate every type - but then I'm not very knowledgeable on the topic.

On top of that there's the all-at-once vs over-time tree generation. Separate systems? Merged together somehow? Marcin Sciesinski might have some ideas on the topic.

I'd say go ahead and see what you can do, more trees are good trees, but I wonder what the long-term architecture of tree generation would be like

 

[socram8888]

I would like to modify the current tree generation system. Making trees look a bit different, because I've noticed that most trees only have minor variations. By removing the depth counter, we could make trees have variable height (right now this is not possible, as each child axioms must have leaves, so they are different from the trunk)

I think it's better to use a single tree generator, and MarcinSc's is the one that looks more promising. Nevertheless I think his uses L-Systems, doesn't it? So current tree rules could be reused on his tree generator.

 

[Cervator]

Best of both worlds would be great - go forth and do great things

 

[socram8888]

Hi again. I've already figured out a way to add more diverse trees, without losing the current ones. How? Well, here are two modifications to the tree generator that can do this:

First of all: variable iterations. When creating a new L-system tree generator, you have to specify two values for the iteration count instead of one: a maximum and a minimum. When this generator creates a new tree, it has a probability of 90% to create one using the average of the min and max, a normal one. And what happens with the remaining 10%? Well, those will have a random iteration count, ranging from the minimum to the maximum.

Here's a graph that depicts what my modification does:

The second one is a per-axiom configuration of leaves and trunk radius. In the current generator, only the first axiom (the initial one) can have no leaves. This modifications allows me not only to disable the generation of the leaves or the trunk, but also to set its radius to a random value. Here's an example picture with leaves radius set to 3+sqrt(2):

You can see the modification here:
https://github.com/socram8888/Terasology/commit/abb66574fc7fc15eb67e07d553349c9d736a8e20

I've not implemented yet the variable trunk radius generator.

 

[Cervator]

Looks and sounds cool

Won't that end up on average just scattering an occasional odd tree here and there? That's nice for variety, although we still need to expand into outright tree species where they all differ as a group

 

[socram8888]

Well, I can modify the function to remove the probability of randomness and make all of them have a random iteration count, so there would not be any "normal" tree. From:

        int iterations;
       if (minIterations == maxIterations) {
            iterations = minIterations;
        } else {
            float itRand = rand.randomFloat();
            if (itRand < 0f) itRand = -itRand;
            if (itRand < ABNORMAL_PROBABILITY) {
                iterations = minIterations + (int) (itRand * (1f / ABNORMAL_PROBABILITY) * (float) (maxIterations - minIterations));
            } else {
                iterations = (minIterations + maxIterations) / 2;
            }
        }

to just:

        int iterations = minIterations + (int) (rand.randomFloat() * (maxIterations - minIterations));

This one will look like:

But the good thing about that small 10% probability is that it would allow the generator to create superlarge trees, as in real life there are actually superlarge trees.

Maybe modifying it to:

using a second grade polynomic equation, so there wouldn't be any supersmall trees, but there would be superlarge trees. This is probably the one I like more.

 

[Skaldarnar]

Can't you just feed the tree generator with different L-systems?
Thus, there would be a slight variation for a specific type of tree, and the biome generator can instantiate the tree generator with different tree types.
Having different generators for the interpolation methods would still allow to suit all of it to your needs.

 

[Cervator]

Yep, that's what I was getting at too

I love the variety options and it would be cool to have the occasional "mutant" within one species, but wantie MOAR SPECIES too

 

[socram8888]

Can't you just feed the tree generator with different L-systems?
Thus, there would be a slight variation for a specific type of tree, and the biome generator can instantiate the tree generator with different tree types.
Having different generators for the interpolation methods would still allow to suit all of it to your needs.

L-Systems here in Terasology have a probability float whose finality is to let the generator create random trees. My goal is to make that ratio to actually have an effect. I don't want to code a thousands of different trees (for a same species), I want Terasology to be able to create those for me!

Right now, because of the fixed iteration and the formulae to weight the probability (which I coded to mimick the old non-recursive generator, but actually I don't like it anyhow), nearly every tree looks the same, except for one or two different blocks. And also creating some trees isn't possible right now, as with the current generator there is no way to make child branches to have no leaves. Sequoias for instance, the tree I wanted to implement, have leaves only at the tip of each branch:

Creating something that looks remotely simmilar to this is not possible right now.

 

[Cervator]

Wow that is a great picture

I'd think another trick there is doing a tree with that level of detail with what's essentially cubic meter blocks.

Have thought about using a limited amount of shaped blocks to make thinner branches, but not sure how that would look or how much it would add.

Anyway - keep up the good work, looking forward to what you figure out!

 

[socram8888]

Can somebody compile and try this code? It's a custom power function I've written. In my setup (Intel i5 2320 with Windows 7 x64 and Java 7 x64), this yields:

Math.pow: 23438251 (234,38251 ns/it)
naive pow: 2423809 (24.23 ns/it)
optimized pow: 1510733 (15.10 ns/it)

Which IMO is a substantial perfomance gain (20x) over the current Math.pow used in several terrain generation methods. There's one drawback, tough, and that is that it won't accept a non-integer exponent, but we can still use Math.pow for these.

// Marcos Vives Del Sol - 11/X/2013
// License: WTFPL
 
public class powtest {
    public static double naivePow(double base, int exp) {
        if (exp <= 0) return 1D;
        double temp = base;
        while (--exp > 0) {
            base *= temp;
        };
        return base;
    };
 
public static double pow(double base, int exp) {
if (exp <= 0) {
if (exp < 0) {
base = 1D / base;
exp = -exp;
} else {
// 0^0 is indeterminate (NaN)
return (base == 0 ? Double.NaN : 1D);
};
};
double temp = base;
exp--;
while (true) {
if ((exp & 1) != 0) {
base *= temp;
};
exp >>= 1;
if (exp <= 0) break;
temp *= temp;
};
return base;
};
 
    public static void main(String[] args) {
        final int it = 100000;
        final double base = 2D;
        final int exp = 24;
        final double expD = (double) exp;
 
        long t1 = System.nanoTime();
        for (int i = 0; i < it; i++) {
            Math.pow(base, expD);
        }
        t1 = System.nanoTime() - t1;
 
        long t2 = System.nanoTime();
        for (int i = 0; i < it; i++) {
            naivePow(base, exp);
        }
        t2 = System.nanoTime() - t2;
 
        long t3 = System.nanoTime();
        for (int i = 0; i < it; i++) {
            pow(base, exp);
        }
        t3 = System.nanoTime() - t3;
 
        System.out.println("    Math.pow: " + t1);
        System.out.println("    naive pow: " + t2);
        System.out.println("optimized pow: " + t3);
    };
};

Full code is here: https://gist.github.com/socram8888/6926452

 

[Immortius]

A couple of things.

One is you need to "warm up" Java before measuring performance. This is because java will dynamically recompile and optimize code that is used heavily. So you should run a number of iterations before you start measuring.
Secondly your number of iterations is too small, at least one my i7 machine. Initially I reverse the order of the tests and the naive implementation came out on top, but after addressing those two issues it is a lot clearer:

    Math.pow: 1795066524
    naive pow: 122303010
optimized pow: 57139739

Math.pow loses, but that is obvious when you are only handling positive integer powers.
Would be good to have some specific tests around exp == 2 is, as it is generally the most common case. I expect the result is the same. Also need some unit tests showing the results are the correct, specifically around the edge scenarios like exp == 0, -1, 1, 2, and base == -1, 0, 1, 2 (for some of those cases you might need to hand over to Math.pow).

Ideally we would then add it to TeraMath as pow(float, int) and pow(double, int), and sit it along side a pow(float, double) and pow(double, double) that map to Math.pow().

Style-wise I would have some complaints, but I assume you're just prototyping. I would point out that there is no need to have D at the end of doubles though. If you want to be clear, include a .0 at the end, but otherwise all floating point numbers in Java are doubles unless a trailing f is included. Checkstyle complains about modifying function parameters, but we probably can turn that off for TeraMath.

 

[socram8888]

Actually I'm also handling negative integers (which is only a simple inversion beforehand)

About the code, you mean complainments about how the code looks, or about the code itself?

 

[Immortius]

Yeah, just the looks. Trivial stuff like braces for if statements and and class names starting in capitals and so forth. For Terasology we follow the Sun style and use CheckStyle to check for violations - this integrates with your IDE or can be run using gradle.

(I tend to get up in arms about braces in particular because on a few occasions I've had to track down difficult to spot issues caused by them being missing.)

 

[socram8888]

I use braces always but for increments or decrements ("var++" or "var--"), "break" and "continue", mostly because they're quite small and they're hardly ever modified. For function calls and more complex operations, even when they only take a single line, I encase them in braces too.

I put the class name because I were as you guessed just prototyping, the Gist code has a proper name (and identation): https://gist.github.com/socram8888/6926452

The code is a bit messy (like using "(exp & 1) != 0" instead of the more clear "(exp & 1) == 1") because I tried to achieve the smallest and fastest bytecode.

 

[Cervator]

Cool stuff - math wizardry!

You already got the architectural feedback, so that's good. The style of brackets everywhere is also good for consistency and ease of configuration for code analysis tools like Checkstyle. A few places you might be able to make a reasoned argument for lack of braces to improve readability, but try to convince Checkstyle config to not report on that without getting really hacky config ...