A星寻路(一) - 图2

A*范围转换 A_rect(table,table)免费

格式 : table = A_rect( {起点x,起点y} ， {目标点x，目标点y} )
适用场景 : A星寻路
其他关联函数 : ptable

初始化起点为（0,0）思路图解：
A星寻路(一) - 图3

1、先求x1,y1,x2,y2范围坐标，才能进行二值化：
我们希望输入任意2个边角坐标，自动计算左上角和右下角的范围{x1,y1,x2,y2}

  1. function A_rect(t1,t2)
  2.     local t={}
  3.     if t1[1]<t2[1] then
  4.         t[1]=t1[1]
  5.         t[3]=t2[1]
  6.     else
  7.         t[1]=t2[1]
  8.         t[3]=t1[1]
  9.     end
  10.     if t1[2]<t2[2] then
  11.         t[2]=t1[2]
  12.         t[4]=t2[2]
  13.     else
  14.         t[2]=t2[2]
  15.         t[4]=t1[2]
  16.     end
  17.     return t
  18. end
  20. local QI_DIAN={440,467}
  21. local ZH_DIAN={486,407}
  22. local rect = A_rect(QI_DIAN,ZH_DIAN) --[[人物起点，目标终点]]
  23. --x1,y1,x2,y2:rect={440,407,486,467}

A*路线代价 A_cost(table,table)免费

格式 : 代价 = A_rect( {起点x,起点y} ， {目标点x，目标点y} )
适用场景 : A星寻路

A星寻路则需要计算起点—>终点消耗的代价：**直线每步+10，斜线每步+14**

  1. function A_cost(Qt,Zt)
  2.     local x1=math.abs(Zt[1]-Qt[1])
  3.     local y1=math.abs(Zt[2]-Qt[2])
  4.     local a = math.abs(x1-y1)  --[[找到x和y之间的差值]]
  5.     local z = 0 --[[代价]]
  6.     if x1<y1 then  --[[x1,y1最小值计算斜线，a差值计算直线]]
  7.         z=x1*14+a*10
  8.     else
  9.         z=y1*14+a*10
  10.     end
  11.     return z
  12. end

二值化代价 A_binarizeImage(table,table,number)免费

格式 : table，缩放Zt,缩放Qt = A_binarizeImage( {范围，颜色-偏色}, {起点x, 起点y}, 步数 )
适用场景 : A星寻路
其他函数 : ptable、A_rect、A_cost
叉叉函数 : keepScreen、getColorRGB

  1. function A_binarizeImage(t,t_1,P)
  2.     local P = P or 1 --[[遍历步数1像素]]
  3.     local x0 = math.floor((t_1[1]-t.rect[1])/P) + 1
  4.     local y0 = math.floor((t_1[2]-t.rect[2])/P) + 1
  5.     local Qt = {x0 , y0 ,0}  --[[二值化起点]]
  6.     local Zt = {0,0,0}  --[[找到最远距离的点]]
  7.     local getColorRGB = getColorRGB
  8.     local rect = t.rect or {0,0,0,0}
  9.     local diff = t.diff or {"0x000000-0x000000"}
  10.     local color = {}
  11.     local tab = {}
  12.     for k,v in pairs(diff) do
  13.         if color[k]==nil then
  14.             local rgb_1 = tonumber(string.sub(v,1,8)) --0xf7d363-->转数值
  15.             local rgb_2 = tonumber(string.sub(v,10,17))
  16.             color[k] = {
  17.                 lr = rgb_1/0x10000,
  18.                 lg = rgb_1%0x10000/0x100,
  19.                 lb = rgb_1%0x100,
  20.                 sr = rgb_2/0x10000,  --阈值
  21.                 sg = rgb_2%0x10000/0x100,  --阈值
  22.                 sb = rgb_2%0x100,  --阈值
  23.             }
  24.         end
  25.     end
  26.     keepScreen(true)  --保持屏幕
  27.     for y=rect[2],rect[4],P do
  28.         local y1 = math.floor((y - rect[2])/P) + 1    --坐标位置初始化
  29.         tab[y1] = {}
  30.         for x=rect[1],rect[3],P do
  31.             local x1 = math.floor((x - rect[1])/P) + 1 --坐标位置初始化
  32.             for i = 1,#color do  --颜色参数数量
  33.                 local lr,lg,lb = color[i].lr,color[i].lg,color[i].lb
  34.                 local sr,sg,sb = color[i].sr,color[i].sg,color[i].sb
  35.                 local r,g,b = getColorRGB(x,y)  --调用这个函数需要用保持屏幕来提高效率
  36.                 if math.abs(lr-r) > sr or math.abs(lg-g) > sg or math.abs(lb-b) > sb then  --绝对值
  37.           local z = A_cost(Qt,{x1,y1}) --路程代价
  38.                     if Zt[3] < z then
  39.                         Zt = {x1, y1, z }
  40.                     end
  41.           tab[y1][x1] = 0
  42.                 else
  43.                     tab[y1][x1] = 1  --[[匹配]]
  44.                     break
  45.                 end
  46.             end
  47.         end
  48.     end
  49.     keepScreen(false)
  50.     return tab,Qt,Zt
  51. end
  53. --rect={440,407,486,467}
  54. local t = {
  55.     rect = rect,
  56.     diff = {"0x000400-0x333333"}
  57. }
  58. local t,Qt,Zt=A_binarizeImage(t,{440,467},3) --[[缩放后的：Zt=终点，Qt=起点]]
  59. ptable(t,Qt,Zt) --Qt={1,21,0},Zt={16,1,260}
  1. t={
  2.     {1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
  3.     {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  4.     {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  5.     {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  6.     {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  7.     {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  8.     {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  9.     {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  10.     {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  11.     {1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0},
  12.     {1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0},
  13.     {1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0},
  14.     {1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0},
  15.     {1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0},
  16.     {1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1},
  17.     {0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1},
  18.     {0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},
  19.     {0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},
  20.     {0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},
  21.     {0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},
  22.     {0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1}}

为了提高二值化速度，二值化步数设置为3，二值化图像比原图缩小3倍。
缩放**注意事项：**保证最少9格子内没有不可走“+++”或“1” ，保证路线宽敞即可，因为我并不想贴着墙走。所以后面会有一种算法，判断格子内有“墙”则不走这条路线。
image.png

游戏图：
范围只是演示，实际范围根据目标点而定！
image.pngA星寻路(一) - 图6
不可走路线：“+++”默认显示 1 

  1. --转化成代价图像，起点为0，终点为260最大代价，从0周围开始寻找最小值路线
  2. t={
  3. {+++,+++,+++,212,216,220,224,228,232,236,240,244,248,252,256,260},
  4. {+++,+++,198,202,206,210,214,218,222,226,230,234,238,242,246,250},
  5. {+++,184,188,192,196,200,204,208,212,216,220,224,228,232,236,240},
  6. {170,174,178,182,186,190,194,198,202,206,210,214,218,222,226,230},
  7. {160,164,168,172,176,180,184,188,192,196,200,204,208,212,216,220},
  8. {150,154,158,162,166,170,174,178,182,186,190,194,198,202,206,210},
  9. {+++,144,148,152,156,160,164,168,172,176,180,184,188,192,196,206},
  10. {+++,134,138,142,146,150,154,158,162,166,170,174,178,182,192,202},
  11. {+++,+++,128,132,136,140,144,148,152,156,160,164,168,178,188,198},
  12. {+++,114,118,122,126,130,134,138,142,146,+++,+++,+++,174,184,194},
  13. {+++,104,108,112,116,120,124,+++,+++,+++,+++,+++,+++,+++,+++,190},
  14. {+++,94,98,102,106,110,+++,+++,+++,+++,+++,+++,+++,+++,+++,186},
  15. {+++,84,88,92,96,100,+++,+++,+++,+++,+++,+++,+++,+++,+++,182},
  16. {+++,74,78,82,86,90,+++,+++,+++,+++,+++,+++,+++,+++,+++,178},
  17. {+++,64,68,72,76,80,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++},
  18. {50,54,58,62,66,70,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++},
  19. {40,44,48,52,56,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++},
  20. {30,34,38,42,52,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++},
  21. {20,24,28,38,48,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++},
  22. {10,14,24,34,44,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++},
  23. {0,10,20,30,40,50,+++,+++,+++,+++,+++,+++,+++,+++,+++,+++}}

地图未探索区域可能发生的情况：
假设黄线内是墙，终点也是墙，那么实际返回距离终点最近的Zt={10,1,240}，证明Zt是确定我们实际的终点。
这里要注意：如果黄线是墙，终点是可走的，但是并没有可走路线，返回Zt不变，这个问题我们在后面学习A星寻路，发现寻路失败，再来解决。
image.png

OK，有了代价图表，我们就可以开始写A星寻路算法，寻找0—>260最短路线。

A星寻路(一) - 图8麻麻再也不用担心我迷路了。。