Path Planning - Greedy Best First Search

I'm working on a path planning algorithm that will be converted to RobotC. I'm trying to optimize it so that it uses the least amount of memory, as the robot it will be implemented on has supposedly as little as 15k available memory.

It may just be the nature of the algorithm used, but it is apparent that it is making some bad choices when it gets to the middle left part of the grid. Any idea how I might optimize this a bit? Perhaps using a real distance measurement? This is important because the program searching the entire map could result in running out of memory. I understand that this probably can't be completely prevented, but I'd like to mitigate it as much as possible.

Extracted algorithm from code snippet below

setTimeout is for visual feedback / understanding of algorithm.

```
function scanCells() {
if (openCells > 0) {
setTimeout(function() {
if (current == undefined) {
finished();
return;
}
open[current.x][current.y] = false;
$(td[current.x][current.y]).css({ "background-color": '#FFFF00' });

if (current.x == goal.x && current.y == goal.y) {
pathFound = true;
finished();
return;
}

var nodeDistances = {
node1: 1000,
node2 : 1000,
node3 : 1000,
node4 : 1000
};

// Get the best node.
// Search adjacent tiles.
var distance = 1000;

var node = {};
node.x = -1;
node.y = -1;
if (current.x - 1 >= 0 && open[current.x - 1][current.y]) {
node.x = current.x - 1;
node.y = current.y;

distance = genericDistance(current.x - 1, current.y, goal.x, goal.y);
}

if (current.y - 1 >= 0 && open[current.x][current.y - 1] && (genericDistance(current.x, current.y - 1, goa

The pathological hunting in the left region of your test case is an unfortunate consequence of using a naïve greedy algorithm. It really is at least as good locally to move up rather than left, and that's true whether you use Manhattan distances or Euclidean distances. If you want to avoid pathological hunting, try the A* algorithm instead.

There are a few simple local improvements to your code.

• var nodeDistances is never used.

• var distance = 1000 is a magic number. var distance = Number.POSITIVE_INFINITY would be better.

• Instead of a global pathFound flag, pass it as a parameter to finished() callback. You can also take advantage of the fact that finished() returns void. The idiom would be return finished(true) or return finished(false).

• Prefer early returns wherever possible. In scanCells(), if you start with if (openCells






• 10 is a magic number. Prefer open[length] and open[0].length.






• When using path as a stack, use path.push(current = node) and path.pop()`.

StackExchange Code Review Q#36145, answer score: 4