[發(fā)明專利]一種基于A*算法的兵棋六角格地圖路徑規(guī)劃方法

在審

• 申請?zhí)枺?/td>: 201710516711.8
• 申請日: 2017-06-29
• 公開（公告）號: CN107506513A
• 公開（公告）日: 2017-12-22
• 發(fā)明（設(shè)計）人: 朱梁;趙一莘;黃炎焱
• 申請（專利權(quán)）人: 南京理工大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06F17/30
• 代理公司: 南京蘇創(chuàng)專利代理事務(wù)所(普通合伙)32273
• 代理人: 張學(xué)彪

1.一種基于A*算法的兵棋六角格地圖路徑規(guī)劃方法，其特征在于：包括以下步驟：

1)、地圖信息建模：建立六角格地圖，根據(jù)棋子在不同單元格中的移動能力數(shù)值，將地形信息轉(zhuǎn)化為移動點數(shù)消耗信息，得出經(jīng)過每個單元格的移動消耗點數(shù)，完成地圖建模；

2)、計算每個單元格的坐標(biāo)，得到單元格初始點以及目標(biāo)點的坐標(biāo)；并記錄每個單元格相鄰的6個單元格的坐標(biāo)信息；

3)、利用A*算法生成路徑：

根據(jù)代價函數(shù)f(x)＝g(x)+h(x)，搜索單元格的鄰域，直至到達(dá)目標(biāo)點，然后從目標(biāo)點回溯到初始點，輸出路徑，其中，f(x)是從初始點經(jīng)由節(jié)點x到目標(biāo)點的估價函數(shù)，g(x)是從初始點到節(jié)點x的實際代價，h(x)是節(jié)點x到目標(biāo)點最優(yōu)路徑的估計代價。

2.根據(jù)權(quán)利要求1所述的基于A*算法的兵棋六角格地圖路徑規(guī)劃方法，其特征在于：步驟3)中g(shù)(x)的通過下式計算得到：

g(x)=Σi=0xNi]]>

式中，x為經(jīng)過的單元格數(shù)，N_i為第i個單元格的移動消耗點數(shù)。

3.根據(jù)權(quán)利要求1所述的基于A*算法的兵棋六角格地圖路徑規(guī)劃方法，其特征在于：步驟3)中h(x)的計算方法包括以下步驟：

一、利用直線l₁,l₂和l₃將六角格地圖分割為六部分，其中，直線l₁,l₂和l₃均通過當(dāng)前單元格x的中心點且均與當(dāng)前單元格x的邊垂直；

二、判斷目標(biāo)點T位于的部分及分割此部分的直線，過目標(biāo)點T做直線l₄和l₅，并使直線l₄和l₅分別平行于分割此部分的直線，并得到直線l₄和l₅與分割此部分的直線的交點P₁和P₂；

三、當(dāng)前單元格x到目標(biāo)點T的距離等于P₁點到目標(biāo)點T的距離加上P₂點到目標(biāo)點T的距離，即滿足等式：

d(x,T)=d(P1,T)+d(P2,T)]]>

式中，d_(x,T)為當(dāng)前單元格x到目標(biāo)點T的距離，為P₁點到目標(biāo)點T的距離，為P₂點到目標(biāo)點T的距離；

四、根據(jù)步驟三得到的當(dāng)前單元格x到目標(biāo)點T的距離d_(x,T)，計算得到h(x)：

h(x)＝D·d_(x,T)

式中，D為最小的單元格移動點數(shù)消耗。

4.根據(jù)權(quán)利要求1所述的基于A*算法的兵棋六角格地圖路徑規(guī)劃方法，其特征在于：步驟1)中單元格的移動消耗點數(shù)通過下式計算得到：

移動消耗點數(shù)N_i為：

式中，N_i為第i個單元格的移動消耗點數(shù)，C_i為棋子在第i個單元格中的移動能力，移動消耗點數(shù)的范圍為[1，n]，單元格的個數(shù)為m個。