Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Weg von A nach B finden


MariaMaria - Sa 25.06.05 17:30
Titel: Weg von A nach B finden
Hallo Leute!
Wie kann ich für ein Spiel für meine Spielfigur möglichst schnell und effektiv den Weg vom aktuellen Punkt zu einem Zielpunkt berechnen?

Das Spielfeld besteht aus einzelnen Rechtecken, die entweder passierbar sind oder nicht. Die Spielfigur kann sich auf dem Spielfeld jeweils ein Kästchen in eine beliebige Richtung bewegen.

Das ganze könnte etwa so aussehen:


Delphi-Quelltext 
1:
2:
3:
 
var Spielfeld : array[0..100,0..100] of boolean; // false bedeutet das feld ist passierbar, true bedeutet Hindernis
    Figur : TPoint; // Die aktuelle Position der Figur auf dem Spielfeld
    Ziel : TPoint;  // Die Stelle wo meine Figur hinmuss


Moderiert von user profile iconChristian S.: Delphi-Tags hinzugefügt.


Gausi - Sa 25.06.05 17:40
Hallo und :welcome:

Eine Möglichkeit, einen Weg durch dieses 0-1-Array zu finden ist folgender:

1. Starte bei A und markiere es als 'begangen'.

2. Suche von dort ein Nachbarfeld, was noch nicht 'begangen' ist, aber passierbar ist.

3. Gibt es ein solches Feld, dann gehe dorthin und markiere es ebenfalls als 'begangen'.

4. Wenn du zu einem Feld kommst, von wo aus es nur zurückgeht (= Sackgasse) dann gehe zurück, und markiere das gerade verlassene Feld als 'Sackgasse'.

5. Wiederhole ab Punkt 2, bis man am Zielfeld ist.


MariaMaria - Sa 25.06.05 19:48
Leider "rast" die Spielfigur so nur eine ewigkeit auf dem Spielfeld herum, bis sie schließlich nach langem Probieren den Weg findet.
Ich dachte eigentlich an eine Möglichkeit, den Weg bereits im Voraus zu berechnen, und zwar einen möglichst kurzen Weg sofort zum Ziel!?


I.MacLeod - Sa 25.06.05 21:43
Da gibt es viele wundervolle Algorithmen für :mrgreen:

http://www.policyalmanac.org/games/aStarTutorial.htm

ach, hier gibts sogar direkt einen haufen Links:

http://www.gameai.com/pathfinding.html


BenBE - So 26.06.05 00:52
Für eine Implementierung (für eine nicht notwendigerweise Regelmäigen Wegeverlauf kannst Du Dir http://cvs.sourceforge.net/viewcvs.py/omorphia/omorphia/library/source/OAIBacktracing.pas angucken. Die Wegebeschreibungen werden dort über Call-Back-Events realisiert. Für Regelmäßige Verlinkung reicht das Normal-Plane aus, was die Unit automatisch verwaltet.
ACHTUNG: Nutzung ATM nicht ganz trivial...


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!