How to generate trees or other structures over chunks in a 2D Minecraft-like game

I am trying to create a 2D Minecraft-like game, and I am running into a problem. I’m trying to generate trees on top of the terrain. The terrain is generated with simplex noise, and it is split up into 8×8 chunks, the game generates new chunks if necessary every time the player moves. I tried generating trees by randomly choosing a location on top of the terrain, and setting the blocks above it to the blocks I wanted, then I ran into another problem. The trees might go into neighboring chunks. I tried to solve this problem by storing the parts of a tree that are in other chunks in a dictionary, and generating them from the dictionary when the other chunk is generated, but there is another problem. Sometimes the chunk neighboring the chunk that contains most of the tree has already been generated, so I cannot overwrite it when the chunk that has the tree gets generated… I am slightly confused on how to get this to work.

This is the code for generating new chunks, where the parameters x and y are the location of the chunk to generate:

def generate_chunk(x, y):
    chunk_data = {}
    for y_pos in range(CHUNK_SIZE):
        for x_pos in range(CHUNK_SIZE):
            block = (x * CHUNK_SIZE + x_pos, y * CHUNK_SIZE + y_pos)
            block_name = ""
            height = int(noise.noise2d(block[0]*0.1, 0)*5)
            if block[1] == 5-height:
                block_name = "grass_block"
            elif 5-height < block[1] < 10-height:
                block_name = "dirt"
            elif block[1] >= 10-height:
                block_name = "stone"
            if block_name != "":
                chunk_data[block] = block_name
    return chunk_data

Here is the main loop where the chunks near the player are generated and are temporarily deleted and saved when the player leaves:

running = True
while running:
    dt = clock.tick(FPS) / 16
    pygame.display.set_caption(f"2D Minecraft | FPS: {int(clock.get_fps())}")

    for event in pygame.event.get():
        if event.type == QUIT:
            running = False

    rendered_chunks = []
    for y in range(int(HEIGHT/(CHUNK_SIZE*BLOCK_SIZE)+2)):
        for x in range(int(WIDTH/(CHUNK_SIZE*BLOCK_SIZE)+2)):
            chunk = (
                x - 1 + int(round(camera.pos.x / (CHUNK_SIZE * BLOCK_SIZE))), 
                y - 1 + int(round(camera.pos.y / (CHUNK_SIZE * BLOCK_SIZE)))
            )
            rendered_chunks.append(chunk)
            if chunk not in chunks:
                chunks[chunk] = Chunk(chunk)
    unrendered_chunks = []
    for y in range(int(HEIGHT/(CHUNK_SIZE*BLOCK_SIZE)+4)):
        for x in range(int(WIDTH/(CHUNK_SIZE*BLOCK_SIZE)+4)):
            chunk = (
                x - 2 + int(round(camera.pos.x / (CHUNK_SIZE * BLOCK_SIZE))), 
                y - 2 + int(round(camera.pos.y / (CHUNK_SIZE * BLOCK_SIZE)))
            )
            try: chunks[chunk]
            except: pass
            else:
                if chunk not in rendered_chunks:
                    unrendered_chunks.append(chunk)
    for chunk in unrendered_chunks:
        for block in chunks[chunk].block_data:
            if block in blocks:
                blocks[block].kill()
                del blocks[block]

    camera.update()
    player.update()
    screen.fill((135, 206, 250))
    for chunk in rendered_chunks:
        chunks[chunk].render()
    player.draw(screen)
    pygame.display.flip()

Here are the Block class and the Chunk class:

class Block(pygame.sprite.Sprite):
    def __init__(self, chunk, pos, name):
        pygame.sprite.Sprite.__init__(self)
        blocks[tuple(pos)] = self
        self.name = name
        self.chunk = chunk
        self.coords = vec(pos)
        self.pos = self.coords * BLOCK_SIZE
        self.image = block_textures[self.name]
        self.rect = self.image.get_rect()

    def update(self):
        self.rect.topleft = self.pos - camera.pos

    def draw(self, screen):
        screen.blit(self.image, self.rect.topleft)

class Chunk(object):
    def __init__(self, pos):
        self.pos = pos
        self.block_data = generate_chunk(pos[0], pos[1])
        for block in self.block_data:
            blocks[block] = Block(self, block, self.block_data[block])

    def render(self):
        if self.pos in rendered_chunks:
            for block in self.block_data:
                try: blocks[block]
                except:
                    blocks[block] = Block(self, block, self.block_data[block])
                blocks[block].update()
                blocks[block].draw(screen)
            pygame.draw.rect(screen, (255, 255, 0), (self.pos[0]*CHUNK_SIZE*BLOCK_SIZE-camera.pos[0], self.pos[1]*CHUNK_SIZE*BLOCK_SIZE-camera.pos[1], CHUNK_SIZE*BLOCK_SIZE, CHUNK_SIZE*BLOCK_SIZE), width=1)

The minimal reproducible code, I think all the information needed would be above but just in case you need the rest:

import pygame
from pygame.locals import *
from random import *
from math import *
import json
import os
import opensimplex
FPS = 60
WIDTH, HEIGHT = 1200, 600
SCR_DIM = (WIDTH, HEIGHT)
GRAVITY = 0.5
SLIDE = 0.3
TERMINAL_VEL = 24
BLOCK_SIZE = 64
CHUNK_SIZE = 8
SEED = randint(-2147483648, 2147483647)
pygame.init()
screen = pygame.display.set_mode((WIDTH, HEIGHT), HWSURFACE | DOUBLEBUF)
pygame.display.set_caption("2D Minecraft")
clock = pygame.time.Clock()
mixer = pygame.mixer.init()
vec = pygame.math.Vector2
noise = opensimplex.OpenSimplex(seed=SEED)
seed(SEED)
block_textures = {}
for img in os.listdir("res/textures/blocks/"):
block_textures[img[:-4]] = pygame.image.load("res/textures/blocks/"+img).convert_alpha()
for image in block_textures:
block_textures[image] = pygame.transform.scale(block_textures[image], (BLOCK_SIZE, BLOCK_SIZE))
def intv(vector):
return vec(int(vector.x), int(vector.y))
def inttup(tup):
return (int(tup[0]), int(tup[1]))
def block_collide(ax, ay, width, height, b):
a_rect = pygame.Rect(ax-camera.pos.x, ay-camera.pos.y, width, height)
b_rect = pygame.Rect(b.pos.x-camera.pos.x, b.pos.y-camera.pos.y, BLOCK_SIZE, BLOCK_SIZE)
if a_rect.colliderect(b_rect):
return True
return False
class Camera(pygame.sprite.Sprite):
def __init__(self, master):
self.master = master
self.pos = self.master.size / 2
self.pos = self.master.pos - self.pos - vec(SCR_DIM) / 2 + self.master.size / 2
def update(self):
tick_offset = self.master.pos - self.pos - vec(SCR_DIM) / 2 + self.master.size / 2
if -1 < tick_offset.x < 1:
tick_offset.x = 0
if -1 < tick_offset.y < 1:
tick_offset.y = 0
self.pos += tick_offset / 10
class Player(pygame.sprite.Sprite):
def __init__(self):
pygame.sprite.Sprite.__init__(self)
self.size = vec(0.225*BLOCK_SIZE, 1.8*BLOCK_SIZE)
self.width, self.height = self.size.x, self.size.y
self.start_pos = vec(0, 3) * BLOCK_SIZE
self.pos = vec(self.start_pos)
self.coords = self.pos // BLOCK_SIZE
self.vel = vec(0, 0)
self.max_speed = 5.306
self.jumping_max_speed = 6.6
self.rect = pygame.Rect((0, 0, 0.225*BLOCK_SIZE, 1.8*BLOCK_SIZE))
self.bottom_bar = pygame.Rect((self.rect.x+1, self.rect.bottom), (self.width-2, 1))
self.on_ground = False
def update(self):
keys = pygame.key.get_pressed()
if keys[K_a]:
if self.vel.x > -self.max_speed:
self.vel.x -= SLIDE
elif self.vel.x < 0:
self.vel.x += SLIDE
if keys[K_d]:
if self.vel.x < self.max_speed:
self.vel.x += SLIDE
elif self.vel.x > 0:
self.vel.x -= SLIDE
if keys[K_w] and self.on_ground:
self.vel.y = -9.2
self.vel.x *= 1.1
if self.vel.x > self.jumping_max_speed:
self.vel.x = self.jumping_max_speed
elif self.vel.x < -self.jumping_max_speed:
self.vel.x = -self.jumping_max_speed
if -SLIDE < self.vel.x < SLIDE:
self.vel.x = 0
self.vel.y += GRAVITY
if self.vel.y > TERMINAL_VEL:
self.vel.y = TERMINAL_VEL
self.move()
self.bottom_bar = pygame.Rect((self.rect.left+1, self.rect.bottom), (self.width-2, 1))
for block in blocks:
if self.bottom_bar.colliderect(blocks[block].rect):
self.on_ground = True
break
else:
self.on_ground = False
if self.on_ground:
self.vel.x *= 0.99
self.coords = self.pos // BLOCK_SIZE
self.chunk = self.coords // CHUNK_SIZE
self.rect.topleft = self.pos - camera.pos
def draw(self, screen):
pygame.draw.rect(screen, (0, 0, 0), self.rect)
def move(self):
for y in range(4):
for x in range(3):
try:
block = blocks[(int(self.coords.x-1+x), int(self.coords.y-1+y))]
except:
pass
else:
if self.vel.y < 0:
if block_collide(floor(self.pos.x), floor(self.pos.y+self.vel.y), self.width, self.height, block):
self.pos.y = floor(block.pos.y + BLOCK_SIZE)
self.vel.y = 0
elif self.vel.y >= 0:
if self.vel.x <= 0:
if block_collide(floor(self.pos.x), ceil(self.pos.y+self.vel.y), self.width, self.height, block):
self.pos.y = ceil(block.pos.y - self.height)
self.vel.y = 0
elif self.vel.x > 0:
if block_collide(ceil(self.pos.x), ceil(self.pos.y+self.vel.y), self.width, self.height, block):
self.pos.y = ceil(block.pos.y - self.height)
self.vel.y = 0
if self.vel.x < 0:
if block_collide(floor(self.pos.x+self.vel.x), floor(self.pos.y), self.width, self.height, block):
self.pos.x = floor(block.pos.x + BLOCK_SIZE)
self.vel.x = 0
elif self.vel.x >= 0:
if block_collide(ceil(self.pos.x+self.vel.x), ceil(self.pos.y), self.width, self.height, block):
self.pos.x = ceil(block.pos.x - self.width)
self.vel.x = 0
self.pos += self.vel
class Block(pygame.sprite.Sprite):
def __init__(self, chunk, pos, name):
pygame.sprite.Sprite.__init__(self)
blocks[tuple(pos)] = self
self.name = name
self.chunk = chunk
self.coords = vec(pos)
self.pos = self.coords * BLOCK_SIZE
self.image = block_textures[self.name]
self.rect = self.image.get_rect()
def update(self):
self.rect.topleft = self.pos - camera.pos
def draw(self, screen):
screen.blit(self.image, self.rect.topleft)
class Chunk(object):
def __init__(self, pos):
self.pos = pos
self.block_data = generate_chunk(pos[0], pos[1])
for block in self.block_data:
blocks[block] = Block(self, block, self.block_data[block])
def render(self):
if self.pos in rendered_chunks:
for block in self.block_data:
try: blocks[block]
except:
blocks[block] = Block(self, block, self.block_data[block])
blocks[block].update()
blocks[block].draw(screen)
pygame.draw.rect(screen, (255, 255, 0), (self.pos[0]*CHUNK_SIZE*BLOCK_SIZE-camera.pos[0], self.pos[1]*CHUNK_SIZE*BLOCK_SIZE-camera.pos[1], CHUNK_SIZE*BLOCK_SIZE, CHUNK_SIZE*BLOCK_SIZE), width=1)
def generate_chunk(x, y):
chunk_data = {}
for y_pos in range(CHUNK_SIZE):
for x_pos in range(CHUNK_SIZE):
block = (x * CHUNK_SIZE + x_pos, y * CHUNK_SIZE + y_pos)
block_name = ""
height = int(noise.noise2d(block[0]*0.1, 0)*5)
if block[1] == 5-height:
block_name = "grass_block"
elif 5-height < block[1] < 10-height:
block_name = "dirt"
elif block[1] >= 10-height:
block_name = "stone"
if block_name != "":
chunk_data[block] = block_name
return chunk_data
blocks = {}
chunks = {}
player = Player()
camera = Camera(player)
running = True
while running:
dt = clock.tick(FPS) / 16
pygame.display.set_caption(f"2D Minecraft | FPS: {int(clock.get_fps())}")
for event in pygame.event.get():
if event.type == QUIT:
running = False
rendered_chunks = []
for y in range(int(HEIGHT/(CHUNK_SIZE*BLOCK_SIZE)+2)):
for x in range(int(WIDTH/(CHUNK_SIZE*BLOCK_SIZE)+2)):
chunk = (
x - 1 + int(round(camera.pos.x / (CHUNK_SIZE * BLOCK_SIZE))), 
y - 1 + int(round(camera.pos.y / (CHUNK_SIZE * BLOCK_SIZE)))
)
rendered_chunks.append(chunk)
if chunk not in chunks:
chunks[chunk] = Chunk(chunk)
unrendered_chunks = []
for y in range(int(HEIGHT/(CHUNK_SIZE*BLOCK_SIZE)+4)):
for x in range(int(WIDTH/(CHUNK_SIZE*BLOCK_SIZE)+4)):
chunk = (
x - 2 + int(round(camera.pos.x / (CHUNK_SIZE * BLOCK_SIZE))), 
y - 2 + int(round(camera.pos.y / (CHUNK_SIZE * BLOCK_SIZE)))
)
try: chunks[chunk]
except: pass
else:
if chunk not in rendered_chunks:
unrendered_chunks.append(chunk)
for chunk in unrendered_chunks:
for block in chunks[chunk].block_data:
if block in blocks:
blocks[block].kill()
del blocks[block]
camera.update()
player.update()
screen.fill((135, 206, 250))
for chunk in rendered_chunks:
chunks[chunk].render()
player.draw(screen)
pygame.display.flip()
pygame.quit()
quit()

(btw the yellow lines are the chunk borders)

Answer

The general idea is to realize how big a structure (e.g. a Tree) can be, calculate how many chunks it can span and then check when generating chunk (x, y) all chunks around it. This could be done with something like this:

TREE_SHAPE = {
(0, 0): "oak_log",
(0, -1): "oak_log",
(0, -2): "oak_log",
(0, -3): "oak_log",
(0, -4): "oak_leaves",
(1, -4): "oak_leaves",
(2, -4): "oak_leaves",
(3, -4): "oak_leaves",
(-1, -4): "oak_leaves",
(-2, -4): "oak_leaves",
(-3, -4): "oak_leaves",
}
MAX_TREE_SIZE = (max(x for x, y in TREE_SHAPE) - min(x for x, y in TREE_SHAPE) + 1,
max(y for x, y in TREE_SHAPE) - min(y for x, y in TREE_SHAPE) + 1)
CHUNKS_TO_CHECK = int(ceil(MAX_TREE_SIZE[0] / CHUNK_SIZE)), int(ceil(MAX_TREE_SIZE[1] / CHUNK_SIZE))
def generate_tree(base):
return {(base[0] + offset[0], base[1] + offset[1]): block for offset, block in TREE_SHAPE.items()}
# Replace everything above with however you want to generate Trees.
# It might be worth factoring that out into a StructureGenerator class.
def get_trees(x, y):
out = []
seed(SEED + x * CHUNK_SIZE + y)  # Make sure this function always produces the same output
for _ in range(CHUNK_SIZE // 8):  # At most one Tree attempt per 4 blocks
block_x = x * CHUNK_SIZE + randrange(0, CHUNK_SIZE)
grass_y = int(5 - noise.noise2d(block_x * 0.1, 0) * 5)  # Same as in generate_chunk
if not 0 <= grass_y - y * CHUNK_SIZE < CHUNK_SIZE:  # Tree spot not in this chunk
continue
out.append(generate_tree((block_x, grass_y)))
return out
def generate_chunk(x, y):
chunk_data = {}
# ... Your old code
for ox in range(-CHUNKS_TO_CHECK[0], CHUNKS_TO_CHECK[0] + 1):
for oy in range(-CHUNKS_TO_CHECK[1], CHUNKS_TO_CHECK[1] + 1):
# For each Chunk around us (and ourself), check which trees there are.
trees = get_trees(x + ox, y + oy)
for tree in trees:
for block, block_name in tree.items():
if 0<=block[0]-x*CHUNK_SIZE<CHUNK_SIZE and 0<=block[0]-x*CHUNK_SIZE<CHUNK_SIZE:
# This block is in this chunk
chunk_data[block] = block_name
return chunk_data
Source: stackoverflow
The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 .