Reducing AABB by combining tiles

Recently I make a terrible mistake, create AABB collision rectangle for each tile, in my wip game. The collision system contains 3941 object and takes 63% of execution time. The debug draw looks like a spider web:

Spider Web!

The most straightforward method is merging small tiles into larger rectangle to reduce total collision object number. This problems is very similar to Algorithm for “healing” multiple rectangles into a smaller number of rectangles . The algorithm has to step:

  1. for each row
    • combine continuous tiles into stripe shape rectangle
  2. from top to bottom row
    • if it and next row have stripes with same horizontal range
      • merge these stripes

After running first step, my collision objects reduce to 363 and collision system only take 38% of execution time. Now the debug draw becomes zebra crossing:

Zebra Crossing~

The first run give us enough confidence to show tile sprites ( without covering by bunch of debug draw ). So the second step makes my collision objects reduce to 48 and the debug draw finally look decent:

Decent Collision System 😛

Even the author thinks this method is not an optimal. But, it is actually very suitable for merge in-door tiles ( dungeon, rooms ). It is shame that I do not use this approach in first place. After reducing collision objects, the FPS increases from 70 to 210. The dramatic improvement also points out how big this mistake is. I guess render system needs some optimizations too. (`・ω・´)


Reducing AABB by combining tiles 有 “ 2 則迴響 ”


在下方填入你的資料或按右方圖示以社群網站登入: 標誌

您的留言將使用 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )


您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s