Hey Leute,
eine kleine Aufgabe für Euch und evtl. könnt Ihr mir helfen, meine Lösung zu verbessern. Kommen wir gleich zum Thema.
Die Aufgabe besteht darin, den kürzesten Weg zwischen zwei Orten zu finden. Konkret bezieht sich das Ganze auf das Spiel EVE-Online. EVE-Online ist mit das größte MMO, das es gibt. Es existiert seit nun fast 13 Jahren. Die Welt von EVE-Online ist die Galaxy "New Eden". Es gibt 5201 verbundene Sonnensysteme, genannt K-Space (Known-Space). 2604 nicht direkt verbundene Sonnensystem W-Space (Wormhole-Space) und 230 nicht zu erreichende Sonnensysteme, der Jove-Space.
Sonnensysteme sind zusammegefasst in Constellations, Constellations sind zusammengefasst in Regions. Sonnensysteme haben verschiede Security-Classes => High-Sec, Low-Sec und 0-Sec. Das aber nur am Rande. Hier geht es nur um die 5201 untereinander erreichbaren Sonnensysteme.
evemaps.dotlan.net/map
Dies ist die Darstellung der Regionen. Mit einem Klick auf eine beliebige Region erhaltet Ihr die Übersicht der in dieser Region enthaltenen Sonnensysteme.
evemaps.dotlan.net/map/Lonetrek#sec
Beispielsweise die Region "Lonetrek".
Jedes Sonnensystem enthält mindestens 1 Stargate, welches zu einem anderen Sonnensystem führt. Manche Systeme haben Verbindungen zu mehreren benachbarten Systemen.
evemaps.dotlan.net/map/Lonetrek/Nalvula#sec
Am Beispiel Sonnensystem "Nalvula" (hier schwarz umrahmt) in der Region "Lonetrek". "Nalvula" hat jeweils eine Verbindung zu "Jan", "Vuorrassi", "Oimmo", "Otsasai", "Taisy" und "Hakonen".
Will ich nun vom System "Nalvula" nach "Mara" (4 Systeme, ausgehend von "Nalvula", links und eines runter) reisen, ergibt sich folgende Route:
evemaps.dotlan.net/route/Nalvula:Mara
Wenn Ihr nochmal eine Blick auf die Map werft, seht ihr aber, dass noch eine zweite Route, mit der gleichen Entfernung (Jumps) möglich gewesen wäre.
Nalvula => Vuorrassi => Hageken => Uosusuokk => Piekura => Mara
Es sind noch weit aus mehr Routen möglich, die aber aufwändiger wären.
Jedes Sonnensystem hat eine Position in der Galaxy (X, Y, Z). Jedes im Spiel befindliche Objekt hat diese Position. Anhand dieser Koordinaten lässt sich die Entfernung in AU (Astrometic Uint) oder LY (Light Year) berechnen. Dies ist der Grund, warum diese Route evemaps.dotlan.net/route/Nalvula:Mara ausgegeben wurde und nicht die Alternative. Aber auf das lege ich keinen Wert. Wenn jemand wirklich überhaupt Lust hat, sich da hineinzudenken, einfach als Fleissaufgabe ansehen.
Die Definition für die kürzeste Route soll die Anzahl der Gate-Jumps sein, nicht die zurückzulegende Entfernung.
All diese Daten werden von CCP, das ist das Unternehmen, das hinter EVE-Online steht, bereitgestellt. Nein, ihr braucht Euch nicht darum kümmern. Ich habe fast das komplette EVE-Universum in Code abgebildet. Alle Daten, die zur Durchführung der Aufgabe nötig sind, erhaltet Ihr von mir.
Im Anhang findet Ihr eine Projektmappe (DLL-Projekt). Übersetzt es und verweist in einem Projekt auf diese .dll.
Wird Eure Anwendung dann zum 1. mal gestartet, wird es ein bisschen dauern. Die nächsten Starts laufen dann schneller. Nachdem das Universe erstellt wurde, liegt es in serialisierter Form in Eurem Debug-Ordner (eveUniverse.dat)
Um mit der Arbeit zu beginnen, benötigt Ihr die 5201 verbundenen System (K-Space). Dazu:
Die Variable kSpace enthält nun eine Auflistung aller relevanten Systeme. Für die Lösung der Aufgabe wichtig ist Folgendes:
Die Klasse Solarsystem enthält eine Auflistung der benachbarten Systeme (AdjacentSystems), sowie die Koordinaten im Universum, falls Ihr auch an die Zusatzaufgabe ranwollt. Meine, zugegeben, recht dürftige Umsetzung der Aufgabe findet Ihr in der Klasse Universe => CalculateRoute. Ich bin, was Logik und Mathematik angeht, eher recht weit unten anzusetzen. Das Projekt habe ich letztes Jahr im Dezember begonnen und konnte die Aufgabe nicht zu meiner Zufriedenheit lösen.
Ich wollte alle möglichen Routen vorberechnet haben und dachte zuerst, meine erste Umsetzung wäre gut. So sind 3 PCs über eine Woche 24/7 gelaufen und haben alle Kombinationen durchgerechnet. Danach musste ich leider feststellen, dass mein Ansatz fehlerhaft war. Danach habe ich das Projekt nicht mehr angerührt. Die in der Projektmappe enthaltene Routenberechnung funktioniert soweit und ich konnte bisher keine Fehler feststellen, jedoch lässt die Performance doch sehr zu wünschen übrig.
Mein Ziel ist es, nochmals einen Versuch zu starten, alle Routen im Voraus zu berechnen.
Noch gut zu wissen ist, dass jedes Solarsystem eine ID hat. Jedes Objekt im Universum hat eine ID. Es ist mit Sicherheit schneller, nur diese IDs als Grundlage für die Berechnung zu nutzen. Dies überlasse ich jedoch Euch.
Um Eure Ansätze zu überprüfen, könnt Ihr diese Seite verwenden:
evemaps.dotlan.net/route
oder als direkt URL: evemaps.dotlan.net/route/nalvula:mara
Die Werte hinter dem letzten Slash entsprechend abändern.
Das gesamte Projekt ist, ebenfalls zugegeben, niemals sauber ausprogrammiert worden. Es ist eher aus einer Laune heraus entstanden. Darum bitte ich um Nachsicht für den schlampigen Code.
Ich bin echt gespannt, wie Ihr das umsetzt.
Viel Spass und Fragen jederzeit hier posten.
eine kleine Aufgabe für Euch und evtl. könnt Ihr mir helfen, meine Lösung zu verbessern. Kommen wir gleich zum Thema.
Die Aufgabe besteht darin, den kürzesten Weg zwischen zwei Orten zu finden. Konkret bezieht sich das Ganze auf das Spiel EVE-Online. EVE-Online ist mit das größte MMO, das es gibt. Es existiert seit nun fast 13 Jahren. Die Welt von EVE-Online ist die Galaxy "New Eden". Es gibt 5201 verbundene Sonnensysteme, genannt K-Space (Known-Space). 2604 nicht direkt verbundene Sonnensystem W-Space (Wormhole-Space) und 230 nicht zu erreichende Sonnensysteme, der Jove-Space.
Sonnensysteme sind zusammegefasst in Constellations, Constellations sind zusammengefasst in Regions. Sonnensysteme haben verschiede Security-Classes => High-Sec, Low-Sec und 0-Sec. Das aber nur am Rande. Hier geht es nur um die 5201 untereinander erreichbaren Sonnensysteme.
evemaps.dotlan.net/map
Dies ist die Darstellung der Regionen. Mit einem Klick auf eine beliebige Region erhaltet Ihr die Übersicht der in dieser Region enthaltenen Sonnensysteme.
evemaps.dotlan.net/map/Lonetrek#sec
Beispielsweise die Region "Lonetrek".
Jedes Sonnensystem enthält mindestens 1 Stargate, welches zu einem anderen Sonnensystem führt. Manche Systeme haben Verbindungen zu mehreren benachbarten Systemen.
evemaps.dotlan.net/map/Lonetrek/Nalvula#sec
Am Beispiel Sonnensystem "Nalvula" (hier schwarz umrahmt) in der Region "Lonetrek". "Nalvula" hat jeweils eine Verbindung zu "Jan", "Vuorrassi", "Oimmo", "Otsasai", "Taisy" und "Hakonen".
Will ich nun vom System "Nalvula" nach "Mara" (4 Systeme, ausgehend von "Nalvula", links und eines runter) reisen, ergibt sich folgende Route:
evemaps.dotlan.net/route/Nalvula:Mara
Wenn Ihr nochmal eine Blick auf die Map werft, seht ihr aber, dass noch eine zweite Route, mit der gleichen Entfernung (Jumps) möglich gewesen wäre.
Nalvula => Vuorrassi => Hageken => Uosusuokk => Piekura => Mara
Es sind noch weit aus mehr Routen möglich, die aber aufwändiger wären.
Jedes Sonnensystem hat eine Position in der Galaxy (X, Y, Z). Jedes im Spiel befindliche Objekt hat diese Position. Anhand dieser Koordinaten lässt sich die Entfernung in AU (Astrometic Uint) oder LY (Light Year) berechnen. Dies ist der Grund, warum diese Route evemaps.dotlan.net/route/Nalvula:Mara ausgegeben wurde und nicht die Alternative. Aber auf das lege ich keinen Wert. Wenn jemand wirklich überhaupt Lust hat, sich da hineinzudenken, einfach als Fleissaufgabe ansehen.
Die Definition für die kürzeste Route soll die Anzahl der Gate-Jumps sein, nicht die zurückzulegende Entfernung.
All diese Daten werden von CCP, das ist das Unternehmen, das hinter EVE-Online steht, bereitgestellt. Nein, ihr braucht Euch nicht darum kümmern. Ich habe fast das komplette EVE-Universum in Code abgebildet. Alle Daten, die zur Durchführung der Aufgabe nötig sind, erhaltet Ihr von mir.
Im Anhang findet Ihr eine Projektmappe (DLL-Projekt). Übersetzt es und verweist in einem Projekt auf diese .dll.
Wird Eure Anwendung dann zum 1. mal gestartet, wird es ein bisschen dauern. Die nächsten Starts laufen dann schneller. Nachdem das Universe erstellt wurde, liegt es in serialisierter Form in Eurem Debug-Ordner (eveUniverse.dat)
Um mit der Arbeit zu beginnen, benötigt Ihr die 5201 verbundenen System (K-Space). Dazu:
Die Variable kSpace enthält nun eine Auflistung aller relevanten Systeme. Für die Lösung der Aufgabe wichtig ist Folgendes:
VB.NET-Quellcode
- Imports EveUniverse
- Module Module1
- Private _universe As Universe = Universe.BuildDefaultEveUniverse()
- Sub Main()
- Dim kSpace As IEnumerable(Of Solarsystem) = _universe.Solarsystems.Where(Function(x) x.IsKSpace)
- Dim y As Solarsystem = kSpace(0)
- y.AdjacentSolarsystems.ForEach(Sub(z)
- Console.WriteLine(z.SystemName)
- End Sub)
- Console.ReadLine()
- End Sub
- End Module
Die Klasse Solarsystem enthält eine Auflistung der benachbarten Systeme (AdjacentSystems), sowie die Koordinaten im Universum, falls Ihr auch an die Zusatzaufgabe ranwollt. Meine, zugegeben, recht dürftige Umsetzung der Aufgabe findet Ihr in der Klasse Universe => CalculateRoute. Ich bin, was Logik und Mathematik angeht, eher recht weit unten anzusetzen. Das Projekt habe ich letztes Jahr im Dezember begonnen und konnte die Aufgabe nicht zu meiner Zufriedenheit lösen.
Ich wollte alle möglichen Routen vorberechnet haben und dachte zuerst, meine erste Umsetzung wäre gut. So sind 3 PCs über eine Woche 24/7 gelaufen und haben alle Kombinationen durchgerechnet. Danach musste ich leider feststellen, dass mein Ansatz fehlerhaft war. Danach habe ich das Projekt nicht mehr angerührt. Die in der Projektmappe enthaltene Routenberechnung funktioniert soweit und ich konnte bisher keine Fehler feststellen, jedoch lässt die Performance doch sehr zu wünschen übrig.
Mein Ziel ist es, nochmals einen Versuch zu starten, alle Routen im Voraus zu berechnen.
Noch gut zu wissen ist, dass jedes Solarsystem eine ID hat. Jedes Objekt im Universum hat eine ID. Es ist mit Sicherheit schneller, nur diese IDs als Grundlage für die Berechnung zu nutzen. Dies überlasse ich jedoch Euch.
Um Eure Ansätze zu überprüfen, könnt Ihr diese Seite verwenden:
evemaps.dotlan.net/route
oder als direkt URL: evemaps.dotlan.net/route/nalvula:mara
Die Werte hinter dem letzten Slash entsprechend abändern.
Das gesamte Projekt ist, ebenfalls zugegeben, niemals sauber ausprogrammiert worden. Es ist eher aus einer Laune heraus entstanden. Darum bitte ich um Nachsicht für den schlampigen Code.
Ich bin echt gespannt, wie Ihr das umsetzt.
Viel Spass und Fragen jederzeit hier posten.
Die Unendlichkeit ist weit. Vor allem gegen Ende. 
Manche Menschen sind gar nicht dumm. Sie haben nur Pech beim Denken.
Manche Menschen sind gar nicht dumm. Sie haben nur Pech beim Denken.
