Пиксельный поиск пути
29.09.2008, автор Stormit, рубрики: ActionScript, Flash игры, Игровые баннерыЭто продолжение предыдущего поста о простом движке для flash-игр. Тогда, в самом конце возникла мысль уйти от метода hitTest() и перейти на пиксельный просчёт. И чтобы сравнить оба способа и выбрать лучший вариант, сделал небольшой визуальный тест.
Кстати, в тот раз я написал не совсем правильный код. Команда break не выводила процесс из вложенного цикла и бессмысленно терялось много процессорных ресурсов. Странно, но никто по этому поводу не отписался. Значит либо все “внимательно” читают и пробуют, либо верят на слово 
Этот баг я поправил. Дальше по слайдам:
- Настало время сделать это. hitTest() или getPixel()? Чья возьмёт? Кто будет править игровым миром?
- Символ path немного изменился, теперь он чёрно-белый, где белый цвет отвечает за проходимость, а чёрный задает препятствия (отверстий теперь нет - закрашено всё).
- Код из прошлого примера заменяем на этот:
import flash.display.BitmapData; step = 2; //переводим зону проходимости в пиксельный вид var pathBD = new BitmapData(path._width, path._height, false, 0x000000); pathBD.draw(path); path._visible = false; onEnterFrame = function () { var dx = _xmouse - man._x; var dy = _ymouse - man._y; var angle = Math.atan2(dy, dx); var dist = Math.sqrt(dx * dx + dy * dy); if (dist > step) { tgtX = man._x + step * Math.cos(angle); tgtY = man._y + step * Math.sin(angle); //Если цвет пиксела черный, значит препятствие if (pathBD.getPixel(tgtX, tgtY) == 0) { var dAngle = dAngleRadian(direction, angle); workAngle = angle + dAngle * .8; var outFlag = false; for (var i = 0; i < 360 && !outFlag; i += 15) { for (var j = -1; j <= 1; j += 2) { var a = workAngle + radian(i) * j; var tempX = man._x + step * Math.cos(a); var tempY = man._y + step * Math.sin(a); if (pathBD.getPixel(tempX, tempY) != 0) { tgtX = tempX; tgtY = tempY; break; } } } } var timeDx = tgtX - man._x; var timeDy = tgtY - man._y; direction = Math.atan2(timeDy, timeDx); var dAngle = dAngleDegree(direction * 180 / Math.PI, man._rotation); man._rotation += dAngle * .2; man._x = tgtX; man._y = tgtY; play(); } else { gotoAndStop(5); } }; function dAngleRadian (a1, a2) { var da = a1 - a2; if (da > Math.PI) { da = -Math.PI * 2 + da; } else if (da < -Math.PI) { da = Math.PI * 2 + da; } return da; }; function dAngleDegree(a1, a2) { var da = a1 - a2; if (da > 180) { da = -360 + da; } else if (da < -180) { da = 360 + da; } return da; }; function degree(a) { return a / Math.PI * 180; }; function radian(a) { return a / 180 * Math.PI; };
Чтобы меньше грузить процессор, я перевел анимацию персонажа в растр.
- А теперь небольшое сравнение. 50 юнитов, метод getPixel(). Для чистоты эксперимента поместите мышку в центр озера, чтобы объекты выполняли максимальный просчёт.
- 50 юнитов, метод hitTest()
- Зона без препятствий. На каждого юнита приходится один вызов функции каждый кадр. 150 юнитов, метод getPixel()
- 150 юнитов, метод hitTest()
- Специально для быстрых машин - 300 спартанцев и getPixel()
- 300 спартанцев и hitTest()
Лично у меня пиксельный способ работает быстрее, но… незначительно. На моем старичке Атлоне 2.5 всего лишь 3 фпс разницы. Честно говоря я ожидал большего, но если уж выбирать, то лучше пусть это будет BitmapData и метод getPixel(). Если же у вас по какой-то причине постоянно меняется рельеф местности, тогда наверное hitTest() будет более кстати.
Если кто-нибудь сделает толковую игру на таком движке, дайте ссылку 
Интересно на 59%
У меня 32 fps на обоих тестах - вообще никакой разницы.
Разница незначительная.
Просто у меня 13 и 16 фпс получается. А вам значит нужно наштамповать их штук 300 в зоне с препятствиями
У меня тоже 32 и 32 :\ Никакой разницы.
Добавил утяжелённый вариант - 300 юнитов (слайды 8 и 9)
Если навести мышку в центр правого озера, то при 300 юнитах оба варианта показывают 8 fps. Разницы никакой.
У меня разница чувствуется только на последнем (300 с препятствиями) тесте 7 fps hitTest() vs 9 fps getPixel()
разницы нет. Думается наиболее ресурсоемкие здесь конструкции вроде Math.cos, Math.sqrt. Да и в общем, конечно, вычислять направление на каждом кадре для всех юнитов никаких ресурсов не хватит
Да, всеравно разницы никакой. и там, и там 19 fps.
to Griman
Так и есть. Сами по себе эти расчёты прилично тормозят.
Частично от них можно избавиться если проверять расстояние без извлечения корня (расстояние и шаг в квадрате): if (dist2 > step2) {}
А точки пробивать так: один раз создаётся вектор под 45 градусов назад от базового направления и дальше прибавлять его. Будет небольшое торможение о препятствие, что в общем-то естественно.
Эмс… интересно… а если сделать тот же поиск пути? Больше будет есть? Если его применять то можно избавиться от некоторой зацикленности во “впадинах” препятствий… Да и не будет постоянно пересчитываться когда будет движение объектов, только при смене позиции мышки…
На последнем хитТест проигрывает, но не сразу постепенно “выдыхается”
никакой раздницы товарищи!
А где предыдущий пример? А то мне этот код не идет!
Вообще getPixel не работает.
Подозреваю что нужно экспортить под более позднюю версию флэш-плеера
Подозреваю что нужно экспортить под более позднюю версию флэш-плеера…
Код?
Мне кажется мы говорим на разных языках.
Если у вас получался раньше предыдущий пример (он никуда с блога не исчезал), то просто замените его код на этот (приведён выше).
В настройках Publish Settings (Ctrl+Shift+F12) выберите версию Flash Player 8 или выше.
У меня кажись шестая версия Макромедии.
А дело в том, что я не знаю ссылки на предыдущий пример.
И спасибо за ответ
Получается символ патч и символ мэн должны быть на одном слое? А как же тогда цветная графика, куда её?
Они должны быть на одной временной линейке (чтобы переменные в коде находили символы). Цветная графика вставляется сверху символа path, слоем выше.
Тогда мувик man не будет видно.
Почему? Он лежит над цветной графикой.
Каждому свой слой - как видите во флэше, так и в флэшке будет.
Перечитал код, у вас visible+false, врубился. Простите за излишние вопросы.
великолепный туториал. ну хочешь его на английский перевести и на мочимедия опубликовать? заодно посещаемость подымишь.
еще раз спасибо, игру уже делаю =))))))) точнее есть, щас только туда это вставлю. покажу потом =)
Можно попробовать, хотя мой английский оставляет желать лучшего
Английский исправим, это не проблема =)
что такое direction ? =)
код не полный =))) ща его вроде вставил.. но чето не то =(
а все разобрался. это текущее направление движения в радианах +)
http://badim.ru/ef_dota/ <- герой и войска, которыми можно управлять обходят здания и башни по этому алгоритму =) мелкие косяки конечно есть.
при больших нагрузках видно оч хорошо (8, 9) так что getPixel() рулит
да, и гет пикселя есть важное приемущество =)
битмапдатами проще управлять =)
Огромное спасибо за поиск пути! Супер сайт… Однако мне больше подошел с методом hit-test.
Кстати, вот игра, куда включен поиск пути… Тоже стратегия =) http://fsstar.do.am/load/1-1-0-17
Извиняюсь… Эта ссылка лучше: (Не хочу принуждать желающих посмотреть игру регистрироваться на сайте) http://fsstar.do.am/_ld/0/17_city-sim0.swf
Кстати, о игре Badim’а… Прикольная, только юнитов не видно иногда (чужих)… А так очень даже прелестно… (Особенно дизайн главного меню).
Еще… Никто не подскажет, как лучше нарисовать идущего человека с видом сверху?
Сейчас человек начинает обходить ров по часовой стрелке. Если мост поставить чуть ниже, он на него никак не отреагирует (а должен) и пойдет обходить пока его не нащупает.
:)) это Settlers это Супер :о))
MayorAndrew
правда есть баги
Можно заказать человечка и он будет стоять у ангара до упора, когда построил ферму человечки больше не заказывались.
Ну и рейд охотников вокруг озера уже описали.
Да уж… Багов действительно достаточно.
Однако, у меня была игра (я сам тоже сделал). Она тоже есть на сайте (CupKiller называется). Так вот, там иногда не удаляются патроны, которые вылетают снизу… А если игру запускать с компьютера все вроде работает.
Об этих багах мне не раз говорили, однако ничего сделать с ними у меня пока не получалось… (Когда запускаю на компьютере, их нет…)
Кстати, охотники по мосту потом все-таки проходят? Если да… то впринципе все понятно… (Поэтому строю два моста =))
А можно-ли как нибудь это с помощью ГетПикселя реализовать? У меня идет ХитТест по невидимым путям, которые ставятся вместе с зданиями…
Можно одновременно с постройкой сооружения (мост, здание…) в объекте BitmapData закрашивать соответствующую область чёрным (проще, наверное, хранить набор таких клипов и добавлять их в виде растра в карту пути).
http://badim.ru/ef_dota/
у меня при постройке башен, зданий обновляеться карта проходимости.
К сожалению действительно разницы нету - а так хотелось.
Народ а как сделать с помощью с помощью хитеста, оно что-то совсем не работает со сложными фигурами.
Не совсем понял вопрос.
Статья как раз о том, как сделать это с помощью хиттеста или getPixel. Для сложных форм нужно просто подбирать параметры (описаны в статье), чтобы персонажи не дёргались и путь корректно находили.
В данном случае первый объект это точка с координатами х,у, а второй это вот всякие сложные фигурки. А если надо сложная фигура + сложная фигура, никак немогу разобраться как сделать
Вот с этих “ложная фигура + сложная фигура” нужно сделать объект BitmapData. Он является “картой проходимости” в чёрно/белом виде. По нему и проверяется пересечение.
Если у вас периодически добавляются и пропадают препятствия на карте, за этим нужно следить и закрашивать соответствующие зоны на “карте проходимости” чтобы они учитывались при поиске пути.
Переписал на ас3, при входе в цикл обработки препятствия координаты нового шага сбрасываются в NaN и соответственно мэн прыгает в 0,0
что бы это могло быть?
ага, вот и причина - не объявленные переменные:
tgtX
tgtY
direction
workAngle
AS3 более строг в написании. Поэтому я для простоты и доступности пишу здесь на AS1
Можете дать исходник этой флешки zloudoktor(собака)mail.ru
Или на вашем сайте
А у мя шото эт код не работает что я делаю не так?
var pathBD = new BitmapData(path._width, path._height, false, 0×000000); вот в этой строчке ошибка, а еслив её удалить то объект не реагирует на столкновение
при помощи drive() можно и тут менять рельеф местности
Сайт супер! Но посты бывают редко (
Пытаюсь переписать на AS3. Все переменные объявил, ошибок нет, но man все время сбрасывается в точку (0,0). Как это можно исправить?
Привет, можете мне какимто образом помоч…у меня такая дилема, ни один из движков непроходимих обектов произвольной формы почемуто неработает, уже 4 дней все пробою но ничего неработает,…что ето может быть ?на каком языке ети скрипты? ктота может дать ‘исходник’?
А размеры человека кто будет учитывать?
Сайт супер! Спасибо.
Поиск пути сделан очень не оптимально, сойдет только если очень мало юнитов.
Я делал поиск пути методом потенциальных полей:
http://www.swfcabin.com/open/1272019894
F8 +10 человек
F9 +50 человек
У меня на asus 1.6 тянет 400 юнитов с фпс около 30, у некоторых за тыщу тянет…
При этом код еще можно оптимизировать, чтоб был быстрее.
Основная идея - зачем определять коллизии с точностью до пикселя? Можно же поделить все на сетку 8х8…
На АS3 не работает, при столкновении бросает героя в (0,0).
Разница есть! у меня на 50 юнитах при getPixel fps=20, а при hitTest fps=16
А подскажите как сделать 50 юнитов как в этом примере? мне очень срочно надо!
Хочу сделать несколько противников движущихся на игрока. Противника сделал,
а вот как сделать несколько ни как не получается. Подскажите кто-нибудь!
Еще для обхода препятствий есть волновой метод. В общем тоже неплохой метод, правда малость придется помучатся еще чтобы если бежит толпа, чтобы они не накладывались друг на друга. В стратегиях его вроде чаще всего и используют.