Darwinbots Forum
Code center => Darwinbots Program Source Code => Topic started by: Botsareus on August 11, 2016, 09:25:40 PM
-
I am just trying to figure out a section of 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
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?
-
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.
-
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/).
-
8)