Hallo.

Ich weiß nie wo so Fragen reingehören :-/ Also ab zu den Einsteiger Fragen?
Naja.

Ich habe ne bestimmte Anzahl an Planeten in einer Galaxie.
Wie kann ich jetzt folgendes realisieren:

Will von einem Planeten zum anderen, aber der Treibstoff reicht nicht. muss also über verschiedene Planeten fliegen zum Tanken.
Wie errechne ich mir den kürzesten weg über so wenig Planeten wie möglich?
Allerdings wenn der weg über 1 Planet weiter ist als über 2, dann über 2 planeten.

Wisst ihr was ich meine?

_________________
www.audi32.de

Was meinst du ? Der kürzeste Weg ist immer direkt von Planet 1 zu Planet 2, dass ist denke ich
klar, da dieser aber nicht möglich ist (hast du ja ausgeschlossen)
Muss 1 Zwischenstation eingelegt werden. Der weg mit über eine Zwischenstation ist aber
auf alle Fälle kürzer als der Über 2, da :
Start Ziel
\ /
Zwischens.
im gegensatz zu
Start Ziel
\ /
Zwischens.1-------Zwischens.2
(Müsste man in einen gleichen Massstab bringen und die Planeten als Punkte betrachten).
D.h. im 1.Fall wird die Zwischenstation angeflogen, und dann direkt zum Ziel weiter -> 3 Strecken
Im 2.Fall wird die 1.Zwischenstation angeflogen, dann die 2. und dann zum Ziel ->4 Strecken.
Da die kürzeste Verbindung zwischen 2 Punkten aber immer eine Linie ist, ist Fall 1 in jedem Fall
günstiger (OK, das kann ich nicht wirklich erklären, kann auch sein, dass wir total anneinader
vorbei reden)[am einfachsten kann man sich das vorstellen, wenn man
die 1.Zwischenstation als Startpunkt nimmt. Im 1.Fall fliegt man direkt weiter, im 2. macht man einen
Umweg.

Am besten du gibst mal ein Fallbeispiel oder so.

mfG
Tomok

_________________
Bevor du definierst, was etwas ist, versichere dich seiner Existenz.

Naja ich habs mal in 2D gemalt...

Nicht immer ist der weg über 2 planeten länger als über einen ...
Wie hier zB siehst du das es über 2 kürzer ist, aber das wäre nicht so schlimm.
Ich weiß es momentan nichtmal anzustellen, das ich den nächsten planeten in richtung des ziels aussuchen kann.
(Dazu muss ich sagen, 1 und 4 sind ziel und start)

_________________
www.audi32.de

Ich poste mal den Basic-Code von einem Annäherungsverfahren für Planetenbewegung, was ich in meinem Physikbuch entdeckt habe

Oder... Ach was soll's... Hab jetzt doch mal nach Pascal übersetzt ^^:

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

@ Frase:

Da ist ja auch Grafitation dabei?!
Evtl. habe ich die Frage falsch gestellt... schau dir mal das Bild an was jetzt drin ist, aber trotzdem danke für die Hilfe

_________________
www.audi32.de

Achso, hatte vergessen, dass andere Strecken evtl. auch zu lang sind.

_________________
Bevor du definierst, was etwas ist, versichere dich seiner Existenz.

Achso. Na das ist doch wirlich einfach ^^ Schonmal was vom Satz des Pythagoras gehört?

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Ja den kann ich, ich kann mir auch die strecken ausrechnen
Ah, jetzt komm ich auf die idee ^^

Also am besten ich geh alle durch zu denen ich anfliegen kann und dann schau ich noch welcher am nächsten am ziel ist?
Aber das kann auch einen ziemlich großen umweg geben :-/
Ich müsste alle möglichen strecken durchgehen und dann addiert die kürzeste?!
Aber das wäre doch unglaublich zum berechnen?! bei so ca. 50 planeten...
Das soll recht zügig gehen (ist jetzt net jeden render durchlauf aber ... meint ihr das ist noch ok)

_________________
www.audi32.de

Das is mal wieder ein hervoragendes Beispiel für eine Problem was man mittels gewichteten Graphen lösen kann.

Also einfach beim erstellen deiner Map (oder wann auch immer) alle Entfernungen zu den möglichen Nachbarn berechnen (die in reichweite liegen) und mit speichern. Danach kannst du ne A* auf deinem Graph laufen lassen. Und fertig.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Da müsste ich viel speichern
Jedes Schiff hat verschiedenen Tank und können (also wenns fertig ist) die Entfernungen entwickeln.

_________________
www.audi32.de

Auch wenn wir hier bei den Einsteiger-Fragen sind, klingt mir deine Antwort ein wenig zu einfach. Zum einen, wieso ne komplette A* basteln, wenn es um sowas einfaches geht? Wieso Graphen implementieren, wenn es mit ein paar Additionen getan ist?

Also Adler:
Du speicherst pro Planet, welche Planeten von ihm aus erreichbar sind und wie lange jeder dieser Wege ist.
Später dann, wenn du dein Raumschiff wohin schickst, prüft es rekursiv jeden Planeten in Reichweite und die Länge des Weges dorthin. Und so weiter, bis du schließlich am Ziel bist.

(Wer es nicht gemerkt hat... Das war Pathfinding für PDAs ^^)

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

So einfach ist das leider nicht. Das kann nämlich richtig Zeit kosten das rekursive Prüfen, da du keine Vorzugsrichtung hast. A* hat sowas über seine Heuristik. Deshalb is der auch so fix. Dein Ansatz deckt sich aber mit dem Meinigen (Liste der Nachbarn + Entfernung), nur stellte sich mir die Frage, was ein Nachbar ist, da die Schiffe unterschiedliche Reichweiten haben. @Adler: Du müsstest also ne maximale Reichweite vorgeben. Alle Planeten die in dieser Liegen sind Nachbarn des aktuellen Planeten. Zu jedem Nachbarn speicherst du dann die Entfernung (das ist die Gewichtung der Kante aktPlantet<->Nachbar). Die Planeten sind dann deine Knoten. Somit hast du einen super Graph. Und das tolle an Graphen ist, dass alle Wegfindungsalgorithmen auf diesen Funktionieren. (Z.B. der A*, welcher zweifellos hier gute dienste tun würde).

Weitere Vorteile von Graphen:

Wenn du dein Universum konstruierst kannst du mit (relativ simplen) Graphalgorithmen herausfinden ob dein Universum zusammenhängen ist (also ob es von jedem Planeten einen Weg zu jedem anderen Planten gibt, oder ob ein Planet soweis außerhalb liegt, dass er niemals erreicht werden kann.

Deine KI kann mit bestimmten Algorithmen leicht strategisch wichtige Planeten herausfinden (Graphentheorie: Artikulationspunkte) falls welche existieren. Art.Pkte sind Knoten welche zwei Teilgraphen verbinden und die benutzt werden MÜSSEN wenn man von dem einen in den anderen will.

Alternative Wege finden dürfte auch kein Problem sein.

Also ich sags mal so: Wer immer was mit KI und Wegsuche vorhat, kommt um Graphentheorie und Bäume nicht herum. Alles andere wird Flickwerk. Graphentheorie hingegen ist durch Mathematik und theoretische Informatik erschöpfend untersucht. Da kann man sich drauf verlassen, dass die Algorithmen das machen was sie sollen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Dieses Problem löst sich wie folgt:
1. Vorraussetzung: Direkte Entfernungen von jedem Planeten zu jedem anderen bekannt.
Dann kannst Du 2. eine Entfernungsmatrix aufstellen: von, bis, über, entfernung
Hier Du in alle Distanzen der Matrix ein: unendlich, wenn aus 1 Entfernung grösser Reichweite oder direkte Entfernung, wenn kleiner Reichweite (über bleibt leer)
Nach diesem ersten Schritt hast Du 'erreichbarkeitsinseln' geschaffen (alle direkten wege sind notiert)
jetzt kannst du 3. den Berechnungsalgorithmus starten:

wiederhole
für jede ÜBER
für jede VON
für jede BIS
wenn (VON nach ÜBER) + (ÜBER nach BIS)<Eintrag VON nach BIS
Dann Ersetze Entfernung und ÜBER in Eintrag
solange bis keine Ersetzung getätigt

Dieser Algorithmus findet mindestens eine 'gute' lösung, wenn Du Glück hast, die 'optimale'
Wichtig ist, in der äußersten Schleive die ÜBER zu durchlaufen, dann ist der Alg n^3logn, wenn du erst über die VONs iterierst, isser n^4
Um den Weg VON nach BIS rauszukriegen fragst Du in der Matrix nach und krigst entweder gleich die Route(wenn ÜBER leer) oder den ersten Zwischenstop (wenn ÜBER nicht leer) in dem Fall must du wieder in die Matrix gucken, aber diesmal mir ÜBER als VON usw.

Ich hoffe, das war jetzt nicht allzu kryptisch

p.s. wenn am schluss noch irgendwo ein unendlich steht, dann gibt es für dieses Schiff keinen Weg (zu kleiner Benzintank)

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Kannst du das nochmal in Deutsch schreiben?

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ja aber erst heute abend ..... also nach 21:00 Uhr, weil ich bin heute mit InsBettBringen dran (Freu!)

VIELLEICHT wird ja auch ein Wiki Artikel draus

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.