Skip to content

Instantly share code, notes, and snippets.

@jnareb

jnareb/jsbin.apUqeVA.css

Created October 24, 2013 23:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jnareb/7146975 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jnareb/7146975 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
jsbin.apUqeVA.css
body {
background: lightblue;
}
canvas {
background: white;
margin: 10px;
padding: 10px;
}
Raw
jsbin.apUqeVA.html
<!DOCTYPE html>
<html>
<head>
<meta name="description" content="[Znajdowanie najkrotszej sciezki w grafie nieskierowanym niewazonym za pomoca przeszukania wszerz]" />
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.8/jquery.min.js"></script>
<meta charset=utf-8 />
<title>Znajdowanie najkrotszej trasy</title>
</head>
<body>
<canvas id="c" width="401px" height="401px"></canvas>
</body>
</html>
Raw
jsbin.apUqeVA.js
/* --------------------------------------------------------- */
/* Queue - kolejka */
function Queue() {
// private
var queue = [];
// public
this.isEmpty = function () {
return (queue.length === 0);
};
this.enqueue = function (item) {
queue.push(item);
};
this.dequeue = function () {
return queue.shift();
};
}
/* --------------------------------------------------------- */
/* board - siatka */
var board = {
size: {
x: 400, // musi byc mniejsze niz width
y: 400 // musi byc mniejsze niz height
},
cell: {
dx: 40,
dy: 40
}
};
/* graf odpowiadajacy w/w siatce, tablica dwuwymiarowa */
var nodes = [
[]
];
/* poczatkowy i koncowy wezel */
var beginNode, endNode;
var c_canvas = document.getElementById("c");
var context = c_canvas.getContext("2d");
function drawBoard() {
board.size.Ni = 0;
for (var x = 0.5; x < board.size.x + 1.0; x += board.cell.dx) {
context.moveTo(x, 0);
context.lineTo(x, board.size.y);
board.size.Ni++;
}
board.size.Nj = 0;
for (var y = 0.5; y < board.size.y + 1.0; y += board.cell.dy) {
context.moveTo(0, y);
context.lineTo(board.size.x, y);
board.size.Nj++;
}
/* o jedno mniej pol niz krawedzi siatki */
board.size.Ni -= 1;
board.size.Nj -= 1;
context.strokeStyle = 'black';
context.stroke();
}
function getCellRect(i, j) {
return {
x: i * board.cell.dx + 1.0,
y: j * board.cell.dy + 1.0,
w: board.cell.dx - 1.0,
h: board.cell.dy - 1.0
};
}
function drawCell(i, j, color) {
var rect = getCellRect(i, j);
context.fillStyle = color;
context.fillRect(rect.x, rect.y, rect.w, rect.h);
}
function clearCell(i, j) {
var rect = getCellRect(i, j);
context.clearRect(rect.x, rect.y, rect.w, rect.h);
}
function printCell(i, j, text) {
var x = (i + 0.5) * board.cell.dx + 0.5,
y = (j + 0.5) * board.cell.dy + 0.5;
context.font = "15px Times New Roman";
context.fillStyle = "black";
context.textAlign = "center";
context.textBaseline = "middle";
context.fillText(text, x, y);
}
function cellLine(i1, j1, i2, j2, width) {
var x1 = (i1 + 0.5) * board.cell.dx + 0.5,
y1 = (j1 + 0.5) * board.cell.dy + 0.5,
x2 = (i2 + 0.5) * board.cell.dx + 0.5,
y2 = (j2 + 0.5) * board.cell.dy + 0.5;
context.beginPath();
context.moveTo(x1, y1);
context.lineTo(x2, y2);
context.lineWidth = width ? width : 1.0;
context.strokeStyle = 'red';
context.stroke();
}
/* --------------------------------------------------------- */
/* otworzenie listy wezlow, dalej reprezentujacej graf */
function createNodesForBoard() {
nodes = new Array(board.size.Ni);
for (var i = 0; i < board.size.Ni; i++) {
nodes[i] = new Array(board.size.Nj);
for (var j = 0; j < board.size.Nj; j++) {
nodes[i][j] = {
filled: false,
name: "" + i + "," + j + ""
};
}
}
}
/**
* Returns a random integer between min and max
* Using Math.round() will give you a non-uniform distribution!
*/
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
/* tworzenie przeszkod */
function randomizeBarriers(N) {
for (var iter = 0; iter < N; iter++) {
var i = getRandomInt(0, board.size.Ni - 1),
j = getRandomInt(0, board.size.Nj - 1);
if (!nodes[i][j].filled) {
nodes[i][j].filled = true;
drawCell(i, j, 'rgba(40, 40, 40, 0.7)');
}
}
}
/* zakladamy, ze i1, j2 sa w tablicy */
function isBoardNeighbour(i1, j1, i2, j2) {
/* i2, j2 nie wyjchodzi poza tablice */
if (!(0 <= i2 && i2 < board.size.Ni)) {
return false;
}
if (!(0 <= j2 && j2 < board.size.Nj)) {
return false;
}
/* moga byc sasiadami tylko jesli indeksy roznia sie o 1 */
/* zapewnione przez uzyta tablice possible_neighbours */
/*
if (!(Math.abs(i2 - i1) <= 1 && Math.abs(j2 - j1) <= 1)) {
return false;
}
*/
/* wypelnione pola nie moga byc sasiadami (przeszkoda) */
if (nodes[i2][j2].filled) {
return false;
}
return true;
}
function fillNodesNeighbours() {
for (var i = 0; i < board.size.Ni; i++) {
for (var j = 0; j < board.size.Nj; j++) {
var node = nodes[i][j];
node.neighbours = [];
var possible_neighbours = [
/* nad wezlem */
[i - 1, j - 1],
[i - 1, j],
[i - 1, j + 1],
/* przed i za wezlem */
[i, j - 1],
[i, j + 1],
/* pod wezlem */
[i + 1, j - 1],
[i + 1, j],
[i + 1, j + 1]
];
for (var idx = 0; idx < possible_neighbours.length; idx++) {
var ii = possible_neighbours[idx][0],
jj = possible_neighbours[idx][1];
if (isBoardNeighbour(i, j, ii, jj)) {
node.neighbours.push(possible_neighbours[idx]);
}
}
}
}
}
/* -------------------------------------------------------- */
/* znajdowanie najkrotszej sciezki, ilustrowane */
function BFS(nodes, src, dst) {
var queue = new Queue();
var curr, node, found = false;
drawCell(src.i, src.j, 'rgba(200, 0, 0, 0.7)');
drawCell(dst.i, dst.j, 'rgba(0, 0, 200, 0.7)');
//printCell(src.i, src.j, '[' + nodes[src.i][src.j].name + ']');
//printCell(dst.i, dst.j, '>' + nodes[dst.i][dst.j].name + '<');
//cellLine(src.i, src.j, dst.i, dst.j, 3.0);
src.dist = 0;
queue.enqueue(src);
while (!queue.isEmpty()) {
curr = queue.dequeue();
node = nodes[curr.i][curr.j];
node.visited = true;
printCell(curr.i, curr.j, curr.dist.toString());
//alert(curr);
if (curr.i === dst.i && curr.j === dst.j) {
found = true;
break;
}
var len = node.neighbours.length;
for (var idx = 0; idx < len; idx++) {
var nb = node.neighbours[idx];
var nb_node = nodes[nb[0]][nb[1]];
if (nb_node.queued || nb_node.visited) {
continue;
}
drawCell(nb[0], nb[1], 'rgba(0, 180, 0, 0.3)');
cellLine(nb[0], nb[1], curr.i, curr.j);
nb_node.queued = true;
nb_node.prev = {
i: curr.i,
j: curr.j
};
nb_node.dist = curr.dist + 1;
queue.enqueue({
i: nb[0],
j: nb[1],
prev: [curr.i, curr.j],
dist: curr.dist + 1
});
}
}
if (!found) {
return;
}
curr = dst;
node = nodes[dst.i][dst.j];
while (node.prev) {
cellLine(curr.i, curr.j, node.prev.i, node.prev.j, 3.0);
printCell(curr.i, curr.j, node.dist.toString());
curr = node.prev;
node = nodes[curr.i][curr.j];
}
}
/* rysowanie tablicy znajduje jej rozmiar */
drawBoard();
var src = {
i: 0,
j: 0
}, dst = {
i: board.size.Ni - 1,
j: board.size.Nj - 1
};
/* te cztery funkcje musza byc wykonane w podanej kolejnosci */
createNodesForBoard();
randomizeBarriers(50);
/* element poczatkowy i koncowy musza miec sasiadow */
nodes[src.i][src.j].filled = false;
nodes[dst.i][dst.j].filled = false;
fillNodesNeighbours();
clearCell(src.i, src.j);
clearCell(dst.i, dst.j);
BFS(nodes, src, dst);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment