Skip to content

Commit fed99cf

Browse files
Ghost---ShadowGhost---Shadow
authored
Merge pull request aimacode#52 from Rishav159/breadthFirstSearch
BreadthFirstSearch Fixed to match the psuedocode
2 parents 1903f1f + 06228ce commit fed99cf

3 files changed

Lines changed: 186 additions & 139 deletions

File tree

‎3-Solving-Problems-By-Searching/breadthFirstSearch.js‎

Lines changed: 36 additions & 61 deletions
Original file line numberDiff line numberDiff line change
@@ -1,62 +1,37 @@
1-
// Code for Breadth First Search
2-
var get_index = function(x,y,max_row,max_col){
3-
return x*max_col + y
4-
};
5-
var breadthFirstSearch = function(){
6-
// Initialize the queue with the source node
7-
var queue = [nodes_list[source_index]];
8-
//Execute this function till queue is empty or destination is reached
9-
interval_function = setInterval(function(){
10-
//if queue is empty , stop the iteration
11-
if(queue.length==0){
12-
clearInterval(interval_function,time_interval)
13-
}
14-
//pop out the element from the queue
15-
curr_node = queue.shift();
16-
//visit that node
17-
visit_node(curr_node);
18-
//Check through each of the neighbors of the current node
19-
for(var i=0;i < curr_node.neighbors.length;i++){
20-
adj_node = nodes_list[curr_node.neighbors[i]];
21-
//If node is not visited before and not blocked
22-
if(!adj_node.visited && !adj_node.is_blocked){
23-
//Add the reference to previous node to retrace the path later
24-
adj_node.prev = curr_node
25-
//If the adjacent node is the destination, stop the iteration
26-
if(adj_node.is_dest){
27-
clearInterval(interval_function,time_interval);
28-
//Retrace the path
29-
finish_traversal(adj_node)
30-
}else{
31-
//Push the node to the queue and color it accordingly
32-
add_to_queue(queue,adj_node)
33-
}
34-
}
35-
}
36-
//Update the front end visualization
37-
two.update();
38-
},time_interval);
39-
}
40-
var node = function(x,y,max_row,max_col){
41-
this.x = x;
42-
this.y = y;
43-
this.visited = false;
44-
this.is_source = false;
45-
this.is_dest = false;
46-
this.is_blocked = false;
47-
this.neighbors = [];
48-
if(this.x > 0){
49-
this.neighbors.push(get_index(this.x-1,this.y,max_row,max_col))
50-
};
51-
if(this.y < max_col-1){
52-
this.neighbors.push(get_index(this.x,this.y+1,max_row,max_col))
53-
};
54-
if(this.x < max_row-1){
55-
this.neighbors.push(get_index(this.x+1,this.y,max_row,max_col))
56-
};
57-
if(this.y > 0){
58-
this.neighbors.push(get_index(this.x,this.y-1,max_row,max_col))
59-
};
601

61-
return this;
62-
};
2+
var breadthFirstSearch = function(problem){
3+
this.problem = problem;
4+
this.node = problem.INITIAL;
5+
if(this.problem.GOAL_TEST(this.node)){
6+
return this.problem.NO_ACTION;
7+
}
8+
this.frontier = [this.node];
9+
this.explored = {};
10+
this.iterate = function(){
11+
var isNewState = false;
12+
//If Goal reached, Return No Action
13+
if(this.problem.GOAL_TEST(this.node)){
14+
return [isNewState,this.problem.NO_ACTION];
15+
}
16+
//If stack is empty, return No Action
17+
if(this.frontier.length == 0){
18+
return [isNewState,this.problem.NO_ACTION];
19+
}
20+
//Extract the shallowest node from the queue
21+
node = this.frontier.shift();
22+
this.node = node;
23+
//Add Extracted node to explored
24+
this.explored[node] = true;
25+
actions = this.problem.ACTIONS(node)
26+
for(var i = 0; i < actions.length; i++){
27+
var action = actions[i]
28+
child = this.problem.CHILD_NODE(node,action);
29+
if(!this.explored[child]){
30+
this.frontier.push(child);
31+
this.explored[child] = true;
32+
}
33+
}
34+
isNewState = true;
35+
return [isNewState,node]
36+
}
37+
}

‎3-Solving-Problems-By-Searching/c_breadthFirstSearch.js‎

Lines changed: 149 additions & 75 deletions
Original file line numberDiff line numberDiff line change
@@ -1,88 +1,162 @@
1-
const max_row = 10;
2-
const max_col = 22;
3-
const node_size =30;
4-
const padding = node_size/2;
5-
var nodes_list = [];
6-
var fnodes_list = [];
7-
var source_index = 90;
8-
var dest_index = 107;
9-
var bfs_canvas;
10-
var w = 660 ,h = 300;
11-
var time_interval = 50;
12-
var interval_function;
13-
14-
var finish_traversal = function(dest){
15-
curr_node = dest.prev
16-
while(!curr_node.is_source){
17-
curr_node.f_node.fill='yellow'
18-
curr_node = curr_node.prev
19-
}
20-
}
21-
var visit_node = function(node){
22-
node.visited = true
23-
if(!curr_node.is_source && !curr_node.is_dest){
24-
curr_node.f_node.fill='rgb(216, 34, 194)';
25-
}
26-
}
27-
var add_to_queue = function(queue,node){
28-
queue.push(node)
29-
node.visited = true
30-
node.f_node.fill='rgb(113, 242, 135)';
31-
}
32-
var onclick_handler = function(){
33-
index = this.getAttribute('list_index')
34-
curr_node = nodes_list[index]
35-
if(!curr_node.is_source && !curr_node.is_dest){
36-
if(curr_node.is_blocked){
37-
this.setAttribute('fill','#fff');
38-
curr_node.is_blocked=false;
39-
}else{
40-
curr_node.is_blocked=true;
41-
this.setAttribute('fill','#a8a8a8');
42-
};
1+
var bfsProblemStatement = function(graph,start,end){
2+
3+
this.graph = graph;
4+
this.ROWS = this.graph.length;
5+
this.COLS = this.graph[0].length;
6+
this.TOTAL_STATES = this.ROWS * this.COLS;
7+
this.INITIAL = start;
8+
this.END = end;
9+
10+
this.NO_ACTION = 0;
11+
this.UP = 1;
12+
this.RIGHT = 2;
13+
this.DOWN = 3;
14+
this.LEFT = 4;
15+
16+
this.at = function(i,j){
17+
return i * this.COLS + j;
4318
};
44-
};
45-
var initialize_start_end = function(){
46-
source = nodes_list[source_index];
47-
destination = nodes_list[dest_index];
48-
source.is_source=true
49-
destination.is_dest = true
50-
source.f_node.fill='green'
51-
destination.f_node.fill='blue'
52-
};
53-
var init = function(){
54-
clearInterval(interval_function,time_interval)
55-
bfs_canvas = document.getElementById('breadthFirstSearchCanvas');
56-
bfs_canvas.innerHTML = ""
57-
nodes_list = []
58-
two = new Two({ width: w, height: h }).appendTo(bfs_canvas);
59-
for(var i=0;i<max_row;i++){
60-
for(var j=0;j<max_col;j++){
61-
x_offset = (j%max_col)*node_size + padding;
62-
y_offset = (i%max_row)*node_size + padding;
63-
var index = get_index(i,j,max_row,max_col)
64-
var f_node = two.makeRectangle(x_offset,y_offset,node_size,node_size);
65-
var curr_node = new node(i,j,max_row,max_col);
66-
curr_node.f_node = f_node
67-
two.update();
68-
nodes_list.push(curr_node);
69-
document.getElementById(f_node.id).setAttribute("list_index",index);
70-
f_node._renderer.elem.addEventListener('mousedown',onclick_handler);
71-
};
19+
this.getIJ = function(x){
20+
return [parseInt(x/this.COLS),x%this.COLS];
21+
};
22+
this.GOAL_TEST = function(state){
23+
return this.END == state;
7224
};
73-
initialize_start_end();
74-
two.update();
75-
}
25+
this.ACTIONS = function(state){
26+
var actions = [this.NO_ACTION];
27+
var i = this.getIJ(state)[0];
28+
var j = this.getIJ(state)[1];
29+
if(i - 1 >= 0 && !this.graph[i-1][j]) actions.push(this.UP);
30+
if(i + 1 < this.ROWS && !this.graph[i+1][j]) actions.push(this.DOWN);
31+
if(j - 1 >= 0 && !this.graph[i][j-1]) actions.push(this.LEFT);
32+
if(j + 1 < this.COLS && !this.graph[i][j+1]) actions.push(this.RIGHT);
33+
return actions;
34+
};
35+
this.CHILD_NODE = function(state,action){
36+
var x = this.getIJ(state)[0];
37+
var y = this.getIJ(state)[1];
38+
switch(action){
39+
case this.NO_ACTION: break;
40+
case this.UP:x--;break;
41+
case this.RIGHT:y++;break;
42+
case this.DOWN:x++;break;
43+
case this.LEFT:y--;break;
44+
}
45+
return this.at(x,y)
46+
}
47+
};
48+
49+
50+
7651
$(document).ready(function(){
7752
$.ajax({
7853
url : "breadthFirstSearch.js",
7954
dataType: "text",
8055
success : function (data) {
81-
document.getElementById('breadthFirstSearchCode').innerHTML = data;
56+
$("#breadthFirstSearchCode").html(data);
8257
}
8358
});
8459

8560

86-
init();
61+
var two,canvas,bfs;
8762

63+
var graph = [[0,0,0,0,1,1,0,0,1,1],
64+
[1,1,0,0,1,0,1,0,0,0],
65+
[0,0,0,0,0,0,0,0,1,1],
66+
[0,0,1,0,1,1,0,0,0,0],
67+
[0,1,1,0,1,1,1,1,0,1],
68+
[0,0,1,0,1,1,0,1,0,0],
69+
[1,0,1,0,1,0,0,0,0,0]];
70+
71+
var start = 0;
72+
var end = 19;
73+
74+
var DELAY = 0.5 *60;
75+
var SIZE = 40;
76+
var NONBLOCKING = "#AAAACC";
77+
var BLOCKING = "#555577";
78+
var EXPLORED = "#edb168";
79+
var STARTCOLOR = "#EE6622";
80+
var ENDCOLOR = "#66EE22";
81+
var FINISHCOLOR = "#0d6d1e";
82+
var w,h,baseX,baseY;
83+
84+
var problem = undefined;
85+
var state,lastState;
86+
var m_frame = DELAY;
87+
var tiles = [];
88+
89+
function updateHandler(frameCount){
90+
--m_frame;
91+
lastState = state;
92+
if(m_frame == 0){
93+
step();
94+
m_frame = DELAY
95+
}else{
96+
interpolate();
97+
}
98+
};
99+
function clickHandler(){
100+
two.unbind('update');
101+
tiles = [];
102+
m_frame = DELAY;
103+
init();
104+
}
105+
function init(){
106+
canvas = document.getElementById('breadthFirstSearchCanvas');
107+
canvas.addEventListener('click',clickHandler,false);
108+
canvas.innerHTML = "";
109+
w = canvas.offsetWidth, h = 300;
110+
two = new Two({width:w , height:h}).appendTo(canvas);
111+
problem = new bfsProblemStatement(graph,start,end);
112+
bfs = new breadthFirstSearch(problem);
113+
114+
state = lastState = problem.INITIAL;
115+
baseX = two.width/2 - problem.COLS/2 * SIZE;
116+
baseY = two.height/2 - problem.ROWS/2 * SIZE;
117+
118+
two.bind('update',updateHandler).play();
119+
120+
drawBackground();
121+
};
122+
123+
function step(){
124+
var isNewState,newState;
125+
[isNewState,newState] = bfs.iterate();
126+
if(isNewState){
127+
state = newState;
128+
}
129+
};
130+
131+
132+
133+
function drawBackground(){
134+
for(var i = 0; i < problem.ROWS; i++){
135+
for(var j = 0; j < problem.COLS; j++){
136+
var temp = two.makeRectangle(SIZE/2+j*SIZE,SIZE/2+i*SIZE,SIZE,SIZE);
137+
if(problem.graph[i][j])
138+
temp.fill = BLOCKING;
139+
else
140+
temp.fill = NONBLOCKING;
141+
temp.noStroke();
142+
tiles.push(temp);
143+
144+
}
145+
}
146+
tiles[problem.INITIAL].fill = STARTCOLOR;
147+
tiles[problem.END].fill = ENDCOLOR;
148+
var backgroundGroup = two.makeGroup(tiles);
149+
backgroundGroup.translation.set(baseX,baseY);
150+
};
151+
152+
function interpolate(){
153+
if(state != problem.INITIAL && state!= problem.END){
154+
tiles[state].fill = EXPLORED;
155+
}
156+
if(state == problem.END){
157+
tiles[state].fill = FINISHCOLOR;
158+
}
159+
}
160+
161+
init();
88162
});

‎3-Solving-Problems-By-Searching/index.html‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -36,9 +36,7 @@ <h1>Solving Problems By Searching</h1>
3636

3737
<h2>Breadth First Search</h2>
3838
<p>Click on the canvas to restart the simulation</p>
39-
<button type="button" onclick='breadthFirstSearch();'>Start BFS</button>
40-
<button type="button" onclick='init()'>Reset</button>
41-
<div class = "canvas" id="breadthFirstSearchCanvas" height="300px" style="background: rgb(154, 255, 255);">
39+
<div class = "canvas" id="breadthFirstSearchCanvas" height="300px">
4240
</div>
4341

4442
<pre id="breadthFirstSearchCode"></pre>

0 commit comments

Comments
 (0)