|
马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有帐号?免费注册
x
本帖最后由 navebayes 于 2023-12-26 12:02 编辑
# N0 N; L. |2 |9 G) N p; I4 b- I9 \* M. I# |! E(欢迎访问老王论坛:laowang.vip)
最近正在玩个游戏,也算是国产之光绯月仙行录,这个游戏哪里都好就是bug太多,并且作者过于摆烂,以至于有很多玩家都认为这个游戏就是故意拖着吃赞助的(bushi)& m* @) u# L+ z6 q. U$ s) m(欢迎访问老王论坛:laowang.vip)
言归正传,在游玩这个游戏的过程中,我在一个评论区里看到这样一段话:自从玩了绯月之后,对于其他RPG游戏都看不上眼了,因为这个游戏独创了自动寻路的功能,可以说是RPG类游戏的里程碑式壮举。# ^; `8 O+ O4 s8 r+ b(欢迎访问老王论坛:laowang.vip)
我对此感到好奇,因为从前从来没有游玩RPG类游戏的经验,但我学过一点点算法,于是我打算用一些浅显易懂的方式说说自动寻路这样一个功能的实现。2 w' j2 P w+ R h(欢迎访问老王论坛:laowang.vip)
- d4 L9 ~6 X' a(欢迎访问老王论坛:laowang.vip)
主流的寻路算法:深度优先,广度优先,Dijkstra,A* 等,我这里主要讲讲后两种。
# |+ {% W: K7 B! m- i; R: F# g
: s: F- g& h& {- TDijkstra算法:这个算法是目前很多地图软件都在使用的算法,采用OPEN,CLOSE表的方式实现寻路功能。
8 M# o) w! _3 b" f3 O 创建两个表,OPEN, CLOSE。+ ~1 J1 n1 e6 g; M1 m9 u& B, T2 {(欢迎访问老王论坛:laowang.vip)
OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。8 a# O! B6 H' e$ ~0 u(欢迎访问老王论坛:laowang.vip)
1. 访问路网中里起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。
$ v8 A/ R0 T/ A2. 从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。
) R1 E8 l1 u5 w# o) B3. 遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。- Z* M+ ?8 y4 X(欢迎访问老王论坛:laowang.vip)
4. 重复2,3,步。直到OPEN表为空,或找到目标点。
: q' u7 R+ k3 G; @: e/ V
( G# i' C+ R0 D3 ?3 [+ _5 ~7 M实际写代码还是比较占行数的,直接给出链接如下。
6 v/ q& e+ K! r# l$ K1 a参考:https://blog.csdn.net/YiYeZhiNian/article/details/122217450
O" E! w$ j: l: E; b$ z# T
6 U0 d x, F/ m, }% g用这个算法,我写过一个课程作业,具体就是对于各个城市的地铁最短路径规划,大致还是比较成功的。先说说个人对于Dijkstra算法设计地铁线路规划:
& r! b. C7 F2 Y1.首先用爬虫爬到该城市的地铁网络,包含站点名称,该站点经纬度和线路图,并生成excel表格。用该excel表格生成pickle文件,方便直接调用。' } _" H& J0 j: I5 |6 ]( c(欢迎访问老王论坛:laowang.vip)
2.注册高德地图开发者账号(该功能需要实名),得到一个key用于调用api(每日上限100次,超过付费,我调试到后面不让我调试了...)3 i- ^5 K: u- k, G5 O(欢迎访问老王论坛:laowang.vip)
3.输入始发地和目的地,并通过api返回两个位置的经纬度坐标。. ^1 Q3 ]& q4 m- E9 s4 Z(欢迎访问老王论坛:laowang.vip)
4.比较两地理位置之间的最近地铁站,并根据Dijkstra算法实现路径规划。% q# E7 n {+ |; I7 o9 t) Z$ ~& r- G(欢迎访问老王论坛:laowang.vip)
5.Dijkstra算法的本质就是不断选择新顶点并更新已处理表,并将他和邻居节点进行比对,当所有节点都被处理后即为最短路径
. u0 P5 W) Y1 q k" M4 w4 D至此,已初步完成具体工作流程。2 P, ?8 V% J6 K5 ~ x( }6 e1 }(欢迎访问老王论坛:laowang.vip)
- def get_nearest_subway(data,longitude1,latitude1):. x+ R# v. K2 _4 J3 r(欢迎访问老王论坛:laowang.vip)
- #找最近的地铁站
/ S, F3 z" r( |6 b* n4 i - longitude1=float(longitude1)0 n: V: h8 U+ R8 ](欢迎访问老王论坛:laowang.vip)
- latitude1=float(latitude1)
( A# ~4 t9 S/ Y$ N+ l z - distance=float('inf')9 g0 ?6 Q. @; D$ b- m$ d! I) J7 b(欢迎访问老王论坛:laowang.vip)
- nearest_subway=None0 w9 f( H/ q* J0 Z(欢迎访问老王论坛:laowang.vip)
- for i in range(data.shape[0]):
7 C1 w1 r$ v6 f4 q. z, d7 x9 e - site1=data.iloc[i]['name']
2 _, f/ V" [+ F# ?% R5 j) w - longitude=float(data.iloc[i]['longitude'])
' L" A1 }5 C/ r! R - latitude=float(data.iloc[i]['latitude']) #分别将经纬度代入,计算与目标之间的欧氏距离; A% ?# A; i7 w) u! `" `7 k& X. w(欢迎访问老王论坛:laowang.vip)
- temp=geodesic((latitude1,longitude1), (latitude,longitude)).m #temp对其遍历即可,这里对比各个地铁站的欧氏距离2 A$ u8 b' `. ?$ v(欢迎访问老王论坛:laowang.vip)
- if temp<distance:
4 @, x; x5 j1 C# Z" x3 C - distance=temp
1 d! e$ C5 M: ` - nearest_subway=site1! L& G1 v: D. d/ M0 l- z1 }(欢迎访问老王论坛:laowang.vip)
- return nearest_subway
复制代码- def subway_line(start,end): #创建点之间的距离
6 s* N$ R) t3 T+ T - file=open('graph.pkl','rb')
, I3 h6 A* r( ?% R - graph=pickle.load(file) #现在我们有了各个地铁站之间的距离存储在graph0 H# ]8 u' I' ?- M5 u8 v( r9 c(欢迎访问老王论坛:laowang.vip)
- costs={} #创建节点的开销表,cost是指从start到该节点的距离( T% \3 t: ]+ P8 b2 K* N5 G: u(欢迎访问老王论坛:laowang.vip)
- parents={}
4 n4 A. a4 P* {! f; h' T8 a - parents[end]=None
. I, m |- V x- o% {/ [ - for node in graph[start].keys():: n$ |; }2 ~, B8 @0 {, E(欢迎访问老王论坛:laowang.vip)
- costs[node]=float(graph[start][node])
' p4 O( O& D0 l; x. D Q - parents[node]=start2 t9 Z- [5 k/ O3 m$ [) u# o' v(欢迎访问老王论坛:laowang.vip)
- costs[end]=float('inf') #终点到起始点距离为无穷大
; w9 U6 f- J) m+ A! Q2 u( v- X+ Q - processed=[] #记录处理过的节点list
h3 A, k& Y, s, U5 o2 A - shortest_path=dijkstra(start,end,graph,costs,processed,parents)
+ M/ E6 s* ?% s( c; Q' c2 ] - return shortest_path
复制代码- #计算图中从start到end的最短路径
1 H0 N5 l2 s& B, [: c - def dijkstra(start,end,graph,costs,processed,parents):
- {3 B! P1 d$ Z, ?" k - #查询到目前开销最小的节点
, U& T$ p \) @) ]9 P - node=find_lowest_cost_node(costs,processed)
% ]; T8 x9 k/ L! k/ W3 a/ O - #使用找到的开销最小节点,计算它的邻居是否可以通过它进行更新
/ @9 p2 {$ u) k6 Z8 P/ Z - #如果所有的节点都在processed里面 就结束- c& {, j, E8 @. Q/ {+ o(欢迎访问老王论坛:laowang.vip)
- while node is not None:4 Q: ~0 t+ q5 |( O, p2 [; j(欢迎访问老王论坛:laowang.vip)
- #获取节点的cost
$ Y" s8 k# b" u5 q# \ - cost=costs[node] #cost 是从node 到start的距离+ d+ P8 x D$ b( R: N; X(欢迎访问老王论坛:laowang.vip)
- #获取节点的邻居
% {4 z% A( m/ m+ Z - neighbors=graph[node]' J3 s z3 J6 E8 I5 G1 N! \(欢迎访问老王论坛:laowang.vip)
- #遍历所有的邻居,看是否可以通过它进行更新4 u" S9 O. E, J P9 f2 B(欢迎访问老王论坛:laowang.vip)
- for neighbor in neighbors.keys():
' j e$ x3 t6 y* e0 a - #计算邻居到当前节点+当前节点的开销
6 O9 q8 ]- Y+ { - new_cost=cost+float(neighbors[neighbor])
! F3 Z) T& x( N W- V2 ~0 ]( p, y) I - if neighbor not in costs or new_cost<costs[neighbor]:
: h8 z6 W7 W2 _+ ^+ T2 O - costs[neighbor]=new_cost
* J4 D; h5 x2 W& e8 O! [ - #经过node到邻居的节点,cost最少
, i) C+ E) Z8 ^7 Y! y7 y$ K9 d( S2 h - parents[neighbor]=node5 G9 y: i# {; V \, A$ P0 G% H2 N. C(欢迎访问老王论坛:laowang.vip)
- #将当前节点标记为已处理
) M- O6 z4 Z7 S3 v# D6 n - processed.append(node)
: U0 X% z! ]# e' S8 J$ G- n - #下一步继续找U中最短距离的节点 costs=U,processed=S
1 \5 q9 A+ H0 |) J7 v - node=find_lowest_cost_node(costs,processed)
复制代码- def find_lowest_cost_node(costs,processed):
* T8 _$ W$ w3 I - #初始化数据: G) _& V/ ]( ^: }! A8 Q(欢迎访问老王论坛:laowang.vip)
- lowest_cost=float('inf') #初始化最小值为无穷大
7 o; _. | n" O; ?2 O - lowest_cost_node=None o( H) v; i; U9 i/ B( o! u/ p(欢迎访问老王论坛:laowang.vip)
- #遍历所有节点
* J: K3 c# d! L0 C/ G3 P - for node in costs:
/ |3 `) }/ V0 F8 D2 f - #如果该节点没有被处理
" Q; J5 j: z, V" p C - if not node in processed:
4 S. k3 t) O, x" D+ J - #如果当前的节点的开销比已经存在的开销小,那么更新该节点为最小开销的节点
; @' o9 V* ]3 x% F3 ` - if costs[node]<lowest_cost:
/ _2 O4 v& S& Y4 ? - lowest_cost=costs[node]$ R# x2 p7 G5 v0 N- y(欢迎访问老王论坛:laowang.vip)
- lowest_cost_node=node
1 U) [$ V3 m# V( K$ y" U - return lowest_cost_node
复制代码 上面这段基本上搬运的,主要是他代码已经写的很好了,注释也写的不错,但我写的时候爬虫调不出来(反爬虫技术可以的),最后是我手动去地图里找经纬度得到的结果。
+ W: u0 w5 E2 z9 q# S& W引用:https://blog.csdn.net/fengdu78/article/details/111570695: J8 h# }6 J8 F h(欢迎访问老王论坛:laowang.vip)
' ~7 c2 |/ t. d( h& L1 n: R& a( E0 r( K% N% E(欢迎访问老王论坛:laowang.vip)
& o" x9 e1 K! b4 ~, T: u \7 Z(欢迎访问老王论坛:laowang.vip)
A*算法:这个算法也是非常著名的算法,与Dijkstra算法相比,增加了启发式函数 ---- 启发函数的好坏直接决定了算法的效率和结果。由此衍生的D*(动态A算法)算法也被广泛运用于各类游戏中。D*的搜索效率高的原因就在于,当计划路径上某点被阻碍,因为是反向指针,可以定位到被堵节点的上一节点。也就是说只需重新搜索很小的一部分,其余部分仍然使用初始规划出的路径,大大提高了重规划的效率。5 h$ E. I6 F ?# k O(欢迎访问老王论坛:laowang.vip)
$ i+ C9 P7 R% B5 [(欢迎访问老王论坛:laowang.vip)
7 ^6 U o6 S9 w& Z* }+ ~. i/ O额外补充-dfs&bfs逻辑# b ~9 }& d# S7 H2 h8 W(欢迎访问老王论坛:laowang.vip)
深度搜索(dfs)和广度搜索(bfs)的算法逻辑可以说是最具有代表性的,基本任何有关于寻路的算法都没法绕开他俩。我担心可能没了解这2个算法直接去看Djkta和A*会有些懵逼& N* r7 d1 |) D/ G1 T; l! L* I2 a(欢迎访问老王论坛:laowang.vip)
% _- [7 c) e: @8 f* q(欢迎访问老王论坛:laowang.vip)
深度搜索(dfs)
* M2 U7 T. y/ G' p' w1 o/ ?& V t/ G1 y
: W: K4 p7 a$ ?6 `- G; c% @( Cdfs就和它字面意思一样,是往更深的地方找(deepfound): C1 x3 A3 M0 t0 _8 }7 F+ W9 ](欢迎访问老王论坛:laowang.vip)
它的核心思想很简单:
; Y, D0 T# Y2 G) X* J* j; I一直往前走,走不通就回头
/ h/ B& Q- q( ?. M
- p: K3 _8 k# p* c' G. F顺序?当然是长幼啦,有长立长无长立幼 (1会先找2而非6,在2时会先找4而非5 ,直到4发现3 发现无路可走再back回去)
) }: i; o0 P. \6 g大致伪代码如下! b# j5 [. J. \+ D4 n(欢迎访问老王论坛:laowang.vip)
- input 地图$ P- ?9 e# k" ~! L; ?(欢迎访问老王论坛:laowang.vip)
- create 已经过点9 I0 b3 c# Y$ s) ^0 j(欢迎访问老王论坛:laowang.vip)
- create 结果存储5 J5 }% V8 N; p; b# `3 o7 a/ E: G: ?0 L(欢迎访问老王论坛:laowang.vip)
- ( f2 a8 Q$ N1 U0 k o" l* X(欢迎访问老王论坛:laowang.vip)
- type node{& R6 n4 L0 R) V2 m(欢迎访问老王论坛:laowang.vip)
- node nextNode[];//下一节点们" X- F5 {( T8 V5 B(欢迎访问老王论坛:laowang.vip)
- nodeval;//节点标记物0 R! @; H [% `) b; @# F" d" b(欢迎访问老王论坛:laowang.vip)
- }% f) a5 k: W9 i. F8 ? L(欢迎访问老王论坛:laowang.vip)
- B) a- m/ H; V7 J. A; ?- T(欢迎访问老王论坛:laowang.vip)
$ E' h" O) x" H _- w, Q1 {- //这里开始是函数+ Q6 S5 [# w+ u4 D(欢迎访问老王论坛:laowang.vip)
- fun dfs(node* nowPoint)
) | Z, p5 s2 z6 Y - {
/ o& z( _% A/ n7 I# y' S$ C - define u 为 nextNode[] size9 n- P" X7 z1 K% z* f; B(欢迎访问老王论坛:laowang.vip)
- int key;
' G g1 ?; T0 Y& v. E - 7 b, j2 I7 {3 o! u2 k4 s( Q(欢迎访问老王论坛:laowang.vip)
- for i in u {
r/ ^ ^. v/ V5 r$ I: g# y - if (nowPoint.noteval == target)
4 {- e4 Q, ] \. n/ b# N+ V# r - {/ n D/ X+ {4 k(欢迎访问老王论坛:laowang.vip)
- 结果存储[0] = nowPoint.noteval;
6 W$ S$ ]' X( w' J5 z - return 0 ;) f" {! Q' R) A' _7 O7 S6 G3 \! Z(欢迎访问老王论坛:laowang.vip)
- } 5 T _: B4 ^7 i* F% y; p! W1 S2 P(欢迎访问老王论坛:laowang.vip)
- else if( key = (dfs(nowPoint->nextNode[i])) != -1 ) //如果dfs这次没有返回负1(即 找到终点了)% X! o( s+ c/ g1 o(欢迎访问老王论坛:laowang.vip)
- {
\' d! ^3 z C, A - 结果存储[key] = nowPoint.noteval;
1 ^# t7 ]* N$ r7 K$ v - return key+1; 4 L( F5 A9 P- j. v+ R(欢迎访问老王论坛:laowang.vip)
- } % v4 u5 t$ S7 }) G(欢迎访问老王论坛:laowang.vip)
- else6 S3 y S& _5 D. n* u(欢迎访问老王论坛:laowang.vip)
- {
9 X- o. s" [! Q% t3 ? - /********************/
! K/ V. o; O0 W& F! q - /** nothing **/% Z' r X! x. _) Z$ v- n, t(欢迎访问老王论坛:laowang.vip)
- /********************/
, T/ v- j' }( u - }
; m) u; Y: i4 f. ?
- g# [" Q p( m& v& Q- ' s+ v8 \5 Z- g8 R2 a( G8 R(欢迎访问老王论坛:laowang.vip)
- } ' a( @* j. e/ ^1 C3 Q(欢迎访问老王论坛:laowang.vip)
- return -1;5 B0 d7 m" o8 U4 S/ s(欢迎访问老王论坛:laowang.vip)
- } c: t7 X3 K2 D9 i: t0 M2 X(欢迎访问老王论坛:laowang.vip)
复制代码 就那么短,你只需要确定是不是就行了
. J; Y' P% K+ d" p! K" f4 k是不是很简单:p 但是这就是一个比较原始的寻路算法的模样-顺其自然流8 h) p2 K2 U* }" J(欢迎访问老王论坛:laowang.vip)
- d& P: r( L, H. H9 e在dfs算法中,你需要做的就是 询问+上抛4 q; _3 Q3 C4 U! p+ Z* P- h(欢迎访问老王论坛:laowang.vip)
当然,dfs算法唯一能保证的就是‘找得到路’,这也是为什么纯粹的dfs算法不常用于生产环境中
: N& s" ?* T" s# e) {: w, g" w s) E3 s, Q/ Q3 p- q(欢迎访问老王论坛:laowang.vip)
2 l1 \& C% @" A+ g# s广度搜索(bfs)1 n, T% V8 h( y(欢迎访问老王论坛:laowang.vip)
知道深度,广度就很容易联想了 先找周围嘛 无论如何,先找周围$ C) ~2 N2 ` Q7 f; D! H(欢迎访问老王论坛:laowang.vip)
+ Z1 J1 j/ G' i* \5 g H这里不进行代码补充了,只简单地说一下逻辑. d) {0 A2 ?# r( s* w; X(欢迎访问老王论坛:laowang.vip)
0 _! ]2 E# M+ ?: R9 L W( f这个算法分以下几步:
5 _( e7 z; F: j( D* I, J0,准备一个队列(就是那个queue),然后丢入我们的起点 命运的齿轮开始拨动
' _' A! C9 F. Z2 M9 Z/ D3 T# q9 ?5 v' l( m- `6 Y, _(欢迎访问老王论坛:laowang.vip)
1,询问当前节点是否终点?
* j z! T. {& r! s2,将自己的nextNode 塞入队列中(除了访问过的)
& C- E k$ f" C. Z7 i& e9 _ X3,从队列里output一个节点,作为下一个‘当前节点’
$ Y) X4 ^2 l, ]( \/ B& s0 v
" C' t/ q2 @( i9 V; p w然后就是循环1~3
% l% n R7 K, s9 o! \8 o0 E+ W0 z5 N7 h9 `, L(欢迎访问老王论坛:laowang.vip)
是不是很简单?9 n/ l A7 c) y' d. p(欢迎访问老王论坛:laowang.vip)
n: Z0 N4 K u5 @(欢迎访问老王论坛:laowang.vip)
这2个算法都属于随性流,一个适合终点远一个适合终点近。但无论如何这俩都暂时没有比较最优的功能
# a& s+ ?$ h& X8 `5 \& e因为他们刚~满~十~八~岁~的审敛条件就只是找得到路
# }2 y, ^* T5 J1 [0 {
! Q) ?" R( \0 ?( S但你可以发现哦?如果将dfs的‘长幼判断’换成‘最优判断’,将呆值传递换为矩阵存储 就是dj算法了诶(a*也是类似的)
8 C7 D+ h1 q, [; ^9 g+ g而bfs作为‘扩散式搜索’显然地在进行多点寻路时效用更加明显0 Y( M4 w: A2 s" ^* P(欢迎访问老王论坛:laowang.vip)
如果觉得寻路算法很难的话,不妨先从dfs&bfs开始了解
: m! h1 M' s5 k4 U9 i7 M; V3 W5 R. ?" V1 [(欢迎访问老王论坛:laowang.vip)
$ ^7 T$ S' @8 K9 f/ ?& [6 w2 j3 {' a1 b4 h# W" ?8 u(欢迎访问老王论坛:laowang.vip)
- N, f3 t5 Q7 e& W, n2 b8 h6 Y(欢迎访问老王论坛:laowang.vip)
|
-
A*寻路算法
评分
-
查看全部评分
|