C#版本的地图路径规划代码

jarlyyn

C#的，代码比较简单，没什么优化和花活，加了适当注释，供参考。

计算分为3个部分

1.mapfile,放所有的房间/出口/飞行的信息

2.context,游戏中的当前状态上下文，包括的出口标签匹配，临时房间，出口等等

3.option 移动的选项，可以限制移动的最大的消耗，避免计算过远的路径，或者禁用飞行信息

jarlyyn

路径规划器，能计算路径，动态规划遍历，动态规划顺序移动

https://github.com/hellclient-sc ... r/Helpers/Mapper.cs

1. using HellMapManager.Models;
   
2. using System.Collections.Generic;
   
3. // 路径规划模块
   
4. namespace HellMapManager.Helpers;
   
5. 
   
6. // 规划中的每一个步骤
   
7. public class WalkingStep
   
8. {
   
9.     //从 出口信息.上一步，出发点，移动消耗，移动总消耗生成一个新的规划步骤
   
10.     //prev是上一个步骤，为空说明是第一步
    
11.     //from是移动起点,因为exit可以在多个房间复用，并不包含起点信息
    
12.     //exit 具体的房间出口信息
    
13.     //cost 这个步骤有多少移动消耗
    
14.     //totalcost 总的移动消耗，如果消耗超过Context中最大的移动消耗，路径规划就会失败
    
15.     public static WalkingStep FromExit(WalkingStep? prev, string from, Exit exit, int cost, int TotalCost)
    
16.     {
    
17.         return new WalkingStep()
    
18.         {
    
19.             Prev = prev,
    
20.             From = from,
    
21.             To = exit.To,
    
22.             Command = exit.Command,
    
23.             Cost = cost,
    
24.             TotalCost = TotalCost + cost,
    
25.             Remain = cost - 1,
    
26.         };
    
27.     }
    
28.     public Step ToStep()
    
29.     {
    
30.         return new Step(Command, To, Cost);
    
31.     }
    
32.     //上一个步骤，为空说明是第一步
    
33.     public WalkingStep? Prev { get; set; } = null;
    
34.     public string From = "";
    
35.     //移动起点,因为exit可以在多个房间复用，并不包含起点信息
    
36.     public string To { get; set; } = "";
    
37.     //目的地
    
38.     public string Command { get; set; } = "";
    
39.     //移动消耗
    
40.     public int Cost { get; set; } = 0;
    
41.     //总移动消耗
    
42.     public int TotalCost { get; set; } = 0;
    
43.     //剩余步数，每个计算回合-1,为0说明这一步移动完成。
    
44.     public int Remain { get; set; } = 0;
    
45. }
    
46. 
    
47. //规划类
    
48. public class Walking(Mapper mapper)
    
49. {
    
50.     //已经移动过的房间信息
    
51.     private Dictionary Walked = new();
    
52.     //对应的mapper
    
53.     public Mapper Mapper { get; } = mapper;
    
54.     //根据最后成功的最后一步移动(last),生成移动结果。targets为目标列表，会在去除移动目标并在结果里记录剩余目标
    
55.     private static QueryResult BuildResult(WalkingStep last, List targets)
    
56.     {
    
57.         var result = new QueryResult();
    
58. 
    
59.         WalkingStep current = last;
    
60.         //没有prev说明是第一步
    
61.         while (current.Prev is not null)
    
62.         {
    
63.             result.Steps.Add(current.ToStep());
    
64.             current = current.Prev;
    
65.         }
    
66.         //第一步也要加入
    
67.         result.Steps.Add(current.ToStep());
    
68.         //逆向一下，最早的步骤应该在最前面
    
69.         result.Steps.Reverse();
    
70.         result.From = current.From;
    
71.         result.To = last.To;
    
72.         //统计剩余目标(移动支持多目标)
    
73.         foreach (var target in targets)
    
74.         {
    
75.             if (target != result.To)
    
76.             {
    
77.                 result.Unvisited.Add(target);
    
78.             }
    
79.         }
    
80.         //计算消耗
    
81.         result.Cost = last.TotalCost;
    
82.         return result;
    
83.     }
    
84.     //在多个起点/终点之间规划一个最近路线
    
85.     //from 起点列表
    
86.     //target 重点目标
    
87.     //initTotalCost 初始移动总消耗，用于缺点多步逼近规划里限制总消耗
    
88.     public QueryResult QueryPathAny(List from, List target, int initTotalCost)
    
89.     {
    
90.         from.RemoveAll(x => x == "");
    
91.         target.RemoveAll(x => x == "");
    
92.         if (from.Count == 0 || target.Count == 0)
    
93.         {
    
94.             return QueryResult.Fail;
    
95.         }
    
96.         Walked = new();
    
97.         //从列表转字典
    
98.         var targets = new Dictionary();
    
99.         List current;
    
100.         List pending = [];
     
101.         foreach (var t in target)
     
102.         {
     
103.             targets[t] = true;
     
104.         }
     
105.         //起点准备
     
106.         foreach (var f in from)
     
107.         {
     
108.             //终点包含起点则直接到达
     
109.             if (targets.ContainsKey(f))
     
110.             {
     
111.                 var result = new QueryResult();
     
112.                 result.From = f;
     
113.                 result.To = f;
     
114.                 result.Cost = initTotalCost;
     
115.                 foreach (var to in target)
     
116.                 {
     
117.                     if (to != f)
     
118.                     {
     
119.                         result.Unvisited.Add(to);
     
120.                     }
     
121.                 }
     
122.                 return result;
     
123.             }
     
124.             //标记起点
     
125.             Walked[f] = new WalkingStep()
     
126.             {
     
127.                 From = "",
     
128.                 Command = "",
     
129.             };
     
130.             //加入移动中列表
     
131.             Mapper.AddRoomWalkingSteps(null, pending, f, initTotalCost);
     
132.         }
     
133.         //移动一轮
     
134.         while (pending.Count > 0)
     
135.         {
     
136.             current = pending;
     
137.             pending = [];
     
138.             //循环每个待移动步骤
     
139.             foreach (var step in current)
     
140.             {
     
141.                 //确定这个步骤还需要计算。
     
142.                 //如果目标已经到达，则放弃
     
143.                 if (!Walked.ContainsKey(step.To))
     
144.                 {
     
145.                     
     
146.                     if (step.Remain <= 1)
     
147.                     {
     
148.                         //移动到达
     
149.                         if (targets.ContainsKey(step.To))
     
150.                         {
     
151.                             //到达终点
     
152.                             return BuildResult(step, target);
     
153.                         }
     
154.                         Walked[step.To] = step;
     
155.                         //还没走完，延迟到下一轮判断
     
156.                         Mapper.AddRoomWalkingSteps(step, pending, step.To, step.TotalCost);
     
157.                     }
     
158.                     else
     
159.                     {
     
160.                         //移动中
     
161.                         step.Remain--;
     
162.                         pending.Add(step);
     
163.                     }
     
164.                 }
     
165.             }
     
166.         }
     
167.         //计算失败
     
168.         return QueryResult.Fail;
     
169.     }
     
170.     //膨胀，在给定的房间边上膨胀iterations个房间
     
171.     //一般用于npc会多步随机移动时，遍历目标和目标周边房间
     
172.     public List Dilate(List src, int iterations)
     
173.     {
     
174.         Walked = new();
     
175.         List current;
     
176.         List pending = [];
     
177.         foreach (var f in src)
     
178.         {
     
179.             //将有效房间加入待计算列表
     
180.             if (Mapper.GetRoom(f) is not null)
     
181.             {
     
182. 
     
183.                 Walked[f] = new WalkingStep()
     
184.                 {
     
185.                     From = "",
     
186.                     Command = "",
     
187.                 };
     
188.                 Mapper.AddRoomWalkingSteps(null, pending, f, 0);
     
189.             }
     
190.         }
     
191.         var i = 0;
     
192.         while (pending.Count > 0 && i < iterations)
     
193.         {
     
194.             current = pending;
     
195.             pending = [];
     
196.             foreach (var step in current)
     
197.             {
     
198.                 //未到达过的新房间加入下一步计算列表
     
199.                 if (!Walked.ContainsKey(step.To))
     
200.                 {
     
201.                     Walked[step.To] = step;
     
202.                     Mapper.AddRoomWalkingSteps(step, pending, step.To, step.TotalCost);
     
203.                 }
     
204.             }
     
205.             i++;
     
206.         }
     
207.         return [.. Walked.Keys];
     
208.     }
     
209.     //通过模拟多步行走的方式，动态计算全遍历路径
     
210.     public QueryResult QueryPathAll(string start, List target)
     
211.     {
     
212.         target.RemoveAll(x => x == "");
     
213.         if (target.Count == 0 || start == "")
     
214.         {
     
215.             return QueryResult.Fail;
     
216.         }
     
217.         var result = new QueryResult
     
218.         {
     
219.             From = start,
     
220.             To = start,
     
221.         };
     
222.         //未走到的房间列表
     
223.         var pending = target;
     
224.         //循环移动，直到全部走完
     
225.         while (pending.Count > 0)
     
226.         {
     
227.             //计算单步
     
228.             var next = QueryPathAny([result.To], pending, result.Cost);
     
229.             if (next.IsSuccess())
     
230.             {
     
231.                 // 累积移动结果，循环下一轮
     
232.                 result.Steps.AddRange(next.Steps);
     
233.                 result.Cost = next.Cost;
     
234.                 result.Unvisited = next.Unvisited;
     
235.                 //更新新的计算列表
     
236.                 pending = result.Unvisited;
     
237.                 result.To = next.To;
     
238.             }
     
239.             else
     
240.             {
     
241.                 //移动失败。结束
     
242.                 pending = [];
     
243.             }
     
244.         }
     
245.         //如果一步也没动过，就是完全失败
     
246.         if (result.Steps.Count == 0)
     
247.         {
     
248.             return QueryResult.Fail;
     
249.         }
     
250.         return result;
     
251.     }
     
252.     //通过模拟多步行走的方式，动态计算顺序路径
     
253.     //targets为带顺序的房间列表
     
254.     //如果有部分房间无法进入，会跳过无法进入的房间。
     
255.     //用于在有某些限制条件的情况下，是指最新的上下文，然后尽可能多的遍历原路径中的房间
     
256.     public QueryResult QueryPathOrdered(string start, List target)
     
257.     {
     
258.         target.RemoveAll(x => x == "");
     
259.         if (target.Count == 0 || start == "")
     
260.         {
     
261.             return QueryResult.Fail;
     
262.         }
     
263.         var result = new QueryResult
     
264.         {
     
265.             From = start,
     
266.             To = start,
     
267.         };
     
268.         for (var i = 0; i < target.Count; i++)
     
269.         {
     
270.             var next = QueryPathAny([result.To], [target[i]], result.Cost);
     
271.             //成功则记录路径，不成功则跳过房间，将失败的房间加入Unvisited,继续计算
     
272.             if (next.IsSuccess())
     
273.             {
     
274.                 result.Steps.AddRange(next.Steps);
     
275.                 result.Cost = next.Cost;
     
276.                 result.To = next.To;
     
277.             }
     
278.             else
     
279.             {
     
280.                 result.Unvisited.Add(target[i]);
     
281.             }
     
282.         }
     
283.         //如果一步也没动过，就是完全失败
     
284.         if (result.Steps.Count == 0)
     
285.         {
     
286.             return QueryResult.Fail;
     
287.         }
     
288.         return result;
     
289.     }
     
290. }
     
291. 
     
292. //地图计算器
     
293. //mapfile为地图信息
     
294. //context为移动上下文,多个移动可能使用相同的上下文
     
295. //options为移动选项，每次移动都可能不一样
     
296. public class Mapper(MapFile mapFile, Context context, MapperOptions options)
     
297. {
     
298.     public Context Context { get; } = context;
     
299.     public MapFile MapFile { get; } = mapFile;
     
300.     public MapperOptions Options { get; } = options;
     
301.     //通过key获取有效房间信息
     
302.     public Room? GetRoom(string key)
     
303.     {
     
304.         if (!Context.Rooms.TryGetValue(key, out var room))
     
305.         {
     
306.             if (!MapFile.Cache.Rooms.TryGetValue(key, out room))
     
307.             {
     
308.                 return null;
     
309.             }
     
310.         }
     
311.         return room;
     
312.     }
     
313.     //更具上下文，获取出口的移动消耗
     
314.     public int GetExitCost(Exit exit)
     
315.     {
     
316.         //判断上下文中是否有单独的出口消耗定义覆盖原始值
     
317.         if (Context.CommandCosts.TryGetValue(exit.Command, out var costs))
     
318.         {
     
319.             if (costs.TryGetValue(exit.To, out var cost))
     
320.             {
     
321.                 return cost;
     
322.             }
     
323.         }
     
324.         return exit.Cost;
     
325.     }
     
326.     //获取房间出口信息
     
327.     public List GetRoomExits(Room room)
     
328.     {
     
329.         List result = [.. room.Exits];
     
330.         //加入上下文中的临时出口
     
331.         if (Context.Paths.TryGetValue(room.Key, out var list))
     
332.         {
     
333.             result.AddRange(list);
     
334.         }
     
335.         //判断是否禁用捷径(飞行)出口
     
336.         if (!Options.DisableShortcuts)
     
337.         {
     
338.             //原始捷径信息
     
339.             MapFile.Map.Shortcuts.ForEach(e =>
     
340.             {
     
341.                 //符合条件则加入列表
     
342.                 if (ValueTag.ValidteConditions(room.Tags, e.RoomConditions))
     
343.                 {
     
344.                     result.Add(e);
     
345.                 }
     
346.             });
     
347.             //上下文的中的临时捷径
     
348.             Context.Shortcuts.ForEach(e =>
     
349.             {
     
350.                 //符合条件则加入列表
     
351.                 if (ValueTag.ValidteConditions(room.Tags, e.RoomConditions))
     
352.                 {
     
353.                     result.Add(e);
     
354.                 }
     
355.             });
     
356.         }
     
357.         return result;
     
358.     }
     
359.     //验证出口
     
360.     //start为出发房间
     
361.     //exit是出口信息
     
362.     //cost为移动消耗
     
363.     public bool ValidateExit(string start, Exit exit, int cost)
     
364.     {
     
365.         //判断房间有效
     
366.         var room = GetRoom(exit.To);
     
367.         if (room == null)
     
368.         {
     
369.             return false;
     
370.         }
     
371.         //验证房间符合当前移动的上下文设置
     
372.         if (!ValidateRoom(room))
     
373.         {
     
374.             return false;
     
375.         }
     
376.         //判断房间不在上下文中的拦截名单里
     
377.         if (Context.IsBlocked(start, exit.To))
     
378.         {
     
379.             return false;
     
380.         }
     
381.         //判断出口不超时
     
382.         if (Options.MaxExitCost > 0 && cost > Options.MaxExitCost)
     
383.         {
     
384.             return false;
     
385.         }
     
386.         //判断出口不超过整个移动的最大消耗
     
387.         if (Options.MaxTotalCost > 0 && cost > Options.MaxTotalCost)
     
388.         {
     
389.             return false;
     
390.         }
     
391.         //判断出口的条件是否匹配当前上下文
     
392.         if (!Context.ValidteConditions(exit.Conditions))
     
393.         {
     
394.             return false;
     
395.         }
     
396.         return true;
     
397.     }
     
398.     //验证房间
     
399.     public bool ValidateRoom(Room room)
     
400.     {
     
401.         //验证房间是否在黑名单
     
402.         if (Context.Blacklist.ContainsKey(room.Key))
     
403.         {
     
404.             return false;
     
405.         }
     
406.         //验证如果启用白名单的话，房间是否在白名单内
     
407.         if (Context.Whitelist.Count > 0 && !Context.Whitelist.ContainsKey(room.Key))
     
408.         {
     
409.             return false;
     
410.         }
     
411.         //验证房间的标签是否匹配上下文中的房间条件
     
412.         if (!ValueTag.ValidteConditions(room.Tags, Context.RoomConditions))
     
413.         {
     
414.             return false;
     
415.         }
     
416.         return true;
     
417.     }
     
418.     //验证路径
     
419.     public bool ValidatePath(string start, Exit exit)
     
420.     {
     
421.         //验证路径是否在黑名单
     
422.         if (Context.IsBlocked(start, exit.To))
     
423.         {
     
424.             return false;
     
425.         }
     
426.         return ValidateExit(start, exit, GetExitCost(exit));
     
427.     }
     
428.     //验证并转换路径
     
429.     //如果路径无效，返回空
     
430.     public WalkingStep? ValidateToWalkingStep(WalkingStep? prev, string from, Exit exit, int TotalCost)
     
431.     {
     
432.         if (exit.To == "" || exit.To == from)
     
433.         {
     
434.             return null;
     
435.         }
     
436.         var cost = GetExitCost(exit);
     
437.         //验证出口
     
438.         if (!ValidateExit(from, exit, cost))
     
439.         {
     
440.             return null;
     
441.         }
     
442.         //判断最大消耗
     
443.         if (Options.MaxTotalCost > 0 && Options.MaxTotalCost < (cost + TotalCost))
     
444.         {
     
445.             return null;
     
446.         }
     
447.         //转换
     
448.         return WalkingStep.FromExit(prev, from, exit, cost, TotalCost);
     
449.     }
     
450.     public void AddRoomWalkingSteps(WalkingStep? prev, List list, string from, int TotalCost)
     
451.     {
     
452.         var room = GetRoom(from);
     
453.         if (room is not null)
     
454.         {
     
455.             foreach (var exit in GetRoomExits(room))
     
456.             {
     
457.                 var step = ValidateToWalkingStep(prev, from, exit, TotalCost);
     
458.                 if (step is not null)
     
459.                 {
     
460.                     list.Add(step);
     
461.                 }
     
462.             }
     
463.         }
     
464.     }
     
465. }

复制代码

jarlyyn

移动上下文

游戏中和移动计算相关的动态信息

https://github.com/hellclient-sc ... r/Models/Context.cs

1. public class Context
   
2. {
   
3.     //标签列表
   
4.     public Dictionary Tags = [];
   
5.     //房间条件列表
   
6.     public List RoomConditions = [];
   
7.     //临时房间
   
8.     public Dictionary Rooms = [];
   
9.     //白名单，为空忽略
   
10.     public Dictionary Whitelist = [];
    
11.     //黑名单
    
12.     public Dictionary Blacklist = [];
    
13.     //临时捷径列表
    
14.     public List Shortcuts = [];
    
15.     //临时出口列表
    
16.     public Dictionary> Paths = [];
    
17.     //拦截路径列表
    
18.     public Dictionary> BlockedLinks = [];
    
19.     //临时指令消耗列表
    
20.     public Dictionary> CommandCosts = [];
    
21. }

复制代码

jarlyyn

移动选项

单次计算移动的信息

https://github.com/hellclient-sc ... els/MapperOption.cs

1. public class MapperOptions
   
2. {
   
3.     //最大单步消耗，为0不限制
   
4.     public int MaxExitCost = 0;
   
5.     //最大总消耗，为0不限制
   
6.     public int MaxTotalCost = 0;
   
7.     //是否禁用捷径
   
8.     public bool DisableShortcuts = false;
   
9. }

复制代码

jarlyyn

https://github.com/hellclient-scripts/hellmapmanager.ts

转写的ts版本的

https://github.com/hellclient-sc ... c/helpers/mapper.ts

https://github.com/hellclient-sc ... c/models/context.ts

https://github.com/hellclient-sc ... els/mapperoption.ts

通过npm能编译成js版本的和lua版本的

js版本的正在稳定性和功能测试

lua的……暂时没空和没脚本测试。

jarlyyn

数据结构大体参考这个

https://www.pkuxkx.net/forum/thread-50071-1-1.html