spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Mit dem hier kannst du den kürzesten Weg bestimmen.
Ist auf jeden Fall einen Blick wert.

Zitat von »Mirac«

Es muss jedes (freie) Feld genau einmal besucht werden

Geht das wirklich mit A*?

Ne, aber es ist ja ein Ansatz, überhaupt einen Weg zu finden

Na, wenn's mit A* sein soll, könntest du ja einfach jedem Tile ein bool geben, ob es bereits besucht wurde / ob es bereits als Teil eines Weges benutzt wurde. Wenn ja behandelst du es genau wie jedes nicht begehbare Tile. Dann lässt du noch eine Schleife laufen, bis der A* irgendwann klemmt, weil er nicht zum Ziel kommt und schon hast du eine Liste aller möglichen Wege. Und diese auch noch automatisch nach deren Kürze geordnet.
Könnte aber natürlich sein, dass du somit nicht alle Tiles besuchst, das weiß ich jetzt nicht. Ausprobieren.

Spontan würde ich einfach alle Möglichkeiten durchprobieren. Du beginnst beim Startknoten und erstellst für jede abgehende Kante, eine Knotenliste. Für Jeden weiteren Knoten betrachtest du wieder die abgehenden Kanten und erstellt für jede weitere Kante wieder eine Knotenliste, in denen alle Vorgänger des aktuellen Knotens enthalten sind. Das machst du natürlich nur, wenn in der entsprechenden Knotenliste der Zielknoten der Kante noch nicht enthalten ist, ansonsten wird die Kante ignoriert.

Am Ende hast du eine Liste von Pfaden durch den Graphen. Jetzt musst du nur noch die Pfade heraussuchen, deren Knotenanzahl gleich der Anzahl der Knoten im Graphen ist und die als letzten Knoten den Endpunkt enthalten.

Ist vielleicht nicht der beste Algo, sollte aber zum Ziel führen.

Du könntest einen Baum aufbauen in dem alle möglichen Felder von einem Feld aus jeweils neue Zweige bilden. Am Ende kannst du dann alle Wege rausfiltern die alle Felder besucht haben. Keine Ahnung ob das effektiv funktioniert.