Привет любителям микро-кодирования. Вот вам кое-что невероятное: крошечный движок raycasting (метод “бросания лучей”) и генератор городов, который помещается в отдельный 256-байтовый HTML-файл.
User
Демо City In A Bottle – система рейкастинга в 256 байтах
Medium
8 min
Review
Translation
Привет всем любителям size coding, сегодня я расскажу о чём-то потрясающем: крошечном движке трассировки лучей (raycasting) и генераторе города, умещающихся в автономном файле HTML размером 256 байтов.
В этом посте я поделюсь секретами работы этой волшебной программы. Возможно, вы уже видели этот пост в моём Twitter. После публикации два года назад он стал самым популярным моим твитом.
В этой потрясающей программе используется множество разных концепций, а их разбор похож на решение головоломки. Программа состоит из нескольких основных частей: html-кода, цикла обновления кадра, системы рендеринга, движка рейкастинга и самого города.
Возможно, вы подумаете, что для распутывания этой загадки необходима сложная математика, но на самом деле это не так, сам код довольно прост и в нём используется простейшая алгебра, даже без тригонометрических функций. Впрочем, там есть несколько трюков, позволяющих создать впечатляющий результат.
Delta-Rle-Huffman (DRH) Texture Format
8 min
Всем привет! В этой статье я опишу алгоритм работы формата сжатия изображений без потерь. Сжатие использует известные методики, которые и дали ему название. Проект начинался с простых экспериментов, которые вышли из под контроля. Не смотря на то, что формат чаще сжимает лучше чем png, никакого практического применения этот формат не имеет, оставаясь чисто академическим.
Внимание! В статье много картинок.
Compiler Explorer — уникальный проект для исследования компилируемого кода
Medium
7 min
Review
Translation
Этот пост посвящён замечательному инструменту, полезному для каждого, кто интересуется компиляторами или архитектурой компьютеров. Это Compiler Explorer, который я в дальнейшем будут называть CE.
CE — потрясающий инструмент. Если вы с ним не знакомы, то прервите чтение и перейдите на веб-сайт CE, где вы увидите примерно такой экран:
Предупреждение: вы забираетесь в «кроличью нору», на которую можете потратить несколько часов своего времени.
В основе CE лежит очень простая идея. Достаточно ввести исходный код в левую панель, и сайт мгновенно покажет вам на правой панели скомпилированный результат (обычно на языке ассемблера).
То есть теперь для просмотра результата работы компилятора достаточно открыть godbolt.org и скопировать туда блок кода.
Это само по себе удивительно, но у CE есть гораздо больше возможностей. Это инструмент, который должны знать все интересующиеся компиляторами и архитектурами компьютеров. В статье мы сможем лишь поверхностно рассмотреть функции CE. Вам стоит самим перейти на сайт CE и попробовать всё самостоятельно.
CE — потрясающий инструмент. Если вы с ним не знакомы, то прервите чтение и перейдите на веб-сайт CE, где вы увидите примерно такой экран:
Предупреждение: вы забираетесь в «кроличью нору», на которую можете потратить несколько часов своего времени.
В основе CE лежит очень простая идея. Достаточно ввести исходный код в левую панель, и сайт мгновенно покажет вам на правой панели скомпилированный результат (обычно на языке ассемблера).
CE поддерживает 69 языков, более двух тысяч компиляторов и широкий спектр архитектур, включая x86, arm, risc-v, avr, mips, vax, tensa, 68k, PowerPC, SPARC и даже древний 6502.
То есть теперь для просмотра результата работы компилятора достаточно открыть godbolt.org и скопировать туда блок кода.
Это само по себе удивительно, но у CE есть гораздо больше возможностей. Это инструмент, который должны знать все интересующиеся компиляторами и архитектурами компьютеров. В статье мы сможем лишь поверхностно рассмотреть функции CE. Вам стоит самим перейти на сайт CE и попробовать всё самостоятельно.
Почему для меня так важен алгоритм CORDIC
Medium
8 min
Review
Translation
CORDIC — это алгоритм для вычисления тригонометрических функций вроде
sin, cos, tan и тому подобных на маломощных устройствах без использования модуля обработки операций с плавающей запятой или затратных таблиц поиска. По факту он сводит эти сложные функции до простых операций сложения и битового сдвига.Перейду сразу к делу и скажу, почему я так сильно люблю этот алгоритм, а затем займёмся изучением принципов его работы. По сути, фактические операции CORDIC весьма просты — как я уже сказал, это сдвиги и сложение — но выполняет он их путём комбинирования векторной арифметики, тригонометрии, доказательств сходимости и продуманных техник компьютерных наук. Лично я считаю, что именно это имеют ввиду, описывая его природу, как «элегантную».
Точное увеличение растровых изображений
Medium
10 min
Analytics
Как красиво в фильмах увеличивают изображения с дешёвой видеокамеры, да так, что чётко видно лицо в отражении зрачка человека, находящегося за километр. Я тоже так хочу. А что мы имеем по факту? На какой максимальный результат можно рассчитывать хотя бы теоретически? А оказывается можно сделать чуть лучше, чем размазню...
Алгоритм пересечения полигонов
20 min
Tutorial
Translation
В этом посте мы разработаем алгоритм, позволяющий вычислять пересечение выпуклых полигонов. Так же на ряду с проверкой точки на принадлежность полигону мы рассмотрим метод пересечения выровненных по осям прямоугольников и функцию пересечения отрезков.
Я купил смартфон за 500 рублей, а он оказался с подвохом. Делаем из него домашний сервер
7 min
К сожалению, не все покупки с пересылкой в другой город на онлайн-барахолках удачные. Иногда продавцы умалчивают серьёзные дефекты ништяков, а на почте всё проверить невозможно: ведь очередь тоже ждать не будет! Так и случилось в рамках сегодняшней статьи, когда я заказал Samsung Galaxy J3 и S4 за 1.000 рублей, а у них обоих оказались очень серьёзные косяки, о которых продавец конечно же умолчал! У J3 был сколот дисплей (на фотографии не было видно), он стоял на пароле (об этом было оговорено заранее) и у него варварски, вместе с пятачками был выдран один из сим-лотков! Но он отнюдь не бесполезен и из него можно сделать вполне себе полноценный сервер. Как? Читайте в статье!
Простое объяснение алгоритмов поиска пути и A*
13 min
Translation
Часть 1. Общий алгоритм поиска
Введение
Поиск пути — это одна из тех тем, которые обычно представляют самые большие сложности для разработчиков игр. Особенно плохо люди понимают алгоритм A*, и многим кажется, что это какая-то непостижимая магия.
Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.
Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.
ChatGPT клиент для MS-DOS
Easy
2 min
Review
Благодаря стараниям ретро энтузиаста Yeo Kheng Meng (очень рекомендую его сайт, много интересного по ретро технике) можно юзать ChatGPT на DOS машинах. Кто владеет языком рекомендую Оригинальный пост на ангельском.
Я тестил проект на машине Toshiba T1200, (для которой к слову опробовал пару новых модов, о которых напишу ниже). Железо: проц 8086, 640КБ озу (Технически 1024КБ но это не точно), HDD неисправен, поэтому грузимся с дискет (720КБ). Подключение к сети я подробно описал в предыдущем посте
Проект на гите https://github.com/yeokm1/doschgpt - качаем самую свежую версию (на момент публикации v0.15) - два файла: doschgpt.exe и doschgpt.ini из папки releases. В ini файле нужно прописать ваш api ключ для chatGPT, версию языковой модели и адрес http-https прокси. Proxy? Да. Разумеется DOS не поддерживает SSL который нужен для подключения к апишке ChatGPT, но к счастью наш друг Yeo Kheng Meng написал удобное proxy-приложение https://github.com/yeokm1/http-to-https-proxy - нужно запустить на промежуточном компьютере и указать адрес этого пром. компьютера в файле doschgpt.ini
Arduino AY player: продолжение
Medium
16 min
Изучаем устройство OLED-экрана SSD1306 и дорабатываем звуковые индикаторы музыкального плеера PSG-файлов на чипе AY-3-8910.
Реализация алгоритма Дейкстры на C#
11 min
Введение
Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке C#. Кстати отмечу, что использую LINQ, так что для работы необходим NET 3.5.
UPDНаконец-то подчистил код :)
Немного теории
Чтобы сразу не кидали камни в мой огород дам ссылку на очень хорошее описание алгоритма на таком незаметном ресурсе как Википедия :). Там вполне доступно описан алгоритм и особенно рекомендую посмотреть пример. Копировать оттуда материал считаю бессмысленно. Все, считаем что теорию изучили.
Начало
Данный код представляет реализацию алгоритма на взвешенном неориентированном графе. Рассмотрим реализацию этого алгоритма.
Объектами данного алгоритма являются три класса:
• Apoint – класс, реализующий вершину графа
• Rebro – класс, реализующий ребро графа
• DekstraAlgoritm – класс, реализующий алгоритм Дейкстры.
Рассмотрим подробнее данные классы и самые важные методы.
APoint
Данный класс содержит в себе 5 полей:
•public float ValueMetka { get; set; } данное поле отвечает за хранение значений метки данной вершины. В программе под бесконечностью берется очень большое число, например 99999.
•public string Name { get; set; } – имя метки. Данное поле необходимо лишь для выведения удобно читаемого результата.
•public bool IsChecked { get; set; } – означает помечена метка или нет
•public APoint predPoint { get; set; } – «предок» точки, т.е. та точка которая является предком текущей в кратчайшем маршруте.
•public object SomeObj { get; set; } – некий объект
Каких-либо значимых методов данный класс не содержит.
Rebro
Данный класс содержит 3 поля:
•public APoint FirstPoint { get; set; } – начальная вершина ребра
•public APoint SecondPoint { get; set; } – конечная вершина ребра
•public float Value { get; set; } – весовой коэффициент.
Каких-либо значимых методов данный класс не содержит.
DekstraAlgorim
Данный класс представляет собой граф и реализацию алгоритма Дейкстры. Содержит 2 поля:
•public APoint[] points { get; set; } – массив вершин
•public Rebro[] rebra { get; set; }- массив ребер
Таким образом, эти 2 массива отражают граф. Рассмотрим методы:
•private APoint GetAnotherUncheckedPoint()
Данный метод возвращает очередную неотмеченную вершину, наименее удаленную, согласно алгоритму.
•public void OneStep(APoint beginpoint)
Данный метод делает один шаг алгоритма для заданной точке.
•private IEnumerable Pred(APoint currpoint)
Данный метод ищет соседей для заданной точки и возвращает коллекцию точек.
•public string MinPath(APoint begin,APoint end)
Данный метод возвращает кратчайший путь, найденный в алгоритме от начальной точке до конечной. Этот метод используется для наглядного отображения пути
•public void AlgoritmRun(APoint beginp)
Данный метод запускает алгоритм и принимает в качестве входа начальную точку.
Все основные методы описаны, представим процесс работы алгоритма в целом на рис.1. Основной метод OneStep представлен на рисунке 2.
Рис.1. Работа алгоритма в целом
Рис.2. Работа метода OneStep
Код
Наконец, рассмотрим сам код. В каждом классе написал подробные комментарии.
Обзор и оживление «японского пенька»
4 min
Всем привет! Сегодня хотелось бы рассказать про реликвию, с которой началось мое настоящее знакомство с компьютерами, — ноутбук Fujitsu Lifebook 634Tx 1998 года выпуска.
Только не надо записывать меня в счастливчики и «мажоры»: девайс принадлежал моему старшему (на 13 лет) брату, мне же, тогда школьнику, иногда перепадала возможность посидеть за ноутбуком и погонять монстров в Doom.
Прошло больше 20 лет. Копаясь на антресолях в бабушкиной квартире, я случайно наткнулся на этот артефакт. Получил от брата разрешение на любые манипуляции и решил оживить и заодно обозреть. Ну, приступим.
MenuetOS, которая умещается на дискете, снова обновилась: что «выросло» в новой версии
4 min
Некоторые читатели Хабра, вероятно, дискет и в руках не держали, поскольку те вышли из обращения много лет назад. Но ряд современных программ и «железа» всё ещё с ними связан. Например, проект MenuetOS представляет собой операционную систему, которая умещается как раз на дискете. Дело в том, что написана она на ассемблере, а команда разработчиков заботится о приемлемом соотношении объём/функциональность. Насколько можно судить, получается у них всё это весьма неплохо. Подробности о новинке — под катом.
Челлендж по обработке миллиарда строк на Go: от 1 минуты 45 секунд до 4 секунд
Medium
14 min
Case
Translation
Пару недель назад я прочитал о запавшем мне в душу челлендже по обработке миллиарда строк, поэтому захотел решить его на Go.
Я немного опоздал, соревнования проводились в январе. И на Java. Меня не особо интересует Java, зато давно интересует оптимизация кода на Go.
Этот челлендж был очень прост: обработать текстовый файл названий метеорологических станций и температур, и для каждой станции вывести минимальное, среднее и максимальное значение. Чтобы упростить задачу, было ещё несколько ограничений, однако я проигнорировал те, что относятся только к Java.
Собираем самодельный перьевой плоттер
7 min
Translation
В этой статье задокументированы уроки, полученные мной при проектировании и создании самодельного перьевого плоттера летом 2023 года.
Моей конечной целью было создание собственного станка с программным управлением, и перьевой плоттер показался мне хорошим промежуточным шагом в этом направлении. Это важный контекст в проектировании этого устройства, потому что если бы мне просто нужен был перьевой плоттер, то многое можно было бы упростить.
Замена CCFL подсветки на светодиодную. На примере информационного дисплея Mitsubishi L200/Pajero Sport II
Easy
3 min
Приветствую, Хабр!
Снова хочу предложить Вашему вниманию статью по ремонту электроники. Несколько лет назад знакомый попросил меня отремонтировать подсветку информационного дисплея на Mitsubishi L200. Позже он пересел на Pajero Sport II и вернулся с той же проблемой уже на этом автомобиле. В прошлый раз я забыл сделать для себя пометки по ремонту и пришлось разбираться заново. Идея замены ламп CCFL на светодиоды лежит на поверхности, и я уже не раз менял подсветку таким образом в стареньких, но еще вполне приличных, телевизорах и мониторах.
Векторизация изображений. Как создать алгоритм поиска похожих изображений на Python
Medium
8 min
Многочисленные исследования ученых доказывают, что около 90% информации человек воспринимает через зрение. Изображения являются одним из самых богатых источников информации, которую можно использовать для разнообразных задач, включая классификацию, детекцию объектов, ранжирование изображений, поиск по изображениям и генерацию текстовых описаний.
Все перечисленные выше задачи сегодня реализуются с применением машинного и глубокого обучения. Однако для эффективной обработки изображений необходимо иметь их числовое представление, так как модели машинного обучения способны воспринимать только его.
В мире есть много вещей, которые интуитивно понятны и очевидны для нас. Например, если перед нами два похожих цветка, мы можем определить их принадлежность одному виду, даже не зная названий этих растений. Этот навык позволяет нам распознавать объекты и определять их в группы. Разумеется, подобные алгоритмы уже давно существуют в современных поисковиках Google, Яндекс и прочих. Но что, если вы проектируете обособленную систему с собственной базой изображений одной или нескольких конкретных тематик и вам необходим функционал поиска похожих изображений?
В этой статье мы сосредоточим ваше внимание на том, как построить подобный алгоритм на Python, а также расскажем о компьютерном зрении и эмбеддинге изображения.
Введение в программирование: простой 3D-шутер с нуля за выходные, часть 1
8 min
Tutorial
Этот текст предназначен для тех, кто только осваивает программирование. Основная идея в том, чтобы показать этап за этапом, как можно самостоятельно сделать игру à la Wolfenstein 3D. Внимание, я совершенно не собираюсь соревноваться с Кармаком, он гений и его код прекрасен. Я же целюсь совсем в другое место: я использую огромную вычислительную мощность современных компьютеров для того, чтобы студенты могли создавать забавные проекты за несколько дней, не погрязая в дебрях оптимизации. Я специально пишу медленный код, так как он существенно короче и просто понятнее. Кармак пишет 0x5f3759df, я же пишу 1/sqrt(x). Мы преследуем разные цели.
Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.
Простыня получилась длинная, поэтому я разбил текст на две части:
Выполнение кода из моего репозитория выглядит вот так:
Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.
Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.
Простыня получилась длинная, поэтому я разбил текст на две части:
- Часть первая: отрисовка стен
- Часть вторая: населяем наш мир + оконный интерфейс
Выполнение кода из моего репозитория выглядит вот так:
Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.
Книги, о которых редко говорят
4 min
Дал ему подборку книг, он приходит месяца через два, и с порога такой сразу:
— Я с друзьями не могу разговаривать.
— Ну да есть такой, недостаточек.
интервью Жака Фреско