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.