-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.js
174 lines (143 loc) · 5.62 KB
/
bfs.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
// list a direction array for knight moves in chess
const directions = [
[-2, -1],
[-2, 1],
[-1, -2],
[-1, 2],
[1, -2],
[1, 2],
[2, -1],
[2, 1]
];
// a src/target bfs returning the cells traversed to get to target
function bfs(src, target) {
// create a queue and enqueue first cell
let q = [];
q.push({ x: src.x, y: src.y, path: `(${src.x},${src.y}).` });
// create a set to avoid cycles
let visited = new Set();
visited.add(src.x + src.y * 8);
// loop until queue is empty
while (q.length > 0) {
let curr = q.shift();
// if we have reached the target cell, return its distance
if (curr.x === target.x && curr.y === target.y) {
return curr.path;
}
// loop for all reachable states
for (let i = 0; i < directions.length; i++) {
let x = curr.x + directions[i][0];
let y = curr.y + directions[i][1];
// if reachable state is not yet visited and inside board, push that state into queue
if (isInsideBoard(x, y) && !visited.has(x + y * 8)) {
visited.add(x + y * 8);
q.push({ x, y, path: curr.path + `(${x},${y}).` });
}
}
}
// return -1 if path is not possible
return -1;
}
// check if (x, y) is valid chess board coordinates
function isInsideBoard(x, y) {
return x >= 0 && x < 8 && y >= 0 && y < 8;
}
// testing bfs
let a1 = bfs({ x: 0, y: 0 }, { x: 3, y: 3 });
console.log(a1); // (0,0)(2,1)(3,3)
// UIManager
class UIManager {
constructor() {
this.chessboard = document.querySelector('.chessboard');
this.createChessBoard();
this.pressedCoords = [];
}
createChessBoard() {
let self = this;
// Create 8 rows
for (let i = 0; i < 8; i++) {
const row = document.createElement('div');
row.classList.add('row');
// Create 8 cells in each row
for (let j = 0; j < 8; j++) {
const cell = document.createElement('div');
cell.classList.add('cell');
// Add a unique identifier to each cell based on its row and column
cell.setAttribute('data-row', i);
cell.setAttribute('data-col', j);
// Add a click event listener to each cell
cell.addEventListener('click', function() {
self.removeKnight();
const row = this.getAttribute('data-row');
const col = this.getAttribute('data-col');
self.pressedCoords.push([Number(row), Number(col)]);
cell.classList.toggle('highlight')
if (self.pressedCoords.length === 2) {
let a1 = bfs({ x: self.pressedCoords[0][0], y: self.pressedCoords[0][1] }, { x: self.pressedCoords[1][0], y: self.pressedCoords[1][1] });
console.log(a1);
self.pressedCoords = [];
self.play(a1);
// remove highlight
let highlighted = document.querySelectorAll('.highlight');
highlighted.forEach((cell) => {
cell.classList.remove('highlight');
});
}
// console.log(`Clicked cell at row ${row}, column ${col}`);
});
// Alternate the color of cells
if ((i + j) % 2 === 0) {
cell.classList.add('white');
} else {
cell.classList.add('black');
}
row.appendChild(cell);
}
this.chessboard.appendChild(row);
}
}
// animate the path
play(path) {
// remove the last dot from the path
path = path.substring(0, path.length - 1);
// Split the path string into an array of coordinates
const coordinates = path.split('.').map(coord => {
const [x, y] = coord.substring(1, coord.length - 1).split(',').map(Number);
return { x, y };
});
// Function to move the knight to the next position with animation
const moveKnight = (index) => {
if (index >= coordinates.length) {
// Animation complete
return;
}
const { x, y } = coordinates[index];
const cell = document.querySelector(`.cell[data-row="${x}"][data-col="${y}"]`);
// Add a class for styling to indicate the knight's position
cell.classList.add('knight');
// Delay the next move for 500 milliseconds (adjust as needed)
setTimeout(() => {
// Remove the knight class from the previous cell
if (index > 0) {
const prevCoordinate = coordinates[index - 1];
const prevCell = document.querySelector(`.cell[data-row="${prevCoordinate.x}"][data-col="${prevCoordinate.y}"]`);
prevCell.classList.remove('knight');
}
// Move to the next position
moveKnight(index + 1);
}, 700); // Adjust the delay time as needed
};
// Start the animation by moving to the first position
moveKnight(0);
this.removeKnight();
}
// remove the knight from the board
removeKnight() {
let knight = document.querySelector('.knight');
if (knight) {
knight.classList.remove('knight');
}
}
}
// Create a new instance of the UIManager class
const uiManager = new UIManager();