Форум Flasher.ru - Простая физика: плиточный мир и ограничение столкновений

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

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

Всем привет!

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

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

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

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

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

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

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

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

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

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

PhysTest.swf (2.5 Кб)

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

Код AS3:

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;

                }

        }

}

Цитата:

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

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

Цитата:

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

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

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

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

gloomyBrain, спасибо.

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

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

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

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

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

Цитата:

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

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

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

Код:

n = Math.round(Math.max(pos2X - pos1X, pos2Y - pos1Y, 1));

xi = pos1X + (i / n) * (pos2X - pos1X);

yi = pos1Y + (i / n) * (pos2Y - pos1Y);

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

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

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

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

Цитата:

gloomyBrain, спасибо.

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

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

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

Цитата:

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

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

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

Вложение 30124

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

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

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

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

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

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

Цитата:

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

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

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

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