Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Ansatz zur Wegfindung

Werbeanzeige

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

1

25.03.2013, 17:24

Ansatz zur Wegfindung

Hallo Community,

für mein Programm bräuchte ich eine Funktion, die die kürzeste Strecke zwischen mehreren Punkten berechnen kann, also die den günstigsten Weg findet.

Ich habe ein zweidimensionales Array, ich nenne es mal Landschaft[x][y].
Diese enthält unterschiedlichste Objekte. Eine 0 bedeutet, dass das Feld leer ist, Felder mit dem Inhalt 1 müssen abgelaufen werden. Felder mit einem Inhalt größer als 1 können ignoriert werden, dürfen aber nicht betreten werden. 9 ist der Startpunkt.

z.b.:
0 | 0 | 1 | 0 | 4 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 5 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
6 | 0 | 0 | 0 | 0 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
0 | 0 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 5 | 0 | 2 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 5 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 3 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 0 | 0 |

Was ich über Wegfindung bisher im Internet gelesen habe hilft mir nicht wirklich weiter, das meiste ist sehr allgemein gehalten und zudem wird meist von Baumdiagrammähnlichen Situationen ausgegangen, komischerweise habe ich noch nichts in der Richtung meines Arrays gefunden.

Lässt sich das nicht so leicht lösen / gibt es nicht so etwas wie einen "Standardalgorithmus" dafür (ich denke Funktionen in der Art kann man für viele Zwecke brauchen), oder müsste ich das auf die einfachere Variante, die aber einen wahrscheinlich längeren Weg berechnet, lösen, indem ich vom Startpunkt immer zum nächsten Wegpunkt und dann zu dessen nächsten Wegpunkt gehe, bis ich alle abgelaufen habe?

Gruß,
MitgliedXYZ

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

2

25.03.2013, 17:45

Da würde sich der A* Algorithmus gut machen. Auf dieser Seite ist seine Funktionsweise und eine Beispiel Implementierung zu finden: www.policyalmanac.org/games/aStarTutorial_de.html
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

3

25.03.2013, 17:50

Wenn ich das richtig verstehe, willst du alle Felder mit einer 1 nacheinander ablaufen in einer beliebigen Reihenfolge, so das du insgesamt die kleineste Summe der Weglaengen erreichst? Das ist eine Variante des Handelsreisenden und nur durch systematisches Probieren loesbar. Ein Weg zwischen zwei bestimmten Einsen kannst mit den ueblichen Verfahren berechnen, z.b. Dijkstra aber wenn es noch ein paar mehr Einsen werden, dann gibt es irgendwann zuviele Kombinationen fuer so einen Ansatz.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

4

25.03.2013, 18:03

Danke schon mal für die Antworten.

Es gibt höchstens 30 mal die 1. Wären dann wohl 30! Möglichkeiten, dass wäre wohl doch sehr rechnaufwändig.

Eine Funktion zum Berechnen des Weges zwischen zwei Punkten habe ich schon geschrieben, ich werde es dann wohl trotzdem so machen, dass ich von der einen 1 zur nächstgelegenen 1 gehe, bis ich alle Punkte durchlaufen habe. Ist zwar nicht das effektivste, aber ich glaube mit solchen Algorithmen wird es mir dann doch zu kompliziert...

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

5

25.03.2013, 18:27

Du schreibst, dass du im Internet immer Baumstrukturen siehst. Das sind im Prinzip keine Bäume sondern Graphen. Ein Baum ist ein Sonderfall eines Graphen. Jeder Punkt (Knoten) in dem Graphen ist eine Position. Die Striche zwischen den Knoten (Kante) sind die Verbindungen. Jetzt könntest du zum Beispiel aus deinem Array so einen Graphen erstellen, indem du jeden begehbaren Punkt als Knoten im Graphen darstellst und angrenzende begehbare Flächen verbindest du im Graphen durch Kanten. Dadurch erhälst du im Prinzip ein Gitternetz. Wenn du bei Google nach A* und Tilemap oder vergleichbarem suchst, solltest du dazu aber auch was finden.
Ansonsten gibt es noch die Möglichkeit eine Matrix zu nehmen und mit den Kosten zu füllen. Bei n Knoten im Graphen würde man eine n x n Matrix erstellen. Dafür könntest du dir mal diesen Algorithmus angucken. Bei 30 verschiedenen Punkten wird es vermutlich schwierig sein alle Möglichkeiten durch Bruteforce zu testen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

EternalPain

Frischling

Beiträge: 87

  • Private Nachricht senden

6

26.03.2013, 14:40

Hatte erst vor ein paar Tagen eine sehr simple Pathfind-Funktion für mein Labyrinth-Generator geschrieben...

Im Prinzip basiert er auf einem Floodfill-Algorithmus allerdings wird hier statt einer Farbe ein Wegwert gesetzt aufsteigend vom Startpunkt... ist das Ziel erreicht wird von dieser Position rückwärts eine Wegliste zusammengestellt bis man wieder am Start ankommt... funktioniert sehr gut wie ich finde...

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

7

26.03.2013, 14:58

Ein paar Ergänzungen zu TGGC's Post:

http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Dort findest du die genauere Beschreibung. Für 30 Städte willst du mit Sicherheit keine optimale Lösung mehr ausrechnen wollen, das würde zu lange dauern. Aber unter "Algorithmische Komplexität" sind Algorithmen verlinkt, mit denen du höchstens den doppelten oder 1,5 fachen Weg läufst und die lassen sich dann wieder sehr gut berechnen.

Als allererstes solltest du aber dein Problem in 2 Teile spalten: Einen Algorithmus finden (in der Literatur nachschlagen) um von A nach B zu kommen und als zweiten Teil dir eine Route überlegen, in welcher Reihenfolge du die Punkte besuchen willst.
Für Teil 1 gibt es schon sehr ordentliche (A* z.B.) Algorithmen, für Teil 2 eben keine optimalen, aber schon welche die verhältnismäßig einfach sind aber trotzdem vernünftige Ergebnisse liefern.
Lieber dumm fragen, als dumm bleiben!

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

8

26.03.2013, 15:24

Danke nochmal für die zahlreichen Antworten.

Mein Programm geht von einen "Stadt" nun immer zur nächsten. Ist zwar nicht das effektivste, aber dennoch für mich ausreichend. Was mehr ein Problem ist sind die Hindernisse, die im Weg stehen. Man kann diese zwar umgehen, aber hier denke ich verschwendet mein Programm unnötige wegstrecke. Werde also vor allem daran noch arbeiten, evtl. finde ich ja im Web noch was passendes.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

9

26.03.2013, 15:35

Einfach lesen was hier geschrieben wird. Dabei geht es ja im Prinzip um Wegsuche. Dazu wurden dir mehr als ein Algorithmus genannt. Ich liste sie dir noch mal auf;)
Dijkstra,
A*,
Floyd und Warshall,
Floodfill

Damit hast du ja schon mal 4 Algorithmen mit welchen du dein Problem angehen könntest;)
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

EternalPain

Frischling

Beiträge: 87

  • Private Nachricht senden

10

27.03.2013, 05:55

Das Thema ist mal gar nicht so Trivial...

Zur eigentlichen Wegfindung wurden ja bereits genug Vorschläge gemacht...

Zu dem oben geschilderten Problem hab ich mal versucht ein möglichst einfachen Weg zu finden...

Ich habe nach deiner Schilderung mal versucht etwas zu basteln...
Dabei müssen zuerst alle Wegpunkte 'ermittelt' werden... anschließend habe ich die Distanz ausgehen vom letzten Wegpunkt bzw Anfänglich der Spieler-Position berechnet und dann als nächstes den Wegpunkt genommen der am nächsten liegt usw, bis zum letzten ermittelten Wegpunkt
Daraus ergibt sich dann eine Wegpunktliste.... anschließend kann dann diese Liste wiederum an einen Wegfindungs-Algorithmus übergeben werden...

Beispiel:

(Link)


Hier hab ich eine Zufalls-Map nach deiner Schilderung oben erstellt mit verschiedenen Wegpunkten, und mir anschließend diese liste/knoten der mir den Weg der Wegpunkte (1) anzeigen sollte...

Das Ergebnis ist nicht immer optimal... aber dafür relativ einfach

Edit:
Hier wie es mit verschiedenen Wegpunkten aussehen könnte...

(Link)

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »EternalPain« (27.03.2013, 06:04)

Werbeanzeige

Ähnliche Themen