Roku Developer Program

Developers and content creators—a complete solution for growing an audience directly.
cancel
Showing results for 
Search instead for 
Did you mean: 
Komag
Level 9

Pathfinding for AI? What language closest to BrightSscript?

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?
0 Kudos
6 Replies
EnTerr
Level 8

Re: Pathfinding for AI? What language closest to BrightSscri

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.
0 Kudos
dev42
Level 7

Re: Pathfinding for AI? What language closest to BrightSscri

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
0 Kudos
Komag
Level 9

Re: Pathfinding for AI? What language closest to BrightSscri

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.
0 Kudos
Highlighted
EnTerr
Level 8

Re: Pathfinding for AI? What language closest to BrightSscri

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
0 Kudos
EnTerr
Level 8

Finding path in a maze

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|
+-------------+
0 Kudos
Komag
Level 9

Re: Pathfinding for AI? What language closest to BrightSscript?

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.
0 Kudos