Author Topic: That old What can see what problem  (Read 2944 times)

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
That old What can see what problem
« on: October 12, 2005, 08:12:04 PM »
If any of you have been paying attention, the "what bot can see what bot" is a major program slowdown.

Part of the problem was figuring out what to research.  I thought maybe a kd-tree was the way to go, but then I wasn't so sure, because a kd-tree must be rebuilt every cycle.

Anyway, I just realized that the problem can be rewritten!

New problem:  "Given spheres of radius "Max view dist / 2", find when they collide.

How does that help, you ask?  Well, collision detection is a fairly common problem in game programming.  Such that I bet I can find a nice article to help me out.

Woo!

I have tests tomorrow (yes, plural) that I really should stop surfing the net and study for.

So if anyone wants to do some google research, I basically need the best algorithm for large scale (say, in the thousands, because DB should be able to run that fast) collision detection between spheres (technically circles in our case).

I'm sure there's lots of fun stuff.  Just be sure they're not doing the simple "test every sphere against every other one" method, because that's what we're doing now.

Words you'll probably see show up:

kd-tree
quad tree
buckets/Unfiform grid
« Last Edit: October 12, 2005, 08:17:44 PM by Numsgil »