Простая физика: плиточный мир и ограничение столкновений

[Hauts]

Всем привет!

У меня тут случилась вроде бы простая задача, но всё никак не получается решить. Буду благодарен за любую помощь.

В общем, есть некий игровой уровень. Он строится из квадратных "блоков" фиксированного размера (30 пикселей), каждый из которых занимает свою "ячейку", координаты которой кратны размеру. Если проще — подобно тому, как закрашиваем клетки в тетрадном листе.

На этом уровне есть персонаж. Его размер кратен размеру блоков, и он, по-сути, является "склеенными" двумя блоками. В ширину персонах 30 пикселей, в высоту 60. В общем, два "блока".

Персонаж может менять свои координаты, при этом его положение не ограничивается кратностью размера. Он может иметь любые координаты.

Теперь, собственно, к проблеме.

Я не использую каких-либо физических движков (их и не предлагать, кстати). Мне необходимо найти алгоритм ограничения персонажа таким образом, чтобы его габаритная фигура (прямоугольник из двух "блоков") не пересекал клетки и, в ситуациях, когда под персонажем нет клеток (падение), он просто смещался бы вниз (без ускорения достаточно).

Перемещение персонажа считать внешним процессом, никак не зависящим от алгоритма. То есть по факту, при каждой новой итерации алгоритма (энтерфрэйм или таймер, не важно) я должен смотреть, зашел ли персонаж на стенку или "вдавился" ли в пол и, соответственно, разруливать эту ситуацию.

Первое, что приходит на ум — проверка соседних клеток. Если координаты персонажа "входят" в клетку под ним, то сдвинуть его вверх. Если слева от него — сдвинуть вправо и так далее. Но при таком подходе есть неочевидный недостаток, — если персонаж упал на пол, углубился хотя бы чуть-чуть, то его клетками слева и справа станут клетки пола, хотя, по-идее, такого быть не должно. Иными словами, если я падаю с движением вправо на совершенно ровный пол из клеток (блоков), то в какой-то момент меня сдвинет в сторону, как от стены.

Если менять последовательность подобных операций (сравнение сначала по вертикали, потом по горизонтали) — толку особого не будет, лишь поменяется вид ошибки.

Я прикрепил очень простенькую заготовку, если у кого возникнет желание помочь / поразбираться.

PhysTest.swf   (2.5 Кб)

И, конечно же, код:

package
{
	import flash.display.Graphics;
	import flash.display.Sprite;
	import flash.display.StageAlign;
	import flash.display.StageScaleMode;
	import flash.events.Event;
	import flash.events.KeyboardEvent;
	import flash.ui.Keyboard;
 
	/**
	 * ...
	 * @author Hauts
	 */
	public class Main extends Sprite
	{
		private var _cells:Array;
		private var _cellsX:Array;
		private var _cellSize:int = 30;
		private var _player:Sprite;
		private var _container:Sprite;
		private var _levelWidth:int;
		private var _levelHeight:int;
		private var _up:Boolean = false;
		private var _down:Boolean = false;
		private var _left:Boolean = false;
		private var _right:Boolean = false;
 
		public function Main():void
		{
			if (stage)
			{
				init();
			}
			else
			{
				addEventListener(Event.ADDED_TO_STAGE, init);
			}
		}
 
		private function init(e:Event = null):void
		{
			removeEventListener(Event.ADDED_TO_STAGE, init);
			// entry point
			stage.scaleMode = StageScaleMode.NO_SCALE;
			stage.showDefaultContextMenu = false;
			stage.align = StageAlign.TOP_LEFT;
			_container = new Sprite();
			addChild(_container)
 
			var map:Array = [];
			map.push([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
			map.push([1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]);
			map.push([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]);
			map.push([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]);
 
			_levelWidth = map[0].length * _cellSize;
			_levelHeight = map.length * _cellSize;
 
			// generate map
			_cells = [];
			_cellsX = [];
			for (var k:int = 0; k < map.length; k++)
			{
				var mapColumn:Array = map[k]
				for (var j:int = 0; j < mapColumn.length; j++)
				{
					if (mapColumn[j] != 0)
					{
						var cell:Sprite = createBlock(_cellSize, _cellSize);
						cell.x = _cellSize * j;
						cell.y = _cellSize * k;
						_cells.push(cell)
						if (_cellsX[j] == null)
						{
							_cellsX[j] = [];
						}
						_cellsX[j][k] = cell;
					}
				}
			}
 
			// create 'player' element
			_player = createBlock(_cellSize, _cellSize * 2, 0x00FF00);
			_player.x = _cellSize * 1.25
			_player.y = _cellSize * 2.75
 
			stage.addEventListener(KeyboardEvent.KEY_DOWN, keyHandler);
			stage.addEventListener(KeyboardEvent.KEY_UP, keyHandler);
			addEventListener(Event.ENTER_FRAME, enterFrameHandler);
			enterFrameHandler(null)
		}
 
		private function keyHandler(e:KeyboardEvent):void
		{
			var value:Boolean = e.type == KeyboardEvent.KEY_DOWN;
			var keyCode:uint = e.keyCode;
			if (keyCode == Keyboard.UP)
			{
				_up = value;
			}
			if (keyCode == Keyboard.DOWN)
			{
				_down = value;
			}
			if (keyCode == Keyboard.LEFT)
			{
				_left = value;
			}
			if (keyCode == Keyboard.RIGHT)
			{
				_right = value;
			}
		}
 
		private function enterFrameHandler(e:Event):void
		{
			if (_left)
			{
				_player.x -= 5.125
			}
			if (_right)
			{
				_player.x += 5.125
			}
			if (_up)
			{
				_player.y -= 7.125
			}
			if (_down)
			{
				_player.y += 7.125
			}
			alignToPlayer()
		}
 
		private function alignToPlayer():void
		{
			var sw:int = stage.width;
			var sh:int = stage.height;
			_container.x = sw / 2 - _player.x;
			_container.y = sh / 2 - _player.y;
			if (_container.y > 0)
			{
				_container.y = 0;
			}
			if (_container.x > 0)
			{
				_container.x = 0;
			}
		}
 
		private function createBlock(width:int, height:int, color:uint = 0xFF0000):Sprite
		{
			var blockSprite:Sprite = new Sprite();
			var gr:Graphics = blockSprite.graphics;
			gr.beginFill(color, 0.35);
			gr.lineStyle(1, 0);
			gr.drawRect(0, 0, width, height);
			gr.endFill();
			gr.lineStyle(2, 0);
			gr.moveTo(-1, 0)
			gr.lineTo(1, 0)
			gr.moveTo(0, -1)
			gr.lineTo(0, 1)
			blockSprite.cacheAsBitmap = true;
			_container.addChild(blockSprite)
			return blockSprite;
		}
	}
}

[gloomyBrain]

Если менять последовательность подобных операций (сравнение сначала по вертикали, потом по горизонтали) — толку особого не будет, лишь поменяется вид ошибки.

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

[expl]

Иными словами, если я падаю с движением вправо на совершенно ровный пол из клеток (блоков), то в какой-то момент меня сдвинет в сторону, как от стены.

Если менять последовательность подобных операций (сравнение сначала по вертикали, потом по горизонтали) — толку особого не будет, лишь поменяется вид ошибки.

Ну, можно сложить сначало все смещения, а потом применить.

Кажется, решение вашей проблемы, на 6-м кадре:
http://xitri.com/2009/06/16/simple-p...me-engine.html

[Hauts]

gloomyBrain, спасибо.

Но вы не правы, как мне кажется. Очень сложно объяснить, в чем траббл такого решения (я его пробовал, да), но попробую.

В общем, если я сначала выставлю персонажу vx и vy, как значения, насколько он должен быть сдвинут в текущей итерации, то в момент, когда я должен ограничивать персонажа (точнее vx и vy) я опять же приду к ситуации, описаной в первом сообщении. Ну получу я два результата, — перс при применении его на vx и vy "заходит" на клетку (блок) по y и по x (диагонально двигается, например). И, в зависимости от того, что я исправлю первым, я получу разные результаты, но все равно не подходящие.

Я ограничу его по y, когда он всего-лишь падает прижавшись к стенке и он прилипнет к ней, стоя на воздухе? Нет, не вариант.

Если я неправильно понял, поправьте.

Добавлено через 4 минуты
expl, о, спасибо, что-то я про хитри забыл совсем

[expl]

Но вы не правы, как мне кажется. Очень сложно объяснить, в чем траббл такого решения (я его пробовал, да), но попробую.

Оно не факт, что хорошее, но работает вполне.

Как у меня это работало:
- Берем текущую позицию
- Берём позицию после перемещения
- Перебираем n промежуточных вариантов тупым циклом

n = Math.round(Math.max(pos2X - pos1X, pos2Y - pos1Y, 1));
xi = pos1X + (i / n) * (pos2X - pos1X);
yi = pos1Y + (i / n) * (pos2Y - pos1Y);

т.е. гарантированно не грубее одного пикселя
- На каждой итерации смотрим, не пересекает ли наш прямоугольник препятствия
- Если пересекает - останавливаемся и считаем текущее положение конечным.
Способ варварский, но на том платформере к тормозам не приводил. Поэтому мне было всё равно

[Hauts]

expl, да, понял. Мультисэмплинг при перемещении в предалах размера клетки такой мне убеждения не позволят сделать, вот в чем проблема. Если скорость перемещения будет больше, то конечно, буду использовать (с шагом в 1/2 клетки к примеру).

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

Вообще я уверен, что есть некий вполне доступный понятный алгоритм для моей ситуации, но вот только я до него не могу додуматься. Что-то мне подсказывает, что в нем должны учитываться направление смещения персонажа и соотношение пересекаемой стороны блока и вектора (?) смещения.

[gloomyBrain]

gloomyBrain, спасибо.

Но вы не правы, как мне кажется.

Я ограничу его по y, когда он всего-лишь падает прижавшись к стенке и он прилипнет к ней, стоя на воздухе? Нет, не вариант.

Эмм? я предлагаю Вам сначала вычислять позицию, в которой мы ни с кем не пересекаемся, а потом на эту позицию ставить персонажа. Я нигде не предлагал остановить движение по x, если оно невозможно по y (ну это ж ерунда, зачем мне Вам такое предлагать?)

Как у меня это работало:
- Берем текущую позицию
- Берём позицию после перемещения
- Перебираем n промежуточных вариантов тупым циклом

Я примерно это и имел ввиду. С важной ремаркой, что идти нужно от новой позиции к старой. И вычислить позицию, максимально близкую к новой (то есть допуская касание занятой ячейки, но не допуская пересечения с ней)

[Hauts]

gloomyBrain, если я правильно понимаю, что то, что вы описываете будет работать примерно таким образом:



То есть начинается итерация, происходят следующие действия:

1. Я знаю, насколько мне нужно сдвинуть персонажа, на vx и vy.

2. Я беру длину его предполагаемого пути и, начиная с конечной точки, "шагаю" до текущего положения, на один пиксель. При каждом шаге я проверяю, пересечет ли персонаж (в иллюстрации это точка) клетку. Если не пересекает — обрываю цикл и подправляю его vx и vy так, чтобы при их применении персонаж (точка) точно не пересек клетку.

3. Применяю vx и vy к координатам персонажа.

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

В чем я ошибаюсь, объясните пожалуйста?

[gloomyBrain]

В чем я ошибаюсь, объясните пожалуйста?

В том что зачем-то объединяете движение по x и по y для предложенного мной алгоритма. Разбейте его на 2 составляющие и получите ровно то, что сами и нарисовали.

Но стоит заметить, что цикл тут не обязателен, так как точку пересечения 2 отрезков можно найти аналитически, а не перебором. А именно (по рисунку) - нужно найти пересечение правой стенки ячейки и отрезка пути, который персонаж прошел по оси x. Это первая фаза.
Второй фазой может быть то же самое, проделанное для оси y и "пола" (нижней границы перемещения).

ЗЫ
Вообще была же где-то статья где прям на пальцах расписана плиточная физика. Inils должен знать, я уже не найду ссылку.

[expl]

Может эта?
http://noregret.org/tutor/index.html