Roku Developer Program

[Komag]

So I'm wondering if anyone has programmed any sort of AI pathfinding with BrightScript?

In reading up on it online, looks like there are quite a few ways I can approach it.

If there isn't any direct BrightScript pathfinding code "lying around", then...

What seems to be the closest language to BrightScript that I might translate some pathfinding code that I find online. Lua? Java?

[EnTerr]

You mean this https://en.wikipedia.org/wiki/Pathfinding ?
I never thought of it as AI (but then again when we accomplish something we say "it's not what AI is about").

You can write Dijkstra's straight up, why port. If you must, i say Lua or Javascript.
If you need A*, i remember some Udacity class had good intro/explanation, i can try looking for that.

[dev42]

Not the "where's the beef?!" you're asking for, but ...

There is a Coursera class on Algorithms taught by Prof. Sedgewick in Java. Coursera's start/end class format doesn't help you here, but there is a "booksite."

Unfortunately, my memory is fuzzy and I believe A* was "taught" as an assignment. So, no lecture IFAICT.

But, here's a reference to it, jump to "Combinatorial search":
http://algs4.cs.princeton.edu/25applications/

From there you'd probably want to implement a Priority Queue.

Other than that, here's something on Graphs/Shortest Paths:
http://algs4.cs.princeton.edu/44sp/

peace & 42

[Komag]

Yeah, I was looking at Dijkstra and A*, all new to me, very deep possibilities, but I'll have to experiment and see how different methods affect performance, how often I'm going to recalculate the pathfinding, etc.

I'll have to look into those links, dev42, thanks.

[EnTerr]

What you are trying to do might be simpler than all those methods. Say if you were trying to find shortest path from A to B in a square maze, a simplified (since all distances to a neighboring cells is of length 1) version of Dijkstra will do, essentially a queue-based flood-fill

[EnTerr]

Ok, so i wrote something down to demonstrate.

First, some utility functions:

function sample_maze():
    return [
        "+-------------+",
        "|.O........O..|",
        "|.O.O.O.O.OOO.|",
        "|...O...O.....|",
        "+-------------+"
    ]
end function

function parse_maze(arrStr): 'array of rows. convert each row from string to array of ints
    res = [ ]
    for each lnStr in arrStr:
        lnArr = [ ]
        for i = 1 to len(lnStr):
            lnArr.push( sgn(instr(1, " .", mid(lnStr, i, 1))) -1 )  'obstacle is -1
        end for
        res.push(lnArr)
    end for
    return res
end function

sub print_maze(maze):
    for each line in maze:
        for each cell in line:
            print right("   " + str(cell), 3);
        end for
        print
    end for
end sub

Let's see how a maze looks (walls are -1, empty is 0):

BrightScript Debugger> maze = parse_maze(sample_maze())
BrightScript Debugger> print_maze(maze)
 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
 -1  0 -1  0  0  0  0  0  0  0  0 -1  0  0 -1
 -1  0 -1  0 -1  0 -1  0 -1  0 -1 -1 -1  0 -1
 -1  0  0  0 -1  0  0  0 -1  0  0  0  0  0 -1
 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Let's mark-up a maze for a particular target:

sub target_maze(maze, x, y):
    if maze[y][x] <> 0 then return

    neighbours = [ [-1, 0], [0, -1], [+1, 0], [0, +1] ] 'left, up, right, down
    queue = createObject("roList")
    maze[y][x] = 1
    queue.addTail([x, y])
    while not queue.isEmpty():
        xy = queue.RemoveHead()
        x0 = xy[0]: y0 = xy[1]: dist = maze[y0][x0]
        for each nbr in neighbours:
            x = x0 + nbr[0]: y = y0 + nbr[1]
            if maze[y][x] = 0:
                maze[y][x] = dist + 1
                queue.addTail([x, y])
            end if
        end for
    end while
end sub

BrightScript Debugger> target_maze(maze, 1, 1)
BrightScript Debugger> print_maze(maze)
 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
 -1  1 -1  7  8  9 10 11 12 13 14 -1 22 21 -1
 -1  2 -1  6 -1 10 -1 12 -1 14 -1 -1 -1 20 -1
 -1  3  4  5 -1 11 12 13 -1 15 16 17 18 19 -1
 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Notice how numbers indicate the (shortest) distance from that cell to the target ([1,1] in the example). All we have to do now is follow the numbers back:

function path_from(maze, x, y):
    dist = maze[y][x]
    if dist < 1 then return invalid

    path = [ [x,y] ]
    neighbours = [ [-1, 0], [0, -1], [+1, 0], [0, +1] ]
    while dist > 1:
        dist = dist - 1
        x0 = x: y0 = y
        for each nbr in neighbours:
            x = x0 + nbr[0]: y = y0 + nbr[1]
            if maze[y][x] = dist:
                path.push([x, y])
                exit for
            end if
        end for
    end while
    return path
end function

BrightScript Debugger> pt = path_from(maze, 12, 1)
BrightScript Debugger> ? toJSON(pt)
[[12,1],[13,1],[13,2],[13,3],[12,3],[11,3],[10,3],[9,3],[9,2],[9,1],[8,1],[7,1],[6,1],[5,1],[4,1],[3,1],[3,2],[3,3],[2,3],[1,3],[1,2],[1,1]]

Decoding the path, that is

+-------------+
|.Ov<<<<<<.O>v|
|^OvO.O.O^OOOv|
|^<<O...O^<<<v|
+-------------+

[Komag]

I've finally got back around to this and implemented a very rough and inefficient newbie attempt at A*, which I'll probably try to refine and streamline if I can. This has definitely been one of the most challenging parts of programming my game, hard to get my head around it all.