define([‘node‘], function(node) {
    var Util = {
        random: function (max){
            return Math.floor(Math.random() * ( max + 1));
        },
        logP: function (point,info){
            var t = ‘ x,y:  ‘+ point.x+‘ ‘+point.y;
            if(info){
                t= info + t;
            }
            console.log(t)
        }
    }
    
    return Util;
})

define([], function() {
    var node = function (x,y){
        this.x = x;
        this.y = y;
        this.walkable = true;
    }
    
    return node;
})

define([‘node‘,‘util‘], function(node,util) {
    var grid = function (option){
        this.width = option.width;
        this.height = option.height;
        this.grid = [];
        this._init();
    }
    
    grid.prototype = {
        _init: function (){
            for(var i=0; i<this.width;i++){
                this.grid[i] = [];
                for(var j=0;j<this.height;j++){
                    this.grid[i][j] = new node(i,j);
                }
            }
        },
        getPointAt: function (x,y){
            return this.grid[x][y];
        },
        isInGrid: function (x,y){
            return (x >= 0 && x < this.width) && (y >= 0 && y < this.height);
        },
        isWorkAble: function (x,y){
            return this.isInGrid(x,y) && this.getPointAt(x,y).walkable
        },
        getRandomNeighbor: function (point){
            var neighbors = this.getNeighbors(point);
            var r = util.random(neighbors.length - 1);
            return neighbors[r];
        },
        getNeighbors: function (point){
            var p1,p2,p3,p4;
            var neighbors = [];
            
            if(this.isWorkAble(point.x-1,point.y)){
                p1 = this.getPointAt(point.x-1,point.y);
                neighbors.push(p1);
            }
            if(this.isWorkAble(point.x+1,point.y)){
                p2 = this.getPointAt(point.x+1,point.y);
                neighbors.push(p2);
            }
            if(this.isWorkAble(point.x,point.y+1)){
                p3 = this.getPointAt(point.x,point.y+1);
                neighbors.push(p3);
            }
            if(this.isWorkAble(point.x,point.y-1)){
                p4 = this.getPointAt(point.x,point.y-1);
                neighbors.push(p4);
            }
            return neighbors;
        }
    }
    
    return grid;
})

define([‘util‘], function(util) {
    var rbp = function (){
        this.grid = null;
        this.path = [];
    }

    rbp.prototype = {
        getPath: function (ox,oy,dx,dy,grid){
            this.grid = grid;
            var startPoint = grid.getPointAt(ox,oy);//起始点
            startPoint.walkable = false;
            var endPoint = grid.getPointAt(dx,dy);//终点
            step = grid.width * grid.height * 2;//最多走这些步数
            var next = startPoint;
            while(step){
                step--;
         
                next = findNext(next);
                
                if(next == 0){
                    var last = this.path.splice(-1);
                    last[0].walkable = false;
                    next = this.path[this.path.length - 1];//回溯
                }else{
                    next.walkable = false;
                    this.path.push(next);
                    if(next == endPoint){//判断到达
                        console.log(‘finish ``````‘);
                        var t= ‘‘;
                        for(var i in this.path){
                            t += ‘[‘ + this.path[i].x + ‘,‘ + this.path[i].y+‘] ‘;
                        }
                        console.log(t);
                        step = 0;//结束
                    }
                }
            }
            
            return this.path;
            
            function findNext(point){
                var neighbor = grid.getRandomNeighbor(point);
                
                if(neighbor){
                    util.logP(neighbor);
                    return neighbor;
                }else{
                    console.log(‘not found‘);
                    return 0;
                }
            }
        },
        
    }
    
    return rbp;
})

require.config({
    paths: {
        pathfinding: ‘pathfinding‘,
        node: ‘node‘,
        grid: ‘grid‘
    }
});

require([‘node‘,‘grid‘,‘rbpathfinding‘,‘util‘], function(node,grid,rbp,util) {
    var map = {
        width: 5,
        height: 5
    }
    var grid = new grid(map)
    
    var startNode = {
        x: util.random(map.width -1 ),
        y: 0
    }
    
    var endNode = {
        x: util.random(map.width - 1),
        y: map.height - 1
    }
    
    util.logP(startNode,‘Start Point‘);
    util.logP(endNode,‘End Point‘);
　　
    //调用
    var rbp = new rbp();
    var path = rbp.getPath(startNode.x,startNode.y,endNode.x,endNode.y,grid);
    
    console.log(path);
    //Start Point x,y:  4 0 VM10885:11
    //End Point x,y:  3 4 
    //Path [3,0] [2,0] [2,1] [1,1] [1,0] [0,0] [0,1] [0,2] [1,2] [2,2] [2,3] [3,3] [4,3] [4,4] [3,4]  
})