Weg von A nach B finden

MariaMaria · Beiträge: 16

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:

markieren

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 Christian S.: Delphi-Tags hinzugefügt.

Gausi · Verfasst: Sa 25.06.05 17:40

Hallo und

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.

_________________
We are, we were and will not be.

MariaMaria · Beiträge: 16

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 · Beiträge: 109

Da gibt es viele wundervolle Algorithmen für :mrgreen:

www.policyalmanac.or...es/aStarTutorial.htm

ach, hier gibts sogar direkt einen haufen Links:

www.gameai.com/pathfinding.html

_________________
{$APPTYPE CONSOLE}uses SysUtils;const a='{$APPTYPE CONSOLE}uses SysUtils;const a=%s;begin write(Format(a,[#39+a+#39]))end.';begin write(Format(a,[#39+a+#39]))end.

BenBE · Verfasst: So 26.06.05 00:52

Für eine Implementierung (für eine nicht notwendigerweise Regelmäigen Wegeverlauf kannst Du Dir cvs.sourceforge.net/...e/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...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme