如何执行符合我需求的Javascript对象递归搜索？

Question

美好的一天,

我正在研究用Javascript编写的基于文本的游戏.我有变量named map这是一个关联对象,包含每个房间的另一个对象.我在某个地方找到了一个小算法,我不知道如何根据我的具体任务修改它.

我的变量:

/**
 *       [003]-[004]
 *         |     |
 * [001]-[002] [007]
 *         |     |
 *       [005]-[006]
 **/     
var map = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "N" : "",
            "S" : "",
            "E" : "002",
            "W" : ""
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "E" : "",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "N" : "",
            "S" : "002",
            "E" : "004",
            "W" : ""
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "N" : "",
            "S" : "007",
            "E" : "",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "S" : "",
            "E" : "006",
            "W" : ""
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "S" : "",
            "E" : "",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006",
            "E" : "",
            "W" : ""
        }
    }
};


function findSteps( id, map, array ) {
    if ( ! ( map && "object" === typeof map ) ) { return; }
    if ( map.Id === id ) { return map; }

    for ( var x in map ) {
        if ( Object.hasOwnProperty.call( map, x ) ) {
            map.Id && array.push( map.Id ); //used to exclude undefined
            var result = findSteps( id, map[ x ], array );

            if ( result !== undefined ) {
                return [ result, array ];
            }
        }
    }
}

console.dir( findSteps( "004", map, [] ) );
// Actually returns [objectObject],001,001,001,002,002,002,003,003,003

我希望该函数返回一个包含所有可能路径的数组数组,稍后我将迭代这些路径以找到最接近的可用路径.

期望的结果将是这样的:

output = [
    [ "001", "002", "003", "004" ],
    [ "001", "002", "005", "006", "007", "004" ]
]

该功能还应该接受启动Id.如果在"map.length"n迭代之前没有找到任何内容,我正在考虑会阻止递归的东西.

也许有点暗示也会受到赞赏.

谢谢!

http://jsfiddle.net/GxZYX/

PS:我已经看过关于递归对象搜索的一些Q/A创建,这正是我找到我正在使用的函数的地方.

编辑:

经过多次思考,希望我不会错.我相信我只需要最短路径.

编辑:

http://jsfiddle.net/GxZYX/1/这是我对广度优先搜索的测试.(窃听)

Answer 1

要找到像您这样的非高度图中两个节点之间的最短路径，您只需要执行广度优先搜索。

function linkedPathToList(next, node){
    var path = [];
    while(true){
        path.push(node);
        if(node == next[node]) break;
        node = next[node];
    }
    return path;
}       

var breadthFirstSearch = function( map, startRoomId, endRoomId ) {

    var next = {};
    next[endRoomId] = endRoomId;

    var currentLevel = [ map[endRoomId] ];

    //(the traditional version of the algorithm uses a queue instead of the
    // complicated two-array thing though)

    while( currentLevel.length ) {

        //if curr level is nodes at distance d from the end
        //next level is d+1
        var nextLevel = [];

        for(var i=0; i<currentLevel.length; i++) {
            var node = currentLevel[i];

            if ( node.Id == startRoomId ) {
                return linkedPathToList(next, startRoomId);
            }

            for( var direction in node.Directions ) {
                var neighbor = node.Directions[direction]; 
                if( !next[neighbor] ) {
                    next[neighbor] = node.Id;
                    nextLevel.push( map[neighbor] );
                }
            }
        }

        currentLevel = nextLevel;
    }

    return null;
};

var map = {
    "001" : {
        "Id" : "001",
        "Name" : "Room 001",
        "Directions" : {
            "E" : "002"
        }
    },
    "002" : {
        "Id" : "002",
        "Name" : "Room 002",
        "Directions" : {
            "N" : "003",
            "S" : "005",
            "W" : "001"
        }
    },
    "003" : {
        "Id" : "003",
        "Name" : "Room 003",
        "Directions" : {
            "S" : "002",
            "E" : "004"
        }
    },
    "004" : {
        "Id" : "004",
        "Name" : "Room 004",
        "Directions" : {
            "S" : "007",
            "W" : "003"
        }
    },
    "005" : {
        "Id" : "005",
        "Name" : "Room 005",
        "Directions" : {
            "N" : "002",
            "E" : "006"
        }
    },
    "006" : {
        "Id" : "006",
        "Name" : "Room 006",
        "Directions" : {
            "N" : "007",
            "W" : "005"
        }
    },
    "007" : {
        "Id" : "007",
        "Name" : "Room 007",
        "Directions" : {
            "N" : "004",
            "S" : "006"
        }
    }
};

console.log('shortest path',  breadthFirstSearch( map, "001", "004" ) );