GLBasic User Manual

Main sections


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


scalex = 640 / MAXX
scaley = 320 / 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)
PRINT "No solution found!?", 0, 400


See also...