Kurven konstruieren

Willkommen in der Transport Fever Community

Welcome to the fan community of Transport Fever and Train Fever, the economic simulators of Urban Games. The community is free for you to share and inform yourself about the game. We cultivate a friendly and objective interaction with each other and our team will be happy to answer any questions you may have.

 

Registration and use is of course free for you.

 

We wish you a lot of fun and hope for active participation.

The Team of the Transport-Fever Community

  • Naiverweise hatte ich mal gedacht, um Kurven für Transport Fever programmiertechnisch zu konstruieren wären nur ein paar Grundparameter wie Radius oder Winkel notwendig; wir hätten also quasi eine Black Box, mit der wir mühelos herumspielen können. Das ist nicht so. Bei Transport Fever ist nichts servierfertig vorgekocht, sondern wir müssen uns noch selbst die Rezepte besorgen, manchmal irgendwo in den Weiten des Internets, wo sie auch nur spärlich gesät sind. Andererseits hat es den Vorteil, dass unsere Möglichkeiten damit auch recht vielseitig sind.

    Wir müssen uns aber mit unbequemen Dingen abgeben, die uns in der Schulzeit womöglich den Spaß an der Mathematik vermiest haben - oder die mangels praktischen Nutzens nicht einmal gelehrt wurden. Wir werden mit Differenzialrechnung, Vektorrechnung, Trigonometrie und anderen nicht immer einfachen Dingen konfrontiert - trotzdem keine Panik, ich hab's auch irgendwie durchgehalten, und damit Ihr es etwas einfacher habt, dieser Beitrag. Ich möchte den Themenbereich nach Möglichkeit künftig noch etwas ausweiten, und Unterstützung ist hierbei auch jederzeit willkommen.


    Gleise und Straßen werden von Transport Fever mit Hilfe von Vektorgrafik dargestellt. Die kennen wir bereits aus Zeichenprogrammen wie Corel Draw, Illustrator & Co. Auch in die Spielewelt hat diese Technik Einzug gefunden, obwohl sie eigentlich ganz andere Ursprünge hat.


    Es war vor allem die französische Autoindustrie, die nach Möglichkeiten gesucht hat, mathematische Modelle für biegsame Kurvenelemente zu entwickeln. Die Namen Pierre Bézier und Paul de Casteljau stehen hierfür. Vor ihnen hat sich aber bereits Charles Hermite, ebenfalls ein Franzose, mit dieser Thematik befasst.


    Die nach Bézier benannte Kurve versucht, eine elastische Strebe zu simulieren, die mittels von Hebeln an den Endpunkten in eine beliebige Bogenform gebracht werden kann. Dieser Gedanke geht auf den Schiffsbau zurück, deswegen spricht man in der Fachwelt auch von Splines, der englische Ausdruck für biegbare Latten zur Modellierung von Schiffskörpern.


    Es gibt eine Vielzahl von Kurvenmodellen; merken wir uns die beiden, die für Transport Fever relevant sind: die Bézier- und die Hermite-Kurve, und zwar die kubische, die auch als "Kurve dritten Grades" bezeichnet wird. Zum Stichwort "Bézier" wird man bei Google schnell fündig, falls man das Thema vertiefen möchte. Bei Hermite wird es etwas schwieriger. Die mathematischen Geheimnisse dahinter möchte ich Euch weitgehend ersparen. Ihr findet genug Fachartikel darüber, leider auch häufig in Fachchinesisch. Nur soviel: Es spielen Vektoren, Polynome und Ableitungen eine Rolle.


    Beginnen wir mit gleich dem einfachsten Sonderfall: der Geraden. Eine Gerade wird exakt durch zwei Endpunkte b0 (x; y; z) und b1 (x; y; z) in einem Koordinatensystem definiert. Ich nenne die Punkte hier bewusst nicht p, sondern b wie "Bézier". Es entspricht der Benennung in Wikipedia. Mehr Punkte bräuchten wir eigentlich nicht. Eine Gerade könnte auch als Kurve mit unendlichem Radius bezeichnet werden. Geraden können von daher auch und erst recht mit dem Bézier-Verfahren dargestellt werden.



    Komplizierter wird's bei Kurven. Mit einem einzigen Vektorgrafik-Segment lassen sich verschiedene Arten von Kurven darstellen: regelmäßige Kreisbögen, Übergangskurven und S-Kurven. Wenn wir mehr wollen, müssen wir mehrere Segmente aneinandersetzen. Beim Bézier-Verfahren haben wir wieder Anfangs- und Endpunkt, nennen wir sie b0 und b3, aber auch noch die Punkte b1 und b2, die als Anfasser, Kontrollpunkte, Steuerpunkte, Hebel oder schlicht und ergreifend als Tangentenpunkte bezeichnet werden. Denn sie bilden mit den zugehörigen Endpunkten jeweils die Tangenten (blau in der Abb.) der zu erzeugenden Kurven (rot in der Abb.). Durch Verschieben dieser Punkte lassen sich - fast - beliebige Kurven modellieren. Warum nur fast? Die hier benutzte Vektorgrafik funktioniert nicht geometrisch exakt, sondern nur mit einer gewissen Ungenauigkeit. Diese ist für die praktische Anwendung jedoch nicht allzu störend. Kritisch wird es allerdings bei Kreisbögen ab einem Winkel von etw 120 Grad. Dann verbeult unser Bogen allmählich, wird immer unförmiger bis hin zum totalen Chaos. Deswegen können wir mit einer einzigen Bézierkurve niemals einen kompletten Kreis modellieren. Aber bei vier Viertelkreisen funktioniert es noch sehr gut.


    Bézier-Kurven finden wir vor allem bei Konstruktions- und Zeichenprogrammen. Aber nicht bei Transport Fever, jedenfalls nicht direkt. Das hat praktische Gründe. Bei Bézierkurven verlaufen die Tangenten entgegengesetzt. Das spart Platz auf dem Monitor und sorgt für schnelles Handling. Bei Spielen hingegen spielt dieses Argument eine untergeordnete Rolle. Hier geht es um möglichst einfache und schnelle Berechnung, und da ist die Hermite-Kurve die bessere Wahl. Hermite- und Bézier-Kurven sind jedoch nicht nur miteinander verwandt, sie sind sogar exakt äquivalent! Deshalb können wir sie einfach und verlustfrei in beide Richtungen konvertieren. Es gibt relativ viele Rechenbeispiele und Codefragmente im Web zu Bézier-Kurven im Web. Auf die können wir zurückgreifen, wenn die Suchergebnisse nach Hermite zu dürftig ausfallen. Wegen der einfachen Konvertierbarkeit stehen uns letztendlich beide Welten zur Verfügung.


    Bei Hermite-Kurven verlaufen die Tangenten in dieselbe Richtung und haben exakt die dreifache Länge von Bézier-Tangenten. Die hintere Tangente muss also zusätzlich zur Multiplikation mit 3 noch umgekehrt werden , d.h. sie wird mit -3 multipliziert. Multipliziert im Sinne der Vektormultiplikation, Ausführungen dazu später einmal. Eine weitere Besonderheit fällt auf: Die Tangenten besitzen ein eigenes, zu Anfangs- und Endpunkt jeweils relatives Koordinatensystem.



    Aufgrund dieser Unterschiede habe ich die Punkte in der Hermite-Kurve nicht mit b0 bis b3, sondern mit p0, p1, t0 und t1 bezeichnet. Diese Bezeichnung ist auch in den UG-eigenen Skripten sowie in der Fachwelt üblich.


    Der Faktor 3 mag noch mathematische Hintergründe haben. Auf jeden Fall hat er auch einen praktischen Nutzen. Die Länge eines Segments ist nämlich ungefähr gleich der Vektorlänge der Tangenten. Zumindest dort, wo hohe Präzision überflüssig ist, reicht es für eine Quick-and-Dirty-Berechnung, sofern man weitere Einschränkungen in Kauf nimmt:

    • Geraden müssen stets (Pseudo-)Tangenten besitzen, deren Länge der Länge der Geraden entspricht. Das liegt allein in der Verantwortung der Modder. Das gilt auch für S-Kurven.
    • Die beiden Tangenten einer Kurve müssen gleich lang sein. Diese Bedingung ist selbst bei den im Spiel von der KI angelegten Kurven nicht immer erfüllt.
    • Bei regelmäßigen Kreissegmenten ist zusätzlich ab etwa 90 Grad eine Längenkompensation erforderlich. Wie das geht, irgendwann später. Ohnehin sollte man, wann immer es geht, große Winkel vermeiden und die Segmente stattdessen unterteilen.

    Bevor wir mit der Praxis beginnen, solltet ihr den Beitrag über die Lua-Programmierung lesen. Dort wird auch verraten, wie man einfacher mit Punkten, Vektoren und Koordinaten rechnen kann, und was vec3-Objekte sind. ;)


    Die Konvertierfunktionen zu den obigen Erläuterungen. Hermite zu Bézier ...

    Code
    1. function convertHermiteToBezier(edge) -- edge must contain vec3 objects
    2. local oneThird = 1 / 3
    3. local b0 = edge.p0 -- b instead of p/t for absolute bezier points, like Wikipedia example
    4. local b1 = edge.p0 + oneThird * edge.t0
    5. local b2 = edge.p1 - oneThird * edge.t1
    6. local b3 = edge.p1
    7. return b0, b1, b2, b3
    8. end

    ... und wieder zurück:

    Code
    1. function convertBezierToHermite(b0, b1, b2, b3) -- arguments must be vec3 objects
    2. local p0 = b0
    3. local p1 = b3
    4. local t0 = 3 * (b1 - b0)
    5. local t1 = 3 * (b3 - b2)
    6. return p0, p1, t0, t1
    7. end

    Dazwischen könnten wir dann eine Berechnung für Bézierkurven einfügen, ohne alle Parameter an Ort und Stelle umrechnen zu müssen. Was wir natürlich auch können, wenn wir Lust und Zeit haben. Oder wir haben gleich eine Formel für Hermite-Kurven, dann entfällt logischerweise die Konvertierung.


    Ihr könntet auch die Punkte p0, p1, t0 und t1 wieder in eine Edge einsetzen und diese dann als Return-Wert ausgeben. Darauf habe ich hier verzichtet.


    (wird ergänzt und fortgesetzt)

Share

Comments 11

  • Ich hatte das gleiche Problem: wie reproduziere ich die Kurven von Strassen- und Bahnsegmenten? Die Lösung war, die (skalare) Länge der Kurve in beliebigen Punkten als Referenz zu nehmen. Diese Länge l(x, y, z) kann man mit 3. Order Splines (Polynomen) genau berechnen.

    Also, es gibt drei 3. Order Splines:
    aX + bX * l + cX * l^2 + dX * l^3 = x
    aY + bY * l + cY * l^2 + dY * l^3 = y
    aZ + bZ * l + cZ * l^2 + dZ * l^3 = z

    Mit den Derivativen über l kriege ich:
    bX + 2 * cX * l + 3 * dX * l^2 = dx/dl
    bY + 2 * cY * l + 3 * dY * l^2 = dy/dl
    bZ + 2 * cZ * l + 3 * dZ * l^2 = dz/dl

    Ich kenne für jeden Edge pX0, pX1, tX0, tX1, pY0, usw. Dann habe ich drei Lineare Systemen, je mit 4 Equationen und 4 Variabeln.

    Hier löse ich die Systeme ganz einfach per Substitution; diese Routine macht noch was Anderes danach, ignoriere es einfach.

    • Ja, erst mal vielen Dank! Das Thema hat mich sowieso schon interessiert. Ich wusste gar nicht, dass du auch hier bist, deswegen hatte ich schon versucht, dich über Steam zu erreichen. Ich würde gerne noch ein paar Sachen über eine Konversation (oben das Sprechblasen-Symbol) abklären, da du einer der wenigen Modder bist, die sich speziell mit diesem Thema befassen. Die Längenberechnung mache ich momentan nach Gauss-Legendre, was aber nicht heißt, dass deine Lösung nicht auch interessant sein könnte.

    • OK über Steam geht es schneller. Discord nutze ich nicht, denn sie wollen meine Telefonnummer wissen.

    • Kann man da Quellcode posten? Ich meine, im Chat ist es vielleicht nicht optimal ... ?

    • Ja man kann. Wie du willst, ruf mich einfach an, entweder hier in der Sprechblase oder in Steam.

  • Danke für den Artikel. Der erste Teil liest sich ganz gut. Trotzdem (und gerade falls du den Artikel erweitern willst) der Tipp, die Übersichtlichkeit von solchen Einträgen lässt sich mit Fett, Kursiv, InlineCode für Ausdrücke/Formeln sowie formatierten Überschriften (das H) noch erhöhen. Das Inhaltsverzeichnis wird dann rechts angezeigt.

  • Das erinnert mich an mein Lane-Tool in JS ^^

  • Du könntest ja vielleicht noch dazu schreiben ob/welchen praktischen nutzen das Ganze beim Spielen oder Modden von TPF2 hat, da mir dieser irgendwie entgangen ist.

    Ich klicke immer auf das Gleissymbol bewege den cursor leicht kreisförmig und *tada* eine Kurve ist fertig.

    • Der praktische Nutzen besteht nur beim Modden, daher diese Anleitung auch unter der Kategorie "Modding". Den Spieler möchte ich damit auch gar nicht konfrontieren. Beim Modden brauchst du es, wenn du Gleise und Straßen mit konkreten Abmessungen programmieren und berechnen möchtest. Ein Beispiel dafür ist mein Weichenbaukasten. Oder meinetwegen auch gebogene Bahnhöfe - da brauchst du es auch.

    • Böhmische Dörfer für mich. Schulzeit ist lange her.... Aber wenn mir das heute jemand plausibel erklären kann, vielleicht kapiere ich es heute. Ich werde mich reinlesen. Vielen Dank, obwohl ich mit modden wohl nicht mehr anfangen werde ;-)

    • Der Teil, wo es ans Rechnen geht, kommt ja noch ;-) Das war zunächst mal der theoretische Unterbau. ;-) Die ganz harte Mathematik wird aber außen vor bleiben, die verstehe ich selber nicht. Es muss auch niemand Gleise modden, aber wer es machen möchte, soll wenigstens einfacher an Informationen kommen als ich. Leider fehlt diesbezüglich jedwede Doku von UG.