Horse trying to find path

Question

I'm trying to get good at JavaScript and I wrote this code in order to make mistakes and learn better ways to do it. It's a silly UTF-8 horse trying to find its way towards the flag. You can check it here.

• It can only see the surrounding squares
• It remembers where it has been
• It knows how far away each square is from the flag

script.js

var makeApp = function () {
  // settings
  var MAX_WIDTH = 64;
  var MAX_HEIGHT = 32;
  var BLOCK_PROBABILITY = 0.45;
  var REVISIT_PENALTY_MULTIPLIER = Math.floor(MAX_WIDTH / 20);
  var LEEWAY_MULTIPLIER = 3;
  var BASE_LEEWAY = 1.5;
  var SUMMED_LEEWAY_BASE = 1;
  var TIMEOUT = 200;

  // types
  var Point = {
    x : 0,
    y : 0,
    price : 0,
    summedPrice : 0,
    priced : false,
    blocked : false,
    visits : 0,
    node : null // DOM node
  };

  // data
  var w = Math.floor(Math.random() * (MAX_WIDTH - 2)) + 2;
  var h = Math.floor(Math.random() * (MAX_HEIGHT - 2)) + 2;
  var goal = makeRandPoint();
  var start = makeRandPoint();
  var grid = [];

  // internal methods
  function init(node) {    
    while (goal.x === start.x && goal.y === start.y) {
      goal = makeRandPoint();
    }

    createGrid(node);
  }

  function getPoint(x,y) {
    return grid[y * w + x];
  }

  function makeRandPoint() {
    var p = Object.create(Point);
    p.x = Math.floor(Math.random() * w);
    p.y = Math.floor(Math.random() * h);

    return p;
  }

  function approxDistance(p0, p1) {
    var xd = Math.abs(p1.x - p0.x);
    var yd = Math.abs(p1.y - p0.y);

    // the greater distance can absorb the smaller by making a diagonal
    var d = Math.max(xd, yd);

    // allow the horse to consider more paths,
    // the farther away, the greater the leeway
    var div = BASE_LEEWAY + LEEWAY_MULTIPLIER * (d / Math.max(w, h));

    return Math.floor(d / div);
  };

  function realDistance(p0, p1) {
    var xd = Math.abs(p1.x - p0.x);
    var yd = Math.abs(p1.y - p0.y);
    return Math.max(xd, yd);
  }

  // without this, the horse will tend to move diagonally
  function summedDistance(p0, p1) {
    var d = Math.abs(p1.x - p0.x) + Math.abs(p1.y - p0.y);
    var div = SUMMED_LEEWAY_BASE + d / Math.max(w, h);

    return Math.floor(d / div);
  }

  function createGrid(node) {
    var table = document.createElement('table');
    var tr;
    var td;
    var y;
    var x;
    var p;

    for (y = 0; y < h; ++y) {
      tr = document.createElement('tr');

      for (x = 0; x < w; ++x) { 
        td = document.createElement('td');

        p = Object.create(Point);
        p.x = x;
        p.y = y;
        p.blocked = Math.random() <= BLOCK_PROBABILITY;
        p.node = td;
        grid.push(p);      

        if (y === goal.y && x === goal.x) {
          td.className = 'goal';
          td.innerText = '⚑';
          p.blocked = false;
        } else if(y === start.y && x === start.x) {
          td.className = 'start';
          td.innerText = '♞'
          p.blocked = false;
          p.price = approxDistance(start, goal);
          p.priced = true;
        } else if (p.blocked) {
          td.className = 'blocked';
        }

        tr.appendChild(td);
      }

      table.appendChild(tr);
    }

    node.appendChild(table);
  }

  function alivenHorse () {
    var p = getPoint(start.x, start.y); // current position

    function forEveryNeighbor(pos, f) {
      var x0 = pos.x - 1;
      var x1 = pos.x + 1;
      var y0 = pos.y - 1;
      var y1 = pos.y + 1;
      var x;
      var y;

      if (x0 === -1) {
        x0 = 0;
      }

      if (x1 === w) {
        x1 = w - 1;
      }

      if (y0 === -1) {
        y0 = 0;
      }

      if (y1 === h) {
        y1 = h - 1;
      }

      for (y = y0; y <= y1; ++y) {
        for (x = x0; x <= x1; ++x) {
          // skip current node
          if (y === pos.y && x === pos.x) {
            continue;
          }

          f(getPoint(x, y), x, y);
        }
      }
    }

    function step() {
      var bestNeighbor = Object.create(Point);
      bestNeighbor.price = Number.MAX_VALUE;

      // price neighbors
      forEveryNeighbor(p, function (np, x, y) {
        var price;
        var realPrice;

        if (np.blocked) {
          return;
        }

        if (!np.priced) {
          np.price = approxDistance(np, goal);
          np.summedPrice = summedDistance(np, goal);
          np.realPrice = realDistance(np, goal);
          np.priced = true;
          np.node.innerText = np.price;
        }

        if (np.price < bestNeighbor.price) {
          bestNeighbor = np;
        } else if (np.price === bestNeighbor.price) {
          if (np.summedPrice < bestNeighbor.summedPrice) {
            bestNeighbor = np;
          } else if (np.summedPrice === bestNeighbor.summedPrice) {
            if (np.realPrice < bestNeighbor.realPrice) {
              bestNeighbor = np;
            }
          }
        }
      });

      // revisited nodes should be assigned a higher-price to avoid dead-ends
      bestNeighbor.price += REVISIT_PENALTY_MULTIPLIER * bestNeighbor.visits;
      bestNeighbor.visits++;

      p.node.innerText = p.price;
      p = bestNeighbor;
      p.node.innerText = '♞';

      if (p.y !== goal.y || p.x !== goal.x) {
        setTimeout(step, TIMEOUT);
      }
    }

    setTimeout(step, TIMEOUT);
  };

  function run(node) {
    init(node);
    alivenHorse();
  }

  // expose public interface
  return {
    run : run,
  };
};

// spawn and let it run
makeApp().run(document.body);

Answer 1

ES6, ES7 and general style review

This review will focus on language use and general style.

Looking at the code it is well written, and works (always a plus). Though I have not looked in detail at the logic of the solution, whether it is optimal in terms of memory and cpu usage I will leave to someone else to maybe expand upon.

As pointed out in your question's comments by jonah, the rendering would best be suited to a separate module, I do not think in this case that is all that important as it is clearly an experiment and not designed as a general path finding solution (e.g. here is a maze, find a path.)

Modern JavaScript.

The most obvious issue with the code is that it uses the older JavaScript language specification (with the exception of const). Though this is not a reason to say the code is bad, but if you are doing this as a learning experience you are better of using the latest and greatest.

Latest versions of JavaScript ES6 and ES7 (links are to compatibility table) provide many useful syntax shortcuts that can take a bit of getting used to, as well as a lot of new functionality.

As example the spread operator.

ECMAScript (stage 3) Spread operator

You use Object.create(point) to create copies of the point object. The point object is just a simple object that you have not assigned a prototype. ES7 provides a simplier method of assigning an object properties from another. The spread operator and object shorthand constructor syntax

const copyOfPoint = {...point}; // use the spread operator 

// or to overwrite defaults, with shorthand properties, and standard property assignment.
function myFunction(x, y, node) {
    const copyOfPoint = {...point, x, y, node, blocked : Math.random() <= BLOCK_PROBABILITY }; 

General style issues.

These are not must do rules, they are just guidelines to think about as you code.

• Use strict mode. Javascript has a directive that puts the engine context into a stricter mode. It will throw errors where normal mode will not. This is very useful when learning javascript and will help you avoid many common mistakes.

---

• Use const for variables that do not change. Within the code there are many variables defined that do not change and should be constants.

• Settings. You have defined some setting constants at the top, but have neglected others, such as CSS class names and strings for display. Personally I define a const object and store settings as properties of that object. This helps organise the constants and lets code complete editors help you find them, and lets you pass settings to the function as a single object.

const MAX_WIDTH = 64;
const settings = {
    solver : {
        blockProbability : 0.45,
        revisitPenaltyMultiplier : MAX_WIDTH / 20 | 0,
        leewayMultiplier : 3,
        baseLeeway : 1.5,
        summedLeewayBase : 1,          
    },
    display : {
        goal : "⚑",
        horse : "♞",
        maxWidth : MAX_WIDTH,
        maxHeight : 32,
        updateRate : 200, // maybe this could be elsewhere
    },
    classNames : {
        goal : "goal",
        player : "start",
        blocked : "blocked",
    },
}

Though this does highlight a problem with this method of defining settings, you can not access the settings when defining them. EG MAX_WIDTH

---

• For integers in the range -(2**31) <= int <= (2**31-1) you can use the bitwise operator | OR to floor a value eg MAX_WIDTH / 20 | 0 rather than Math.floor(MAX_WIDTH / 20 | 0). It shortens the syntax and is a little quicker.

_{Note: ** is ES7 exponentiation operator 2**31 is same as Math.pow(2,31)}

---

• Use functions to define repeating code, and use them.

You have

function realDistance(p0, p1) {       
  var xd = Math.abs(p1.x - p0.x);
  var yd = Math.abs(p1.y - p0.y);         
  return Math.max(xd, yd);    
}

But also do the very same calculation but don't call the function you defined to do it. Good code is compact and non repeating.

---

• Pre calculate values rather than calculate a value that is the same each time.

You had Math.max(w, h) repeated several times in code and called many times. This is a constant so should be defined at creation. Maybe const maxDim = Math.max(w, h);

---

• Combine var declarations into a single line at the top of the function without defining them. Only define 'var' if they need to change.

You had

var table = document.createElement('table'); // does not change
var tr;  // local to the first loop and does not change in that scope
var td;  // local an const to the inner loop.
var y;
var x;
var p;

is better as

var y, x, p;
const table = document.createElement('table');
for (y = 0; y < h; y++) {
    const tr = document.createElement('tr');
    for (x = 0; x < w; x++) {
        const td = document.createElement('td');

There is also the school of thought that requires variable declaration to be within the closest possible scope (an unfortunate hang on from the old days of C where scope also implied CPU register usage)

var p;
const table = document.createElement('table');
for (let y = 0; y < h; y++) {
    const tr = document.createElement('tr');
    for (let x = 0; x < w; x++) {
        const td = document.createElement('td');

The reason I don't like this syntax is somewhat complicated, but there are performance and memory issues to do with function closure that using let introduces. I would recommend that you learn all about closure befor you start using block scope variables within loops.

---

• Use HTMLElement.textContent rather than HTMLElement.innerText. Changes to textContent do not force a reflow while innerText does. Though in this case not a major issue it is good to know.

---

• continue and break should be avoided if possible (and this is almost always possible, with the exception of switch statements)

You had

if (y === pos.y && x === pos.x) {
    continue;
}
f(getPoint(x, y), x, y);

Better as

if (y !== pos.y || x !== pos.x) {
    f(getPoint(x, y), x, y);
}

---

• Use the ternary operator to assign to constants, rather than having to define variables.

you had

var x0 = pos.x - 1;
var x1 = pos.x + 1;
...
if (x0 === -1) {
   x0 = 0;
}

if (x1 === w) {
   x1 = w - 1;
}

Better as

const x0 = pos.x === 0 ? 0 : pos.x - 1;
const x1 = pos.x === w - 1 ? w - 1 : pos.x + 1; 

---

• Use function declarations rather than anonymous function expressions.It makes debugging easier as function declarations provide a named stack trace and it makes the code easier to read and thus less prone to bugs.

  The example in your code is in the function step where you provide the callback as an anonymous function expression. forEveryNeighbor(p, function (np, x, y) { would be better as function testStep(np, x, y) {...} defined above the call forEveryNeighbor(p, testStep) and also gives more meaning to what the callback does as in the function forEveryNeighbor you simply call it f

---

• Clean up during development. While you are creating code you can be testing logic and trying out layouts. In this process you may create variables that in the end are not used. Be sure to remove all redundant code when you make changes.

  You had declared price and realPrice within a function yet not used them.

---

• JS6 introduced template strings (AKA Template literals) that use back quotes to delimit. This gives JavaScript 3 ways of delimiting strings. Template strings behave very differently from standard string literals. This can throw errors only during execution and thus be a source of latent bugs. This is good reason to use double "quotes" rather than 'apostrophes' (single quotes) when delimiting string literal so that you can more easily see the difference and avoid problems when mixing string types.