Skip to content

Commit 6c0ffb9

Browse files
jcla1jcla1
committed
Merge pull request kennyledet#216 from Yonaba/master
Added BFS and Greedy BFS in Lua
2 parents 51f5090 + 0289d45 commit 6c0ffb9

9 files changed

Lines changed: 551 additions & 1 deletion

File tree

‎Best_First_Search/Lua/Yonaba/bfs.lua‎

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
-- Generic Best First Search algorithm implementation
2+
-- See : http://en.wikipedia.org/wiki/Best-first_search
3+
4+
-- Notes : this is a generic implementation of BFS graph search algorithm.
5+
-- It is devised to be used on any type of graph (point-graph, tile-graph,
6+
-- or whatever. It expects to be initialized with a handler, which acts as
7+
-- an interface between the search algorithm and the search space.
8+
9+
-- This implementation uses internally a binary heap to handle fast retrieval
10+
-- of the lowest-cost node.
11+
12+
-- The BFS class expects a handler to be initialized. Roughly said, the handler
13+
-- is an interface between your search space and the generic search algorithm.
14+
-- This model ensures flexibility, so that this generic implementation can be
15+
-- adapted to search on any kind of space.
16+
-- The passed-in handler should implement those functions.
17+
-- handler.getNode(...) -> returns a Node (instance of node.lua)
18+
-- handler.distance(a, b) -> heuristic function which returns the distance
19+
-- between node a and node b
20+
-- handler.getNeighbors(n) -> returns an array of all nodes that can be reached
21+
-- via node n (also called successors of node n)
22+
23+
-- The generic Node class provided (see node.lua) should also be implemented
24+
-- through the handler. Basically, it should describe how nodes are labelled
25+
-- and tested for equality for a custom search space.
26+
-- The following functions should be implemented:
27+
-- function Node:initialize(...) -> creates a Node with custom attributes
28+
-- function Node:isEqualTo(n) -> returns if self is equal to node n
29+
-- function Node:toString() -> returns a unique string representation of
30+
-- the node, for debug purposes
31+
32+
-- See custom handlers for reference (*_hander.lua).
33+
34+
-- Dependencies
35+
local class = require 'class'
36+
local bheap = require 'bheap'
37+
38+
-- Clears nodes data between consecutive path requests.
39+
local function clearNodes(bfs)
40+
for node in pairs(bfs.visited) do
41+
node.parent, node.opened, node.closed = nil, nil, nil
42+
node.cost = 0
43+
end
44+
bfs.visited = {}
45+
end
46+
47+
-- Builds and returns the path to the goal node
48+
local function backtrace(node)
49+
local path = {}
50+
repeat
51+
table.insert(path, 1, node)
52+
node = node.parent
53+
until not node
54+
return path
55+
end
56+
57+
-- Initializes BFS search with a custom handler
58+
local BFS = class()
59+
function BFS:initialize(handler)
60+
self.handler = handler
61+
self.Q = bheap()
62+
self.heuristic = handler.distance
63+
self.visited = {}
64+
end
65+
66+
-- Returns the path between start and goal locations
67+
-- start : a Node representing the start location
68+
-- goal : a Node representing the target location
69+
-- greedy : if true, switches to Greedy Best-First Search
70+
function BFS:findPath(start, goal)
71+
self.Q:clear()
72+
clearNodes(self)
73+
74+
start.cost = self.heuristic(start, goal)
75+
self.Q:push(start)
76+
self.visited[start] = true
77+
78+
while not self.Q:isEmpty() do
79+
local node = self.Q:pop()
80+
if node == goal then return backtrace(node) end
81+
node.closed = true
82+
local neighbors = self.handler.getNeighbors(node)
83+
if greedy then
84+
-- Greedy Best-First Search
85+
local first_neighbor = neighbors[1]
86+
if first_neighbor then
87+
local cost_from_first_neighbor = self.heuristic(first_neighbor, goal)
88+
if cost_from_first_neighbor < node.cost then
89+
first_neighbor.parent = node
90+
first_neighbor.cost = cost_from_first_neighbor
91+
self.Q:push(first_neighbor)
92+
self.Q:push(node)
93+
self.visited[first_neighbor] = true
94+
end
95+
end
96+
else
97+
-- STandard Best-First Search
98+
for _, neighbor in ipairs(neighbors) do
99+
if not neighbor.closed then
100+
local tentative_cost = self.heuristic(neighbor, goal)
101+
if not neighbor.opened or tentative_cost < neighbor.cost then
102+
neighbor.parent = node
103+
neighbor.cost = tentative_cost
104+
self.visited[neighbor] = true
105+
if not neighbor.opened then
106+
neighbor.opened = true
107+
self.Q:push(neighbor)
108+
else
109+
self.openList:sort(neighbor)
110+
end
111+
end
112+
end
113+
end
114+
end
115+
end
116+
117+
end
118+
119+
return BFS

‎Best_First_Search/Lua/Yonaba/bfs_test.lua‎

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
-- Tests for bfs.lua
2+
local BFS = require 'bfs'
3+
4+
local total, pass = 0, 0
5+
6+
local function dec(str, len)
7+
return #str < len
8+
and str .. (('.'):rep(len-#str))
9+
or str:sub(1,len)
10+
end
11+
12+
local function same(t, p, comp)
13+
for k,v in ipairs(t) do
14+
if not comp(v, p[k]) then return false end
15+
end
16+
return true
17+
end
18+
19+
local function run(message, f)
20+
total = total + 1
21+
local ok, err = pcall(f)
22+
if ok then pass = pass + 1 end
23+
local status = ok and 'PASSED' or 'FAILED'
24+
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
25+
end
26+
27+
run('Testing BFS search on linear graph', function()
28+
local comp = function(a, b) return a.value == b end
29+
local ln_handler = require 'linear_handler'
30+
local bfs = BFS(ln_handler)
31+
local start, goal = ln_handler.getNode(0), ln_handler.getNode(5)
32+
assert(same(bfs:findPath(start, goal), {0,1,2,3,4,5}, comp))
33+
34+
start, goal = ln_handler.getNode(-2), ln_handler.getNode(2)
35+
assert(same(bfs:findPath(start, goal), {-2,-1,0,1,2}, comp))
36+
end)
37+
38+
run('Testing Greedy BFS search on linear graph', function()
39+
local comp = function(a, b) return a.value == b end
40+
local ln_handler = require 'linear_handler'
41+
local bfs = BFS(ln_handler)
42+
local start, goal = ln_handler.getNode(0), ln_handler.getNode(5)
43+
assert(same(bfs:findPath(start, goal, true), {0,1,2,3,4,5}, comp))
44+
45+
start, goal = ln_handler.getNode(-2), ln_handler.getNode(2)
46+
assert(same(bfs:findPath(start, goal, true), {-2,-1,0,1,2}, comp))
47+
end)
48+
49+
run('Testing BFS search on grid graph', function()
50+
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
51+
local gm_handler = require 'gridmap_handler'
52+
local bfs = BFS(gm_handler)
53+
gm_handler.map = {{0,0,0,0,0},{0,1,1,1,1},{0,0,0,0,0}}
54+
55+
gm_handler.diagonal = false
56+
local start, goal = gm_handler.getNode(1,1), gm_handler.getNode(5,3)
57+
assert(same(bfs:findPath(start, goal), {{1,1},{1,2},{1,3},{2,3},{3,3},{4,3},{5,3}}, comp))
58+
59+
gm_handler.diagonal = true
60+
assert(same(bfs:findPath(start, goal), {{1,1},{1,2},{2,3},{3,3},{4,3},{5,3}}, comp))
61+
end)
62+
63+
run('Testing Greedy BFS search on grid graph', function()
64+
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
65+
local gm_handler = require 'gridmap_handler'
66+
local bfs = BFS(gm_handler)
67+
gm_handler.map = {{0,0,0,0,0},{0,1,1,1,1},{0,0,0,0,0}}
68+
69+
gm_handler.diagonal = false
70+
local start, goal = gm_handler.getNode(1,1), gm_handler.getNode(5,3)
71+
assert(same(bfs:findPath(start, goal,true), {{1,1},{1,2},{1,3},{2,3},{3,3},{4,3},{5,3}}, comp))
72+
73+
gm_handler.diagonal = true
74+
assert(same(bfs:findPath(start, goal,true), {{1,1},{1,2},{2,3},{3,3},{4,3},{5,3}}, comp))
75+
end)
76+
77+
run('Testing BFS search on point graph', function()
78+
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
79+
local pg_handler = require 'point_graph_handler'
80+
local bfs = BFS(pg_handler)
81+
82+
pg_handler.addNode('a')
83+
pg_handler.addNode('b')
84+
pg_handler.addNode('c')
85+
pg_handler.addNode('d')
86+
pg_handler.addNode('e')
87+
pg_handler.addEdge('a', 'b', 10)
88+
pg_handler.addEdge('b', 'e', 10)
89+
pg_handler.addEdge('a', 'c', 5)
90+
pg_handler.addEdge('c', 'd', 5)
91+
pg_handler.addEdge('d', 'e', 5)
92+
93+
local comp = function(a, b) return a.name == b end
94+
local start, goal = pg_handler.getNode('a'), pg_handler.getNode('e')
95+
assert(same(bfs:findPath(start, goal), {'a','c','d','e'}, comp))
96+
97+
pg_handler.setEdgeWeight('a', 'b', 1)
98+
pg_handler.setEdgeWeight('b', 'e', 1)
99+
100+
assert(same(bfs:findPath(start, goal), {'a','b','e'}, comp))
101+
end)
102+
103+
run('Testing Greedy BFS search on point graph', function()
104+
local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
105+
local pg_handler = require 'point_graph_handler'
106+
local bfs = BFS(pg_handler)
107+
108+
pg_handler.addNode('a')
109+
pg_handler.addNode('b')
110+
pg_handler.addNode('c')
111+
pg_handler.addNode('d')
112+
pg_handler.addNode('e')
113+
pg_handler.addEdge('a', 'b', 10)
114+
pg_handler.addEdge('b', 'e', 10)
115+
pg_handler.addEdge('a', 'c', 5)
116+
pg_handler.addEdge('c', 'd', 5)
117+
pg_handler.addEdge('d', 'e', 5)
118+
119+
local comp = function(a, b) return a.name == b end
120+
local start, goal = pg_handler.getNode('a'), pg_handler.getNode('e')
121+
assert(same(bfs:findPath(start, goal,true), {'a','c','d','e'}, comp))
122+
123+
pg_handler.setEdgeWeight('a', 'b', 1)
124+
pg_handler.setEdgeWeight('b', 'e', 1)
125+
126+
assert(same(bfs:findPath(start, goal,true), {'a','b','e'}, comp))
127+
end)
128+
129+
print(('-'):rep(80))
130+
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
131+
:format(total, pass, total-pass, (pass*100/total)))

‎Best_First_Search/Lua/Yonaba/bheap.lua‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
-- Binary Heap data structure implementation
2+
-- See: http://www.policyalmanac.org/games/binaryHeaps.htm
3+
-- Adapted from: https://github.com/Yonaba/Binary-Heaps
4+
5+
local class = require 'class'
6+
7+
-- Looks for item in an array
8+
local function findIndex(array, item)
9+
for k,v in ipairs(array) do
10+
if v == item then return k end
11+
end
12+
end
13+
14+
-- Percolates up to restore heap property
15+
local function sift_up(bheap, index)
16+
if index == 1 then return end
17+
local pIndex
18+
if index <= 1 then return end
19+
if index%2 == 0 then
20+
pIndex = index/2
21+
else pIndex = (index-1)/2
22+
end
23+
if not bheap._sort(bheap._heap[pIndex], bheap._heap[index]) then
24+
bheap._heap[pIndex], bheap._heap[index] =
25+
bheap._heap[index], bheap._heap[pIndex]
26+
sift_up(bheap, pIndex)
27+
end
28+
end
29+
30+
-- Percolates down to restore heap property
31+
local function sift_down(bheap,index)
32+
local lfIndex,rtIndex,minIndex
33+
lfIndex = 2*index
34+
rtIndex = lfIndex + 1
35+
if rtIndex > bheap.size then
36+
if lfIndex > bheap.size then return
37+
else minIndex = lfIndex end
38+
else
39+
if bheap._sort(bheap._heap[lfIndex],bheap._heap[rtIndex]) then
40+
minIndex = lfIndex
41+
else
42+
minIndex = rtIndex
43+
end
44+
end
45+
if not bheap._sort(bheap._heap[index],bheap._heap[minIndex]) then
46+
bheap._heap[index],bheap._heap[minIndex] = bheap._heap[minIndex],bheap._heap[index]
47+
sift_down(bheap,minIndex)
48+
end
49+
end
50+
51+
-- Binary heap class
52+
-- Instantiates minHeaps by default
53+
local bheap = class()
54+
function bheap:initialize()
55+
self.size = 0
56+
self._sort = function(a,b) return a < b end
57+
self._heap = {}
58+
end
59+
60+
-- Clears the heap
61+
function bheap:clear()
62+
self._heap = {}
63+
self.size = 0
64+
end
65+
66+
-- Checks if the heap is empty
67+
function bheap:isEmpty()
68+
return (self.size==0)
69+
end
70+
71+
-- Pushes a new item into the heap
72+
function bheap:push(item)
73+
self.size = self.size + 1
74+
self._heap[self.size] = item
75+
sift_up(self, self.size)
76+
end
77+
78+
-- Pops the lowest (or highest) best item out of the heap
79+
function bheap:pop()
80+
local root
81+
if self.size > 0 then
82+
root = self._heap[1]
83+
self._heap[1] = self._heap[self.size]
84+
self._heap[self.size] = nil
85+
self.size = self.size-1
86+
if self.size > 1 then
87+
sift_down(self, 1)
88+
end
89+
end
90+
return root
91+
end
92+
93+
-- Sorts a specific item in the heap
94+
function bheap:sort(item)
95+
if self.size <= 1 then return end
96+
local i = findIndex(self._heap, item)
97+
if i then sift_up(self, i) end
98+
end
99+
100+
return bheap

‎Best_First_Search/Lua/Yonaba/class.lua‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
-- Minimalistic class implementation
2+
3+
local class = function(attr)
4+
local klass = attr or {}
5+
klass.__index = klass
6+
klass.__call = function(_,...) return klass:new(...) end
7+
function klass:new(...)
8+
local instance = setmetatable({}, klass)
9+
klass.initialize(instance, ...)
10+
return instance
11+
end
12+
return setmetatable(klass,{__call = klass.__call})
13+
end
14+
15+
return class

0 commit comments

Comments
 (0)