[转] 高效的格子碰撞检测算法

[心得] 高效的格子碰撞检测算法

 

http://bbs.9ria.com/viewthread.php?tid=95423&extra=page%3D1%26amp%3Borderby%3Ddateline%26amp%3Bfilter%3D2592000

1. package{ 
   
2.         import flash.display.DisplayObject; 
   
3.         import flash.display.Graphics; 
   
4.         import flash.events.EventDispatcher; 
   
5.          
   
6.         public class CollisionGrid extends EventDispatcher 
   
7.         { 
   
8.         private var _checks:Vector.<DisplayObject>; 
   
9.         private var _grid:Vector.<Vector.<DisplayObject>>; 
   
10.         private var _gridSize:Number; 
    
11.         private var _height:Number; 
    
12.         private var _numCells:int; 
    
13.         private var _numCols:int; 
    
14.         private var _numRows:int; 
    
15.         private var _width:Number; 
    
16.                          
    
17.         public function CollisionGrid(width:Number, height:Number, gridSize:Number) 
    
18.         { 
    
19.                 _width = width; 
    
20.                 _height = height; 
    
21.                 _gridSize = gridSize; 
    
22.                 _numCols = Math.ceil(_width / _gridSize); 
    
23.                 _numRows = Math.ceil(_height / _gridSize); 
    
24.                 _numCells = _numCols * _numRows; 
    
25.         }        
    
26.         public function drawGrid(graphics:Graphics):void 
    
27.         { 
    
28.         graphics.lineStyle(0, .5); 
    
29.         for(var i:int = 0; i <= _width; i += _gridSize) 
    
30.         { 
    
31.           graphics.moveTo(i, 0); 
    
32.           graphics.lineTo(i, _height); 
    
33.         } 
    
34.         for(i = 0; i <= _height; i += _gridSize) 
    
35.         { 
    
36.           graphics.moveTo(0, i); 
    
37.           graphics.lineTo(_width, i); 
    
38.         }                        
    
39.         } 
    
40.         public function check(objects:Vector.<DisplayObject>):void 
    
41.         { 
    
42.           var numObjects:int = objects.length; 
    
43.           _grid = new Vector.<Vector.<DisplayObject>>(_numCells); 
    
44.           _checks = new Vector.<DisplayObject>(); 
    
45.         for(var i:int = 0; i < numObjects; i++) 
    
46.         { 
    
47.           var obj:DisplayObject = objects[i]; 
    
48. var index:int=Math.floor(obj.y / _gridSize)*_numCols+Math.floor(obj.x /_gridSize); 
    
49.           if(_grid[index] == null) _grid[index] = new Vector.<DisplayObject>;
    
50.           _grid[index].push(obj); 
    
51.         } 
    
52.                            checkGrid(); 
    
53.         } 
    
54.         private function checkGrid():void 
    
55.         { 
    
56.         for(var i:int = 0; i < _numCols; i++) 
    
57.         { 
    
58.                 for(var j:int = 0; j < _numRows; j++) 
    
59.                 { 
    
60.                         checkOneCell(i, j); 
    
61.                         checkTwoCells(i, j, i + 1, j); 
    
62.                         checkTwoCells(i, j, i - 1, j + 1); 
    
63.                         checkTwoCells(i, j, i,     j + 1); 
    
64.                         checkTwoCells(i, j, i + 1, j + 1); 
    
65.                 } 
    
66.         } 
    
67.         } 
    
68.         private function checkOneCell(x:int, y:int):void 
    
69.         { 
    
70.                 var cell:Vector.<DisplayObject> = _grid[y * _numCols + x]; 
    
71.                 if(cell == null) return; 
    
72.                  
    
73.                 var cellLength:int = cell.length; 
    
74.                 for(var i:int = 0; i < cellLength - 1; i++) 
    
75.                 { 
    
76.                         var objA:DisplayObject = cell[i]; 
    
77.                         for(var j:int = i + 1; j < cellLength; j++) 
    
78.                         { 
    
79.                                 var objB:DisplayObject = cell[j]; 
    
80.                                 _checks.push(objA, objB); 
    
81.                         } 
    
82.                 } 
    
83.         } 
    
84.         private function checkTwoCells(x1:int, y1:int, x2:int, y2:int):void 
    
85.         { 
    
86.                 if(x2 >= _numCols || x2 < 0 || y2 >= _numRows) return; 
    
87.                 var cellA:Vector.<DisplayObject> = _grid[y1 * _numCols + x1];
    
88.                 var cellB:Vector.<DisplayObject> = _grid[y2 * _numCols + x2];
    
89.                 if(cellA == null || cellB == null) return; 
    
90.                  
    
91.                 var cellALength:int = cellA.length; 
    
92.                 var cellBLength:int = cellB.length; 
    
93.                 for(var i:int = 0; i < cellALength; i++) 
    
94.                 { 
    
95.                         var objA:DisplayObject = cellA[i]; 
    
96.                         for(var j:int = 0; j < cellBLength; j++) 
    
97.                         { 
    
98.                                 var objB:DisplayObject = cellB[j]; 
    
99.                                 _checks.push(objA, objB); 
    
100.                         } 
     
101.                 } 
     
102.         } 
     
103.         public function get checks():Vector.<DisplayObject> 
     
104.         { 
     
105.                 return _checks; 
     
106.         } 
     
107.         } 
     
108. }

复制代码

Vector 的使用。Vector是 Flash10 的新内容，相当于一个具有类型的数组。由于编译器知道 vector 中的每个元素都是同样的类型，所以就能为之创建出更有效的字节码，从而提高执行效率。 
以这段程序为例，从数组改为 vector 差不多使运行效率翻了一倍。 
drawGrid 函数一点没变，它依旧用来画出网格。 
check 函数是这个类对外交互的主要函数。其接收参数的类型是元素类型为 DisplayObject
的 vector。 
选择 Displayobject 的原因是因为碰撞检测通常用于 Sprite，MovieClip，Shape 和Bitmap，
而这些类都继承自 Displayobject。Displayobject 也有x和y 两个位置属性。 
所以要用自定义的对象时，请确保继承自 Displayobject。 
函数一开始定义了一个名为_grid 的 vector，还有一个名为_checks 的 vector。 
_grid 应该不陌生，但在实现上有点不同，这里用一维 vector 加索引技巧取代了二维数组。 
因为这么做，可以使访问元素速度更快并减少了循环。等下会有详细介绍。 
_checks 用来保存需要进行碰撞检测的对象。注意 CollisionGrid 类不处理具体的碰撞检测，它只
用来创建网格，分配对象，以及生成一组需要被检测的对象。具体的碰撞检测算法由你而定。 
接着，check 函数对给定的 vector 进行遍历，把其中每个 Displayobject 都分配进网格。