вторник, 27 апреля 2010 г.

Тестирование и тюнинг сетки

Продолжение перевода Определение столкновений множества объектов. Теперь мы поговорим о преимуществах применения сетки для определения столкновений перед обычным методом перебора. Для этого проведем несколько тестов, а также посмотрим на применение сетки для движущихся объектов.

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/hit_testing_with_a_large_number_of_objects/GridCollision2.swf, 600, 400[/SWF]


Шаг 4. Тестирование и тюнинг сетки

Каждый раз, когда вы запускаете это приложение, вы можете с помощью метода trace() получить в окне output количество проверок столкновения. На моем компьютере, с разрешением экрана 1440х900 и запущенном на весь экран браузере, я получил около 80-130 проверок столкновения при количестве шаров равном 100, радиусе шара 25 и размере ячейки 50. Чем меньше размер stage, тем больше столкновений будет. Запустите приложение несколько раз и посмотрите, какие количества столкновений вам это даст. Поскольку взаимное расположение шаров осуществляется в случайном порядке, то каждый раз количество столкновений может отличаться от предыдущего значения.

Теперь увеличьте размер ячейки сетки до 100, например. Вы заметите, что количество проверок резко увеличилось, т.к. количество шаров в каждой ячейке увеличилось. Звучит плохо, но это также уменьшает число ячеек и число массивов, которые должны обходиться циклами.

Теперь попробуйте уменьшить размер сетки до 40 или даже 30. Там будет меньше столкновений, но посмотрим на результат внимательней. Вы, возможно, увидите случайно пропущенные два столкнувшихся объекта, которые не окрашены в красный цвет, как столкнувшиеся (прим перев: - я не увидел, хотя пытался много раз, только время на проверку всей сетки значительно увеличивается). Это не хорошо, но служит нам напоминанием о том, что размер ячейки должен быть не менее большего из объектов.
Установите размер ячейки сетки обратно на 50 и измените строку в методе makeBalls()

var ball:Ball = new Ball(RADIUS);


на следующую

var ball:Ball = new Ball(Match.random()*RADIUS);


Это изменение никак не влияет на количество проверок на столкновения, все работает прекрасно, что показывает на работоспособность системы при различных размерах объектов.

Теперь сделаем более серьезное изменение, чтобы увидеть насколько быстрей проверка столкновений с помощью сетки, чем традиционная проверка каждого объекта с каждым.
Для того, чтобы это сделать необходимо применить новый метод. Назовем его basicCheck()

private function basicCheck():void
{
for(var i:int = 0; i < _balls.length - 1; i++)
{
var ballA:Ball = _balls[i] as Ball;
for(var j:int = i + 1; j < _balls.length; j++)
{
var ballB:Ball = _balls[j] as Ball;
checkCollision(ballA, ballB);
}
}
}


Этот код генерирует 4950 проверок на столкновения для ста объектов. Мы знаем, что это гораздо больше, чем при проверке с помощью сетки. Как сравнить два метода? Как увидеть реальное преимущество?

Итак, очевидно, что мы должны увидеть преимущество, иначе я бы не писал этой главы, и лучше один раз увидеть эту выгоду, чем сто раз о ней услышать. Мы запустим оба способа по десять раз и сравним значения затраченного времени на полную проверку для каждого способа. Эта проверка будет выполняться в конструкторе класса:

public function GridCollision()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;

makeBalls();
drawGrid();

var startTime:int;
var elapsed:int;
var i:int;

startTime = getTimer();
for(i = 0; i < 10; i++)
{
makeGrid();
assignBallsToGrid();
checkGrid();
}
elapsed = getTimer() - startTime;
trace("Grid-based:", elapsed);

startTime = getTimer();
for(i = 0; i < 10; i++)
{
basicCheck();
}
elapsed = getTimer() - startTime;
trace("Basic check", elapsed);

}


Здесь мы создаем переменные для хранения времени начала и времени окончания проверки для каждого из способов. Время начала задаем с помощью метода getTimer() и запускаем следующие три метода десять раз:

makeGrid();
assignBallsToGrid();
checkGrid();


Вычтите время начала из текущего времени и посмотрите как долго это продолжается. Повторите то же самое для метода basicCheck() (прим перев: - см класс GridCollision1 в архиве scr в аттаче, при тестировании в среде Flash вам нужно сделать этот класс классом документа).

Какие результаты это вам даст? У меня метод? основанный на сетке выполняется в среднем в 2,5 раза быстрее чем традиционный метод. Не очень большой перевес, которого я ожидал, избавляясь от 4800 проверок на столкновения, но который, тем не менее, показывает преимущество метода основанного на сетке. Увеличение скорости проверки в 2,5 раза – хороший результат, правда?

Кроме того, чем больше объектов присутствуют на сцене, тем большую экономию ресурсов мы увидим. Если я увеличу число объектов до 1000, то метод? основанный на сетках будет выполняться 1 секунду, а традиционный метод 13 секунд. (Конечно скорость один кадр в секунду неприемлема, но более неприемлема скорость один кадр в 13 секунд!). С другой стороны, если я уменьшаю количество объектов до 50, то традиционный метод оказывается быстрее. Таким образом необходимо подтверждать целесообразность применения того или иного метода опытным путем.

Шаг 5. Создание универсального класса

Хотелось бы надеяться, что изучение класса GridCollision помогло вам разобраться с концепцией метода обнаружения столкновений с помощью сетки и доказать его преимущество в определенных ситуациях. Но есть довольно много проблем. Во-первых, весь код проверки находиться в главном классе приложения, и для использования его в другом приложении мы вынуждены будем копировать этот код в новый класс. Те же трудности и с классом Ball. Если вы хотите проверять столкновения с другими типами объектов, то будет необходимо изменить все ссылки, которые ссылаются на объект типа Ball. Кроме того, алгоритм обнаружения столкновений основан на определении расстояния между центрами объектов. Вам могут понадобиться другие методы, например hitTestObject() и т.д. Поэтому создадим новый класс, который бы решал все эти проблемы насколько это возможно. Назовем его CollisionGrid.

package
{
import flash.display.DisplayObject;
import flash.display.Graphics;
import flash.events.EventDispatcher;

public class CollisionGrid extends EventDispatcher
{
private var _checks:Vector.;
private var _grid:Vector.>;
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.):void
{
var numObjects:int = objects.length;
_grid = new Vector.>(_numCells);
_checks = new Vector.();
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.;
_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. = _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. = _grid[y1 * _numCols + x1];
var cellB:Vector. = _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.
{
return _checks;
}
}
}


Много из этого кода должно быть знакомо вам из предыдущего примера. Многое было сделано для оптимизации класса насколько это возможно, особенно использование векторов. Векторы появились во Flash 10 и, по сути, представляют собой массивы, элементы которых относятся к одному и тому же типу. Поскольку компилятор знает, что все элементы в векторе принадлежат одному типу, то это позволяет создать более эффективный байт-код, который выполняется быстрее. Переход от массивов к векторам дает двойной прирост производительности!

Метод drawGrid() не отличается от того, что мы видели ранее. Он отрисовывает сетку.

Метод check() – главный открытый метод, который взаимодействует с этим классом. Вы передаете в метод в качестве параметра вектор DisplayObject. Я выбрал DisplayObject потому, что объекты, используемые для определения столкновений – это Sprites, MovieClips, Shapes и т.д., которые все наследуются от базового класса DisplayObject. DisplayObject также имеет свойства х и у, которые нам понадобятся для определения позиции и, следовательно, их положения в сетке. Если вы используете свой класс, наследуемый от DisplayObject, убедитесь в изменении класса в этом методе.

Метод check() создает два вектора _grid и _cheks. Вы уже сталкивались с массивом _grid в предыдущем примере, здесь все реализовано немного по-другому, как одномерный вектор с двухмерными векторами-элементами. Это сделано для увеличения производительности при обходе этого вектора в циклах. Мы разберем это более детально очень скоро. Вектор _checks используется для хранения объектов, которые необходимо проверить на столкновения. Заметим что класс CollisionGrid не выполняет сам проверку на столкновение. Это делает сетка, к которой присоединены объекты, она же создает список объектов, которые потенциально могут столкнуться. Пользователь класса должен решать сам, в зависимости от обстоятельств, каким методом определять столкновение.

Затем цикл обходит вектор объектов типа DisplayObject и каждый из них добавляет в сетку. Эта часть кода требует объяснений:

public function check(objects:Vector.):void
{
var numObjects:int = objects.length;
_grid = new Vector.>(_numCells);
_checks = new Vector.();
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.;
_grid[index].push(obj);
}

checkGrid();
}


Повторим, мы используем одномерный вектор вместо двухмерного массива. Переменная index показывает, какое положение в сетке занимает определенный объект. Определяется эта переменная по следующей формуле:

index = y * numColumns + x;


Разберем это на примере:


Рисунок 11



Здесь у нас пять колонок и пять строк. Объект находится в колонке 3 и строке 2, т.е. х=3 и у=2. Тогда index = 2 * 5 + 3 = 13 и это хорошо видно на рисунке 12.
В коде мы получаем номера колонок и строк также, как и раньше.

Math.floor(obj.x / _gridSize)


и

Math.floor(obj.y / _gridSize)


Следующая хитрость. Вместо использования цикла и создания вектора для каждой ячейки сетки, который возможно никогда не будет использоваться, мы проверяем, существует ли там вектор объектов, для которых необходимо проверить столкновение. Если его там нет, мы его создаем.

if(_grid[index] == null)
{
_grid[index] = new Vector.;
}


Когда мы доходим до последней строки цикла, мы уже знаем, что вектор создан и добавляем в него объект:

_grid[index].push(obj);


Последняя строка метода check() вызывает метод 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);
}
}
}


Здесь есть отличия от предыдущего примера.

Методы checkOneCell() и checkTwoCells() работаю совершенно так же, как и раньше. Конечно, они используют одномерные векторы вместо двумерных массивов, и т.к. векторы создаются только для ячеек, которые в этом нуждаются, то они сначала проверяют, является ли ячейка пустой. Также заметим, что вместо проверки столкновения двух объектов они добавляют эти объекты в вектор _checks, который хранит все объекты, для которых должна быть проведена проверка на столкновения.

В конце концов, вектор _checks содержит вектора, содержащие по два объекта для которых необходимо проверить проверку на столкновение. Для получения вектора checks мы должны вызвать метод-геттер checks().

Шаг 6. Использование класса

Примечание переводчика – для использования этого класса у вас должен быть установлен в системе flashplayer v10

package {
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.display.DisplayObject;
import flash.events.Event;

public class GridCollision2 extends Sprite
{
private const GRID_SIZE:Number = 80;
private const RADIUS:Number = 15;

private var _balls:Vector.;
private var _grid:CollisionGrid;
private var _numBalls:int = 50;

public function GridCollision2()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;

_grid = new CollisionGrid(stage.stageWidth, stage.stageHeight, GRID_SIZE);
_grid.drawGrid(graphics);

makeBalls();
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

function onEnterFrame(event:Event):void
{
updateBalls();
_grid.check(_balls);
var numChecks:int = _grid.checks.length;
for(var j:int = 0; j < numChecks; j += 2)
{
checkCollision(_grid.checks[j] as Ball, _grid.checks[j + 1] as Ball);
}
}


private function makeBalls():void
{
_balls = new Vector.(_numBalls);
for(var i:int = 0; i < _numBalls; i++)
{
var ball:Ball = new Ball(RADIUS);
ball.x = Math.random() * stage.stageWidth;
ball.y = Math.random() * stage.stageHeight;
ball.vx = Math.random() * 4 - 2;
ball.vy = Math.random() * 4 - 2;
addChild(ball);
_balls[i] = ball;
}
}

private function updateBalls():void
{
for(var i:int = 0; i < _numBalls; i++)
{
var ball:Ball = _balls[i] as Ball;
ball.update();
if(ball.x < RADIUS)
{
ball.x = RADIUS;
ball.vx *= -1;
}
else if(ball.x > stage.stageWidth - RADIUS)
{
ball.x = stage.stageWidth - RADIUS;
ball.vx *= -1;
}
if(ball.y < RADIUS)
{
ball.y = RADIUS;
ball.vy *= -1;
}
else if(ball.y > stage.stageHeight - RADIUS)
{
ball.y = stage.stageHeight - RADIUS;
ball.vy *= -1;
}
ball.color = 0xffffff;
}
}

private function checkCollision(ballA:Ball, ballB:Ball):void
{
var dx:Number = ballB.x - ballA.x;
var dy:Number = ballB.y - ballA.y;
var dist:Number = Math.sqrt(dx * dx + dy * dy);
if(dist < ballA.radius + ballB.radius)
{
ballA.color = 0xff0000;
ballB.color = 0xff0000;
}
}
}
}


На этом у меня все.

Исходники

Комментариев нет:

Отправить комментарий