source: 2014/24/EemeliK/Zombieland/Jypeli/Physics2DDotNet/Detectors/SelectiveSweepDetector.cs @ 5974

Revision 5974, 9.2 KB checked in by empaheik, 4 years ago (diff)
Line 
1#region MIT License
2/*
3 * Copyright (c) 2005-2008 Jonathan Mark Porter. http://physics2d.googlepages.com/
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights to
8 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
9 * the Software, and to permit persons to whom the Software is furnished to do so,
10 * subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
16 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
17 * PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 */
22#endregion
23  // Contributor: Andrew D. Jones
24
25
26
27#if UseDouble
28using Scalar = System.Double;
29#else
30using Scalar = System.Single;
31#endif
32using System;
33using System.Collections.Generic;
34using System.Runtime.Serialization;
35using AdvanceMath.Geometry2D;
36using Physics2DDotNet.DataTypes;
37
38namespace Physics2DDotNet.Detectors
39{
40    /// <summary>
41    /// Faster then sweep and prune and does not stutter like SingleSweep
42    /// </summary>
43#if !(WINDOWS_PHONE || XBOX)
44    [Serializable]
45#endif
46    public sealed class SelectiveSweepDetector : BroadPhaseCollisionDetector
47    {
48#if !(WINDOWS_PHONE || XBOX)
49        [Serializable]
50#endif
51        sealed class StubComparer : IComparer<Stub>
52        {
53            public int Compare(Stub left, Stub right)
54            {
55                if (left.value < right.value) { return -1; }
56                if (left.value > right.value) { return 1; }
57                return ((left == right) ? (0) : ((left.begin) ? (-1) : (1)));
58            }
59        }
60#if !(WINDOWS_PHONE || XBOX)
61        [Serializable]
62#endif
63        sealed class Wrapper 
64#if !WINDOWS_PHONE
65            : IDeserializationCallback
66#endif
67        {
68#if !WINDOWS_PHONE
69            [NonSerialized]
70#endif
71            public LinkedListNode2<Wrapper> node;
72            public Body body;
73            public bool shouldAddNode;
74            public Scalar min;
75            public Scalar max;
76            Stub xBegin;
77            Stub xEnd;
78            Stub yBegin;
79            Stub yEnd;
80            public Wrapper(Body body)
81            {
82                this.body = body;
83                this.node = new LinkedListNode2<Wrapper>(this);
84                xBegin = new Stub(this, true);
85                xEnd = new Stub(this, false);
86                yBegin = new Stub(this, true);
87                yEnd = new Stub(this, false);
88            }
89            public void AddStubs(List<Stub> xStubs, List<Stub> yStubs)
90            {
91                xStubs.Add(xBegin);
92                xStubs.Add(xEnd);
93
94                yStubs.Add(yBegin);
95                yStubs.Add(yEnd);
96            }
97            public void Update()
98            {
99                BoundingRectangle rect = body.Rectangle;
100                //if it is a single point in space
101                //then dont even add it to the link list.
102                shouldAddNode = rect.Min.X != rect.Max.X || rect.Min.Y != rect.Max.Y;
103
104                xBegin.value = rect.Min.X;
105                xEnd.value = rect.Max.X;
106
107                yBegin.value = rect.Min.Y;
108                yEnd.value = rect.Max.Y;
109            }
110
111            public void SetX()
112            {
113                this.min = this.xBegin.value;
114                this.max = this.xEnd.value;
115            }
116            public void SetY()
117            {
118                this.min = this.yBegin.value;
119                this.max = this.yEnd.value;
120            }
121#if !WINDOWS_PHONE
122            void IDeserializationCallback.OnDeserialization(object sender)
123            {
124                this.node = new LinkedListNode2<Wrapper>(this);
125            }
126#endif
127        }
128#if !(WINDOWS_PHONE || XBOX)
129        [Serializable]
130#endif
131        sealed class Stub
132        {
133            public Wrapper wrapper;
134            public bool begin;
135            public Scalar value;
136            public Stub(Wrapper wrapper, bool begin)
137            {
138                this.wrapper = wrapper;
139                this.begin = begin;
140            }
141        }
142
143        static StubComparer comparer = new StubComparer();
144
145        static bool WrapperIsRemoved(Wrapper wrapper)
146        {
147            return !wrapper.body.IsAdded;
148        }
149        static bool StubIsRemoved(Stub stub)
150        {
151            return !stub.wrapper.body.IsAdded;
152        }
153        List<Wrapper> wrappers;
154        List<Stub> xStubs;
155        List<Stub> yStubs;
156
157        public SelectiveSweepDetector()
158        {
159            this.wrappers = new List<Wrapper>();
160            this.xStubs = new List<Stub>();
161            this.yStubs = new List<Stub>();
162        }
163
164        protected internal override void AddBodyRange(List<Body> collection)
165        {
166            int wrappercount = collection.Count + wrappers.Count;
167            if (wrappers.Capacity < wrappercount)
168            {
169                wrappers.Capacity = wrappercount;
170            }
171            int nodeCount = collection.Count * 2 + xStubs.Count;
172            if (xStubs.Capacity < nodeCount)
173            {
174                xStubs.Capacity = nodeCount;
175                yStubs.Capacity = nodeCount;
176            }
177            foreach (Body item in collection)
178            {
179                Wrapper wrapper = new Wrapper(item);
180                wrappers.Add(wrapper);
181                wrapper.AddStubs(xStubs, yStubs);
182            }
183        }
184        protected internal override void Clear()
185        {
186            wrappers.Clear();
187            xStubs.Clear();
188            yStubs.Clear();
189        }
190        protected internal override void RemoveExpiredBodies()
191        {
192            wrappers.RemoveAll(WrapperIsRemoved);
193            xStubs.RemoveAll(StubIsRemoved);
194            yStubs.RemoveAll(StubIsRemoved);
195        }
196
197        /// <summary>
198        /// updates all the nodes to their new values and sorts the lists
199        /// </summary>
200        private void Update()
201        {
202            for (int index = 0; index < wrappers.Count; ++index)
203            {
204                wrappers[index].Update();
205            }
206            xStubs.Sort(comparer);
207            yStubs.Sort(comparer);
208        }
209
210        /// <summary>
211        /// Finds how many collisions there are on the x and y and returns if
212        /// the x axis has the least
213        /// </summary>
214        private bool ShouldDoX()
215        {
216            int xCount = 0;
217            int xdepth = 0;
218            int yCount = 0;
219            int ydepth = 0;
220            for (int index = 0; index < xStubs.Count; index++)
221            {
222                if (xStubs[index].begin) { xCount += xdepth++; }
223                else { xdepth--; }
224
225                if (yStubs[index].begin) { yCount += ydepth++; }
226                else { ydepth--; }
227            }
228            return xCount < yCount;
229        }
230
231        public override void Detect(TimeStep step)
232        {
233            Update();
234            DetectInternal(step, ShouldDoX());
235        }
236        private void DetectInternal(TimeStep step, bool doX)
237        {
238            List<Stub> stubs = (doX) ? (xStubs) : (yStubs);
239            LinkedList2<Wrapper> currentBodies = new LinkedList2<Wrapper>();
240            for (int index = 0; index < stubs.Count; index++)
241            {
242                Stub stub = stubs[index];
243                Wrapper wrapper1 = stub.wrapper;
244                if (stub.begin)
245                {
246                    //set the min and max values
247                    if (doX) { wrapper1.SetY(); }
248                    else { wrapper1.SetX(); }
249
250                    Body body1 = wrapper1.body;
251                    for (LinkedListNode2<Wrapper> node = currentBodies.First;
252                        node != null;
253                        node = node.Next)
254                    {
255                        Wrapper wrapper2 = node.Value;
256                        Body body2 = wrapper2.body;
257                        if (wrapper1.min <= wrapper2.max && //tests the other axis
258                            wrapper2.min <= wrapper1.max &&
259                            Body.CanCollide(body1, body2))
260                        {
261                            OnCollision(step, body1, body2);
262                        }
263                    }
264                    if (wrapper1.shouldAddNode)
265                    {
266                        currentBodies.AddLast( wrapper1.node );
267                    }
268                }
269                else
270                {
271                    if (wrapper1.shouldAddNode)
272                    {
273                        currentBodies.Remove(wrapper1.node);
274                    }
275                }
276            }
277        }
278    }
279}
Note: See TracBrowser for help on using the repository browser.