Skip to content

Commit d76241c

Browse files
mime9599mime9599
committed
fixing maze creation
1 parent 0ac1b7e commit d76241c

26 files changed

Lines changed: 410 additions & 347 deletions

‎src/Utility/Colors.js‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
export const TEST_COLOR = '#FF66CC';
2+
export const BURN_COLOR = '#fad6ee';
3+
export const PATH_COLOR = '#63caef';
4+
export const WALL_COLOR = '#624646';
5+
export const GOAL_COLOR = '#30fa04';
6+
export const START_COLOR = '#ff0000';
7+
export const SELECTED_COLOR = '#ffd300';
8+
export const FLOOR_COLOR = '#ffffff';
9+
export const DEFAULT_COLOR = '#8f8d8d';
10+
export const FLOOR_TYPE = '_floor_';
11+
export const DEFAULT_TYPE = '_default_';
12+
export const WALL_TYPE = '_wall_';
13+
export const PATH_TYPE = '_path_';
14+
export const GOAL_TYPE = '_goal_';
15+
export const START_TYPE = '_start_';
16+
export const TEST_TYPE = '_test_';
17+
18+
19+
export function getColor(type) {
20+
switch (type) {
21+
case FLOOR_TYPE:
22+
return FLOOR_COLOR;
23+
case WALL_TYPE:
24+
return WALL_COLOR;
25+
case PATH_TYPE:
26+
return PATH_COLOR;
27+
case GOAL_TYPE:
28+
return GOAL_COLOR;
29+
case START_TYPE:
30+
return START_COLOR;
31+
case TEST_TYPE:
32+
return TEST_COLOR;
33+
case DEFAULT_TYPE:
34+
return DEFAULT_COLOR;
35+
default:
36+
return '#ffffff';
37+
}
38+
}

‎src/Utility/PriorityQueue.js‎

Lines changed: 32 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,31 @@
11
// User defined class
22
// to store element and its priority
33
class CellPQPair {
4-
constructor(element, priority) {
4+
constructor(element) {
55
this.cell = element;
6-
this.priority = priority;
6+
this.priority = element.priority;
77
}
88
}
99

1010

1111

1212
// Cell PriorityQueue class
13-
class PriorityQueue {
13+
export class PriorityQueue {
1414
constructor() {
1515
this.cellContainer = [];
1616
}
1717

1818

19-
enqueue(pElement, priority) {
20-
const element = new CellPQPair(pElement, priority);
21-
var contain = false;
22-
23-
for (var i = 0; i < this.cellContainer.length; i++) {
24-
if (this.cellContainer[i].priority > element.priority) {
25-
this.cellContainer.splice(i, 0, element);
26-
contain = true;
27-
break;
28-
}
29-
}
19+
enqueue(pElement) {
20+
let cellPair = new CellPQPair(pElement);
21+
this.cellContainer.push(cellPair);
22+
this.sort();
23+
}
3024

31-
if (!contain) {
32-
this.cellContainer.push(qElement);
33-
}
25+
sort() {
26+
this.cellContainer.sort((a, b) => {
27+
return a.cell.priority - b.cell.priority;
28+
});
3429
}
3530

3631

@@ -39,7 +34,8 @@ class PriorityQueue {
3934
console.log('Queue Underflow');
4035
return null;
4136
}
42-
return this.cellContainer.shift();
37+
38+
return this.cellContainer.shift().cell;
4339
}
4440

4541

@@ -48,7 +44,7 @@ class PriorityQueue {
4844
console.log('Queue Underflow');
4945
return null;
5046
}
51-
return this.cellContainer[0].id;
47+
return this.cellContainer[0].cell.id;
5248
}
5349

5450

@@ -57,9 +53,17 @@ class PriorityQueue {
5753
console.log('Empty Queue');
5854
return null;
5955
}
60-
return this.cellContainer[0];
56+
return this.cellContainer[0].cell;
57+
}
58+
59+
has(cell) {
60+
return !!this.cellContainer.find(cell => cell.cell.id === cell.id);
61+
6162
}
6263

64+
equals(other) {
65+
return this.cellContainer.every(cell => other.has(cell.cell));
66+
}
6367

6468
isEmpty() {
6569
return (this.cellContainer === undefined || this.cellContainer.length === 0);
@@ -71,4 +75,12 @@ class PriorityQueue {
7175
console.log(element.cell + ' ' + element.priority);
7276
}.bind(this));
7377
}
78+
79+
length() {
80+
return this.cellContainer.length;
81+
}
82+
83+
clear() {
84+
this.cellContainer = [];
85+
}
7486
}

‎src/components/Algorithms/Maze/Generation/BfsCreation.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
import {directions} from '../Directions';
2+
import {_FindCellVisitState, _FindCellTypeState, _FindCell, _BoardReset, _GetNeighbors, _SetWalls} from '../Tools';
3+
// import exit from 'exit';
4+
import {PATH_TYPE, DEFAULT_TYPE, FLOOR_TYPE, WALL_TYPE, START_TYPE, GOAL_TYPE} from '../../../../Utility/Colors';
5+
6+
7+
8+
9+
export function BfsCreation(board, start, end) {
10+
_BoardReset(board);
11+
const startCell = start || board[Math.floor(Math.random() * board.length)];
12+
let endCell = end || board[Math.floor(Math.random() * board.length)];
13+
startCell.type = START_TYPE;
14+
endCell.type = GOAL_TYPE;
15+
console.log('Start: ' + startCell.id + ' (' + startCell.x + ' | ' + startCell.y + ')');
16+
console.log('End: ' + endCell.id + ' (' + endCell.x + ' | ' + endCell.y + ')');
17+
18+
let queue = [];
19+
let visited = [];
20+
let path = [];
21+
let current = startCell;
22+
23+
queue.push(current);
24+
visited.push(current);
25+
while (queue.length > 0) {
26+
current = queue.shift();
27+
console.log('Current: ' + current.id + ' (' + current.x + ' | ' + current.y + ')');
28+
if (current === endCell) {
29+
break;
30+
}
31+
if (current.type !== START_TYPE) {
32+
current.type = FLOOR_TYPE;
33+
}
34+
current.visited = true;
35+
let neighbors = _GetNeighbors(board, current);
36+
console.log('Neighbors: ' + neighbors.length);
37+
for (let i = 0; i < neighbors.length; i++) {
38+
let neighbor = neighbors[i];
39+
if (!neighbor.visited) {
40+
neighbor.parent = current;
41+
visited.push(neighbor);
42+
queue.push(neighbor);
43+
}
44+
}
45+
}
46+
47+
_SetWalls(board);
48+
49+
50+
}

‎src/components/Algorithms/Maze/Generation/BinaryTreeCreation.js‎

Lines changed: 23 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,36 @@
1-
import {directions} from '../Directions';
2-
import {_FindCellVisitState, _FindCellTypeState, _FindCell, _BoardReset, _GetNeighbors} from '../Tools';
3-
import exit from 'exit';
1+
import {directions} from '../Directions';
2+
import {_FindCellVisitState, _FindCellTypeState, _FindCell, _BoardReset, _GetNeighbors, _SetWalls} from '../Tools';
3+
import exit from 'exit';
44
import {PATH_TYPE, DEFAULT_TYPE, FLOOR_TYPE, WALL_TYPE, START_TYPE, GOAL_TYPE} from '../../../../Utility/Colors';
55

66

77

88

9-
export function BinaryTreeCreation(board) {
9+
export function BinaryTreeCreation(board, start, end) {
1010
_BoardReset(board);
11+
let startCell = null;
12+
let endCell = null;
13+
if (start === undefined || start === null) {
14+
startCell = board[Math.floor(Math.random() * board.length)];
15+
}
16+
if (end === undefined || end === null) {
17+
endCell = board[Math.floor(Math.random() * board.length)];
18+
}
19+
startCell.type = START_TYPE;
20+
endCell.type = GOAL_TYPE;
21+
console.log('Start: ' + startCell.id + " (" + startCell.x + ' | ' + startCell.y + ')');
22+
console.log('End: ' + endCell.id + " (" + endCell.x + ' | ' + endCell.y + ')');
23+
1124
const numPoints = board.length;
12-
const numCols = Math.ceil(Math.sqrt(numPoints));
13-
const prev = null;
1425
for (var i = 0; i < numPoints; i++) {
26+
if (board[i] === startCell || board[i] === endCell) {
27+
continue;
28+
}
1529
let node = board[i];
1630
// Needed to be percise to avoid floating point errors....
1731
let direction = Math.floor(Math.random() * 4);
18-
// console.log(node);
19-
// console.log(direction);
20-
// console.log(directions[direction].x);
21-
// console.log(board[i].x + directions[direction].x);
2232
let xcord = node.x + directions[direction].x;
2333
let ycord = node.y + directions[direction].y;
24-
// console.log(xcord, ycord);
25-
// console.log(node.x + directions[direction].x, node.y + directions[direction].y);
2634
const cell = _FindCell(board, xcord, ycord);
2735
// console.log(cell);
2836
// exit();
@@ -39,21 +47,16 @@ export function BinaryTreeCreation(board) {
3947
// return;
4048

4149

42-
if (!cell.visited) {
50+
if (!cell.visited && cell.type !== START_TYPE && cell.type !== GOAL_TYPE) {
4351
// console.log(cell);
4452
cell.visited = true;
45-
cell.type = '_floor_';
53+
cell.type = FLOOR_TYPE;
4654
}
4755
}
4856
}
4957

50-
for (var x = 0; x < numPoints; x++) {
51-
let node = board[x];
58+
_SetWalls(board);
5259

53-
if (!node.visited) {
54-
node.type = '_wall_';
55-
}
56-
}
5760

5861
}
5962

‎src/components/Algorithms/Maze/Generation/BreathFirstSearchCreation.js‎

Whitespace-only changes.

‎src/components/Algorithms/Maze/Generation/Directions 2.js‎

Lines changed: 0 additions & 7 deletions
This file was deleted.

‎src/components/Algorithms/Maze/Generation/GrowingTree.js‎

Lines changed: 0 additions & 13 deletions
This file was deleted.

‎src/components/Algorithms/Maze/Generation/GrowingTreeCreation.js‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
import {directions} from '../Directions';
2+
import {_FindCellVisitState, _FindCellTypeState, _FindCell, _BoardReset, _GetNeighbors, _SetWalls} from '../Tools';
3+
import exit from 'exit';
4+
import {PATH_TYPE, DEFAULT_TYPE, FLOOR_TYPE, WALL_TYPE, START_TYPE, GOAL_TYPE} from '../../../../Utility/Colors';
5+
import {PriorityQueue} from '../../../../Utility/PriorityQueue';
6+
7+
8+
9+
10+
export function GrowingTreeCreation(board, start, end) {
11+
_BoardReset(board);
12+
let startCell = null;
13+
let endCell = null;
14+
if (start === undefined || start === null) {
15+
startCell = board[Math.floor(Math.random() * board.length)];
16+
}
17+
if (end === undefined || end === null) {
18+
endCell = board[Math.floor(Math.random() * board.length)];
19+
}
20+
startCell.type = START_TYPE;
21+
endCell.type = GOAL_TYPE;
22+
console.log('Start: ' + startCell.id + ' (' + startCell.x + ' | ' + startCell.y + ')');
23+
console.log('End: ' + endCell.id + ' (' + endCell.x + ' | ' + endCell.y + ')');
24+
25+
26+
const visited = new PriorityQueue();
27+
const queue = new PriorityQueue();
28+
29+
while (queue.length > 0) {
30+
const cell = queue.dequeue();
31+
if (cell.type === GOAL_TYPE) {
32+
break;
33+
}
34+
if (cell.type !== START_TYPE) {
35+
cell.type = FLOOR_TYPE;
36+
}
37+
cell.visited = true;
38+
visited.enqueue(cell);
39+
40+
41+
const neighbors = _GetNeighbors(board, cell);
42+
for (let i = 0; i < neighbors.length; i++) {
43+
const neighbor = neighbors[i];
44+
if (visited.has(neighbor) === false) {
45+
// neighbor.type = FLOOR_TYPE;
46+
queue.enqueue(neighbor);
47+
}
48+
}
49+
}
50+
51+
_SetWalls(board);
52+
53+
}

‎src/components/Algorithms/Maze/Generation/RecursiveBacktrackCreation.js‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
import {directions} from '../Directions';
2+
import {_FindCellVisitState, _FindCellTypeState, _FindCell, _BoardReset, _GetNeighbors, _SetWalls} from '../Tools';
3+
import exit from 'exit';
4+
import {PATH_TYPE, DEFAULT_TYPE, FLOOR_TYPE, WALL_TYPE, START_TYPE, GOAL_TYPE} from '../../../../Utility/Colors';
5+
import {PriorityQueue} from '../../../../Utility/PriorityQueue.js';
6+
7+
8+
9+
10+
export function RecursiveBacktrackCreation(board, start, end) {
11+
_BoardReset(board);
12+
let startCell = null;
13+
let endCell = null;
14+
if (start === undefined || start === null) {
15+
startCell = board[Math.floor(Math.random() * board.length)];
16+
}
17+
if (end === undefined || end === null) {
18+
endCell = board[Math.floor(Math.random() * board.length)];
19+
}
20+
startCell.type = START_TYPE;
21+
endCell.type = GOAL_TYPE;
22+
console.log('Start: ' + startCell.id + ' (' + startCell.x + ' | ' + startCell.y + ')');
23+
console.log('End: ' + endCell.id + ' (' + endCell.x + ' | ' + endCell.y + ')');
24+
25+
const stack = new PriorityQueue();
26+
startCell.visited = true;
27+
stack.enqueue(startCell);
28+
while (stack.length > 0) {
29+
let currentCell = stack.dequeue();
30+
if (currentCell.type === GOAL_TYPE) {
31+
stack.clear();
32+
break;
33+
}
34+
if (currentCell.type !== START_TYPE) {
35+
currentCell.type = FLOOR_TYPE;
36+
}
37+
currentCell.visited = true;
38+
let neighbors = _GetNeighbors(board, currentCell);
39+
for (let i = 0; i < neighbors.length; i++) {
40+
let neighbor = neighbors[i];
41+
if (neighbor.visited === false) {
42+
stack.enqueue(neighbor);
43+
}
44+
}
45+
}
46+
47+
_SetWalls(board);
48+
49+
50+
}
51+

0 commit comments

Comments
 (0)