How to create a procedural generated forests?

Question

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

Comments

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

Answer 1

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

Comments

@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/