Denkanstoß: Wie Verbindungen besser darstellen?

[Namenloser]

Zitat von Dejan Vu:

Vielleicht bringt es was, sich deine Leinwand als z.B. 100x100 Matrix vorzustellen und jede Zelle ist entweder eine Linie (senkrecht, waagerecht, Ecke) oder Teil eines Bausteins (Anschlusspunkt, sonstiges). Und schon kannst Du sehr sauber 'zeichnen'. Mit einem Algorithmus, der den 'optimalen' Weg von A nach B findet, solltest Du beim Layouten schon weit kommen. Die Regeln sind klar: Jede Ecke kostet und das überkreuzen auch.

Genau so hatte ich das gemacht, hat sich nicht wirklich bewährt, wie oben beschrieben.

Edit: Im Anhang mal ein Screenshot. Das Ergebnis sieht schon ähnlich aus wie bei den Komponenten, die Perlsau verlinkt hat (nur weniger schön gezeichnet, z.B. keine abgerundeten Ecken). Das Hauptproblem ist halt, dass die Berechnung von Routen in dieser Qualität bei mir einfach viel zu lange gedauert hat.

[Dejan Vu]

Ah, ist also dein Wegfindealgorithmus suboptimal? Welchen verwendest Du denn? A* würde sich hier anbieten, wobei dem man das 'schräge' -also Zick-Zack- laufen einfach nur abgewöhnen müsste.

PS: Ist doch ordentlich... Bisserl mehr Mühe beim rendern, und schon ist das perfekt. Aber es ist auch so imho vollkommen ausreichend (die Verbindungen sollten halbdurchsichtig sein, das wäre noch besser)

[Namenloser]

Zitat von Dejan Vu:

Ah, ist also dein Wegfindealgorithmus suboptimal? Welchen verwendest Du denn? A* würde sich hier anbieten, wobei dem man das 'schräge' -also Zick-Zack- laufen einfach nur abgewöhnen müsste.

Das ist A*. Der Algorithmus braucht deshalb so lange, weil durch das komplizierte Qualitätsmaß einfach sehr viele mögliche Routen in Frage kommen und er deshalb sehr viele Möglichkeiten durchprobieren muss, bis die optimale Route gefunden ist. Beispiel: Setzt man die Bestrafung für eine Überkreuzung hoch, dann probiert natürlich er einen besseren Umweg zu finden. Je größer man die Bestrafung setzt, desto größer darf der Umweg sein, und das alles kostet eben Zeit. Im Endeffekt läuft A* hier fast auf Brute Force hinaus.

Dass er an den Ecken eine 45°-Kurve macht, ist gewollt. Das ist nicht der Zick-Zack-Fall, den ich meine. Der Zick-Zack-Fall tritt erst bei Platzmangel auf. Ich hab ihn im Anhang mal provoziert. Glaub mir, ich habe wirklich Tage damit verbracht, zu versuchen, ihm das abzugewöhnen, aber es kam immer zu noch schlimmeren Seiteneffekten.

Ich denke, man könnte den Algorithmus nur effizienter zu machen, indem man die Anzahl der in Betrachtung gezogenen Wegpunkte durch irgendeine Vorberechnung reduziert. Bisher wurde hier mit einem einfachen Raster gearbeitet. D.h. auch bei einer geraden Strecke gibt es dadurch sehr viele Abzweigungspunkte, die der Algorithmus ggf. durchprobiert. Wenn man die Anzahl der in Betrachtung gezogenen Punkte durch eine Vorberechnung einschränken würde, würde sich der Suchraum deutlich verkleinern, und dann wäre es vielleicht effizient machbar.