Shortest path

Nu ved jeg ikke helt hvad du vil bruge det til.... Men hvis det til f.eks. er til kort vil jeg tro du kan bruge en simpel andengradsligning. Jeg skal nok have lidt mere info for at kunne give brugbar input...

Jeg har et kort, med en masse kendte punkter (x,y).

Så vil jeg gerne fra A(x,y)-Z(x,y), men der vil være mange muligheder.

Jeg tror det er et skoleproblem, på et kort med punkter forbundet af veje skal der findes den korteste vej fra eet punkt til et andet. du kan ikke blot gå direkte fra startpunkt til slutpunkt.

Hvis det er det er der en ganke god algoritme til det. den er dog desværre ikke super hurtig.

1) gem punkterne i en datastruktur hvor det for hvert punk kan ses hvilke andre punkter der er en vej fra det punkt hen til. derudover er der for hvert punkt en tal-variabel (lad os kalde den vægt)

2) sæt vægt-variabelen til 9999999 i all punkter.

3) lav en rekursiv funktion der starter i det punkt du skal starte i og sætter vægten til 0 der. så går ud ad alle veje der fører fra det punkt, for hvert punkt den kommer tii kikker den på det punkts vægt.
  Hvis vægten er større end ('mit startpunkt vægt'+1) sætter den vægten til ('mit startpunkt vægt'+1). og rekursionen fortsætter fra det punkt.
  Hvis vægten er mindre end ('mit startpunkt vægt'+1) gør den ingentig, og fortætter heller ikke rekursionen.

4) når funktionen har kørt færdig tager du så slutpunktet og kikker på vægten der. og finder så (igen rekursivt) et af dens nabopunkter der har en vægt der er een mindre (der kan være flere, men det gør ikke noget, bare vælg det første du ser). På den måde finder nr 2 funktion den korteste vej fra det ene punkt til det andet.

mvh JakobA
     

2)

En implementation, der ikke er ret effiktiv, men dog virker:
http://home20.inet.tele.dk/midgaard/snip/pacman.html

Kik efter FindPath

har selv fundet divesre Ai artikler til spil programmering.