六角格棋盤距離計算的一種思路

2023-06-23 19:45 作者:查稽查稽查稽 0人讀過 | 我要投稿

六角格棋盤廣泛應用于戰(zhàn)棋游戲中。比起四角格棋盤，六角格棋盤的距離計算更加復雜。關于六角格的距離計算，有非常多的思路和解決方案，本文僅從數學的角度簡單介紹一種方法。

一、如何定義六角格棋盤的距離

在平面上，與某點距離相同的點集合是一個圓。在六角格棋盤中，與某格距離相同的格集合是個“六邊形”，如圖1所示，用相同顏色表示距離相同的格。

二、六角格棋盤的坐標

????1. 四角格棋盤的坐標

先來分析較為簡單的四角格，如圖2所示。

在四角格中，由某一格向相鄰的格移動時，有四個運動方向：i，-i，j，-j

$i%3D(1%2C%5C%200)$

$-i%3D(-1%2C%5C%200)$

$j%3D(0%2C%5C%201)$

$-j%3D(0%2C%5C%20-1)$

從格 $(0%2C%5C%200)$ 經過若干次運動到達某一格，每次運動的向量和，即為該格的坐標。由此繪制四角格棋盤的坐標，如圖3所示。

????2. 六角格棋盤的坐標

在六角格中，由某一格向相鄰的格移動時，有六個運動方向：i，-i，j，-j，k，-k

$i%3D(1%2C%5C%200%2C%5C%200)$

$-i%3D(-1%2C%5C%200%2C%5C%200)$

$j%3D(0%2C%5C%201%2C%5C%200)$

$-j%3D(0%2C%5C%20-1%2C%5C%200)$

$k%3D(0%2C%5C%200%2C%5C%201)$

$-k%3D(0%2C%5C%200%2C%5C%20-1)$

如圖4所示。

從格 $%5Cleft(0%2C0%2C0%5Cright)$ 經過若干次運動到達某一格，每次運動的向量和，即為該格的坐標。

但是這樣會帶來一個問題：我們都知道平面上的一點只需要兩個坐標就可以確定了，現在我們用了三個坐標，必然有一個是不獨立的。由? $i%2Bj%2Bk%3D0$ 可知，坐標

$(a%2C%5C%20b%2C%5C%20c)$

$(a%2B1%2C%5C%20b%2B1%2C%5C%20c%2B1)$

$(a%2B2%2C%5C%20b%2B2%2C%5C%20c%2B2)$

……

$(a%2Bk%2C%5C%20b%2Bk%2C%5C%20c%2Bk)$

……

描述的是同一個格。

因此，我們設法舍掉一個坐標。對于坐標 $(a%2C%5C%20b%2C%5C%20c)$ 來說， $%5Cleft(a-c%2Cb-c%2C0%5Cright)$ 是同一個格。將第三個坐標變?yōu)?并舍去，每個格就有了統(tǒng)一的坐標 $%5Cleft(a-c%2Cb-c%5Cright)$ 。如圖5所示。

不難看出，用兩個坐標想要直觀計算六角格棋盤的距離還是太困難，在推導中仍將采用三坐標進行計算，最后再將結果雙坐標化表示。

三、六角格棋盤的距離計算

????1. 四角格棋盤的距離

易知，四角格棋盤中格 $(a%2C%5C%20b)$ 與格 $(0%2C%5C%200)$ 的距離 $r$ 為

$r%3D%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C$

推導過程如下：

假設我們從格 $(0%2C%5C%200)$ 出發(fā)，走任意路徑到達格 $(a%2C%5C%20b)$ ，設我們進行 $i$ 運動的次數是 $A_1$ ， $-i$ 運動的次數是 $A_2$ ， $j$ 運動的次數是 $B_1$ ， $-j$ 運動的次數是 $B_2$ ，那么我們走過的路程 $s$ 為

$s%3DA_1%2BA_2%2BB_1%2BB_2$

且有

$a%3DA_1-A_2$

$%7Bb%3DB%7D_1-B_2$

定義

$s_A%3DA_1%2BA_2$

則

$s_A%5E2%3DA_1%5E2%2BA_2%5E2%2B2A_1A_2%3Da%5E2%2B4A_1A_2%5Cgeq%20a%5E2$

$s_A%5Cgeq%5Cleft%7Ca%5Cright%7C$

取等條件 $A_1%3D0$ 或 $A_2%3D0$

同理有

$s_B%3DB_1%2BB_2%5Cgeq%5Cleft%7Cb%5Cright%7C$

$s%3Ds_A%2Bs_B%5Cgeq%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C$

定義所有路徑中路程最小值為距離 $r$ ，則有

$r%3D%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C$

對于更一般的情況，格 $(a_1%2C%5C%20b_1)$ 與格 $(a_2%2C%5C%20b_2)$ 的距離 $r$ 為

$r%3D%5Cleft%7Ca_2-a_1%5Cright%7C%2B%5Cleft%7Cb_2-b_1%5Cright%7C$

????2. 六角格棋盤的距離

根據對四角格的討論，我們得到路程 $s$ 和距離 $r$ 有以下結論：

$s%5Cgeq%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C$

$r%3D%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C$

在六角格中，假如我們從 $(0%2C%5C%200%2C%5C%200)$ 出發(fā)，走任意路徑到達 $(a%2C%5C%20b%2C%5C%20c)$ ，類比易得如下結論：

$s%5Cgeq%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C%2B%5Cleft%7Cc%5Cright%7C$

那么

$r%3D%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C%2B%5Cleft%7Cc%5Cright%7C$

是否也成立呢？

答案是不成立，因為 $a$ ， $b$ ， $c$ 三個坐標并不是唯一的。根據對六角格棋盤坐標的討論，我們可以得到：

$s%5Cgeq%5Cleft%7Ca%5Cright%7C%2B%5Cleft%7Cb%5Cright%7C%2B%5Cleft%7Cc%5Cright%7C$

$s%5Cgeq%5Cleft%7Ca%2B1%5Cright%7C%2B%5Cleft%7Cb%2B1%5Cright%7C%2B%5Cleft%7Cc%2B1%5Cright%7C$

$s%5Cgeq%5Cleft%7Ca%2B2%5Cright%7C%2B%5Cleft%7Cb%2B2%5Cright%7C%2B%5Cleft%7Cc%2B2%5Cright%7C$

……

$s%5Cgeq%5Cleft%7Ca%2Bk%5Cright%7C%2B%5Cleft%7Cb%2Bk%5Cright%7C%2B%5Cleft%7Cc%2Bk%5Cright%7C$

……

在這些右式中的最小值才是距離 $r$ 。

如何求得這個最小值，關鍵是找到對應的 $k$ 。在數軸上， $%5Cleft%7Ca%2Bk%5Cright%7C$ 對應 $a$ 與 $-k$ 的距離， $%5Cleft%7Cb%2Bk%5Cright%7C$ 對應 $b$ 與 $-k$ 的距離， $%5Cleft%7Cc%2Bk%5Cright%7C$ 對應 $c$ 與 $-k$ 的距離。不妨假設 $a%5Cle%20b%5Cle%20c$ ，那么：

$%5Cleft%7Ca%2Bk%5Cright%7C%2B%5Cleft%7Cc%2Bk%5Cright%7C%5Cgeq%5Cleft%7Ca-c%5Cright%7C$

取等時 $a%5Cle%20-k%5Cle%20c$

$s%5Cgeq%5Cleft%7Ca%2Bk%5Cright%7C%2B%5Cleft%7Cb%2Bk%5Cright%7C%2B%5Cleft%7Cc%2Bk%5Cright%7C%5Cgeq%5Cleft%7Ca-c%5Cright%7C%2B%5Cleft%7Cb%2Bk%5Cright%7C%5Cgeq%5Cleft%7Ca-c%5Cright%7C$