Определение столкновений множества объектов

Представляю вашему вниманию вольный перевод главы из книги AdvancED ActionScript 3.0 Animation, автор Keith Peters.

Речь пойдет об определении столкновений для большого количества объектов. Определение столкновений может использоваться при разработке игр, программировании систем частиц и т.д.

Шаг 1. Предисловие

ActionScript в Flash Player 10 выполняется быстрее, чем когда-либо прежде и это позволяет нам наполнять сцену многими объектами и одновременно перемещать их. Но и здесь есть ограничения. Если вы начинаете перемещение большого количества объектов на экране, то рано или поздно это приведет к потере производительности. Определение столкновений большого количества объектов сопряжено с трудностями, т.к. каждый отдельный объект должен быть проверен на столкновение с каждым из оставшихся. И как правило все не ограничивается проверкой на столкновение, т.к. любая система частиц или игра в которой присутствует множество объектов содержат такие типы взаимодействия как, например, гравитация или изменения направления по ходу движения объектов.

Если у вас есть только шесть взаимодействующих друг с другом объектов, каждый объект нужно соотнести с каждым из оставшихся и проверить их на столкновение, притяжение, взаимное расположение и тд. Обозначив объекты как A, B, C, D, E, F, получим следующие пары

AB, AC, AD, AE, AF
BC, BD, BE, BF // В не нужно проверять с объектом А, т.к. А уже проверен с В
CD, CE, CF
DE, DF
EF // к этому моменту объект Е проверен со всеми остальными объектами, кроме объекта F
//к этому моменту объект F проверен со всеми оставшимися объектами.

Формула, определяющая необходимое и достаточное количество проверок выглядит следующим образом (где N – количество объектов):

(N*N – N)/2

Для 6 объектов это (36 - 6)/2=15 проверок.
Для 10 объектов это (100 - 10)/2=45 проверок.
20 объектов означают 190 проверок, и 30 объектов 435!

Заметно, что количество необходимых проверок растет очень быстро и нам необходимо это как-то ограничить. Перемещение ста объектов на экране для ActionScript 3.0 не составит труда, но когда мы начнем проверять объекты на столкновения или другие взаимодействия это сразу дает 4950 необходимых проверок! В каждом кадре! Это определенно скажется на производительности.

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

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

Рисунок 1. – Шар может столкнуться только с объектами в соседних ячейках

Шар, показанный на рисунке 1, расположен в центре ячейки. Объекты, которые могут с ним столкнуться, должны находиться в затененной области. Объекты, которые находятся в белых ячейках, с этим шаром столкнуться не могут. Даже если шар будет на самом краю серой ячейки, и другой шар был на самом краю белой ячейки, они не смогут столкнуться друг с другом (см. рисунок 2).

Рисунок 2. – Два шара не могут столкнуться

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

Ок, это основное условие. Зная его можно продолжить решение проблемы несколькими способами. Я не уверен, что это лучший путь, но суть состоит в проверке каждого объекта находящегося в зоне досягаемости, и быть уверенным, что объекты не проверяются дважды. Это довольно непросто.

Я выделю метод, который будет казаться довольно абстрактным. Попытайтесь понять идею определения столкновения в области сетки. Далее мы обсудим это подробней.

Шаг 2. Реализация определения столкновения

Итак, начнем с левого верхнего угла. Я уменьшил размер сетки, чтобы упростить пример.

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

Рисунок 3.

Двигаемся дальше. Смотрим на рисунок 4. Здесь у нас появляется еще пара ячеек, которые должны быть проверены, но мы помним, что уже проверили первую (белую на рисунке) со всеми объектами в окружающих ее ячейках, включаю и ту, в которой сейчас находится наш главный объект. Поэтому нет необходимости проверять первую ячейку снова.

Рисунок 4.

Аналогично мы продолжаем двигаться по первой строке. Мы должны проверять текущую ячейку, ячейку справа и три ячейки снизу. См рисунок 5.

Рисунок 5.

Конечно, когда мы доберемся до левого края экрана, то нам нужно будет проверить только две нижних ячейки.

Перейдем на вторую строку. См рисунок 6.

Рисунок 6.

Снова мы должны проверить все окружающие ячейки, но верхняя строка уже проверена с ячейками второй строки. Поэтому проверку верхней строки мы пропускаем.
Наконец переходим к последней строке. Смотрим на рисунок 7.

Рисунок 7.

Аналогично, верхняя строка уже проверена, нижняя строка отсутствует, поэтому нам остается проверить только ту ячейку, которая справа. Когда мы дойдем до последней ячейки, то нам уже ничего проверять не нужно, т.к. все уже проверено :). См рисунок 8.

Рисунок 8.

Ок, мы сделали это. Что делать теперь? Итак, самое большее, с чем нам придется иметь дело это пять ячеек: текущая ячейка, одна ячейка справа и три ячейки снизу. Каждую из этих ячеек можно представить как массив находящихся в ней объектов. Назовем эти объекты cell0, cell1, cell2, cell3, cell4, and cell5. Для простоты примем, что каждая ячейка может содержать только объекты типа Ball (шар).

Теперь возьмем cell0, первый массив шаров. Любой из шаров в этой ячейке может столкнуться с любым из других в этой же ячейке, поэтому необходимо проверить каждый с каждым. Мы сделаем это с помощью вложенного цикла, как показано ниже

for (var i:int = 0; i < cell0.length - 1; i++)
{
var ballA:Ball = cell0[i] as Ball;

for (var j:int = i + 1; j < cell0.length; j++)
{
var ballB:Ball = cell0[j] as Ball;
//Проверка столкновения между ballA и ballB. Код не показан.
}
}

Этот код проверяет каждый шар с каждым в массиве cell0, каждый шар не проверяет столкновение сам с собой и не проверяется столкновение любой пары дважды. Теперь проверим cell0 и cell1. Здесь мы проверяем каждый шар из массива cell0 с каждым из cell1.

for (var i:int = 0; i < cell0.length; i++)
{
var ballA:Ball = cell0[i] as Ball;

for (var j:int = 0; j < cell1.length; j++)
{
var ballB:Ball = cell1[j] as Ball;
//Проверка столкновения между ballA и ballB. Код не показан.
}
}

Заметим, что этот код проверяет каждый элемент массива cell0 с каждым из элементов массива cell1, в первом примере мы должны были использовать уловки, чтобы не проверять объект сам с собой и не проверять пару шаров дважды. Здесь, мы можем не беспокоится об этом, т.к. имеем дело с двумя массивами, которые содержат совершенно разные элементы.

Мы можем повторить последний код для проверки cell0 с cell2, cell3, cell4 и cell5. В текущей позиции cell0 проверен, и мы можем переместиться в следующую ячейку, которая теперь становится cell0. Конечно, как было показано выше, для проверки ячеек находящихся на краях экрана необходимо делать проверку меньше четырех ячеек. Это нужно принимать во внимание.

Шаг 3. Код сетки

Ок, наш первый шаг будет прост. Мы разберем подробно каждую функцию, чтобы вы могли видеть, как все происходит. Перед тем, как погрузиться в определение столкновений, создадим класс Ball (шар):

Ball.as

package
{
	import flash.display.Sprite;

	public class Ball extends Sprite
	{
		private var _color:uint;
		private var _radius:Number;
		private var _vx:Number = 0;
		private var _vy:Number = 0;
		
		
		public function Ball(radius:Number, color:uint = 0xffffff)
		{
			_radius = radius;
			_color = color;
			draw();
		}
		
		private function draw():void
		{
			// draw a circle with a dot in the center
			graphics.clear();
			graphics.lineStyle(0);
			graphics.beginFill(_color, 1);
			graphics.drawCircle(0, 0, _radius);
			graphics.endFill();
			graphics.drawCircle(0, 0, 1);
		}
		
		public function update():void
		{
			// add velocity to position
			x += _vx;
			y += _vy;
		}
		
		public function set color(value:uint):void
		{
			_color = value;
			draw();
		}
		
		public function get color():uint
		{
			return _color;
		}
		
		public function set radius(value:Number):void
		{
			_radius = value;
			draw();
		}
		
		public function get radius():Number
		{
			return _radius;
		}
		
		public function set vx(value:Number):void
		{
			_vx = value;
		}
		
		public function get vx():Number
		{
			return _vx;
		}
		
		public function set vy(value:Number):void
		{
			_vy = value;
		}
		
		public function get vy():Number
		{
			return _vy;
		}
		
	}
}

Здесь нет ничего сложного. Задаем радиус и цвет, затем отрисовываем круг. Каждый круг сохраняет приращения по осям х и у и прибавляет их к текущей позиции, когда происходит обновление экрана. Теперь создадим класс приложения, который вы можете использовать как главный в Flex Builder, или как класс документа в Flash CS3 или CS4. Убедитесь, что класс Ball находится в той же папке, что и класс приложения. Для простоты я сохраняю все классы в безымянном пакете package. Вы можете организовать структуру классов как вам удобно. Итак класс GridCollision:

package {
	import flash.display.Sprite;
	import flash.display.StageAlign;
	import flash.display.StageScaleMode;
	import flash.utils.getTimer;

	public class GridCollision extends Sprite
	{
		private const GRID_SIZE:Number = 50;
		private const RADIUS:Number = 25;
		
		private var _balls:Array;
		private var _grid:Array;
		private var _numBalls:int = 100;
		private var _numChecks:int = 0;
		
		public function GridCollision()
		{
			stage.align = StageAlign.TOP_LEFT;
			stage.scaleMode = StageScaleMode.NO_SCALE;
			
			makeBalls();
			drawGrid();
			makeGrid();
			assignBallsToGrid();
			checkGrid();
			trace(_numChecks);
		}
		
		
		private function makeBalls():void
		{
			_balls = new Array();
			for(var i:int = 0; i < _numBalls; i++)
			{
				// создаем экземпляр класса Ball, добавляем его в список отображения
				// и в массив _balls
				var ball:Ball = new Ball(RADIUS);
				ball.x = Math.random() * stage.stageWidth;
				ball.y = Math.random() * stage.stageHeight;
				addChild(ball);
				_balls.push(ball);
			}
		}
		
		private function makeGrid():void
		{
			_grid = new Array();
			// stage width / grid size = номер колонки
   			for(var i:int = 0; i < stage.stageWidth / GRID_SIZE; i++)
			{
				_grid[i] = new Array();
				// stage height / grid size = номер строки
				for(var j:int = 0; j < stage.stageHeight / GRID_SIZE; j++)
				{
					_grid[i][j] = new Array();
				}
			}
		}
		
		private function drawGrid():void
		{
			// рисуем сетку
			graphics.lineStyle(0, .5);
			for(var i:int = 0; i <= stage.stageWidth; i += GRID_SIZE)
			{
				graphics.moveTo(i, 0);
				graphics.lineTo(i, stage.stageHeight);
			}
			for(i = 0; i <= stage.stageHeight; i += GRID_SIZE)
			{
				graphics.moveTo(0, i);
				graphics.lineTo(stage.stageWidth, i);
			}			
		}
		
		private function assignBallsToGrid():void
		{
			for(var i:int = 0; i < _numBalls; i++)
			{
				// определяем позицию каждого шара в сетке
				// из массива _balls
				var ball:Ball = _balls[i] as Ball;
				var xpos:int = Math.floor(ball.x / GRID_SIZE);
				var ypos:int = Math.floor(ball.y / GRID_SIZE);
				_grid[xpos][ypos].push(ball);
			}
		}
		
		private function checkGrid():void
		{
		    // с помощью цикла обходим каждую ячейку сетки
		    for(var i:int = 0; i < _grid.length; i++)
		    {
		        for(var j:int = 0; j < _grid[i].length; 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:Array = _grid[x][y] as Array;
			
			for(var i:int = 0; i < cell.length - 1; i++)
			{
				var ballA:Ball = cell[i] as Ball;
				for(var j:int = i + 1; j < cell.length; j++)
				{
					var ballB:Ball = cell[j] as Ball;
					checkCollision(ballA, ballB);
				}
			}
		}
		
		private function checkTwoCells(x1:int, y1:int, x2:int, y2:int):void
		{
			// убеждаемся в наличии второй ячейки
			if(x2 < 0) return;
			if(x2 >= _grid.length) return;
			if(y2 >= _grid[x2].length) return;
			
			var cell0:Array = _grid[x1][y1] as Array;
			var cell1:Array = _grid[x2][y2] as Array;
			
			// проверяем каждый объект в текущей ячейке
			// с каждым объектом в соседней ячейке
			for(var i:int = 0; i < cell0.length; i++)
			{
				var ballA:Ball = cell0[i] as Ball;
				for(var j:int = 0; j < cell1.length; j++)
				{
					var ballB:Ball = cell1[j] as Ball;
					checkCollision(ballA, ballB);
				}
			}
		}
		
		private function checkCollision(ballA:Ball, ballB:Ball):void
		{
			// если расстояние между центрами двух шаров
			// меньше суммы их радиусов, то они столкнулись
			_numChecks++;
			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;
			}
		}
	}
}

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

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

Теперь разберем методы класса. Начнем с makeBalls().

private function makeBalls():void
{
	_balls = new Array();
	for(var i:int = 0; i < _numBalls; i++)
	{
		// создаем экземпляр класса Ball, добавляем его в список отображения
		// и в массив _balls
		var ball:Ball = new Ball(RADIUS);
		ball.x = Math.random() * stage.stageWidth;
		ball.y = Math.random() * stage.stageHeight;
		addChild(ball);
		_balls.push(ball);
	}
}

Повторим, ничего здесь сложного нет. Здесь создается массив _balls для хранения шаров, запускается цикл для создания экземпляров класса Ball, затем они располагаются в случайном порядке, добавляются в список отображения и добавляются в массив _balls.

Следующий метод makeGrid():

private function makeGrid():void
{
	_grid = new Array();
	// stage width / grid size = номер колонки
   	for(var i:int = 0; i < stage.stageWidth / GRID_SIZE; i++)
	{
		_grid[i] = new Array();
		// stage height / grid size = номер строки
		for(var j:int = 0; j < stage.stageHeight / GRID_SIZE; j++)
		{
			_grid[i][j] = new Array();
		}
	}
}

Здесь мы создаем двухмерный массив [[КОЛОНКА][ ЯЧЕЙКА]], в котором каждый элемент ЯЧЕЙКА представляет собой квадратную ячейку. Каждая ячейка – это массив для хранения находящихся в ней объектов.

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

private function drawGrid():void
{
	// рисуем сетку
	graphics.lineStyle(0, .5);
	for(var i:int = 0; i <= stage.stageWidth; i += GRID_SIZE)
	{
		graphics.moveTo(i, 0);
		graphics.lineTo(i, stage.stageHeight);
	}
	for(i = 0; i <= stage.stageHeight; i += GRID_SIZE)
	{
		graphics.moveTo(0, i);
		graphics.lineTo(stage.stageWidth, i);
	}			
}

А вот одни из самых важных методов:

private function assignBallsToGrid():void
{
	for(var i:int = 0; i < _numBalls; i++)
	{
		// определяем позицию каждого шара в сетке
		// из массива _balls
		var ball:Ball = _balls[i] as Ball;
		var xpos:int = Math.floor(ball.x / GRID_SIZE);
		var ypos:int = Math.floor(ball.y / GRID_SIZE);
		_grid[xpos][ypos].push(ball);
	}
}

Этот код требует пояснения. Первая часть очевидна: цикл выполняется для каждого элемента массива _numBalls. Затем мы делим координаты х и у на размер сетки и округляем в сторону меньшего значения. Это дает нам номера столбца и строки, в которые должен быть помещен каждый шар. См рисунок 9.

Рисунок 9.

На этом рисунке размер ячейки сетки составляет 100х100. Шар, который вы видите, имеет координаты х=380, у=280. Мы делим 380 на 100 и получаем 3.8. Затем округляем до 3 и получаем номер колонки 3. Помня о том, что нумерация элементов массива начинается с нуля, получаем, что индекс 3 дает на четвертую колонку. Тем же способом получаем третью строку для нашего шара.

Мы присваиваем результаты вычислений переменным xpos и ypos, которые используем как индексы двухмерного массива, которым представлена наша сетка. Т.к. каждый элемент сетки сам является массивом, то мы добавляем каждый шар в этот массив как его элемент.

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

Метод checkGrid() делает всю черную работу. Он содержит несколько других методов, которые мы рассмотрим ниже. Начнем:

private function checkGrid():void
{
    // с помощью цикла обходим каждую ячейку сетки
for(var i:int = 0; i < _grid.length; i++)
{
	 for(var j:int = 0; j < _grid[i].length; 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); // проверка с объектами ячейки снизу справа
	}
}
}

Мы используем цикл в цикле, чтобы пройти все столбцы и строки сетки. Индексы i и j показывают ячейку, которая проверяется в текущий момент. Сначала, с помощью метода checkOneCell() мы проверяем все объекты, которые находятся в текущей ячейке.

private function checkOneCell(x:int, y:int):void
{
	// проверяем каждый объект в текущей ячейке друг с другом			
	var cell:Array = _grid[x][y] as Array;
			
	for(var i:int = 0; i < cell.length - 1; i++)
	{
		var ballA:Ball = cell[i] as Ball;
		for(var j:int = i + 1; j < cell.length; j++)
		{
			var ballB:Ball = cell[j] as Ball;
			checkCollision(ballA, ballB);
		}
	}
}

Теперь мы вызываем метод checkTwoCells() четыре раза:

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); // проверка с объектами ячейки снизу справа

Индексы i и j обращаются к текущей ячейке которую мы проверяем, индексы i+1, j обращаются к ячейке справа; i-1, j+1 – к ячейке снизу слева; i, j+1 – к ячейке снизу; i+1, j+1 – к ячейке снизу справа. Ниже представлен код метода checkTwoCells():

private function checkTwoCells(x1:int, y1:int, x2:int, y2:int):void
{
	// убеждаемся в наличии второй ячейки
	if(x2 < 0) return;
	if(x2 >= _grid.length) return;
	if(y2 >= _grid[x2].length) return;
			
	var cell0:Array = _grid[x1][y1] as Array;
	var cell1:Array = _grid[x2][y2] as Array;
			
	// проверяем каждый объект в текущей ячейке
	// с каждым объектом в соседней ячейке
	for(var i:int = 0; i < cell0.length; i++)
	{
		var ballA:Ball = cell0[i] as Ball;
		for(var j:int = 0; j < cell1.length; j++)
		{
			var ballB:Ball = cell1[j] as Ball;
			checkCollision(ballA, ballB);
		}
	}
}

Здесь значения i и j присваиваются параметрам метода х1 и у1 соответственно. Эти параметры используются для получения первой из проверяемых ячеек. Следующие два параметра используются для получения второй из проверяемых ячеек. Нам нужно удостовериться, что они находятся в требуемом диапазоне. Если х2 меньше нуля или больше или равно длине массива _grid.length, то _grid[x2] будет иметь значение null. Это произойдет, если главная ячейка будет находиться в первом или последнем столбце. Также, если у2 больше чем число ячеек в этом столбце, это приведет к значению у2 равном null. Если произойдет любой из этих случаев, то метод checkTwoCells() будет выполняться неправильно.

Мы используем цикл в цикле для проверки каждого объекта первой ячейки с каждым объектом второй ячейки так, как делали ранее. Наконец последнее по порядку, но не последнее по значению – сама проверка столкновения. Мы вызываем метод checkCollision(), который использует полученные ранее описания для каждого проверяемого объекта. Ниже представлен код этого метода:

private function checkCollision(ballA:Ball, ballB:Ball):void
{
	// если расстояние между центрами двух шаров
	// меньше суммы их радиусов, то они столкнулись
	_numChecks++;
	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;
	}
}

Поскольку мы добрались до реального определения столкновения между двумя объектами, обновим свойство _numChecks. Теперь мы используем стандартное определение столкновения, основанное на определении расстояния между центрами объектов и сравнения его с радиусом шара. Если оно меньше радиуса, значит произошло столкновение и шары окрашиваются в красный цвет.

Мы проделали большую работу, благодаря которой нам не нужно вызывать метод checkCollision() тысячи раз. Если вы все сделали правильно, то у вас должно получиться что-то похожее на это:

Рисунок 10.