xxxxxxxxxx
173
let n = 50;
let grid;
let start = [5,7];
let target = [n-3,n-8];
let path;
let R = []; // Should be implemented as a min heap
let finish = false;
let play = false;
let walls = [];
function h(i1, i2) {
let j1 = target[0];
let j2 = target[1];
return sqrt((i1-j1)*(i1-j1) + (i2-j2)*(i2-j2));
}
function get_adj(u){
let i = u[0];
let j = u[1];
let a = [];
// 4 corners
if(i == 0 && j == 0) {
a = [[0,1],[1,0],[1,1]];
}
else if(i == n-1 && j == n-1) {
a = [[n-2, n-1],[n-1,n-2],[n-2,n-2]];
}
else if(i == 0 && j == n-1) {
a = [[0, n-2],[1,n-2],[1, n-1]];
}
else if(i == n-1 && j == 0) {
a = [[n-1,1],[n-2,1],[n-2,0]];
}
// Up Edge
else if(i == 0) {
a = [[0, j-1],[1,j-1],[1,j],[1,j+1],[0,j+1]];
}
// Left Edge
else if(j == 0) {
a = [[i-1,0],[i-1,1],[i,1],[i+1,0],[i+1,1]];
}
// Right Edge
else if(j == n-1){
a = [[i-1,n-1],[i-1,n-2],[i,n-2],[i+1,n-2],[i+1,n-1]];
}
// Down Edge
else if(i == n-1){
a = [[n-1,j-1],[n-2,j-1],[n-2,j],[n-2,j+1],[n-1,j+1]];
}
else {
a = [[i-1,j],[i-1,j+1],[i,j+1],[i+1,j+1],[i+1,j],[i+1,j-1],[i,j-1],[i-1,j-1]];
}
let b = a.filter((el) => {
let m = true;
walls.forEach((wall) => {
if(el[0] == wall[0] && el[1] == wall[1]) m = false;
})
return m;
});
return b;
}
function setup() {
createCanvas(800, 800);
grid = new Array(n);
path = new Array(n);
biasedPath = new Array(n);
for(let i = 0; i < n; ++i){
let colGrid = new Array(n);
let colPath = new Array(n);
let colBiased = new Array(n);
for(let j = 0; j < n; ++j) {
colGrid[j] = 0;
colPath[j] = [Infinity, [null, null]];
colBiased[j] = Infinity;
}
grid[i] = colGrid;
path[i] = colPath;
biasedPath[i] = colBiased;
}
let i = start[0];
let j = start[1];
let k = target[0];
let l = target[1];
path[i][j] = [0, [null,null]];
grid[k][l] = 3;
biasedPath[i][j] = h(i, j);
R.push([biasedPath[i][j], [i, j]]);
}
function draw() {
background(220);
show_grid();
show_squares();
if(R != [] && !finish && play) {
R.sort();
let u = R.shift()[1];
if(u[0] == target[0] && u[1] == target[1]) {
finish = true;
}
grid[u[0]][u[1]] = 2;
adj = get_adj(u);
adj.forEach((v) => {
if(path[u[0]][u[1]][0] + 1 < path[v[0]][v[1]][0]){
path[v[0]][v[1]][0] = path[u[0]][u[1]][0] + 1;
path[v[0]][v[1]][1] = u;
biasedPath[v[0]][v[1]] =
path[v[0]][v[1]][0] + h(v[0],v[1]);
R.push([biasedPath[v[0]][v[1]], [v[0], v[1]]]);
grid[v[0]][v[1]] = 1;
}
});
}
else {
// reset
}
}
function show_grid() {
for(let x = 0; x <= width; x += width/n) {
line(x, 0, x, height);
}
for(let y = 0; y <= height; y += height/n){
line(0, y, width, y);
}
}
function show_squares() {
for(let i = 0; i < n; ++i) {
for(let j = 0; j < n; ++j) {
noFill();
if(i == start[0] && j == start[1]) {
fill(255);
}
else if(grid[i][j] == 1) {
fill(0, 100, 0);
}
else if(grid[i][j] == 2) {
fill(100, 0, 0);
}
else if(grid[i][j] == 3) {
fill(0);
}
else if(grid[i][j] == 4) {
fill(255);
}
else if(grid[i][j] == 5) {
fill(80, 0, 80);
}
square(i*(width/n), j*(height/n), width/n);
}
}
}
function mouseDragged() {
let x = floor(mouseX/width*n);
let y = floor(mouseY/height*n);
if ((x < n) && (y < n )) {
if(!walls.includes([x,y])){
walls.push([x,y]);
grid[x][y] = 5;
}
}
}
function keyPressed() {
play = true;
}