Pull to refresh
52
0
Send message

Проверка принадлежности точки невыпуклому многоугольнику

Reading time 5 min
Views 37K
Проверить принадлежность точки невыпуклому многоугольнику за линейное время совсем не сложно. Один из самых распространенных методов — выпустить луч и посчитать число точек пересечения. Однако, при этом нужно аккуратно рассматривать случаи, когда точки многоугольника попадают на луч. Отсюда естественно возникает вопрос, как рассмотреть эти случаи проще всего?
Дать волю пефекционизму
Total votes 51: ↑49 and ↓2 +47
Comments 57

Смешанный AI в игре DROD — человек+компьютер=?

Reading time 3 min
Views 1.2K
DROD — весьма необычная логическая игра. Главные ее особенности:
  • Пошаговость. В отличие от supaplex реакция не имеет значения.
  • Детерменированность. Элемент случайности отсуствует, любую позицию можно просчитать в уме, хотя обычно это очень не просто сделать.
  • Большое концептульное разнообразие головоломок. Благодаря этому игра надоедает гораздо медленнее чем, например, судоку.
  • Приключенческий антураж, придающий смысл процессу (в основной миссии мы делаем виртуальный мир DROD чуточку чище).

Головомки состоят в том, чтобы убить всех монстров в комнате 38x32 клетки. Игрок управляет персонажем занимающем 1 клетку, который держит меч, занимающий еще одну из 8 соседних клеток. Каждый ход можно либо пойти на одну из 8 соседних клеток, либо повернуть меч, либо подождать. После чего по очереди ходят оставшиеся в живых монстры. Если они смогут занять клетку, на которой стоит игрок, он проигрывает и возвращается к началу комнаты.

image

Дополнительный интерес к игре придает таблица рекордов скорости (по количеству ходов) прохождения комнат. Она-то и является нашей целью. Но как можно применить компьютер к игре, с концептуально различными головоломками и астрономическим количеством вариантов (в каждый момент у нас 11 вариантов хода, а общее число возможных состояний комнаты на много больше чем в шахматах)?! Выход один — переложить интеллектуальную часть задачи на человека, а рассчетную (оптимизация решения по количеству ходов) — на компьютер.

Читать дальше →
Total votes 18: ↑15 and ↓3 +12
Comments 6

Information

Rating
Does not participate
Date of birth
Registered
Activity