赞 | 13 |
VIP | 642 |
好人卡 | 62 |
积分 | 27 |
经验 | 117527 |
最后登录 | 2024-10-4 |
在线时间 | 2630 小时 |
Lv3.寻梦者
- 梦石
- 0
- 星屑
- 2749
- 在线时间
- 2630 小时
- 注册时间
- 2013-1-16
- 帖子
- 5657
|
帖子有讨论价值于是挖个坟(如有讨论请点评)
寻路/移动范围的算法通常可以参考图的广度优先(百度搜索“广度优先”的结果适用于更一般的图,初学者看起来比较吃力)。
具体思路就是不断搜索待搜索节点周围的节点直至满足约束条件搜索结束。
首先要有一个列表openlist,用来储存待搜索的节点。
当然还要有closelist列表,储存已搜索的节点。
最初,这两个表都是空的。
一开始,往openlist里塞进起点。
以下是核心
从openlist里拎出一个节点设为当前节点,
寻找周围尚未搜索(即closelist均无的节点)并可以到达的节点。
如果周围的点存在于openlist,则要判断如果从当前节点到达该点是否更省力,如果是则修改该点的消耗。
将找到的点塞进openlist,并记录各个点的消耗。
当openlist为空时,中断循环;否则,以上循环。
核心结束
来张图助助兴……
注释:
图1:紫色为起点,执行第一次循环后的结果。红色表示openlist的点,绿色钩表示closelist已经存在该点;
图2:新的一轮循环。3号图块由于已经存在于closelist,故未添加至openlist;
图3:若干次循环后;
图4:由于灰色块不可到达,故也没有添加至openlist。 |
|