alisdair/roku.html

## roku.html
<html>
<head>
  <meta name="viewport" content="user-scalable=no, width=device-width, initial-scale=1.0, maximum-scale=1.0"/>
  <meta name="apple-mobile-web-app-capable" content="yes" />
  <meta name="apple-mobile-web-app-status-bar-style" content="white" />
  <meta name="apple-touch-fullscreen" content="yes" />
  <title>roku</title>
  <script src="roku.js" type="text/javascript"></script>
  <style type="text/css">
  html {
    font: 14px "Helvetica Neue", sans-serif;
    margin: 0;
    padding: 0;
    color: white;
    background: #333;
  }
  h1 {
    font: bold 2em "Helvetica Neue", sans-serif;
    margin: 0.25em 0;
  }
  body {
    margin: 0;
    padding: 0;
  }
  canvas {
    background: white;
    margin: 0;
    padding: 0;
    width: 320px;
    height: 460px;
  }
  ul {
      padding: 0;
      margin: 0;
  }
  li {
    display: block;
    border: 3px solid black;
    margin: -3px 0;
    list-style-type: none;
  }
  #container {
    width: 320px;
    text-align: center;
    margin: 0 auto;
  }
  </style>
</head>
<body onload="window.top.scrollTo(0, 1);draw();">
  <div id="container">
    <h1>roku</h1>
    <canvas width="320" height="460" id="canvas"></canvas>
    <div id="logging"><p>Click two tiles to find a route.</p></div>
    <div id="instructions"></div>
  </div>
</body>
</html>

## roku.js
var window;
var canvas;
var ctx;
var xOrigin = 6;
var yOrigin = 20;
var d = 22;
var a = Math.floor(Math.sin(Math.PI / 3) * d);
var b = d / 2;
var highlighted = [];

var tiles = ["grass", "forest", "rock", "hill", "water"];

var colours  = ["#292", "#253", "#770", "#850", "#07a"];

var cost = [1, 3, 3, 10, 5];

var map = [[3, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0],
             [2, 0, 0, 2, 0, 4, 0, 0, 2, 0],
           [3, 0, 0, 0, 1, 4, 0, 0, 2, 0, 0],
             [2, 0, 0, 0, 1, 1, 2, 0, 0, 0],
           [2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2],
             [0, 0, 0, 2, 1, 1, 0, 0, 0, 2],
           [0, 0, 2, 0, 0, 4, 1, 0, 0, 0, 3],
             [0, 2, 0, 0, 4, 0, 2, 0, 0, 2],
           [0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 3]];

function Position(x, y) {
    this.x = x;
    this.y = y;
}

function mapContainsHex(hex) {
    return (map[hex.column] !== undefined && map[hex.column][hex.mapRow] !== undefined);
}

function Hex(column, row) {
    this.column = column;
    this.row = row;
    this.mapRow = row - Math.ceil(column / 2);
}
Hex.prototype.toString = function () {
    return "(" + this.column + "," + this.row + ")";
};
Hex.prototype.equals = function (other) {
    return other.row === this.row && other.column === this.column;
};
Hex.prototype.surrounding = function () {
    var possible = [new Hex(this.column - 1, this.row - 1),
    new Hex(this.column - 1, this.row),
    new Hex(this.column, this.row + 1),
    new Hex(this.column + 1, this.row + 1),
    new Hex(this.column + 1, this.row),
    new Hex(this.column, this.row - 1)];
    return possible.filter(function (hex) {
        return hex.cost() < Infinity;
    });
};
Hex.prototype.distanceTo = function (other) {
    var dX, dY;

    dX = other.row - this.row;
    dY = other.column - this.column;
    return (Math.abs(dX) + Math.abs(dY) + Math.abs(dX - dY)) / 2;
};
Hex.prototype.euclideanDistanceTo = function (other) {
    var dX, dY;

    dX = other.row - this.row;
    dY = other.column - this.column;
    return Math.sqrt(dX * dX + dY * dY + (dX - dY) * (dX - dY));
};
Hex.prototype.cost = function () {
    if (mapContainsHex(this))
    {
        return cost[map[this.column][this.mapRow]];
    }
    else
    {
        return Infinity;
    }
};


function MapHex(column, mapRow) {
    this.column = column;
    this.mapRow = mapRow;
    this.row = mapRow + Math.ceil(column / 2);
}

function getCursorPosition(e)
{
    var x, y;

    if (e.pageX || e.pageY)
    {
        x = e.pageX;
        y = e.pageY;
    }
    else
    {
        x = e.clientX + document.body.scrollLeft +
        document.documentElement.scrollLeft;
        y = e.clientY + document.body.scrollTop +
        document.documentElement.scrollTop;
    }
    x -= canvas.offsetLeft;
    y -= canvas.offsetTop;
    x -= xOrigin;
    y -= yOrigin;

    if (x < 0 || y < 0)
    {
        console.debug("Out of bounds.");
        return undefined;
    }

    return new Position(x, y);
}

function getHexagon(p)
{
    // Diagram to help explain the algorithm:
    //
    //  x=0123456789
    // y   __    __
    // 0  /00\__/21\
    // 1  \__/11\__/
    // 2  /01\__/22\
    // 3  \__/  \__/
    //
    // First, check if the click is in the rectangular portion of the hex grid.
    // In the diagram above, columns 1--2, 4--5, 7--8. Do this by getting a
    // "rough column" value, which splits on the left 3/4 of hexagon columns.
    // Pixel columns 0--3 are hexagon column 0, 4--5 are hex column 1, and so
    // on.
    //
    // Then calculate an x offset from the left of this column. If this is
    // greater than the width of the angle segment, we're in the rectangular
    // portion. Then we can immediately calculate which row we are in, and
    // we're done.
    //
    // If that doesn't work, it gets more complicated.

    var rc, rcx, rr, rry;

    rc = Math.floor(p.x / (d + b));
    rcx = p.x - (rc * (d + b));
    rr = Math.floor((p.y + (a * rc)) / (2 * a));
    rry = (p.y + (a * rc)) - (rr * 2 * a);

    if (rcx > b)
    {
        return new Hex(rc, rr);
    }
    else
    {
        //       __rry=0
        //  1 | /|
        // ___|/3| rry=a
        //    |\ |
        //  2 | \|_rry=2a
        //
        // Above is the intersection of three hexes:
        //
        // 1 is (rc-1, rr-1)
        // 2 is (rc-1, rr)
        // 3 is (rc,rr)
        //
        // For all clicks, 0 <= rry < 2a, and 0 <= rrx <= b.
        //
        // When rry <= a, the choice is between 1 and 3.

        if (rry <= a)
        {
            if ((rcx / (a - rry)) < (b / a))
            {
                return new Hex(rc - 1, rr - 1);
            }
            else
            {
                return new Hex(rc, rr);
            }
        }
        else // (rry > a)
        {
            if ((rcx / (rry - a)) > (b / a))
            {
                return new Hex(rc, rr);
            }
            else
            {
                return new Hex(rc - 1, rr);
            }
        }

        return undefined;
    }
}

function drawHexagon(hex, highlighted)
{
    var x, y, cx, cy, label, metrics, textHeight;

    x = hex.column;
    y = hex.row;
    cx = b + x * (d + b);
    cy = a * (y * 2 - x);

    ctx.save();
    ctx.translate(cx, cy);
    ctx.translate(xOrigin, yOrigin);

    ctx.beginPath();
    ctx.moveTo(0, 0);
    ctx.lineTo(d, 0);
    ctx.lineTo(d + b, a);
    ctx.lineTo(d, 2 * a);
    ctx.lineTo(0, 2 * a);
    ctx.lineTo(0 - b, a);
    ctx.closePath();

    ctx.lineWidth = 4;
    if (highlighted)
    {
        ctx.strokeStyle = "#500";
        ctx.fillStyle   = "#999";
    }
    else
    {
        ctx.strokeStyle = "#000";
        ctx.fillStyle   = colours[map[hex.column][hex.mapRow]];
    }

    ctx.fill();
    ctx.stroke();

    ctx.font = "bold 8px verdana";
    ctx.fillStyle = "#fff";
    label = "(" + x + "," + y + ")";
    metrics = ctx.measureText(label);
    textHeight = ctx.measureText("m").width;
    ctx.fillText(label, b - metrics.width / 2, a + textHeight / 3);

    ctx.restore();
}

function highlightPath(path)
{
    for (var i = 0; i < path.length; i += 1)
    {
        // Highlight
        window.setTimeout(drawHexagon, 50 * i, path[i], true);

        // Clear
        window.setTimeout(drawHexagon, 50 * path.length + 2000, path[i], false);
    }
}

function routeDistance(start, end)
{
    var path, current, candidates, best, bestDist, i, curDist, shortest;

    path = [start];
    while (!path[path.length - 1].equals(end))
    {
        console.debug("Current path: " + path.toString());

        current = path[path.length - 1];

        surrounding = current.surrounding();

        candidates = []
        surrounding.forEach(function (s)
        {
            if (path.every(function (p) { return !p.equals(s); }))
            {
                candidates.push(s);
            }
        });
        if (candidates.length == 0)
        {
            break;
        }

        console.debug("Candidates: " + candidates.toString());
        best = [];
        bestDist = 9999;
        for (i = 0; i < candidates.length; i += 1)
        {
            console.debug("Distance for " + candidates[i].toString() + ": " + candidates[i].distanceTo(end));
            curDist = candidates[i].distanceTo(end);
            if (curDist === bestDist)
            {
                best.push(candidates[i]);
            }
            else if (curDist < bestDist)
            {
                bestDist = curDist;
                best = [candidates[i]];
            }
        }

        console.debug("Found " + best.length + " options");
        shortest = best[0];
        for (i = 0; i < best.length; i += 1)
        {
            console.debug(best[i].toString() + ": " + best[i].euclideanDistanceTo(end));
            if (best[i].euclideanDistanceTo(end) < shortest.euclideanDistanceTo(end))
            {
                shortest = best[i];
            }
        }

        path.push(shortest);
    }
    return path;
}

function routeAStar(start, goal)
{
    var closed = [];
    var open = [];
    var from = {};
    var g = {};
    var h = {};
    var f = {};

    open.push(start);

    g[start] = 0;
    h[start] = start.euclideanDistanceTo(goal);
    f[start] = g[start] + h[start];

    // invariant: each element x of open must have defined f[x], g[x], h[x]
    while (open.length > 0)
    {
        var x = open.reduce(function (a, b) { return (f[b] < f[a]) ? b : a; } );
        if (x.equals(goal))
        {
            return reconstructPath(from, goal);
        }
        open.splice(open.indexOf(x), 1); // remove x from open
        closed.push(x);
        x.surrounding().forEach(function (y)
        {
            var tg;
            var tib;

            if (closed.some(function (z) { return y.equals(z); }))
            {
                return;
            }

            tg = g[x] + y.cost();

            if (!open.some(function (z) { return y.equals(z); }))
            {
                open.push(y);
                tib = true;
            }
            else if (tg < g[y]) // y is in open, so g[y] exists
            {
                tib = true;
            }
            else
            {
                tib = false;
            }

            if (tib)
            {
                from[y] = x;
                g[y] = tg;
                h[y] = y.euclideanDistanceTo(goal);
                f[y] = g[y] + h[y];
            }
        } );
    }
    return [start];
}

function reconstructPath(from, current)
{
    return from[current] ? reconstructPath(from, from[current]).concat(current) : [current];
}

function route(start, end)
{
    var path, i;

    path = [start];
    while (!path[path.length - 1].equals(end))
    {
        i = path[path.length - 1];

        if (i.row < end.row)
        {
            path.push(new Hex(i.column, i.row + 1));
        }
        else if (i.row > end.row)
        {
            path.push(new Hex(i.column, i.row - 1));
        }
        else if (i.column < end.column)
        {
            path.push(new Hex(i.column + 1, i.row));
        }
        else if (i.column > end.column)
        {
            path.push(new Hex(i.column - 1, i.row));
        }
        else
        {
            console.debug(path.toString);
            break;
        }
    }
    return path;
}

function rokuOnClick(e)
{
    var position, hex, end, start, path;

    position = getCursorPosition(e);

    if (position === undefined) {
        return;
    }

    hex = getHexagon(position);

    if (hex !== undefined && mapContainsHex(hex))
    {
        highlighted.push(hex);
        if (highlighted.length >= 2)
        {
            end = highlighted.pop();
            start = highlighted.pop();

            path = routeAStar(start, end);

            logging = document.getElementById('logging');
            pathlog = "<p>Path: " + path.join("&nbsp;-> ") + "</p>\n";
            pathlog += "<p>Tiles: " + path.map(function f(hex) { return tiles[map[hex.column][hex.mapRow]] }).join("&nbsp;-> ") + "</p>\n";
            pathlog += "<p>Path cost: " + path.map(function f(hex) { return cost[map[hex.column][hex.mapRow]] }).reduce(function f(a, b) { return a + b }) + "</p>";
            logging.innerHTML = pathlog;

            highlightPath(path);
        }
        else
        {
            drawHexagon(hex, true);
        }
    }
}

function draw()
{
    var c, r, column, value, i;

    canvas = document.getElementById('canvas');
    ctx = canvas.getContext("2d");

    if (window.devicePixelRatio === 2) {
        canvas.setAttribute('width', 640);
        canvas.setAttribute('height', 920);
        ctx.scale(2, 2);
    }

    canvas.addEventListener("click", rokuOnClick, false);

    for (c = 0; c < map.length; c += 1)
    {
        column = map[c];

        for (r = 0; r < column.length; r += 1)
        {
            value = column[r];
            if (value === undefined)
            {
                continue;
            }

            drawHexagon(new MapHex(c, r));
        }
    }

    instructionsDiv = document.getElementById('instructions');
    instructions = "\n<ul>";
    for (i = 0; i < tiles.length; i++)
    {
        instructions += "<li style=\"background: " + colours[i] + "\">" + tiles[i] + " (path cost " + cost[i] + ")</li>\n";
    }
    instructions += "</ul>";
    instructionsDiv.innerHTML = instructions;
}
	<html>
	<head>
	<meta name="viewport" content="user-scalable=no, width=device-width, initial-scale=1.0, maximum-scale=1.0"/>
	<meta name="apple-mobile-web-app-capable" content="yes" />
	<meta name="apple-mobile-web-app-status-bar-style" content="white" />
	<meta name="apple-touch-fullscreen" content="yes" />
	<title>roku</title>
	<script src="roku.js" type="text/javascript"></script>
	<style type="text/css">
	html {
	font: 14px "Helvetica Neue", sans-serif;
	margin: 0;
	padding: 0;
	color: white;
	background: #333;
	}
	h1 {
	font: bold 2em "Helvetica Neue", sans-serif;
	margin: 0.25em 0;
	}
	body {
	margin: 0;
	padding: 0;
	}
	canvas {
	background: white;
	margin: 0;
	padding: 0;
	width: 320px;
	height: 460px;
	}
	ul {
	padding: 0;
	margin: 0;
	}
	li {
	display: block;
	border: 3px solid black;
	margin: -3px 0;
	list-style-type: none;
	}
	#container {
	width: 320px;
	text-align: center;
	margin: 0 auto;
	}
	</style>
	</head>
	<body onload="window.top.scrollTo(0, 1);draw();">
	<div id="container">
	<h1>roku</h1>
	<canvas width="320" height="460" id="canvas"></canvas>
	<div id="logging"><p>Click two tiles to find a route.</p></div>
	<div id="instructions"></div>
	</div>
	</body>
	</html>
	var window;
	var canvas;
	var ctx;
	var xOrigin = 6;
	var yOrigin = 20;
	var d = 22;
	var a = Math.floor(Math.sin(Math.PI / 3) * d);
	var b = d / 2;
	var highlighted = [];

	var tiles = ["grass", "forest", "rock", "hill", "water"];

	var colours = ["#292", "#253", "#770", "#850", "#07a"];

	var cost = [1, 3, 3, 10, 5];

	var map = [[3, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0],
	[2, 0, 0, 2, 0, 4, 0, 0, 2, 0],
	[3, 0, 0, 0, 1, 4, 0, 0, 2, 0, 0],
	[2, 0, 0, 0, 1, 1, 2, 0, 0, 0],
	[2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2],
	[0, 0, 0, 2, 1, 1, 0, 0, 0, 2],
	[0, 0, 2, 0, 0, 4, 1, 0, 0, 0, 3],
	[0, 2, 0, 0, 4, 0, 2, 0, 0, 2],
	[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 3]];

	function Position(x, y) {
	this.x = x;
	this.y = y;
	}

	function mapContainsHex(hex) {
	return (map[hex.column] !== undefined && map[hex.column][hex.mapRow] !== undefined);
	}

	function Hex(column, row) {
	this.column = column;
	this.row = row;
	this.mapRow = row - Math.ceil(column / 2);
	}
	Hex.prototype.toString = function () {
	return "(" + this.column + "," + this.row + ")";
	};
	Hex.prototype.equals = function (other) {
	return other.row === this.row && other.column === this.column;
	};
	Hex.prototype.surrounding = function () {
	var possible = [new Hex(this.column - 1, this.row - 1),
	new Hex(this.column - 1, this.row),
	new Hex(this.column, this.row + 1),
	new Hex(this.column + 1, this.row + 1),
	new Hex(this.column + 1, this.row),
	new Hex(this.column, this.row - 1)];
	return possible.filter(function (hex) {
	return hex.cost() < Infinity;
	});
	};
	Hex.prototype.distanceTo = function (other) {
	var dX, dY;

	dX = other.row - this.row;
	dY = other.column - this.column;
	return (Math.abs(dX) + Math.abs(dY) + Math.abs(dX - dY)) / 2;
	};
	Hex.prototype.euclideanDistanceTo = function (other) {
	var dX, dY;

	dX = other.row - this.row;
	dY = other.column - this.column;
	return Math.sqrt(dX * dX + dY * dY + (dX - dY) * (dX - dY));
	};
	Hex.prototype.cost = function () {
	if (mapContainsHex(this))
	{
	return cost[map[this.column][this.mapRow]];
	}
	else
	{
	return Infinity;
	}
	};


	function MapHex(column, mapRow) {
	this.column = column;
	this.mapRow = mapRow;
	this.row = mapRow + Math.ceil(column / 2);
	}

	function getCursorPosition(e)
	{
	var x, y;

	if (e.pageX \|\| e.pageY)
	{
	x = e.pageX;
	y = e.pageY;
	}
	else
	{
	x = e.clientX + document.body.scrollLeft +
	document.documentElement.scrollLeft;
	y = e.clientY + document.body.scrollTop +
	document.documentElement.scrollTop;
	}
	x -= canvas.offsetLeft;
	y -= canvas.offsetTop;
	x -= xOrigin;
	y -= yOrigin;

	if (x < 0 \|\| y < 0)
	{
	console.debug("Out of bounds.");
	return undefined;
	}

	return new Position(x, y);
	}

	function getHexagon(p)
	{
	// Diagram to help explain the algorithm:
	//
	// x=0123456789
	// y __ __
	// 0 /00\__/21\
	// 1 \__/11\__/
	// 2 /01\__/22\
	// 3 \__/ \__/
	//
	// First, check if the click is in the rectangular portion of the hex grid.
	// In the diagram above, columns 1--2, 4--5, 7--8. Do this by getting a
	// "rough column" value, which splits on the left 3/4 of hexagon columns.
	// Pixel columns 0--3 are hexagon column 0, 4--5 are hex column 1, and so
	// on.
	//
	// Then calculate an x offset from the left of this column. If this is
	// greater than the width of the angle segment, we're in the rectangular
	// portion. Then we can immediately calculate which row we are in, and
	// we're done.
	//
	// If that doesn't work, it gets more complicated.

	var rc, rcx, rr, rry;

	rc = Math.floor(p.x / (d + b));
	rcx = p.x - (rc * (d + b));
	rr = Math.floor((p.y + (a * rc)) / (2 * a));
	rry = (p.y + (a * rc)) - (rr * 2 * a);

	if (rcx > b)
	{
	return new Hex(rc, rr);
	}
	else
	{
	// __rry=0
	// 1 \| /\|
	// ___\|/3\| rry=a
	// \|\ \|
	// 2 \| \\|_rry=2a
	//
	// Above is the intersection of three hexes:
	//
	// 1 is (rc-1, rr-1)
	// 2 is (rc-1, rr)
	// 3 is (rc,rr)
	//
	// For all clicks, 0 <= rry < 2a, and 0 <= rrx <= b.
	//
	// When rry <= a, the choice is between 1 and 3.

	if (rry <= a)
	{
	if ((rcx / (a - rry)) < (b / a))
	{
	return new Hex(rc - 1, rr - 1);
	}
	else
	{
	return new Hex(rc, rr);
	}
	}
	else // (rry > a)
	{
	if ((rcx / (rry - a)) > (b / a))
	{
	return new Hex(rc, rr);
	}
	else
	{
	return new Hex(rc - 1, rr);
	}
	}

	return undefined;
	}
	}

	function drawHexagon(hex, highlighted)
	{
	var x, y, cx, cy, label, metrics, textHeight;

	x = hex.column;
	y = hex.row;
	cx = b + x * (d + b);
	cy = a * (y * 2 - x);

	ctx.save();
	ctx.translate(cx, cy);
	ctx.translate(xOrigin, yOrigin);

	ctx.beginPath();
	ctx.moveTo(0, 0);
	ctx.lineTo(d, 0);
	ctx.lineTo(d + b, a);
	ctx.lineTo(d, 2 * a);
	ctx.lineTo(0, 2 * a);
	ctx.lineTo(0 - b, a);
	ctx.closePath();

	ctx.lineWidth = 4;
	if (highlighted)
	{
	ctx.strokeStyle = "#500";
	ctx.fillStyle = "#999";
	}
	else
	{
	ctx.strokeStyle = "#000";
	ctx.fillStyle = colours[map[hex.column][hex.mapRow]];
	}

	ctx.fill();
	ctx.stroke();

	ctx.font = "bold 8px verdana";
	ctx.fillStyle = "#fff";
	label = "(" + x + "," + y + ")";
	metrics = ctx.measureText(label);
	textHeight = ctx.measureText("m").width;
	ctx.fillText(label, b - metrics.width / 2, a + textHeight / 3);

	ctx.restore();
	}

	function highlightPath(path)
	{
	for (var i = 0; i < path.length; i += 1)
	{
	// Highlight
	window.setTimeout(drawHexagon, 50 * i, path[i], true);

	// Clear
	window.setTimeout(drawHexagon, 50 * path.length + 2000, path[i], false);
	}
	}

	function routeDistance(start, end)
	{
	var path, current, candidates, best, bestDist, i, curDist, shortest;

	path = [start];
	while (!path[path.length - 1].equals(end))
	{
	console.debug("Current path: " + path.toString());

	current = path[path.length - 1];

	surrounding = current.surrounding();

	candidates = []
	surrounding.forEach(function (s)
	{
	if (path.every(function (p) { return !p.equals(s); }))
	{
	candidates.push(s);
	}
	});
	if (candidates.length == 0)
	{
	break;
	}

	console.debug("Candidates: " + candidates.toString());
	best = [];
	bestDist = 9999;
	for (i = 0; i < candidates.length; i += 1)
	{
	console.debug("Distance for " + candidates[i].toString() + ": " + candidates[i].distanceTo(end));
	curDist = candidates[i].distanceTo(end);
	if (curDist === bestDist)
	{
	best.push(candidates[i]);
	}
	else if (curDist < bestDist)
	{
	bestDist = curDist;
	best = [candidates[i]];
	}
	}

	console.debug("Found " + best.length + " options");
	shortest = best[0];
	for (i = 0; i < best.length; i += 1)
	{
	console.debug(best[i].toString() + ": " + best[i].euclideanDistanceTo(end));
	if (best[i].euclideanDistanceTo(end) < shortest.euclideanDistanceTo(end))
	{
	shortest = best[i];
	}
	}

	path.push(shortest);
	}
	return path;
	}

	function routeAStar(start, goal)
	{
	var closed = [];
	var open = [];
	var from = {};
	var g = {};
	var h = {};
	var f = {};

	open.push(start);

	g[start] = 0;
	h[start] = start.euclideanDistanceTo(goal);
	f[start] = g[start] + h[start];

	// invariant: each element x of open must have defined f[x], g[x], h[x]
	while (open.length > 0)
	{
	var x = open.reduce(function (a, b) { return (f[b] < f[a]) ? b : a; } );
	if (x.equals(goal))
	{
	return reconstructPath(from, goal);
	}
	open.splice(open.indexOf(x), 1); // remove x from open
	closed.push(x);
	x.surrounding().forEach(function (y)
	{
	var tg;
	var tib;

	if (closed.some(function (z) { return y.equals(z); }))
	{
	return;
	}

	tg = g[x] + y.cost();

	if (!open.some(function (z) { return y.equals(z); }))
	{
	open.push(y);
	tib = true;
	}
	else if (tg < g[y]) // y is in open, so g[y] exists
	{
	tib = true;
	}
	else
	{
	tib = false;
	}

	if (tib)
	{
	from[y] = x;
	g[y] = tg;
	h[y] = y.euclideanDistanceTo(goal);
	f[y] = g[y] + h[y];
	}
	} );
	}
	return [start];
	}

	function reconstructPath(from, current)
	{
	return from[current] ? reconstructPath(from, from[current]).concat(current) : [current];
	}

	function route(start, end)
	{
	var path, i;

	path = [start];
	while (!path[path.length - 1].equals(end))
	{
	i = path[path.length - 1];

	if (i.row < end.row)
	{
	path.push(new Hex(i.column, i.row + 1));
	}
	else if (i.row > end.row)
	{
	path.push(new Hex(i.column, i.row - 1));
	}
	else if (i.column < end.column)
	{
	path.push(new Hex(i.column + 1, i.row));
	}
	else if (i.column > end.column)
	{
	path.push(new Hex(i.column - 1, i.row));
	}
	else
	{
	console.debug(path.toString);
	break;
	}
	}
	return path;
	}

	function rokuOnClick(e)
	{
	var position, hex, end, start, path;

	position = getCursorPosition(e);

	if (position === undefined) {
	return;
	}

	hex = getHexagon(position);

	if (hex !== undefined && mapContainsHex(hex))
	{
	highlighted.push(hex);
	if (highlighted.length >= 2)
	{
	end = highlighted.pop();
	start = highlighted.pop();

	path = routeAStar(start, end);

	logging = document.getElementById('logging');
	pathlog = "<p>Path: " + path.join(" -> ") + "</p>\n";
	pathlog += "<p>Tiles: " + path.map(function f(hex) { return tiles[map[hex.column][hex.mapRow]] }).join(" -> ") + "</p>\n";
	pathlog += "<p>Path cost: " + path.map(function f(hex) { return cost[map[hex.column][hex.mapRow]] }).reduce(function f(a, b) { return a + b }) + "</p>";
	logging.innerHTML = pathlog;

	highlightPath(path);
	}
	else
	{
	drawHexagon(hex, true);
	}
	}
	}

	function draw()
	{
	var c, r, column, value, i;

	canvas = document.getElementById('canvas');
	ctx = canvas.getContext("2d");

	if (window.devicePixelRatio === 2) {
	canvas.setAttribute('width', 640);
	canvas.setAttribute('height', 920);
	ctx.scale(2, 2);
	}

	canvas.addEventListener("click", rokuOnClick, false);

	for (c = 0; c < map.length; c += 1)
	{
	column = map[c];

	for (r = 0; r < column.length; r += 1)
	{
	value = column[r];
	if (value === undefined)
	{
	continue;
	}

	drawHexagon(new MapHex(c, r));
	}
	}

	instructionsDiv = document.getElementById('instructions');
	instructions = "\n<ul>";
	for (i = 0; i < tiles.length; i++)
	{
	instructions += "<li style=\"background: " + colours[i] + "\">" + tiles[i] + " (path cost " + cost[i] + ")</li>\n";
	}
	instructions += "</ul>";
	instructionsDiv.innerHTML = instructions;
	}