Author Topic: Buckets?  (Read 478 times)

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
    • DJ Paul Kononov
Buckets?
« on: August 11, 2016, 09:25:40 PM »
I am just trying to figure out a section of code:

Code: [Select]
'This is the buckets Array
Dim Buckets() As BucketType

Public Type BucketType
  arr() As Integer
  size As Integer 'number of bots in the bucket i.e. highest array element with a bot
  adjBucket(8) As vector ' List of buckets adjoining this one.  Interior buckets will have 8.  Edge buckets 5.  Corners 3.
End Type

Why do we use buckets in DB2? I know it has something to do with multibot collisions, but beyond that I am lost. Will it not be faster to check collisions one bot at a time instead of using buckets?

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
    • DJ Paul Kononov
Re: Buckets?
« Reply #1 on: August 12, 2016, 03:24:00 PM »
Bump

I think I figured it out. It splits the simulation into a grid and only checks collisions and vision for robots in a specific grid location and adjacent grid locations. Though I really do not see how doing extra work like that improves speed by much.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7704
    • View Profile
Re: Buckets?
« Reply #2 on: August 12, 2016, 04:46:40 PM »
It's basically a way to cut down the number of intersections from O(n^2) to O(n), which helps the simulation scale to large numbers of bots.  It probably would be faster to just do one at a time for, say, a simulation of ~25 bots.  But when you get more like 1000 bots, the bucket system helps cut down the number of checks massively.

Another term for it is spatial hash, or uniform grid.  There's a few articles online that talk about it, eg: this one.
« Last Edit: August 12, 2016, 04:53:38 PM by Numsgil »

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
    • DJ Paul Kononov
Re: Buckets?
« Reply #3 on: August 14, 2016, 04:49:25 PM »
 8)