Let’s Code Part 8 & 9

By Shamus Posted Friday Jan 21, 2011

Filed under: Programming 35 comments

The Craft of Craftcraft project continues. Here is part 8, which is followed, according to the ancient traditions, by part 9. My own coding work has been shelved. I really want to get back to it, but the time just isn’t there right now. So I’m living vicariously through Michael’s work.

I think it’s really interesting what he’s doing. He’s doing a Minecraft-like game, but the “world” is actually a series of asteroids floating in space.

Goodfellow has been doing just fine without my advice, but I thought I’d throw some out there and do a little armchair game design. This is probably more for my benefit than his, but verbal restraint is a cross-class skill for me…

The Horizon

If this was my game, I’d want a horizon to give a sense of orientation and break up the visual monotony of the sky. EVE online does this with ridiculous and unrealistic nebulae. It even draws the nearby sun with a huge horizontal lens flare to approximate the horizon. It looks fantastic. It can also help orient you visually. “North” is the red clouds and “south” is the cyan / purple clouds, and so on. His idea for setting it in a planetary ring / asteroid belt is a good way of accomplishing all of this, although he’s still working on making it look right.

(You could even take this one step further and have these asteroids appear to float around a planet. White clouds below. Blue sky above. It would explain the presence of gravity and atmosphere. This would make the rocks easier to make out against the sky. (Right now they are hard to spot.) The downside is that the current “space” look is very unique and there’s no real reason to abandon it.)

Plant Life

Michael introduces the idea of plants. (Ferns, bushes, grass, whatever.) This is something I think is really missing from Minecraft. Of course, once you add this, people will want to do landscaping. They will want to remove some plants. Move others. Cultivate ones they like and uproot ones they don’t. That adds a lot of complexity, as well as gameplay. Minecraft has, basically, two flowers and two mushrooms, and you can only find them – you can’t grow more on your own. I really like the farming aspects of the game, and I’d love a game that featured more of that.

Level of Detail

He’s talking about how to render the asteroids in the distance without needing to render EVERYTHING. I have no idea how he’ll accomplish this. Standard level-of detail-techniques will NOT work well with a block-style world. The blocks ARE the detail, and merging them will make a mess of things, I think. (Consider: Players are going to want to build bridges between these, even if you give them other modes of transport. How do you detail-reduce a single-bock walkway that stretches on hundreds of meters, without simply obliterating it? The way people build in these games will lead to worst-case-scenario structures on a regular basis.)

This is a problem that not even Mincraft author Notch has solved. Check out this screenshot from Minecraft:

minecraft_xray.jpg

Here I’m using a texture pack that makes stone block into windows, so you can see through walls. I’m staring into a dead end tunnel here, with my nose just a short distance from the featureless wall. Yet you can see the game is drawing, basically, everything. It’s drawing the lava chambers in the distance. A system of caves beyond that. And up above, it’s drawing all of the terrain topside. I have a sense that this is solvable, although I also sense that this is one of those problems that will be way harder than it seems like it should be.

And maybe it’s not worth solving. From some vantage points, the game will need to draw this many polygons. If the game can’t handle it, then the game won’t run right anyway. You could spend a lot of time optimizing the game so that the framerate will sometimes skyrocket (like in my dead-end situation above) but it wouldn’t really make the overall game that much faster. You could blow a week on a problem like this and discover that the overall benefit is minimal, situational, and only worthwhile to the bottom 10% of the machines running the game. I don’t know. I’ve never used an octree (which is odd, given the work I’ve done in the past, but there you go) so I’m working on this in my head conceptually, which is a lot less useful than experience.

And even if you found a solution that worked really well and was a great benefit in Minecraft, it might be useless on CoCC, because of the “open asteroid” design.

Interesting project. Looking forward to seeing where this will go.

 


From The Archives:
 

35 thoughts on “Let’s Code Part 8 & 9

  1. Matt K says:

    Where did you get the window-block texture pack?

    1. Sydney says:

      Sydney also would like to know.

    2. Shamus says:

      I just hacked it together myself. I extracted the terrain texture and made the stone transparent in photoshop.

      1. MichaelG says:

        This whole project has made me more impressed with Minecraft, and with display cards.

        Yes, he uses a small window, and the nastiest linear scaling method on textures, but the game is still drawing A LOT of triangles. Notice how far away the horizon is and how many blocks are within the visible area. We’re talking millions!

        1. Will says:

          Triangles havn’t been an issue for a very long time; modern graphics cards can render absurd numbers of polygons with phenomenal ease.

          1. (LK) says:

            But triangles are pointy. Someone could get hurt

            1. MoonBeans says:

              Best. Comment. Ever.

  2. Groboclown says:

    I would imagine that, in a block world + octree store, the distance optimization problem wouldn’t be as much of a problem. Now, this is speaking not from experience, but from off-the-head.

    Since the octree is stored in blocks of different sizes, it naturally seems to be able to store, at a non-leaf level, aggregate information about its leaves.

    Essentially, when plotting out the block to draw, trace through the octree until both a certain distance is met AND the octree node is small enough. At that point, draw the “average” texture for the node, at the size of the node.

    This has problems in that the texture won’t scale correctly over the large block, and a few other issues with going “far away enough.”

    Arm-chair design is always nice when you don’t have to implement the code.

    1. MichaelG says:

      I guess I should just try this to see how nasty it is. It’s not hard to implement.

      I just think if you take a Minecraft building, cut the dimensions in half (total number of cubes down by factor of 8), replacing things like thin pillars with thick ones, it’s going to look horrible.

      1. Groboclown says:

        I agree, and that’s why you have a minimum distance + average in order to do this.

        If the compress block size is 8×8, and the pillar is just 8 blocks on one corner, then the average is not the pillar, but the other stuff. This will give the effect of the pillar “magically appearing” as you get closer, but that happens in most graphical games.

        EDIT: on further thought, if the compressed block is far enough away, you could get away with even more interesting things – like taking the color average of the textures to use as the texture for the block. Yes, it’s more up-front computation, but could be cached just once.

      2. Robyrt says:

        True, but a series of spidery pillars is your worst-case scenario. Houses, trees, boats, etc. will simply appear like rectangles, with a simple “best guess texture” on them.

        1. Kiesel says:

          there is also the fact that the human eye only has so much resolution in the real world, and the fact that atmospheric scattering further decreases the ability to distinguish detail at long ranges.

          In many ways, a method which averaged the individual blocks together, would closely resemble the way actual vision functions.

          Of course the “atmospheric perspective” effects would have to be much stronger than in reality to have performance benefit. But objects rapidly blurring with distance could be made part of the visual style. Giving a sort of “painterly” effect.

          1. Kiesel says:

            A particularly good way to deal with extremely distant objects is to render them only rarely and add them to the skybox texture.

            The only way for the player to tell the difference would be to move far enough to notice the parallax anomaly.
            If the texture is updated only when the player has moved far enough away from the point at which the original box was rendered from, then it should save a lot of render time.

            Of course this technique is only unobtrusive when it is rendering things that the player cannot interact with. Hence requiring a maximum distance that the game keeps track of moving objects.

            1. Rilias says:

              I wonder how crappy you’r result would be if you precompute blocks for the parents of some level of the oct-tree, by treating these say 8x8x8 areas of game world as a single block with 6 sides for which the textures are computed based on the actual blocks visible from these 6 sides.

              At the same time this sounds like the worst kind of hack, but also like a hack that might actually fit into the minecraft style quite well.

  3. Jabor says:

    This is what older games used “fog” to accomplish ;)

    The battlefield would be perpetually shrouded in a thick mist, thereby making it impossible to see beyond a distance that the machines of the time could comfortably render.

    1. Irridium says:

      Reminds me of Battlefield 2, especially on Karkand.

      I want to snipe people from buildings, but the f*cking fog makes it really, really annoying.

      Anyway, more on the topic… this reminds me of Kingdom Hearts 2. In that game you participate in a battle against 1000 enemies. I’m not talking about the “6 enemies at a time” way like most would solve it, but all those enemies were there, onscreen, and able to fight. I’m sure there was some virtual wizardry involved, probably had the enemies that were farther away do little-to-nothing, while closer ones did more and more as they got closer to you.

      But thats more AI related then texture/draw distance related I suppose. Or maybe not, I’m not sure. Still, felt it was worth mentioning.

      1. SatansBestBuddy says:

        It’s actually a clever trick with sprites that they used in a few other spots in the game, where the enemies that fight back are made of a few hundred polygons, but you’re only fighting 8~, while the hundreds in the background are made of maybe two polygons each and don’t really do much more than run around and die.

        The reason it’s clever is because the sprites are just the right size to look indistinguishable from the attacking enemies thanks to the PS2’s resolution, but when people started up that resolution with emulators the effect became really obvious, showing that a lot of time was put in to make that effect look good only on PS2.

        So… yeah, doesn’t really solve the problem at hand, but that’s how they did it in that game.

    2. Dys says:

      Minecraft has a Draw Distance slider, which fogs out things at increasing distances. Fog was always an uncomfortable solution though, since it was basically giving up on rendering the world properly.

      Minecraft fog does often look like a weather effect though. Can be quite nice.

      Minecraft needs weather…

      1. James says:

        The fog looks a bit weird underground though if you dig a long tunnel.

        Minecraft does need weather. And water that behaves more realistically (but without flooding the entire game!).

  4. wererogue says:

    You can farm wheat in minecraft, which grow, and can be made into bread. You can also grow/farm cacti, and reeds/sugar canes (they used to be reeds, but now they’re sugar, and can be used to make cake.
    You can also grow new trees.

    It’s not exactly super-deep farming, but it’s not accurate to say that there are only flowers and mushrooms.

  5. Christopher M says:

    It seems to me that an effective way of cutting polygon counts in exchange for texture memory in a blocky world like this would be to cut the world up into slices, each with their own texture.

    So if the world is 128 blocks high, you have 128 vertical slices – 256 polygons and 128 textures to represent the tops and bottoms of every block. (Alternately, a shader to perform texture atlasing would cut the memory/texture prep time problems entirely, but increase the draw time for each polygon)
    Likewise, depending on the draw distance, you need only have perhaps 2048 additional polygons in total to represent a draw distance of 256 tiles in every direction.

    Total polygon count (optimal) for a Minecraft-style world? 2304.

  6. S. Richmond says:

    I might be wrong here, but most of the render time in these games is spent drawing the individual block faces. If you wanted to reduce level of detail at a distance I would see about whether you could run a cheap algorithm that merges large clusters of block faces into a single face. For example, a bridge 6 blocks wide and 500 blocks deep is 4000 polygons (quads) (or 8000 (tris)), if you don’t draw the bottom. You could turn that into 3 polygons (quads) if you merged the blocks into a single block or model.

    1. EmmEnnEff says:

      The problem comes when you’ve got different-colored blocks making up a larger block.

      1. S. Richmond says:

        This method will require a fair bit of texture management logic yes – One will need to be able to stitch together textures over a face. Shouldn’t be impossible though, as its done on almost any game in existence now-a-days.

  7. Pickly says:

    Somewhat related to this, how is Project hex coming? I noticed in the post from a few weeks ago you said you had stopped working on it, have you just been really busy otherwise, or has the project hit some other snag that’s stopped it in its tracks for awhile?

    1. MichaelG says:

      I have the impression Shamus is writing a novel. Hard to do that and code at the same time.

  8. Reach says:

    One reason to solve that problem is to prevent people from doing what you did, basically x-raying everything in front of you, on multiplayer servers. Even among my close friends I’m having trouble with wall hacking on my server and there’s no way of preventing it right now.

    Edit: The problem I’m referring to is the drawing of things the player shouldn’t be able to see.

  9. rofltehcat says:

    How do you detail-reduce a single-bock walkway that stretches on hundreds of meters, without simply obliterating it?

    Can’t you somehow decrease how the blocks are drawn? For example, after 200 m blocks lose their textures and become monochrome (ofc. still a grey color for stone blocks, blue for water etc.) and after 400 m they start to blend into the blackness of space (become transparent until they vanish because they are ‘too far away to see’) etc.
    After all in 3D the things that are farther away become smaller and thus they are harder to see. Couldn’t you just replace blocks after X distance by single pixels? This would probably be hard to see for anyone anyways because they are already so small by then and it should reduce the amount of drawing your machine has to do by telling it to just replace every block after X distance with a single ‘pixel’ (well, maybe start with 5×5 pixels and get smaller to 1 pixel gradually) instead of a miniature block? Though that might cause problems with overlaping structures etc. because everything after a certain distance might look 2D so you would have to make the farther ones even smaller or still vanish.

    The thought behind this would be to make the transition as smooth as possible because objects that pop up suddenly would be pretty weird even though the objects would be created from single blocks so there would no whole tower plop into sight but instead a few blocks at a time while you are getting closer.

    I keep wondering… how is gravity handled in that asteroid game?

    1. Christopher M says:

      That concept (at least where it relates to texture detail) is, essentially, mipmapping, where by doubling the texture size, you can compile a list of progressively-smaller textures for use at distance. At Minecraft’s detail level, however, 3D block ‘mipmapping’ would be rather hard to accomplish; assuming a series of 2x scaling “mipmaps” where every eight blocks becomes a single colored cube based on average properties (itself rather complicated to compute), one would have to start exchanging sizes at the very edge of the current maximum draw distance to prevent people from really noticing the difference, and that wouldn’t exactly make things faster.

  10. Benny Pendentes says:

    Dark Ade of Camelot had (what I thought was) a good technique for handling LOD of distant objects: beyond a certain distance, instead of rendering the 3D geometry it threw up a sprite with a 2D representation of the view. When you got closer both would exist for a while, the the sprite would disappear… poor-man’s morph.

    In DAoC things were much more complex, though, so some kludginess remained. The sprite wasn’t an actual map of the 3D view; it was always the same sprite for one kind of trees, always another for a different kind of trees. And it always faced you directly, even if the actual lay of the land veered off in some direction.

    But it seems like block-based geometry is ideal for this technique: blocks are square, pixels are squarish, so just build a tiny sprite where each pixel represents a block in a vertical plane and all of the rest is transparent and scale the sprite to the correct size. Color the sprite not with the block’s texture (since each block becomes a single pixel), but with the average color of each block’s texture, precomputed or defined on load or something.

    If it’s not already apparent that I’m not a programmer, it probably will be pretty soon.

    The first big problem I see is how to handle arbitrary slices through the geometry that define a plane whose normal points at the camera but which may be oriented any-which-way relative to the orthogonal axes of the world. The second problem is related to the usual culling problem: if block-less areas map to transparent sprite pixels, you’ve got to make more sprite-plane slices and stack them up behind the first one.

    It occurs to me that this is similar to a technique used in Disney cartoons, with multiple layers of glass with matte painting and clear areas focusing differently in the camera… it gave a pretty good illusion of 3D, for the times.

    I don’t think any of what I’ve described is insurmountable, but won’t be surprised if it is pointed out that the idea is lame. Criticism/discussion is welcome.

  11. Ben Munson says:

    Oh level of detail, the enemy I grapple with at work on a seemly daily basis now.

    The whole world in the game is being treated as if it can change at any time. While true, only the portions around the player can, there is a big performance win to be had by building static buffers for areas far from players that aren’t likely to change, rather than building up a display every frame. This is an ideal task for multi-threading.

    These asteroids are being treated as if you’ll be able to see every change that a player makes. This is unlikely, they’ll have to build/destroy 10s if not 100s of blocks to make a visible difference at that range. The asteroid can be rendered to a texture once every 10, 20, 30 frames or whatever your card is capable of, and per frame you only have a single quad to worry about.

    Occlusion culling can be done very effectively and fairly easily here. If you have a set of blocks near the user, you can transform their vertices into projection space (basically where they would be on the screen). You now have a few polygons behind which nothing can be seen. If you do the same for each octree nodes bounding box, and the resulting polygon of that is entirely with the first set, you have a whole set of blocks you can safely ignore.

    I think it’d be very interesting to see a performance profile to know where the bottle necks are.

  12. Zak McKracken says:

    My shot:
    Reduce the maximum octree depth depending on distance. Each branch that isn’t displayed in ful detail could be represented by an “average” block. Also, as rofltehcat already wrote, at a certain distance you can ignore textures and replace them by an average colour for each block type. So now you have only one colour (and transparancy) for each type of block, and those can be averaged. The only thing that remains is the shaiding, and that’s not quite so easy.
    Althoug I guess you could determine the angle at which you’re looking at the averaged block, compute the three colours you’d be seeing (three sides of a cube) and blend them according to the fraction of screen areea they’d be covering if they wore more close. voila, that’s your block colour.

    When to blend? I guess you can foget about textures when a block is only 2×2 pixels, and start blending blocks if a “superblock” has less than that. You could do it earlier if there was some sort of space fog or something …

  13. Rodyle says:

    I may misunderstand where the bottlenecks in these systems are, but wouldn’t most of these solutions require enough calculations and whatnot that it’d basically take just as long as drawing the entire thing?

  14. Integer Man says:

    Shamus, how do you stay motivated on long projects? How do you get stuff done when life and distractions heat up?

    Love coding for fun, but when life gets complicated or work goes into crunch mode, my projects just kind of fall by the wayside. Any advice?

  15. TheZoobler says:

    So Shamus (and Twentysided community), I have a question. A question about programming games.

    Lets say that I have a passion for games and gaming in general, and really enjoyed the few programming classes I’ve taken (just a college semester in Python and some Java). Well, what if I want to make games of my own? Indie is a big thing right now, so obviously its possible to make enjoyable games with few resources and a lot of ingenuity. Lets leave creativity and luck and passion all out of the question for a moment though, because only time could tell if someone has those three things.

    So the basics. How and where should I learn to code games? Are there good free references? Suggested reading or tutorials? Should I take college classes on it?

    I don’t expect to be the next Minecraft or Super Meat Boy or even the next Haven and Hearth, I just want to know where I can learn the programming skills necessary to make a solid game. I’m starting from pretty much scratch when it comes to everything coding. All I know how to do so far is random integers, logic loops, basic algorithms, that sort of thing. Manipulate a command window. I have no idea how to make a working GUI or code sprites and models and animations or anything at all really. Where and how is the best place to learn? What programming language would be a good starting point/which language is standard for indie games such as Meat boy? Anyone have any advice? Should I post this in a more recent and relevant entry?

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

Your email address will not be published. Required fields are marked *