DFS in action

Solution to level 13 robotMaze in Untrusted: http://alex.nisnevich.com/untrusted/

	/*
	* robotMaze.js
	*
	* The blue key is inside a labyrinth, and extracting
	* it will not be easy.
	*
	* It's a good thing that you're a AI expert, or
	* we would have to leave empty-handed.
	*/
	function startLevel(map) {
	// Hint: you can press R or 5 to "rest" and not move the
	// player, while the robot moves around.
	map.getRandomInt = function(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
	}
	map.placePlayer(map.getWidth()-1, map.getHeight()-1);
	var player = map.getPlayer();
	map.defineObject('robot', {
	'type': 'dynamic',
	'symbol': 'R',
	'color': 'gray',
	'onCollision': function (player, me) {
	me.giveItemTo(player, 'blueKey');
	},
	'behavior': function (me) {
	if (map.path) {
	if (map.path.length > 0) {
	var dir = map.path[map.path.length - 1];
	me.move(dir);
	map.path.pop();
	} else {
	me.move('down');
	}
	} else {
	var parent = new Array(10);
	for (var i = 0; i < 10; i++) {
	parent[i] = new Array(map.getWidth());
	}
	parent[me.getY()][me.getX()] = [[-1, -1], ''];
	var endX = map.getWidth() - 2;
	var endY = 7;
	var dfs = function (x, y) {
	if (x == endX && y == endY)
	return;
	var moves = map.getAdjacentEmptyCells(x, y);
	for (var i = 0; i < moves.length; i++) {
	var nextx = moves[i][0][0];
	var nexty = moves[i][0][1];
	if (!parent[nexty][nextx]) {
	parent[nexty][nextx] = [[x, y], moves[i][1]];
	dfs(nextx, nexty);
	}
	}
	}
	dfs(me.getX(), me.getY());
	var x = endX;
	var y = endY;
	map.path = [];
	while (parent[y][x][1] != '') {
	map.path.push(parent[y][x][1]);
	var xy = parent[y][x][0];
	y = xy[1];
	x = xy[0]
	}
	}
	}
	});
	map.defineObject('barrier', {
	'symbol': '░',
	'color': 'purple',
	'impassable': true,
	'passableFor': ['robot']
	});
	map.placeObject(0, map.getHeight() - 1, 'exit');
	map.placeObject(1, 1, 'robot');
	map.placeObject(map.getWidth() - 2, 8, 'blueKey');
	map.placeObject(map.getWidth() - 2, 9, 'barrier');
	var autoGeneratedMaze = new ROT.Map.DividedMaze(map.getWidth(), 10);
	autoGeneratedMaze.create( function (x, y, mapValue) {
	// don't write maze over robot or barrier
	if ((x == 1 && y == 1) || (x == map.getWidth() - 2 && y >= 8)) {
	return 0;
	} else if (mapValue === 1) { //0 is empty space 1 is wall
	map.placeObject(x,y, 'block');
	} else {
	map.placeObject(x,y,'empty');
	}
	});
	}
	function validateLevel(map) {
	map.validateExactlyXManyObjects(1, 'exit');
	map.validateExactlyXManyObjects(1, 'robot');
	map.validateAtMostXObjects(1, 'blueKey');
	}
	function onExit(map) {
	if (!map.getPlayer().hasItem('blueKey')) {
	map.writeStatus("We need to get that key!");
	return false;
	} else {
	return true;
	}
	}

view raw untrusted-lvl13-solution.js hosted with ❤ by GitHub