How Fast is Fast Enough?

Something I was thinking on the way home: in real-time procedural world generation how fast do we have to be able to create the world in real-time? In a procedural and semi-infinite world like MineCraft the game only generates and saves what the player has explored for obvious reasons. As the player moves around and explores the game has to generate new areas as it comes to them. It has to be in “real time” as we would prefer not to have stutters or even worse, pop-up “loading” messages, forcing the player to wait while we create the world around them.

As an example let’s consider a MineCraft-like block world. It has 1 meter sized blocks and 16x16x128 block chunks, like MineCraft, and the viewing distance is a 9×9 chunks, or 144×144 blocks, with the player at the center.  As the player walks in one direction and crosses a chunk boundary the game has to generate new chunks in the distance which, in this case is 9 chunks, or 32768 blocks. There are corner cases when the player is walking perfectly on the X-Y diagonal where we might need to create 17 chunks at a time but we’ll focus on the average case for now.

Assuming the player is running at full speed in one direction at 4 m/s the resulting chunk generation rate is 2.25 chunks/sec. This basically means that if we had the chunks being generated in the background thread and we could perfectly predict what chunks were needed next, then the minimum chunk creation rate would be 2.25 chunks/sec. Since we will never be able to perfectly predict where the player will go next in practice we will likely need a higher chunk creation rate.

In a world with a larger view distance, say 17×17 chunks, the minimum chunk creation rate is increased to 4.25 chunks/sec. With a very large view distance, 65×65, it increases to 16.25 chunks/sec.

Why does this matter? It matters because if we want a real-time world generation with no “pauses” as the player explores it we have to be careful about the complexity and time required for the world generation. Simple methods like plasma/mid-point displacement are relatively quick but adding more complex generation like ridged-multi noise can be orders of magnitude slower. For example, in some older tests a 256x256x256 block world was created in 2 sec with simple noise but adding caves via ridged-multi noise raised that up to 60 sec. In our prior chunk creation rate examples this corresponds to a rate of 256 chunks/sec and 8.5 chunks/sec respectively.

So ultimately, while more complex world generation may be interesting and desired it is ultimately linked to the size of world we’d like to display. A larger world display, even with some Level-Of-Detail system may require a more simplistic world generation.


This entry was posted in design, game and tagged , , , . Bookmark the permalink.

Leave a Reply

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


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>