Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am looking for documentation that explains the different kinds of (well the major ones anyway) 2D space partitioning algorithms & data structures.

Any pointers besides 'Google it and sift through hundreds of papers'. A book perhaps?

share|improve this question
    
Do you have any specific algorithms and data structures you are interested in? What kind of game are you making? –  NoobsArePeople2 Dec 28 '11 at 23:18
    
I simply wanted to digest the main ones and understand the strengths and trade-offs. I am not making a game, but know that this is the right place to ask this question :) –  r1x Dec 28 '11 at 23:38

1 Answer 1

up vote 5 down vote accepted

I've got this sort of info spread over many books on my bibliography, but I'm currently away from them. But from what I could gather up from memory and browsing through the table of contents online, I recall the following books:

3D Math Primer for Graphics and Game Development 1st Edition or Mathematics for 3D Game Programming & Computer Graphics

3D Math Primer or Mathematics for 3D

Chapter 16 (Visibility Determination) of 3D Math Primer for Graphics and Game Development 1st Edition (strangely the authors seem to have removed this section from the second edition of the book) covers the most common techniques (i.e. grid system, quadtree and octree, bsp trees, portal occlusion). The book is really good, although perhaps not the best of its kind.

I've seen Mathematics for 3D Game Programming & Computer Graphics being mentioned very often, but unfortunately haven't gotten my hands on it yet. From the table of contents, it seems to cover space partitioning algorithms too. Not sure how they compare against each other.

Naturally, the focus of these books is on the math. And although the title says 3D, they are also quite relevant for 2D programming.

Real-time Rendering 3rd Edition

Real-time Rendering

Chapter 14 (Acceleration Algorithms) of Real-time Rendering also covers most of these topics, and this is actually my favorite general graphics programming book ever. Very comprehensive but I don't recall how much it covered this particular subject.

The focus of this book is on the graphics theory, but it covers such a large amount of topics that I could hardly find a better recommendation for anyone interested in the field.

Game Programming Gems

Game Programming Gems Volume One

The previous books were mostly theoretical though. For more specific and practical advice, I've read several articles on the subject scattered throughout the Game Programming Gems series. Some that come to mind:

  • Octree Construction - Game Programming Gems 1
  • Loose Octrees - Game Programming Gems 1
  • Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching - Game Programming Gems 2
  • A High-Performance Tile-based Line-of-Sight and Search System - Game Programming Gems 2
  • Sphere Trees for Speedy BSPs - Game Programming Gems 5
  • Spatial Partitioning Using an Adaptive Binary Tree - Game Programming Gems 6
  • BSP Techniques - Game Programming Gems 6
share|improve this answer
    
Theory is actually what I'm after. Hopefully explanations that involve linear algebra & discrete geometry. –  r1x Dec 28 '11 at 23:51
    
Then I believe one of the math books might be the better choice, although you might be disappointed at how little coverage there really is (at least I remember it being rather simple). –  David Gouveia Dec 29 '11 at 4:22
    
Therefore you might benefit from combining that with some practical (and more advanced) examples too. –  David Gouveia Dec 29 '11 at 4:29
    
Thanks for your detailed answer ! –  r1x Dec 29 '11 at 7:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.