在Python/Pyglet中分離軸定理

Question

我想用Pyglet在Python中製作一個（各種）Asteroids的克隆。我想我會盡量想出一點幻想，並實施分離軸定理來進行碰撞。我有它的工作，但問題是，它是非常緩慢。我測試了玩家射擊的子彈與屏幕上的小行星之間的雙重for-loop碰撞，我認爲這是二次時間，但幀速率從大約60到30 fps下降到大約6個小行星和6個子彈在屏幕上看起來非常慢，即使是非優化的碰撞檢測方式。

因此，我運行了一個分析器來確定程序在哪裏，確切地說，在程序被掛起。它似乎掛在了我將形狀頂點轉換爲世界空間的方法中（我定義了圍繞原點的形狀並使用OpenGL代碼轉換爲繪製的世界空間，我相信這是正確的方式）。我從OpenGL抓取變換矩陣，將它變成一個NumPy數組，然後將每個頂點乘以這個矩陣以獲得變換的頂點。值得注意的是，我每做一次碰撞檢查都會這樣做：我曾經使用過XNA，當我在那裏實施SAT時（我也在那裏製作了一個小行星克隆），頂點也在原點周圍定義，然後您必須轉換他們使用世界矩陣。

圍繞（0,0）存儲頂點並轉換每個調用，還是隻存儲變換的頂點最好？我覺得算法不應該這麼慢，所以我願意打賭我搞砸了一些東西。如果我更擅長剖析（我對它很不熟悉），我可能能夠獲得更全面的圖片，但我希望你們可以有一些想法。

下面是帶有Shape類的文件的直接鏈接，其中包含所有碰撞邏輯：shape.py。 profiler似乎標記爲瓶頸的具體方法是__get_transformed_verts。顯然，你也可以從那裏獲得整個回購，但要注意，還有很多沒有評論的交易。

Answer 1

正如Nico在評論中所建議的那樣，快速獲得較好加速度的方法是先檢查較簡單的幾何圖形。對於一個小行星克隆，我猜測一個圓圈將會很適合（或3D的球體）。如果圓圈（至少足夠大以覆蓋實際形狀）不重疊，則不需要進行更昂貴的幾何測試。

如果您有很多對象，您可能會希望避免每幀進行n * n次測試。看看空間分區結構/算法。 2D中大量移動對象的最簡單方案是網格。然後，您只需測試屬於相同或相鄰網格單元的對象以進行碰撞。

我注意到的另一件事：您每次測試碰撞時都會生成變換的頂點。對於圓圈測試不合格的每個對象，每個時間步（幀）僅生成一次會更快。