RPG游戏的寻路算法——从绯月讲起
本帖最后由 navebayes 于 2023-12-26 12:02 编辑最近正在玩个游戏，也算是国产之光绯月仙行录，这个游戏哪里都好就是bug太多，并且作者过于摆烂，以至于有很多玩家都认为这个游戏就是故意拖着吃赞助的（bushi）
言归正传，在游玩这个游戏的过程中，我在一个评论区里看到这样一段话：自从玩了绯月之后，对于其他RPG游戏都看不上眼了，因为这个游戏独创了自动寻路的功能，可以说是RPG类游戏的里程碑式壮举。
我对此感到好奇，因为从前从来没有游玩RPG类游戏的经验，但我学过一点点算法，于是我打算用一些浅显易懂的方式说说自动寻路这样一个功能的实现。
主流的寻路算法：深度优先，广度优先，Dijkstra，A* 等，我这里主要讲讲后两种。
Dijkstra算法：这个算法是目前很多地图软件都在使用的算法，采用OPEN,CLOSE表的方式实现寻路功能。
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。
实际写代码还是比较占行数的，直接给出链接如下。
参考：https://blog.csdn.net/YiYeZhiNian/article/details/122217450
用这个算法，我写过一个课程作业，具体就是对于各个城市的地铁最短路径规划，大致还是比较成功的。先说说个人对于Dijkstra算法设计地铁线路规划：
1.首先用爬虫爬到该城市的地铁网络，包含站点名称，该站点经纬度和线路图，并生成excel表格。用该excel表格生成pickle文件，方便直接调用。
2.注册高德地图开发者账号（该功能需要实名），得到一个key用于调用api（每日上限100次，超过付费，我调试到后面不让我调试了...）
3.输入始发地和目的地，并通过api返回两个位置的经纬度坐标。
4.比较两地理位置之间的最近地铁站，并根据Dijkstra算法实现路径规划。
5.Dijkstra算法的本质就是不断选择新顶点并更新已处理表，并将他和邻居节点进行比对，当所有节点都被处理后即为最短路径
至此，已初步完成具体工作流程。
def get_nearest_subway(data,longitude1,latitude1):
#找最近的地铁站
longitude1=float(longitude1)
latitude1=float(latitude1)
distance=float('inf')
nearest_subway=None
for i in range(data.shape):
site1=data.iloc['name']
longitude=float(data.iloc['longitude'])
latitude=float(data.iloc['latitude']) #分别将经纬度代入，计算与目标之间的欧氏距离
temp=geodesic((latitude1,longitude1), (latitude,longitude)).m #temp对其遍历即可，这里对比各个地铁站的欧氏距离
if temp<distance:
distance=temp
nearest_subway=site1
return nearest_subwaydef subway_line(start,end): #创建点之间的距离
file=open('graph.pkl','rb')
graph=pickle.load(file) #现在我们有了各个地铁站之间的距离存储在graph
costs={} #创建节点的开销表，cost是指从start到该节点的距离
parents={}
parents=None
for node in graph.keys():
costs=float(graph)
parents=start
costs=float('inf') #终点到起始点距离为无穷大
processed=[] #记录处理过的节点list
shortest_path=dijkstra(start,end,graph,costs,processed,parents)
return shortest_path#计算图中从start到end的最短路径
def dijkstra(start,end,graph,costs,processed,parents):
#查询到目前开销最小的节点
node=find_lowest_cost_node(costs,processed)
#使用找到的开销最小节点，计算它的邻居是否可以通过它进行更新
#如果所有的节点都在processed里面 就结束
while node is not None:
#获取节点的cost
cost=costs#cost 是从node 到start的距离
#获取节点的邻居
neighbors=graph
#遍历所有的邻居，看是否可以通过它进行更新
for neighbor in neighbors.keys():
#计算邻居到当前节点+当前节点的开销
new_cost=cost+float(neighbors)
if neighbor not in costs or new_cost<costs:
costs=new_cost
#经过node到邻居的节点，cost最少
parents=node
#将当前节点标记为已处理
processed.append(node)
#下一步继续找U中最短距离的节点costs=U,processed=S
node=find_lowest_cost_node(costs,processed)def find_lowest_cost_node(costs,processed):
#初始化数据
lowest_cost=float('inf') #初始化最小值为无穷大
lowest_cost_node=None
#遍历所有节点
for node in costs:
#如果该节点没有被处理
if not node in processed:
#如果当前的节点的开销比已经存在的开销小，那么更新该节点为最小开销的节点
if costs<lowest_cost:
lowest_cost=costs
lowest_cost_node=node
return lowest_cost_node上面这段基本上搬运的，主要是他代码已经写的很好了，注释也写的不错，但我写的时候爬虫调不出来（反爬虫技术可以的），最后是我手动去地图里找经纬度得到的结果。
引用：https://blog.csdn.net/fengdu78/article/details/111570695
A*算法：这个算法也是非常著名的算法，与Dijkstra算法相比，增加了启发式函数 ---- 启发函数的好坏直接决定了算法的效率和结果。由此衍生的D*（动态A算法）算法也被广泛运用于各类游戏中。D*的搜索效率高的原因就在于，当计划路径上某点被阻碍，因为是反向指针，可以定位到被堵节点的上一节点。也就是说只需重新搜索很小的一部分，其余部分仍然使用初始规划出的路径，大大提高了重规划的效率。
额外补充-dfs&bfs逻辑
深度搜索（dfs）和广度搜索（bfs）的算法逻辑可以说是最具有代表性的，基本任何有关于寻路的算法都没法绕开他俩。我担心可能没了解这2个算法直接去看Djkta和A*会有些懵逼
深度搜索（dfs）
dfs就和它字面意思一样，是往更深的地方找（deepfound）
它的核心思想很简单：
一直往前走，走不通就回头
顺序？当然是长幼啦，有长立长无长立幼 （1会先找2而非6，在2时会先找4而非5 ，直到4发现3 发现无路可走再back回去）
大致伪代码如下
input 地图
create 已经过点
create 结果存储
type node{
node nextNode[];//下一节点们
nodeval;//节点标记物
}
//这里开始是函数
fun dfs（node* nowPoint）
{
define u 为 nextNode[] size
intkey;
for i in u {
if (nowPoint.noteval == target)
{
结果存储 = nowPoint.noteval；
return 0 ；
}
else if( key = (dfs(nowPoint->nextNode)) != -1 ) //如果dfs这次没有返回负1（即 找到终点了）
{
结果存储 = nowPoint.noteval；
return key+1；
}
else
{
/********************/
/** nothing **/
/********************/
}
}
return -1；
}
就那么短，你只需要确定是不是就行了
是不是很简单：p 但是这就是一个比较原始的寻路算法的模样-顺其自然流
在dfs算法中，你需要做的就是 询问+上抛
当然，dfs算法唯一能保证的就是‘找得到路’，这也是为什么纯粹的dfs算法不常用于生产环境中
广度搜索（bfs）
知道深度，广度就很容易联想了 先找周围嘛 无论如何，先找周围
这里不进行代码补充了，只简单地说一下逻辑
这个算法分以下几步：
0，准备一个队列（就是那个queue），然后丢入我们的起点 命运的齿轮开始拨动
1，询问当前节点是否终点？
2，将自己的nextNode 塞入队列中（除了访问过的）
3，从队列里output一个节点，作为下一个‘当前节点’
然后就是循环1~3
是不是很简单？
这2个算法都属于随性流，一个适合终点远一个适合终点近。但无论如何这俩都暂时没有比较最优的功能
因为他们刚~满~十~八~岁~的审敛条件就只是找得到路
但你可以发现哦？如果将dfs的‘长幼判断’换成‘最优判断’，将呆值传递换为矩阵存储 就是dj算法了诶（a*也是类似的）
而bfs作为‘扩散式搜索’显然地在进行多点寻路时效用更加明显
如果觉得寻路算法很难的话，不妨先从dfs&bfs开始了解
Applcu 发表于 2023-12-25 20:19
我在想怎么算说明运作逻辑.....真贴上去么？这个编辑器到底怎么用啊
...
有一个代码框功能，可以用那个。主要编辑的话建议用正八经的md编辑器（我用的是国产的typora） navebayes 发表于 2023-12-25 20:11
申请失败，原因：对算法本身描述过少，请更具体地说明算法的运作逻辑和方式，如果可以最好给出部分低代码
...
啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
这玩意考试考得头昏脑涨，我tm 深度生成树画错了，越想越气 怎么会这么蠢
昔有佳人公孙氏 发表于 2023-12-25 23:08
其实目前，本科生能接触到的寻路算法 无外乎迪杰斯特拉和弗洛伊德 一个不吃负值 一个不吃负环
但其实寻找最 ...
黏菌那个早有耳闻，确实是大自然的力量。我之后还想写点加密算法，比如ＡＥＳ，ＲＳＡ，ＥＣＣ之类的，其实这个地铁的算法也是我的一个课设，我大概花了两天就搞完了，我的主专业课是自控／单片机／数电／模电／嵌入式之类的，更偏自动化这个方向，算法我研究的不深。这个当毕业论文可能还是有一些勉强的，个人感觉工科是要做出一点实物的东西，当然不同学校可能要求不尽相同。
先说说个人对于Dijkstra算法设计地铁线路规划：
1.首先用爬虫爬到该城市的地铁网络，包含站点名称，该站点经纬度和线路图，并生成excel表格。用该excel表格生成pickle文件，方便直接调用。
2.注册高德地图开发者账号（该功能需要实名），得到一个key用于调用api（每日上限100次，超过付费，我调试到后面不让我调试了...）
3.输入始发地和目的地，并通过api返回两个位置的经纬度坐标。
4.比较两地理位置之间的最近地铁站，并根据Dijkstra算法实现路径规划。
5.Dijkstra算法的本质就是不断选择新顶点并更新已处理表，并将他和邻居节点进行比对，当所有节点都被处理后即为最短路径
至此，已初步完成具体工作流程。
def get_nearest_subway(data,longitude1,latitude1):
#找最近的地铁站
longitude1=float(longitude1)
latitude1=float(latitude1)
distance=float('inf')
nearest_subway=None
for i in range(data.shape):
site1=data.iloc['name']
longitude=float(data.iloc['longitude'])
latitude=float(data.iloc['latitude']) #分别将经纬度代入，计算与目标之间的欧氏距离
temp=geodesic((latitude1,longitude1), (latitude,longitude)).m #temp对其遍历即可，这里对比各个地铁站的欧氏距离
if temp<distance:
distance=temp
nearest_subway=site1
return nearest_subwaydef subway_line(start,end): #创建点之间的距离
file=open('graph.pkl','rb')
graph=pickle.load(file) #现在我们有了各个地铁站之间的距离存储在graph
costs={} #创建节点的开销表，cost是指从start到该节点的距离
parents={}
parents=None
for node in graph.keys():
costs=float(graph)
parents=start
costs=float('inf') #终点到起始点距离为无穷大
processed=[] #记录处理过的节点list
shortest_path=dijkstra(start,end,graph,costs,processed,parents)
return shortest_path#计算图中从start到end的最短路径
def dijkstra(start,end,graph,costs,processed,parents):
#查询到目前开销最小的节点
node=find_lowest_cost_node(costs,processed)
#使用找到的开销最小节点，计算它的邻居是否可以通过它进行更新
#如果所有的节点都在processed里面 就结束
while node is not None:
#获取节点的cost
cost=costs#cost 是从node 到start的距离
#获取节点的邻居
neighbors=graph
#遍历所有的邻居，看是否可以通过它进行更新
for neighbor in neighbors.keys():
#计算邻居到当前节点+当前节点的开销
new_cost=cost+float(neighbors)
if neighbor not in costs or new_cost<costs:
costs=new_cost
#经过node到邻居的节点，cost最少
parents=node
#将当前节点标记为已处理
processed.append(node)
#下一步继续找U中最短距离的节点costs=U,processed=S
node=find_lowest_cost_node(costs,processed)
def find_lowest_cost_node(costs,processed):
#初始化数据
lowest_cost=float('inf') #初始化最小值为无穷大
lowest_cost_node=None
#遍历所有节点
for node in costs:
#如果该节点没有被处理
if not node in processed:
#如果当前的节点的开销比已经存在的开销小，那么更新该节点为最小开销的节点
if costs<lowest_cost:
lowest_cost=costs
lowest_cost_node=node
return lowest_cost_node上面这段基本上搬运的，主要是他代码已经写的很好了，注释也写的不错，但我写的时候爬虫调不出来（反爬虫技术可以的），最后是我手动去地图里找经纬度得到的结果。
引用：https://blog.csdn.net/fengdu78/article/details/111570695
修改修改
本帖最后由 navebayes 于 2023-12-25 20:14 编辑申请失败，原因：对算法本身描述过少，请更具体地说明算法的运作逻辑和方式，如果可以最好给出部分低代码
ps：只要做滴好，王爷有赏啊 navebayes 发表于 2023-12-25 20:11
申请失败，原因：对算法本身描述过少，请更具体地说明算法的运作逻辑和方式，如果可以最好给出部分低代码
...
我在想怎么算说明运作逻辑.....真贴上去么？这个编辑器到底怎么用啊{:4_119:}
昔有佳人公孙氏 发表于 2023-12-25 20:25
啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
这玩意考试考得头 ...
看作者本人嘛，我不想干涉思路..
（程序：哥们这可不是什么负权圈，这是时空之门啊啊啊啊啊（然后获得了每过一年减一岁的黄金体验）） 昔有佳人公孙氏 发表于 2023-12-25 20:25
啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
这玩意考试考得头 ...
这应该是考专业课考破防了
昔有佳人公孙氏 发表于 2023-12-25 20:25
啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
这玩意考试考得头 ...
负权不就卡bug了么，越来越低{:4_111:}就成环了
Applcu 发表于 2023-12-25 20:48
负权不就卡bug了么，越来越低就成环了
宝宝，把剩下的内容补上嘛{:4_158:} navebayes 发表于 2023-12-25 20:56
宝宝，把剩下的内容补上嘛
{:4_105:}真是男童啊.....
Applcu 发表于 2023-12-25 21:15
真是男童啊.....
诽谤管理封七天{:4_144:} Applcu 发表于 2023-12-25 21:58
先说说个人对于Dijkstra算法设计地铁线路规划：
1.首先用爬虫爬到该城市的地铁网络，包含站点名称，该站点 ...
可以加入正文喵
昔有佳人公孙氏 发表于 2023-12-25 20:25
啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
这玩意考试考得头 ...
我也头大了.....但本质还是因为Dijkstra算法认为，如果有一条最短路线可以直达目的地，那么从旁边走另外的路将会直接不考虑，但在负权边这里，反而会减小cost，所以Dijkstra算法失效了，因为无法发现这条最短的路径
navebayes 发表于 2023-12-25 22:34
可以加入正文喵
加了加了
Applcu 发表于 2023-12-25 22:51
加了加了
介意让我改一下吗https://pic.imgdb.cn/item/6589996fc458853aef070f38.gif
其实目前，本科生能接触到的寻路算法 无外乎迪杰斯特拉和弗洛伊德 一个不吃负值 一个不吃负环
但其实寻找最短路径的算法里还有很知名的黏菌算法。
有兴趣的可以去B站搜搜黏菌走迷宫，看看在大自然顶级的算法编辑下的单源最短路径问题的解法
不是说将奖励放置位置对应于日本的各大城市，两天内的黏菌路线就基本和目前日本的城市规划大致相似了吗，当然不太严谨是真的
就好像楼主说的做了地铁最短路径规划， 这玩意我舍友和你类似，她做的事全国铁路路径规划，涉及到价格，时间，反正做到最后是你输入起始地址和目的地，就能得出花费最少，时间最少，转站最少的路线，C++课设 我记得很清楚，我记得老师说的评价是，如果再加上运筹学的内容，说不定可以当毕业论文了，不出意外她拿了满分。 navebayes 发表于 2023-12-25 23:02
介意让我改一下吗
可以可以{:4_111:}
Applcu 发表于 2023-12-25 23:30
可以可以
排版改了下喵，东西加好了喵
页:
[1]
2