Python游戏之运动物体寻路

2024-07-16 11:15| 来源: 网络整理| 查看: 265

上一篇文章主要完成了游戏地图的创建，其中简单为游戏寻路做了一点准备，就是格栅背景地图。游戏场景中的各种山川、河流、楼阁等都都可以视为为某种运动精灵的障碍物，那么精灵如何绕过障碍物运动都自己的目的地呢？目前关于寻路的算法有很多，最常见的就是A-Star算法，也叫A星算法。典型的A-star算法处理的是运动物体和格栅大小一致，如果运动物体比格栅小，自然没有任何问题。如果运动物体比格栅大，典型的A-star算法就不能处理了。那么是不是A-star方法就不能处理了呢？不是，针对这个问题，国外有人提出了叫做 Brushfire的算法。据说得google才能找到。我简单看了一下，应该也是可以实现的。有兴趣的朋友可以自行探索。典型的Astar算法网上有很多详细的讲解，有一位大拿的文章请参考，还有一些前人给出了C/C++/JAVA/JSP等各种语言的实现。这里就不再重复了。本文解决的问题是大于格栅大小的物体的寻路问题，并尽可能实现任何大小的物体寻路。下面有几个示意图可以先看一下。在这里插入图片描述为了方便理解，这里用虚线展示精灵的运动路径，实际上是精灵的左上角运动轨迹。有些Astar算法只允许精灵在水平和垂直方向运动，有些可以8个方向(45度角）。这其实没有本质的区别，只是在寻路过程中对合格邻接点的筛选策略不同而已。完全可以根据自己的需要来处理。好了，现在开始展示A-star算法。既然涉及到格栅，那么格栅怎么描述呢？就是点的集合。先描述点：

class Node: def __init__(self, point, target, father=None): self.point = point self.father = father if father is not None: self.gCost = father.gCost + self.get_gCost(father.point) self.hCost = self.get_hCost(target) self.fCost = self.gCost + self.hCost else: self.gCost = 0 self.hCost = 0 self.fCost = 0 # 计算自己到父节点的gCost。如果到父节点为 45 度方向，设置 gCost 为 14，否则设为 10 def get_gCost(self, father): if abs(self.point[0] - father[0]) + abs(self.point[1] - father[1]) == 2: return 14 return 10 def get_hCost(self, target): return (abs(target[0] - self.point[0]) + abs(target[1] - self.point[1])) * 10 def reset_father(self, father, newgCost): if father is not None: self.gCost = newgCost self.fCost = self.gCost + self.hCost self.father = father

关于cost的设置方法，有很多策略，有兴趣的可以进一步研究。这里使用最简单的实现，便于理解。 point是什么呢？就是格栅点的（X轴索引，Y轴索引），一个Tuple。有了Node，下面就是A-Star了。类属性定义：

class AStar: # stat and target 是Tuple (x, y), 是格栅的索引点，不是像素坐标。 # size 为寻径主体的大小，表示边长为格栅尺寸的倍数 # 对于非正方形主体，将其边长大的边计算size就可以 def __init__(self, grids, start, target, size): self.grids = grids self.size = size self.start = self.adjust_position(start) self.target = self.adjust_position(target) self.startNode = Node(self.start, self

【本文地址】

Python游戏之运动物体寻路

Python游戏之运动物体寻路

今日新闻

推荐新闻