[分享]战棋中寻路方法

116205035

开始写的是 i++ 不过发帖的时候会异常，所以改为 ii++


[em04][em04]

FantasyDR

加上[ code]标签试试……注意不是大写的CODE，是小写。

116205035

不是A*，WQX上恐怕用不起消耗这么大的方法。

所以想过了一个。
以下是用LAVA写的代码。

2. char map[16][16]={
3. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
4. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
5. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
6. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
7. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
8. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
9. 1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,
10. 1,1,1,1,3,1,1,1,1,1,1,1,1,1,1,1,
11. 1,1,1,1,1,1,5,2,4,1,1,1,1,1,1,1,
12. 1,1,1,1,1,2,1,1,1,1,3,1,1,1,1,1,
13. 1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,
14. 1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,
15. 1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,
16. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
17. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
18. 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
19. // 地图数组
20. char out[16][16];
21. char Step[10][2];
22. char fx;
23. char fy;              /*初始坐标   (7,11)  */
24. char tx;
25. char ty;              /*目标坐标   (4,8)   */
26. char mp;              /*  拥有的移动力    */
27. char Y_Max;
28. char Y_Min;            /*   供查询边界使用  */
29. char V_Path;
30. char lx;
31. char ly;
32. void WriteOut(char x,char y,char Left_mp)
33. {
35.    if(y<Y_Min)Y_Min=y;
36.    else
37.    if(y>Y_Max)Y_Max=y;
38.   
39.   /* 向左搜索*/
40.    if(x-1)
41.     {
42.      if(Left_mp>=map[y][x-1])
43.       {
44.       if(Left_mp-map[y][x-1]>out[y][x-1])
45.        {
46.         out[y][x-1]=Left_mp-map[y][x-1];
47.         if((abs(x-tx)+abs(y-ty))<=V_Path)
48.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
49.         WriteOut(x-1,y,Left_mp-map[y][x-1]);
50.        }
51.       }
52.      else
53.       {
54.         if((abs(x-tx)+abs(y-ty))<=V_Path)
55.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
56.       }
58.     }
59.   /* 向右搜索*/
60.    if((x+1)<16)
61.     {
62.      if(Left_mp>=map[y][x+1])
63.       {
64.       if(Left_mp-map[y][x+1]>out[y][x+1])
65.        {
66.         out[y][x+1]=Left_mp-map[y][x+1];
67.         if((abs(x-tx)+abs(y-ty))<=V_Path)
68.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
69.         WriteOut(x+1,y,Left_mp-map[y][x+1]);
70.        }
71.       }
72.       else
73.       {
74.         if((abs(x-tx)+abs(y-ty))<=V_Path)
75.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
76.       }
77.     }
78.   /* 向上搜索*/
79.    if(y-1)
80.     {
81.      if(Left_mp>=map[y-1][x])
82.       {
83.       if(Left_mp-map[y-1][x]>out[y-1][x])
84.         {
85.         out[y-1][x]=Left_mp-map[y-1][x];
86.         if((abs(x-tx)+abs(y-ty))<=V_Path)
87.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
88.         WriteOut(x,y-1,Left_mp-map[y-1][x]);
89.         }
90.       }
91.       else
92.       {
93.         if((abs(x-tx)+abs(y-ty))<=V_Path)
94.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
95.       }
96.     }
97.   /*向下搜索*/
98.   if((y+1)<16)
99.     {
100.      if(Left_mp>=map[y+1][x])
101.       {
102.        if(Left_mp-map[y+1][x]>out[y+1][x])
103.         {
104.         out[y+1][x]=Left_mp-map[y+1][x];
105.         if((abs(x-tx)+abs(y-ty))<=V_Path)
106.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
107.         WriteOut(x,y+1,Left_mp-map[y+1][x]);
108.         }
109.       }
110.       else
111.       {
112.         if((abs(x-tx)+abs(y-ty))<=V_Path)
113.         {V_Path=abs(x-tx)+abs(y-ty);lx=x;ly=y;}
114.       }
115.     }
116.    
117. }
118. void main()
119. {
120.    char fp;
121.    char wx;
122.    char wy;
123.    char px;
124.    char py;
125.    char ii;
126.    char pv;
127.    char s[20];
128.    mp=6;
129.    fx=7;
130.    fy=11;
131.    tx=12;
132.    ty=4;
133.    Y_Max=fy;
134.    Y_Min=fy;
135.    V_Path=abs(tx-fx)+abs(ty-fy);   /* 初试估价权值 */
136.    
137.    /* 加1是为了不致减到最后变为0而不好判断范围*/
138.    
139.    out[fy][fx]=mp+1;
140.    WriteOut(fx,fy,mp+1);            
141.    printf("Write Out Ok!\n");
142.    printf("%d,%d\n",Y_Min,Y_Max);
143.    printf("%d,%d",lx,ly);
144.    /* 将行进坐标输出 */
145.    ii=0;
146.    px=lx;
147.    py=ly;
148.    pv=out[py][px];
149.    Step[ii][0]=px;
150.    Step[ii][1]=py;
151.    i++;
152.    while(out[py][px]!=mp+1)
153.    {
154.     if(out[py][px-1]>pv){pv=out[py][px-1];Step[ii][0]=px-1;Step[ii][1]=py;ii++;px--;}
155.     else
156.     if(out[py][px+1]>pv){pv=out[py][px+1];Step[ii][0]=px+1;Step[ii][1]=py;ii++;px++;}
157.     else
158.     if(out[py-1][px]>pv){pv=out[py-1][px];Step[ii][0]=px;Step[ii][1]=py-1;ii++;py--;}
159.     else
160.     if(out[py+1][px]>pv){pv=out[py+1][px];Step[ii][0]=px;Step[ii][1]=py+1;ii++;py++;}
161.    }
162.    /* 输出以打印的寻路暂存图*/
163.    
164.    if ((fp=fopen("/LavaData/Out.txt","w"))==0)
165.         printf("创建文件失败!");
166.    else {
167.         for(wy=0;wy<16;wy++)
168.          {
169.           for(wx=0;wx<16;wx++)
170.             {
171.               out[wy][wx]=out[wy][wx]+48;
172.               putc(out[wy][wx],fp);
173.               putc(&#39;,&#39;,fp);
174.             }
175.           putc(13,fp);
176.           putc(10,fp);
177.          }
178.         ii--;
179.         ii--;
180.         for(ii;ii>0;ii--)
181.         {
182.           sprintf(s,"(%d,%d)\r\n",Step[ii][0],Step[ii][1]);
183.           fwrite(s,1,strlen(s)+1,fp);
184.         }
185.           sprintf(s,"(%d,%d)\r\n",Step[0][0],Step[0][1]);
186.           fwrite(s,1,strlen(s)+1,fp);
187.           fclose(fp);
188.       }
189. }

复制代码

可输出OUT 文件：

3. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
4. 0,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. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
9. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
10. 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
11. 0,0,0,0,1,1,0,1,0,1,0,0,0,0,0,0,
12. 0,0,0,1,2,2,4,3,3,2,0,0,0,0,0,0,
13. 0,0,1,2,3,4,5,4,4,3,2,1,0,0,0,0,
14. 0,1,2,3,4,5,6,7,5,4,3,2,1,0,0,0,
15. 0,0,1,2,3,3,5,6,5,4,3,2,1,0,0,0,
16. 0,0,0,1,2,3,4,5,4,3,2,1,0,0,0,0,
17. 0,0,0,0,1,2,3,4,3,2,1,0,0,0,0,0,
18. 0,0,0,0,0,1,2,3,2,1,0,0,0,0,0,0,
19. (8,11)
20. (8,10)
21. (8,9)
22. (9,9)
23. (9,8)

复制代码

括号内的为路径坐标，文件中的矩阵是辅助矩阵。

这个方法是可以节约遍历的点数，缺点是不能寻太长的路，4-6步内最佳。

附上原理：

从出发点（FX，FY）开始递归遍历其周围的点，通过遍历生成一个辅助表，其实就是可以移动到的范围，然后估价范围内点到目标点（TX，TY）的最短距离，找到点（LX，LY），然后通过辅助表，从（LX，LY）开始找路，即找点周围比该点MP（out数组里的值）值大的点。
---------------------------------------------------------------------

以此法可以以最少的移动力消耗到达离目标最近的点。

[此贴子已经被作者于2006-6-26 21:33:19编辑过]