Code center > Darwinbots Program Source Code

Buckets?

(1/1)

Botsareus:
I am just trying to figure out a section of code:


--- Code: ---'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
--- End code ---

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?

Botsareus:
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.

Numsgil:
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.

Botsareus:
 8)

Navigation

[0] Message Index