Ankündigung

Einklappen
Keine Ankündigung bisher.

Routenberechnung in einem 2D Sonnensystem

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Routenberechnung in einem 2D Sonnensystem

    Hallo Leute,

    ich suche jemanden der mir bei folgender Problemstellung hilft bzw. entwickelt.

    Ausgangssituation ist ein Sonnensystem, in dem mehrere Planeten in kreisförmigen Orbits um eine Sonne kreisen. Die Orbits haben alle den selben Abstand zueinander, sind kreisförmig (keine Ellipsen) und die Planeten rotieren abhänging vom Orbit unterschiedlich schnell um die Sonne. Abhänging davon, wie nah der Orbit der Sonne ist, benötigen die Planeten n * 1440 Minuten (24 Stunden). Orbit 1 ist dabei der Sonne am nächsten. Dann folgt Orbit 2 usw.
    Sonne
    Orbit 1 1440 Minuten
    Orbit 2 2880 Minuten
    Orbit 3 4320 Minuten
    Orbit 4 5760 Minuten
    Orbit 5 7200 Minuten
    Orbit n n * 1440 Minuten

    2.PNG
    Der Orange / Grüne Punkt sowie die Blauen sind Planeten. Der rote Punkt in der Mitte die Sonne und die schwarzen Linien die Orbits.

    Die Koordinaten der Planeten werden dabei in Orbit und aktuelle Gradzahl angegeben. Also Orbit = 1 und Position = 257 oder Orbit = 4 und Position = 23.
    Somit kann möglichst genau die Position jedes Planeten innerhalb des Sonnensystems berechnet werden.

    Die aktualisierungs Rate beträgt 1 Minute. Das heißt, jede Minute sind die Planeten anhand ihrer Geschwindigkeit einen "Schritt" weiter auf ihrem Orbit gegangen.

    Zur berechnung der aktuellen Position eines Planeten habe ich folgende Funktion genutzt:
    PHP-Code:

    // 0.25 = 360/1440, das heißt, der Planet auf dem Orbit 1 wandert um 0.25 Grad pro Minute, der Planet auf dem Orbit 2 um 0.25 / 2 usw.
    $geschwindigkeit 0.25/$planet->Orbit;

    // schritte = geschwindigkeit * aktuelleMinute
    $schritte = ($minute*geschwindigkeit);

    // aktuelle Position = Die aktuelle Position des Planeten addiert mit den Schritte nach x Minuten
    $aktuellePosition $planet->Position +$schritte;

                
    $position = array(
                    
    "x" => (sin(deg2rad(aktuellePosition)) * 50 $planet->Orbit),
                    
    "y" => (cos(deg2rad(aktuellePosition)) * 50 $planet->Orbit)
                ); 
    Die 50 beschreibt den Abstand zwischen den verschiedenen Orbits.

    Als weitere Komponente zu dem ganzen kommen die Raumschiffe hinzu.
    Diese fliegen mit einer Geschwindigkeit von x pro Minute durchs Weltall.

    Soviel zur Ausgangssituation.


    Nun würde ich ganz gerne den die Route von einem Planeten zu einem anderen berechnen und in kleinere Teilvektoren aufsplitten. Die Bedingungen sind:
    • Raumschiffe dürfen NICHT durch die Sonne fliegen.
    • Raumschiffe dürfen NICHT in einen Bereich um "feindliche" Planeten fliegen
    • Raumschiffe sollen immer den schnellsten/kürzesten Weg fliegen.

    3.PNG

    Folgende Grafik als Beispiel:

    Ich möchte von grünen Planeten zum orangen Planten fliegen. Die Blauen Planeten sind alle "feindlich", daher möchte ich in einem Abstand von x um diese herumfliegen. (Die blauen Punkte sind die Planeten und die blauen Kreise herum der "Sicherheitsabstand").

    Zu beachten ist halt, das alle Positionen sich pro Minute verändern. Ein einfacher Vektor ist daher nicht möglich. Auch muss die Reisegeschwindigkeit von Raumschiffen beachtet werden sowie der Sicherheitsabstand und die Sonne.



    Ich glaube ich habe nun alles erklärt sowie alle relevanten Daten und Variablen geliefert.

    Ich hoffe jemand kann da Helfen oder nimmt sich dem an.

    Angebote und weitere Nachfragen gerne per PM an mich.

    Mit freundlichen Grüßen,

    Tim Heise


  • #2
    Schnell und kurz ist ja in diesem Fall nicht (immer) äquivalent. Kurz wäre die direkte Verbindung (Gerade) zwischen Start und Ziel, das würde aber die Planeten vernachlässigen. Was soll nun also passieren, wenn ein Raumschiff auf einen "Planetenradius" trifft? Eine einfache Möglichkeit wäre warten oder entlang des Radiuses vorbei fliegen (unter Berücksichtigung der Dymnamik, da sich der Radius/Planet ja auch bewegt.) Ich weiß allerdings nicht, ob das dann die optimale Lösung ist, insbesondere wenn es viele Planeten gibt. Kreisen alle Objekte in die selbe Richtung? Generell halte ich dieses Optimierungsproblem aber schon eher für schwierig.

    Kommentar


    • #3
      Hi, danke für die Antwort.

      Ja, das Problem ist was schwieriger. Deswegen hoffe ich hier auf Lösungen. Mein bisheriger Ansatz war der, dass ich erstmal den kürzestens Weg als gerade Berechne und die anderen Planeten ignoriere.
      Sobald ich dann den kürzestesn Vektor habe dividiere ich diesen durch die Anzahl der Minuten die ich bis zum Ziel Planet gebraucht habe. Damit habe ich den Vektor welche meine Schiff pro Minute gehen müssen um auf dem kürzestens Weg zum Ziel zu kommen.

      Anschließend "simuliere" ich den Weg, gehe für jede Minute den "Weg" entlang. Sollte ich dann auf ein Hinderniss treffen, gehe ich den Weg 10 Schritte zurück, reduziere die vergangenen Minuten um 10 und gehe parallel um 90° "links" und 90° "rechts" für 10 Schritte (das sind die Rückgängiggemachten 10 Minuten). Am Ende dieser zwei neuen Pfade berechne ich wieder den kürzestens Pfad (oben der Teil) zum Ziel. Das mache ich solange bis ich einen Pfad habe der am Ziel angekommen ist.

      Die Lösung ist nur absolut unsauber. Die 90° stören und sind nicht elegant. Lieber wäre ein vorbei Fliegen am Radius unter Berücksichtigung des Planeten.

      Ob die Lösung optimal ist un da das ein schwieriges Problem ist suche ich ja wie gesagt hier nach Hilfe.

      Kommentar


      • #4
        Wie wärs mit A* ? du hast ja schön die Planeten auf einem Grid abgebildet, wenn du jetzt von der Sonne, sowie den "Feindlichen" planeten die x/y Koordinaten ermitteln kannst zur Minute X, kannst du mit A* den Kürzesten Weg Berechen.

        quasi hast du da "Bounding Boxes" http://imgur.com/a/szI5y.

        Ich hab dazu eine Library erstellt https://github.com/BlackScorp/astar (nutze bitte version 1.0.1 die neueste ist Verbugt und ich bin zu Faul) auf jeden fall, wenn du aus deiner Abbildung ein 2 Dimensionales Array erstellst und dabei die Bounding Boxes blockierst, kannst du für Minute X den kürzesten Weg ermitteln.


        Übringes ist deine Rechnung oben nicht ganz korrekt, $aktuellePosition ist in radianten und nicht grad

        PHP-Code:
          $position = array(
                
        "x" => ~~(sin(rad2deg($aktuellePosition)) * 50 $planet->Orbit),
                
        "y" => ~~(cos(rad2deg($aktuellePosition)) * 50 $planet->Orbit)
            ); 
        kriegst du bessere Zahlen raus

        EDIT: https://pastebin.com/iQHD2Khz hab da die Max und Min Werte des Koordinaten Systems schon mal herausgefunden, daraus machst du ein Grid, blocks die Bereiche mit den Planeten und mi A* findeste du den Kürzesten Weg
        apt-get install npm -> npm install -g bower -> bower install <package> YOLO [URL]https://www.paypal.me/BlackScorp[/URL] | Mein Youtube PHP Kanal: [url]https://www.youtube.com/c/VitalijMik[/url]

        Kommentar


        • #5
          Danke für den Tip mit dem Radianten.

          Und danke für den Hinwesi mit A*. Ich hab zwar versucht es hiermit zu simulieren. https://qiao.github.io/PathFinding.js/visual/ hab es aber als "nicht umsetzbar" befunden vor 6 Monaten. Das Problem ist die ständige rotation der Planeten. Ich muss das mal ausprobieren. Da ich ja für Minute Werte zwischen 1 und theoretisch 1000 erfahren kann... Ich schau mir deine Bibliothek mal an.

          Danke!

          Kommentar


          • #6
            Also du kannst nicht einmalig A* ausführen und dann den Weg ermitteln und somit wann der Raumschiff da ankommt. Du musst es schon durchspielen, jede Minute verändert sich die Position, also für jede Minute berechnest du den Weg neu bis du dein Ziel erreicht hast.
            apt-get install npm -> npm install -g bower -> bower install <package> YOLO [URL]https://www.paypal.me/BlackScorp[/URL] | Mein Youtube PHP Kanal: [url]https://www.youtube.com/c/VitalijMik[/url]

            Kommentar


            • #7
              Ja, ich muss dann schauen wie oft ich dsa optimal durchlaufen lassen. Danke für den Tip.

              Kommentar


              • #8
                BlackScorp Also ich bin mir jetzt unsicher ob das mit dem rad2deg korrekt ist. Auch die ~~ Helfen mir nicht weiter, weil sie mein System verfälschen...

                Wenn ich den Code anpasse auf meine Ursprüngliche Berechnung komme ich wieder auf meine korrekten Zielwerte (Planet auf Orbit 1 braucht 1440 Minuten zum umkreisen, Planet 2 auf Orbit 2 2880 Minuten usw...)

                PHP-Code:
                $startBase = [2,45];

                $visited = [];
                $da false;
                for(
                $minute 0$minute 100000$minute++)
                {


                    
                //recalc positions

                    
                $start = array(
                        (
                sin(deg2rad($startBase[1] + ($minute*0.25/$startBase[0]))) * 50 $startBase[0]),
                        (
                cos(deg2rad($startBase[1] + ($minute*0.25/$startBase[0]))) * 50 $startBase[0])
                    );

                    
                $key $start[0]."#".$start[1];

                    if(
                array_key_exists($key,$visited))
                    {
                        echo 
                "Ist nach $minute wieder an der Ursprungsposition";
                        
                $da true;
                        break;
                    }
                    else
                    {
                        
                $visited[$key] = true;
                    }
                }
                if(!
                $da)
                {
                    echo 
                "Nope, sorry";

                Mit rad2deg und ~~ werden die Ergebnisse jedoch zu start verfälscht...

                Nur so als Bermerkung. Ansonsten teste ich dein Code noch aus.

                Kommentar


                • #9
                  also schau mal, mein Script von da oben, den kannst du direkt kopieren und der erzeugt dir ein Bild

                  Minute 0 sieht dann so aus:
                  http://i.imgur.com/r75ktIW.png

                  Minute 6:
                  http://i.imgur.com/Fup2Zv1.png

                  Die Minute kann ich per URL bestimmen. Es ist möglich dass die Geschwindigkeit nicht korrekt ist, aber die Einzelnen Punkte drehen sich um die Sonne herum, mach ich rad2deg, dann bleibt X immer und verändert sich nicht viel. Die ~~ kann man auch weglasen, ich hab damit nur die nachkomma stellen weggeschmissen.

                  Vielleicht hab ich dein Koordinaten System nicht verstanden?

                  $startBase kann auch nicht 2/25 sein weil x und y von der Zeit abhängt.

                  Es kann eher sein 3er Planet in Sonnensystem x
                  apt-get install npm -> npm install -g bower -> bower install <package> YOLO [URL]https://www.paypal.me/BlackScorp[/URL] | Mein Youtube PHP Kanal: [url]https://www.youtube.com/c/VitalijMik[/url]

                  Kommentar


                  • #10
                    https://jsfiddle.net/oeme2o70/6/

                    Ich hab hier mal ein kleines JS Beispiel wie das aussehen soll. Im Input Feld mit Mauszeiger hoch/runter einfach die Minuten erhöhen.

                    Alle Planeten (bis auf Start) rotieren dann gemäß deren Geschwindigkeit von Minute*0.25/Orbit.

                    Kommentar


                    • #11
                      Noch als Anmerkung:

                      Die aktuelle Position eines Planeten berechne ich jedesmal wenn der Planet irgendwo geladen wird. Den Wert speichere ich dann ab in der Datenbank. Somit habe ich immer die aktuelle Positon zur aktuellen Zeit.

                      Die Berechnung des Pfades erfolgt dann mit den neu geladenen Positionen der Planeten.

                      Kommentar


                      • #12
                        Wie gesagt, ich würde die Aktuelle projektion in ein Grid umwandeln und bestimmte pixel blocken und dann daraus den weg ermitteln. Das ganze solange machen bis man sein Ziel erreicht hat und daraus hast du dann dein End Tick wann der Raumschiff dann ankommt

                        irgendwie so

                        PHP-Code:
                        $tick $currentTick;
                        $currentPosition = [10,100];
                        do{
                            
                        $data getGalaxyData($tick);
                            
                        $map $data['map'];
                            
                        $targetPlanetPosition $data['targetPlanet']; //Zeilplanet befindet sich bie jedem Tick wo anders, desswegen immer wieder das Ziel abfragen
                            
                        $grid = new BlackScorp\Astar\Grid($map);
                            
                        $startPosition $grid->getPoint($currentPosition[0],$currentPosition[1]);
                            
                        $endPosition $grid->getPoint($targetPlanetPosition[0],$targetPlanetPosition[1]);
                            
                        $astar = new BlackScorp\Astar\Astar($grid);
                            
                        $nodes $astar->search($startPosition,$endPosition);
                            
                        $currentPosition $nodes[1]; //hier wahrschienlich prüfen ob $nodes[1] überhaupt exestiert wenn nicht, ist das ziel erreicht
                            
                        $zielNichtErreich $currentPosition != $targetPlanetPosition;
                        $tick++;
                        }while(
                        $zielNichtErreich);

                        echo 
                        $tick."ticks bis zum Ziel"
                        apt-get install npm -> npm install -g bower -> bower install <package> YOLO [URL]https://www.paypal.me/BlackScorp[/URL] | Mein Youtube PHP Kanal: [url]https://www.youtube.com/c/VitalijMik[/url]

                        Kommentar


                        • #13
                          Daran arbeite ich ja momentan anhand deines Scripts.

                          Kommentar


                          • #14
                            Zitat von CaptainXTimmy Beitrag anzeigen
                            Daran arbeite ich ja momentan anhand deines Scripts.
                            bin echt gespannt wie performant das sein wird hab es selbst noch nie in so einem Fall getestet.

                            Fing halt an mit "Make it work " dann weiter nach "Make it right" und jetzt muss ich noch "Make it fast" einbauen
                            apt-get install npm -> npm install -g bower -> bower install <package> YOLO [URL]https://www.paypal.me/BlackScorp[/URL] | Mein Youtube PHP Kanal: [url]https://www.youtube.com/c/VitalijMik[/url]

                            Kommentar


                            • #15
                              Ich auch! Aber ich hoffe nicht allzuviel. Ist halt abhänging davon wie "groß" das Grid ist...

                              Kommentar

                              Lädt...
                              X