package ru.dbotthepony.kstarbound.server.world

import com.github.benmanes.caffeine.cache.Caffeine
import com.google.gson.JsonArray
import com.google.gson.JsonObject
import it.unimi.dsi.fastutil.ints.IntArraySet
import it.unimi.dsi.fastutil.objects.ObjectArrayList
import it.unimi.dsi.fastutil.objects.ObjectOpenHashSet
import kotlinx.coroutines.CoroutineScope
import kotlinx.coroutines.SupervisorJob
import kotlinx.coroutines.asCoroutineDispatcher
import kotlinx.coroutines.async
import kotlinx.coroutines.cancel
import kotlinx.coroutines.delay
import kotlinx.coroutines.future.asCompletableFuture
import kotlinx.coroutines.future.await
import ru.dbotthepony.kommons.gson.JsonArrayCollector
import ru.dbotthepony.kommons.gson.contains
import ru.dbotthepony.kommons.gson.get
import ru.dbotthepony.kommons.gson.set
import ru.dbotthepony.kstarbound.math.AABBi
import ru.dbotthepony.kommons.util.KOptional
import ru.dbotthepony.kstarbound.math.vector.Vector2i
import ru.dbotthepony.kstarbound.Globals
import ru.dbotthepony.kstarbound.Starbound
import ru.dbotthepony.kstarbound.defs.world.CelestialBaseInformation
import ru.dbotthepony.kstarbound.defs.world.CelestialConfig
import ru.dbotthepony.kstarbound.defs.world.CelestialParameters
import ru.dbotthepony.kstarbound.fromJson
import ru.dbotthepony.kstarbound.io.BTreeDB5
import ru.dbotthepony.kstarbound.json.jsonArrayOf
import ru.dbotthepony.kstarbound.json.mergeJson
import ru.dbotthepony.kstarbound.json.readJsonArrayInflated
import ru.dbotthepony.kstarbound.json.readJsonElementInflated
import ru.dbotthepony.kstarbound.json.writeJsonArrayDeflated
import ru.dbotthepony.kstarbound.json.writeJsonElementDeflated
import ru.dbotthepony.kstarbound.math.Line2d
import ru.dbotthepony.kstarbound.math.vector.Vector3i
import ru.dbotthepony.kstarbound.util.CarriedExecutor
import ru.dbotthepony.kstarbound.util.ScheduledCoroutineExecutor
import ru.dbotthepony.kstarbound.util.binnedChoice
import ru.dbotthepony.kstarbound.util.paddedNumber
import ru.dbotthepony.kstarbound.util.random.AbstractPerlinNoise
import ru.dbotthepony.kstarbound.util.random.nextRange
import ru.dbotthepony.kstarbound.util.random.random
import ru.dbotthepony.kstarbound.util.random.staticRandom64
import ru.dbotthepony.kstarbound.util.supplyAsync
import ru.dbotthepony.kstarbound.world.Universe
import ru.dbotthepony.kstarbound.world.UniversePos
import java.io.Closeable
import java.io.File
import java.lang.ref.Cleaner.Cleanable
import java.sql.Connection
import java.sql.DriverManager
import java.sql.PreparedStatement
import java.sql.ResultSet
import java.util.concurrent.CompletableFuture
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.TimeUnit
import java.util.function.Consumer
import java.util.function.Function
import java.util.function.Supplier
import java.util.random.RandomGenerator
import kotlin.collections.ArrayList

class ServerUniverse(folder: File? = null) : Universe(), Closeable {
	override val baseInformation: CelestialBaseInformation
		get() = Globals.celestialBaseInformation

	val generationInformation: CelestialConfig
		get() = Globals.celestialConfig

	private val database: Connection
	private val legacyDatabase: BTreeDB5?
	private val isMemory = folder == null
	private val databaseCleanable: Cleanable

	init {
		if (folder == null) {
			// in-memory database
			database = DriverManager.getConnection("jdbc:sqlite:")
			legacyDatabase = null
			databaseCleanable = Starbound.CLEANER.register(this, database::close)
		} else {
			val nativeFile = File(folder, "universe-chunks.db")
			val legacyFile = File(folder, "universe.chunks")

			database = DriverManager.getConnection("jdbc:sqlite:${nativeFile.absolutePath.replace('\\', '/')}")
			databaseCleanable = Starbound.CLEANER.register(this, database::close)

			if (legacyFile.exists()) {
				legacyDatabase = BTreeDB5(legacyFile)
			} else {
				legacyDatabase = null
			}
		}

		database.createStatement().use {
			it.execute("PRAGMA journal_mode=WAL")
			it.execute("PRAGMA synchronous=NORMAL")

			it.execute("""
				CREATE TABLE IF NOT EXISTS `chunk` (
					`x` INTEGER NOT NULL,
					`y` INTEGER NOT NULL,
					`systems` BLOB NOT NULL, -- binary json array representing 3D coordinates
					`constellations` BLOB NOT NULL, -- binary json array representing pairs of 2D coordinates
					PRIMARY KEY(`x`, `y`)
				)
			""".trimIndent())

			it.execute("""
				CREATE TABLE IF NOT EXISTS `system` (
					`x` INTEGER NOT NULL,
					`y` INTEGER NOT NULL,
					`z` INTEGER NOT NULL,
					`parameters` BLOB NOT NULL,
					`planets` BLOB NOT NULL,
					PRIMARY KEY(`x`, `y`, `z`)
				)
			""".trimIndent())
		}

		database.autoCommit = false
	}

	// don't allow execution in place because of computeIfAbsent of ConcurrentHashMap
	private val carrier = CarriedExecutor(Starbound.IO_EXECUTOR, allowExecutionInPlace = false)
	private val scope = CoroutineScope(ScheduledCoroutineExecutor(carrier) + SupervisorJob())

	private val selectChunk = database.prepareStatement("SELECT `systems`, `constellations` FROM `chunk` WHERE `x` = ? AND `y` = ?")
	private val selectSystem = database.prepareStatement("SELECT `parameters`, `planets` FROM `system` WHERE `x` = ? AND `y` = ? AND `z` = ?")

	private val insertChunk = database.prepareStatement("INSERT INTO `chunk` (`x`, `y`, `systems`, `constellations`) VALUES (?, ?, ?, ?)")
	private val insertSystem = database.prepareStatement("INSERT INTO `system` (`x`, `y`, `z`, `parameters`, `planets`) VALUES (?, ?, ?, ?, ?)")

	private class SerializedChunk(val x: Int, val y: Int, val systems: ByteArray, val constellations: ByteArray) {
		fun write(statement: PreparedStatement) {
			statement.setInt(1, x)
			statement.setInt(2, y)
			statement.setBytes(3, systems)
			statement.setBytes(4, constellations)

			statement.execute()
		}
	}

	private data class Chunk(val x: Int, val y: Int, val systems: Set<Vector3i>, val constellations: Set<Pair<Vector2i, Vector2i>>) {
		constructor(x: Int, y: Int, data: ResultSet) : this(
			x, y,
			data.getBytes(1).readJsonArrayInflated().map { Vector3i(it.asJsonArray[0].asInt, it.asJsonArray[1].asInt, it.asJsonArray[2].asInt) }.toSet(),
			data.getBytes(2).readJsonArrayInflated().map {
				val a = it.asJsonArray[0].asJsonArray
				val b = it.asJsonArray[1].asJsonArray
				Vector2i(a[0].asInt, a[1].asInt) to Vector2i(b[0].asInt, b[1].asInt)
			}.toSet()
		)

		fun serialize(): SerializedChunk {
			return SerializedChunk(
				x, y,
				systems.stream()
					.map { jsonArrayOf(it.x, it.y, it.z) }
					.collect(JsonArrayCollector)
					.writeJsonArrayDeflated(),
				constellations.stream().map {
					jsonArrayOf(jsonArrayOf(it.first.x, it.first.y), jsonArrayOf(it.second.x, it.second.y))
				}.collect(JsonArrayCollector).writeJsonArrayDeflated()
			)
		}

		fun write(statement: PreparedStatement) {
			serialize().write(statement)
		}
	}

	private class SerializedSystem(val x: Int, val y: Int, val z: Int, val parameters: ByteArray, val planets: ByteArray) {
		fun write(statement: PreparedStatement) {
			statement.setInt(1, x)
			statement.setInt(2, y)
			statement.setInt(3, z)
			statement.setBytes(4, parameters)
			statement.setBytes(5, planets)

			statement.execute()
		}
	}

	private data class System(val x: Int, val y: Int, val z: Int, val parameters: CelestialParameters, val planets: Map<Pair<Int, Int>, CelestialParameters>) {
		fun parameters(pos: UniversePos): CelestialParameters? {
			if (pos.isSystem) {
				return parameters
			} else {
				return planets[pos.planetOrbit to pos.satelliteOrbit]
			}
		}

		fun serialize(): SerializedSystem {
			return SerializedSystem(
				x, y, z,
				Starbound.gson.toJsonTree(parameters).writeJsonElementDeflated(),
				planets.entries.stream()
					.map { jsonArrayOf(it.key.first, it.key.second, it.value) }
					.collect(JsonArrayCollector).writeJsonArrayDeflated()
			)
		}

		fun write(statement: PreparedStatement) {
			serialize().write(statement)
		}
	}

	// first, chunks in process of loading/generating must not be evicted
	private val chunkFutures = ConcurrentHashMap<Vector2i, CompletableFuture<Chunk>>()

	// then, once chunk is loaded, it is put into cache, where it may get evicted
	private val chunksCache = Caffeine.newBuilder()
		.maximumSize(4096L)
		.executor(Starbound.EXECUTOR)
		.build<Vector2i, CompletableFuture<Chunk>>()

	private suspend fun getChunk0(pos: Vector2i): Chunk {
		selectChunk.setInt(1, pos.x)
		selectChunk.setInt(2, pos.y)

		selectChunk.executeQuery().use {
			if (it.next()) {
				return Chunk(pos.x, pos.y, it)
			}
		}

		// TODO
		//  load legacy chunk here

		return generateChunk(pos).await()
	}

	private fun getChunk(pos: Vector2i): CompletableFuture<Chunk> {
		return chunksCache.get(pos) {
			chunkFutures.computeIfAbsent(it) {
				scope.async {
					try {
						getChunk0(it)
					} finally {
						chunkFutures.remove(it)
					}
				}.asCompletableFuture()
			}
		}
	}

	// first, systems in process of loading/generating must not be evicted
	private val systemFutures = ConcurrentHashMap<Vector3i, CompletableFuture<System?>>()

	// then, once system is loaded, it is put into cache, where it may get evicted
	private val systemCache = Caffeine.newBuilder()
		.maximumSize(2048L)
		.executor(Starbound.EXECUTOR)
		.build<Vector3i, CompletableFuture<System?>>()

	private fun loadSystem(pos: Vector3i): CompletableFuture<System>? {
		selectSystem.setInt(1, pos.x)
		selectSystem.setInt(2, pos.y)
		selectSystem.setInt(3, pos.z)

		return selectSystem.executeQuery().use {
			if (it.next()) {
				val parametersBytes = it.getBytes(1)
				val planetsBytes = it.getBytes(2)

				// deserialize in off-thread since it involves big json structures
				Starbound.EXECUTOR.supplyAsync {
					val parameters: CelestialParameters = Starbound.gson.fromJson(parametersBytes.readJsonElementInflated())!!

					val planets: Map<Pair<Int, Int>, CelestialParameters> = planetsBytes.readJsonArrayInflated().associate {
						it as JsonArray
						(it[0].asInt to it[1].asInt) to Starbound.gson.fromJson(it[2])!!
					}

					System(pos.x, pos.y, pos.z, parameters, planets)
				}
			} else {
				null
			}
		}
	}

	private suspend fun loadOrComputeSystem(pos: Vector3i): System? {
		val existing = loadSystem(pos)

		if (existing != null) {
			// hit, system already exists
			return existing.await()
		}

		// lets try to get chunk this system is in
		// if chunk doesn't exist, it will be generated, along all systems in it
		val chunk = getChunk(world2chunk(Vector2i(pos))).await()

		// once chunk has been generated, try again
		// if nothing is there, then system does not exist
		if (pos !in chunk.systems)
			return null

		return loadSystem(pos)!!.await()
	}

	private fun getSystem(pos: Vector3i): CompletableFuture<System?> {
		return systemCache.get(pos) {
			systemFutures.computeIfAbsent(it) {
				scope.async {
					try {
						loadOrComputeSystem(it)
					} finally {
						systemFutures.remove(it)
					}
				}.asCompletableFuture()
			}
		}
	}

	override suspend fun parameters(pos: UniversePos): CelestialParameters? {
		return getSystem(pos.location).await()?.parameters(pos)
	}

	override suspend fun hasChildren(pos: UniversePos): Boolean {
		if (pos.isSatellite)
			return false

		val system = getSystem(pos.location).await() ?: return false

		if (pos.isSystem) {
			return system.planets.isNotEmpty()
		} else {
			return system.planets.keys.any { it.first == pos.planetOrbit && it.second != 0 }
		}
	}

	override suspend fun chunkSystems(pos: Vector2i): List<UniversePos> {
		val chunk = getChunk(pos).await()
		return chunk.systems.map { UniversePos(Vector3i(it.x, it.y, it.z)) }
	}

	override suspend fun chunkConstellations(pos: Vector2i): List<Pair<Vector2i, Vector2i>> {
		val chunk = getChunk(pos).await()
		return chunk.constellations.toList()
	}

	override suspend fun children(pos: UniversePos): List<UniversePos> {
		if (pos.isSatellite)
			return emptyList()

		val system = getSystem(pos.location).await() ?: return emptyList()

		if (pos.isSystem) {
			val keys = IntArraySet()

			for ((key, s) in system.planets.keys) {
				if (s == 0)
					keys.add(key)
			}

			return keys.map { pos.child(it) }
		} else {
			val keys = IntArraySet()

			for ((f, key) in system.planets.keys) {
				if (f == pos.planetOrbit && key != 0)
					keys.add(key)
			}

			return keys.map { pos.child(it) }
		}
	}

	override suspend fun findSystems(region: AABBi, includedTypes: Set<String>?): List<UniversePos> {
		val copy = if (includedTypes != null) ObjectOpenHashSet(includedTypes) else null
		val futures = ArrayList<CompletableFuture<ArrayList<UniversePos>>>()

		for (pos in chunkPositions(region)) {
			val f = getChunk(pos).thenApply {
				if (copy == null) {
					val result = ArrayList<UniversePos>()

					for (system in it.systems) {
						result.add(UniversePos(system))
					}

					CompletableFuture.completedFuture(result)
				} else {
					val innerFutures = ArrayList<CompletableFuture<System?>>()

					for (system in it.systems) {
						innerFutures.add(getSystem(system))
					}

					CompletableFuture.allOf(*innerFutures.toTypedArray())
						.thenApply {
							val result = ArrayList<UniversePos>()

							for (systemF in innerFutures) {
								val system = systemF.get() ?: continue

								if (system.parameters.parameters.get("typeName", "") in copy) {
									result.add(UniversePos(Vector3i(system.x, system.y, system.z)))
								}
							}

							result
						}
				}
			}.thenCompose { it }

			futures.add(f)
		}

		CompletableFuture.allOf(*futures.toTypedArray()).await()
		return futures.stream().flatMap { it.get().stream() }.toList()
	}

	override suspend fun <T> scanSystems(region: AABBi, callback: suspend (UniversePos) -> KOptional<T>): KOptional<T> {
		for (pos in chunkPositions(region)) {
			val chunk = getChunk(pos).await()

			for (system in chunk.systems) {
				val result = callback(UniversePos(system))

				if (result.isPresent) {
					return result
				}
			}
		}

		return KOptional()
	}

	suspend fun findRandomWorld(tries: Int, range: Int, seed: Long? = null, visitAll: Boolean = false, predicate: suspend (UniversePos) -> Boolean = { true }): UniversePos? {
		require(tries > 0) { "Non-positive amount of tries: $tries" }
		require(range > 0) { "Non-positive range: $range" }

		val random = random(seed ?: java.lang.System.nanoTime())
		val rect = AABBi(Vector2i(-range, -range), Vector2i(range, range))

		for (i in 0 until tries) {
			val x = random.nextRange(baseInformation.xyCoordRange)
			val y = random.nextRange(baseInformation.xyCoordRange)

			val result = scanSystems<UniversePos>(rect + Vector2i(x, y)) {
				val children = ArrayList<UniversePos>()

				for (planet in children(it)) {
					children.add(planet)

					for (satellite in children(planet)) {
						children.add(satellite)
					}
				}

				if (children.isEmpty())
					return@scanSystems KOptional()

				if (visitAll) {
					for (world in children)
						if (predicate(world))
							return@scanSystems KOptional(world)
				} else {
					// This sucks, 50% of the time will try and return satellite, not really
					// balanced probability wise
					val world = children.random(random)

					if (predicate(world))
						return@scanSystems KOptional(world)
				}

				KOptional()
			}

			if (result.isPresent) {
				return result.value
			}
		}

		return null
	}

	override suspend fun scanConstellationLines(region: AABBi, aggressive: Boolean): List<Pair<Vector2i, Vector2i>> {
		val futures = ArrayList<CompletableFuture<ObjectArrayList<Pair<Vector2i, Vector2i>>>>()

		for (pos in chunkPositions(region)) {
			val f = getChunk(pos).thenApply {
				ObjectArrayList(it.constellations)
			}

			futures.add(f)
		}

		CompletableFuture.allOf(*futures.toTypedArray()).await()
		return futures.stream().flatMap { it.get().stream() }.toList()
	}

	override fun scanRegionFullyLoaded(region: AABBi): Boolean {
		return true
	}

	override fun close() {
		scope.cancel()

		carrier.execute {
			legacyDatabase?.close()
			databaseCleanable.clean()
		}

		carrier.wait(300L, TimeUnit.SECONDS)
	}

	private val systemPerlin = AbstractPerlinNoise.of(generationInformation.systemTypePerlin)

	init {
		if (!systemPerlin.hasSeedSpecified) {
			systemPerlin.init(staticRandom64("SystemTypePerlin"))
		}
	}

	private fun generateChunk(chunkPos: Vector2i): CompletableFuture<Chunk> {
		val random = random(staticRandom64(chunkPos.x, chunkPos.y, "ChunkIndexMix"))
		val region = chunkRegion(chunkPos)

		return CompletableFuture.supplyAsync(Supplier {
			val constellationCandidates = ArrayList<Vector2i>()
			val systemPositions = ArrayList<Vector3i>()
			val systems = ArrayList<CompletableFuture<SerializedSystem>>()

			for (x in region.mins.x until region.maxs.x) {
				for (y in region.mins.y until region.maxs.y) {
					if (random.nextFloat() < generationInformation.systemProbability) {
						val z = random.nextInt(baseInformation.zCoordRange.x, baseInformation.zCoordRange.y)
						val pos = Vector3i(x, y, z)

						val system = generateSystem(random, pos) ?: continue
						systemPositions.add(pos)
						systems.add(CompletableFuture.supplyAsync(Supplier { system.serialize() }, Starbound.EXECUTOR))
						systemCache.put(Vector3i(system.x, system.y, system.z), CompletableFuture.completedFuture(system))

						if (
							system.parameters.parameters.get("constellationCapable", true) &&
							system.parameters.parameters.get("magnitude", 0.0) >= generationInformation.minimumConstellationMagnitude
						) {
							constellationCandidates.add(Vector2i(x, y))
						}
					}
				}
			}

			val chunk = Chunk(chunkPos.x, chunkPos.y, ObjectOpenHashSet(systemPositions), ObjectOpenHashSet(generateConstellations(random, constellationCandidates)))
			val serialized = chunk.serialize()

			CompletableFuture.allOf(*systems.toTypedArray()).thenApplyAsync(Function {
				serialized.write(insertChunk)
				systems.forEach { it.get().write(insertSystem) }
				database.commit()
				chunk
			}, carrier)
		}, Starbound.EXECUTOR).thenCompose { it }
	}

	private fun generateSystem(random: RandomGenerator, location: Vector3i): System? {
		val typeSelector = systemPerlin[location.x.toDouble(), location.y.toDouble()]

		val type = generationInformation.systemTypeBins
			.stream()
			.binnedChoice(typeSelector).orElse("")

		if (type.isBlank())
			return null

		val system = generationInformation.systemTypes[type]!!
		val systemPos = UniversePos(location)
		val systemSeed = random.nextLong()

		val prefix = Globals.celestialNames.systemPrefixNames.sample(random).orElse("")
		val mid = Globals.celestialNames.systemNames.sample(random).orElse("missingsystemname $location")
		val suffix = Globals.celestialNames.systemSuffixNames.sample(random).orElse("")

		val systemName = "$prefix $mid $suffix".trim()
			.replace("<onedigit>", random.nextInt(0, 10).toString())
			.replace("<twodigit>", paddedNumber(random.nextInt(0, 100), 2))
			.replace("<threedigit>", paddedNumber(random.nextInt(0, 1000), 3))
			.replace("<fourdigit>", paddedNumber(random.nextInt(0, 10000), 4))

		val systemParams = CelestialParameters(
			systemPos,
			systemSeed,
			systemName,
			mergeJson(system.baseParameters.deepCopy(), system.variationParameters.random(random))
		)

		if ("typeName" !in systemParams.parameters) {
			systemParams.parameters["typeName"] = system.typeName
		}

		if ("constellationCapable" !in systemParams.parameters) {
			systemParams.parameters["constellationCapable"] = system.constellationCapable
		}

		val planets = HashMap<Pair<Int, Int>, CelestialParameters>()

		for (planetOrbitIndex in 1 .. baseInformation.planetOrbitalLevels) {
			// this looks dumb at first, but then it makes sense
			// in celestial.config, you define orbital region, where planets
			// of only specific type appear.
			val systemOrbitRegion = system.orbitRegions
				.stream()
				.filter { planetOrbitIndex in it.orbitRange.x .. it.orbitRange.y }
				.findFirst().orElse(null) ?: continue

			if (systemOrbitRegion.bodyProbability > random.nextDouble()) continue

			val planetaryTypeO = systemOrbitRegion.planetaryTypes.sample(random).flatMap { KOptional.ofNullable(generationInformation.planetaryTypes[it]) }
			if (!planetaryTypeO.isPresent) continue
			val planetaryType = planetaryTypeO.value

			val planetCoordinate = UniversePos(location, planetOrbitIndex)
			val planetSeed = random.nextLong()
			val planetName = "$systemName ${Globals.celestialNames.planetarySuffixes[planetOrbitIndex]}"

			planets[planetOrbitIndex to 0] = CelestialParameters(
				planetCoordinate,
				planetSeed,
				planetName,
				mergeJson(planetaryType.baseParameters.deepCopy(), planetaryType.variationParameters.random(random))
			)

			var satelliteCount = 0
			val maxSatelliteCount = planetaryType.maxSatelliteCount ?: baseInformation.satelliteOrbitalLevels

			if (maxSatelliteCount > 0) {
				for (satelliteOrbitIndex in 1 .. baseInformation.satelliteOrbitalLevels) {
					if (random.nextDouble() < planetaryType.satelliteProbability) {
						val satelliteTypeO = systemOrbitRegion.satelliteTypes.sample(random).flatMap { KOptional.ofNullable(generationInformation.satelliteTypes[it]) }
						if (!satelliteTypeO.isPresent) continue
						val satelliteType = satelliteTypeO.value
						val satelliteSeed = random.nextLong()
						val satelliteName = "$planetName ${Globals.celestialNames.satelliteSuffixes[satelliteCount]}"
						val satelliteCoordinate = UniversePos(location, planetOrbitIndex, satelliteOrbitIndex)

						val merge = JsonObject()
						mergeJson(merge, satelliteType.baseParameters)
						mergeJson(merge, satelliteType.variationParameters.random(random))

						if (systemOrbitRegion.regionName in satelliteType.orbitParameters) {
							mergeJson(merge, satelliteType.orbitParameters[systemOrbitRegion.regionName]!!.random(random))
						}

						planets[planetOrbitIndex to satelliteOrbitIndex] = CelestialParameters(
							satelliteCoordinate,
							satelliteSeed,
							satelliteName,
							merge
						)

						if (++satelliteCount >= maxSatelliteCount)
							break
					}
				}
			}
		}

		return System(location.x, location.y, location.z, systemParams, planets)
	}

	private fun generateConstellations(random: RandomGenerator, candidates: List<Vector2i>): List<Pair<Vector2i, Vector2i>> {
		if (candidates.size <= 2 || random.nextDouble() > generationInformation.constellationProbability) return listOf()

		val constellations = ArrayList<Pair<Vector2i, Vector2i>>()
		val constellationPoints = ObjectArrayList<Vector2i>()
		val constellationLines = ArrayList<Line2d>()

		val target = random.nextInt(generationInformation.constellationLineCountRange.x, generationInformation.constellationLineCountRange.y)
		var tries = 0

		while (constellationLines.size < target && ++tries < generationInformation.constellationMaxTries) {
			val start = if (constellationPoints.isEmpty)
				candidates.random(random)
			else
				constellationPoints.random(random)

			val end = candidates.random(random)

			if (start == end) continue
			val proposed = Line2d(start.toDoubleVector(), end.toDoubleVector())
			val proposedReversed = proposed.reverse()

			if (proposed in constellationLines || proposedReversed in constellationLines) continue
			if (start.distance(end) !in generationInformation.minimumConstellationLineLength .. generationInformation.maximumConstellationLineLength) continue

			var valid = true

			for (existingLine in constellationLines) {
				val intersection = proposed.intersect(existingLine)

				if (
					intersection.intersects &&
					intersection.point != proposed.p0 &&
					intersection.point != proposed.p1
				) {
					valid = false
					break
				}

				if (
					proposed != existingLine &&
					existingLine.distanceTo(proposed.p0) < generationInformation.minimumConstellationLineCloseness
				) {
					valid = false
					break
				}

				if (
					proposed != existingLine.reverse() &&
					existingLine.distanceTo(proposed.p1) < generationInformation.minimumConstellationLineCloseness
				) {
					valid = false
					break
				}
			}

			if (valid) {
				// TODO: Original engine generates "single" constellation
				//  out of multiple (probably disconnected) point pairs.
				//  Should we do the same? It just doesn't seem to make much sense
				// Side effect: It is now possible to have chunks where only two stars are connected (one line)
				// Original game engine requires at least two lines to be present to form a constellation
				constellations.add(start to end)

				constellationLines.add(proposed)
				constellationPoints.add(start)
				constellationPoints.add(end)
			}
		}

		return constellations
	}

	override val region: AABBi = AABBi(Vector2i(baseInformation.xyCoordRange.x, baseInformation.xyCoordRange.x), Vector2i(baseInformation.xyCoordRange.y, baseInformation.xyCoordRange.y))
}
