[Monkey] [Erledigt] Algorithmus herausfinden ...
Übersicht
Andere Programmiersprachen Beginners-Corner
|
kogBetreff: [Erledigt] Algorithmus herausfinden ... |
 Fr, Feb 03, 2012 13:21Antworten mit Zitat 
|
|---|---|---|
|
Guten Tag
Ich wende mich in der Verzweifelung wiedermal an euch... Ich versuche schon den ganzen Morgen (in der Nacht sogar davon geträumt...) herauszufinden, wie ich am besten den Schnellsten Weg von A nach B finde: 
Die Grünen sind Energieverbindungen und das Blaue ein Gebäude und das Rote das Kraftwerk sozusagen. Das Gebäude hat ein Feld namens "Pipe" (Für seinen Anschluss) und die Verbindungen haben ein Array mit 5 Einträgen, worin sich ein Gebäude (auch Energieverbindungen) befinden kann. So sind die untereinander verbunden. Doch ich tüftelte schon den ganzen morgen, wie das am besten gehen könnte und verwarf jeden Entwurf wieder, weil keiner funktionierte .... Vielleicht hat jemand von euch eine brennende Idee? Freundliche Grüsse kog |
||
- Zuletzt bearbeitet von kog am So, Feb 05, 2012 1:35, insgesamt 2-mal bearbeitet
|
BladeRunnerModerator |
Fr, Feb 03, 2012 13:28 Antworten mit Zitat
|
|---|---|---|
|
Zum einen, bitte bitte bitte, es heisst: Algorithmus und hat mit dem Rhythmus nichts zu tun.
Zum anderen klingt dein Problem nach einer Sonderform des Problemes des Handlungsreisenden und ist damit nicht gerade trivial, da sich die Wegemöglichkeiten rapide erhöhen können. Eine Breitensuche bietet zwar eine Lösung, ist jedoch unter Umständen sehr langsam. |
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
Tankbuster |
Fr, Feb 03, 2012 13:38 Antworten mit Zitat
|
|---|---|---|
1. Alle möglichen Wege herrausfinden (dabei sollte beachtet werden, dass Wege auch im nichts enden können, bzw hier unendlich in einer Schleife hängen können  )
2. Alle Vektorlängen jedes "guten" weges addieren (mit Vektorlänge meine ich die Entfernung zwischen 2 Punkten des Weges) 3. Den kürzesten Weg gefunden haben
Es gibt sicher auch bessere Lösungen, aber das wird funktionieren
|
||
|
Twitter
Download Jewel Snake! Windows|Android |
||
PhillipK |
Fr, Feb 03, 2012 13:42 Antworten mit Zitat
|
|
|---|---|---|
|
Du möchtest eine Art wegfindung schreiben?
Nun, das ist eigentlich relativ simpel. Ich verweise dich erstmal auf wikipedia :> Nämlich zur Breitensuche Die ist unter Blitzmax schneller als zb. der a* algorythmus. Dieser ist zwar von der Theorie zwar Effizienter und dadurch schneller, aber nach recherchen von Noobody dennoch langsamer, er vermutet, der Garbage Collector sei schuld. Wie dem auch sei, Monkey ist wieder ein anderes Kaliber, da kann ich dir nicht direkt helfen 
Zur Breitensuche: Im regelfall hast du einen ausgangspunkt und unterschiedliche verbundpunkte. Ausgangspunkt: Der erste punkt (startpunkt) befindet sich in einer Liste oder ähnlichem. Listen bieten sich an und existieren auch in Monkey. Nun schreibst du einen algorythmus, bzw eine Whileschleife, die solange aktiv ist, wie noch Punkte in der Liste sind oder der Endpunkt gefunden wurde. Für jeden punkt den du rausholst und "überprüfst" speicherst du die daten irgendwo. Zb in einem Type. Hier brauchst du 1) Wegkosten (ich nenne sie G), 2) den "vorherigen" punkt. Wenn du nun einen punkt findest, welcher bereits abgeklappert wurde, überprüfst du, ob der bisherige weg (die G kosten) 'Teurer' war, als dein "Aktiver" zu prüfunder punkt + Die wegkosten. Wegkosten könnten zb die kleinen Zahlen in deinem Bild sein. Das ganze läuft nun wie folgt ab: A kommt in die liste. Algo startet. A wird rausgeholt, der erste grüne punkt mit der "2" wird gefunden. Der punkt wird in die liste geschoben, du merkst dir ausserdem, das er von "A" erreicht wurde und 2 wegkosten hat. Weitere verbundmöglichkeiten sind nicht gefunden. Ergo: neuer durchlauf. Der grade in die liste gepackte punkt ist dran. Er findet Oben einen punkt mit 3 und unten einen punkt mit 3. Beide kommen in die liste. Bisherige wegkosten: 2+3 (A->punkt1 -> punkt2), der knoten davor: "GrünMit2" ^^ Das geht so weiter, nur das nun wieder nur ein weg pro knoten möglich ist -> irgendwann hast du alle knoten durch und bist bei B. Sofern dein "updaten" bekannter wege funktioniert, dürfte ein relativ schneller weg gefunden sein. (Ich hab grade echt probleme zu erklären, weil ich aus allen ecken und enden genervt werde.. wikipedia wird dir vllt besser helfen  )
|
||
|
|
BladeRunnerModerator |
Fr, Feb 03, 2012 13:44 Antworten mit Zitat
|
|---|---|---|
|
Das alle möglichen Wege finden ist hier der Hemmschuh, das die Anzahl potentieller Wege exponentiell steigt.
Solange keine vernünftige Restkostenschätzung zB anhand der Koordinaten erfolgen kann kommt man auch mit einem AStar nicht weiter. EDIT: Wenn Du jedoch die Koordinaten für eine Kostenschätzung heranziehen kannst hangle dich immer an den Knoten entlang die noch nicht geprüft wurden und aktuell die geringste Kostenschätzung haben. Das führt unter Umständen zu einem sehr raschen Ergebnis und ist hier sicher bedeutend schneller als eine Breitensuche da idR die meisten Wege rasch wegfallen werden und deshalb auch nicht weiter untersucht werden. |
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
- Zuletzt bearbeitet von BladeRunner am Fr, Feb 03, 2012 13:47, insgesamt einmal bearbeitet
|
|
kog |
Fr, Feb 03, 2012 13:46 Antworten mit Zitat
|
|---|---|---|
Danke für die Antworten... Ich hoffe, es kommt dabei was raus 
@PhillipK Ja das klingt gut, mal versuchen es dann umzusetzen... Die Zahlen oben dran, bedeuten wie viele Verbindungen noch möglich sind. Hier das "Spiel": http://kognetwork.ch/UniverseMiner/MonkeyGame.html *Big Edit* Habe nun eine Lösung gefunden und scheint auch zu Funktionieren, bzw. mit den verschiedensten Möglichkeiten die ich zurzeit probierte: 
|
||
Übersicht
Andere Programmiersprachen Beginners-Corner
Powered by phpBB © 2001 - 2006, phpBB Group