Grid Pathfinding (Hero to Position)
#1
About the simplest example of a grid-pathfinding system that I could imagine one could ever use to move a hero from Point A to Point B.  This would be used for 4-directional movement games such as Zelda/Dragon Warrior/Final Fantasy type 2D games.

Code:
SCREEN _NEWIMAGE(640, 480, 32)

CONST SquareSize = 15
HeroX = 5: HeroY = 1 'use these to move our hero's position
TargetX = 9: TargetY = 14 'our target position

x = SquareSize
y = SquareSize
DIM Grid(x + 1, y + 1)
DIM Path(x + 1, y + 1) AS STRING

W = _WIDTH / x: H = _HEIGHT / y

FOR i = 0 TO (SquareSize) / 2
    LINE (W * i, 0)-((_WIDTH - W * i), _HEIGHT - 1), -1, B
    LINE (0, H * i)-(_WIDTH - 1, _HEIGHT - H * i), -1, B
NEXT

_PRINTSTRING (HeroX * W - (W - _FONTWIDTH) * .75, (HeroY - 1) * H + (H - _FONTHEIGHT) * .5), CHR$(1)
_PRINTSTRING (TargetX * W - (W - _FONTWIDTH) * .75, (TargetY - 1) * H + (H - _FONTHEIGHT) * .5), "T"

finished = 0
FOR i = 1 TO x 'Initialize our grid as being blank
    FOR j = 1 TO x
        Grid(i, j) = -1
    NEXT
NEXT

Grid(HeroX, HeroY) = 0
Path(HeroX, HeroY) = ""
counter = -1
DO
    counter = counter + 1
    FOR i = 1 TO x
        FOR j = 1 TO y
            IF Grid(i, j) = counter THEN 'Let's see where we can go from our last steps
                IF i > 1 AND Grid(i - 1, j) = -1 THEN Grid(i - 1, j) = counter + 1: Path(i - 1, j) = Path(i, j) + "L"
                IF i < SquareSize AND Grid(i + 1, j) = -1 THEN Grid(i + 1, j) = counter + 1: Path(i + 1, j) = Path(i, j) + "R"
                IF j > 1 AND Grid(i, j - 1) = -1 THEN Grid(i, j - 1) = counter + 1: Path(i, j - 1) = Path(i, j) + "U"
                IF j < SquareSize AND Grid(i, j + 1) = -1 THEN Grid(i, j + 1) = counter + 1: Path(i, j + 1) = Path(i, j) + "D"
            END IF
        NEXT
    NEXT
    FOR i = 1 TO x
        FOR j = 1 TO y
            IF Grid(i, j) <> -1 THEN _PRINTSTRING (i * W - (W - _FONTWIDTH) * .75, (j - 1) * H + (H - _FONTHEIGHT) * .5), STR$(Grid(i, j))
    NEXT j, i
    SLEEP
    IF Grid(TargetX, TargetY) <> -1 THEN finished = -1
LOOP UNTIL finished

LOCATE 1, 1: PRINT "PATH IS:"; Path(TargetX, TargetY)

SLEEP
FOR j = 0 TO LEN(Path$(TargetX, TargetY))
    _LIMIT 1
    CLS
    FOR i = 0 TO (SquareSize) / 2
        LINE (W * i, 0)-((_WIDTH - W * i), _HEIGHT - 1), -1, B
        LINE (0, H * i)-(_WIDTH - 1, _HEIGHT - H * i), -1, B
    NEXT
    D$ = MID$(Path$(TargetX, TargetY), j, 1)
    SELECT CASE D$
        CASE "L": HeroX = HeroX - 1
        CASE "R": HeroX = HeroX + 1
        CASE "U": HeroY = HeroY - 1
        CASE "D": HeroY = HeroY + 1
    END SELECT
    _PRINTSTRING (HeroX * W - (W - _FONTWIDTH) * .75, (HeroY - 1) * H + (H - _FONTHEIGHT) * .5), CHR$(1)
    _PRINTSTRING (TargetX * W - (W - _FONTWIDTH) * .75, (TargetY - 1) * H + (H - _FONTHEIGHT) * .5), CHR$(1)
NEXT
Reply