Data

in lua

Tags

graph traversal, pathfinding

Source Code

-- Generic Breadth-First search algorithm implementation

-- Notes : this is a generic implementation of Breadth-First search algorithm.
-- It is devised to be used on any type of graph (point-graph, tile-graph,
-- or whatever. It expects to be initialized with a handler, which acts as
-- an interface between the search algorithm and the search space.

-- This implementation uses a FIFO (First In First Out) queue, which can be
-- easily represented via a simple Lua array (see fifo.lua).

-- The BFS class expects a handler to be initialized. Roughly said, the handler
-- is an interface between your search space and the generic search algorithm.
-- This ensures flexibility, so that the generic algorithm can be adapted to
-- search on any kind of space.
-- The passed-in handler should implement those functions.
-- handler.getNode(...)   ->  returns a Node (instance of node.lua)
-- handler.getNeighbors(n) -> returns an array of all nodes that can be reached
--                            via node n (also called successors of node n)

-- The generic Node class provided (see node.lua) should also be implemented
-- through the handler. Basically, it should describe how nodes are labelled
-- and tested for equality for a custom search space.
-- The following functions should be implemented:
-- function Node:initialize(...) -> creates a Node with custom attributes
-- function Node:isEqualTo(n)    -> returns if self is equal to node n
-- function Node:toString()      -> returns a unique string representation of
--                                  the node, for debug purposes

-- See custom handlers for reference (*_hander.lua).

-- Dependencies
local class = require 'utils.class'
local fifo  = require 'utils.fifo'

-- Clears nodes data between consecutive path requests.
local function resetForNextSearch(bfs)
for node in pairs(bfs.visited) do
node.parent, node.visited = nil, nil
end
bfs.queue:clear()
bfs.visited = {}
end

-- Builds and returns the path to the goal node
local function backtrace(node)
local path = {}
repeat
table.insert(path, 1, node)
node = node.parent
until not node
return path
end

-- Initializes Breadth-Fist search with a custom handler
local BFS = class()
function BFS:initialize(handler)
self.handler = handler
self.queue = fifo()
self.visited = {}
end

-- Returns the path between start and goal locations
-- start   : a Node representing the start location
-- goal    : a Node representing the target location
-- returns : an array of nodes
function BFS:findPath(start, goal)
resetForNextSearch(self)

start.visited = true
self.queue:push(start)
self.visited[start] = true
while not self.queue:isEmpty() do
local node = self.queue:pop()
if node == goal then return backtrace(node) end
local neighbors = self.handler.getNeighbors(node)
for _, neighbor in ipairs(neighbors) do
if not neighbor.visited then
neighbor.visited = true
neighbor.parent = node
self.queue:push(neighbor)
self.visited[neighbor] = true
end
end
end
end

return BFS
-- Tests for bfs.lua
local BFS = require 'bfs'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function same(t, p, comp)
for k,v in ipairs(t) do
if not comp(v, p[k]) then return false end
end
return true
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Testing linear graph', function()
local comp = function(a, b) return a.value == b end
local ln_handler = require 'handlers.linear_handler'
ln_handler.init(-2,5)
local bfs = BFS(ln_handler)
local start, goal = ln_handler.getNode(0), ln_handler.getNode(5)
assert(same(bfs:findPath(start, goal),  {0,1,2,3,4,5}, comp))

start, goal = ln_handler.getNode(-2), ln_handler.getNode(2)
assert(same(bfs:findPath(start, goal),  {-2,-1,0,1,2}, comp))
end)

run('Testing grid graph', function()
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
local gm_handler = require 'handlers.gridmap_handler'
local bfs = BFS(gm_handler)
local map = {{0,0,0,0,0},{0,1,1,1,1},{0,0,0,0,0}}
gm_handler.init(map)

gm_handler.diagonal = false
local start, goal = gm_handler.getNode(1,1), gm_handler.getNode(5,3)
assert(same(bfs:findPath(start, goal), {{1,1},{1,2},{1,3},{2,3},{3,3},{4,3},{5,3}}, comp))

gm_handler.diagonal = true
assert(same(bfs:findPath(start, goal), {{1,1},{1,2},{2,3},{3,3},{4,3},{5,3}},       comp))
end)

run('Testing point graph', function()
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
local pg_handler = require 'handlers.point_graph_handler'
local bfs = BFS(pg_handler)