[Projektvorstellung] Wegfindung

[Crymes]

Hallo,
ich möchte hier mein Projekt vorstellen.
In dem Java-Programm geht es darum, einen Weg in einer Welt aus willkürlichen Linien zu finden.

Das Wichtigste zur Bedienung des Programms:

(oben rechts steht Erstellen)

- linke Maustaste gedrückt halten, die Maus bewegen und loslassen: Linie/Wand erstellen

- rechte Maustaste drücken: Ball erstellen, der sein Weg zum Ziel sucht

- Mausrad drücken: Ziel erstelln, zu dem die Bälle ihren Weg finden müssen

- t: Wechselt den Wegfindungsmodus, mit dem neu erstellte Bälle ihren Weg finden

- schnell: naive Wegfindung, ein Wegpunkt nach dem anderen
- Tiefensuche: berechnung des Weges mithilfe der Tiefensuche im Graphen der Wegpunkte
- Breitensuche: berechnung des Weges mithilfe der Breitensuche im Graphen
- Vorberechnung: die Wege werden von zufälligen Startpunkten mithilfe der Breitensuche zum Ziel berechnet, wenn ein Ball den Weg ohne Hindernis erreichen kann, so folgt er diesem Weg bis zum Ziel

- m: Wechselt zwischen den Modi "Erstellen" und "Löschen" (steht oben rechts)

Im Modus "Löschen" hat die Maus folgende Belegung:

- linke Maustaste drücken, die Maus bewegen und loslassen: Zeichnet ein Viereck, innerhalb dem alle Linien gelöscht werden.
- rechte Maustaste drücken: Wenn der Mauszeiger über einem Ball ist, so wird dieser gelöscht.
- Mausrad drücken: Wenn der Mauszeiger über einem Tor ist, so wird dieses gelöscht.

- c: Wechselt zwischen den Modi "mit Kollision" und "ohne Kollision", jeder neu erstellte Ball bekommt den zum Zeitpunkt des Erstellens angezeigten Modus.

Wer Interesse hat, dem kann ich per Mail noch eine Dokumentation/Präsentation und den Source Code senden. (Der Source Code sollte aber mit in der Jar sein)
Viel Spaß beim ausprobieren

 

[Multithread]

Wie sieht es mit der Wegperformance aus? So wie ich das sehe können ja mehrere Tausend einträge in der Queue warten.

Ansonsten ein netes kleines Projekt

 

[Hansvonwurst]

Schaut ganz interessant aus!
Hast du schon versucht sowas wie Dijkstras Algorithmus zu implementieren um die kürzesten Wege zu finden? Denn momentan erscheint mir die Wegfindung nicht wirklich effitzient. Im Anhang hat der Ball da ca. 5 Minuten verbracht, ohne dass er seine Position wirklich großartig verändert hat. (danach hab ich es beendet)

 

[Crymes]

@Multithread
Mit der Tiefensuche gehts so bis 5-10 Linien, mit der Breitensuche bis deutlich mehr.
Irgendwann wird aber kein Weg mehr in einer vernünftigen Zeitspamne gefunden.
Ich kann den Dijkstra Algorithmus nicht verwenden, da jeder Wegpunkt mindestens 2-Mal gefundrn wird und der Algorithmus dann im Kreis laufen würde.

@HansvonWurst
In deinem Screenshot hast du den Modus "ohne Kollision", der ist verbuggt und der Ball hängt am Rand und kommt da nicht mehr weg. Um das richtig zu lösen müsste man z.B. Box2D nehmen, bin ich aber zu faul dazu

 

[Multithread]

@Multithread
Mit der Tiefensuche gehts so bis 5-10 Linien, mit der Breitensuche bis deutlich mehr.
Irgendwann wird aber kein Weg mehr in einer vernünftigen Zeitspamne gefunden.
Ich kann den Dijkstra Algorithmus nicht verwenden, da jeder Wegpunkt mindestens 2-Mal gefundrn wird und der Algorithmus dann im Kreis laufen würde.

Ich sehe das problem nicht
Doppelte Einträge kannst du ja vor dem anwenden des Algorithmus einfach raus löschen.

 

[Crymes]

Man hat folgende Linienwelt:
-------c----------------
| | |
|b | |------- ---
| a| | |
---d-------- ---z--

a,b,c,d wären einige von vielen möglichen Positionen. Dijkstra würde immer im Kreis gehen da a,b,c und d immer neu entdeckt werden und günstiger liegen als das Ziel z.

Edit: Mist, die Leerzeichen werrden immer rausgenommen und alles verrutscht. Vll. erkennt mab trotzdem was ich mein.

 

[Multithread]

Deshalb sollte man sich auch merken wo man schon war

Dafür empfiehlt sich aber ein Array, wegen der Performance, wenn das voll ist, manuell array copy und einige Hundert oder 1000 einträge mehr machen beim neuen. -> Problem solved.

Und dann in den noch zu gehenden Wegen alles rauslöschen was schon im array ist, solltest du die noch zu gehenden Wege aktuallisieren.

 

[Crymes]

Bei dem "merken wo man schon war" taucht meiner Meinung nach das Problem auf: Ich teste die möglichen Positionen mit einem Strahl, daher ist es unwahrscheinlich dass ich zweimal exakt die gleiche Position bekomme. Wenn ich jetzt nach 2 Positionen wieder in der Nähe der ersten bin, was garantiert dann dass die Positionen praktisch die gleichen sind und mir die Neue nicht einen Vorteil für den nächsten Strahl bringt ?

Evt. könnte man das alles austesten, aber ob man dann Dijkstra noch performant läuft ?

 

[DarkMo]

Edit: Mist, die Leerzeichen werrden immer rausgenommen und alles verrutscht. Vll. erkennt mab trotzdem was ich mein.

probier mal code-tags.

 

[Multithread]

Bei dem "merken wo man schon war" taucht meiner Meinung nach das Problem auf: Ich teste die möglichen Positionen mit einem Strahl, daher ist es unwahrscheinlich dass ich zweimal exakt die gleiche Position bekomme. Wenn ich jetzt nach 2 Positionen wieder in der Nähe der ersten bin, was garantiert dann dass die Positionen praktisch die gleichen sind und mir die Neue nicht einen Vorteil für den nächsten Strahl bringt ?

Evt. könnte man das alles austesten, aber ob man dann Dijkstra noch performant läuft ?

Dann musst du eben tricksen.

Die kleinste grösse die du hast sind Pixel, ergo kannst du zb die einzelnen Pixel Positionen testen.
Die Idee mit dem Strahl ist zwar nicht so schlecht, für grössere Felder aber irgendwann zu ineffizient.

Wenn der Ball nicht über die Linien rollen kann, kannst du als grösse sogar 'Radius /sqrt(2)' nehmen und hast entsprechend viel weniger Felder zum Prüfen
Damit hättest du zwar nicht ganz 100% aller möglichen Wege (wegen engen gassen), jedoch wäre es durchaus 'Performant'.

Oder du kannst das 'ende' eines jeden Strahles auf 1-3 Pixel runden, dann geht das mit der Liste wieder.


Manchmal muss man ganz neue ansätze gehen. Andere haben Genauso Probleme mit der Performance irgendwo.