在js中使用多維數組尋找路徑

Question

我有一個存儲在多維數組中的x-y網格。 x-y網格中的每個點都有一個值。

實施例：

var xy = [ 
    [0,3,1,1,0], 
    [0,0,2,2,1], 
    [0,0,1,1,0] 
]; 

假定VAR xy的佈局是像的xy網格（x 1和y 2。將3例如

下面是這種較大 '打印出來'。一個變量，以更大的高度和寬度：現在

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) 
(1) 0 0 0 1 1 1 2 2 1 1 0 0 0 
(2) 0 0 1 1 1 2 2 3 2 2 1 0 0 
(3) 0 0 0 1 2 2 3 3 2 1 0 0 0 
(4) 0 4 0 1 1 1 2 2 1 0 0 0 8 
(5) 0 0 0 0 0 0 1 1 0 0 0 0 4 
(6) 0 0 0 0 9 9 9 0 0 0 0 0 0 
(7) 0 0 0 0 9 9 0 0 0 0 0 0 0 

，爲舉例起見，假裝是，上述佈局是一個圖，像棋盤對於初學者來說，以不注意每個POIN的值。對電網T，假設我們想知道的一個「棋子」可以，比如說，從X4 Y8達到該廣場....我們可以做這樣的事在JS：

var n = ,//total # of items in grid 
    a = ,//a certain point on the grid 
    r = 5; //range of movement 
for(var i = 0; i < n; i++){ //this would be a double for or something similar to go through the grid properly, but let's pretend i is a given point on the grid. 
    Math.abs(((a.xLocation + a.yLocation) - (i.xLocation + i.yLocation)) <= r) //if the positive difference between the current point in the loop and the location of the certain point is less than or equal to the range....true! 
} 

在粗糙

所以上面的例子A點的東西可以移動5個步驟，對角線，垂直，水平，無論如何。我們不知道方向，只是運動的潛力。

這很容易弄清楚。我仍然試圖讓自己頭腦發熱的部分是這樣的：你怎麼知道點a上的東西是否可以基於網格的VALUES達到點i。 0意味着沒有增強，但1或2需要1或2或其他任何額外的運動.....你怎麼知道在地圖上的每個點？再次，不知道哪個方向或路徑 - 是否是最優的。

澄清：想象一下棋盤。每個方形棋盤都有一個值，表示需要多少個額外移動點才能到達那裏。一個給定的棋子，根本不使用國際象棋規則，可以向任何方向移動，比方說，5'移動點'。許多正方形的值爲0，因此不需要花費更多的移動點。但是1的正方形需要2個總移動點數，2個需要3個總數，等等。真的，您可以輕鬆地將1添加到下面的所有方塊中，以確定鄰近方塊中的棋子是否可以移動到那裏。不過你喜歡。我只是在尋找某種能夠得出答案的論壇或建議。在這裏，看看這個更簡單的例子。

(1) (2) (3) 
(1) 0 1 3 
(2) 1 X 2 
(3) 2 0 1 

把它想象成一個遊戲，每個方塊都代表某種地形缺陷。有些路徑比其他路徑更容易，但其他路徑更直接。你可以採取任何方式到達某個廣場，但在移動之前，哪些廣場是合法的，哪些不是？所以我們的作品在X2 Y2上，對吧？他有5個運動點。他想知道他可以搬到哪些地方。那麼，他可以轉移到其中任何一個。但是X1Y1將花費1個動作點，X1Y2花費2個，X1Y3花費4個等等等容易弄清楚。但如果董事會更大，每個潛在的（未知的）運動都需要積分，他可以移動到哪個方塊，哪個方塊不能？這有意義嗎？

編輯2：稍微複雜一些的例子：

(1) (2) (3) (4) (5) 
(1) 0 1 3 0 0 
(2) 1 X 2 1 0 
(3) 2 0 1 0 0 
(4) 1 0 0 1 3 
(5) 0 0 0 0 4 

因此，我們在這個例子中一塊是X2Y2了，但他想知道，對於每平方米，如果他能做到有 - 布爾值，是或否。只有九個方格很容易，但隨着網格的增長，複雜性也隨之增加。我當然可以手動做 - 他可以達到X4Y4嗎？是。但在編程上，我怎麼得到這個？

編輯3：網格的大小是沒有意義的，我只是意識到。這真的是範圍的大小。例如。，如果運動範圍是5，我只需要計算出每個方向上五個方格的可行性。這樣就簡化了一下。

編輯4：我覺得我有點更好的想法。看最外面的5環。它是否大於0？那就不要。下一個最外層的環（4 out）。大於1？號碼下一個最外圈。大於2？那就不要。等等這些工作或可能導致不正確的結果？

js或jQuery的答案（或者甚至只是在正確的方向上）首選，但即使你可以通過邏輯工作，我可以將它翻譯成js或jquery。

Answer 1

我認爲你想要做的是一種基本的搜索，在每次迭代時檢查周圍的正方形。我想出了一個模型示例with this jsfiddle。打開控制檯，點擊運行，它應該從（2，2）的3個步驟中打印出示例地圖和它可以到達的地方。

有一個在那裏設置一些額外的代碼，但主要代碼是search_rec功能：

function search_rec(
     map, // The input 'difficulty' map 
     output, // The output map (puts '1's in spots that can be reached) 
       // Should be the same size as the input map 
     x, y, // The current/starting position 
     limit) { // The number of spaces you are allowed to move 

    // If the number of spaces allowed to move is negative, then we can't 
    // reach this position, so we stop 
    if (limit < 0) { 
     return; 
    } 

    // Otherwise, if the limit is >= 0, then we can make it here and we 
    // store that in the output 
    output[y][x] = 1; 

    // Now, for each of the four directions 
    // Check if we're at a map boundary 
    if (x > 0) { 
     // If we're not, then we recurse, moving our starting point in 
     // the given direction, and lowering our limit by 1 (for the 
     // base movement) as well as the 'difficulty' of the terrain of 
     // the space we're moving into 

     search_rec(map, output, x - 1, y, 
     //     ^change position 
         limit   - 1   - map[y][x - 1]); 
     // lower limit^by the base^and the difficulty^
    } 
    if (x < map[0].length - 1) { 
     search_rec(map, output, x + 1, y, limit - map[y][x + 1] - 1); 
    } 
    if (y > 0) { 
     search_rec(map, output, x, y - 1, limit - map[y - 1][x] - 1); 
    } 
    if (y < map.length - 1) { 
     search_rec(map, output, x, y + 1, limit - map[y + 1][x] - 1); 
    } 
} 

希望這邏輯是有道理的，而且它實際上解決您就想解決了這個問題。