Datenstruktur für Dodekaeda (Infinity Cube Mirror)



  • Moin! Ich baue mir ein Infinity Cube Mirror. Damit ich die Lauflichter dadrin möglichst frei laufen lassen kann (an Kreuzungen mal recht oder links abzweigen) bin ich seit Tagen am überlegen wie ich eine sinnvolle Datenstruktur anlege. Ich kann die Basics von C und möchte mit dem Projekt meine Programmierfähigkeiten deutlich verbessern. Meine Gedanken sind bisher soweit das ich ein Struct und eine Liste denke ich, verbinden muss, um die 20 Ecken, 30 Seiten, 3 möglichen Richtungen und die Richtung des Lichts zu realisieren. Ich suche gerade nach irgendeinen Werk, möglichst kostenlos, um mich in diese Art von Datenstrukturen einzuarbeiten um so was zu realisieren. Strukturen denke ich, habe ich bisher gut verstanden, mit den Listen an sich haper ich gerade noch bisschen, sollte sich aber hoffentlich die Tage legen. Ich hoffe ihr könnt mir dabei ein zwei Tipps geben.
    Dankeschön für eure Hilfe und Zeit!

    Cheers



  • Ähm.
    Das ist doch ein ganz normaler Graph.
    D.h. du hast deine Knoten und die Verbindungen zwischen den Knoten.

    Also einfach

    struct DdEdge;
    
    struct DdVertex {
        DdEdge* edges[3];
    };
    
    struct DdEdge {
        DdVertex* vertices[2];
    };
    
    extern struct DdEdge g_ddEdges[30];
    
    struct DdVertex g_ddVertices[20] = {
        ...
    };
    
    struct DdEdge g_ddEdges[30] = {
        ...
    };

  • Mod

    Das klingt so, als bräuchtest du einfach allgemein mehr Wissen über C und Datenstrukturen, denn das sind ziemliche Grundlagen. Jedenfalls wirst du keine Bücher speziell über Structs und Listen finden. Höchstwahrscheinlich solltest du dich auch von der Idee von verketteten Listen verabschieden, denn Listen sind eher Programmieraufgabe zur Übung von Zeigern, als eine praxisrelevante Datenstruktur (außer in ganz wenigen Fällen, wo sie super gut sind). Das was hustbaer vorschlägt klingt schon realistischer als Datenmodell.

    Für konkrete Tipps müsste man jetzt genauer wissen, wie genau (und womit? Arduino?) das überhaupt aufgebaut und angesteuert wird, und welche Effekte du umsetzen möchtest. Aber mit ein bisschen mehr Erfahrung wirst du da auch ganz alleine auf passende Ansätze kommen. Sprich: Mein Ratschlag ist ein beliebiges gutes Lehrbuch über C (oder C++? Arduino benutzt doch eher eine Variante von C++).



  • @hustbaer sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    struct DdEdge;

    Ganz doofe Frage: wofür steht das Dd?



  • Ich will erst raten:

    D o d ekaeda?



  • @5cript sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Ich will erst raten:

    D o d ekaeda?

    Oh! Verdammt! Ich schiebs mal auf die Hitze... 🙂


  • Mod

    @5cript sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Ich will erst raten:

    D o d ekaeda?

    Falls ja, mag ich das nicht. Der Code legt zwar fest, dass ein Vertex 3 Edges hat, was eine Eigenschaft von "normalen" Dodekaedern ist. Aber es gibt jede Menge andere Körper, die auch diese Eigenschaft haben. Das hieße, wir haben eine unnötige Spezialisierung der Datenstruktur im Namen festgesetzt, obwohl die Struktur eigentlich viel universeller ist. Und die mathematischen Klugscheißer würden gleichzeitig bemängeln, dass es auch andere Dodekaeder gibt, die mehr als 3 Kanten pro Ecke haben.



  • Ja "Dd" steht für Dodekaeder. ("Dde" wäre vermutlich besser gewesen.)
    Ich wollte die Dinger bloss nicht einfach "Vertex" und "Edge" nennen, weil sie eben den Constraint haben dass jeder Vertex immer genau 3 Edges hat.

    @SeppJ
    sed -i 's/DdVertex/MyVertex/g'
    sed -i 's/DdEdge/MyEdge/g'

    Fixed 🙂


  • Mod

    My ist auch doof. Vertex3?

    In einer idealen Welt hätte Edge dann auch zwei allgemeine Vertices, die Basisklasse von VertexX sind. Aber ich würde davon absehen, eine Vererbungshierarchie in C zu implementieren, wenn man sie dann nicht nutzt.



  • @hustbaer Danke schonmal! Also von Graphen habe ich bisher nichts gehört gehabt. Listen war das letzte was wir in der Uni durchgenommen haben oder ich habe es evt. einfach verpeilt? Wer weiß. Danke schonmal! Gucke mal was ich damit anfangen kann. Denn ich merke das ich doch mehr vergessen habe als gedacht 😅



  • @SeppJ Muss gestehen das es halt das einzige war, was mit in den Sinn gekommen ist bisher. Aber mit den Code von @hustbaer kann ich bestimmt weiterkommen! 🙂

    Ja wie du schon erraten hast wird es von einen Mikrocontroller später gesteuert und ich programmiere es in der Arduino IDE bzw spiele es mit dieser eher auf den Controller später. Ein paar Lichteffekte habe ich schon im Sinn aber noch nicht alle. Wollte erstmal ein generelles Konstrukt worauf ich die Animationen aufbauen kann.

    @alle nochmal danke! 🙂



  • @SeppJ Wieso ist "My" doof? Ich finde "My" nicht doof. Korrekt angewendet natürlich. Ich habe "My" schon als Teil einer public API gesehen. Oder in grossen Projekten wo mehrere Foos gab und eines davon dann MyFoo hiess. Das ist grausam.

    Ich finde "My" praktisch:

    • Als Prefix für lokale Typen (anonymer Namespace)
    • Als Prefix für nested Classes
    • Als Prefix für Klassen in sehr kleinen Projekten

    Vertex3? Ist OK. Und wie nennst du dann die Edges? Vertex3Edge ginge natürlich. Aber ... eieiei, das ist schon irgendwie patschert. Dann noch lieber "My".

    In einer idealen Welt hätte Edge dann auch zwei allgemeine Vertices, die Basisklasse von VertexX sind. Aber ich würde davon absehen, eine Vererbungshierarchie in C zu implementieren, wenn man sie dann nicht nutzt.

    Ja, kann man machen. Man kann aber auch den Ball flach halten, und genau das implementieren was gefragt ist. Ist halt ein Unterschied ob man etwas darauf auslegt allgemein verwendbar zu sein, oder ob man bloss mal eben was ganz bestimmtes braucht.



  • Wie wärs hier mit "namespace icm" (für "Infinity Cube Mirror")
    Und dann icm::Vertex und icm::Edge?



  • Achja, vergessen:

    @SeppJ sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Aber ich würde davon absehen, eine Vererbungshierarchie in C zu implementieren, wenn man sie dann nicht nutzt.

    Ich würde allgemein davon abgesehn eine Vererbungshierarchie zu implementieren wenn man sie nicht nutzt. Bin auch überhaupt kein grosser Fan von Vererbung -- abgesehen von reiner Interface-Vererbung. Und kein grosser Fan heisst ich mag es ganz und gar nicht. Macht alles nur unübersichtlich und kompliziert 🙂


  • Mod

    @hustbaer sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Achja, vergessen:

    @SeppJ sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Aber ich würde davon absehen, eine Vererbungshierarchie in C zu implementieren, wenn man sie dann nicht nutzt.

    Ich würde allgemein davon abgesehn eine Vererbungshierarchie zu implementieren wenn man sie nicht nutzt. Bin auch überhaupt kein grosser Fan von Vererbung -- abgesehen von reiner Interface-Vererbung. Und kein grosser Fan heisst ich mag es ganz und gar nicht. Macht alles nur unübersichtlich und kompliziert 🙂

    Ja, ich auch nicht. Aber wenn wir feste Vertexklassen mit unterschiedlich vielen Edges haben wollten, dann würde ich für diesen Fall Vererbung einsetzen. Aber ich würde es nicht tun, sondern dann stattdessen einfach einen allgemeinen N-Vertex programmieren. Man mag zwar denken, dass das ineffizient ist, weil der sein N mitschleppen muss, aber dafür würde die ganze Indirektion für die Polymorphie wegfallen, die man im anderen Fall hätte.

    Bzgl "My": Ja, im privaten Teil darfste das natürlich gerne machen, ich hatte das hier als public-Schnittstelle verstanden.

    @wob sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Wie wärs hier mit "namespace icm" (für "Infinity Cube Mirror")
    Und dann icm::Vertex und icm::Edge?

    Hat imho das gleiche Problem, dass es eine allgemeine graphentheoretische Eigenschaft unnötig auf das spezielle Problem einschränkt. Die vorgeschlagene Datenstruktur ist (ohne solche speziellen Namen) ja schließlich komplett wiederbenutzbar für jedes Graphenproblem. Und das ist ja gerade die Stärke von gutem Design, dass man Wiederbenutzbarkeit gewinnt. Du entwickelst deine Software für deinen ICM, aber gewinnst gleichzeitig eine ausgereifte Graphenlibrary für alle weiteren Projekte, die du dort ohne jedwede Änderung einsetzen kannst. Eine spezielle Kombination von solch einem allgemeinen Vertex und einer Nutzlast für den Farbwert einer LED, das wäre dann ein Kandidat für den Namen ICM-Vertex



  • @SeppJ sagte in Datenstruktur für Dodekaeda (Infinity Cube Mirror):

    Du entwickelst deine Software für deinen ICM, aber gewinnst gleichzeitig eine ausgereifte Graphenlibrary für alle weiteren Projekte, die du dort ohne jedwede Änderung einsetzen kannst.

    Ich hab halt die Erfahrung gemacht dass das dabei so gut wie nie was gutes rauskommt. Entweder es klappt überhaupt nicht, weil der Entwickler es gar nicht wirklich probiert hat. Und der Manager wundert sich dann beim nächsten Projekt weil er glaubt "der Teil ist ja schon fertig". Oder es kommt dabei was raus was man zwar irgendwie aus dem Projekt raustrennen und dann eigenständig verwenden kann, was aber vom Funktionsumfang her einfach nicht reicht um es allgemein zu verwenden.

    Das sieht man auch immer wieder in Open Source Libraries, darunter auch einige recht beliebte. LibUV z.B. ist IIRC als "Backend" für Node entstanden, und man merkt am Design und der Art und Weise wie die Library zu verwenden ist deutlich dass sie nicht als allgemeine async-IO und platform abstraction Library geplant/entwickelt wurde. Boost.ASIO ist da viel runder & geschmeidiger.

    Und da spare ich mir dann lieber gleich die Arbeit es zu versuchen. Denn etwas als allgemeine Library zu implementieren ist IMO viel viel mehr Aufwand als es spezifisch auf ein Projekt zurechtgeschnitten zu implementieren.

    Eine allgemein verwendbare Lösung kann man dann beim 2. oder 3. Projekt angehen wo man die selbe funktionalität braucht. Genau so wie ich nicht jede Funktion in kleinste 2-3 Zeilen Stückchen zerhacke die alle für sich universell verwendbar sind, wenn diese dann nur an einer Stelle aufgerufen würden. Ich mache das beim 2. oder 3. mal wo ich so ein Stückchen Code brauche.
    Der Vorteil davon ist nicht nur dass man sich Zeit spart, sondern auch dass man beim 2. oder 3. mal mehr über die Anforderungen weiss als beim 1. mal. Weil man dann schon 2 bzw. 3 verschiedene "Anwender" der gewünschten Funktion/Klasse/Library kennt.


  • Mod

    Meine Erfahrung ist auch, dass nie etwas rauskommt. Aber vor allem, weil es nie jemand ernsthaft von Anfang an so etwas versucht, mit genau den von dir gegebenen Argumenten. Nach dem 3. Projekt hat man dann eben drei inkompatible Spezialimplementierungen, und das Vereinheitlichen würde genau so viel Arbeit machen wie eine Neuentwicklung, daher macht man es dann auch nicht, und lebt lieber mit dem 3-fachen Wartungsaufwand.



  • Meine Erfahrung ist auch, dass nie etwas rauskommt. Aber vor allem, weil es nie jemand ernsthaft von Anfang an so etwas versucht, mit genau den von dir gegebenen Argumenten.

    In meiner alten Firma haben wir das ein paar mal versucht. Zwei mal ist was halbwegs brauchbares rausgekommen. Beide male war das aber quasi ein alleingang jeweils eines deutlich überdurchschnittlich fähigen und schnellen Entwicklers. Wobei das aber beides Projekte waren wo wir als Firma schon viel Erfahrung damit hatten, und in einem Fall auch der Entwickler persönlich.

    Die anderen Versuche sind alle gescheitert und meistens wurde viel Zeit rein versenkt die man sich hätte sparen können.

    Nach dem 3. Projekt hat man dann eben drei inkompatible Spezialimplementierungen, und das Vereinheitlichen würde genau so viel Arbeit machen wie eine Neuentwicklung, daher macht man es dann auch nicht, und lebt lieber mit dem 3-fachen Wartungsaufwand.

    Ich meinte eher man macht es für das 3. Projekt allgemein, nicht nach dem 3. Projekt. Und man muss Projekte 1 und 2 ja nicht unbedingt auf das neue System umstellen. Aber Projekt 4 kann man dann auf das neue Ding aufbauen.


    Was ich damit nur sagen will: die von mir gebrachten Argumente sind nichts was ich jetzt irgendwem nachplappere. Das sind Erfahrungswerte.

    Was auch funktioniert (auch ein Erfahrungswert), ist gleich bei Projekt 1 zu versuchen es allgemein zu machen. Dann bei Projekt 2 draufzukommen dass es nicht passt, und dort wieder zu versuchen eine neue allgemeine Version zu machen. So lange bis dabei mal etwas rauskommt was wirklich allgemein verwendbar ist. Dabei versenkt man allerdings viel Zeit mit den zum Scheitern verurteilten Versuchen. Und ob man dabei so viel mehr lernt als wenn man es für Projekte 1 und 2 gleich gar nicht versucht, weiss ich nicht.
    Und es besteht die Gefahr dass sich ein "Druck" entwickelt den verunglückten ersten oder zweiten Versuch doch im nächsten Projekt zu verwenden, obwohl er vorn und hinten nicht passt. Das kann vom Management kommen oder manchmal sogar von den Entwicklern -- schlechtes Gewissen Zeit zu verschwenden oder manchmal eine dumme Form von Faulheit (dumm weil sie einem dann später sehr viel sehr lästige Arbeit macht).



  • @hustbaer Danke vielmals für die Aufgliederung. Wird immer wieder gebraucht, wie ich sehe! 😃