 |
| Screenshot showing different tree shapes |
Many times the best way to understand how to solve a coding challenge is to sit down and write the code. By the time you get the code (mostly) working, you'll have identified the important parts of the problem and some of the considerations you have to make in the code.
Take trees, for instance. Recently I added a bunch of new tree types to my terrain engine. How do add trees? For a lot of terrain generation, I just start with "walk through every cell and decide if there's a tree there." Forest? Greater chance that there's a tree. Desert? Unlikely that there'll be a tree, and if there is, it'll be a cactus or maybe a Joshua tree. Sure. OK. How big is the tree? For a sparse area (like plains or desert, or even a mountain that isn't forest-covered), once you decide to place a tree, you're pretty much free to choose any tree size you want without having to worry about butting against other terrain.
But what about forests? The naïve algorithm (gimme the next square; ok, what size tree will fit here?) produces a forest of tiny trees ... because the tile to the north and the west are both filled. (This is assuming a walk of the for (y=0..n) for (x=0..n) sort.) Tiny trees? Well that's a poor forest. My first assumption was that I would try to center a tree on x, y. The next choice is to put the top-left right there. This results in a forest of giant trees, because (generally) the space to the south and east is empty because the algo hasn't walked there yet. But I can't choose the type of tree first and then choose where to put it, because I don't want to put a forest-type tree in a non-forest biome. (Each tile has its own biome, and borders are irregular -- which is why I started with putting the trunk of a tree at x,y -- because I knew the biome for x,y.)
OK, so maybe I pick a size first, and then pick a tree type. This kinda works, because generally if I'm at x,y and that's the northwest corner of a tree, generally the spot where I want to put the trunk of the tree is very close and of the same biome type. But what if it's not?
What I finally settled on is to first make sure I had a minimal tree size available. This is just 3x3. If that much room isn't available and/or the center of that possible tree is in a different biome, then I decide not to plant a tree and move on. This minimal condition means I have a fallback. Next I try to make as big a tree as possible. If a 5x5 is possible, I think check 7x7. This goes up until I reach my max tree size (which right now is 7x7, just because I don't want to fuss with larger trees yet; and also I haven't yet looked at asymmetric trees OR trees with 2x2 trunks). So now I have a set of possible sizes: (3x3, 5x5, 7x7), as well as a maximum height that the space allows. THEN I decide what type of tree, how wide to make it, and how tall.
Given those parameters, it's still possible to make the same type of tree (eg an oak) in different ways. Sometimes the trunk is taller; sometimes the leaf canopy is shaped differently. But, having written the code, it became clear that if I said "this tree MUST be 5x5 and it MUST be 9 voxels high and it MUST be an oak", that it's fairly straightforward to define the algorithm for making an oak that big.
At first the code was sloppy, but it got better. Gradually. I added the assistance functions as I went (is there room for a 3x3 here? is there a function for saying "all these voxels should be leaves"?). I separated size-checking from tree-size-choice. In this case, I really wound up inverting the algorithm -- instead of randomly choosing a tree type and size first, and then checking to see if it fits, I see how much room I have, and then choose a size (and type) based on that.
The key is to be willing to rewrite code. My end goal wasn't just to have more trees in the world; it was to have a well-built, robust, and extensible system. This means the code isn't fragile; small changes won't crash the whole thing. The code used to plant trees on top of other trees; it doesn't do that any more. Robustness means that all the trees it generates are properly formed and in the right places. Finally, it's easy to add more trees ... which is good, because I've got plans for 15 different tree types!
I started by writing sloppy code. To me, quick and dirty is ok, because it leads the programmer to solve the most important problem first: understanding the solution.
