Main sections
FINDPATH()
gefunden% = FINDPATH ( karte#[], loesung#[], heuristik#, startx%, starty%, endex%, endey%)
Sucht im Feld karte#[] nach einem Pfad von startx#, starty# nach endex#, endey#. Dabei wird ein A* Algorithmus verwendet, der Wegkosten berücksichtigen kann. D.h. umso höher ein Wert in dem Feld karte[] ist, desto höher sind die Kosten für dieses Wegstück. Ein Wert von kleiner gleich 0 ist unpassierbar.
Mit dem Heuristikregler kann man festlegen, ob die kürzeste Route (=0.0) oder die Kostengünstigste Route (=1.0) gefunden werden soll. Zwischenwerte beschleunigen die Rechenzeit und verringern aber auch die Qualität der Lösung.
Der Rückgabewert ist die Länge des Pfads.
Wenn ein Pfad gefunden wurde, so enthält loesung#[] ein 2-dimensionales Feld, das im ersten index die Nummer des Schritts angibt und im 2. Index die x (=Wert 0) und y(=Wert 1) position des Schritts angibt.
Das Beispiel verdeutlicht die Anwendung:
// --------------------------------- //
// Project: PathFinder
// Start: Tuesday, September 23, 2003
// IDE Version: 1.30923
// Diesen Wert ändern für mehr/weniger Gelände
MAXX = 500
MAXY = MAXX/2
scalex = 640 / MAXX
scaley = 320 / MAXY
DIM map[MAXX][MAXY]
DIM solution[0]
// Irgend eine Karte machen
FOR x=0 TO MAXX-1; FOR y=0 TO MAXY-1; map[x][y]=100; NEXT; NEXT
FOR i=0 TO MAXX*MAXY*4; map[RND(MAXX-1)][RND(MAXY-1)] = RND(25); NEXT
FOR i=0 TO MAXY*.5; map[i+1][i] = 0; map[i+MAXY/2][MAXY-i-1]=0; NEXT
// Go Pfadfinder, go!
gut = FINDPATH(map[], solution[], .3, 0,0, MAXX-1, MAXY-1)
// Karte zeichnen
FOR x=0 TO MAXX-1; FOR y=0 TO MAXY-1; DRAWRECT x*scalex, y*scaley, scalex, scaley, RGB(255*(1-map[x][y]), 255*map[x][y], 0); NEXT; NEXT
IF gut
PRINT "Loesung gefunden!", 0, 400
x=0; y=0
FOR i=0 TO BOUNDS(solution[], 0)-1
xl = x
yl = y
x = solution[i][0]
y = solution[i][1]
DRAWLINE xl*scalex+scalex/2, yl*scaley+scaley/2, x*scalex+scalex/2, y*scaley+scalex/2, RGB(0, 0, 255)
NEXT
ELSE
PRINT "Keine Loesung gefunden!?", 0, 400
ENDIF
SHOWSCREEN
MOUSEWAIT
END