Был как-то проект у меня, который был связан с картой города. И возникла идея, что раз есть карта с маршрутами и соответствующими остановками городского транспорта, то почему бы не сделать поиск пути из пункта А в пункт Б на ней.

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

Где-то около часа или двух я сидел и не мог ничего придумать, а потом появилась идея, что я могу рассматривать маршрут, не как множество остановок, а как 1 точку. И если я сверну маршруты в точку, то я получу очень простой граф.
Идея показалось неплохой, и мне понравилась.

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

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

За несколько месяцев алгоритм переписывался пару раз, далее поподробнее расскажу о последней реализации.

Качество видео ужас, но как сделать получше я так и не обнаружил.



Усредненное время, затрачиваемое на выполнение шагов:

gpt — 0.009с, найти ближайшие остановки к точке клика
grt — 0.001с, найти кратчайший путь от маршрута к маршруту
apt — 0.0001с, добавляем остановки и точки поворота к нашему маршруту
all — 0.01c, суммарное время выполнения поиска пути

Всем доброго пятничного вечера!

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

К сожалению, даже на официальной вики почти не возможно найти каких либо примеров использования SDL2.x, что уж говорить о рунете. Пытаясь разобраться, я нашел всего лишь пару статей, которые не покрыли и трети моих вопросов.
SDL 2.x существенно отличается от 1.x и даже, если в прошлом вам приходилось с ним работать — теперь вы рискуете ничего не понять.

Сегодня мы напишем простенькую программу выводящую на экран фон и зумируемый спрайт персонажа перемещающегося с помощью WASD и стрелок. + разберемся как в SDL работать с мышкой.

На этот раз нововведений гораздо меньше, чем в первой части. Все-таки С++14 считается незначительным релизом, нацеленным скорее на устранение недочетов С++11, чем привнесение новых возможностей.

Краткий перечень:

• Освобождение памяти определенного размера
• Одинарная кавычка, как цифровой разделитель
• Аттрибут [[deprecated]]
• Пользовательские литералы для std::complex
• Filesystem API
• Преобразование сетевого порядка байт

Обзор новых возможностей С++14: Часть 1
Текущий черновик стандарта

Привет. В этой статье будет рассмотрен способ кластеризации данных, используя метод градиентного спуска. Честно говоря данный способ носит больше академический характер, нежели практический. Реализация этого метода мне понадобилась в демонстрационных целях для курса по машинному обучению, что бы показать как одинаковые задачи можно решить различными способами. Хотя конечно если вы планируете осуществить кластеризацию данных, используя дифференцируемую метрику, для которой вычислительно труднее найти центроид, нежели подсчитать градиент на некотором наборе данных, то этот метод может быть полезным. Итак если вам интересно как можно решить задачу k-means кластеризации с обобщенной метрикой используя метод градиентного спуска, прошу под кат. Код на языке R.

Первая статья из цикла «Теория магии» носит обзорный характер. Ее цель — сформулировать основные вопросы рассматриваемой дисциплины преимущественно на качественном уровне, а так же разъяснить, какие принято выделять субдисциплины, и как аспекты, находящиеся в центре их внимания, связаны между собой.

Привет.

Недавно я создал мобильную игру для Android, в которой потенциально мог бы быть мультиплеер, чего и затребовали пользователи.
Мультиплеер не предусматривался, так как не соблюдал разделения модели и представления.
В этой статье я рассмотрю простую реализацию сетевого режима игры и расскажу об ошибках, допущенных на этапе продумывания архитектуры игры.
Воодушевившись статьей goblin wars II структура игры была разделена на независимые блоки, что в конечном итоге позволило пользователям играть по сети.

Одной из основ разработки игр является обработка сообщений поступающих во время каких-либо событий (Events). Все видеоигры, от тенниса до очень сложных игр для ПК и консолей, используют т.н. события для взаимодействия с игроком. Эти события могут поступать от клавиатур, мышей, джойстиков, геймпадов, и т.д., а также от самой операционной системы. Важно понимать, как они работают, если мы хотим надлежащим образом обрабатывать взаимодействие пользователя с игрой. Мы уже использовали события, но только для закрытия нашего окна, теперь мы будем глубже разбираться с тем, как получать события от пользователя.

Я поискал по хабру перевод уроков с этого сайта, но нашлось только одно упоминание, да и то — в комментариях:



Потому и решил исправить положение, попытался дополнить и разнообразить примеры своими наработками, а заодно попрактиковался в переводе. Также, поскольку моей любимой ОС сначала была WinXP а теперь Ubuntu, постараюсь сделать кроссплатформенные примеры, захватив как можно больше нюансов настройки для этих платформ. В данной серии уроков рассматривается создание фрэймфорка, достаточного для начала разработки 2D игр.
Что из этого получилось

К сожалению, стандарт C++ не допускает применения операторов switch-case к строковым константам. Хотя в других языках, вроде C#, такая возможность имеется прямо «из коробки». Поэтому, понятное дело, многие C++ программисты пытались написать свою версию «switch для строк» — и я не исключение.
Для C++03 решения не отличались красотой и лишь усложняли код, дополнительно нагружая приложение в рантайме. Однако с появлением C++11 наконец-то появилась возможность реализовать такой код:

   std::string month;
   std::string days;

   std::cout << "Enter month name: ";
   std::cin  >> month;

   SWITCH (month)
   {
   CASE("february"):
       days = "28 or 29";
       break;

   CASE("april"):
   CASE("june"):
   CASE("september"):
   CASE("november"):
       days = "30";
       break;

   CASE("january"):
   CASE("march"):
   CASE("may"):
   CASE("july"):
   CASE("august"):
   CASE("october"):
   CASE("december"):
       days = "31";
       break;

   DEFAULT:
       days = "?";
       break;
   }

   std::cout << month << " has " << days << " days." << std::endl;

Реализация этой конструкции весьма проста. Она основана на constexpr-функциях из C++11, благодаря чему почти все вычисления производятся ещё на этапе компиляции. Если кого-то интересуют её детали, добро пожаловать под кат — благо на Хабре о «switch для строк» почему-то ничего не сказано.

Под BlackBerry OS 10 есть отличная среда разработки: QNX Momentics IDE, на базе Eclipse. И всё бы хорошо, но когда дело доходит до автоматизации сборки билдов, настройки билд-конфигураций на TeamCity, то IDE нужна как собаке пятая нога. Именно это было самой большой проблемой при портировании нашего движка на BlackBerry. Давайте разберёмся, как можно собрать проект, упаковать дистрибутив, подписать его и запустить на эмуляторе — и всё это без использования IDE.

Понадобилось мне прикрутить Lua к проекту на C++. Писать обертки в ручную — лень (слишком много писать), готовые не подходили по тем или иным причинам. Решил написать свою. А потому задался вопросом, как максимально упростить интерфейс? От одной только мысли об этом в голову лезли жутчайшие конструкции из шаблонов. Так оно в последствии и оказалось, но гораздо проще, чем представлялось.

В C++11 появились шаблоны с переменным числом аргументов, это позволяет писать шаблонные функции/классы так, как в C++03 было невозможно вовсе. Такие шаблоны сильно упрощают задачу.

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

В итоге хотелось увидеть интерфейс близкий к следующему:

lua.export_function(some_function);

Приветствую вас еще раз, дорогие хабражители!
_{Эта статья выкладывается в разгар сессии, так что я могу пропасть из комментариев.}

1. Первое знакомство

2. Симуляция и простейший бот

Сегодня разберёмся с настройками симуляции и посмотрим на простейшего бота (или робота, как вам будет удобно). Нет, я не буду досконально рассматривать интерфейс программы – это будет вашим домашним заданием:-) И да, само понятие «генетический алгоритм» четко расписано в Википедии, поэтому опустим это объяснение.

Добрый день/вечер/утро, уважаемые хабравчане и Вы, %username%!
Я занимаюсь разработкой приложений для Android, обожаю эту операционную систему и хочу поделиться своим опытом использования в своих проектах диалоговых окон. В первую очередь эта статья записка очень пригодится начинающим в области разработки для Android.
Также для новичков в этой отрасли рекомендую сперва прочитать вот этот пост уважаемого Hoorsh.
А теперь приступим к рассмотрению данного вопроса (у которого есть несколько подводных камней) под катом.

Австралийский разработчик indie-игр Финн Морган (Finn Morgan) разработал очень интересную и полезную технологию для динамической подсветки 2D-спрайтов Sprite Lamp. Изюминкой этой программы является то, что для подсветки объекта с произвольной точки не требуется построение 3D-модели.



Скоро каждый сможет использовать Sprite Lamp в своих играх.

Оптический поток (Optical flow) – технология, использующаяся в различных областях computer vision для определения сдвигов, сегментации, выделения объектов, компрессии видео. Однако если мы захотим его по-быстрому реализовать в своем проекте, прочитав про него на википедии или где-нибудь еще, то, скорее всего, очень быстро наткнемся на то, что он работает очень плохо и сбоит при определении сдвигов уже порядка 1-2 пикселей (по крайней мере так было у меня). Тогда обратимся к готовым реализациям, например, в OpenCV. Там он реализован различными методами и совершенно непонятно, чем аббревиатура PyrLK лучше или хуже обозначения Farneback или чего-нибудь в этом роде, да и придется поразбираться со смыслом параметров, которых в некоторых реализациях очень много. Причем, что интересно, эти алгоритмы как-то работают, в отличие от того, что мы написали сами. В чем же секрет?

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

Ну чтож, пора копнуть чуть глубже. Понимание самого ассемблера по мне так не мыслимо без понимания того, как работает микроконтроллер. Оставим наших персонажей в комнате и вновь воспользуемся нашим воображением.
Итак сейчас нужно будет просто представлять то, о чём я напишу.
***
Представь, что ты сидишь внутри микроконтроллера. Скажем внутри ATmega 8. Только микроконтроллер это такая большая прямоугольная белая комната, а ты сидишь в удобном кресле в самом её центре. Эта комната — твой личный центр управления — ты из неё управляешь тем, что снаружи. Пока неважно ЧЕМ — пока важно КАК.

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

Меня зовут Дмитрий Никифоров, я художник по эффектам в студии Allods Team. Работа над проектом Skyforge началась для меня в мае 2011 года, до этого я делал эффекты для MMORPG «Аллоды Онлайн».

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

Доброго времени суток!

Я бы хотел рассказать Вам о своих личных ощущениях о игрострое после года работы над собственным проектом.

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

Еще раз напомнюсь, эта статья — лишь ощущения от знакомства с игростроем, и рассказ о своем небольшом опыте.