jnareb · October 24, 2013 21:29
diff --git a/jsbin.apUqeVA.css b/jsbin.apUqeVA.css
 body {
    background: lightblue;
 }
 canvas {
    background: white;
    margin: 10px;
    padding: 10px;
 }
diff --git a/jsbin.apUqeVA.html b/jsbin.apUqeVA.html
 <!DOCTYPE html>
 <html>
 <head>
 <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>
diff --git a/jsbin.apUqeVA.js b/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: 320 // 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 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 + ""
            };
        }
    }
 }

 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 = [];
            /* nad wezlem */
            if (0 <= i - 1) {
                if (0 <= j - 1) {
                    node.neighbours.push([i - 1, j - 1]);
                }
                node.neighbours.push([i - 1, j]);
                if (j + 1 < board.size.Nj) {
                    node.neighbours.push([i - 1, j + 1]);
                }
            }
            /* przed i za wezlem */
            if (0 <= j - 1) {
                node.neighbours.push([i, j - 1]);
            }
            if (j + 1 < board.size.Nj) {
                node.neighbours.push([i, j + 1]);
            }
            /* pod wezlem */
            if (i + 1 < board.size.Ni) {
                if (0 <= j - 1) {
                    node.neighbours.push([i + 1, j - 1]);
                }
                node.neighbours.push([i + 1, j]);
                if (j + 1 < board.size.Nj) {
                    node.neighbours.push([i + 1, j + 1]);
                }
            }
        }
    }
 }
 /* -------------------------------------------------------- */
 /* znajdowanie najkrotszej sciezki, ilustrowane */
 function BFS(nodes, src, dst) {
    var queue = new Queue();

    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 + '<');

    src.dist = 0;
    queue.enqueue(src);

    while (!queue.isEmpty()) {
        var curr = queue.dequeue();
        var node = nodes[curr.i][curr.j];
        node.visited = true;
      
        printCell(curr.i, curr.j, 'x');
        //alert(curr);

        if (curr === dst) {
            break;
        }

        var len = node.neighbours.length;
        for (idx = 0; idx < len; idx++) {
            var nb = node.neighbours[idx];
            
            if (nodes[nb.i][nb.j].visited) {
              continue;
            }
          
            queue.enqueue({
                i: nb[0],
                j: nb[1],
                prev: [curr.i, curr.j],
                dist: curr.dist++
            });
        }
    }
 }

 drawBoard();
 createNodesForBoard();
 fillNodesNeighbours();

 /*
 var i = 2,
    j = 1;
 drawCell(i, j, 'rgba(0, 100, 0, 0.5)');
 printCell(i, j, '[' + nodes[i][j].name + ']');
 $.each(nodes[i][j].neighbours, function (idx, nb) {
    var ii = nb[0],
        jj = nb[1];
    printCell(ii, jj, nodes[ii][jj].name);
 });
 */

 /*
 drawCell(board.size.Ni - 1, board.size.Nj - 1, 'yellow');
 drawCell(9, 0, 'yellow');
 drawCell(0, 7, 'yellow');
 */
 //alert(board.size.Nj);

 BFS(nodes, {
    i: 0,
    j: 0
 }, {
    i: 2,
    j: 3
 });
	body {
	background: lightblue;
	}
	canvas {
	background: white;
	margin: 10px;
	padding: 10px;
	}
	<!DOCTYPE html>
	<html>
	<head>
	<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>
	/* --------------------------------------------------------- */
	/* 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: 320 // 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 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 + ""
	};
	}
	}
	}

	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 = [];
	/* nad wezlem */
	if (0 <= i - 1) {
	if (0 <= j - 1) {
	node.neighbours.push([i - 1, j - 1]);
	}
	node.neighbours.push([i - 1, j]);
	if (j + 1 < board.size.Nj) {
	node.neighbours.push([i - 1, j + 1]);
	}
	}
	/* przed i za wezlem */
	if (0 <= j - 1) {
	node.neighbours.push([i, j - 1]);
	}
	if (j + 1 < board.size.Nj) {
	node.neighbours.push([i, j + 1]);
	}
	/* pod wezlem */
	if (i + 1 < board.size.Ni) {
	if (0 <= j - 1) {
	node.neighbours.push([i + 1, j - 1]);
	}
	node.neighbours.push([i + 1, j]);
	if (j + 1 < board.size.Nj) {
	node.neighbours.push([i + 1, j + 1]);
	}
	}
	}
	}
	}
	/* -------------------------------------------------------- */
	/* znajdowanie najkrotszej sciezki, ilustrowane */
	function BFS(nodes, src, dst) {
	var queue = new Queue();

	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 + '<');

	src.dist = 0;
	queue.enqueue(src);

	while (!queue.isEmpty()) {
	var curr = queue.dequeue();
	var node = nodes[curr.i][curr.j];
	node.visited = true;

	printCell(curr.i, curr.j, 'x');
	//alert(curr);

	if (curr === dst) {
	break;
	}

	var len = node.neighbours.length;
	for (idx = 0; idx < len; idx++) {
	var nb = node.neighbours[idx];

	if (nodes[nb.i][nb.j].visited) {
	continue;
	}

	queue.enqueue({
	i: nb[0],
	j: nb[1],
	prev: [curr.i, curr.j],
	dist: curr.dist++
	});
	}
	}
	}

	drawBoard();
	createNodesForBoard();
	fillNodesNeighbours();

	/*
	var i = 2,
	j = 1;
	drawCell(i, j, 'rgba(0, 100, 0, 0.5)');
	printCell(i, j, '[' + nodes[i][j].name + ']');
	$.each(nodes[i][j].neighbours, function (idx, nb) {
	var ii = nb[0],
	jj = nb[1];
	printCell(ii, jj, nodes[ii][jj].name);
	});
	*/

	/*
	drawCell(board.size.Ni - 1, board.size.Nj - 1, 'yellow');
	drawCell(9, 0, 'yellow');
	drawCell(0, 7, 'yellow');
	*/
	//alert(board.size.Nj);

	BFS(nodes, {
	i: 0,
	j: 0
	}, {
	i: 2,
	j: 3
	});