Искусственный интеллект. Моделируем спасательную операцию

Немного теории

Что нам нужно сделать? У нас будет граф, то есть все контрольные точки здания, по которых будут бегать наши люди. Выглядеть он будет примерно так:

Кстати здание реальное, это планировка одного из корпусов моего универа. Окей, у нас есть граф по которому нужно бегать. При чем не просто бегать, а кратчайшими путями. Здесь и приходит наш ИИ. Для поиска кратчайшего пути будет использоваться алгоритм Дейкстры. На хабре о нем много статей, и даже несколько реализаций, которые мне упростили много работы. Алгоритм вынесен отдельно, на вход будет получать граф и начальную вершину — возвращать будет набор путей к всех остальным вершинам. Один путь — это массив точек по которых будут бегать спасатели. Как видим у нас четыре выхода, то есть, логично, спасатели будут выводить людей к ближайшему выходу. С теорией все. Приступим к практике.

Реализация

Получится в нас вот такое ссылка, но сначала пару слов об интерфейсе:
— вы можете изменить к-во спасателей
— вы можете добавлять людей (сколько хотите) по комнатах (просто кликаем по комнате)
— вы можете отображать граф и вершины (за которые можно драг_енд_дропить)
— запускаем по кнопке с соответствующим названием
кто прочел инструкции жмем сюда
Как видим у меня там много кнопок вверху (которые я закоментил, чтобы никто ничего не поламал). Они там для того, чтобы строить сам граф. то есть кликаем по сцене, добавляем вершину, потом соединяем вершины в ребра, потом выставляем на графе комнаты (они станут зеленого цвета), выходы (темно вишневого), можем по ходу если что менять положения вершины, перетаскивая ее, когда граф готов — жмем сохранить в базу. Потом при инициализации считаются табличка точек и табличка рёбер и построится граф.
Точки строились средствами html, но можно было бы сделать их при помощи того же фреймворка LibCanvas например, и так же рисовать их на канвасе, это бы, наверное, было бы даже более правильным решением. Но было сделано так, как это изначально была не просто точка, а там по клику на нее выпадало меню настроек, которые меняли ее тип, добавляли человека и т.д. Но в результате было переделано по-другому. А так как делалось это в последнюю ночь, как всегда, времени менять уже не было.
У нас будет класс этой точки, которая будет хранить координаты и еще много чего. Точек будет много и с эти всем нужно как то удобно работать.

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 объектов, каждый с которых анимируется.

Все остальное по коду вроде бы очевидно и не сложно. С кодом все. Приступим к разделу «Как это работает». («на пальцах»)

Раздел «Как это работает»

• 1. Никто из спасателей не знает где люди, они бегают по комнатах, и смотрят, есть ли там люди, если есть ведут их на выход.
• 2. Начиная со входа в здание каждому спасателю дается путь, по которому бежать, то есть, на точке «ноль» ищутся кратчайшие пути от этой точки к комнатам (точнее ко всем точкам, так работает ИИ алгоритм, но мы из них берем только те, которые заканчиваются точкой «комната»). То есть берем первый путь, даем ее первому спасателю, и так далее всем. Как только путь с конечной «комнатой» кому то присвоили, она выпадает из списка «куда нужно забежать и посмотреть есть ли там люди».
• 3. Когда спасатель прибежал в комнату проверяется точка комнаты с точкой человека внутри ( или вблизи) этой комнаты. То есть когда мы расставляем людей в начале, каждый человек прикрепляется к какой то точке-комнате (простым поиском ближайшей из всех)
• 4. Окей, прибежал, есть люди, всех людей берет в массив своих «дочерних» элементов, и пересчитывает, опять же ИИ алгоритмом, пути к выходам, берет самый короткий из всех. Бежит к нему, таща за собой людей. Оставляет всех людей там (на выходе). Кстати, кто то может в этом узнать змейку, да это она и есть, тот же прием.
• 5. Смотрит, остались ли еще не проверенные комнаты (спасатели, по легенде, общаются между собою, поэтому знают, в которые комнаты еще никто не ходил), если остались, опять же, уже с текущей точки, находится кратчайший путь к комнатам. Если комнат больше нет, остается на выходе.
• 6. Если в 4-м пункте людей не оказалось — проверяется есть ли не проверенные комнаты, если есть — пересчитываются пути, бежит к ним, если комнат больше нет пункт 5.
• 7. Все заканчивается когда все спасатели вышли из здания.

Здесь все. Переходим к разделу «Еще немного ни о чём»

Еще немного ни о чём (не, не будет заголовка)

Повторяю, чтобы не скролитть вверх: Пару слов об интерфейсе:
— вы можете изменить к-во спасателей
— вы можете добавлять людей (сколько хотите) по комнатах (просто кликаем по комнате)
— вы можете отображать граф и вершины (за которые можно драг_енд_дропить)
— запускаем по кнопке с соответствующим названием
Чтобы попробовать жмем сюда.
Файлы можно взять нажав сюда.

P.S. Делалось в последнюю ночь перед сдачей как всегда (курс логического программирования), поэтому стилизация кода местами не очень ну думаю, у многих такой код, когда пишется в ритме «сессии»

P.P.S. Изначально планировалось двухэтажное здания, и пожар. Операция была ограничена по времени (пока все не сгорит) и в конце люди должны были прыгать с окон. Но по просьбе преподавателя, это было исключено из задания (прыгать с окон). И смысл двух этажей исчез. Также были сделаны кнопки взрывов выхода (он загорался), и спасатели «исключали» его из возможных выходов и искали следующий. Но так как не успел отладить (один раз из четырех они просто бежали в огонь) это было исключено из «финальной» версии.