Проверить принадлежность точки невыпуклому многоугольнику за линейное время совсем не сложно. Один из самых распространенных методов — выпустить луч и посчитать число точек пересечения. Однако, при этом нужно аккуратно рассматривать случаи, когда точки многоугольника попадают на луч. Отсюда естественно возникает вопрос, как рассмотреть эти случаи проще всего?

DROD — весьма необычная логическая игра. Главные ее особенности:

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

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



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