確定點A是否需要切角才能到達點B

我正在尋找一種有效的方法來檢查對象是否會切角從點A到點B或防止對象從點A移動如果在兩者之間存在對角線不可行的位置，則指向B點。確定點A是否需要切角才能到達點B

什麼是已知的：

每個點是寬度和高度1
每點都有8個相鄰點的列表的平方
的點可以是適於步行或nonwalkable

這裏有一些例子（a是來源，b是desination和X是一個不可行的點）：

aX 
b

在上述情況下，a不能走路是因爲在相鄰的兩者點a和點b一個不可行走點...因此，對於該電流的情況下，變得b從a（即，a不可行走必須在繼續b）

下面是一個類似的情況之前向下移動，在這個意義上a不能走路到b：

aX 
Xb

我現在這樣做的方式是獲取點A和點B的正交相鄰點集合並使這兩個集合相交。如果相交結果中沒有元素，則點A可以走到點B。

...它的工作原理。

但是，有沒有一個，也許更實用的數學和有效的方法？

來源

2010-08-09 Andreas Grech

那麼它是什麼樣子一樣，如果它是適合步行？你可能想要展示如何從A - > B得到。 – 2010-08-09 11:17:53

這是無關緊要的。我只想知道是否可以從A移動到B. – 2010-08-09 11:26:00

我假設你只在情況感興趣，其中b是一個「一個鄰居的關係，然後只對角相鄰。這將是

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1))

現在在這種情況下，我們只需要檢查兩個點相鄰的兩個點。

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1)) { 
    if (blocked(a.x, b.y) || blocked(b.x, a.y)) { 
     // unwalkable 
    } else { 
     // walkable 
    } 
}

你當然可以合併if語句。

來源

2010-08-09 12:30:12 deinst

小修正：... || （b.x，a.y） – 2010-08-09 18:11:18

Doh！我是付費會員，是全國誦讀困難協會的DNA。我會解決它。 – deinst 2010-08-09 18:17:30

由於上面的答案假定要檢查的單元格是鄰居，因此可以簡單地檢查它們是否彼此對角，而不是對角線和彼此相鄰。這樣你可以削減額外的比較。

if (abs(a.x - b.x) == abs(a.y - b.y)) {

代替

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1)) {

來源

2010-08-11 13:21:01

確定點A是否需要切角才能到達點B

回答

相關問題