FINDPATH problem

Previous topic - Next topic

doimus

I'm not sure whether this is a bug, feature, or (most likely) I'm doing something wrong, but I have a problem with FINDPATH routine.

I'm trying to get a "character" to move across map towards target via the shortest possible route.
No matter what I do, I always get movement that is totally perpendicular.
For example, if I have a clear map without obstacles and with same movement cost for all fields, "character" will move first horizontally along x-axis and then descend down on y-axis towards the target in a perfect, L-shaped path (that's obviously not the shortest).
If I add some random blocks and terrain costs to the map, it still follows this same angular path, but it's kind of masked by the pathfinding heuristics.

Here's the code:
Code (glbasic) Select

// change these variables for different map layouts

LOCAL mapIsFlat = TRUE // true = all fields on map have same passage value
LOCAL heuristics = 0.0          // 0 = shortest route , 1 = cheapest route
LOCAL mapBlockValue = 0 // percentage of blocked map fields, 0 = clear map



GLOBAL walkpath[]
GLOBAL map[]


makeMap(300, 300, mapBlockValue, mapIsFlat)

calculatePath(heuristics)

WHILE TRUE

walk()

SLEEP 20
SHOWSCREEN

WEND


FUNCTION walk:

        // draw map
DRAWSPRITE 0,0,0

STATIC currentStep
LOCAL maxStep

STATIC currentx
STATIC currenty

PRINT "step: " + currentStep + "  x: " + currentx + "  y: " + currenty ,0,0

maxStep = BOUNDS(walkpath[], 0) - 1

currentx = walkpath[currentStep][0]
currenty = walkpath[currentStep][1]

// draw path
FOR i = 0 TO maxStep - 1
SETPIXEL walkpath[i][0], walkpath[i][1], RGB(0,0,90)
NEXT

// draw character
SETPIXEL currentx, currenty, RGB(0,255,0)

//draw target
SETPIXEL walkpath[-1][0], walkpath[-1][1], RGB(255,0,0)

INC currentStep, 1
IF currentStep = maxStep THEN currentStep = 0


ENDFUNCTION



FUNCTION calculatePath: heuristics


LOCAL startx, starty, targetx, targety

startx = 10
starty = 10
targetx = BOUNDS(map[], 0) - 20
targety = BOUNDS(map[], 1) - 20

LOCAL ok = FINDPATH(map[], walkpath[], heuristics, startx, starty, targetx, targety)

IF ok = FALSE

PRINT "Path NOT found!", 10,10
SHOWSCREEN
KEYWAIT
END

ENDIF


ENDFUNCTION


FUNCTION makeMap: x, y, blocked, mapIsFlat


DIM map[x][y]

FOR i = 0 TO x - 1
FOR j = 0 TO y -1

LOCAL r = RND(100) + 1

IF mapIsFlat = TRUE
IF r > blocked THEN map[i][j] = 1
ELSE
IF r > blocked THEN map[i][j] = RND(10) + 1
ENDIF
NEXT
NEXT


FOR i = 0 TO x - 1
FOR j = 0 TO y - 1
IF map[i][j] > 0.1
LOCAL col = 32 + (map[i][j])
SETPIXEL i, j, RGB(col,col,col)
ENDIF
NEXT
NEXT

GRABSPRITE 0, 0,0, x,y

ENDFUNCTION


MrTAToad

#1
Have you tried the example routine for FINDPATH ?

Kitty Hello

blocked should be 0, no?

monono

Last time I used it, GLB-pathfinding wasn´t capable of diagonal movement. That way the L-shape is the shortest path. And many others, if the array has no obstacles.

Minion

Yes, according to the helpfile, only 4 directioons are considered. Would be nice to be able to use 8 directions (or more) maybe a flag to set that ?

monono

There is already a solution in the forum somewhere! It wasn´t as fast as Gernots, but usable.

doimus

Quote from: monono on 2011-Sep-23
Last time I used it, GLB-pathfinding wasn´t capable of diagonal movement. That way the L-shape is the shortest path. And many others, if the array has no obstacles.

That's the problem!
Basically, all "angular" paths are correct (mathematically) but design-wise, only one is correct.



Here it is:
Image A is what I want and FINDPATH doesn't do (diagonal movement).
Image B is what I get and image C is what I would like to have ideally. Notice how the field count is the same for both methods (and for all paths in between, really).

Problem is, although option B is the most logical and rational path for the machine, it's totally unsuitable for any useful purpose.


Kitty Hello

add some tiny noise to the "free" cells, maybe?

Wampus

Quote from: monono on 2011-Sep-23
There is already a solution in the forum somewhere! It wasn´t as fast as Gernots, but usable.

I'm aware of two solutions that use diagonals that have been posted on the forum. I included both in a little comparison proggy. Click here to go to the thread. They are a lot slower than Gernot's inbuilt solution.




Quote from: doimus on 2011-Sep-23
That's the problem!
Basically, all "angular" paths are correct (mathematically) but design-wise, only one is correct.



Here it is:
Image A is what I want and FINDPATH doesn't do (diagonal movement).
Image B is what I get and image C is what I would like to have ideally. Notice how the field count is the same for both methods (and for all paths in between, really).

Problem is, although option B is the most logical and rational path for the machine, it's totally unsuitable for any useful purpose.

The part of the pathfinding routine that is responsible for making the next educated guess about the shortest path, the manhattan heuristic, is what is responsible for that creating that L shape path. To change it to the diagonal shown in the third diagram C the heuristic would need to modified to create a more natural looking pattern.

If Gernot's suggestion about adding some noise to the free cells doesn't work in the way that you want it to, you might want to write or modify your own pathfinding routine after studying a bit about how they work. Its fun. :)

kanonet

Quote from: Wampus on 2011-Sep-23They are a lot slower than Gernot's inbuilt solution.
Not true, you should try it again! Since Gernot improved the speed of arrays, our codes arent much slower than FINDPATH(). Btw. i corrected one error in my code, so maybe you could use the version that is in this post for your comparison.
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64

Wampus

Quote from: kanonet on 2011-Sep-23
Quote from: Wampus on 2011-Sep-23They are a lot slower than Gernot's inbuilt solution.
Not true, you should try it again! Since Gernot improved the speed of arrays, our codes arent much slower than FINDPATH(). Btw. i corrected one error in my code, so maybe you could use the version that is in this post for your comparison.

You're right. Holy cow! The array optimisation makes a heck of difference. On my PC at least I'm seeing array heavy routines like pathfinding and ray casting running up to 350% as fast as previously compiled apps.

I missed all this stuff from being away so long.  ;/