Darwinbots Forum

Code center => Darwinbots Program Source Code => Topic started by: Botsareus on August 11, 2016, 09:25:40 PM

Title: Buckets?
Post by: Botsareus 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?
Title: Re: Buckets?
Post by: Botsareus 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.
Title: Re: Buckets?
Post by: Numsgil 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 (http://buildnewgames.com/broad-phase-collision-detection/).
Title: Re: Buckets?
Post by: Botsareus on August 14, 2016, 04:49:25 PM
 8)