Для разработки небольшой компьютерной игры зачастую применяются базовые алгоритмы поиска пути (алгоритм Дейкстры, А*), которых вполне достаточно для игрового поля не слишком больших размеров. Однако как же решить задачу о поиске пути на громадных игровых пространствах в играх жанра RTS или RPG? Ведь в виду значительного потребления памяти и ресурсов процессора базовые алгоритмы не подходят. О решении этой проблемы (а также нескольких других) и пойдет речь дальше в статье.
Читать полностью »
Рубрика «алгоритм» - 11
Иерархический поиск пути
2013-01-22 в 19:08, admin, рубрики: game development, HPA*, rpg, RTS, алгоритм, Алгоритмы, поиск пути, Программирование, метки: HPA*, rpg, RTS, алгоритм, поиск путиСимуляция жизни в системе Darwinbots. II. Симуляция и простейший бот
2013-01-15 в 16:06, admin, рубрики: алгоритм, Алгоритмы, Биотехнологии, выживание, генетика, генетический алгоритм, естественный отбор, Программирование, симуляция, метки: алгоритм, выживание, генетика, генетический алгоритм, естественный отбор, Программирование, симуляция
Приветствую вас еще раз, дорогие читатели!
Эта статья выкладывается в разгар сессии, так что я могу пропасть из комментариев.
1. Первое знакомство
2. Симуляция и простейший бот
Сегодня разберёмся с настройками симуляции и посмотрим на простейшего бота (или робота, как вам будет удобно). Нет, я не буду досконально рассматривать интерфейс программы – это будет вашим домашним заданием:-) И да, само понятие «генетический алгоритм» четко расписано в Википедии, поэтому опустим это объяснение.
Читать полностью »
Квантовые вычисления, часть вторая
2013-01-10 в 12:17, admin, рубрики: алгоритм, Алгоритмы, квантовые вычисления, квантовый компьютер, ненормальное программирование, Программирование, метки: алгоритм, квантовые вычисления, квантовый, квантовый компьютерСказал как-то раз Евклид, что параллельные линии не пересекаются. И назвал он это пятым постулатом. Жалко, что не вторым.
В этой статье я бы хотел перейти от сферических котов Шредингера в резонаторах Гельмгольца к чему-то более практичному, тем более, что Хабр интересуют физические реализации и применение квантовых компьютеров.
Тут я решил рассказать про составные системы и описать алгоритм Дойча.
Симуляция жизни в системе Darwinbots. Часть первая
2013-01-04 в 10:53, admin, рубрики: алгоритм, Алгоритмы, Биотехнологии, выживание, генетика, генетический алгоритм, естественный отбор, Программирование, симуляция, метки: алгоритм, выживание, генетика, генетический алгоритм, естественный отбор, симуляция Привет!
Недавно сдал курсовую работу по генетическим алгоритмам в программе Darwinbots и решил, что это будет интересно сообществу. Тем более, что в данный момент сообщество проекта довольно мало. Статьи будут наполовину переводом документации, а наполовину своими исследованиями программы.
Читать полностью »
Алгоритм кодирования Punycode
2013-01-03 в 10:29, admin, рубрики: алгоритм, Алгоритмы, домены, Песочница, метки: алгоритм Не так давно передо мною встала задача использовать русские символы в имеющемся у меня скрипте конструктора сайтов, авторы которого почему-то не позаботились о том, чтобы сделать данную возможность. После бессмысленных поисков алгоритма работа Punycode, я начал интересоваться на форумах, и задал данный вопрос на нескольких десятках форумах соответствующей тематики. Но лучшее, что я получил в результате своих исканий, это несколько ссылок на уже готовые классы и методы и англоязычную документацию rfc, а также некоторые небольшие пояснения, которые помогли мне разобраться, но не раскрыли самого алгоритма работы.
Поэтому взяв за основу один из классов я стал его разбирать, и узнал, что основной алгоритм кодирования (до декодирования еще дело не дошло), кроется в php классе в методе _encode. Именно на его примере мы и будем разбирать работу всего алгоритма кодирования.
До цикла
while ($codecount < $deco_len) {
все более менее понятно и довольно просто.
Все символы преобразовываются в свои десятичные представления Юникода, передаются посимвольно в массив $decoded, вначале ставим «xn--», затем ставим все символы ascii по порядку исключая все не ascii и в конце добавляем "-". И все это в том случае если наши символы имеют интернациональные символы. Я не рассматриваю все дополнительные проверки, т.к. подразумевается, что мы вне всяких сомнений рассматирваем строку, где хотя бы один из символов не входит в ascii, соответственно все, что у нас есть для кодирования строки описано выше.
GPS и карты: смещённые координаты в Китае
2012-12-14 в 12:40, admin, рубрики: алгоритм, карты, китай, координаты, метки: алгоритм, карты, китай, координатыТак как я работаю в картографическом сервисе, то недавно я сделал для себя открытие, что все координаты в Китае смещенны по секретному алгоритму. Я собрал немного интересных историй и информации об этом факте.
Есть только граница Китая в этом мире © heremaps.cn
Управление инженерными системами здания с помощью решений на базе оборудования «Болид» + SCADA «Алгоритм»
2012-11-30 в 14:03, admin, рубрики: scada, автоматизация, алгоритм, Анализ и проектирование систем, болид, Железо, инженерные системы, контроллеры, метки: scada, автоматизация, алгоритм, болид, инженерные системы, контроллерыДанная короткая заметка будет полезна людям занимающимся автоматизацией инженерных систем(ИС) зданий и сооружений. Я заметил, что на сайте есть люди знающие о компании «Болид» и ее интегрированной системах охраны – «Орион». Но буквально совсем недавно я узнал. Что ИСО «Орион» это не их единственная разработка. Оказывается товарищи из славного города Королёва разработали свою SCADA и контроллер для автоматизации ИС здания. О них вам в вкратце и хотел бы рассказать в данной заметке.Читать полностью »
Поиск гамильтонова цикла в большом графе (задача коммивояжера)
2012-11-24 в 15:00, admin, рубрики: c++, алгоритм, гамильтонов цикл, Программирование, метки: c++, алгоритм, гамильтонов цикл1. Постановка задачи
Полный взвешенный граф из 500 вершин задан матрицей смежности.
Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.
Читать полностью »
Поиск пути: алгоритм для новичков
2012-11-20 в 8:06, admin, рубрики: javascript, jquery, алгоритм, логика, поиск пути, метки: javascript, jquery, алгоритм, логика, поиск путиПоиск пути — неотъемлемая часть игр, встречающаяся в большинстве современных игровых жанров. Наиболее часто задача поиска пути возникает в стратегиях, в которых игрок дает команды игровым юнитам двигаться через область карты, которая содержит препятствия. Игры постоянно усложняются, а поиск пути эволюционирует и развивается вместе с ними.
Алгоритмы поиска пути не всегда эффективны, но их изучение помогает понять, как решаются различные проблемы, одной из которых является обход препятствий.
Наиболее простым, но достаточно известным и популярным алгоритмом поиска пути является алгоритм Астар (или A*), данная статья основана на данном алгоритме и содержит реализацию на JavaScript.
Читать полностью »
Инкрементальный алгоритм привязки GPS-трека к дорожному графу
2012-11-08 в 12:32, admin, рубрики: gps, алгоритм, Блог компании Mail.Ru Group, Геоинформационные сервисы, метки: gps, алгоритм
Геоинформационные системы постепенно входят в повседневный быт.
Большинство мобильных устройств снабжены GPS/ГЛОНАСС-приёмниками. Это позволяет разработчикам получать записи пути своих пользователей (треки). Треки можно использовать для решения целого ряда задач — от навигации по карте и информирования о местоположении друзей до построения пробок и предсказания дорожной ситуации.
К сожалению, без дополнительной обработки трек пользователя малоинформативен, поэтому требуется этап связи внешних данных и внутренней карты приложения. Для этого существуют специальные алгоритмы привязки данных (map matching algorithms).
Эта статья посвящена алгоритму привязки трека к дорожному графу и результатам его применения в проекте Карты@Mail.ru.
Читать полностью »