+2 votes

How to generate a forest using GDScript? Can you give me few advices how to start?

in Engine by (246 points)

What does generate Forest mean? Generate trees? Place trees on a surface? What about shrubs and gras?
You have to be more specific!

Researching Poisson disc sampling might be a good start. It helps avoid overlapping trees. Here is a video that discusses it.

@klaas I mean trees, bushes, grass, stones. I have some terrain and I need to add areas where forests will grow and it should be generated.

unity video but looks like a good option too maybe
https://www.youtube.com/watch?v=7WcmyxyFO7o

1 Answer

+1 vote
Best answer

enter image description here

one option is to just the the cellular cave generation algorithm and use the 'caves' for placing trees, i use this to place clustered groups of trees, flowers, and grass in a tile map and even bodies of water

const _standardChance := 0.4
const _standardBirth := 4
const _standardDeath := 3
const _standardSteps := 10

func _getAdjacentCount(list: Array, x: int, y: int) -> int:
    var count := 0
    for yy in range(-1, 2):
        for xx in range(-1, 2):
            if not ((xx == 0) and (yy == 0)):
                var new := Vector2(xx + x, yy + y)
                if _level.insideMapV(new):
                    if list[Utility.indexV(new, _width)]:
                        count += 1
                else:
                    count += 1
    return count

func _getCellularList(steps: int, chance: float, birth: int, death: int) -> Array:
    var list := Utility.repeat(false, _width * _height)
    for i in range(list.size()):
        list[i] = Random.nextFloat() <= chance
    for _i in range(steps):
        var temp := Utility.repeat(false, _width * _height)
        for y in range(_height):
            for x in range(_width):
                var adjacent := _getAdjacentCount(list, x, y)
                var index := Utility.index(x, y, _width)
                var value: bool = list[index]
                if value:
                    value = value and adjacent >= death
                else:
                    value = value or adjacent > birth
                temp[index] = value
        list = temp.duplicate()
    if steps > 0 and Random.nextBool():
        _removeSmall(list)
    return list

you can also use a disjoint set to split the caves and remove or use only some

by (1,659 points)
selected by

@rakkarage Can you explain what this functions do?

Is it applicable to 3D?

Yes, but of course with some rewriting.

@rakkarage Where is _removeSmall defined? I don't see it

extends Object
class_name DisjointSet

var _parent : Array

func _init(count: int) -> void:
    _parent = Utility.repeat(-1, count)

func find(i: int) -> int:
    if _parent[i] < 0:
        return i
    else:
        var parent := find(_parent[i])
        _parent[i] = parent
        return parent

func union(i: int, j: int) -> void:
    var pi := find(i)
    var pj := find(j)
    if pi < pj:
        _parent[pi] -= 1
        _parent[pj] = pi
    elif pi > pj:
        _parent[pi] = pj
        _parent[pj] -= 1

func split(list: Array) -> Dictionary:
    var groups := {}
    for i in range(_parent.size()):
        if not list[i]:
            var root := find(i)
            if not groups.has(root):
                groups[root] = []
            groups[root].append(i)
    return groups
func _combineLists(destination: Array, source: Array) -> void:
    var random := Random.nextBool()
    for y in range(_height):
        for x in range(_width):
            var index := Utility.index(x, y, _width)
            destination[index] = (destination[index] and source[index]) if random else (destination[index] or source[index])

func _biggest(list: Array) -> Array:
    var disjointSet := _disjointSetup(list)
    var caves := disjointSet.split(list)
    _removeSmallCaves(caves, list)
    return caves.values()[0]

func _bigEnough(list: Array) -> bool:
    return _biggest(list).size() > 4

func _unionAdjacent(disjointSet: DisjointSet, list: Array, x: int, y: int) -> void:
    for yy in range(-1, 2):
        for xx in range(-1, 2):
            if not ((xx == 0) and (yy == 0)) and _level.insideMap(x + xx, y + yy):
                var index1 := Utility.index(x + xx, y + yy, _width)
                if not list[index1]:
                    var root1 := disjointSet.find(index1)
                    var index0 := Utility.index(x, y, _width)
                    var root0 := disjointSet.find(index0)
                    if root0 != root1:
                        disjointSet.union(root0, root1)

func _disjointSetup(list: Array) -> DisjointSet:
    var disjointSet := DisjointSet.new(_width * _height)
    for y in range(_height):
        for x in range(_width):
            if not list[Utility.index(x, y, _width)]:
                _unionAdjacent(disjointSet, list, x, y)
    return disjointSet

func _removeSmall(list: Array) -> void:
    _removeSmallCaves(_disjointSetup(list).split(list), list)

func _removeSmallCaves(caves: Dictionary, list: Array) -> void:
    var biggest := 0
    var biggestKey := 0
    for key in caves.keys():
        var size: int = caves[key].size()
        if size > biggest:
            biggest = size
            biggestKey = key
    var delete := []
    for key in caves.keys():
        if key != biggestKey:
            delete.append(key)
    for key in delete:
        if list != null:
            var cave: Array = caves[key]
            for i in cave:
                list[i] = true
        Utility.stfu(caves.erase(key))

func _isCaveEdge(list: Array, x: int, y: int) -> bool:
    var edge := false
    for yy in range(-1, 2):
        for xx in range(-1, 2):
            if not ((xx == 0) and (yy == 0)):
                var new := Vector2(x + xx, y + yy)
                if _level.insideMapV(new) and not list[Utility.indexV(new, _width)]:
                    edge = true
    return edge

func _outlineCaves(list: Array) -> void:
    for y in range(_height):
        for x in range(_width):
            if list[Utility.index(x, y, _width)]:
                if _isCaveEdge(list, x, y):
                    _setWall(x, y)
static func index(x: int, y: int, width: int) -> int:
    return int(y * width + x)

static func position(index: int, width: int) -> Vector2:
    var y := int(index / float(width))
    var x := int(index - width * y)
    return Vector2(x, y)

func _printArray(array: Array) -> void:
    var output := ""
    for y in range(_height):
        for x in range(_width):
            output += "1" if array[Utility.index(x, y, _width)] else "0"
        output += "\n"
    output += "\r"
    print(output)

@rakkarage Thank you very much for you help, but can you explain in two words what does this code do? What is it logic?

call getCellularList to get a list of bools that defines the caves (0 for floor and 1 for wall) (or 0 for tree and 1 for not tree) if that is all you wanna do can just draw (trees) or anything based on those bools

or call it multiple times with different settings (maybe removing small) and then combine them

use _printArray to visualize these 'caves'

the disjoint set is only needed when you want to split caves into groups (sometimes it is just one group anyway) or check the size of the room it split the cave into a dictionary of each individual cave { 0: [0, 1, 2] 1: [3, 4, 5] } so i can work on 'caves' individually

(i am sure this code could be fixed up a bit but)

sometimes when it is defining rooms i check to make sure the room is big enough for stairs up and stairs down

when defining caves i split caves into rooms and put up and down stairs in same biggest cave

sometimes when defining caves I split caves into rooms and remove all small rooms

sometimes when defining caves i split caves and outline caves in fancy walls because they are initialized with plain walls

sometimes when defining forests i split 'caves' and replace some caves with cut down trees or pick a random point in a cave and cut down all trees in a random direction so it looks like someone was working

here is working example and link to code
takes a while to get a 'forest' level sometimes
https://gotm.io/henry-software/pixelleveltest/

Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to webmaster@godotengine.org with your username.