• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
  • entries
    432
  • comments
    1166
  • views
    759376

Revisiting the block worlds stuff

Sign in to follow this  
Followers 0
JTippetts

1839 views

In revising the ANL, I've revisited some of my old projects. Today I did up another example Lua script, included in the Examples folder, called blockworld.lua. It's a remake of my old cube-world generation stuff, demonstrating how a complex function to assign block types for a cube terrain can be built up using ANL's modular pieces. The example follows pretty closely along with my original articles, although it is updated for the new library version.

Since ANL is just a Lua framework, with no in-built graphical capabilities, visualizing such a beast as a cube world isn't straightforward. The example script constructs the noise function, maps it to a voxel array, then iteratively constructs meshes for each of the block types using the Volume functionality, built atop PolyVox. It then dumps the meshes to .OBJ format files. The script generates chunks of the function, specified by chunkx and chunkz coordinates, so the world is essentially infinite (at least to the limits of double precision).

The function isn't sophisticated. It shows strata layering using a distorted vertical gradient, ore deposits, caves with the lower levels filled with magma, a solid bedrock layer, etc... There is no large-scale variation in the distortion function, such as you might want to use if you are generating different kinds of biomes and geography; it just uses a simple fBm fractal with some slight vertical axis dampening to reduce the frothy distortion that can result in floating islands of terrain. Here are a couple shots of it in action:

LSDbrnE.png
Idu3eMR.png

I don't do much with this sort of generation. I don't really have any interest in building a Minecraft clone, for example. My interest is purely academic, a fascination with procedural world-building in general. Every time I tinker with this kind of thing, I am reminded how my library is actually kind of slow. This example script does a lot of stupid shit with copying and recopying buffers, iterating voxel arrays multiple times, not cacheing some values, etc... It could be faster, but even if I squeezed it as tight as I could it would still be somewhat slow.

I've always been a concepts guy. I have ideas for things I want to tinker with, I build a tool or a prototype to demonstrate it, I move on. I've spent a good bit of time on ANL, mungeing things around, re-organizing, etc... but I've never been very good at optimization, and so ANL has never really been tightened up. But lately, I've been thinking about how I can make things faster.

To start with, it seems like learning about SSE might be a good place to go. This sort of function wrangling is pretty computation-heavy (especially when dealing with the higher orders of noise; ANL does up to 6D noise, which can be slow as balls) so I'm thinking that between implementing many of the computations using SSE intrinsics and trying to take advantage of multiple cores, I might be able to squeeze some better juice out of this thing. I don't know how much time I'll be able to devote to it for now, but I'll probably at least start reading a few sources to learn the ins and outs of SSE to see if it's something I could pull off.

14
Sign in to follow this  
Followers 0


13 Comments


Thanks for the additional example script. blockworld.lua takes about 20 seconds on my Phenom (3.3 GHz). Doesn't sound all too bad for me. But I hear you. Noise screams for parallelization in one way or another.
 
As food for thought I recommend reading this dev blog. They're doing amazing stuff, but it's a whole team and one guy even juggles with tensors.
 
PS: Oh, and thanks for making me rediscover de Carpentier. (For other readers: ANL has built-in support for this kind of noise).
1

Share this comment


Link to comment

That was an interesting link, thanks. It looks like they're considering basically a similar system to what I'm actually considering; that is, representing a module tree as an expression and parsing it down to a sort of sequential bytecode operation. That is the idea I've been considering. I would build an expression kernel from either a Lua table, an explicitly built module tree (similar to how I build them now), or some other means, and turn it into a flat array of operations that can be executed by a task handler to generate a value. This way, I would eliminate all of the virtual calls that occur now, and solve problems of requiring a thread-unfriendly cache in each module to prevent multiple duplicate calculations. Each stage of the tree would be an operation that could refer backwards to operations earlier in the sequence, then cache their results locally for subsequent operations. By giving a copy of the expression sequence to multiple tasks (each with its own result array for cacheing) I can multi-thread it fairly easily.

1

Share this comment


Link to comment

I'm not sure SSE is a worthwhile rabbit hole to venture down - modern compilers are pretty good at generating SSE code for the simple cases at least.

 

Algorithmic improvements via better caching strategies and so forth seem like lower-hanging fruit.

0

Share this comment


Link to comment

Hmmm, I see you use double precision throughout. Ever considered/checked single precision ? 

0

Share this comment


Link to comment

Looking at most of my use-cases (in particular, the island generators for GC plus a slew of procedural textures), I'm not sure my idea of compiling down to a sequential array of bytecode would really be the best thing, A lot of my stuff uses a step function, or a variant of a step function that includes a fade boundary. If the tree is evaluated from the root up, this provides an early-out for entire branches of the tree, whereas if I compile it to a sequential array and evaluate from the start, it will evaluate all leaves first, then the next branch up, and so forth until root. The early-out provided by the non-selected branch of a step function in this case won't happen, so I'd be getting lots of redundant processing.

1

Share this comment


Link to comment

If your bytecode doesn't support conditionals/jumps then that early-out won't translate I guess, yes. Can't tell from that dev blog if they do support something like this.
 
As an aside: Using /arch:SSE2 with MSVC gave me a 10% boost for the multicolor.lua script.
 
BTW, thanks for the second fix.
 
PS: map.lua is fun wink.png

0

Share this comment


Link to comment

Thanks, unbird. I made a couple changes, adding an option in CMake to enable/disable SSE2 (it makes a difference on GCC build as well) as well as an option to choose double or float precision. The double/float conversion is still kind of questionable in my mind given that it was a search/replace with a macro definition for the float type and while I fixed some compile bugs it created, I haven't fully checked for unanticipated side-effects yet. Still, I see a difference of about .5 seconds on multicolor.lua between the GCC double no-SSE build and the GCC float SSE build, so I reckon on more complicated things the savings might be better still. I haven't propagated most of the new changes into the Goblinson Crusoe codebase, so I can't yet test it there. I'll wait until it all stabilizes a bit further before I allow it in to my game.

2

Share this comment


Link to comment

Is it just me or does the second island bear a strong resemblance to a chocolate icecream cone? :p

 

I think SSE would be a huge improvement, as well as optimizing memory transfers (copying stuff back and forth sounds fast but it gets really slow really quickly). Going GPU would be arguably faster but that is probably not realistic for a general-purpose library. Make sure to use the intrinsics, they are easier to use and still allow the compiler to reason about your code, which it can't do if you're writing raw assembly, not as effectively anyway.

1

Share this comment


Link to comment

That's Sierra Chocolate. Cream Peak is at another chunk, though.
must be really hot where you are.

For my MSVC the switch to single precision was surprisingly a huge step back in performance. Take this with a grain of salt, I compared against an earlier version and probably missed something else. Maybe I got some time this weekend to play with a profiler and some compiler flags.

1

Share this comment


Link to comment

Do you have any links or could maybe give a little description on what "twistiness" is? I really want to move onto 3D noise for terrain but I'm having trouble getting it to be less....blobby and bubbly, for lack of better words...

 

-ST

0

Share this comment


Link to comment
@studentTeacher: Here are some images I made for an article explaining all of this stuff. They are 2D, but 3D is just a natural extension of it. (And it's hard to visualize this in 3D, without a bunch of volumetric imaging tools.)
 
1) The divide between solid and open is a step function. Any coordinates with a Y component above the ground threshold are open, any coordinates below it are solid. Without any kind of perturbation, this creates a flat-topped volume, with the ground surface comprising the top of the volume. In 2D, it creates a  region of solid below, open above like this:
minecraft_gradient_select.jpg

2) If a 2D noise function is used to perturb the 3D ground plane up or down (heightmap style) then hills are formed. In essence, any input point that has a given X and Z coordinate, regardless of Y, is "pushed" up or down by some value. All points at that X,Z are pushed by the same amount. This deforms the plane up and down, but does not allow for overhangs or sheer cliffs. In 2D, this is similar to deforming the ground line by a 1D noise function, like this:

minecraft_ground_scaley.jpg

3) In order to generate a ground surface with overhangs and cliffs, you need to perturb the 3D surface by a 3D noise function, rather than a 2D function. This means that each input coordinate is pushed up or down by its own amount, and this amount is not necessarily the same as other points that share X and Z with the point. In 2D, this is similar to perturbing the 2D surface with a 2D noise function. The result is a "frothy" terrain that can have cliffs, overhangs, and even disconnected floating islands:

minecraft_gradient_fractal_perturb.jpg

4) Of course, while overhangs are nice, floating islands really aren't. In the blockworlds example, I take the distortion fractal (called elev/elevscale) and scale its input coordinate by another fractal, twistiness. This fractal is corrected to output values in the range 0.25 to 0.5. When applytwist is called, the effect is that this fractal is called and the value it returns is multiplied by the Y coordinate of the input point before calling the elevation fractal. As this value approaches 0 it has the effect of gradually "morphing" the elevation fractal toward a 2D version. That is, if you scale the input Y coordinate of a point by 0 before calling the function, it is tantamount to calling noise(X,0,Z), which results in effectively a 2D result. As demonstrated above, a 2D fractal won't result in overhangs, cliffs or floating islands. So the closer this scaling value gets to 0, the lower the likelihood of generating these kinds of features. So by scaling down the "twistiness" you tame the fractal and eliminate some of the weirdness. The use of a fractal for scaling here provides some terrain variation, so that some areas are "twistier", or more frothy, than others.

Eliminating the blobbiness and bubbliness is also a factor of lowering the frequency of the elevation function. By lowering the frequency, the features are stretched out across more area.
2

Share this comment


Link to comment

As promised I've played a bit with the flags. I'm still pretty clueless, though. No matter what flags I use, double is always faster. Guess GCC is better at auto-vectorizing - and general optimization at that. VerySleepy tells me the hotspot is - not surprisingly - at anl::gradient_noise/cellular either way (map.lua). Still can't tell you the reason for the difference, sorry (cache issues, alignment ?).

 

Anyway: I don't mind. I'm happy with a scriptable noise library to play with.

 

@Bacterius: I think you just invented "chunk food".

1

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now