ASTAR - Fine Grid Movement.

define(function() {

    var AStar = (function () {

        /**
         * A* (A-Star) algorithm for a path finder
         * @author  Andrea Giammarchi
         * @license Mit Style License
         */

        function diagonalSuccessors($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i) {
            if($N) {
                $E && !grid[N][E] && (result[i++] = {x:E, y:N});
                $W && !grid[N][W] && (result[i++] = {x:W, y:N});
            }
            if($S){
                $E && !grid[S][E] && (result[i++] = {x:E, y:S});
                $W && !grid[S][W] && (result[i++] = {x:W, y:S});
            }
            return result;
        }

        function diagonalSuccessorsFree($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i) {
            $N = N > -1;
            $S = S < rows;
            $E = E < cols;
            $W = W > -1;
            if($E) {
                $N && !grid[N][E] && (result[i++] = {x:E, y:N});
                $S && !grid[S][E] && (result[i++] = {x:E, y:S});
            }
            if($W) {
                $N && !grid[N][W] && (result[i++] = {x:W, y:N});
                $S && !grid[S][W] && (result[i++] = {x:W, y:S});
            }
            return result;
        }

        function nothingToDo($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i) {
            return result;
        }

        function successors(find, x, y, grid, rows, cols){
            var
                N = y - 1,
                S = y + 1,
                E = x + 1,
                W = x - 1,
                $N = N > -1 && !grid[N][x],
                $S = S < rows && !grid[S][x],
                $E = E < cols && !grid[y][E],
                $W = W > -1 && !grid[y][W],
                result = [],
                i = 0
            ;
            $N && (result[i++] = {x:x, y:N});
            $E && (result[i++] = {x:E, y:y});
            $S && (result[i++] = {x:x, y:S});
            $W && (result[i++] = {x:W, y:y});
            return find($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i);
        }

        function successors2(find, x, y, grid, rows, cols){
            var result = [],
                i = 0;

            var
                N = (y % 1 == 0) ? (y - 1) : Math.round(y),
                NL = (y % 1 == 0) ? (y - 1) : Math.floor(y),
                NR = (y % 1 == 0) ? (y - 1) : Math.ceil(y),
                S = (y % 1 == 0) ? (y + 1) : Math.round(y),
                SL = (y % 1 == 0) ? (y + 1) : Math.floor(y),
                SR = (y % 1 == 0) ? (y + 1) : Math.ceil(y),
                $N = NL >= 0 && !grid[NL][Math.floor(x)] && NR >= 0 && !grid[NR][Math.ceil(x)],
                $S = SL <= (rows-1) && !grid[SL][Math.floor(x)] && SR <= (rows-1) && !grid[SR][Math.ceil(x)];

            var
                E = (x % 1 == 0) ? (x + 1) : Math.round(x),
                ET = (x % 1 == 0) ? (x + 1) : Math.floor(x),
                EB = (x % 1 == 0) ? (x + 1) : Math.ceil(x),
                W = (x % 1 == 0) ? (x - 1) : Math.round(x),
                WT = (x % 1 == 0) ? (x - 1) : Math.floor(x),
                WB = (x % 1 == 0) ? (x - 1) : Math.ceil(x),
                $E = ET <= (cols-1) && !grid[Math.floor(y)][ET] && EB <= (cols-1) && !grid[Math.ceil(y)][EB],
                $W = WT >= 0 && !grid[Math.floor(y)][WT] && WB >= 0 && !grid[Math.ceil(y)][WB];

            $N && (result[i++] = {x:Math.floor(x), y:N, rx:x, ry:(y-1)});
            $S && (result[i++] = {x:Math.ceil(x), y:S, rx:x, ry:(y+1)});
            $E && (result[i++] = {x:E, y:Math.ceil(y), rx:(x+1), ry:y});
            $W && (result[i++] = {x:W, y:Math.floor(y), rx:(x-1), ry:y});

            return find($N, $S, $E, $W, N, S, E, W, grid, rows, cols, result, i);
        }

        function diagonal(start, end, f1, f2) {
            return f2(f1(start.x - end.x), f1(start.y - end.y));
        }

        function euclidean(start, end, f1, f2) {
            var
                x = start.x - end.x,
                y = start.y - end.y
            ;
            return f2(x * x + y * y);
        }

        function manhattan(start, end, f1, f2) {
            return f1(start.x - end.x) + f1(start.y - end.y);
        }

        function AStar(grid, start, end, f) {
          return [];
        }

        /*function AStar(grid, start, end, f) {
            var
                cols = grid[0].length,
                rows = grid.length,
                limit = cols * rows,
                f1 = Math.abs,
                f2 = Math.max,
                list = {},
                result = [],
                open = [{x:start[0], y:start[1], f:0, g:0, v:start[0]+start[1]*cols}],
                length = 1,
                adj, distance, find, i, j, max, min, current, next
            ;
            end = {x:end[0], y:end[1], v:end[0]+end[1]*cols};
            switch (f) {
                case "Diagonal":
                    find = diagonalSuccessors;
                case "DiagonalFree":
                    distance = diagonal;
                    break;
                case "Euclidean":
                    find = diagonalSuccessors;
                case "EuclideanFree":
                    f2 = Math.sqrt;
                    distance = euclidean;
                    break;
                default:
                    distance = manhattan;
                    find = nothingToDo;
                    break;
            }
            find || (find = diagonalSuccessorsFree);
            do {
                max = limit;
                min = 0;
                for(i = 0; i < length; ++i) {
                    if((f = open[i].f) < max) {
                        max = f;
                        min = i;
                    }
                };
                current = open.splice(min, 1)[0];
                if (Math.min(current.v,end.v) <= Math.max(end.v,current.v)) {
                    --length;
                    next = successors(find, current.x, current.y, grid, rows, cols);
                    for(i = 0, j = next.length; i < j; ++i){
                        (adj = next[i]).p = current;
                        adj.f = adj.g = 0;
                        adj.v = adj.x + adj.y * cols;
                        if(!(adj.v in list)){
                            adj.f = (adj.g = current.g + distance(adj, current, f1, f2)) + distance(adj, end, f1, f2);
                            open[length++] = adj;
                            list[adj.v] = 1;
                        }
                    }
                } else {
                    i = length = 0;
                    do {
                        result[i++] = [current.x, current.y];
                    } while (current = current.p);
                    result.reverse();
                }
            } while (length);
            return result;
        }*/

        function AStar2(grid, start, end, f) {
            var
                cols = grid[0].length,
                rows = grid.length,
                limit = (cols * rows),
                f1 = Math.abs,
                f2 = Math.max,
                list = {},
                result = [],
                open = [{x:start[0], y:start[1], rx:start[0], ry:start[1], f:0, g:0, v:Math.round(start[0]) + Math.round(start[1])*cols}],
                length = 1,
                adj, distance, find, i, j, max, min, current, next
            ;
            end2 = {x:end[0], y:end[1], rx:end[0], ry:end[1], v:Math.round(end[0]) + Math.round(end[1])*cols};

            console.warn("grid length: "+cols+","+rows);
            console.warn(JSON.stringify(open));
            console.warn(JSON.stringify(end2));

            switch (f) {
                case "Diagonal":
                    find = diagonalSuccessors;
                case "DiagonalFree":
                    distance = diagonal;
                    break;
                case "Euclidean":
                    find = diagonalSuccessors;
                case "EuclideanFree":
                    f2 = Math.sqrt;
                    distance = euclidean;
                    break;
                default:
                    distance = manhattan;
                    find = nothingToDo;
                    break;
            }
            find || (find = diagonalSuccessorsFree);
            do {
                max = limit;
                min = 0;
                for(i = 0; i < length; ++i) {
                    if((f = open[i].f) < max) {
                        max = f;
                        min = i;
                    }
                };
                current = open.splice(min, 1)[0];
                //if (Math.min(current.v,end2.v) != Math.max(current.v,end2.v)) {
                if (current.v != end2.v) {
                    --length;
                    next = successors2(find, current.rx, current.ry, grid, rows, cols);
                    for(i = 0, j = next.length; i < j; ++i){
                        (adj = next[i]).p = current;
                        adj.f = adj.g = 0;
                        adj.v = Math.round(adj.x) + Math.round(adj.y) * cols;
                        if(!(adj.v in list)){
                            adj.f = (adj.g = current.g + distance(adj, current, f1, f2)) + distance(adj, end, f1, f2);
                            open[length++] = adj;
                            list[adj.v] = 1;
                        }
                    }
                } else {
                    i = length = 0;
                    do {
                        result[i++] = [current.rx, current.ry];
                    } while (current = current.p);
                    result.reverse();
                    result.push([end2.x, end2.y]);
                }
            } while (length);

            log.error(JSON.stringify(result));

            for (var i=3; i < (result.length-1); ++i)
            {
              if ((Math.abs(result[i-2][0] - result[i][0]) >= 2 && Math.abs(result[i-2][1] - result[i][1]) == 0) ||
                  (Math.abs(result[i-2][1] - result[i][1]) >= 2 && Math.abs(result[i-2][0] - result[i][0]) == 0))
                result.splice(--i,1);
            }
            return result;
        }

        return {AStar, AStar2};

    }());

    return AStar;
});