#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL maze(64) AS LONG
    LOCAL dist(64) AS LONG
    LOCAL prev(64) AS LONG
    LOCAL queue(64) AS LONG
    LOCAL q_head AS LONG
    LOCAL q_tail AS LONG
    LOCAL maze_w AS LONG
    LOCAL maze_h AS LONG
    LOCAL start_pos AS LONG
    LOCAL end_pos AS LONG
    LOCAL cur_pos AS LONG
    LOCAL nx AS LONG
    LOCAL ny AS LONG
    LOCAL i AS LONG
    LOCAL neighbor AS LONG
    LOCAL path_len AS LONG
    LOCAL path_arr(64) AS LONG
    LOCAL temp_str AS STRING

    maze_w = 8
    maze_h = 8
    start_pos = 0
    end_pos = 7 * maze_w + 7

    i = 0
    WHILE i < 64
        maze(i) = 0
        dist(i) = -1
        prev(i) = -1
        queue(i) = 0
        i = i + 1
    WEND

    maze(1 * maze_w + 1) = 1
    maze(1 * maze_w + 2) = 1
    maze(1 * maze_w + 3) = 1
    maze(2 * maze_w + 3) = 1
    maze(3 * maze_w + 1) = 1
    maze(3 * maze_w + 3) = 1
    maze(3 * maze_w + 5) = 1
    maze(4 * maze_w + 5) = 1
    maze(5 * maze_w + 1) = 1
    maze(5 * maze_w + 2) = 1
    maze(5 * maze_w + 5) = 1
    maze(6 * maze_w + 3) = 1
    maze(6 * maze_w + 5) = 1

    dist(start_pos) = 0
    q_head = 0
    q_tail = 0
    queue(q_tail) = start_pos
    q_tail = q_tail + 1

    WHILE q_head < q_tail
        cur_pos = queue(q_head)
        q_head = q_head + 1

        IF cur_pos = end_pos THEN
            q_head = q_tail
        ELSE
            i = 0
            WHILE i < 4
                IF i = 0 THEN
                    nx = (cur_pos MOD maze_w) + 1
                    ny = cur_pos / maze_w
                ELSEIF i = 1 THEN
                    nx = (cur_pos MOD maze_w) - 1
                    ny = cur_pos / maze_w
                ELSEIF i = 2 THEN
                    nx = cur_pos MOD maze_w
                    ny = cur_pos / maze_w + 1
                ELSE
                    nx = cur_pos MOD maze_w
                    ny = cur_pos / maze_w - 1
                END IF

                IF nx >= 0 AND nx < maze_w AND ny >= 0 AND ny < maze_h THEN
                    neighbor = ny * maze_w + nx
                    IF maze(neighbor) = 0 AND dist(neighbor) = -1 THEN
                        dist(neighbor) = dist(cur_pos) + 1
                        prev(neighbor) = cur_pos
                        queue(q_tail) = neighbor
                        q_tail = q_tail + 1
                    END IF
                END IF
                i = i + 1
            WEND
        END IF
    WEND

    path_len = 0
    IF dist(end_pos) >= 0 THEN
        cur_pos = end_pos
        WHILE cur_pos >= 0
            path_arr(path_len) = cur_pos
            path_len = path_len + 1
            cur_pos = prev(cur_pos)
        WEND
    END IF

    PRINT "BFS Shortest Path (8x8 grid)"
    PRINT "==========================="
    PRINT ""

    ny = 0
    WHILE ny < maze_h
        temp_str = ""
        nx = 0
        WHILE nx < maze_w
            cur_pos = ny * maze_w + nx
            IF cur_pos = start_pos THEN
                temp_str = temp_str + "S"
            ELSEIF cur_pos = end_pos THEN
                temp_str = temp_str + "E"
            ELSEIF maze(cur_pos) = 1 THEN
                temp_str = temp_str + "#"
            ELSE
                i = 0
                WHILE i < path_len
                    IF path_arr(i) = cur_pos THEN
                        temp_str = temp_str + "."
                    END IF
                    i = i + 1
                WEND
                IF LEN(temp_str) <= nx THEN
                    temp_str = temp_str + " "
                END IF
            END IF
            nx = nx + 1
        WEND
        PRINT temp_str
        ny = ny + 1
    WEND

    temp_str = STR$(path_len - 1)
    PRINT ""
    PRINT "Shortest path: " + temp_str + " steps"
    IF path_len > 0 THEN
        temp_str = ""
        i = path_len - 1
        WHILE i >= 0
            temp_str = temp_str + "(" + STR$(path_arr(i) MOD maze_w) + "," + STR$(path_arr(i) / maze_w) + ")"
            IF i > 0 THEN
                temp_str = temp_str + " -> "
            END IF
            i = i - 1
        WEND
        PRINT "Path: " + temp_str
    END IF

    PRINT ""
    PRINT "BFS pathfinding complete."

    FUNCTION = 0
END FUNCTION
