142 lines
3.8 KiB
GDScript
142 lines
3.8 KiB
GDScript
class_name Netz
|
|
extends RefCounted
|
|
## Ein Wegenetz: Knoten und Kanten in der Ebene. Wege wachsen daran, indem
|
|
## neue Punkte an die nächste Stelle des bestehenden Netzes angebunden werden.
|
|
## Wiederverwendung ist gratis -- deshalb bündeln sich Wege und gabeln sich,
|
|
## statt sternförmig zur Mitte zu laufen.
|
|
|
|
var knoten: Array[Vector3] = []
|
|
var kanten: Array = [] # [a, b] Indexpaare
|
|
|
|
|
|
func fuege_knoten(p: Vector3) -> int:
|
|
var q := Vector3(p.x, 0.0, p.z)
|
|
for i in range(knoten.size()):
|
|
if knoten[i].distance_to(q) < 0.6:
|
|
return i
|
|
knoten.append(q)
|
|
return knoten.size() - 1
|
|
|
|
|
|
func verbinde(a: int, b: int) -> void:
|
|
if a == b:
|
|
return
|
|
for k in kanten:
|
|
if (k[0] == a and k[1] == b) or (k[0] == b and k[1] == a):
|
|
return
|
|
kanten.append([a, b])
|
|
|
|
|
|
func nachbarn(i: int) -> Array:
|
|
var out: Array = []
|
|
for k in kanten:
|
|
if k[0] == i:
|
|
out.append(k[1])
|
|
elif k[1] == i:
|
|
out.append(k[0])
|
|
return out
|
|
|
|
|
|
## Nächster Punkt auf einer Kante -- gibt {knoten, dist} zurück und teilt die
|
|
## Kante, falls der Fußpunkt zwischen zwei Knoten liegt.
|
|
func andocken(p: Vector3) -> Dictionary:
|
|
var q := Vector3(p.x, 0.0, p.z)
|
|
var beste := INF
|
|
var best_i := -1
|
|
var best_k := -1
|
|
var best_p := Vector3.ZERO
|
|
for i in range(knoten.size()):
|
|
var d := knoten[i].distance_to(q)
|
|
if d < beste:
|
|
beste = d
|
|
best_i = i
|
|
best_k = -1
|
|
for ki in range(kanten.size()):
|
|
var a: Vector3 = knoten[kanten[ki][0]]
|
|
var b: Vector3 = knoten[kanten[ki][1]]
|
|
var f := Geometry3D.get_closest_point_to_segment(q, a, b)
|
|
var d := f.distance_to(q)
|
|
if d < beste - 0.01 and f.distance_to(a) > 1.5 and f.distance_to(b) > 1.5:
|
|
beste = d
|
|
best_k = ki
|
|
best_p = f
|
|
if best_k < 0:
|
|
return {"knoten": best_i, "dist": beste, "punkt": knoten[best_i]}
|
|
# Kante teilen
|
|
var alt: Array = kanten[best_k]
|
|
kanten.remove_at(best_k)
|
|
var neu := fuege_knoten(best_p)
|
|
verbinde(alt[0], neu)
|
|
verbinde(neu, alt[1])
|
|
return {"knoten": neu, "dist": beste, "punkt": knoten[neu]}
|
|
|
|
|
|
## Kürzester Weg als Knotenfolge, leer wenn es keinen gibt.
|
|
func pfad(start: int, ziel: int) -> Array:
|
|
if start == ziel:
|
|
return [start]
|
|
var offen: Array = [start]
|
|
var kosten: Dictionary = {start: 0.0}
|
|
var her: Dictionary = {}
|
|
while not offen.is_empty():
|
|
var best := 0
|
|
for i in range(1, offen.size()):
|
|
if float(kosten[offen[i]]) < float(kosten[offen[best]]):
|
|
best = i
|
|
var k: int = offen[best]
|
|
offen.remove_at(best)
|
|
if k == ziel:
|
|
break
|
|
for n in nachbarn(k):
|
|
var neu: float = float(kosten[k]) + knoten[k].distance_to(knoten[n])
|
|
if not kosten.has(n) or neu < float(kosten[n]) - 0.001:
|
|
kosten[n] = neu
|
|
her[n] = k
|
|
if not offen.has(n):
|
|
offen.append(n)
|
|
if not kosten.has(ziel):
|
|
return []
|
|
var weg: Array = [ziel]
|
|
var cur: int = ziel
|
|
while cur != start:
|
|
cur = int(her[cur])
|
|
weg.push_front(cur)
|
|
return weg
|
|
|
|
|
|
func weglaenge(start: int, ziel: int) -> float:
|
|
var w := pfad(start, ziel)
|
|
if w.size() < 2:
|
|
return 0.0 if w.size() == 1 else INF
|
|
var l := 0.0
|
|
for i in range(w.size() - 1):
|
|
l += knoten[w[i]].distance_to(knoten[w[i + 1]])
|
|
return l
|
|
|
|
|
|
## Hängen alle Knoten zusammen?
|
|
func zusammenhaengend() -> bool:
|
|
if knoten.is_empty():
|
|
return true
|
|
var gesehen: Dictionary = {0: true}
|
|
var stapel: Array = [0]
|
|
while not stapel.is_empty():
|
|
var k: int = stapel.pop_back()
|
|
for n in nachbarn(k):
|
|
if not gesehen.has(n):
|
|
gesehen[n] = true
|
|
stapel.append(n)
|
|
return gesehen.size() == knoten.size()
|
|
|
|
|
|
## Schneidet die Strecke a-b ein Rechteck (Mittelpunkt c, Größe s, mit Rand)?
|
|
static func trifft_rechteck(a: Vector3, b: Vector3, c: Vector3, s: Vector2, rand: float) -> bool:
|
|
var hx := s.x * 0.5 + rand
|
|
var hz := s.y * 0.5 + rand
|
|
var schritte := int(maxf(2.0, a.distance_to(b) / 1.5))
|
|
for i in range(schritte + 1):
|
|
var p := a.lerp(b, float(i) / float(schritte))
|
|
if absf(p.x - c.x) <= hx and absf(p.z - c.z) <= hz:
|
|
return true
|
|
return false
|