prova.collision.spacialmap2d source code

1 module prova.collision.spacialmap2d;
2 
3 import prova.collision,
4        prova.core,
5        prova.graphics,
6        prova.math,
7        prova.util,
8        std.math;
9 
10 ///
11 class SpacialMap2D
12 {
13   ///
14   int bucketPadding = 5;
15   private Vector2 bucketSize;
16   private LinkedList!(Collider2D)[Vector2] map;
17   private LinkedList!(Collider2D) colliders;
18   private LinkedList!(Collider2D[2]) collisions;
19 
20   ///
21   this()
22   {
23     colliders = new LinkedList!(Collider2D);
24     collisions = new LinkedList!(Collider2D[2]);
25   }
26 
27   ///
28   void mapColliders()
29   {
30     foreach(Collider2D collider; colliders)
31     {
32       // we map the corners to a space,
33       // edges don't matter as the buckets are
34       // as big as the largest collider
35       Rect bounds = collider.getBounds();
36 
37       mapColliderCorner(bounds.getTopLeft(), collider);
38       mapColliderCorner(bounds.getTopRight(), collider);
39       mapColliderCorner(bounds.getBottomLeft(), collider);
40       mapColliderCorner(bounds.getBottomRight(), collider);
41 
42       collider.previousCollisions = collider.collisions;
43       collider.collisions = new LinkedList!Collider2D;
44     }
45   }
46 
47   private void mapColliderCorner(Vector2 corner, Collider2D collider)
48   {
49     Vector2 key = Vector2(
50       floor(corner.x / bucketSize.x),
51       floor(corner.y / bucketSize.y)
52     );
53 
54     if(!(key in map))
55       map[key] = new LinkedList!(Collider2D);
56 
57     LinkedList!Collider2D bucket = map[key];
58 
59     if(!bucket.contains(collider))
60       map[key].insertBack(collider);
61   }
62 
63   ///
64   void markCollisions()
65   {
66     // loop through buckets in the spacial map
67     foreach(LinkedList!Collider2D bucket; map.values)
68     {
69       searchBucket(bucket);
70       
71       bucket.clear();
72     }
73 
74     map.clear();
75   }
76 
77   private void searchBucket(LinkedList!Collider2D bucket)
78   {
79     // test for collision with every collider within the bucket
80     foreach(Node!Collider2D nodeA; bucket)
81     {
82       Collider2D colliderA = nodeA.value;
83 
84       // test with colliders that haven't already been tested with every collider
85       // by starting after the current collider being tested
86       for(Node!Collider2D nodeB = nodeA.getNext(); nodeB; nodeB = nodeB.getNext())
87       {
88         Collider2D colliderB = nodeB.value;
89 
90         if(colliderA.intersects(colliderB) && !colliderA.collisions.contains(colliderB))
91           markCollision(colliderA, colliderB);
92       }
93     }
94   }
95 
96   private void markCollision(Collider2D colliderA, Collider2D colliderB)
97   {
98     colliderA.collisions.insertBack(colliderB);
99     colliderB.collisions.insertBack(colliderA);
100 
101     Collider2D[2] collision = [colliderA, colliderB];
102     collisions.insertBack(collision);
103   }
104 
105   ///
106   void resolveCollisions()
107   {
108     foreach(Collider2D[2] collision; collisions)
109       resolveCollision(collision[0], collision[1]);
110 
111     foreach(Collider2D colliderA; colliders)
112       foreach(Collider2D colliderB; colliderA.previousCollisions)
113         colliderA.entity.onCollisionExit2D(colliderA, colliderB);
114 
115     collisions.clear();
116   }
117 
118   private void resolveCollision(Collider2D colliderA, Collider2D colliderB)
119   {
120     if(!colliderA.previousCollisions.contains(colliderB)) {
121       colliderA.entity.onCollisionEnter2D(colliderA, colliderB);
122       colliderB.entity.onCollisionEnter2D(colliderB, colliderA);
123     }
124 
125     colliderA.entity.onCollision2D(colliderA, colliderB);
126     colliderB.entity.onCollision2D(colliderB, colliderA);
127 
128     // remove the collision from the previous list if it exists,
129     // to speed up the collision exit loop
130     colliderA.previousCollisions.remove(colliderB);
131     colliderB.previousCollisions.remove(colliderA);
132   }
133 
134   /// Should not be called in most circumstances
135   void add(Collider2D collider)
136   {
137     colliders.insertBack(collider);
138 
139     updateBucketSize(collider);
140   }
141 
142   /// Should not be called in most circumstances
143   void add(LinkedList!Collider2D colliders)
144   {
145     foreach(Collider2D collider; colliders) {
146       this.colliders.insertBack(collider);
147 
148       updateBucketSize(collider);
149     }
150   }
151 
152   /// Should not be called in most circumstances
153   void remove(Collider2D collider)
154   {
155     colliders.remove(collider);
156 
157     updateBucketSize();
158   }
159 
160   /// Should not be called in most circumstances
161   void remove(LinkedList!Collider2D colliders)
162   {
163     foreach(Collider2D collider; colliders)
164       colliders.remove(collider);
165 
166     updateBucketSize();
167   }
168 
169   private void updateBucketSize()
170   {
171     bucketSize.set(0, 0);
172 
173     foreach(Collider2D collider; colliders)
174       updateBucketSize(collider);
175   }
176 
177   private void updateBucketSize(Collider2D collider)
178   {
179     const Vector2 size = collider.getSize();
180 
181     if(size.x + bucketPadding * 2 > bucketSize.x)
182       bucketSize.x = size.x + bucketPadding * 2;
183     if(size.y + bucketPadding * 2 > bucketSize.y)
184       bucketSize.y = size.y + bucketPadding * 2;
185   }
186 }