- PVSM.RU - https://www.pvsm.ru -
Возможно заголовок слишком кричащий, муза по заголовкам меня покинула. И, да, здесь не будет японских роботов и сюжета фильмов где эти же роботы захватывают мир. Но здесь будет искусственный интеллект (ИИ), так как ИИ можно считать присутствующим, если при принятии решения используется оценочная функция. А она будет в нашем алгоритме поиска пути. И, да, это будет моделирования спасательной операции, заключаться будет в том, что команде спасателей нужно обойти всё здания (все комнаты), найти там людей (который по задумке автора сами спастись не могут) и вывести их из здания. Реализовано все будет на JavaScipt, Canvas, и немного PHP для работы с базой. Думал сначала сделать статью в стиле своей последней [1], то есть обсуждаем именно JavaScript, но не хочу повторятся, так что здесь скорее всего пройдемся по архитектуре самой программы (да, зразу скажу, если может кто очень ждет вторую часть змейки, она в процессе, в комментариях по этому поводу ничего нового не скажу). С бюрократией вроде бы все, приступим.
Что нам нужно сделать? У нас будет граф, то есть все контрольные точки здания, по которых будут бегать наши люди. Выглядеть он будет примерно так:
Кстати здание реальное, это планировка одного из корпусов моего универа. Окей, у нас есть граф по которому нужно бегать. При чем не просто бегать, а кратчайшими путями. Здесь и приходит наш ИИ. Для поиска кратчайшего пути будет использоваться алгоритм Дейкстры. [2] На хабре о нем много статей, и даже несколько реализаций, которые мне упростили много работы. Алгоритм вынесен отдельно, на вход будет получать граф и начальную вершину — возвращать будет набор путей к всех остальным вершинам. Один путь — это массив точек по которых будут бегать спасатели. Как видим у нас четыре выхода, то есть, логично, спасатели будут выводить людей к ближайшему выходу. С теорией все. Приступим к практике.
Получится в нас вот такое ссылка, но сначала пару слов об интерфейсе:
— вы можете изменить к-во спасателей
— вы можете добавлять людей (сколько хотите) по комнатах (просто кликаем по комнате)
— вы можете отображать граф и вершины (за которые можно драг_енд_дропить)
— запускаем по кнопке с соответствующим названием
кто прочел инструкции жмем сюда [3]
Как видим у меня там много кнопок вверху (которые я закоментил, чтобы никто ничего не поламал). Они там для того, чтобы строить сам граф. то есть кликаем по сцене, добавляем вершину, потом соединяем вершины в ребра, потом выставляем на графе комнаты (они станут зеленого цвета), выходы (темно вишневого), можем по ходу если что менять положения вершины, перетаскивая ее, когда граф готов — жмем сохранить в базу. Потом при инициализации считаются табличка точек и табличка рёбер и построится граф.
Точки строились средствами html, но можно было бы сделать их при помощи того же фреймворка LibCanvas [4] например, и так же рисовать их на канвасе, это бы, наверное, было бы даже более правильным решением. Но было сделано так, как это изначально была не просто точка, а там по клику на нее выпадало меню настроек, которые меняли ее тип, добавляли человека и т.д. Но в результате было переделано по-другому. А так как делалось это в последнюю ночь, как всегда, времени менять уже не было.
У нас будет класс этой точки, которая будет хранить координаты и еще много чего. Точек будет много и с эти всем нужно как то удобно работать.
function PointGR(_data) {
this.id = PointGR.setId();
PointGR.statArr.push(this);
}
PointGR.statArr = [];
PointGR.getPointGRById = function(_id) {
for (var i = PointGR.statArr.length; i--;) {
if (PointGR.statArr[i].id == _id) {
return PointGR.statArr[i];
}
}
return null;
}
PointGR.idPoint = 0;
PointGR.setId = function() {
return PointGR.idPoint++;
}
Это первые строки, которые я пишу во всех классах, объекты которых будут заполнять массивы (то есть которых будет много).
1. Ставим уникальный идентификатор. Делается это (логично) через статическое поле.
2. В конструкторе добавляем каждый новый созданный объект в статический массив.
3. Пишем функцию в которую передаем идентификатор и она по нему, перебрав массив, возвращает нужный нам объект. Функция так же статическая (можно и нет, то есть цеплять на прототип класса, но, как показывает практика, удобней статическая)
Так… муза советов по JavaScript так же ушла, следом за музой по заголовкам.
Хотя нет, вроде еще здесь. Еще можно сказать об оптимизации. Изначально все было на одном канвасе и каждый кадр перерисовывалось. Но при просмотре загрузки цп во время отображения графа были сделаны логические выводи и внесены изменения.
Выносим все статические элементы на отдельный канвас. Что я и сделал. Граф рисуется отдельно от бегающих человечков. При чем один раз. Когда мы начинаем таскать за вершины — включается перерисовка, как только перестаем — перерисовывается последний раз и останавливается.
На большом количестве человечков (а это все объекты классов, и они кстати еще являются физическими телами (на том же движке, что недавно писал), но в данном случаи с выключенной коллизией) конечно лаги заметные, к сожалению.
Вот, я типа забил все комнаты людьми.
Почти 1800 объектов, каждый с которых анимируется.
Все остальное по коду вроде бы очевидно и не сложно. С кодом все. Приступим к разделу «Как это работает». («на пальцах»)
Здесь все. Переходим к разделу «Еще немного ни о чём»
Еще немного ни о чём (не, не будет заголовка)
Повторяю, чтобы не скролитть вверх: Пару слов об интерфейсе:
— вы можете изменить к-во спасателей
— вы можете добавлять людей (сколько хотите) по комнатах (просто кликаем по комнате)
— вы можете отображать граф и вершины (за которые можно драг_енд_дропить)
— запускаем по кнопке с соответствующим названием
Чтобы попробовать жмем сюда [3].
Файлы можно взять нажав сюда [6].
P.S. Делалось в последнюю ночь перед сдачей как всегда (курс логического программирования), поэтому стилизация кода местами не очень ну думаю, у многих такой код, когда пишется в ритме «сессии»
P.P.S. Изначально планировалось двухэтажное здания, и пожар. Операция была ограничена по времени (пока все не сгорит) и в конце люди должны были прыгать с окон. Но по просьбе преподавателя, это было исключено из задания (прыгать с окон). И смысл двух этажей исчез. Также были сделаны кнопки взрывов выхода (он загорался), и спасатели «исключали» его из возможных выходов и искали следующий. Но так как не успел отладить (один раз из четырех они просто бежали в огонь) это было исключено из «финальной» версии.
Автор: bob_lyashenko
Источник [7]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/26170
Ссылки в тексте:
[1] своей последней: http://habrahabr.ru/post/167007/
[2] алгоритм Дейкстры.: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
[3] жмем сюда: http://lyashenko-inc.in.ua/projects/logproj_upload/www/
[4] LibCanvas: https://github.com/theshock/libcanvas/
[5] змейку: http://lyashenko-inc.in.ua/projects/snake/
[6] нажав сюда: http://lyashenko-inc.in.ua/projects/logproj_upload/www/upload.rar
[7] Источник: http://habrahabr.ru/post/167973/
Нажмите здесь для печати.