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

ПОИСК ПУТИ

На пути постижения мудрости не надо бояться, что свернёшь не туда.

Пауло Коэльо

Автор Utkin www.programmersforum.ru

Прокладка маршрута называется навигацией. Она бывает двух видов: автономная – когда объект (бот) самостоятельно прокладывает маршрут из одной точки карты в другую, запоминает его индивидуально (либо в общем, хранилище маршрутов для одной группы юнитов), и предварительная – когда маршруты уже проложены во время проектирования карты (опять же автоматически или программистом), или же на этапе загрузки карты игрового мира. Маршрут обычно представляет собой некоторую совокупность точек (или их координат) со связями между ними, то есть это маршрут, проложенный на графе. Сами точки называются вейпоинтами – это углы (или вершины) графа. Соответственно подавляющее большинство алгоритмов поиска пути есть алгоритмы по работе с графами.

Краткий экскурс…

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

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

Предварительный просчет точек осуществлен, например, в игре StarСraft. Это видно если отправить рабочего добывать ресурсы, он смело перемещается через туман войны и по неисследованной области, способен находить подъемы на другой уровень плоскости и сразу определять местоположение моста.

Алгоритм Дейкстры

Этот алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных.

Сначала рассмотрим граф без применения алгоритма Дейкстры, это упростит понимание алгоритма в дальнейшем. Для удобства восприятия обозначим каждую вершину идентификатором, пусть это будет номер вершины (порядок нумерации на графе значения не имеет). В качестве отношения между точками возьмем расстояние. Получается, точка имеет: идентификатор, список точек, куда можно попасть из данной точки и расстояния до каждой из доступных точек.

Вот образец графа (см. рисунок 1):

Рис. 1. Образец типичного графа

Представьте, что нам нужно попасть из точки 1 в точку 5. Сколько имеется путей достижения точки 5? Давайте посчитаем:

а) 1-2-5

б) 1-2-6-5

в) 1-6-5

г)  1-6-2-5

Итого четыре маршрута. Вычислим расстояния по каждому маршруту (суммированием расстояний между точками). Вот расстояния между точками:

а) 1-2    расстояние 6

б) 2-5   расстояние 4

в) 2-6    расстояние 6

г) 6-5    расстояние 5

д) 1-6   расстояние 8

е) 6-2, он же 2-6 расстояние 6

Общее расстояние всего маршрута:

а) 1-2-5             расстояние 6+4=10

б) 1-2-6-5          расстояние 6+6+5=17

в) 1-6-5             расстояние 8+5=13

г) 1-6-2-5          расстояние 8+6+4=18

Самый оптимальный (для нашего примера) является путь а) расстояние всего 10. Если же будут обнаружено два и более маршрутов, имеющих одинаковую длину, то выбирается, как правило, первый (либо заранее продумано, какой из маршрутов, лишь бы выбор был осуществлен).

Также нужно обратить внимание, что на первый взгляд маршруты б) и г) равны (казалось бы, от перемены мест слагаемых сумма не меняется), однако следует не забывать, что идентификаторы здесь не несут математического смысла это просто имена точек. Таким же образом мы могли бы назвать и a, b, c и т.д. Операции идут над расстояниями, а суммы пар расстояний (1-2; 2-6) и (1-6; 2-6) не эквивалентны (не равны) между собой.

Теперь сам алгоритм. Он предназначен для поиска всех наикратчайших путей от указанной вершины до всех остальных. Изначально расстояния нам не известны, поэтому будем считать, что они равны максимально возможному расстоянию до каждой из вершин (точек) графа (кроме исходной, до нее расстояние естественно равно нулю).  Далее, необходимо отмечать рассмотренные точки графа (чтобы не повторяться)…

Перейдем к алгоритму

Итак, рассмотрим действие алгоритма для первой вершины нашего графа. Вершина 1 имеет отношения (в дальнейшем будем считать отношения просто расстояниями между вершинами графа) с вершинами 2 и 6. Ближайшей точкой будет являться точка 2, поскольку расстояние до нее меньше и составляет 6 единиц (в примере неважно каких единиц, в игре это могут быть условные единицы реальных км, м и т.д., единицы местоположения юнита на карте, число пикселей с привязкой к координатной сетке области отображения и т.д.).  Считаем точку 1 пройденной, поскольку нам известны кратчайшие расстояния до точек 2 и 6.

Следующей рассмотрим точку 2 (потому что она ближе к 1 точке). Для нашего графа соседями точки 2 являются 1, 6, 5 и 3. Точку 1 мы рассматривать не будем, поскольку уже было отмечено, что она была просмотрена ранее. Вот расстояния:

. до точки 6 расстояние 6;

. до точки 5 расстояние 4;

. до точки 3 расстояние 5.

Отсюда следует, что ближайшей точкой к вершине 2 будет точка 5, поскольку расстояние до нее минимально, по сравнению с вершинами 6 и 3.

На данном этапе:

. расстояние до точки 1 составляет 0;

. расстояние до точки 2 составляет 6;

. расстояние до точки 5 составляет 10 (6+4);

. маршрут до точки 5 следующий – 1-2-5 (и никакой другой до данной точки более не рассматривается);

. следующей точкой будет являться точка 5;

. точка 2, также как и точка 1 считается отмеченной и больше не рассматривается;

. расстояние до точки 6 (маршрут 1-6) равен 8 (0+8), а не 12 (маршрут 1-2-6, расстояние 6+6), поскольку хоть точка 6 и не отмечена, но текущее расстояние до нее уже было вычислено и оно менее текущего (не забываем, что изначально расстояние до каждой точки равно максимально возможному для данного графа).

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

Представление точек графа

Граф можно представлять многими способами, например, в виде таблицы смежности (ru.wikipedia.org/wiki/Список_ребер). Такой способ представления удобен с математической точки зрения, но абсолютно не удобен с практической. Например, точку можно представить как ее координаты и набор отношений (где отношение можно представить как пару – указатель на точку-соседа и расстояние до точки-соседа). Если отношение представляет собой расстояние между двумя точками в данной системе координат, то его можно вычислять автоматически по формуле вычисления расстояния между двумя точками (школьный курс геометрии), при этом расстояние для системы координат с числом осей более двух вычисляется аналогично по обобщенной формуле. Собственно совокупность точек графа и будут являться самим графом.

Отмеченные точки графа

Здесь необходимо отмечать те точки графа, которые были пройдены во время работы алгоритма, чтобы не проходить их повторно. Считаю, эти данные должны лежать отдельно от точек графа, потому как такая информация собственно к графу отношения не имеет (а вот к алгоритму самое прямое).

Таблица кратчайших расстояний

Согласно алгоритму изначально расстояние до точек должно представляться максимально возможным расстоянием (за исключением стартовой, до нее расстояние минимально – 0). Затем эти расстояния заполняются в процессе выполнения алгоритма. Также эти расстояния нужны для сравнения имеющихся и предлагаемых расстояний (расстояние до точки 6 для нашего примера).

Маршруты от начальной до остальных точек

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

Рис. 2. Тестовая утилита

Заключение

Несмотря на кажущуюся сложность данного алгоритма, при четком понимании работы, его реализация очень проста, а скорость работы вполне приемлема для не очень больших графов.

Исходники тестового проекта прилагаются в виде ресурсов в теме «Журнал клуба программистов. Третий выпуск» или непосредственно в архиве с журналом [5].

Ресурсы

. Реализация алгоритма Дейкстры http://plagiata.net.ru/?p=90

. Описание алгоритма Дейкстры http://algolist.ru/maths/graphs/shortpath/dijkstra.php

. Математическое и неформальное описание алгоритма Дейкстры

http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

. Дополнительные материалы http://borisvolfson.h11.ru/show_article.php?article_id=0000020 и

http://www.excode.ru/art6837p1.html

. Модули и проекты, использованные в статье http://programmersclub.ru/pro/pro3.zip

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Поиск пути

С выходом третьего номера журнала [ПРОграммист] у него появился собственный сайт. Разработке этого ресурса и посвящен цикл статей.

Для начала оговорим, что мы решили разбить статью на две части, т.к это не поместиться в объеме одной статьи. Первая часть будет о написании ленты новостей, гостевой книги и вообще всего интерфейса пользователя, а вторая будет посвящена написанию панели администратора.

Первую часть будет вести Егор Горохов aka Revival1002, вторую — Алексей Шульга aka Levsha100, мы будем помогать друг другу в этом нелегком труде. Итак, начнем.

1. Дизайн

Для начала был нарисован PSD шаблон сайта в графическом редакторе Photoshop.  Оттуда же мы потом и «выдирали» картинки для сайта. В результате у нас получилось это (см. рисунок 1):

Рис. 1. Предварительный дизайн сайта журнала

Плюс такого дизайна в том, что можно оченьбыстро сделать редизайн. Для этого достаточносменить фоновую картинку и немного подкорректировать таблицы стилей CSS.

2. Верстка

Для создания закругленных углов использовалось свойство border-radius. К сожалению, пока что свойство работает не во всех браузерах, например в IE 6…8 оно игнорируется. Конечно существуют и альтернативные способы создания круглых углов, но они зачастую требуют до 9 (!) картинок блока (4 угла, 4 стороны и центр). Так как мы «очень ленивые», да и острые углы не очень портят дизайн, мы использовали простейшее решение, с надеждой на то, что вскоре все браузеры будут поддерживать данное свойство…

Для полупрозрачности главного div не было найдено (возможно мы плохо «гуглили») кроссбраузерного решения, поэтому мы пошли на хитрость, создав однопиксельный полупрозрачный png, и поставили его на фон. Но и этот способ, как оказалось имеет свои минусы. Например*, ненавистный всеми дизайнерами/верстальщиками IE6 его игнорирует.

* Комментарий автора.

Кстати, я уже давно не видел людей использующих IE6. Все мои знакомые, даже если они мало понимают в компьютерах (например девушки) используют браузеры типа Opera и Mozilla Firefox. Поэтому причин продолжать верстать под MSIE6 я уже не вижу.

Ознакомится с CSS можно по адресу:
http://procoder.info/style.css

3. Написание скриптов

Для начала, вынесем все наиболее часто используемые переменные в отдельный файл “config.php”, и потом будем его «инклудить» во все скрипты. Мы поместили туда логин\пароль от БД, путь к сайту и т.п. В дальнейшем, если мы захотим изменить что-либо, то это займет всего- лишь несколько секунд, и не потребуется вносить изменения во множество скриптов.

Итак, при заходе на сайт пользователь должен видеть: ленту новостей, журналы доступные для скачивания, гостевую книгу. Реализция происходит практически одинаково. Покажу на примере гостевой книги (см. листинг 1):

<?php

require_once "config.php"; // Подключение файла конфигурации

// Функция обрабатывает строку, и заменяет все bb-коды на html

function bbcodes($str)

{

$bbcode = array(

"/\[b\](.*?)\[\/b\]/is" =] "<strong>$1</strong>",

"/\[u\](.*?)\[\/u\]/is" =] "<u>$1</u>",

"/\[url\=(.*?)\](.*?)\[\/url\]/is" =] "<a href='$1'>$2</a>",

"/\[color\=(.*?)\](.*?)\[\/color\]/is" =] "<font

color='$1'>$2</font>",

"/\[i\](.*?)\[\/i\]/is" =] "<i>$1</i>]",

"/\[quote\](.*?)\[\/quote\]/is" =] "<div

class=\"quote\">$1</div>",

"/\[img\](.*?)\[\/img\]/is" =] "<img src=\"$1\">"

);

$str = preg_replace(array_keys($bbcode), array_values($bbcode),

$str);

return $str;

} // Функция взята из мануалов по PHP

// Подключение к БД

$db = mysql_connect($db_server, $db_user, $db_pass);

mysql_select_db($db_name);

// Выбираем из таблицы table_gb последние 30 записей и

сортируем их по id
$db_query=mysql_query("SELECT * FROM `table_gb` ORDER BY `id`

DESC LIMIT 0 , 30", $db);

while ($res = mysql_fetch_array($db_query)) // Вывод записей

{

echo "<div class=\"guest_comment\"><b>".$res['name']."-

".$res['date']."</b><br>";

echo bbcodes(wordwrap("<pre>".$res['text']."</pre>", 75));

echo "</div><br>";

}

?>

// Тут находится форма, для добавления записей в БД, которая
передает скрипту gb.php данные

А теперь скрипт добавляющий записи в БД (см.листинг 2):

<?php

require_once "config.php";

$db = mysql_connect($db_server, $db_user, $db_pass);

mysql_select_db($db_name);

// Получаем данные и убираем из них спец-символы,

// для защиты от XSS-атак

$name = htmlspecialchars($_POST['name']);

$text = htmlspecialchars($_POST['text']);

$date_array = getdate(time());

$date =
$date_array['mday'].".".$date_array['mon'].".".$date_array['year'];

if (($text=='') or ($text=='Введите текст'))

{

echo "<script>alert('Запись не добавлена.');</script>";

echo '<meta http-equiv="Refresh" content="0;
URL='."$index_path".'">';

}

else

{

if (($name=='Ваше имя') or ($name=='')) {$name='Аноним';}

// Добавляем запись в БД

$db_query = mysql_query("INSERT INTO `table_db` (

`id` ,

`name` ,

`text` ,

`date`

) VALUES ('', '$name', '$text', '$date');", $db);

mysql_close($db);

echo "<script]alert('Запись добавлена');</script>";

echo '<meta http-equiv="Refresh" content="0;
URL='."$index_path".'">';

}

?>

Аналогичным образом выводятся записи для новостей, журналов для закачки и другая информация (см.  рисунок 2):

Рис. 2. Скрин тестовой работы скриптов

Подведем предварительные итоги…

Что есть и что планируется? Пока сделано очень мало, и нововведения** будут появляться практически каждый день. Совсем скоро будет система регистрации, что позволит комментировать статьи, новости и выставлять им оценки. У каждого пользователя будет личный кабинет. Создавать отдельный форум для сайта не планируется, так как это совместный проект Клуба ПРОграммистов www.programmersclub.ru и форум уже есть. Существующие алгоритмы тоже будут улучшены. Все предложения оставляйте либо на форуме, либо отправляйте на электронный ящик редакции.

Это статья из третьего номера журнала “ПРОграммист”.
Скачать его можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Разработка ресурса для журнала. Часть 1

Код клавиши Shift #16

Как проверить, зажат ли Shift?

Procedure TForm1.Timer1Timer(Sender: TObject);
Var State : TKeyboardState;
Begin
  GetKeyboardState(State);
  If ((State[16] and 128) 0) Then
    caption:=’нажат’
  Else
    caption:=’не нажат’
End;

Тема на форуме

psSolid Сплошная линия
psDash Штриховая линия
psDot Пунктирная линия
psDashDot Штрих-пунктирная линия
psDashDotDot Линия, чередующая штрих и два пунктира
psClear Отсутствие линии
psInsideFrame Сплошная линия, но при Width > 1 допускающая цвета, отличные от палитры Windows

Тема на форуме

Многие новички сталкиваются с проблемой отображения русских символов при программировании на С++.

В интернете уже много раз обсуждался данная проблема, но вопросов меньше не становится. Поэтому, вместо теории рабочий код на С++.

#include <iostream>
 #include <string>
 #include <conio.h>
 using namespace std;
  int main()
{
/* locale - это класс salo - это объект
"russian_Russia.866" - это параметры для объекта global(loc) означает область видимости метода глобал в классе под названием locale
 */
locale salo("russian_Russia.866");
  locale::global(salo);
 wstring text;
 wcout<<L"Введи слово: "<<endl;
 wcin>>text;
 setlocale(0,"");
if(text==L"клоун")
wcout<<text;
     getch();
 }

Тема на форуме.

Terran:

Вот пример. Остался ещё с моей давней проги. Только Вам надо его подкорректировать как Вам надо.

Private
{ Private declarations }
     Procedure OnMove(Var Msg: TWMMove);
     Message WM_MOVE;
…
Procedure TForm1.OnMove(Var Msg: TWMMove);
Var
RWorkArea: TRect;
Begin
  SystemParametersInfo(SPI_GETWORKAREA, 0, @RWorkArea, 0);
  If Form1.Showing Then
  Begin
    If Form2.Showing Then
    Begin
      If (Form2.Top+Form2.Height>RWorkArea.Bottom) Then
      Form2.Left:=Form1.Left;
      Form2.Top:=Form1.Top+Form1.Height;
    End;
  End;
End;

Тема на форуме

Многим из нас знаком советский электретный микрофон типа МКЭ-3, а те, кто не знаком, все равно применяют его или его аналоги в повсеместной практике, даже не догадываясь о замечательных свойствах материала – электрета (поляризованного диэлектрика), используемого в нем.

Не менее примечательна история появления этого замечательного материала… В 1943 году во время боевых действий на Тихом Океане американский флот захватил японский эсминец. Для изучения вражеской техники на корабль прибыли специалисты флота, осмотрели все – от трюма до капитанской рубки. Связист подробно изучил систему телефонной связи, она работала как часы. Одного он не мог понять, как система может работать без источника питания, ни батарей, ни аккумуляторов не было и в помине!

Физики разобрались в принципе работы телефонной связи на японском корабле. Ее работа стала возможной благодаря открытию японского физика Егучи, еще в 1922 году получившему новые материалы – электреты (с 1922 года работу с электретами Егучи проводил в обстановке строжайшей секретности для Министерства обороны Японии). Егучи получал электретные материалы из смеси смолы карнаубской пальмы и воска. Нагрев смесь до расплавленного состояния Егучи подал на нее напряжение 10 кВ, после застывания таблетка электрета сохраняла электростатический заряд высокой напряженности в течение нескольких часов (см. рецептуры). Современные электреты могут сохранять заряд до 100 лет, величина заряда достигает 5*10-8 Кл/см2.

В настоящее время электреты получают из таких материалов как: политетрафторэтилен (макс. Поверхностный потенциал 527 В), полиметилметакрилат или органическое стекло (3965 В), рутиловая керамика, смолы, воск,  полимеры, титанаты щелочноземельных металлов и даже растворы органических веществ в летучих растворителях.

Рецептура N1

Нагреваем 2-5 г касторового масла до температуры 75-90 °С и высыпаем в него при помешивании 50 г мелкоизмельченной канифоли (если возится неохота, то возьмите и используйте парафин вместо канифоли и масла, расплавьте его и поместите между электродами – после остывания электрет готов). После чего расплав наливаем в плоскую баночку (стеклянную) или на предметное стекло и помещаем его между электродами, на которые подается напряжение от высоковольтного выпрямителя (5-10 кВ) или электростатической машины. Толщина слоя диэлектрика должна быть менее 4 мм. После остывания канифоль достается из баночки. Электрет готов.

Докажем, что электростатическое поле электрета имеет высокую напряженность. Если около неоновой лампочки быстро провести электретом, то она ярко вспыхнет, так как при пересечении лампой линий электростатического поля на электродах лампы наводится переменное высокое напряжение и лампа начинает светиться. Застывший диэлектрик – электрет способен сохранять заряд в течение нескольких суток. Хранить электреты можно завернутыми в алюминиевую фольгу.

Более стабильные электреты можно получить при нагреве диэлектриков до температуры меньшей или равной температуре плавления, а затем охлаждая их в сильном электрическом поле. При застывании органических растворов в сильном электрическом поле получают так называемые «криоэлектреты». Существуют и другие разновидности электретов: фотоэлектреты, трибоэлектреты и др.

Рецептура N2

Вместо канифоли и касторового масла можно между электродами в баночке поместить какой-нибудь полимер, например – капрон, растворенный в небольшом количестве растворителя. Подать высокое напряжение и после полного испарения растворителя – электрет готов.

Это заметка с третьего выпуска журнала “ПРОграммист”.
Скачать этот выпуск можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Этот удивительный электрет

Новые модификации анализаторов спектра в реальном времени с технологией обработки изображений сигнала DPX™ представила компания Tektronix Inc. Модели серий RSA3000B и RSA6100В поставляются в двух исполнениях с разными диапазонами перекрываемых частот: 0-3 ГГЦ или 0-8 ГГц

Технология обработки изображений сигналов DPX, позволяет просматривать спектр в режиме реального времени, при скорости обработки более 48000 измерений спектра в секунду. Процессор обработки изображений сигналов с эффектом послесвечения позволяет выявлять в динамических сигналах отклонения и частоту их повторения, а также обеспечивает мгновенную обратную связь при временных изменениях сигналов.  Благодаря этому можно быстро просмотреть на экране переходные процессы и сигналы, которые раньше рассмотреть было невозможно, поскольку они маскировались
другими сигналами, или для их выявления приходилось проводить автономный анализ, занимающий много времени. Основные виды анализируемых тестовых сигналов (W-CDMA, GSM/EDGE, CDMA, HSDPA, TD-SCDMA, WLAN 802.11a/b/g, HDTV и даже радиочастотных меток RFID) представлены на скриншотах, а видеотестирование вы можете просмотреть тут http://raxp.radioliga.com/cnt/s.php?p=dpx.wmv

Это заметка с третьего выпуска журнала “ПРОграммист”.
Скачать этот выпуск можно по ссылке.
Ознакомиться со всеми номерами журнала.

Обсудить на форуме — Новые модификации анализаторов спектра