IT-lexikon › Programmering › Uniformt rutnät

Uniformt rutnät

Programmering In English → Uppdaterad: 2026-10-25

Rumsindelning som delar rummet i lika stora celler och sorterar objekten i dem, så kollisionstester bara görs mot grannar i samma cell.

Varje objekt läggs i den eller de celler det överlappar, och en kollisions- eller grannfråga behöver bara titta i den egna cellen och de intilliggande i stället för i hela scenen. När objekten är jämnstora och jämnt utspridda är både inläggning och sökning O(1) i snitt, strukturen är cachevänlig och lätt att parallellisera — därför är den en vanlig broad phase i 2D-fysik och i boids.

Svagheten är "tekannan i stadion": få eller vitt skilda storlekar slösar celler eller spränger dem. Då passar rumslig hashning, hierarkiska rutnät eller adaptiva träd som quadtree och octree bättre.

← Tillbaka till lexikonet