User
Простое объяснение алгоритмов поиска пути и A*
Часть 1. Общий алгоритм поиска
Введение
Поиск пути — это одна из тех тем, которые обычно представляют самые большие сложности для разработчиков игр. Особенно плохо люди понимают алгоритм A*, и многим кажется, что это какая-то непостижимая магия.
Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.
Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.
ChatGPT клиент для MS-DOS
Благодаря стараниям ретро энтузиаста 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: продолжение
Изучаем устройство OLED-экрана SSD1306 и дорабатываем звуковые индикаторы музыкального плеера PSG-файлов на чипе AY-3-8910.
Реализация алгоритма Дейкстры на C#
Введение
Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке 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
Код
Наконец, рассмотрим сам код. В каждом классе написал подробные комментарии.
Обзор и оживление «японского пенька»
Всем привет! Сегодня хотелось бы рассказать про реликвию, с которой началось мое настоящее знакомство с компьютерами, — ноутбук Fujitsu Lifebook 634Tx 1998 года выпуска.
Только не надо записывать меня в счастливчики и «мажоры»: девайс принадлежал моему старшему (на 13 лет) брату, мне же, тогда школьнику, иногда перепадала возможность посидеть за ноутбуком и погонять монстров в Doom.
Прошло больше 20 лет. Копаясь на антресолях в бабушкиной квартире, я случайно наткнулся на этот артефакт. Получил от брата разрешение на любые манипуляции и решил оживить и заодно обозреть. Ну, приступим.
MenuetOS, которая умещается на дискете, снова обновилась: что «выросло» в новой версии
Некоторые читатели Хабра, вероятно, дискет и в руках не держали, поскольку те вышли из обращения много лет назад. Но ряд современных программ и «железа» всё ещё с ними связан. Например, проект MenuetOS представляет собой операционную систему, которая умещается как раз на дискете. Дело в том, что написана она на ассемблере, а команда разработчиков заботится о приемлемом соотношении объём/функциональность. Насколько можно судить, получается у них всё это весьма неплохо. Подробности о новинке — под катом.
Челлендж по обработке миллиарда строк на Go: от 1 минуты 45 секунд до 4 секунд
Пару недель назад я прочитал о запавшем мне в душу челлендже по обработке миллиарда строк, поэтому захотел решить его на Go.
Я немного опоздал, соревнования проводились в январе. И на Java. Меня не особо интересует Java, зато давно интересует оптимизация кода на Go.
Этот челлендж был очень прост: обработать текстовый файл названий метеорологических станций и температур, и для каждой станции вывести минимальное, среднее и максимальное значение. Чтобы упростить задачу, было ещё несколько ограничений, однако я проигнорировал те, что относятся только к Java.
Собираем самодельный перьевой плоттер
В этой статье задокументированы уроки, полученные мной при проектировании и создании самодельного перьевого плоттера летом 2023 года.
Моей конечной целью было создание собственного станка с программным управлением, и перьевой плоттер показался мне хорошим промежуточным шагом в этом направлении. Это важный контекст в проектировании этого устройства, потому что если бы мне просто нужен был перьевой плоттер, то многое можно было бы упростить.
Замена CCFL подсветки на светодиодную. На примере информационного дисплея Mitsubishi L200/Pajero Sport II
Приветствую, Хабр!
Снова хочу предложить Вашему вниманию статью по ремонту электроники. Несколько лет назад знакомый попросил меня отремонтировать подсветку информационного дисплея на Mitsubishi L200. Позже он пересел на Pajero Sport II и вернулся с той же проблемой уже на этом автомобиле. В прошлый раз я забыл сделать для себя пометки по ремонту и пришлось разбираться заново. Идея замены ламп CCFL на светодиоды лежит на поверхности, и я уже не раз менял подсветку таким образом в стареньких, но еще вполне приличных, телевизорах и мониторах.
Векторизация изображений. Как создать алгоритм поиска похожих изображений на Python
Многочисленные исследования ученых доказывают, что около 90% информации человек воспринимает через зрение. Изображения являются одним из самых богатых источников информации, которую можно использовать для разнообразных задач, включая классификацию, детекцию объектов, ранжирование изображений, поиск по изображениям и генерацию текстовых описаний.
Все перечисленные выше задачи сегодня реализуются с применением машинного и глубокого обучения. Однако для эффективной обработки изображений необходимо иметь их числовое представление, так как модели машинного обучения способны воспринимать только его.
В мире есть много вещей, которые интуитивно понятны и очевидны для нас. Например, если перед нами два похожих цветка, мы можем определить их принадлежность одному виду, даже не зная названий этих растений. Этот навык позволяет нам распознавать объекты и определять их в группы. Разумеется, подобные алгоритмы уже давно существуют в современных поисковиках Google, Яндекс и прочих. Но что, если вы проектируете обособленную систему с собственной базой изображений одной или нескольких конкретных тематик и вам необходим функционал поиска похожих изображений?
В этой статье мы сосредоточим ваше внимание на том, как построить подобный алгоритм на Python, а также расскажем о компьютерном зрении и эмбеддинге изображения.
Введение в программирование: простой 3D-шутер с нуля за выходные, часть 1
Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.
Простыня получилась длинная, поэтому я разбил текст на две части:
- Часть первая: отрисовка стен
- Часть вторая: населяем наш мир + оконный интерфейс
Выполнение кода из моего репозитория выглядит вот так:
Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.
Книги, о которых редко говорят
Дал ему подборку книг, он приходит месяца через два, и с порога такой сразу:
— Я с друзьями не могу разговаривать.
— Ну да есть такой, недостаточек.
интервью Жака Фреско
Восстановление данных с M.2 NVMe SSD. Скрипт ddrescue-loop v0.2
Речь пойдет о способе извлечения данных с неисправного SSD для случаев когда после попытки чтения любого сбойного сектора - SSD совсем перестает отдавать данные и помогает только отключение включение питания.
Представляю доработанную версию скрипта ddrescue-loop с поддержкой управления USB реле и uhubctl.
Для прерывания питания SSD задействовал простое и дешевое решение USB Relay Module LCUS-1 CH340 которые доступны на Aliexpress. И подключение через док станцию AgeStar 31CBNV1C на основе USB-NVMe моста JMicron JMS583.
Рассмотрим процесс восстановления на примере случая с неисправными M.2 NVMe SSD производства Kimtigo на контроллере Maxio MAP1202.
«Самоидентификация» клавиатуры
«Я — русский!»‑ спел недавно известный певец. Да и я, после 20 лет пользования клавиатурой, наконец‑то, устал вечно поправлять текст, набранный не в той раскладке клавиатуры (в голове держать всё невозможно!) и сделал индикацию текущей раскладки. Казалось бы, мелочь, а приятно.
А раньше как бывало? Оторвал взгляд от клавы, посмотрел на экран… «Фу, чёрт! Не та раскладка!» Стираешь то, что набрал непосильным трудом и заново набираешь тот же текст.
Вы скажете: «Не интересное решение! Есть же замечательная программа Punto Switcher! Она может автоматически исправлять набранный текст в нужную раскладку.» Но всегда оставалась проблема набрать специальные символы независимо от языка ввода. И вот тут‑то Punto Switcher начинал ошибаться.
А нельзя ли поставить прямо возле клавиш небольшой экранчик OLED (благо таких стало в продаже много) и выводить на него текстом текущую раскладку аж по всем языкам мира? Можно. Но как показал мой дальнейший опыт, увидеть свечение боковым взглядом проще, чем вглядываться в надпись на экранчике. Кроме того, обычно мало кто пользуется одновременно более чем тремя языками раскладки. Да и по цене решение со свечением светодиодами будет гораздо дешевле.
Вот я так и пошёл по этому простому пути. И замутил банальную схему:
Простой индикатор раскладки клавиатуры в курсоре на С++
«Галоп пикселя — часть шестая» — Анимация персонажей. Бег
«Галоп пикселя», часть I — базовые понятия, этапы взросления, прикладные упражнения (линк)
«Галоп пикселя», часть II — перспектива, цвет, анатомия и прикладные упражнения (линк)
«Галоп пикселя», часть III — Анимация (линк)
«Галоп пикселя», часть IV — Анимация света и тени (линк)
«Галоп пикселя», часть V — Анимация персонажей. Ходьба (линк)
«Галоп пикселя», часть VI — Анимация персонажей. Бег (линк)
Доброго времени суток, Хабр. Мы продолжаем цикл «Галоп Пикселя». И хотя паузы между главами этой саги достигли практически четырехлетнего перерыва — я рад (надеюсь и вы тоже) продолжить двигаться вперёд. Миля за милей, дорога за дорогой, в этой вечной былине о пиксель-арте. Пространном повествовании о пикселях, их жизни, способе их создания, приёмах и уловках в работе с ними.
На этот раз речь пойдёт о создании анимации бега, от истоков малых кадрами и цветами — к ренессансу больших разрешений и буйству цветов. В статье будут разобраны примеры самых разных типов анимаций, будет определена разница между шагом и бегом. Мы затронем как создание игровых ассетов, так и сущности близкие к анимационным заставкам, в простонародье известные как синематики.
Сегодняшняя публикация станет ещё одной вехой, которая могла бы стать финальным аккордом в нашей истории. Но мне думается, что это… скорее окончание базового цикла, но не истории в целом, которую можно продолжать ещё долго. Существует масса неисследованных территорий, нехоженых дорог и мест, куда ещё не ступала нога пытливых археологов от мира любителей пиксель-арта. Лопаты в руки, друзья. Лопаты в руки.
SSP — Собственный алгоритм сжатия изображений без потерь
Алгоритм имеет два режима компресии:
- без потерь – в котором, изображения после декомпресии будет восстановлено с точностью до бита;
- с потерями – который не уменьшает качества картинки, просто в нем непосредственно перед сжатием, изображение переводится палитру YcbCr
Только лишь за счет изменения палитры удается существенно улучшить сжатие. Использую следующие коэффициенты:
cY = 0.30078125 * R + 0.5859375 * G + 0.11328125 * B
cCb = -0.171875 * R - 0.33984375 * G + 0.51171875 * B + 128
cCr = 0.51171875 * R - 0.4296875 * G - 0.08203125 * B + 128
Дизассемблер 6502 (nes/famicom/dendy) на php
Я продолжаю изучать ассемблер 6502, но для экспериментов мне понадобился дизассемблер, Я пробовал использовать da65 собственно тот что идет вместе с ассемблером и линкером ca65 и ld65 соответственно. Но заметив в документации коды команд в hex представление. И вдруг понял что если прочитать файл nes то можно просто взять код инструкции, взять ее длину и спарсить аргумент. И мы получим дизассемблированный код в его простом представление.
Под катом небольшой рассказ о том как я написал скрипт дизассемблера на PHP.
Лучше IBM PC, дешевле Apple. История компьютера Tandy 1000
В одной из своих предыдущих публикаций я рассказал об удивительной истории корпорации Tandy, превратившейся из скромной кожевенной мастерской в известнейшего мирового производителя компьютеров. В комментариях читатели вспомнили и самую успешную модель этой компании — Tandy 1000, персоналку, о которой мечтал маленький Шелдон Купер из «Теории большого взрыва». Об этой необычной машине — сегодняшняя статья.
Information
- Rating
- 699-th
- Location
- Россия
- Registered
- Activity