Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function getCommands(field, power) {
- var myField = new Field(field);
- var robby = new Robot(myField.startPoint, power, Directions.NORTH, []);
- myField.prettyPrint();
- var winnerRobots = [];
- var explored = new PathSet();
- var frontier = new PathSet();
- // initial frontier value
- frontier.add(robby.getState(), robby);
- while(frontier.states.length) {
- var fs = frontier.states.shift();
- consume(fs);
- }
- function consume(fs) { // fs for frontier state
- // 1 transfer to explored
- explored.add(fs.state, fs.robot);
- // 2 check solution
- if(fs.state.isPointEqual(myField.targetPoint)) {
- winnerRobots.push(fs.robot);
- return;
- }
- // 3 check power level
- if(fs.robot.power === 0) {
- return;
- }
- // 4 discover options, add to frontier if new
- var options = fs.robot.discoverOptions(myField);
- options.forEach(function(opt) {
- var resultState = fs.robot.predictState(opt, myField);
- if(!frontier.exists(resultState) && !explored.exists(resultState)) {
- var roboSpawn = fs.robot.clone();
- roboSpawn.executeCommand(opt, myField);
- frontier.add(resultState, roboSpawn);
- }
- });
- }
- console.log('The winners are:');
- console.log(winnerRobots);
- if(!winnerRobots.length) {
- return [];
- }
- return winnerRobots.sort((r1, r2) => r2.power - r1.power)[0].commandLog;
- }
- var Commands = {
- "TURN_RIGHT": "r", // turn right by 90°
- "TURN_LEFT": "l", // turn left by 90°
- "MOVE_FORWARDS": "f" // move one field forwards into current direction
- };
- var Fields = {
- "WALKABLE": ".", // Robby may walk on this
- "BLOCKED": "#", // Robby must not walk on this
- "START": "S", // Robby is starting here, he may also walk here
- "TARGET": "T" // The target cell, Robby has to reach
- };
- var Directions = {
- "NORTH": 0,
- "EAST": 1,
- "SOUTH": 2,
- "WEST": 3
- }
- function State(x, y, d) {
- this.x = x;
- this.y = y;
- this.d = d;
- }
- State.prototype = {
- isEqual: function(otherState) {
- return this.x === otherState.x && this.y === otherState.y && this.d === otherState.d;
- },
- isPointEqual: function(point) {
- return this.x === point.x && this.y === point.y;
- }
- }
- function PathSet(states) {
- this.states = states || [];
- }
- PathSet.prototype = {
- add: function(state, robot) {
- if(!this.exists(state)) {
- this.states.push({state: state, robot: robot});
- }
- },
- exists: function(state) {
- return this.states.filter((s) => {
- return state.isEqual(s.state);
- }).length;
- }
- }
- function Field(field) {
- this.size = Math.sqrt(field.length);
- this.square = [];
- for(var i = 0; i < this.size; i++) {
- this.square.push([]);
- for(var j = 0; j < this.size; j++) {
- this.square[i][j] = field[this.size * i + j];
- if(this.square[i][j] === Fields.START) {
- this.startPoint = { x: i, y: j }
- }
- if(this.square[i][j] === Fields.TARGET) {
- this.targetPoint = { x: i, y: j }
- }
- }
- }
- }
- Field.prototype = {
- prettyPrint: function() {
- console.log('\n');
- for(var i = 0; i < this.size; i++) {
- console.log(this.square[i].join(' '));
- console.log('\n');
- }
- console.log('\n');
- }
- }
- function Robot(startPoint, power, direction, commandLog) {
- this.x = startPoint.x;
- this.y = startPoint.y;
- this.power = power;
- this.direction = direction;
- this.commandLog = [...commandLog];
- }
- Robot.prototype = {
- turnRight: function() {
- this.direction++;
- if(this.direction > Directions.WEST) {
- this.direction = Directions.NORTH;
- }
- this.power--;
- this.commandLog.push(Commands.TURN_RIGHT);
- },
- turnLeft: function() {
- this.direction--;
- if(this.direction < Directions.NORTH) {
- this.direction = Directions.WEST;
- }
- this.power--;
- this.commandLog.push(Commands.TURN_LEFT);
- },
- moveForward: function(field) {
- if(this.canWalk(field)) {
- var np = this.getNextPoint(field);
- this.x = np.x;
- this.y = np.y;
- this.power--;
- this.commandLog.push(Commands.MOVE_FORWARDS);
- }
- },
- canWalk: function(field) {
- var np = this.getNextPoint();
- var outOfSquare = np.x < 0 || np.y < 0 || np.x >= field.size || np.y>= field.size;
- if(outOfSquare) {
- return false;
- }
- var isBlocked = (field.square[np.x][np.y] === Fields.BLOCKED);
- return !isBlocked;
- },
- getNextPoint: function() {
- var p = {};
- if(this.direction === Directions.NORTH) {
- p.x = this.x - 1;
- p.y = this.y;
- }
- else if(this.direction === Directions.EAST) {
- p.x = this.x;
- p.y = this.y + 1;
- }
- else if(this.direction === Directions.SOUTH) {
- p.x = this.x + 1;
- p.y = this.y;
- }
- else if(this.direction === Directions.WEST) {
- p.x = this.x;
- p.y = this.y - 1;
- }
- return p;
- },
- getState: function() {
- return new State(this.x, this.y, this.direction);
- },
- discoverOptions: function(field) {
- var options = [Commands.TURN_LEFT, Commands.TURN_RIGHT];
- if(this.canWalk(field)) {
- options.unshift(Commands.MOVE_FORWARDS);
- }
- return options;
- },
- predictState: function(command, field) {
- var clone = this.clone();
- if(command === Commands.TURN_LEFT) {
- clone.turnLeft();
- }
- else if(command === Commands.TURN_RIGHT) {
- clone.turnRight();
- }
- else if(command === Commands.MOVE_FORWARDS) {
- clone.moveForward(field);
- }
- return clone.getState();
- },
- executeCommand: function(command, field) {
- if(command === Commands.TURN_LEFT) {
- this.turnLeft();
- }
- else if(command === Commands.TURN_RIGHT) {
- this.turnRight();
- }
- else if(command === Commands.MOVE_FORWARDS) {
- this.moveForward(field);
- }
- },
- clone: function() {
- return new Robot({ x: this.x, y: this.y }, this.power, this.direction, this.commandLog);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement