Grid Pathfinding (Mobs to Hero)
#1
This is about the simplest example of how we'd calculate and figure out how to move several creatures from their starting position to the Hero, using a 2D Grid type map system.

Code:
SCREEN _NEWIMAGE(640, 480, 32)

CONST SquareSize = 15
HeroX = 5: HeroY = 1 'use these to move our hero's position
Mob1X = 14: Mob1Y = 4 'mob1
Mob2X = 1: Mob2Y = 15 'mob2
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 = 0 TO X 'Initialize our grid as being blank
    FOR j = 0 TO X
        Grid(i, j) = -1
    NEXT
NEXT

Grid(HeroX, HeroY) = 0
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
                IF i < SquareSize AND Grid(i + 1, j) = -1 THEN Grid(i + 1, j) = counter + 1
                IF j > 1 AND Grid(i, j - 1) = -1 THEN Grid(i, j - 1) = counter + 1
                IF j < SquareSize AND Grid(i, j + 1) = -1 THEN Grid(i, j + 1) = counter + 1
            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
    finished = -1
    FOR i = 1 TO X
        FOR j = 1 TO X
            IF Grid(i, j) = -1 THEN finished = 0
    NEXT j, i
LOOP UNTIL finished
SLEEP


IF Grid(Mob1X, Mob1Y) > Grid(Mob2X, Mob2Y) THEN maxmoves = Grid(Mob1X, Mob1Y) ELSE maxmoves = Grid(Mob2X, Mob2Y)
FOR j = 0 TO maxmoves
    _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
    IF Grid(Mob1X - 1, Mob1Y) < Grid(Mob1X, Mob1Y) AND Mob1X > 1 THEN
        Mob1X = Mob1X - 1
    ELSEIF Grid(Mob1X + 1, Mob1Y) < Grid(Mob1X, Mob1Y) AND Mob1X < SquareSize THEN
        Mob1X = Mob1X + 1
    ELSEIF Grid(Mob1X, Mob1Y - 1) < Grid(Mob1X, Mob1Y) AND Mob1Y > 1 THEN
        Mob1Y = Mob1Y - 1
    ELSEIF Grid(Mob1X, Mob1Y + 1) < Grid(Mob1X, Mob1Y) AND Mob1Y < SquareSize THEN
        Mob1Y = Mob1Y + 1
    END IF

    IF Grid(Mob2X - 1, Mob2Y) < Grid(Mob2X, Mob2Y) AND Mob2X > 1 THEN
        Mob2X = Mob2X - 1
    ELSEIF Grid(Mob2X + 1, Mob2Y) < Grid(Mob2X, Mob2Y) AND Mob2X < SquareSize THEN
        Mob2X = Mob2X + 1
    ELSEIF Grid(Mob2X, Mob2Y - 1) < Grid(Mob2X, Mob2Y) AND Mob2Y > 1 THEN
        Mob2Y = Mob2Y - 1
    ELSEIF Grid(Mob2X, Mob2Y + 1) < Grid(Mob2X, Mob2Y) AND Mob2Y < SquareSize THEN
        Mob2Y = Mob2Y + 1
    END IF

    _PRINTSTRING (HeroX * W - (W - _FONTWIDTH) * .75, (HeroY - 1) * H + (H - _FONTHEIGHT) * .5), CHR$(1)
    _PRINTSTRING (Mob1X * W - (W - _FONTWIDTH) * .75, (Mob1Y - 1) * H + (H - _FONTHEIGHT) * .5), "1"
    _PRINTSTRING (Mob2X * W - (W - _FONTWIDTH) * .75, (Mob2Y - 1) * H + (H - _FONTHEIGHT) * .5), "2"
NEXT


Notice, this simply choose movement based on a prefered case movement (vertical over horizontal).  If we wanted something a little more realistic, we'd probably be better off if we calculated distance and then closed whevever is greater:  Horizontal or Vertical distance.  (Or a modification to make this an 8-directional checker would make things seem a lot more natural as well.)

Note:  This is just the very most basic routines possible, and can be expanded in many different ways.  It's just nice to have somewhere to start,  without getting too complicated for new programmers.  Wink
Reply