Ich habe ein wenig mit dem A*-Algorithmus experimentiert. Dazu habe ich mir eine Testkarte im Format 400x400 erstellt.
Im Anhang ist der errechnete Weg, funktioniert also.
Bei der Sache gibt es nur 2 Probleme. Das erste wäre, dass die Wege nicht wirklich optimal sind. Der Algorithmus geht immer nur zum nächstgelegenen Nachbarfeld (logisch). Bei einem Weg von 1/1 nach 2/4 wird nicht der direkte Weg gewählt, sonder es wird ein Umweg über 2/2 genommen.
Wie auch immer, das andere Problem ist viel gravierender. Für die Berechnung des Weges (nicht das Generieren der Grafik) im Anhang wurden 21 Sekunden lang bis zu 54 MB Speicher bei einer 100%igen Prozessorauslastung verbraten. Bei 250 Orten sind das ja Tage die der Rechner da heiss laufen würde.
Hinzu kommt dass die Testgrafik recht klein angesetzt war. Die echte Karte wird vermutlich mindestens 2000x1500 abmessen.
Durch solch ein virtuelles Fahrrinnensystem könnte man den Rechenaufwand sicher bedeutend vermindern, da man die Knoten deutlich reduziernen könnte. Leider fehlt mir der Ansatz.
Derzeit lese ich meine Karte aus einer Textdatei ein die im Prinzip so aufgebaut ist:
Code:
000000000000000
000001100000000
000000111110000
000001111111000
000000111100000
000000001110000
000000000010000
000000000000000
0=Wasser 1=Land
Die Datei wird in ein zweidimensionales Array eingelesen womit ich dann den Algorithmus füttere.
Habe ich nun irgend eine Möglichkeit nur bestimmte Routenpunkte zu definieren?
Ich hoffe man konnte mich einigermassen verstehen. Ist mal wieder etwas spät geworden.