AI-алгоритм для игры "RaceTrack"

Ответ 1

Я сделал С++-решатель, который слишком длинный (187 строк), чтобы удобно уместиться здесь, поэтому я положил его в pastebin вместо: http://pastebin.com/3G4dfTjR. Программа либо вычисляет оптимальное (минимально возможное количество ходов) решение, либо сообщает, что нет возможности.

Использование

Запустите программу как гоночный трек startX startY цельX цельY [круг X кругY радиус].

Программа предполагает сетку 100x100, которая может опционально содержать одно круговое препятствие, чей центр и радиус вы указываете. Вы должны дополнительно указать начальное местоположение автомобиля и место одной цели. Хотя эти ограничения несколько ограничительны, посмотрите на код, чтобы было очевидно, что они не ограничивают алгоритм в целом - вся соответствующая логика инкапсулирована в подпрограммы isMoveValid() и isGoalState(), поэтому, если кто-то может быть обеспокоены внедрением более общих версий этих подпрограмм (например, позволяя пользователю указывать растровое изображение местоположений сетки и/или разрешать несколько местоположений целей), тогда это может быть включено без труда.

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

Как это работает

Поскольку каждое движение стоит ровно 1, можно использовать ширину первого поиска через пространство состояний 4D, чтобы найти оптимальное решение. Всякий раз, когда мы посещаем заданное состояние s, состоящее из 4-кортежей (x, y, dx, dy), где dx и dy - вектор скорости, который мы использовали для перехода к (x, y), мы рассматриваем все 9 состояний, что мы может достигать от s с одним движением. Для любого такого состояния t, которое еще не было видно, этот путь к t (т.е. Через s) гарантированно оптимален, так как BFS всегда посещает узлы в порядке их минимального расстояния от корня. Всякий раз, когда мы определяем оптимальный путь для состояния, мы записываем состояние предшественника, позволяя отслеживать полный путь, который должен быть создан в конце.

BFS проще и, вероятно, быстрее, чем Dijkstra Algorithm или * search, которые являются более общими алгоритмами, которые позволяют перемещать разные затраты - гибкость, которая нам здесь не нужна. A * может быть быстрее, если есть несколько препятствий для устранения его эвристики, но на каждом шаге ему нужно искать минимальную стоимость node, которая обычно выполняется с использованием кучи, тогда как для BFS минимальная стоимость node всегда доступен в передней части очереди.

Примеры

гоночный трек секундомера 30 3 90 10

Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
No obstacle.
11-step solution:
(90, 10) (dx=10, dy=4)
(80, 6) (dx=9, dy=3)
(71, 3) (dx=8, dy=2)
(63, 1) (dx=7, dy=1)
(56, 0) (dx=6, dy=0)
(50, 0) (dx=5, dy=0)
(45, 0) (dx=5, dy=0)
(40, 0) (dx=4, dy=0)
(36, 0) (dx=3, dy=-1)
(33, 1) (dx=2, dy=-1)
(31, 2) (dx=1, dy=-1)
(30, 3) (dx=0, dy=0)
128113 states were examined in the process.
stopwatch: Terminated. Elapsed time: 343ms
stopwatch: Process completed with exit code 0.

гоночный трек секундомера 30 3 90 10 50 20 25

Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
A circular obstacle of radius 25 is centred at (50, 20).
22-step solution:
(90, 10) (dx=5, dy=-8)
(85, 18) (dx=5, dy=-7)
(80, 25) (dx=4, dy=-6)
(76, 31) (dx=4, dy=-5)
(72, 36) (dx=5, dy=-4)
(67, 40) (dx=6, dy=-3)
(61, 43) (dx=7, dy=-2)
(54, 45) (dx=8, dy=-1)
(46, 46) (dx=7, dy=0)
(39, 46) (dx=6, dy=1)
(33, 45) (dx=5, dy=2)
(28, 43) (dx=4, dy=3)
(24, 40) (dx=3, dy=4)
(21, 36) (dx=2, dy=5)
(19, 31) (dx=1, dy=6)
(18, 25) (dx=0, dy=6)
(18, 19) (dx=-1, dy=5)
(19, 14) (dx=-2, dy=4)
(21, 10) (dx=-3, dy=3)
(24, 7) (dx=-3, dy=2)
(27, 5) (dx=-2, dy=1)
(29, 4) (dx=-1, dy=1)
(30, 3) (dx=0, dy=0)
949565 states were examined in the process.
stopwatch: Terminated. Elapsed time: 3076ms
stopwatch: Process completed with exit code 0.

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

Небольшая ошибка: отправленный код даст короткий (но ненулевой) ответ, если вы установите местоположение цели равным исходному местоположению. Очевидно, это можно было проверить как особый случай, но я уже поставил код на pastebin, когда понял это...:)

Ответ 2

Другие рекомендуют A *, это, вероятно, путь, но проблема с этим подходом. Позвольте мне сначала сказать, что "стоимость" перехода от одного node к другому всегда 1, так как вы хотите минимизировать количество шагов, просто нет других затрат.

Но важным моментом, который я хочу сделать, является то, что местоположение (x, y) не является уникальным node в графе поиска A *! node характеризуется x и y, но также координатами x и y node автомобиль исходит из (или по компонентам скорости vx и vy, если хотите). Таким образом, вы не можете просто пересечь алгоритм A * над двумерной сеткой; он должен быть фактически 4-мерным. Тем не менее, A *, вероятно, все еще остается.

Что касается эвристики, вы можете получить действительно творческий подход к этому, но я предлагаю нечто вроде расстояния до конца минус текущая скорость, где расстояние предварительно рассчитано для каждой точки в обычной двумерной сетке (используйте для этого алгоритм Дейкстры), Это делает алгоритм поиска A * первым в направлении финишной линии и желательно как можно быстрее. Я считаю, что такой алгоритм будет очень хорошо рассчитать весь маршрут сразу.

Одна из проблем заключается в том, что A * всегда будет давать оптимальный маршрут, поэтому ИИ, использующий такой алгоритм, не будет забавой играть против, так как он всегда будет побеждать (при условии, что исходные позиции справедливы).

Ответ 3

До сих пор я не думаю, что кто-то обратился к ключевому моменту вашего вопроса: как вы придумали хорошую "качественную ценность"? В ИИ качество, о котором вы говорите, обычно называется "эвристическим". В идеале, ваш эвристический указатель точно скажет вам минимальное количество ходов, необходимых для достижения финиша, учитывая текущую позицию/скорость. В действительности, мы должны довольствоваться тем, что легче вычислить.

Одним из важных рекомендаций является то, что хорошая эвристика должна быть допустимой; то есть, он никогда не должен переоценивать стоимость достижения цели (в вашем случае количество ходов для достижения финиша). Алгоритм A * зависит от допустимой эвристики.

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

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

Ответ 4

http://www.csc.kth.se/utbildning/kth/kurser/DD143X/dkand11/Group3Johan/report/tarandi_olsson_report.pdf

Этот документ может помочь вам

Ответ 5

Пока он не будет немедленно применим к RaceTrack, вы можете узнать что-то из алгоритма A * path-find. Он использовался во многих играх, чтобы помочь ИИ выяснить, как добраться из точки А в точку Б как можно быстрее.

Ответ 6

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

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

Еще один момент - попытаться предварительно вычислить всю гонку с самого начала. Затем речь идет о минимизации числа оборотов для пересечения финишной линии. Одним удобным алгоритмом поиска минимального значения является имитированный отжиг.

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

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

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

Ответ 7

Я бы предложил начать с решения проблемы. Используйте ретроградный анализ (как, например, в шахматных эндшпилях http://en.wikipedia.org/wiki/Retrograde_analysis), чтобы рассчитывать назад с конца, предполагая, что вы единственный игрок, чтобы посмотреть, как требуется много шагов для пересечения финишной линии, учитывая положение и скорость. Если мое мышление правильное, время его вычисления должно быть линейным по количеству позиций. Должно быть очень быстро.

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

Ответ 8

существует несколько алгоритмов, известных в шахматах, таких как альфа-бета-обрезка, перемещение заказов и т.д. возможно, вам повезло, если вы ищете в шахматном контексте.

alpha beta, strategy

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