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

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

Предисловие

→ Первая часть

Итак. Оценив отклик аудитории Хабра и разобравшись с делами, я принялся за написание второй статьи из цикла. Реакция публики оказалась значительно позитивнее моих предположений, а значит, мы продолжаем разговор на одну из любопытнейших тем процедурной генерации – создание лабиринтов.

В этой части мы поговорим о том, что же такое случайная и псевдослучайная генерации, какие алгоритмы могут дать нам равновероятно ничем не похожие друг на друга лабиринты и в чем их минусы. Героями нашего сегодняшнего приключения станут алгоритм Уилсона и алгоритм Олдоса-Бродера для создания случайного остовного дерева (Uniform Spanning Tree). ОСТОРОЖНО ТРАФИК.

Помните небезызвестный мем про "корованы"? Наверное, каждый, кто разрабатывает игры (или хотел бы этим заняться) раздумывает о неком "проекте мечты", где можно будет "грабить корованы" и "набигать". А ещё, чтобы погода менялась динамически, и на грязи следы от сапог оставались, и деревья росли в реальном времени. И ещё, чтобы ...

Понятно, что в реальном игровом проекте такая погоня за хотелками — смерти подобна. А вот в техно-демке — самое то.

Приветствую пользователей Хабра. Наверное, многие из более менее опытных пользователей слышали про JavaScriptInterface — «мостик» между Java и JavaScript, при помощи которого можно вызывать Java методы. У JavaScriptInterface есть несколько довольно значимых недостатков:

1) Методы вызываются не в UI-потоке, а в специальном потоке Java Bridge, который нельзя забивать, иначе WebView перестанет отвечать.
2) При обращении к UI из методов, вызванных при помощи JavaScriptInterface, ничего не происходит, что может привести к нескольким часам дебага у незнающих разработчиков. Как решение, приходится использовать метод runOnUi или хендлеры.
3) Невозможно передавать пользовательские типы данных

Вызов JS-функций стандартным способом происходит так:

myWebView.loadUrl("myFunction('Hello World!')");

Минус данного подхода в том, что вызов функции — это, фактически, строка, и при передаче аргументов всех их нужно конвертировать в String.

Столкнувшись с этими проблемами в одном из своих проектов, в котором Java и JavaScript взаимодействуют очень тесно, я решил написать библиотеку облегчающую вызовы JS из Java и наоборот.

В этом уроке мы будем изучать React Native – фреймворк от компании Facebook для создания нативных приложений под iOS и Android. У него много общего с другим очень популярным фреймворком от Facebook – React Javascript, который предназначен для построения декларативных пользовательских интерфейсов.

В данной статье я расскажу про интересные и немного неочевидные моменты разработки видеоигры в сжатые сроки: по регламенту конкурса, работоспособную демку необходимо сдать в течение недели, а релиз — в течение двух недель. Статья предназначена для тех, кто уже игрался с Unity3D, но еще не делал на этом игровом движке никаких проектов сложнее HelloWorld’а.

Картинка для привлечения внимания — скриншот игры.

Последние несколько лет я занимаюсь R&D в области интернета вещей и распределенных систем, а так же являюсь Google developer expert IoT. В этой статье я хочу поделиться своим опытом и рассказать про новую концепцию Physical Web. Так же расскажу про разные маячки (англ. Beacon — маяк) и сравню основные стандарты iBeacon, Altbeacon и Eddystone.

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

Jack (Java Android Compiler Kit) – это компилятор, преобразующий исходный код на Java в DEX-файлы Android. Jack – это набор инструментов, среди его возможностей – переупаковка, сжатие, обфускация и поддержка множественных DEX-файлов.

В Jack используются промежуточные библиотеки в формате .jack. Преобразованием существующих .aar/.jar файлов в этот формат занимается Jill (Jack Intermediate Library Linker).



Если для сборки используется Jack, то сначала Jill конвертирует внешние библиотеки, используемые в проекте, в .jack-файлы. Это подготавливает библиотеки к быстрому слиянию с другими .jack-файлами на следующем этапе, когда Jack и плагин Android Gradle, используя подготовленные ранее.jack-файлы и исходный Java-код, компилируют DEX-файл (или файлы). В ходе этого процесса Jack может выполнить минификацию кода (сжатие, обфускацию, или и то и другое вместе). На выходе получается APK-файл Android-приложения.

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

Я столкнулся с необходимостью составления списка всех перестановок из n элементов. Для n = 4 или даже 5, задача решается вручную в считанные минуты, но для 6! = 720 и выше исписывать страницы мне уже было лень – нужна была автоматизация. Я был уверен, что этот «велосипед» уже изобретён многократно и в различных вариациях, но было интересно разобраться самостоятельно – поэтому, намеренно не заглядывая в профильную литературу, я засел за создание алгоритма.

Около двух месяцев назад мы анонсировали конкурс по Material Design. Вот и подходит к концу последняя неделя конкурса (напомним, работы принимаются до 15 ноября), поэтому самое время для последнего рывка. Пока не поздно подать заявку. :)


^{Вы думали, обои для Android 6.0 делают в фотошопе? А вот и нет.}

За время конкурса произошли следующие позитивные изменения: часть материалов по Material Design стала доступна и на русском языке (если у вас на странице текст отображается на английском, то проверьте выбор языка в нижнем правом углу). Данный курс по Material Design содержит примеры кода и разметки и будет полезен разработчикам. Кроме того, мы рады представить вам дополнительные источники вдохновения. Быть может, именно они помогут вам завершить редизайн.

CMU Sphinx сейчас является крупнейшим проектом по распознаванию человеческой речи. В инструментарий входят следующие программы и библиотеки:

• Pocketsphinx — небольшая программа, которая принимает на вход произвольные акустические модели, грамматики и словари, а также звуковой поток(либо звуковой файл, либо сам берет поток с микрофона). На выходе получается распознанный текст. Написана на C, работает быстро.
• Sphinxbase — библиотека необходимая для работы Pocketsphinx
• Sphinx4 — гибкая библиотека для распознавания, написана на Java.
• Sphinxtrain — программа для обучения акустических моделей.

Для работы со CMU Sphinx важно запомнить несколько определений и понять их отличия.

• Акустическая модель — отвечает за сопоставление звуку произнесенной фонемы. Акустическую модель для русского языка можно скачать на сайте проекта. Русская акустическая и языковая модели. А также словарь.
• Словарь — это файл, в котором написаны сопоставлены лексемы и фонемы (слово и его транскрипция). Например, калькулятор (k ay ll k u ll ja t ay r). Он необходим для преобразования фонем, распознанных акустической моделью в лексемы.
• Грамматика — это формальные правила, которые описывают простые правила построения предложений. Лексемы, полученные на предыдущем шаге пытаются сопоставиться с грамматикой и если удачно, то выводится результат.
• Языковая модель — это статистическая модель языка. Она описывает вероятности слов и их комбинаций. Таким образом распознавание лексем — это максимизация правдоподобности распознанной фразы.

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

Несколько месяцев назад я опубликовал плагин к Moment.js позволяющий рассчитать: сколько это N рабочих дней от сегодня в календарных днях? какая дата будет спустя N рабочих дней от заданной даты? сколько рабочих дней в заданном диапазоне? Возможность сконфигурировать рабочие дни и исключения в виде праздников — имеется.

Плагин можно найти на github: https://github.com/andruhon/moment-weekday-calc

Плагин можно установить через bower и npm:

bower install moment-weekday-calc

npm install moment-weekday-calc

Плагин добавляет несколько функций в Moment.js:

• int weekdayCalc — считает сколько «рабочих» дней в заданном диапазоне
• date addWorkdays — находит дату спустя N «рабочих» (пн-пт) дней
• int workdaysToCalendarDays — конвертирует рабочие дни в календарные
• date addWeekdaysFromSet — добавляет дни из заданного множества к заданной дате
• int weekdaysFromSetToCalendarDays — конвертирует дни из заданного множетсва в календартные дни

Каждая из функций доступна с префиксом iso, такие функции используют множество рабочих дней начинающееся с понедельника (1-7), функции без префикса используют американский формат начинающийся с воскресенья (0-6).

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

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

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

Этот урок описывает метод планирования течения игры и навигации юнитов, который использует многоагентные потенциальные поля. Он основан на работах под номерами [1, 2, 3]. (Смотри в конце статьи ссылки на используемые материалы)

Я должен признаться, что написать эту статью я решил очень спонтанно, прочитав статью «XMPP отстой» и почувствовав некоторую близость к чувствам автора, так как также использую ХМРР в одном из наших продуктов. Тем не менее, сжав эмоции в кулак, я всё-таки решил просто изложить, почему я испытываю смешанные чувства к данному протоколу и разложить по полкам плюсы и минусы. Также расскажу, что мы выбрали для сервера и клиента. Это все, чтобы тебе, дорогой читатель, сделать правильный выбор и вырвать меньше волос в твоих будущих проектах.

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

Для статьи я подобрал наиболее полезные дополнения «на все случаи жизни».

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

Для примеров будет использоваться популярный движок Unity3D. Рассматриваются подходы, применимые в больших играх. Написано из моего личного опыта и из того, как я это понимаю. Конечно, где-то я могу быть не прав, где-то можно лучше сделать. Я тоже все еще в процессе набирания опыта и набивания новых шишек.

В публикации рассматриваются следующие темы:

• Наследование VS компоненты
• Сложные иерархии классов юнитов, предметов и прочего
• Машины состояний, деревья поведений
• Абстракции игровых объектов
• Упрощение доступа к другим компонентам в объекте, сцене
• Сложные составные игровые объекты
• Характеристики объектов в игре
• Модификаторы (баффы/дебаффы)
• Сериализация данных

ownCloud, как утверждает Википедия — это Свободное и открытое веб-приложение для синхронизации данных, расшаривания файлов и удалённого хранения документов в «облаке». И, как мне кажется, довольно интересное решение для организации собственного домашнего облака.

Однако, ownCloud, устанавливающийся в виде плагина в системе FreeNAS, да и просто из коробки, имеет ряд недостатков, от которых хотелось бы избавится даже при использовании дома:

• Во-первых, устанавливается в связке с SQLite, что подходит только если у вас небольшое кол-во файлов и пользователей, и абсолютно не подходит, если вы планируете синхронизацию с помощью клиента. У меня же хранилище уже расползлось почти на 5Tb и установленный таким образом ownCloud просто отказывался видеть часть файлов. Да и без синхронизации отдача от облака не велика. Заменим базу данных на MariaDB.
• Во-вторых, отсутствует работа по https, а мне совсем не нравится мысль о том, что кто-то может перехватить мои файлы. Включим https.
• В-третьих, начисто отсутствует защита от банального подбора пароля методом брутфорса. Защитимся от брутфорса с помощью fail2ban.
• В-четвёртых, мне лень часто просматривать логи на предмет взлома, но очень хочется оперативно узнавать о таких попытках. Настроим push-оповещения о попытках подбора пароля с помощью сервиса pushover.net.

Предлагаю читателям «Хабрахабра» перевод публикации «30 Amazing PHP Libraries for Programmers and Developers». Авторы собрали несколько удивительных PHP-библиотек, которые помогут реализовать некоторые классные вещи, не прилагая много усилий. Цель обзора состоит в том, чтобы преподнести что-то новое, поэтому список не включает популярные библиотеки.