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

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

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

package{?
? ?? ???import?flash.display.DisplayObject;?
? ?? ???import flash.display.Graphics;?
? ?? ???import flash.events.EventDispatcher;?
? ?? ?? ?
? ?? ???public class CollisionGrid extends EventDispatcher?
? ?? ???{?
? ?? ???private var _checks:Vector.<DisplayObject>;?
? ?? ???private var _grid:Vector.<Vector.<DisplayObject>>;?
? ?? ???private var _gridSize:Number;?
? ?? ???private var _height:Number;?
? ?? ???private var _numCells:int;?
? ?? ???private var _numCols:int;?
? ?? ???private var _numRows:int;?
? ?? ???private var _width:Number;?
? ?? ?? ?? ?? ?? ?? ?? ??
? ?? ???public function CollisionGrid(width:Number, height:Number, gridSize:Number)?
? ?? ???{?
? ?? ?? ?? ?? ? _width = width;?
? ?? ?? ?? ?? ? _height = height;?
? ?? ?? ?? ?? ? _gridSize = gridSize;?
? ?? ?? ?? ?? ? _numCols = Math.ceil(_width / _gridSize);?
? ?? ?? ?? ?? ? _numRows = Math.ceil(_height / _gridSize);?
? ?? ?? ?? ?? ? _numCells = _numCols * _numRows;?
? ?? ???}? ?? ???
? ?? ???public function drawGrid(graphics:Graphics):void?
? ?? ???{?
? ?? ???graphics.lineStyle(0, .5);?
? ?? ???for(var i:int = 0; i <= _width; i += _gridSize)?
? ?? ???{?
? ?? ?? ? graphics.moveTo(i, 0);?
? ?? ?? ? graphics.lineTo(i, _height);?
? ?? ???}?
? ?? ???for(i = 0; i <= _height; i += _gridSize)?
? ?? ???{?
? ?? ?? ? graphics.moveTo(0, i);?
? ?? ?? ? graphics.lineTo(_width, i);?
? ?? ???}? ?? ?? ?? ?? ?? ?? ?? ?
? ?? ???}?
? ?? ???public function check(objects:Vector.<DisplayObject>):void?
? ?? ???{?
? ?? ?? ? var numObjects:int = objects.length;?
? ?? ?? ? _grid = new Vector.<Vector.<DisplayObject>>(_numCells);?
? ?? ?? ? _checks = new Vector.<DisplayObject>();?
? ?? ???for(var i:int = 0; i < numObjects; i++)?
? ?? ???{?
? ?? ?? ? var obj:DisplayObject = objects[i];?
var index:int=Math.floor(obj.y / _gridSize)*_numCols+Math.floor(obj.x /_gridSize);?
? ?? ?? ? if(_grid[index] == null) _grid[index] = new Vector.<DisplayObject>;
? ?? ?? ? _grid[index].push(obj);?
? ?? ???}?
? ?? ?? ?? ?? ?? ?? ?? ?? ?checkGrid();?
? ?? ???}?
? ?? ???private function checkGrid():void?
? ?? ???{?
? ?? ???for(var i:int = 0; i < _numCols; i++)?
? ?? ???{?
? ?? ?? ?? ?? ? for(var j:int = 0; j < _numRows; j++)?
? ?? ?? ?? ?? ? {?
? ?? ?? ?? ?? ?? ?? ?? ?checkOneCell(i, j);?
? ?? ?? ?? ?? ?? ?? ?? ?checkTwoCells(i, j, i + 1, j);?
? ?? ?? ?? ?? ?? ?? ?? ?checkTwoCells(i, j, i - 1, j + 1);?
? ?? ?? ?? ?? ?? ?? ?? ?checkTwoCells(i, j, i,? ???j + 1);?
? ?? ?? ?? ?? ?? ?? ?? ?checkTwoCells(i, j, i + 1, j + 1);?
? ?? ?? ?? ?? ? }?
? ?? ???}?
? ?? ???}?
? ?? ???private function checkOneCell(x:int, y:int):void?
? ?? ???{?
? ?? ?? ?? ?? ? var cell:Vector.<DisplayObject> = _grid[y * _numCols + x];?
? ?? ?? ?? ?? ? if(cell == null) return;?
? ?? ?? ?? ?? ???
? ?? ?? ?? ?? ? var cellLength:int = cell.length;?
? ?? ?? ?? ?? ? for(var i:int = 0; i < cellLength - 1; i++)?
? ?? ?? ?? ?? ? {?
? ?? ?? ?? ?? ?? ?? ?? ?var objA:DisplayObject = cell[i];?
? ?? ?? ?? ?? ?? ?? ?? ?for(var j:int = i + 1; j < cellLength; j++)?
? ?? ?? ?? ?? ?? ?? ?? ?{?
? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???var objB:DisplayObject = cell[j];?
? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???_checks.push(objA, objB);?
? ?? ?? ?? ?? ?? ?? ?? ?}?
? ?? ?? ?? ?? ? }?
? ?? ???}?
? ?? ???private function checkTwoCells(x1:int, y1:int, x2:int, y2:int):void?
? ?? ???{?
? ?? ?? ?? ?? ? if(x2 >= _numCols || x2 < 0 || y2 >= _numRows) return;?
? ?? ?? ?? ?? ? var cellA:Vector.<DisplayObject> = _grid[y1 * _numCols + x1];
? ?? ?? ?? ?? ? var cellB:Vector.<DisplayObject> = _grid[y2 * _numCols + x2];
? ?? ?? ?? ?? ? if(cellA == null || cellB == null) return;?
? ?? ?? ?? ?? ???
? ?? ?? ?? ?? ? var cellALength:int = cellA.length;?
? ?? ?? ?? ?? ? var cellBLength:int = cellB.length;?
? ?? ?? ?? ?? ? for(var i:int = 0; i < cellALength; i++)?
? ?? ?? ?? ?? ? {?
? ?? ?? ?? ?? ?? ?? ?? ?var objA:DisplayObject = cellA[i];?
? ?? ?? ?? ?? ?? ?? ?? ?for(var j:int = 0; j < cellBLength; j++)?
? ?? ?? ?? ?? ?? ?? ?? ?{?
? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???var objB:DisplayObject = cellB[j];?
? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???_checks.push(objA, objB);?
? ?? ?? ?? ?? ?? ?? ?? ?}?
? ?? ?? ?? ?? ? }?
? ?? ???}?
? ?? ???public function get checks():Vector.<DisplayObject>?
? ?? ???{?
? ?? ?? ?? ?? ? return _checks;?
? ?? ???}?
? ?? ???}?
}

复制代码

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 都分配进网格。

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

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