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

Классификация лабиринтов

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

Не так давно я прочёл фантастический роман «Задача трёх тел» Лю Цысиня. В нём у одних инопланетян была проблема — они не умели, с достаточной для них точностью, вычислять траекторию своей родной планеты. В отличии от нас, они жили в системе из трёх звёзд, и от их взаимного расположения сильно зависела «погода» на планете — от испепеляющей жары до леденящего мороза. И я решил проверить, можем ли мы решать подобные задачи.

Пришли очередные выходные, надо написать пару десятков строк кода и нарисовать картинку, да лучше не одну. Итак, на прошлых и позапрошлых выходных я показал, как делать трассировку лучей и даже взрывать всякое. Это многих удивляет, но комьпютерная графика — очень простая вещь, пары сотен строк голого C++ вполне хватает на создание интересных картинок.

Тема сегдоняшнего разговора — бинокулярное зрение, причём сегодня даже до ста строк кода не дотянем. Умея рендерить трёхмерные сцены, было бы глупо пройти мимо стерепар, сегодня будем рисовать примерно вот такое:

Добрый день.
Меня зовут Головач Иван, я руковожу небольшой образовательной компанией и преподаю сам:

1. Java Core
2. Junior Java Developer: Servlet API, JDBC, Maven, JUnit, Mockito, Log4J, основы Spring/SpringMVC, основы JPA/Hibernate, шаблоны/архитектуры MVC/IoC/DAO.
3. Multicore programming in Java.

Также я веду курс «Scala for Java Developers» на платформе для онлайн-образования udemy.com (аналог Coursera/EdX).

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

(GolovachCourses.com)

Здесь собраны несколько вариантов записи моего курса Java Core.
Модуль #1 (Procedural Java):
Набор июль 2013: #1, #2, #3, #4
Набор апрель 2013: #1, #2, #3, #4
Набор февраль 2013: #1, #2, #3, #4
Набор январь 2013: #1, #2, #3, #4
Набор октябрь 2012: #1, #2, #3, #4.

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

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

Итого, как в таких условиях нарисовать вот такую картинку за 180 строчек кода?

С 2012 года ежегодно проводится соревнование Russian AI Cup по написанию искусственного интеллекта и ботов, которые ожесточенно сражаются в виртуальном мире вместо своих владельцев. За все прошлые чемпионаты на платформе зарегистрировалось более 20 000 пользователей, которые прислали нам более 150 000 различных решений. Каждый новый чемпионат — это новая игровая задача со своими правилами, законами и механикой. Стараемся постоянно вносить новые идеи и фичи, чтобы игры из года в год становились еще более интересными и зрелищными, развивая наш мотор под капотом проекта и делая всё во славу нашего сообщества.

Этот год не стал исключением. Mail.Ru Group в сотрудничестве с Codeforces.com официально объявляют о датах чемпионата Russian AI Cup 2018 под названием CodeBall.

Итак, поехали!

Суть разработки программного обеспечения
— Нужно проделать 500 отверстий в стене, так что я сконструировал автоматическую дрель. В ней используются элегантные точные шестерни для непрерывной регулировки скорости и крутящего момента по мере необходимости.
— Отлично, у неё идеальный вес. Загрузим 500 таких дрелей в пушку, которые мы сделали, и выстрелим в стену.

Я занимаюсь программированием уже 15 лет. Но в последнее время при разработке не принято думать об эффективности, простоте и совершенстве: вплоть до того, что мне становится грустно за свою карьеру и за IT-отрасль в целом.

Для примера, современные автомобили работают, скажем, на 98% от того, что физически позволяет нынешняя конструкция двигателя. Современная архитектура использует точно рассчитанное количество материала, чтобы выполнять свою функцию и оставаться в безопасности в данных условиях. Все самолёты сошлись к оптимальному размеру/форме/нагрузке и в основном выглядят одинаково.

Только в программном обеспечении считается нормальным, если программа работает на уровне 1% или даже 0,01% от возможной производительности. Ни у кого вроде нет возражений.

В предыдущей статье мы рассмотрели несколько интересных моментов языка python, разумеется, одной статьёй они не исчерпываются, поэтому продолжим.

В одном из комментариев рассматривался следующий код:

SEX = 'Female', 'Male'
sex = SEX[True]  # -> Male
sex = SEX[False] # -> Female

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

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

В итоге все свои эксперименты я вылил на GitHub.

Источник: Pexels

Каждый пользователь Хабра, хоть раз напечатавший здесь «пробел-дефис-пробел», может видеть, как дефис магическим образом заменяется на длинное тире. Это сработала автозамена, похожая на ту, что имеется в ворде и других текстовых процессорах.

Не хотите читать? Посмотрите демо.

Символы нулевой ширины — это непечатаемые управляющие символы, которые не отображаются большинством приложений. Н​апример, в э​то пред​ложение я вст​авил де​сять про​​белов н​улевой ширины, вы эт​о замет​или? (Подсказка: вставьте предложение в Diff Checker, чтобы увидеть местоположение символов!). Эти символы можно использовать как уникальные «отпечатки» текста для идентификации пользователей.


Безусловно, он может здесь быть. И вы никогда не догадаетесь

Зачем?

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

Всем бобра!

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

Поехали.

PyPy способен ускорить код в 2 раза, что радует очень многих людей. Хочу поделиться короткой, личной историей, доказывающей, что PyPy способен на большее.

ДИСКЛЕЙМЕР: это не чудодейственное средство на все случаи жизни, да, сработало конкретно в этом случае, но может оказаться не таким эффективным во многих других. Однако метод все равно интересный. Более того, шаги, описанные здесь, я применял во время разработки в том же порядке, что делает статью жизненным примером оптимизации PyPy.

Я экспериментировал с эволюционными алгоритмами несколько месяцев назад: план был амбициозным — автоматически развить логику, способную контролировать (симулированный) квадрокоптер, то есть PID-регулятор (спойлер: не летает).

Некоторое время тому назад я решил попробовать написать что-то на Python под Android. Такой странный для многих выбор обусловлен тем, что я люблю Python и люблю Android, а ещё люблю делать необычное (ну хорошо, не самое обычное). В качестве фреймворка был выбран Kivy — фактически, безальтернативный вариант, но он мне очень понравился. Однако, по нему не так уж много информации (нет, документация отличная, но иногда её недостаточно), особенно на русском языке, а некоторые вещи хоть и можно реализовать, но их то ли никто раньше не делал, то ли не счёл нужным поделиться информацией. Ну а я счёл :) И этот пост тому результатом.

Под катом я расскажу обо всех этапах разработки, о том, как развивалась простая идея и как для этого приходилось искать новые возможности, о возникших подводных камнях и багах, о неочевидных решениях и устаревшей документации :) Цель — описать в одном тексте основные пункты, чтобы человеку, решившему написать что-то немного сложнее игры Pong из официального туториала, не приходилось перерывать официальный форум поддержки и StackOverflow и тратить часы на то, что делается за пару минут, если знаешь, как.

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


Я недавно подсчитал, что уже 5 лет занимаюсь созданием игр в свободное от основной работы время. За этот период я сделал несколько игр, которые можно назвать успешными, если судить по количеству загрузок. Но по настоящему, я горжусь только последней, она изображена на картинке выше. Нет, это не игра про лутбоксы. Это набор головоломок, основная идея которого в том, чтобы объединить разноплановые головоломки одним сюжетом. Но главное, это должны быть головоломки с подвохом, такие, которые требуют от игрока нешаблонного, креативного мышления. Головоломки с простым, но при этом неожиданным решением. Под катом гифки, история создания и технические детали этой игры.

Предисловие

Как можно развлечься в новогодние праздники? Поиграть в компьютерные игры? Нет! Лучше написать бота, который это будет делать за тебя, а самому пойти лепить снеговика и пить глинтвейн.

Когда-то в школьные годы был увлечен одной из популярных MMORPG — Lineage 2. В игре можно объединяться в кланы, группы, заводить друзей и сражаться с соперниками, но в общем игра наполнена однообразными действиями: выполнением квестов и фармом (сбор ресурсов, получение опыта).

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

Всем привет! Хочу рассказать про историю своей победы в ежегодном соревновании по написанию игровых ботов Russian AI Cup, в 2017. В финале бот выиграл 98% игр, что, как оказалось, наивысший результат по финалам среди всех годов проведения чемпионата. Также занял 1-е место в песочнице по завершению её работы, в пике переходя за 4000 очков рейтинга.



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

После публикации моей статьи о том, какой была бы Земля, будь она в два раза больше, у читателей появился вопрос: «А что насчёт тороидальной Земли»? Вопрос не самый оригинальный, эту тему уже обсуждали в онлайне и проводили её моделирование. Но я люблю всё делать сам, так что я попытался провести свой собственный анализ.

Может ли существовать тороидальная планета?

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

Привет, Хабр!

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

Всем привет! Это уже восемнадцатый выпуск дайджеста на Хабрахабр о новостях из мира Python.

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

Итак, поехали!