16

私は、物理とプログラミングの演習として、Python で独自の物理エンジンを作成して遊んでいます。ここにあるチュートリアルに従うことから始めました。それはうまくいきましたが、その後、Thomas jakobsen による「Advanced character physics」という記事を見つけました。この記事では、シミュレーションに Verlet 統合を使用する方法が取り上げられており、興味深いものでした。

verlet 統合を使用して、独自の基本的な物理シミュレーターを作成しようとしていますが、最初に予想したよりも少し難しいことがわかりました。私はサンプルプログラムを読んで外に出ていて、Python で書かれたこのプログラムに出くわし、Processing を使用するこのチュートリアルも見つけました。

Processing バージョンで印象に残っているのは、実行速度の速さです。布だけでも 2400 の異なるポイントがシミュレートされていますが、これにはボディは含まれていません。

Python の例では、クロスに 256 個のパーティクルのみを使用しており、毎秒約 30 フレームで実行されます。パーティクルの数を 2401 に増やしてみました (そのプログラムが機能するには正方形である必要があります)、約 3 fps で実行されました。


これらはどちらも、パーティクル オブジェクトのインスタンスをリストに格納し、リストを反復処理して、各パーティクルの「位置の更新」メソッドを呼び出すことによって機能します。例として、これは各パーティクルの新しい位置を計算する処理スケッチのコードの一部です。

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

4 に答える 4

8

PythonWikiのパフォーマンスのヒントのセクションにリンクされているGuidovanRossumの記事があります。結論として、あなたは次の文章を読むことができます:

スピードの必要性を感じたら、組み込み関数を試してみてください。Cで書かれたループに勝るものはありません。

エッセイは、ループ最適化のガイドラインのリストに続きます。Pythonコードの最適化について具体的かつ実践的なアドバイスを提供するため、両方のリソースをお勧めします。

また、benchmarksgame.alioth.debian.orgには有名なベンチマークのグループがあり異なるマシンのさまざまなプログラムや言語間の比較を見つけることができます。ご覧のとおり、 JavaがPythonよりも高速であるため、不可能な状態を可能にする変数がたくさんあります。これは通常、「言語には速度がありません。実装には速度があります」という文に要約されています。

コードでは、組み込み関数を使用して、より多くのpythonicでより高速な代替手段を適用できます。imapたとえば、リスト内包表記を使用して書き換えることができるネストされたループがいくつかあります(リスト全体を処理する必要がないものもあります)。PyPyは、パフォーマンスを向上させるためのもう1つの興味深いオプションです。私はPythonの最適化の専門家ではありませんが、非常に役立つヒントがたくさんあります(PythonでJavaを記述しないこともその1つです!)。

SOに関するリソースおよびその他の関連する質問:

于 2013-03-13T02:02:01.447 に答える
5

他の物理エンジンについても読むことをお勧めします。「物理学」を計算するためにさまざまな方法を使用するいくつかのオープンソースエンジンがあります。

  • ニュートンゲームダイナミクス
  • シマリス
  • 銃弾
  • Box2D
  • ODE(Open Dynamics Engine)

ほとんどのエンジンのポートもあります。

  • ピマンク
  • PyBullet
  • PyBox2D
  • PyODE

これらのエンジンのドキュメントを読むと、速度が最適化されている(30fps〜60fps)という記述がよくあります。しかし、「実際の」物理学を計算しているときに彼らがこれを行うことができると思うなら、あなたは間違っています。ほとんどのエンジンは、通常のユーザーが「実際の」物理的動作と「シミュレートされた」物理的動作を光学的に区別できないポイントまで物理を計算します。ただし、エラーを調査する場合、ゲームを作成する場合は無視できます。しかし、物理学をやりたいのであれば、それらのエンジンはすべて役に立たない。そのため、実際の物理シミュレーションを実行している場合は、設計上、これらのエンジンよりも低速であり、別の物理エンジンを超えることはありません。

于 2013-03-13T08:26:28.963 に答える
5

Java を書くように Python を書くと、もちろん遅くなります。慣用的な Java は、慣用的な Python にうまく変換されません。

このパフォーマンスの違いは Python の性質の一部ですか? 独自の Python プログラムのパフォーマンスを向上させたい場合、上記とは別の方法で何を行う必要がありますか? たとえば、個々のオブジェクトなどを使用する代わりに、すべてのパーティクルのプロパティを配列内に格納します。

コードを見ずに言うのは難しいです。

以下は、パフォーマンスに影響を与える可能性のある python と java の相違点の不完全なリストです。

  1. 処理は即時モード キャンバスを使用します。Python で同等のパフォーマンスが必要な場合は、即時モード キャンバスも使用する必要があります。ほとんどの GUI フレームワーク (Tkinter キャンバスを含む) のキャンバスは保持モードです。これは使いやすいですが、本質的に即時モードよりも低速です。pygame、SDL、または Pyglet によって提供されるような即時モード キャンバスを使用する必要があります。

  2. Python は動的言語です。つまり、インスタンス メンバー アクセス、モジュール メンバー アクセス、グローバル変数アクセスは実行時に解決されます。Python でのインスタンス メンバー アクセス、モジュール メンバー アクセス、およびグローバル変数アクセスは、実際にはディクショナリ アクセスです。Java では、それらはコンパイル時に解決され、その性質上、はるかに高速です。頻繁にアクセスされるグローバル、モジュール変数、および属性をローカル変数にキャッシュします。

  3. Python 2.x では、range() は具体的なリストを生成します。Python ではfor item in list、反復子 を使用して実行される反復は、通常、反復変数 を使用して実行される反復よりも高速ですfor n in range(len(list))。ほとんどの場合、range(len(...)) を使用して反復するのではなく、反復子を使用して直接反復する必要があります。

  4. Python の数値は不変です。これは、あらゆる算術計算が新しいオブジェクトを割り当てることを意味します。これが、プレーンな python が低レベルの計算にあまり適していない理由の 1 つです。C 拡張機能を作成する必要なしに低レベルの計算を作成できるようにしたいほとんどの人は、通常、cython、psyco、または numpy を使用します。ただし、これは通常、何百万もの計算がある場合にのみ問題になります。

これはほんの一部であり、非常に不完全なリストです。java を python に変換すると次善のコードが生成される理由は他にもたくさんあります。コードを見なければ、何を別の方法で行う必要があるかを判断することは不可能です。最適化された Python コードは、通常、最適化された Java コードとは大きく異なります。

于 2013-03-13T00:13:38.957 に答える
0

粒子ベースの物理シミュレーションは、線形代数演算に簡単に変換できます。行列演算。Numpy はそのような操作を提供し、内部では Fortran/C/C++ で実装されています。適切に作成された python/Numpy コード (言語とライブラリを最大限に活用) により、かなり高速なコードを作成できます。

于 2013-04-28T01:40:09.903 に答える