0

Description

"In previous contributions, we have seen [how to compute (and display) terrain based on small heightmaps](https:\/\/thegodotbarn.com\/contributions\/snippet\/422\/small-terrain-generator). Now is the time to add some water to those barren environments.\r\n\r\nThe scope of this contribution is not to display water in terrain (this will be the subject of another contribution). Here, we will only compute the (absolute) water level, flowing through a heightmap from a designated source.\r\n\r\n## Parameters\r\n\r\nThe function below (`computer_water_from`) takes the following parameters:\r\n* **source** : The starting point of the water flow\r\n* **heights** : The heightmap, stored in a `PackedFloat64Array`\r\n* **size** : The size of the map\r\n* **required_output** : Optional output flow. If set to `0` or below, the algorithm stops as soon as it reaches the border. Else, it will wait until one of the exit point reaches the desired output level.\r\n\r\nIt returns a `PackedFloat64Array` containing the absolute level of water for each cell (or `NaN` if there's no water). This means that the amount of water for a given cell is `water[i] - heights[i]`.\r\n\r\n## Final Words (for now ...)\r\n\r\nThis code is fitted for square cell terrain. The propagation only follows the four main directions. However, you can modify the `AROUND` constant array to expand (or restrict) water propagation (to the eight neighbors for example).\r\n\r\nA particular attention has to be paid to the source selection. Not all points in a heightmap are suitable for a source. Choosing the right source (or sources) is the matter of another algorithm, especially if you're aiming at a particular water coverage ratio.\r\n\r\n\r\n_The source set at the center of the map is not always the best choice_\r\n\r\nAnd finally, keep in mind that this code is executed as a script. It performs well on small heightmap but might not be appropriate for large terrains (even if the current performances for a 256x256 terrain on a Core i5-13600KF for a single source goes from 10ms for small rivers to 80ms for sets of big lakes)."

Screenshots

Main code

const AROUND : Array[Vector2i] = [
	Vector2i(-1, 0), Vector2i(0, -1), Vector2i(1, 0), Vector2i(0, 1)
]

func compute_water_from(source : Vector2i, heights : PackedFloat64Array, size : Vector2i, required_output : float = 1.) -> PackedFloat64Array:
	assert(source.x < size.x and source.y < size.y)
	var cell_count : int = size.x * size.y
	var water : PackedFloat64Array = PackedFloat64Array()
	water.resize(cell_count); water.fill(NAN)

	var sort_func : Callable = func (a : Vector2i, b : Vector2i) -> bool:
		var ai : int = a.y * size.x + a.x; var bi : int = b.y * size.x + b.x
		return heights[ai] < heights[bi]

	var compute : PackedInt32Array = PackedInt32Array()
	compute.resize(cell_count); compute.fill(-1)

	var queue : Array[Vector2i] = [ source ]
	var stack : Array[Vector2i] = [ source ]
	var id : int = 0

	var lowest_output : float = NAN
	var current_output : float = NAN


	while not (queue.is_empty() or (is_finite(current_output) and (current_output - lowest_output) >= required_output)):
		id += 1
		var current : Vector2i = queue.pop_front()
		var idx : int = current.y * size.x + current.x
		if compute[idx] > 0: continue
		compute[idx] = id
		stack.append(current)
		for a : Vector2i in AROUND:
			var v : Vector2i = current + a

			if v.x < 0 or v.y < 0 or v.x == size.x or v.y == size.y:
				if not is_finite(lowest_output):
					lowest_output = heights[idx]
					current_output = lowest_output
				elif heights[idx] < lowest_output:
					lowest_output = heights[idx]
				else:
					current_output = heights[idx]
				break

			var vidx : int = v.y * size.x + v.x
			if compute[vidx] > 0:
				continue
			# Add to queue
			var i : int = max(0, queue.bsearch_custom(v, sort_func))
			queue.insert(i, v)

	# Resolve water level
	while not stack.is_empty():
		var current : Vector2i = stack.pop_back()
		var idx : int = current.y * size.y + current.x
		if is_finite(water[idx]): continue
		var max_id : int = compute[idx]
		var water_level : float = heights[idx]
		queue.clear();queue.append(current)
		while not queue.is_empty():
			var fill : Vector2i = queue.pop_back()
			var fidx : int = fill.y * size.x + fill.x
			if is_finite(water[fidx]): continue
			water[fidx] = water_level
			for a : Vector2i in AROUND:
				var t : Vector2i = fill + a
				if t.x < 0 or t.y < 0 or t.x == size.x or t.y == size.y: continue
				var tidx : int = t.y * size.x + t.x
				if compute[tidx] > -1 and compute[tidx] < max_id and heights[tidx] <= water_level:
					queue.append(t)
	return water

Comments