## Main sections

## FINDPATH()

### found% = FINDPATH ( map#[], solution#[], heuristic#, startx%, starty%, endx%, endy%)

FINDPATH searches the array map#[] for a path from startx%, starty% to endx%, endy%. An A* algorithm is used that can take costs of using various paths into consideration. A higher value in a given map location will cost more and should be avoided. A value of 0 and smaller is considered unpassable. FINDPATH searches the map in 4 directions only, it does not calculate diagonal paths.

With the heuristic slider you can specify whether the shortest route (=0.0) or the route with the lowest costs (=1.0) is to be calculated. You can use values in between 0 and 1 to have a trade-off between the two.

Imagine trying to get from one side of a high mountain to the other. The shortest path is straight over the top but will take you a lot of effort (i.e. the "cost"), the lowest cost one is to take the nice flat ground around the mountain, longer in terms of distance travelled, but easier.

The return value from FINDPATH() is the length of the found path.

If a path was found, the array solution#[] contains a 2 dimensional array. The first index indicates the number of the step. The second has an x (=index 0) and an y (=index 1) value of the step's position.

This sample shows how to use it.

// --------------------------------- //

// Project:

// Start: Tuesday, September 23, 2003

// IDE Version: 1.30923

// Change this value for more/less terrain

MAXX = 500

MAXY = MAXX/2

scalex = 640 / MAXX

scaley = 320 / MAXY

DIM map[MAXX][MAXY]

DIM solution[0]

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

good = FINDPATH(map[], solution[], .3, 0,0, MAXX-1, MAXY-1)

// Draw the map

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 good

PRINT "Found a solution!", 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 "No solution found!?", 0, 400

ENDIF

SHOWSCREEN

MOUSEWAIT

END