Algorithmus Problem

ViperNeo

Hi Leute!

Ich soll ein Spiel programmieren, PacMan und hab alles soweit fertig. Jetzt ist die KI dran und die Vorgabe ist es, diese nach einem Backtracking prinzip laufen zu lassen. Jetzt ist mein Problem, ich hab keine AHnung was das genau ist, wie es funktioniert und wie ich das umsetze.

Habt ihr evtl. Hilfestellungen, vorhandene Lösungen zum studieren oder diverse Links?

Wäre sehr hilfreich, danke euch!

Liebe grüße

http://www.faust.fr.bw.schule.de/mhb/backtrack/backtr.htm. Von da gehts auch weiter...

ViperNeo

Hm... DAnke schonmal, aber irgendwie hilft mir das nicht gerade weiter. Vorallem dauert der Algorithmus bei den KArten viel zu lange.

CStoll

Da mußt du das Backtracking halt etwas früher abbrechen - wenn jedes der Monsterchen jeden möglichen Weg bis zum Spielende durchrechnen will, dauert das eine Weile.

Okay, aber wie mache ich einen solchen Backtracking Algorithmus? Steh da immer noch aufem Schlauch....

CStoll

im Prinzip so:

Backtrack(Daten)
  if Abbruch return
  for each x in mögliche Folgewege
    gehe Schritt x
    Backtrack(neue Daten)
    mache Schritt x rückgängig
  end for
end sub

BorisDieKlinge

der backtracking algorithums arbeitet nach dem Versuchs-Irrtum prinzip...es wird versucht bspw. den weg von start bis ziel zu suchen, in dem der algortihmus versucht jeden möglicehn weg zu gehen... kommt er in einer sackgase geht er wieder ein schritt zurück .. kommt er an eine verzweigung.. wir jeder richtugn an der verzweigung nacheinder druchgelaufen bist zu sackgasse und wieder zurückgeangen zu kreuzung, und der nächte weg druchlaufen das wird in der regel mit einem rekusiver algorithmus realisiert!!

CStoll hat das ganze was ich hier ausgeschrieben hat in code beschrieben!