Это топик-перевод статьи Eller's Algorithm. В ней рассказывается о способе программной генерации лабиринтов. Дальнейшее повествование идет от лица автора.

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|

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

Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2^k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n²)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.

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

На первый взгляд это может показаться тривиальной задачей, не так ли? Если сторонами треугольника являются x и y, то, формально, формулой для вычисления гипотенузы будет:

sqrt(x*x + y*y)

Это работает теоретически, но на практике данный подход может приводить к ошибке. Если значение x достаточно велико, то вычисление x*x может привести к переполнению типа данных (ни один тип данных от этого не застрахован, если не рассматривать длинную арифметику), и результатом вычислений будет бесконечность.

Месяц назад здесь было объявлено, что Алексей Брагин теперь читает авторский курс лекций об операционных системах. С тех пор Алексей успел провести уже несколько занятий, которые были записаны на видео. Думаю, вполне логичным шагом будет поделиться этими записями с сообществом. Что нам стоит поступить так же как, к примеру, сделал MIT?

Прошу принять во внимание, что это пилотный проект. А так конструктивная критика приветствуется, пожелания принимаются.
Приносим извинения за качество звука, смотреть лучше в HD и погромче.

Платежи через iTunes фактические лидеры по монетизации контента, предоставляемого мобильными приложениями. В одном из известных мне приложений доход от них в 3 раза превышает доход от Google Play пользователей при том, что посещаемость последних в 1.5 раза выше. Таким образом, с одного пользователя iTunes можно получить вплоть до 5 раз больше денег, чем с одного пользователя Google Play. Данный аргумент достаточен для интеграции платежей iTunes в мобильные приложения.

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

Продолжение перевода статьи Джона Оллспоу о личных качествах ведущих разработчиков.

Зрелые разработчики не жалуются просто так

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

В этой главе сказа про дружбу C++ и Python будет на удивление мало использования Boost.Python. Передача исключений туда и обратно является по сути слабым местом данной библиотеки. Будем обходиться родным API языка Python, а где это возможно использовать Boost.Python.
Тем не менее Boost.Python создаёт окружение, в котором исключения из C++ попадают в Python в виде стандартного RuntimeError, а обратно из Python генерируется исключение C++ типа error_already_set, что означает «тебе что-то прилетело, сходи сам почитай что там». И вот здесь нам как раз будет не лишним использовать C-API языка Python, чтобы вычитать необходимую информацию об исключении и преобразовать в соответствующий класс сообразно логике приложения.
К чему такие сложности? — Дело в том, что в Python, в отличие от C++, кроме текста исключения и его типа приходит ещё и traceback — стек до места возникновения исключения. Давайте немного расширим стандартный std::exception дополнительным параметром для этого stacktrace, а заодно напишем конвертер исключений туда и обратно из классов C++ в классы исключений Python.

Как всем известно, 71% поверхности Земли занимает вода. К сожалению или к счастью, корректно изобразить океан умеют единицы. Иван Айвазовский вошел в учебники живописи благодаря одним только морским пейзажам. В компьютерных играх все еще сложнее. Когда-то море в них обозначали скоплением синих пикселей, раскрашенных белыми квадратами пены. Со временем виртуальные моря стали больше похожи на снимки из отпуска, научились качать волну и покрываться рябью, в которой иногда даже отражались очертания парусников. Но они оставались самостоятельной стихией: натолкнувшись на берег, волна превращалась в незамысловатые угловатые полигоны. Настоящий прибой логично взаимодействует с пляжем, увлажняет песок и с шуршанием откатывается назад. Такого правдоподобия удалось добиться только в современных играх. В том числе в нашем Skyforge. И хоть в основные события будут разворачиваться на суше, игроки попадут и на тропические острова, и в шумные порты. Вода будет постоянно рядом. Ее «правильный» облик будет играть большую роль. И воссоздание морской стихии – серьезная математическая задача. Расскажу об этапах ее реализации.

Данная статья является продолжением первой части.
Продолжаем мучить Boost.Python. В этот раз настала очередь класса, который нельзя ни создать, ни скопировать.
Обернём почти обычную сишную структуру с необычным конструктором.
И поработаем с возвращением ссылки на поле объекта C++, так чтобы сборщик мусора Python его не удалил ненароком. Ну и наоборот, сделаем альтернативный вариант, чтобы Python прибрал мусор после удаления того, что ему отдали на хранение.
Поехали…

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

Помимо улучшения вашего приложения путем добавления в него всяких «завитушек», есть одна вещь, которую все хорошие разработчики должны сделать со своим кодом – обработать его утилитой Instruments!

Это руководство покажет вам, как использовать наиболее важные особенности утилиты под названием Instruments, которая поставляется вместе с Xcode. Она позволит вам проверить свой программный код на наличие проблем с производительностью, утечкой памяти и других проблем.

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

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

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

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

lua.export_function(some_function);

Введение

По моему скромному мнению, Lisp — жемчужина среди языков функционального программирования. Несмотря на то, что это один из первых в истории (1958 год) высокоуровневых языков, он по сей день не перестает удивлять. Мне кажется, он настолько обогнал свое время, что его час еще только готовится прийти.

Так давайте попытаемся написать программу, которую проблематично будет создать на других языках. Как следует из названия статьи, эта программа будет редактировать собственный код по мере своего выполнения. Для ее создания я использую Common Lisp, а точнее его интерпретатор SBCL.

Пару лет назад, когда стоял вопрос отделки новой квартиры, возникла тривиальная, казалось бы, задача.
Дано:

• Кухня-студия (кухня совмещенная с холлом/коридором), три точки освещения.
• Необходимо управлять освещением из двух точек. У входа в квартиру и на кухне.

Варианты решения:

• Покупаем, так называемые, проходные выключатели, ставим три штуки на кухню, три в коридоре — вот оно счастье. Вот только получилось, что от коридора на кухню нужно вести 9 жил кабеля, некрасиво, спрятать некуда.
• Покупаем готовые решения по управлению одним источником с нескольких точек.
  Точных чисел не помню, но получалось что-то около 10000р за точку освещения + 1000р за каждый выключатель, итого 36000р. Жаба.
• Как это ни странно, но эту идею высказала жена, в общем-то далекая от IT: “ А помнишь, ты светофор в Яндексе делал? Может тут тоже что-то сам сообразишь?”
  В самом деле, а почему бы и нет, подумал я?

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

Вместо предисловия

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

Перед тем как начать я хотел бы сделать акцент на двух положениях:
Первое. Мы исходим из того что читатель знаком с такими пакетами как 3D Studio MAX (либо любым другим пакетом трехмерного моделирования) и Photoshop (или любым его аналогом). В данном конкретном случае я собираюсь использовать терминологию этих двух пакетов. Однако, не смотря на это те же самые принципы можно использовать, пользуясь любым другим софтом.

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

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

Хочу также отметить, что я не причисляю себя к мастерам, которые делают шедевры. Данное примечание я делаю для тех злых людей, которые говорят (или скажут после публикации), что я заносчив, что меня занесло под небеса, и тех кто вместо того чтобы работать предпочитает злословить словно ябедник Кийр из моей любимой книги Оскара Лутса «Весна».

С преамбулами покончено перейдем к сути.

Я утверждаю и не беспочвенно, что хороший фон можно и нужно создавать не за неделю, не за пять дней и даже не за три. Чтобы сделать хорошую картинку для казуальной игры, без разницы i-spy это, match-3 или аркада, достаточно 48 часов. Разумеется, при условии того, что человек занимается работой, а не просиживанием штанов.

Если вы пишете не казуалку под веб и не беспощадный суровый рогалик, без сохранения данных на диск не обойтись.
Как это делается в Unity? Вариантов тут достаточно — есть класс PlayerPrefs в библиотеке, можно сериализовать объекты в XML или бинарники, сохранить в *SQL*, можно, в конце-концов, разработать собственный парсер и формат сохранения.
Рассмотрим поподробнее с первые два варианта, и заодно попробуем сделать меню загрузки-сохранения со скриншотами.

Будем считать, что читающий дальше базовыми навыками обращения с этим движком владеет. Но при этом можно не подозревать о сущестовании в его библиотеке PlayerPrefs, GUI, и ещё в принципе не знать о сериализации. С этим всем и разберёмся.
А чтобы эта заметка не стала слишком уж увлекательной и полезной, ориентирована она самый неактуальный в мобильно/планшетно/онлайновый век вариант — сборку под винду (хотя, конечно, более общих моментов достаточно).

• Кстати, пару недель назад на Хабре была статья, где автор упомянул, что Unity3D проходят в курсе компьютерной графики на кафедре информатики питерского матмеха. Занятный факт, немало говорящий о популярности движка.
  Хотя насколько это в целом хорошая идея — на мой взгляд, тема для дискуссии. Может быть, обсудить это было бы даже интереснее вопросов сериализации =)

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

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

Основная проблема – это то, что маркетинг у нас или обывательский («мне кажется, что должно быть так») или книжный («а вот у Котлера написано, что…».). В первом варианте советы представляют из себя смесь банальностей со стереотипами, во втором — знание устаревшее на полвека. Делать маркетинг по книжкам, это все равно, что работать на PCX86 – вроде можно, но смысл?



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

Доброго всем дня.

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

Добрый день!



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

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

Итак, сначала немного пафоса.

Ключ к успеху при разработке free-to-play игр — анализ поведения игроков и постоянный тюнинг игрового функционала на основе статистики. Собрать статистику — это пол дела. Но как превратить гору сырых данных в информацию?

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

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

В результате стандартный консервативный аллокатор выстраивает все запросы в очередь на pthread_mutex / critical section. И наш многоядерный процессор медленно и печально едет на первой передаче.

И что с этим делать? Познакомимся поближе с деталями реализации метода Scalable Lock-Free Dynamic Memory Allocation. Maged M. Michael. IBM Thomas J. Watson Research Center.

Самый простой код что я сумел найти — написан под LGPL камрадами Scott Schneider и Christos Antonopoulos. Его и рассмотрим.