Project Frontier #9: Happy Little Trees

By Shamus Posted Monday Jun 27, 2011

Filed under: Programming 144 comments

frontier9_bob_ross.jpg

With apologies to the late Bob Ross. His work has been widely criticized, but this project shares a certain kinship with his work: We’re not trying to make Great Art, we’re trying to make “Pretty Good Art” in 10% of the time. I imagine that if paintings could somehow cost as much to produce as videogames, the “Bob Ross method” would be the only way to get anything done.

Hopefully my tree-making skills are better than my photoshopping skills.

Minecraft has proven that a large number of people are capable of accepting a stack of one-meter cubes as a tree, both visually and as a gameplay conceit. Perhaps even a majority of the people are capable of embracing this sort of abstraction. I imagine there are people who are not like this. There are those who look at Minecraft and scoff, who refuse to enter a world of such low fidelity. I am not interested in attempting to entertain those people. I don’t think I can. It’s too expensive. I’ll leave them in the hands of id Software and Crytek.

For those who can look at a pile of blocks and see the the emergent cubic beauty, I hope to create something a bit different. Not cubic, but… chunky. Low poly, colorful, vibrant, and varied. Somewhere between Minecraft and World of Warcraft in its first years.

Now, there are a LOT of techniques for making trees out there. Check out this one, which does complex maths on… geeze. I duuno. There’s a lot going on there. The point is, if those trees are under 10k polygons I’ll eat my mouse. Still, there is a lot to think about in that post. (And some of the other things people have linked. Thanks.)

I actually wrote a tree generator way back in the last few months of 2000. Like a lot of the experimental work I did for my employer at the time, it was met with polite admiration, followed by indifference. “That’s really cool, Shamus. Seriously. Nice work there. But it is completely useless to us. Thanks anyway, though.”

The source for it is long gone, but I still have most of the concepts in my head. That tree builder accepted three pieces of information:

  1. Properties: This was a huge list of fiddly little details like: How tall is the (fully grown) tree overall? How far between the roots and the lowest branch? How many branches overall? How straight is the trunk? How wide is it? What colors are the bark, and the leaves? How much do the branches lift or sag from their origin?

    And so on. This list of properties could be thought of as the template for the species as a whole.

  2. Seed: Not “seed” as in “plant seed” but “seed” as in “random number seed”. (Although the two concepts overlapped here in a way that greatly amused me.) Basically, change the seed and you’ll change a bunch of numbers like the shape of the bending and the branch positioning. Create two trees with the same properties but with different seeds, and they’ll look like two different trees of the same species.
  3. Age: On a scale of 0.0 to 1.0, how close is the tree to full grown? You could manipulate this number to smoothly grow a plant from sprout to full-grown. Very slick.

Now, the “smooth growing” thing added a lot of complexity. I don’t think I’m going to need that here, so I’m going to leave that out for now.

My polygon budget in 2000 was somewhere between 50 and 100 polygons. Now, given the massive increase in computing power since 2000, I’m sure trees today are many times heavier than that. I wouldn’t be surprised to find out the average Crysis tree clocks in at 1,000 triangles.

However, I need a lot of trees. Most games are focused on delivering a highly polished, high-detail scene of very limited size. I’m aiming at lower platforms AND trying to extend the view distance at the same time, which is like trying to make a car that burns less fuel and goes faster. This is usually an either / or arrangement. If you’re making gains in both of these areas, odds are you’re making big sacrifices elsewhere.

The thing about view distance is that it gets ridiculously expensive to make even small increases, because it’s based on area. If you have a view distance of 100 meters, that means you actually need a 200×200 meter area of viewable stuff, with the player at the center. (Unless you can persuade the player to never turn around. Let me know how that works out.) That’s 40,000 square meters. Now let’s say you want to increase your view distance to 150 meters. That means you need an area of 300×300 meters, for a grand total of 90,000 square meters. A 50% increase in view distance resulted in a 125% increase in resources. I don’t care how much computing horsepower you throw at a problem, sooner or later those numbers will kill you.

While a lot of games sprinkle a few trees at the edges of the map and call it a day, I might have hundreds of them in view at once, so I can’t afford to spend too much on them. I think 200-300 polygons is a good starting point.

So my trees are dead simple: When a new map is generated, it creates a selection of trees for various climates. It actually makes a table of them. One axis of the table is for moisture, the other for temperature. So, once the climate is decided for a region, it looks up in the table for the most appropriate tree. Here is an example map:

The grey circles are mountains, the blue circles are “lakes”.  The light squares are plains. I’ll be showing these off in a later post.  For now, just note the climate.  The coloring tells us that the arctic climate is to the south, and the tropic climate is to the north.  The land gets drier (more brown and yellow) as you go east, which means the wind is from the west.
The grey circles are mountains, the blue circles are “lakes”. The light squares are plains. I’ll be showing these off in a later post. For now, just note the climate. The coloring tells us that the arctic climate is to the south, and the tropic climate is to the north. The land gets drier (more brown and yellow) as you go east, which means the wind is from the west.

For development, I’m using a 5×5 table of trees. (5 different moisture settings, times 5 different temperature settings, for a total of 25 different trees. Er, actually, 24. “Tree zero” is for areas with minimum moisture and minimum temperature, and means “no tree at all”. We can argu about whether or not that should count as a “type of tree”, but that’s a problem for a philosopher, not a programmer.)

Here I’ve given each tree a random unique color. Areas with the same color will have the same tree type:

frontier9_2.jpg

If I up the tree grid to 10×10, I’ll have 100 species of trees. It end up looking like this:

frontier9_3.jpg

I like the complex shapes I’m seeing here. That’s not random. That’s emergent, based on the cheapo climate simulation I outlined before.

You might be worried that these hard lines will look odd, “You mean you’re walking along and suddenly you come to an invisible line and all the trees are different?” But the trees use the same scattering code that I used on the grass back in part 3, so the change is not instant. It’s staggered enough to hide the boundaries, at least.

The trees draw their foliage color from the same palette as the grass. So, tropical trees will be deep greens, and desert trees will be pale greens and yellows. Trees in cold climates will have a bit of blue in them. Similarly, the bark color draws from the dirt palette. Note that I’m not forcing the tress to always match the grass. I’m just drawing from the same palette. This means trees will still stand out, but the two together will still look like a good thematic match.

frontier9_4.jpg

Next time I’ll actually get down to talking about how the trees are constructed.

 


From The Archives:
 

144 thoughts on “Project Frontier #9: Happy Little Trees

  1. TheAngryMongoose says:

    When I saw that picture it took me a few seconds to realise it wasn’t Dun Morogh. I only realised when I started thinking about WHERE in Dun Morogh it was.

    1. kmc says:

      I had the same reaction! It was pretty striking when I realized.

    2. Museli says:

      It was the last pic that felt really ‘WoW-like’ to me, but going back to the first, I totally see your point. I haven’t thought much about WoW in ages, but these pics make me miss it a little. Keep up the great work, Shamus.

    3. Pickly says:

      A fourth person here who noticed this. I was thinking a combination of “Strange how similar these graphics are to WoW” (Without knowing for sure they were Shamus’s), and “Where in WoW was this?”.

  2. Hal says:

    Very neat looking. I’m assuming you’ll handle why the trees look so conical next time. I’m just curious if it’s a design decision or something of a convenience. As in, “The next best thing would take 2 months to do right and eat all the memory for other features, so conical trees it is.”

    1. BenD says:

      I love the conical trees. It makes me think this planet has a higher gravity than ours.

  3. DanMan says:

    Not only does the “Bob Ross method” take less time, it allows people who are unable to spend years and years practicing to at least get a bit of experience painting.

    I understand your earlier post about keeping the source code, and I still stand by your decision, but it’s engines like these that allow people who are more temperately interested in programming to get into the practice. I’ve been programming professionaly for 6 years and I know I couldn’t get close to doing what AAA games do (because I have very little experience in 3D graphics).

    This little proof of concept could not only prove that companies can make games with less effort on their part, but create a gateway into making games for the less experienced.

    1. theLameBrain says:

      I watched a bunch of Bob Ross when I was a kid, but I do not know what the “Bob Ross method” is… Is that a real thing?

      Also Bob Ross wasn’t a great artist? I always thought of him as being a great artist… of course I was like, 7…

    2. Gndwyn says:

      I’ve done a couple Bob Ross paintings. They are to painting what Guitar Hero is to playing a musical instrument. I’ll not apologize for having fun with either one, but I also don’t claim to be a painter.

      1. krellen says:

        Bob Ross is fast-food painting; quick, cheap, easy, and accessible to the masses. Like fast-food, such things have a place in society.

      2. Dan says:

        I agree. That’s a very good analogy with Guitar Hero (and below with fast food). A point is that while Guitar Hero is not playing guitar, it is rhythm and “chords”. Being an expert in Guitar Hero will not make you a great guitarist, but take two people (with the same natural talent) and have one get good on Guitar Hero and the other do nothing. Then teach each of them to play the guitar. I think that the Guitar Hero person will have an easier time of it.

        I also agree that with the Bob Ross method, you’ll develop some bad habits that you will need to unlearn in order to progress as a good artist.

        1. Will says:

          You develop bad habits that you need to unlearn whenever you’re taught anything. Often in University courses the first thing you do is unlearn all the stuff you’ve previously learned that is wrong. And then they teach you a bunch of new stuff which is less wrong, but which you need to understand so you can learn the next set of stuff, which is less wrong again, and so on.

          1. Soylent Dave says:

            My very first Chemistry lecture began “PV does not equal nRT”

            I was most upset.

            1. Tengokujin says:

              Only for real gases!
              Ideal gas law still works for ideal gases (i.e., none of them).

  4. kikito says:

    I realized I hadn’t said this yet: I’m so glad you are doing this.

    I initially got to this forum via your procedural city project.

    I stuck around because of the thoughtful opinions and amusing prose. But I always longed for more procedural stuff (a little bit).

    All I can say is, thanks for taking the time to write this series, and keep them coming!

    1. kanodin says:

      I’m gonna take this rare opportunity where there aren’t 100 comments by the time I’ve read it to add my praise to this project, it really is amazing.

      1. Nick Bell says:

        In an effort to make sure this hits 100, I’d join the chorus. The explanations of the process are as interesting to me as the end product. These posts let me feel like part of the project, without having to do any of the work. Win!

        1. Reet says:

          Yay, more project frontier! I started reading this on a whim one day mainly because I didn’t have much to do. I have to say that I am now really enjoying it. It’s great to see this project being put together in this unique way. I’m looking forward to the next update.

          1. porschecm2 says:

            Ditto all of the comments in the thread above this. I enjoy a lot of the posts you make, but the procedural stuff is by far the most fascinating.
            Now we just need to convince more game creators to use procedural content. I want more games with vast huge open areas.

      2. Deoxy says:

        Ditto. As great as it is for Shamus to have a larger following (well, I hope it’s great, anyway), I really miss having comment threads small enough to meaningfully participate in.

        Of course, as much as I enjoy his stuff (on many topics) it would be selfish to keep the group small.

    2. Blake says:

      I thought I’d just add in a ‘these are my favourite kinds of posts’ post as well.
      Seemed like the place to do it.
      Trees in the last screenshot look good, look forward to seeing more of them.

  5. mac says:

    That parting picture is lovely. The conical foliage on the trees looks a bit wrong, but ignoring the nearby clump of trees the effect is of a wonderful, slightly alien, landscape.

    1. decius says:

      The straight lines on the foliage tweak me a bit; is there a way to make the edges appear less straight without adding polygons? Could you cheaply alter the texture or transparency near the edges to cut off the edges?

  6. scowdich says:

    Very impressive! I look forward to seeing how you’re handling mountains, lakes and plains. I’ll admit to being a bit concerned by your lake model – one of them seems to intersect with a river, but I guess if it’s a problem at ground level it can be fixed easily enough.
    I kind of like the surreal look you’ve got in that final picture, and think I understand why you’re using cones for the tree trunks instead of cylinders.
    With a cone, the tree can be generated in a handful of recursive steps – place trunk, stick a few boughs on top (with a random vertical displacement), stick a few branches on each bough as though it were a trunk, apply leaves to the ends of those. If the trunk were cylindrical, it’d require a few more lines of code, and wouldn’t mesh very well with the branch polytopes – there would be odd shapes generated at the apex of the trunk.
    I hope one of the tree species is “Deku”.

    1. Chargone says:

      i’d be more worried about the lakes that Didn’t intersect with rivers, personally.

      1. aldowyn says:

        There’s both. Some lakes are completely landlocked, and are fed by rain runoff and/or underground springs. Others are fed by rivers, but they usually don’t have rivers leading out of them. And then there’s the ones like the ones we have here in Oklahoma, which are just fat sections of rivers that have been dammed >.>

        1. Gndwyn says:

          If he has a river leading out of a lake, he just needs to add a procedurally-generated beaver dam at the juncture.

          1. BenD says:

            I want procedurally-generated beavers, too!

            1. Alexander The 1st says:

              In my mind, Beavers are close to moles, at least in some properties.

              So now I’m imagining procerdurally-generated whack-a-mole minigames at the lakes. <_<

        2. BenD says:

          Er, many natural lakes have both inlets and outlets. Some have only outlets (fed by snowmelt/rain, but with outlets) or the inlets are hidden (springs beneath the lake). Mountainous country produces all of the above. XD

          1. Yonder says:

            I’m not a… terrainatologist, but from what I have read I believe that the vast majority of fresh water lakes have outlets, and nearly all salt water lakes do not have outlets. The lack of outlets cause the salinity, as all of the salinity that rivers and other water runoff seeps out of the surrounding ground collects in the lake with no escape.

            However I think that salt water lakes tend to be larger as well, right? Perhaps smaller lakes with no outlets do not get enough runoff to be pushed that far out of equilibrium with their surroundings.

  7. The Schwarz says:

    Definitely impressive, but if you’re going for variety, isn’t it kinda odd to have exactly 1 species of trees in an entire region? Even in the more varied map above, you can walk for miles and encounter only one type of trees…

    1. Nick Bell says:

      Pure conjuncture, but I would guess that diversification comes after this initial step. Once trees are programmed to properly populated by climate, then the table is updated to have multiple kinds of trees per climate. That will break up the monotony within climates.

      1. jwwzeke says:

        I was thinking the same. The eventual table could even return a “set” of available trees for that region. Could go a step further and have the “set of trees” for an area broken down by percentages. So one area (based on moisture and temperature) has 4 types of available trees, but one of them is dominant and is 85% likely, while the other three fight over the other 15%. Allows for forests that are mostly one or two types of trees, but with those nice little odd other-types spotted throughout.

        Course all of that requires more steps each time you want to generate a tree… so whether it’s worth it or not?

        Leads to a question though… Shamus, are you planning on widespread areas of dense tree placements (i.e. big forests)? Would love to see what those stylized trees of yours look like covering a hillside or similar.

        As always, this world of yours looks incredible. And on that note, you should produce a bunch of high resolution (1680×1050) screenshots for all your followers to use as desktop backgrounds. All the best games are doing it for building hype. :)

        Also, are you taking preorders for this yet? Heck, if you add a little code to have this thing generate a world and just present the view from random locations and elevations I’d buy this as a screensaver right now.

        1. jwwzeke says:

          Late EDIT: Guess I should learn to read the rest of the comments before posting. Screenshots and forest are both mentioned below. Sigh.

  8. Naota says:

    “While a lot of games sprinkle a few trees at the edges of the map and call it a day, I might have hundreds of them in view at once, so I can't afford to spend too much on them. I think 200-300 polygons is a good starting point.”

    This is probably immediately obvious and may in fact make me look silly for pointing it out, but are you planning on using different level of detail models for your trees when rendered at certain distances? Generally you can step down these 200-300 poly trees to cheaper 100ish poly ones at a fair distance, all the way down to something like 4-8 poly billboards at the edge of the horizon and the player won’t notice a difference because the model is a mere ten pixels high on their screen.

    Even for whimsical retro-style foliage, I imagine a few LOD’s for these trees would net you quite a bit of a extra processing power to use for other things.

    1. MrPyro says:

      Yeah, if it’s possible having the trees generated at a few levels of detail would probably help rendering.

      A very long time ago I had to implement an algorithm that did a pretty good job of this; it calculated the least significant… can’t remember if it was vertex or line, removed it, and then recalculated the other points to try to keep the shape as close to as it was before as possible. Can’t remember many details as I did it in one night in lieu of sleeping; stupid deadlines.

      The main issue you can run into with this is when to change the model; I remember playing a game called Summoner on the PS2; in one of the stealth sections you spent a lot of time watching soldiers patrol the corridors, and the jump between models was pretty obvious.

      1. Deoxy says:

        the jump between models was pretty obvious.

        This is the problem I have with the “fewer polys at greater distance” method – the change as you get closer never seems to be smooth. The switch always registers to my eye as “movement”, which makes me notice it, and it looks like crap.

        1. X2-Eliah says:

          That’s usually the case where the change distance is set to be too close. Ideally it should change at a point where the only thing noticeable is maybe slight pixel flickering along the silhouette or so, but too many games do the model changes far too late, so you see actual geometry swaps.

        2. Piflik says:

          Well…usually you would replace them by making the low res one progressively more transparent, and the high res one more opaque. That minimizes the impact of the switch. One thing to consider is however, that you would have to draw both versions at the same time during the switch, which means that you have to do the switch closer to the player than with an instant switch.

          But draw distance without LODs is unthinkable as of now and will probably be for years to come. There really is no other method.

        3. Avpix says:

          Whenever I notice this happening in a game it reminds me of the part in Terry Pratchet’s The Wee Free Men where nothing looks quite right in the witch’s world.

          1. Will says:

            I vaguely remember playing a game which did exactly that. I don’t remember the specifics, but you spent some time in a dream world or something and one of the changes they made for that section was to make the environment stuff have a lot more LODs and scale them far more often.

            The end result was that you could actually see that objects literally just got more detailed and complex the closer you were to them, which was a beautiful and stark alien contrast to the ‘normal’ world and looked brilliant in context.

        4. Naota says:

          I think this is sort of a false impression, as LOD’s aren’t so much a method as they are a standard of any 3D application that allows free movement in an environment and has to render a lot of polygons. It’s a technique used in just about every game, but you only notice them when they’re done badly, which is why it “never” appears to be smooth.

          If you can tell LOD’s are there because they stand out or draw your attention, they’re just bad LOD’s with too near a distance.

    2. StranaMente says:

      Just cause 2 uses this method, I noticed only realtively later in the game, as it only become clearer with planes and high velocity low height flight. There’s a sphere around the player and trees are always with the front to the player. It’s neat and solves many memory problems. As your player will (probably) be always on foot and walk at a certain speed you could do this too.

  9. Shamus that last image is so alien and yet so beautiful.
    I’d dare to call that image art.
    Like the awesome wall posters you can buy, made by some artists.

    Could you make that one (and a few others?) without the stats/info text,
    and in common wallpaper resolutions?
    I think many here would love having those as wallpaper or wallpaper slideshows.

    1. MDCore says:

      Yes, wallpapers please!

  10. Mystyk says:

    It sounds like your previous tree system was a custom variant of an L-system. Your new system seems similar, but like you’ve lumped the parameters into discrete groups (24+1 for the 5×5, 99+1 for the 10×10) rather than defining them individually. This could actually benefit you more than you realize, as L-trees can be coded to refine themselves based upon proximity, attaining near realism at close range while reducing to nearly nothing at farther ranges. (This also works wonders with grasses and shrubs, and provides the necessary consistency for revisits so the scene stays appropriate.)

    1. Zukhramm says:

      I do not see how you can make that prediction having heard absolutely nothing regarding the actual generation of trees.

      1. Mystyk says:

        It was an educated guess based upon my own experiences and the description he gave. In the case of this project, I appear to have guessed incorrectly (based on the details mentioned in “Project Frontier #10”) but I still think the earlier one he described fits the bill well.

  11. Otakun says:

    i see the trees! but not quite any forests. Hoping you have at least one somewhere, eventually – a proper forest is something even Azeroth lacks (trees are either singletons or gigantic. you’re never really running around in Mirkwood – even in Duskwood.)

    1. aldowyn says:

      I’m pretty sure Tolkienesque forests tended to be BOTH – crowded and gigantic. Or maybe that’s just Jackson’s interpretation.

      And WOW, there are a lot of forests in LotR. The Old Forest back in the Shire, Mirkwood, Lothlorien, and Fangorn… :D

      Of course, there’s also half a dozen or better mountain ranges in that not-so-huge area

      1. krellen says:

        At one point, the planet’s landmass was 90% covered in trees. Even as recently as the Medieval period it was still upwards of that much – humanity has done a lot of thinning out of tree populations, much of it recently. So it would make sense for there to be massive sprawling forests in a mythical, pre-historic era such as Middle Earth.

        1. Soylent Dave says:

          Particularly as Tolkien was writing an English mythology, and almost the entirety of southern Britain was forest before we chopped them all down and built farms.

    2. Ian says:

      I think the lack of proper forests in WoW is more of a gameplay feature than anything else. I have enough trouble steering my tauren toons through Stranglethorn and Ashenvale without having even more trees for the camera to clip through. :x It doesn’t help that I’m used to having the camera zoomed waaaaaaaay out from when I raided all the time.

      Given that this project is all first-person, it’s going to be much easier to traverse a dense forest without issues. Issues will crop up if trees are too close together, but that’s about it outside of possible framerate issues.

      1. Otakun says:

        fair enough, though if they kept teh canopy a little high, then they could probably minimize camera interference in follow-above mode. Would be great to see a dense forest area with space between trees at least one mounted toon’s width between them. There are areas in Ashenvale that came close, but very limited in scope (or at least, there were, pre Cata. Havent been back since…)

        1. Sumanai says:

          Couple that with the trick of making trees see-through (except for the stump) if they’re in-between the camera and player character, and I think it should be playable.

  12. X2-Eliah says:

    Nice. Um. Erm. Are you planning to handle tree-sized mushrooms too? (like from morrowind). Or any other kind of growth besides trees/grass?

    Also, this already looks like something that’d be fun to explore. Real crying shame there’s no underground tunnel-system, if that was deterministic and based on the overworld, it’d be just amazing.

  13. James says:

    Small nitpick, it’s only a 125% increase in resources. This is super impressive though.

    1. Shamus says:

      Of course. It’s 225% of what it was before, but only 125% INCREASE.

      Fixed.

  14. Simon says:

    This is looking more and more incredible for every post! You’ve now gone past the 90’s and Minecraft and into the 00’s. I’m getting a strong WoW-vibe from these latest screenshots.

    In the previous post I wrote a comment that I think got a bit misunderstood.

    I guess I should have been a little more clear. I wasn’t talking about fog and sky in general or in real life, what I was specifically talking about was that uniform fog will never make the silhouette of a dark tree, house or mountain brighter than the sky behind it.

    In real life, fog is everywhere and shows up both in front of the tree and in front of the horizon. In fact, the horizon will have way more fog in front of it. But in games you typically exclude the skybox from the fog pass, so while the tree has fog in front of it, the horizon has none at all.

    If you were to imagine what this strange scenario would look like in real life to an onlooker, he would see cones of fog projecting from your eyes toward every object close enough to be loaded into the world, but outside of the cones there would be no fog at all.

    You need to compensate for this by including fog in the skybox texture, and if you really want to do it properly you need to use a map for the fog (that you could generate from the skybox) so that the fog can have different colors in different directions.

    1. decius says:

      Small nitpick: In real life, fog is defined such that it only exists when it reduces visibility to less than 3/4 SM (or some metric equivalent in other countries) Small water droplets suspended in the air which do not reduce visibility below 3/4SM is the definition of mist. Haze has a third definition.

      Often the horizon can be clearly visible, even from a height of hundreds of feet.

  15. Magnesium says:

    Tree zero may be considered a tree if you call it one. None of the 24 other trees is an actual tree, they are representations of trees. They each resemble a tree and they are called such, and so we accept that they are trees. Tree zero does not resemble anything as it is nothing, and so we may judge that it is not a tree. But if we call it a tree, though it does not resemble one, is it not a tree? Must it resemble a tree to be called as such? And if so, to what degree? Humans are not identical, yet we still accept all humans as human, so is only a basic resemblance required? You could go so far as to cite William Shakespeare on his use of the rose as an example of the insubstantial nature of a mere name, but doing so would make you sound like a pompous twit with too much time on his…

    I’ll be going now.

    1. nawyria says:

      As a student of mathematics I don’t at all mind calling Tree zero a tree. This is something done quite often in mathematics to represent the “simplest” form of a particular class of object. In knot theory, for example, the simplest “knot” is called the “unknot” and is a simple loop that is not knotted at all.

      1. aldowyn says:

        There’s knot theory? I should look that up some time :D

        1. Avpix says:

          It’s knot that hard to learn.

          1. Otakun says:

            don’t bother, It’s all for nought.

            1. Avpix says:

              We both deserve to be punished for this.

        2. Zukhramm says:

          If I had to give one single piece of advice regarding mathematics, it would be to stay away from topology.

          1. Simon Buchan says:

            If *I* had to give one single piece of advice regarding mathematics, it would be to stay away from it. :) (The longer answer is less absolute, of course)

    2. Deoxy says:

      We could simply say that “tree zero” trees are tree seeds that never grew. Tada – tree.

      Edit: as many times are “tree” is coming up in these comments, I am reminded of a certain game of “I Spy” played by a certain pair of moose…. “Tree”

    3. Simon says:

      I wonder if Shamus still places these zero trees randomly in the terrain, and they simply lack geometry, or if he omits placing them at all.

      1. aldowyn says:

        they’re placed deterministically, so I imagine they are technically “placed” in the areas with the minimum temp and humidity.

        1. Michael says:

          It sounds like that’s what he’s doing, but I don’t think it would be too difficult to code an exception either.

          Instead of planting Zero Trees in areas that aren’t supposed to have trees, he could tell his engine to not plant any trees in that climate type [Biome? That’s the word for it, right?].

          That’s also [slightly] more work. I think I read somewhere that he wanted less code, not more.

          1. Piflik says:

            I guess that’s what he does. There’s bound to be a density function that determines how far apart trees may be placed in a given area and in the ‘0-Tree’ area there would simply be not enough space for a single tree. In his table there would still be an element for that tree, just unpopulated and unused…

    4. Piflik says:

      None of the 24 other trees is an actual tree, they are representations of trees.
      This is not a pipe?

      1. Michael says:

        Physically, no. But considering how colloquial language (and, indeed, language itself) works, I would still call it a pipe.

        To me, saying “This is a pipe,” and pointing at the painting is the same as saying “This picture is representing an object; a pipe.”

        Descriptivism.

      2. anaphysik says:

        As is technically true with any image.

        Though less fitting, I was instead reminded of this.

      3. Wtrmute says:

        I think it’s more like the other 24 aren’t trees per se, but representations of classes of trees. The trees are the individual instances scattered through the game world, which need both one of those 24 classes and a random seed number (oh, and the age parameter, too). Only when you have both (well, all three) of them do you have an individual tree, with a well-defined shape, which can be placed in the game world.

      4. decius says:

        What we call a tree is not a tree; that is why we call it a tree.

  16. Woodthorn says:

    Aw… Look at the pwetty twees!

  17. Canthros says:

    If a no-tree falls in a no-forest, does it make a no-sound?

    (I also like these articles, but I’ve little of value to add.)

    1. Chargone says:

      i think this joke may even have removed some :P

      also, it depends on whether you define a no-sound as a vibration in the no-atmosphere or a sensory experience by a no-being.

      (i wish i had more confidence that i remembered that correctly than i do.)

      1. Canthros says:

        Presumably, we’d be disinterested in the insensory impression of an unbeing incapable of such inexperiential aperception. Pretty irrelevant to the article, though.

        I think I understand the basics of making trees better than I’ve followed most of what Shamus has documented in this series of articles, so I expect to have a better grasp of what’s going on with the next article. Which is not saying much.

    2. anaphysik says:

      Unmaybe.

    3. Steve says:

      No, because Shamus hasn’t implemented a sound engine yet. ;)

      1. Jarenth says:

        An unsound engine sounds like a hard thing to generate procedurally.

        1. decius says:

          An unsound engine would seem to be pretty easy to generate procedurally. Or you could just license one of Obsidian’s engines; they tend not to be very sound.

          1. Jarenth says:

            Well played.

  18. Wtrmute says:

    Well, you can always write a game simulating Orpheus returning from Hades, or Lot fleeing Sodom. Have an NPC in front of the player look back and turn into a pillar of salt or something, and flood the screen with white and throw up a game over screen if the player tries to look back.

    That would be a bit too experimental for most people’s tastes, but it technically prevents the player from looking back… ;-)

    1. ZzzzSleep says:

      Orpheus has been done already. It’s called, oddly enough, “Don’t Look Back”. You can find it at http://www.distractionware.com/games/flash/dontlookback/

  19. nersh says:

    “Unless you can persuade the player to never turn around. Let me know how that works out.”

    Amnesia monster?

    1. X2-Eliah says:

      *shudder* you just had to mention that, didn’t ya? Mwaaaaaaaaa

  20. Odoylerules360 says:

    That tree page that you linked to uses voxels (probably sparse voxel octrees), so it uses exactly zero polys.

    Is the mouse eating going to be a video post? Perhaps to make up for the Spoiler Warning hiatus?

    http://www.youtube.com/watch?v=gNZtx3ijjpo
    ^^this explains voxels a bit

    1. Simon says:

      While the trees are stored as voxels, they must then be converted to polygons to be rendered by the graphics card.

      Unfortunately, as can be read in the post below, this still doesn’t save Shamus’ mouse.

      1. Simon Buchan says:

        Not necessarily. Pixel shaders can (theoretically?) directly render voxels, though it’s not for the faint of heart. Unless you count generating a ‘canvas’ quad as converting it to polygons :). More realistically, there are examples of using inverted boxes as the canvas to raytrace terrain accurately, with self shadowing even. The performance isn’t great, but it’s good enough to imagine it being useful in certain areas.

  21. MCeperoG says:

    “The point is, if those trees are under 10k polygons I'll eat my mouse.”

    This is Miguel Cepero from ProcWorld. I love what you are doing here and I don’t want to mess up with your diet, but when rendered to the user my trees are way below 10K, even for the closest LOD. And they still look very close to the original models shown in your link.

    It is a chain of tricks. First, I don’t need to render most of the branches since they are inside the crown volume (which is fully opaque and renders similar to your grass). The same for the roots, which quickly go underground. Most of the complexity that remains is then projected into a low-polygon mesh which uses some sort of Unique Texturing method.

    When they are distant, trees can be packed together. A single polygon has information coming from more than one tree. This is good if you want to show a very distant forest for instance. It actually saves polygons if you do a per-tree average.

    The difference with your approach is how long this process takes. It will take your system a few seconds to seed a new world and then the actual chunks are done in real-time. In my approach it takes a couple of weeks to create an entire world, and it would produce terabytes of data I would need to store on a server and stream to players (think of Google Earth for a virtual planet). Everyone using my project would see the same world, like in a MMO.

    While my trees may end up having less than 10K polys, I spend an awful amount of time generating them. It is like 400 milliseconds per tree, approximately, from seed to simplified mesh and unique texturing.

    Your project and mine are coming from very different angles. Your are starting from the desktop, I’m trying to put world generation in the cloud. It is not fair to compare whatever results we may achieve.

    1. Shamus says:

      Great, now I have to buy a new mouse.

      VERY interesting about your project. I was linked to it and actually started reading mid-stream, so I didn’t have a sense of what you were trying to accomplish.

      The fact that your trees are “way below” 10k is impressive. Those things look phenomenal.

    2. aldowyn says:

      eh, a question, if you don’t mind.

      If I’m following correctly, the models shown on that page are different from what you would actually see, right? And, given that those images show the roots and all that, there’s a lot more there to render. So, wouldn’t it be true that those actual models might have 10k polygons, even if the end result doesn’t?

      Yes, it’s a loophole :P

      1. MCeperoG says:

        Correct, the models are different. But still there is not much more to render, if you define rendering as drawing what the user needs to see. You can bypass intermediate generation steps.

        Check out this image: http://i.imgur.com/FNAe1.jpg

        The upper row contains the tree as it comes out of the voxels, which matches the polygon counts you see in the page Shamus linked. However, the user never sees that model. What the user gets is what you see in the second row. It is very simplified, but it is the same tree.

        In the screenshot there is a key step missing from this last row: the look of the leaves can be greatly improved by a technique similar to what Shamus is doing for his grass. It will mask the silhouette of the crown, which is where simplification shows the most. This will add some polygons for sure, but not many. Also to be fair, some of the polygons you see here are needed to “stitch” different world cells together. If the tree was entirely contained in a single cell the polygon count would be smaller as no stitching would be needed.

        Sorry Shamus for hijacking some of your post…

        1. Piflik says:

          Short question…are you baking the shadows or are there really no differences in silhouette between the Gazillion tree and the 6k tree?

          1. MCeperoG says:

            I bake the shadows produced by the high-resolution mesh. It helps with the illusion. If you look at the image I posted before, you can see there is some shadow over the trunk. It does not change from high-res to low-res.

            1. Piflik says:

              Yeah I saw that…that was why I asked ;)

    3. Otakun says:

      worth pointing out that if teh deterministic rules are eth same, then all players in Shamus’ world will see teh same landscaope. Its just that the terrain is generated on the fly, but still the same for everyone.

      Which would actually save the Big MMO Boys bazillions of bandwidth… hmm.

      1. scowdich says:

        Looks like you accidentally spelled “the” correctly a couple times. :P

        1. brain fast

          keyboards slow

  22. Phoenix says:

    I’m one who doesn’t like that much cubes (like on minecraft), especially on open areas. However I came to appreciate badly-animated, not-too-defined 2d graphics of haven & hearth (a mmorpg who basically is more complex than minecraft about crafting and it’s almost all about crafting).

    http://www.spilljenta.com/assets/hh_pinetree.png

    So I guess it’s not black & white, since there are probably people who hate not-so-good 2d graphics but like 3d cubes.

    1. Simon Buchan says:

      Honestly, it’s not the lack of detail or care that bothers me, it’s the lack of *consistency* of detail: the ground and vegetation is in a different style to the fencing, structures and other objects, which again are in a different style to the interface. If they could pick one style and be *consistent*, then it could look great, no matter the detail.

  23. TSHolden says:

    Shamus, please check out this page: Graphics and post-processing effects used in Shadow of the Colossus

    It’s a fun read, and in particular I am wondering if the LOD System and Landscape Rendering section is applicable to Project Frontier. In a nutshell, the world is rendered in 3 passes, where each pass renders an area at a certain distance from the camera. The furthest level is rendered to a skybox image which is only rerendered every few frames, effectively letting you cut your cost down to a small fraction (if you rerender every fourth frame, the cost is now 25% of what it was).

    1. aldowyn says:

      I’ve noticed that, for some reason especially at that first cliff. The places really far away look like… well, the horizon/skybox.

  24. Adam says:

    This is probably well beyond the scope of the project, but have you ever considered making a procedural (say) monster generator, or quest maker? Something like this could be a sort of procedurally-generated Morrowwind, with the right add-ons.

    1. droid says:

      So a higher tech version of Daggerfall?

    2. Otakun says:

      Shamus already did this once, actually!

      http://www.shamusyoung.com/twentysidedtale/?p=1462

      code reuse!

      1. uberfail says:

        I always wondered where the face-shapes came from.

        Also, so very pretty. I’m guessing the trees look like cones because they ‘are’ cones…

  25. 2tm says:

    Thank you for the link over to Miguel’s project Shamus! Another very cool thing to follow!

    Liking the progress on Frontier, I honestly think that it’s looking really great already, and the hack trees you’ve thrown in there really aren’t half bad at all for a low-res game/world!

  26. aldowyn says:

    You might be planning on talking about this later, but how are you going to approach tree density?

    I would make it partially dependent on the temperature and moisture, but also partially randomized. There was something earlier that was done the way I was thinking, but I don’t remember…

    1. decius says:

      Additionally, some regions should have a tendency to cluster, and other regions should tend towards even distribution.

  27. Velkrin says:

    “The grey circles are mountains”

    Either you’re lacking mountains or you meant squares. Or both.

    1. Piflik says:

      A square is nothing other than a very low-poly circle ;)

  28. Gndwyn says:

    Minecraft has proven that a large number of people are capable of accepting a stack of one-meter cubes as a tree, both visually and as a gameplay conceit.

    What about those of us who think Minecraft’s deciduous trees are great but the pine trees look like crap?

    A sample of one such person thinks your trees look fantastic.

  29. Mogatrat says:

    It’s looking more and more like Sacrifice as you go on! And this is a very, very good thing, as Sacrifice had a lovely, weird aesthetic that I’ve always loved.

  30. UbarElite says:

    This does seem to be coming along nicely. From this and the youtube video, it looks very good, especially considering that it’s a one man job. Loved the procedural city and I’m loving this so far.

  31. Kelhim says:

    I like the trees and I’m looking forward to seeing how the lakes were generated in conjunction with the rivers.

  32. TigranTheMetz says:

    I really love this chunky feel you’re doing here, especially with the trees. As you said, it’s a hit between Minecraft and the early World of Warcraft. And my favourite thing about the latter was just the art style. Now it feels a bit dated, but before I was just in love with the chunky tree shapes and overly-rugged terrain.

    When I saw that last picture, it was really nostalgic seeing those trees and that background. I really can’t wait to just walk around your procedurally generated world, Shamus :D

  33. Kdansky says:

    I have a huge criticism! Why are there only two screenshots!? My eyes require more pretty pixels!

    Now it only needs gameplay that isn’t like WoW (i.e. engaging), it can already easily keep up in the looks department.

  34. psivamp says:

    Seed: Not “seed” as in “plant seed” but “seed” as in “random number seed”. (Although the two concepts overlapped here in a way that greatly amused me.)

    What I think would be neat is if your world L-System-esque data and random seed (call it a world seed, if you will) was the same size as and parsable as a tree seed you could have a unique tree for each world that you save — Yggdrasil.

    Then you could have a fancy shmancy menu where you’re looking at a row of world trees and you select which saved world to go to by clicking on its tree.

  35. Nidokoenig says:

    I assume there’s a very good reason for this to do with computers doing everything in squares, but why are using squares to calculate draw distance, rather than circles, or at least an approximation of one? Does it just create more work for the magic thinky box to pare what it draws down to just what’s in the circle/octagon/whatever that’s as wide/as wide in the middle of its faces as the standard draw distance, than it saves by not just drawing the whole square? Or am I just taking the example too literally?

    1. MichaelG says:

      If you store things in squares, you have a natural data structure — a table with rows and columns. Adjacent squares meet up cleanly and you can walk from one to another. You can tell which square you are in with a simple division.

      If you tried to store things in circles/octagons, how would you store the values, and how would you tile them to cover the landscape? How would you find which one you are in from your x,y position?

      1. Bubble181 says:

        Still, one would assume you could save about 1/pi of the generating power by approximating a circle with squares, instead of drawing it out over a full square grid of squares. No?

        1. WJS says:

          Considering that that would be a linear saving, while the cost of rendering is quadratic with distance, it won’t be that big a saving. You still do it, to be sure, but it won’t save you all that much.

      2. decius says:

        If you describe your position in x,y,z coordinates, you have already embraced the rectangular world.

        Heading, elevation, distance is the proper way to describe position in the circular world (distance is nontrivial to calculate without vector math, or trivial with it); or row, col, height in the world of hexagonal prisms. (row and col are at 60 or 120 degrees to each other, not 90; distance between two points at the same height is the maximum of the difference in row and the difference in col)

        The real advantage in using squares to calculate view distance is that straight-line distance calculation is expensive compared to Chebyshev distance calculation.

    2. Simon Buchan says:

      In fact, what most engines draw is a ‘frustum’: a pyramid with the top chopped off where your eye is where the top would be, the screen is at the chopping plane, the sides of the screen are the sides of the pyramid and the draw distance is the base. This is because the first step of rendering is moving everything so it is where it should be, so implementing the draw distance is just ‘object.z < DRAW_DEPTH'.

  36. Gordon says:

    hundredth post?

  37. Davie says:

    Good god, Shamus, every screenshot you post makes me want to just jump in, load up a world and start exploring. The fact that you still have a bunch of things to add to the project makes it all the more exciting, and in the meantime these posts are an immensely interesting read for some one like me with an interest in the process of programming but not the specifics.

    These are easily my favorite articles of yours in all the three years of following your blog, so thank you. And I can’t wait to see more.

  38. uberfail says:

    The only thing this is lacking is more pretty pictures

  39. RCN says:

    I wonder if you could jam in a genetic algorithm in there to make trees from a certain area to have similar attributes since they’ll probably be from the same family. That’d be at the same time incredibly awesome and useless, from the same kind you talked about, generating both admiration and apathy. Still, the people who’d notice would REALLY notice it.

    On an off-topic note: did you hear about that:

    http://dvice.com/archives/2011/06/capcom-tries-to.php

    So… after the whole Sony-online shutdown fiasco, Capcom chose to see what went wrong and make it a hundred times worse! That’s sooooooo wrong. It is nice to know that if I buy games from capcom from now on (or even games I’ve already bought, they can probably implement that with an update) it will not work anymore after I’ve uninstalled them, or if my console/PC breaks and I get a new one/format it.

    Sometimes I wonder if those publishers are actively fighting over for the title of “Most Evil Mother******”. When it is not Ubisoft and their DRM it is Kotick and his natural evil aura or EA with their whoring of their products or Nintendo preying on nostalgia or Capcom treating their customers WORSE than criminals…

    (EDIT: Have I told you already how the Edit function from your site works much more smoothly and easier than most professional business sites? Just thought you’d like to know)

  40. Thomas says:

    That picture is rather pretty

  41. Zak McKracken says:

    Regarding your photoshopping skills: Doesn’t look half bad, even the intersection of the right picture border with his hair looks right.
    One thing that helps immensely: work with a much higher-res version, then blur a bit and scale down (that helps the whole picture have the same or similar blurriness, as opposed to perfectly sharp computer graphics vs. a photo). Oh, and don’t cut off Bob Ross’ paint brush :)

    … but I guess the same rule as for making games apply: If you want to make it perfect, you’ll take forever, This is usually what happens to me, even if I set out to do it really quick ‘n’ dirty.

  42. Steve C says:

    How come I have a strong desire to set your trees on fire and see how the fire spreads like in Mindcraft?
    And great job.

  43. Blanko2 says:

    i love the idea of this.
    and i really love the look of the map, the distribution of trees seems pretty realistic, going by what your weather is.

    are you going to render the trees as 2d images the further away they get from the player? that seems like a good way of getting higher performance at lower sys specs.

  44. Noah C. says:

    Huh. You know, that map (not the climate and different tree zones, the actual land) looks just like the Morrowind map. Weird.

  45. Adam says:

    This project is amazing, but I do have a suggestion for the trees-and sorry if I missed this somewhere else. Speaking as a biologist, some (or most) of your tree biomes should contain more than a single species. Most trees could occur in several climates, and each climate could contain varying percentages of trees. If you want to go for realism, your warm, wet climates should have more diversity. Using the edge-fuzzing method may be a good enough shortcut though. Another thing you may want to consider is doing some micro scale tree placement, as with the micro-scale geography. Have it check things like “am I near water?” or “am I on top of a hill?” or even “am I in the middle of a bunch of other trees?” and put down a different tree if that is the case. All of the above could also apply to the grasses and flowers. This could give you things like weeping willows and reeds.

  46. Neil Roy says:

    I realize this is an old project by now, but I was thinking about those blue spots that are lakes. I thought the solution to the river problem from earlier posts, where it ran into a hill should be like nature, just find the lowest edge the water can flow over, then fill up the area with water as it would naturally and voila, you find a path for the river and you create a more natural looking lake in the process.

    1. WJS says:

      Agreed. Perfectly circular lakes? Eww! (for all of them to be that way, anyway) He really should have done lakes from rivers. Ah well, fait accompli.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to BenD Cancel reply

Your email address will not be published.