1
\$\begingroup\$

My game has a 'chunk' engine similar to Minecraft's but in 2 dimensions. Each chunk is a square of 32 by 32 tiles.

What I want to do is generate a defined shape across multiple chunks without breaking the shape.

This is made difficult by the fact that chunks are generated one chunk at a time in unknown intervals of time, so I cannot place a structure after the amount of chunks it needs to fit in are generated, as the player might move into the area before that time.

Another problem is that I cannot simply tile the shape uniformly because the shape needs to be exactly one tile above the surface, which is a heightmap generated using simplex noise, so it is not flat.

Is there any way I can generate this structure from one point of origin placed at random intervals over a heightmap that is known?

Example of what I want: Example of across-chunk generation

Grey Lines - chunk bounds

White Tiles - structure generation

Blue Tiles - known 1D heightmap

How can this be done?

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I have also implemented a chunked engine. The best way to think of it is to just think of the chunks as memory storage locations rather than as actual structures of the world. Then, whenever you generate content, generate it as though you had a giant array of arbitrary size.

Just implement some functions like

Voxel* GetVoxelAt(int x, int y, int z);

Which will end up looking like this:

Voxel* GetVoxelAt(int x, int y, int z)
{
    Chunk* chunk = GetChunkAt(x, y, z);


    if (chunk) return chunk->GetVoxelAt(x, y, z);
    else return NULL;
}

Then you can happily do all of your generation, logic, etc. in the global space without having to worry about chunks. Now as for your question of time, well you need to defer any generation you do to another system that waits for the chunk to exist. You can simply generate the chunks whenever content needs to be placed there, for instance, or you can just put the content on a "To generate" list that gets checked whenever the chunk that's needed gets created.

Another option is to store all of your content as "templates" in the global space. When chunks get generated, they check each of the templates to see if they intersect them. If they do, the content gets generated there.

In my game, I just have a list of templates, and each template is just a list of voxel relative to some other voxel. I also have a hack called "pillars" which place voxels all the way from the bottom of the template to the land so that all structures are "supported". Then, when I generate a new chunk, I iterate through the incomplete templates to find one that intersects the chunk. Then, I place all of the blocks and pillars that the template specifies in the new chunk, and mark those blocks as completed. When all the blocks in a template are completed, its removed from the template list.

EDIT Template list example pseudocode:

// Represents a 2D template of voxel types.
class Template
{
    int sizeX;
    int sizeY;
    VoxelType[][] values;
}


// Represents a template at a specific location
class TemplateInstance
{
    Template template;
    bool[][] completed;
    int xLocation;
    int yLocation;
    Set<ChunkID> intersectingChunks;


   // Compute all potential chunks that could intersect this template
   void ComputeIntersectingChunks()
   {
        for (int x = xLocation; x < template.sizeX + xLocation; x++)
        {
             for (int y = yLocation; y < template.sizeY + yLocation; y++)
             {
                 ChunkID id = GetChunkIDAt(x, y);

                 if(!intersectingChunks.contains(id)) intersectingChunks.add(id);
             }
        }
   }

   // Add this instance to a hash map of all chunks to list of instances
   void AddInstance(HashMap<ChunkID, List<TemplateInstance> > instances)
   {
       for (ChunkID id in intersectingChunks)
       {
           instances[id].add(this);
       }
   }

   // Remove this instance from the hash map of instances
   void RemoveInstance(HashMap<ChunkID, List<TemplateInstance> > instances)
   {

      for (ChunkID id in intersectingChunks)
      {
          instances[id].remove(this);
      }
   }

   // Given a specific chunk, generate all the voxels in that chunk
   // belonging to this instance (does not include "pillars")
   void Generate(Chunk chunk)
   {
        for (int dx = 0; dx < template.sizeX; dx++)
        {
             int x = dx + xLocation;
             for (int dy = 0; dy < template.sizeY; dy++)
             {
                 int y = dy + yLocation;
                 if(!chunk.Contains(x, y)) continue;
                 Voxel* voxel = chunk.GetVoxelAt(x, y);
                 voxel.type = template.values[dx][dy];
                 completed[dx][dy] = true;
             }
         }

   }

   // True when all the voxels have been placed.
   bool IsComplete()
   {
      return *all completed*
   }
}


// Outer function generates all the templates intersecting a chunk
void GenerateTemplates(Chunk chunk, HashMap<ChunkID, List<TemplateInstance> > instances)
{
    List<TemplateInstance> intersecting = instances[chunk.ID];

    for (TemplateInstance template in intersecting)
    {
        template.Generate(chunk);
        if (template.IsComplete())
        {
           template.RemoveInstance(instances);
        }
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ The first option is something I already do (both the GetVoxelAt and the list of chunks to be generated) and I have left using the global coord system for the reason of speed when generating chunks (the rest of the game does use it). As for the second option, wouldn't that be quite slow, especially when having a lot of templates? \$\endgroup\$
    – ben
    Nov 20, 2014 at 19:41
  • 2
    \$\begingroup\$ If you store them as a simple list that you iterate over, it will be linear in the number of templates. You could do something more clever by instead storing templates in a hash map of chunk IDs to templates that intersect those chunks. That would be very fast, as it would have O(1) lookup times. \$\endgroup\$
    – mklingen
    Nov 20, 2014 at 20:43
  • \$\begingroup\$ Could you whip up a quick code example of this method? Thanks. \$\endgroup\$
    – ben
    Nov 20, 2014 at 20:59
  • \$\begingroup\$ Yeah I just added one \$\endgroup\$
    – mklingen
    Nov 20, 2014 at 21:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .