检测是否在python中跨越矩形。 需要速度提升

我正在写一个自上而下的人vs机器人射击游戏。 游戏现在可以工作,但是如果我有一个体面的大小的级别,当你被机器人追赶的时候,它会运行的很慢。 漫游时可以达到60fps,但尾巴上的机器人会非常缓慢。

我已经把问题的根源追溯到机器人决定他们的视线是否被墙壁阻挡的那部分代码。 该代码通过查看机器人中心和玩家中心形成的线段是否与墙壁相交而起作用。

我已经写了这个algorithm来看看一个线段是否通过矩形:

for wall in wall_rects: #is wall between the robot and player: if man.rect.centerx < wall.rect.centerx < self.rect.centerx or\ man.rect.centerx > wall.rect.centerx > self.rect.centerx or\ man.rect.centery < wall.rect.centery < self.rect.centery or\ man.rect.centery > wall.rect.centery > self.rect.centery: r = [] #are the corners above or below the line between the man and robot r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.top-man.rect.centery)\ - (self.rect.centery-man.rect.centery)*(wall.rect.left-man.rect.centerx)) r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.top-man.rect.centery)\ - (self.rect.centery-man.rect.centery)*(wall.rect.right-man.rect.centerx)) r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.bottom-man.rect.centery)\ - (self.rect.centery-man.rect.centery)*(wall.rect.left-man.rect.centerx)) r.append((self.rect.centerx-man.rect.centerx)*(wall.rect.bottom-man.rect.centery)\ - (self.rect.centery-man.rect.centery)*(wall.rect.right-man.rect.centerx)) if not(max(r) < 0 or min(r) > 0): #if all of the corners are not on the same #side then the line does go through the wall break else: #IT SEES YOU! >:D 

然而,在我的testing水平上,还没有足够快的速度检查所有450个墙。 我的困难是要么加快速度,要么找出哪些墙壁值得检查视线阻塞。 我试着检查墙壁和机器人之间的距离,看看它是否比机器人更接近机器人,从而减慢了机器人的速度。

有什么建议么?

编辑:
我忘记提到,在这个游戏中,当墙壁被放置在一个25X25像素的方格上时,你可以随意移动任何方向的距离,机器人也是如此,但是下面的建议看起来还是很有帮助的。

您可以减less使用空间散列(或空间分区)检查的墙的数量。 这是一个数据结构,可以回答这个问题:“这个地区有什么物体?”在你的情况下,物体是墙壁。 你只需要检查线路所经过的区域而不是所有的墙壁。 网格是空间散列的一种forms,但也有其他forms。

本文末尾有一段关于一条线与空间散列相交的部分。 正如nihohit提到的,你可以使用一个画线algorithm。

然而,接下来的问题是,你是否为每个机器人做这个? 如果是的话,你会多次穿过所有的墙壁。 由于玩家的位置每次都可以使用更智能的algorithm。 而不是看每个敌人,询问玩家是否可见,请问一次,玩家可以看到哪些敌人。

roguelike社区收集了一些关于视野问题的资源。

看起来你有一些2D网格去那里 – 也许Bresenham的线algorithm将在网格上运行时解决问题。