编写更快的Python物理模拟器
我最近在用Python写自己的物理引擎，算是一种物理和编程的练习。一开始我跟着这个教程学，进展还不错，但后来我发现了thomas jakobsen写的“高级角色物理”这篇文章，里面讲了用Verlet积分法来做模拟，我觉得特别有意思。
我尝试用Verlet积分法写一个简单的物理模拟器，但发现这比我想象的要难一些。我在网上找了一些示例程序来阅读，偶然发现了这个用Python写的例子，还有这个使用Processing的教程。
让我印象深刻的是Processing版本的运行速度。光是布料模拟就有2400个不同的点在运算，这还不包括其他物体。
而Python的例子只用了256个粒子来模拟布料，运行速度大约是每秒30帧。我试着把粒子数量增加到2401（因为这个程序需要是平方的），结果运行速度降到了每秒大约3帧。
这两个程序的工作原理大致相同，都是把粒子对象存储在一个列表中，然后遍历这个列表，调用每个粒子的“更新位置”方法。举个例子，这是Processing代码中计算每个粒子新位置的部分：
for (int i = 0; i < pointmasses.size(); i++) {
PointMass pointmass = (PointMass) pointmasses.get(i);
pointmass.updateInteractions();
pointmass.updatePhysics(fixedDeltaTimeSeconds);
}
编辑：这是我之前提到的Python版本的代码：
"""
verletCloth01.py
Eric Pavey - 2010-07-03 - www.akeric.com
Riding on the shoulders of giants.
I wanted to learn now to do 'verlet cloth' in Python\Pygame. I first ran across
this post \ source:
http://forums.overclockers.com.au/showthread.php?t=870396
http://dl.dropbox.com/u/3240460/cloth5.py
Which pointed to some good reference, that was a dead link. After some searching,
I found it here:
http://www.gpgstudy.com/gpgiki/GDC%202001%3A%20Advanced%20Character%20Physics
Which is a 2001 SIGGRAPH paper by Thomas Jakobsen called:
"GDC 2001: Advanced Characer Physics".
This code is a Python\Pygame interpretation of that 2001 Siggraph paper. I did
borrow some code from 'domlebo's source code, it was a great starting point. But
I'd like to think I put my own flavor on it.
"""
#--------------
# Imports & Initis
import sys
from math import sqrt
# Vec2D comes from here: http://pygame.org/wiki/2DVectorClass
from vec2d import Vec2d
import pygame
from pygame.locals import *
pygame.init()
#--------------
# Constants
TITLE = "verletCloth01"
WIDTH = 600
HEIGHT = 600
FRAMERATE = 60
# How many iterations to run on our constraints per frame?
# This will 'tighten' the cloth, but slow the sim.
ITERATE = 2
GRAVITY = Vec2d(0.0,0.05)
TSTEP = 2.8
# How many pixels to position between each particle?
PSTEP = int(WIDTH*.03)
# Offset in pixels from the top left of screen to position grid:
OFFSET = int(.25*WIDTH)
#-------------
# Define helper functions, classes
class Particle(object):
"""
Stores position, previous position, and where it is in the grid.
"""
def __init__(self, screen, currentPos, gridIndex):
# Current Position : m_x
self.currentPos = Vec2d(currentPos)
# Index [x][y] of Where it lives in the grid
self.gridIndex = gridIndex
# Previous Position : m_oldx
self.oldPos = Vec2d(currentPos)
# Force accumulators : m_a
self.forces = GRAVITY
# Should the particle be locked at its current position?
self.locked = False
self.followMouse = False
self.colorUnlocked = Color('white')
self.colorLocked = Color('green')
self.screen = screen
def __str__(self):
return "Particle <%s, %s>"%(self.gridIndex[0], self.gridIndex[1])
def draw(self):
# Draw a circle at the given Particle.
screenPos = (self.currentPos[0], self.currentPos[1])
if self.locked:
pygame.draw.circle(self.screen, self.colorLocked, (int(screenPos[0]),
int(screenPos[1])), 4, 0)
else:
pygame.draw.circle(self.screen, self.colorUnlocked, (int(screenPos[0]),
int(screenPos[1])), 1, 0)
class Constraint(object):
"""
Stores 'constraint' data between two Particle objects. Stores this data
before the sim runs, to speed sim and draw operations.
"""
def __init__(self, screen, particles):
self.particles = sorted(particles)
# Calculate restlength as the initial distance between the two particles:
self.restLength = sqrt(abs(pow(self.particles[1].currentPos.x -
self.particles[0].currentPos.x, 2) +
pow(self.particles[1].currentPos.y -
self.particles[0].currentPos.y, 2)))
self.screen = screen
self.color = Color('red')
def __str__(self):
return "Constraint <%s, %s>"%(self.particles[0], self.particles[1])
def draw(self):
# Draw line between the two particles.
p1 = self.particles[0]
p2 = self.particles[1]
p1pos = (p1.currentPos[0],
p1.currentPos[1])
p2pos = (p2.currentPos[0],
p2.currentPos[1])
pygame.draw.aaline(self.screen, self.color,
(p1pos[0], p1pos[1]), (p2pos[0], p2pos[1]), 1)
class Grid(object):
"""
Stores a grid of Particle objects. Emulates a 2d container object. Particle
objects can be indexed by position:
grid = Grid()
particle = g[2][4]
"""
def __init__(self, screen, rows, columns, step, offset):
self.screen = screen
self.rows = rows
self.columns = columns
self.step = step
self.offset = offset
# Make our internal grid:
# _grid is a list of sublists.
# Each sublist is a 'column'.
# Each column holds a particle object per row:
# _grid =
# [[p00, [p10, [etc,
# p01, p11,
# etc], etc], ]]
self._grid = []
for x in range(columns):
self._grid.append([])
for y in range(rows):
currentPos = (x*self.step+self.offset, y*self.step+self.offset)
self._grid[x].append(Particle(self.screen, currentPos, (x,y)))
def getNeighbors(self, gridIndex):
"""
return a list of all neighbor particles to the particle at the given gridIndex:
gridIndex = [x,x] : The particle index we're polling
"""
possNeighbors = []
possNeighbors.append([gridIndex[0]-1, gridIndex[1]])
possNeighbors.append([gridIndex[0], gridIndex[1]-1])
possNeighbors.append([gridIndex[0]+1, gridIndex[1]])
possNeighbors.append([gridIndex[0], gridIndex[1]+1])
neigh = []
for coord in possNeighbors:
if (coord[0] < 0) | (coord[0] > self.rows-1):
pass
elif (coord[1] < 0) | (coord[1] > self.columns-1):
pass
else:
neigh.append(coord)
finalNeighbors = []
for point in neigh:
finalNeighbors.append((point[0], point[1]))
return finalNeighbors
#--------------------------
# Implement Container Type:
def __len__(self):
return len(self.rows * self.columns)
def __getitem__(self, key):
return self._grid[key]
def __setitem__(self, key, value):
self._grid[key] = value
#def __delitem__(self, key):
#del(self._grid[key])
def __iter__(self):
for x in self._grid:
for y in x:
yield y
def __contains__(self, item):
for x in self._grid:
for y in x:
if y is item:
return True
return False
class ParticleSystem(Grid):
"""
Implements the verlet particles physics on the encapsulated Grid object.
"""
def __init__(self, screen, rows=49, columns=49, step=PSTEP, offset=OFFSET):
super(ParticleSystem, self).__init__(screen, rows, columns, step, offset)
# Generate our list of Constraint objects. One is generated between
# every particle connection.
self.constraints = []
for p in self:
neighborIndices = self.getNeighbors(p.gridIndex)
for ni in neighborIndices:
# Get the neighbor Particle from the index:
n = self[ni[0]][ni[1]]
# Let's not add duplicate Constraints, which would be easy to do!
new = True
for con in self.constraints:
if n in con.particles and p in con.particles:
new = False
if new:
self.constraints.append( Constraint(self.screen, (p,n)) )
# Lock our top left and right particles by default:
self[0][0].locked = True
self[1][0].locked = True
self[-2][0].locked = True
self[-1][0].locked = True
def verlet(self):
# Verlet integration step:
for p in self:
if not p.locked:
# make a copy of our current position
temp = Vec2d(p.currentPos)
p.currentPos += p.currentPos - p.oldPos + p.forces * TSTEP**2
p.oldPos = temp
elif p.followMouse:
temp = Vec2d(p.currentPos)
p.currentPos = Vec2d(pygame.mouse.get_pos())
p.oldPos = temp
def satisfyConstraints(self):
# Keep particles together:
for c in self.constraints:
delta = c.particles[0].currentPos - c.particles[1].currentPos
deltaLength = sqrt(delta.dot(delta))
try:
# You can get a ZeroDivisionError here once, so let's catch it.
# I think it's when particles sit on top of one another due to
# being locked.
diff = (deltaLength-c.restLength)/deltaLength
if not c.particles[0].locked:
c.particles[0].currentPos -= delta*0.5*diff
if not c.particles[1].locked:
c.particles[1].currentPos += delta*0.5*diff
except ZeroDivisionError:
pass
def accumulateForces(self):
# This doesn't do much right now, other than constantly reset the
# particles 'forces' to be 'gravity'. But this is where you'd implement
# other things, like drag, wind, etc.
for p in self:
p.forces = GRAVITY
def timeStep(self):
# This executes the whole shebang:
self.accumulateForces()
self.verlet()
for i in range(ITERATE):
self.satisfyConstraints()
def draw(self):
"""
Draw constraint connections, and particle positions:
"""
for c in self.constraints:
c.draw()
#for p in self:
# p.draw()
def lockParticle(self):
"""
If the mouse LMB is pressed for the first time on a particle, the particle
will assume the mouse motion. When it is pressed again, it will lock
the particle in space.
"""
mousePos = Vec2d(pygame.mouse.get_pos())
for p in self:
dist2mouse = sqrt(abs(pow(p.currentPos.x -
mousePos.x, 2) +
pow(p.currentPos.y -
mousePos.y, 2)))
if dist2mouse < 10:
if not p.followMouse:
p.locked = True
p.followMouse = True
p.oldPos = Vec2d(p.currentPos)
else:
p.followMouse = False
def unlockParticle(self):
"""
If the RMB is pressed on a particle, if the particle is currently
locked or being moved by the mouse, it will be 'unlocked'/stop following
the mouse.
"""
mousePos = Vec2d(pygame.mouse.get_pos())
for p in self:
dist2mouse = sqrt(abs(pow(p.currentPos.x -
mousePos.x, 2) +
pow(p.currentPos.y -
mousePos.y, 2)))
if dist2mouse < 5:
p.locked = False
#------------
# Main Program
def main():
# Screen Setup
screen = pygame.display.set_mode((WIDTH, HEIGHT))
clock = pygame.time.Clock()
# Create our grid of particles:
particleSystem = ParticleSystem(screen)
backgroundCol = Color('black')
# main loop
looping = True
while looping:
clock.tick(FRAMERATE)
pygame.display.set_caption("%s -- www.AKEric.com -- LMB: move\lock - RMB: unlock - fps: %.2f"%(TITLE, clock.get_fps()) )
screen.fill(backgroundCol)
# Detect for events
for event in pygame.event.get():
if event.type == pygame.QUIT:
looping = False
elif event.type == MOUSEBUTTONDOWN:
if event.button == 1:
# See if we can make a particle follow the mouse and lock
# its position when done.
particleSystem.lockParticle()
if event.button == 3:
# Try to unlock the current particles position:
particleSystem.unlockParticle()
# Do stuff!
particleSystem.timeStep()
particleSystem.draw()
# update our display:
pygame.display.update()
#------------
# Execution from shell\icon:
if __name__ == "__main__":
print "Running Python version:", sys.version
print "Running PyGame version:", pygame.ver
print "Running %s.py"%TITLE
sys.exit(main())
因为这两个程序的工作方式差不多，但Python版本的速度慢得多，这让我开始思考：
- 这种性能差异是Python的特性吗？
- 如果我想让自己的Python程序性能更好，应该做些什么不同的事情？比如把所有粒子的属性存储在一个数组里，而不是使用单独的对象等等。
编辑：已回答！！
@Mr E在评论中链接的PyCon演讲，以及@A. Rosa的回答和相关资源，都极大地帮助我更好地理解如何写出优秀且快速的Python代码。我现在把这个页面收藏起来，以备将来参考 :D
4 个回答
5
我还建议你了解其他的物理引擎。有一些开源的引擎使用了不同的方法来计算“物理效果”。
- Newton Game Dynamics
- Chipmunk
- Bullet
- Box2D
- ODE（开放动力学引擎）
大多数引擎也有对应的移植版本：
- Pymunk
- PyBullet
- PyBox2D
- PyODE
如果你仔细阅读这些引擎的文档，通常会看到它们的说明说是为了速度进行了优化（30帧每秒到60帧每秒）。但是如果你认为它们可以在计算“真实”物理的同时达到这个速度，那你就错了。大多数引擎计算物理效果的精度足够高，以至于普通用户无法在视觉上区分“真实”的物理行为和“模拟”的物理行为。不过，如果你仔细研究误差，你会发现这些误差在写游戏时是可以忽略不计的。但如果你想进行真正的物理模拟，这些引擎就没什么用处了。
所以我想说，如果你在做真实的物理模拟，按照设计来说，你的速度会比这些引擎慢，而且你永远也追不上其他的物理引擎。
5
如果你用写Java的方式来写Python，当然会慢了，因为Java的写法不太适合Python。
这种性能差异是Python的特性吗？如果我想让自己的Python程序运行得更快，我应该怎么做呢？比如，把所有粒子的属性放在一个数组里，而不是用单独的对象等等。
不看到你的代码，很难说。
这里有一些Python和Java之间的不同之处，这些差异有时会影响性能：
处理使用的是即时模式画布，如果你想在Python中获得类似的性能，你也需要使用即时模式画布。大多数图形用户界面框架（包括Tkinter画布）使用的是保留模式，这种模式更容易使用，但本质上比即时模式慢。你需要使用像pygame、SDL或Pyglet提供的即时模式画布。
Python是动态语言，这意味着实例成员访问、模块成员访问和全局变量访问是在运行时解决的。在Python中，实例成员、模块成员和全局变量的访问实际上是字典访问。而在Java中，这些是在编译时解决的，因此速度更快。可以将经常访问的全局变量、模块变量和属性缓存到局部变量中。
在Python 2.x中，range()会生成一个具体的列表，而在Python中，使用迭代器进行迭代，比如
for item in list，通常比使用迭代变量的方式更快，比如for n in range(len(list))。你几乎总是应该直接使用迭代器进行迭代，而不是使用range(len(...))。Python的数字是不可变的，这意味着任何算术计算都会分配一个新对象。这是普通Python不太适合低级计算的原因之一；大多数希望能够进行低级计算而不需要写C扩展的人，通常会使用cython、psyco或numpy。不过，通常只有在你有数百万次计算时，这个问题才会显现出来。
这些只是部分、不完整的列表，还有很多其他原因导致将Java代码翻译成Python时效果不佳。如果不看到你的代码，就无法判断你需要做什么不同的事情。优化后的Python代码通常与优化后的Java代码看起来非常不同。
8
在Python Wiki的性能提示部分，有一篇Guido van Rossum的文章。文章的结尾提到了一句话：
如果你觉得需要速度，那就使用内置函数——没有什么能比用C语言写的循环更快。
这篇文章还列出了一些优化循环的建议。我推荐这两个资源，因为它们提供了关于如何优化Python代码的具体和实用的建议。
还有一个著名的基准测试网站benchmarksgame.alioth.debian.org，你可以在这里找到不同程序和语言在不同机器上的比较。可以看出，有很多变量在影响结果，所以很难简单地说“Java比Python快”。这通常用一句话总结：“语言没有速度；实现才有速度”。
在你的代码中，可以使用更Pythonic和更快的内置函数替代一些写法。例如，有几个嵌套循环（其中一些不需要处理整个列表），可以用imap或列表推导式来重写。PyPy也是一个提高性能的有趣选择。我不是Python优化方面的专家，但有很多非常有用的技巧（注意，不要在Python中写Java就是其中之一！）。
相关资源和其他问题：