#pragma config(Sensor, S1, lightSensorL, sensorLightActive)
#pragma config(Sensor, S2, lightSensorR, sensorLightActive)
#pragma config(Sensor, S3, lightSensorF, sensorLightActive)
long left , право, прямо;
int doneL, doneR, goS, track

Сокобан — классическая игра, придуманная в Японии. Первоначальная версия игры была написана Хироюки Имабаяши, победившим в конкурсе по программированию в 1980 году.

Термин Sokoban означает «смотритель магазина» (по-английски «смотритель склада»), и это одна из самых любимых логических игр, конкретные уровни которой создаются сегодня.

Цель игры Sokoban - переносить ящики в указанную область, толкая их. Пользователь управляет передвижением Сокобана. Он может двигаться вверх, вниз, влево и вправо, не может проходить сквозь стены. Может одновременно только толкать коробку (не может стрелять).

Чтобы решить игру, все ящики должны быть перенесены в целевые области. Кажется простым, но в каком-то маленьком лабиринте могут возникнуть очень сложные проблемы. Поиск решения может занять часы или дни.

Сокобан обладает некоторыми важными свойствами. Например, перемещение ящиков в целевые области не означает, что у нас есть решение. В некоторых случаях для достижения решения могут быть предприняты неинтуитивные движения. Порядок толкания ящиков всегда важен. Иногда удаление ящиков из целевой области происходит дальше, хотя сначала толкать блоки в целевых областях довольно просто, последний блок или даже Сокобан нельзя было удерживать для завершения игры.

Проблема Сокобана:

Нам нужно было найти путь для решения игры Сокобан и протестировать путь с помощью созданного нами робота.

Сначала мы поговорим об особенностях робота, затем об алгоритме перемещения робота, а после этого попытаемся найти решение этой проблемы, используя знания ИИ.

Описание робота

Требования:

Робот должен решить игру Sokoban. Эта игра представлена ​​​​черной линией на белом полу и некоторыми банками, которые представляют собой бриллианты. Чтобы разрешить Сокобан, робот должен:

-Движение по карте
-Толкать бриллианты
-Читать свое положение

1 Перемещение по карте:

Чтобы дать роботу возможность двигаться, были использованы два серводвигателя Lego, по одному на каждую сторону.

Каждый двигатель имеет встроенный датчик вращения. Это позволяет точно контролировать движения робота. Датчик вращения измеряет обороты двигателя в градусах или полных оборотах [точность +/- один градус]. Один оборот равен 360 градусам, поэтому, если настроить двигатель на поворот на 180 градусов, его выходной вал сделает пол-оборота.

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

2 бриллианта Push:

Основная цель робота — подтолкнуть алмаз в нужное место. Робот может просто толкать бриллианты, он не может их удерживать или поворачивать. Просто нужно было что-то, чтобы держать бриллианты перед роботом. Поэтому мы просто добавили несколько деталей Lego перед роботом.

3 Прочитайте его позицию:

Робот должен знать, где он находится на карте, чтобы обнаружить линию, следовать за ней, обнаружить пересечения. Для этого ему нужен датчик освещенности, как показано ниже. Он позволяет роботу различать светлое и темное, а также определять интенсивность света в помещении или интенсивность света разных цветов. Но его просто использовали для определения разницы между темной линией и белым полом. Чтобы следовать линии, было решено поставить три датчика рядом, в один ряд.

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

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

Для того, чтобы всем этим управлять, роботу нужен «мозг». Вот почему используется NXT Intelligent Brick.

NXT — это 32-битный микропроцессор с флэш-памятью. Он был запрограммирован с использованием языка NXC (не совсем C) и программного обеспечения «ROBOTC for Mindstorms» в качестве среды.

Могу сказать, что только робот был очень своеобразным. Мы использовали цепь для перемещения колес. Конструкция робота была нетяжелой, но прочной, и снять белый кирпичик NXT было очень легко. Точка массы находилась в центре, между двумя моторами и очень близко к полу, поэтому робот был очень устойчивым и мог двигаться быстрее.

Ниже представлен окончательный вариант конструкции робота.

Анализ конструкции:

Сначала о преимуществах конструкции, а затем о недостатках.

Первое преимущество робота касается подвижности. Я построил привод на 4 колеса, каждая сторона которого независима от другой. Таким образом, он может повернуться одной стороной в одну сторону, а другой стороной в противоположную, чтобы повернуться быстрее. Для этого было две возможности. Первый — сделать гусеничную машину наподобие танка, но такое решение вредит скорости робота, поэтому было решено использовать настоящие шины с цепью для передачи мощности на колеса. Второе преимущество этой конструкции заключается в использовании большей конструкции, чем более высокой, чтобы повысить устойчивость при повороте. Третьим преимуществом робота является его прочность, постройте прочную конструкцию, чтобы избежать каких-либо проблем. Одним словом, резюмируя эти преимущества, маневренность.

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

Так что у него был риск ударить банку, робот взял банку и ударил ее.

Кроме того, поверхность не была гладкой из-за черной ленты на полу.

Вторая проблема была связана с датчиками, которые использовали три датчика рядом друг с другом, поэтому у них была проблема остановить робота в нужном положении, чтобы покинуть банку. Три датчика использовались для навигации.

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

Этап тестирования:

Чтобы улучшить робота, мы провели простой тест.

1. Прочность:
2. Значение датчиков
3. Значение скорости двигателей

Надежность:

Мы провели простой тест на устойчивость к шоку, уронив конструкцию робота (без блока NXT из-за цены) на расстояние 1 метр. Робот прошел это испытание.

Значение датчиков:

Это значение является причиной многих проблем с переносимостью. Потому что робот хорошо работал с белым полом и черной линией, но не так с темной линией на сером полу. Во-первых, значение было равно 45%, и это значение уменьшалось до тех пор, пока не было достигнуто хорошее соотношение между переносимостью и производительностью со значением 31.

Значение скорости двигателей:

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

Вклад робота:

С помощью legoNXT мы создали робота, способного решить проблему Сокобан. Это было интересно, потому что мы занимались не только программированием, но и конструировали робота.

Управление роботом:

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

· «s» -› Идти прямо
· «b» -› Вернуться назад
· «l» -› Повернуть на 90° влево
· «r» -› Повернуть на 90° налево справа
· «f» -› оставить ромб

Робот получает строку для программы ИИ, которая дает ему все эти действия. Вот пример строки:
{'l','s','r','s','s','r','s','s','s',' с','с','с','б','б','ф'};

Идея матрицы:

А пока мы нашли очень полезную идею, которую постараемся кратко описать. Если бы у нас было больше времени, мы бы использовали его, но, конечно, с некоторыми улучшениями.

Поскольку мы впервые столкнулись с проблемой соединения программного обеспечения с железом, мы ничего не знали об интерфейсе и о том, как робот должен общаться со второй программой. Это может быть своего рода строка, вид или матрица. Сначала мы решили использовать второе решение, но это было неправильное решение. Мы забыли о старой пословице: самые простые решения всегда самые лучшие…

Так почему для меня эта матрица была лучше для передачи команд роботу, чем простая строка?

Мы подумали, что будет проще реализовать что-то вроде одного оператора цикла while, и робот будет следовать до ближайшего числа. Но мы не знали, что без какой-либо коллекции это будет очень тяжело сделать.

В идеале среднее решение игры Сокобан должно иметь около 160, но не более 200 перемещений с использованием карты аналогичного размера. Робот должен был следовать пути ниже:

Итак, давайте поставим несколько цифр, которые укажут путь. Все числа будут увеличиваться после каждого движения. Таким образом, первый кирпич будет начинаться с 0, второй — с 1, один после второго — с 2 и… как в этом шаблоне, он должен быть только розового цвета:

После каждого движения мы уменьшали все числа на 1:

Ситуация повторяется каждое следующее движение. Конечно, если бы я хотел вернуться назад, мы бы просто добавили ко всем числам плюс 1. После каждого движения мы просто ищем ближайшее число, в данном случае это 1 цифра. Мы пытались разработать это решение, но столкнулись с некоторыми проблемами. Например, первым было: что случилось с пересечением одной строки:

А как насчет этого кирпича 1/15? Мы разработали его, создав каждый узел для одной ячейки, и каждый узел имеет набор чисел. Это было очень трудоемким решением, но оно сработало. Мы создали почти всю программу с этим трюком. Проблема началась с передачи его этому роботу. Поэтому было решено использовать простую строку и счетчик, указывающий на текущий символ строки. Как передать коллекцию роботу? К сожалению, мы не могли использовать сериализацию или что-то в этом роде. Мы могли бы создать коллекцию, но было проще использовать указанную выше строку. Это была первая проблема, с которой мы столкнулись. Алгоритм был такой:

1. найти решение (часть ИИ, выполняется вручную)
2. определить начальную точку и конечную точку решения
3. заполнить числами (часть ИИ, выполнить вручную)
4. проверить, существует ближайший
5. если нет, выйти, пока
6. проверить, является ли ближайший последний последним
7. если да, выйти, пока
8. если нет, перейти к ближайший и обновить позицию и уменьшить числа

Реализация:

Было решено работать с одной основной задачей, которая считывает строку символов и указывает действие, которое должен выполнить робот. Для этого мы добавили семь функций:

Нам нужно было определить значение для датчиков, чтобы отличить черную линию от белого пола. Это значение в процентах. Во-первых, мы поставили 45%, потому что это работало с настоящим белым полом. Но проблема была в том, что пол был не совсем белым, а серым. Итак, мы решили изменить это значение на 31%, и оно сработало лучше.

Вы можете увидеть весь код с комментариями в конце этого отчета.

Вывод:

Было проведено много тестов, чтобы улучшить этот код и компоненты, добавленные в робота, чтобы сделать его достаточно эффективным. У нас была проблема с функциональностью датчиков, потому что они работали на белом полу, но при попытке на сером полу возникла проблема. Так что, если бы было больше времени. мы могли бы сосредоточиться на улучшении этой функции. Мы также будем использовать предварительно скомпилированные инструкции C, например #DEFINE LIGHT_LEVEL 48.

A*

Поэтому было принято решение использовать алгоритм A* для перемещения робота из точки в точку. Некоторые части алгоритма были изменены, в основном связанные с отображением результата.

Во-первых, мы использовали манхэттенский тип определения расстояния между текущей точкой и целевой точкой, мы изменили его после на a2+b2=c2, позже мы использовали оба с модификацией, а после этого ушли на манхэттенский способ. Почему? Потому что решение имело наименьшее количество поворотов.

Это реализованный алгоритм A*:

Добавить стартовый узел в список открытых узлов

Повторение:

1 Найдите наивысшее f в списке открытых узлов.
2 Текущий узел = наивысшему узлу f
3. Добавьте Текущий узел в список закрытых узлов
4 Для всех соседей текущего узла мы сделать:
а. Если это стена или что-то в этом роде или оно находится в закрытом списке, я его игнорирую
б. Если соседа нет в списке открытых узлов, я добавляю его. Текущий узел будет родительским и вычислит F, G и H
c. Если сосед уже был в открытом списке, он проверяет, не короче ли путь, ведущий к этому узлу. Это делается путем проверки только G. Чем меньше G, тем лучше путь. Если он короче, мы меняем родительский узел на этот текущий узел и снова вычисляем G и F. Если открытый список был отсортирован по критерию F, его нужно было отсортировать еще раз.

5. Остановитесь, если:
а. Если путь назначения добавлен в список закрытых узлов. Это означает, что путь найден
b. Если открытые узлы списка пусты. Путь не найден.

6. Сохраните путь.

Иногда слова усложняли вопрос, поэтому, если вы посмотрите на картинку ниже:

Как видите, это простой алгоритм A*. Внесены некоторые изменения, особенно способ поиска соседей и некоторые изменения с отображением пути. Было создано приложение Windows Form. Вот несколько картинок, первая — интерфейса, вторая — примера:

Робот путешествует из точки в точку и старается избегать кирпичей. Мы создали своего рода индикатор выполнения, чтобы видеть ход расчета. Если бы мы хотели использовать решение только между точками, нам просто нужно было поставить галочку «между точками». Если мы хотели найти решение всей игры Сокобан, нам нужно было нажать «Вся игра», а затем «Решить». Кнопка шага предназначена для отображения матрицы после каждого движения, которое используется для расчета Manhattan Way Calculation. Этот расчет имеет наименьшее количество поворотов, но тогда мы не думали, что это лучшая идея. Мы могли бы использовать просто a2+b2=c2 и улучшить эвристическую функцию, например, она будет возвращать меньшее значение, если следующим шагом будет поворот.

В первую очередь надо было решить проблему с банкой: Как повернуть с банкой? Для этого был изменен алгоритм A*. Действие добавлено к каждому узлу, наименьшему направлению движения. Если предыдущая была другой, текущая запускала новую рекурсию с алгоритмом A*. В новую рекурсию передавались точки в зависимости от направления робота, например, если это был север и было бы неплохо повернуть налево, начальная и конечная точки показаны ниже.

У нас было две матрицы, одна для решения робота, вторая для поиска пути. Каждая ячейка в матрице имеет некоторое значение, которое равно G.

Мы создали парсер для сохранения строки. Мы дошли до этой точки решения Сокобана и не знали, зачем был создан своеобразный мост, мы могли его пройти, но об этом ниже. Все описание вы можете увидеть на этих картинках:

Если робот не мог оттолкнуться с одной стороны, например, в данном случае справа, он просто отметил путь 0 с одной матрицей или с меньшими числами, и алгоритм должен начаться заново. Мы пометили нулями, чтобы больше не использовать то же самое.

Барьер и мост

Барьер был найден после того, как реализовал алгоритм * и начал думать об планировщике ИИ. Решение для этого алгоритма описано ниже.

Планировщик ИИ

Во-первых, мы понятия не имели, как ее решить. Мы пробовали с алгоритмом брутальной силы, но с 1 ГБ оперативной памяти Fujitsu Siemens Amilo это было невозможно. Позже мы нашли идею, которая на самом деле не была решением ИИ, но она была немного ближе, просто лучше, чем грубая сила. Это означает: найти ближайшую и перейти к самой короткой дыре. Это было не очень хорошо, и поэтому нашел что-то вроде этого:

Алгоритм ИИ с A*. Внутри цикла нужно найти лучший путь от точки к точке, снаружи определить, какие точки следует выбирать. Внутренний алгоритм был описан выше, давайте поговорим о внешнем A*.

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

Как определить каждый узел в древовидном решении, что такое начальная точка (корень) и что такое узел конечной точки. Это была настоящая проблема. A * также имеет дерево, каждый узел которого является позицией в матрице. Начальный узел — это позиция робота, а цель — точка назначения. В основном цикле while он проверяет с помощью эвристики, какой узел следует выбрать, а какой можно выбрать. Узел во внешнем алгоритме X должен быть похож на узел A*. Следующая проблема заключалась в том, что мы не могли определить узел после 5 или 6 движений, потому что мы могли потерять пять или шесть движений, которые могли быть необходимы для решения своего рода доски. Он должен был подтолкнуть какой-то алмаз в положение, совершенно не связанное с их пунктами назначения, но без этого решение карты было бы невозможным. Если бы он проталкивал до дыр только алмазы, мы не смогли бы решить проблему. Именно поэтому мы изменили идею использовать только один алгоритм ИИ.

Предполагаемые данные:

· Узлом было состояние матрицы,
· Корнем была матрица с начальной позицией робота,
· Целевым корнем была позиция матрицы со всеми ромбами в их отверстиях.
· Эвристическая функция:
> d-расстояние между ромбами до их отверстий при следующем движении.
c-Если ромбы перемещаются до своих отверстий при следующем движении, добавьте «с».
m-расстояние от робота до первого ромба.

F = 0.6d + 0.1c + 0.3m.

· Старайтесь выбирать наименьшее F
· Алгоритм подобен упомянутому ранее A*, он имеет открытый список, закрытый список…
· Алгоритм создает своего рода дерево решений
· Дерево физически реализован в виде связанного списка или древовидной коллекции в .NET 3.5
· Узел добавляется после каждого перехода к следующему блоку
· Если алгоритм не может добавить узел, он поднимается на один узел вверх и проверяет, является ли он возможно, как и в обычном A* (список открытых и закрытых узлов)

Во-первых, проверяются соседи текущей точки на карте (начальное положение робота). Его нашли с ближайшим F соседей. Новый текущий узел — это тот, который только что был найден. Новый узел также имеет указатель (ссылку) на своего родителя. Это новый узел, отмеченный в дереве как «а». Итак, теперь снова нашел новую хорошую точку. Это «с». «с» также относится к «а». Имейте в виду, что каждый узел является состоянием матрицы. Еще один новый и его «е». К сожалению, он не мог больше толкнуть алмаз из-за стены, потому что он был в углу, причин может быть много. Но это не проблема. Он просто перемещается к родительскому узлу и снова пытается найти что-нибудь интересное. Но важно не проверять еще раз узел «е», потому что он находится в закрытом списке. Ситуация повторяется постоянно. Эвристическая функция вернет терку F, если она переместит алмаз в отверстие на следующем шаге. Конечно, не так важно передвинуть только один ромб, как найти завершенное решение задачи. Поэтому умножается на 0,1. После создания каждого узла я просто проверяю, совпадает ли он с целью назначения. Если это так, он прерывает оператор цикла while, а если нет, попробуйте снова выполнить поиск. Если было много ромбов и маленькая карта, то дерево будет скорее глубоко, чем широко. Если это была большая карта, но количество бриллиантов будет маленьким, то дерево будет не очень глубоким. Используя такой алгоритм, создается от 200 000 до 500 000 узлов. Некоторые изменения, сделанные в балансе с помощью эвристической функции, поэтому количество узлов действительно связано с эвристической функцией. Поэтому очень важно найти хорошие критерии в этой функции и, в данном случае, хороший баланс между c, d и m. Это небольшое введение было планировщиком ИИ. Алгоритм такой же, как и для A*, описанного в первой главе. Только определение узла будет другим. Узел не будет содержать позиции x и y, а только матричное состояние. В настоящее время не используется алгоритм A* для определения пути, другой может повернуться. Все реализовано в этом A*подобном алгоритме.

Вторая программа:

В этой реализации есть три основных класса.

· Карта — этот класс представляет карту.

· Узел — этот класс представляет каждую плитку на карте. Он имеет два основных метода.

o CompareTo — этот метод позволяет мне решить, какой узел лучше. Мы могли бы сказать, что текущий узел лучше, если этот метод возвращает отрицательное число, что означает, что текущий узел имеет более низкую стоимость, чем другой сравниваемый узел.

o isMatch — это позволяет мне решить, совпадают ли геометрические положения двух узлов или нет.

· SortedCostNodeList — это список, в котором хранится список объектов Node. Нам нужно было выбрать узел с наименьшей стоимостью из списка, поэтому этот список реализован как отсортированный список по значению стоимости узла, и нам не нужно проверять стоимость всех элементов в списке каждый раз, чтобы вытолкнуть узел с наименьшей стоимостью, поскольку они уже были отсортированы. Просто поп один. Этот список имеет два основных метода.

o push — добавить элементы узла в список в правильном порядке позиций по стоимости узла.

o Метод узла CompareTo используется внутри для сортировки по стоимости.

o pop — просто возвращает узел с наименьшей стоимостью из списка и удаляет его из списка.

Описание каждого класса кода A*:

Приступим к описанию кода. Как только это будет сочтено полезным, в него будут добавлены комментарии о том, что нужно изменить, чтобы решить всю игру Sokoban. Первым в списке стоит Diamond Class. Этот класс использовался не очень часто. Это было связано с упомянутым выше матричным решением.

Теперь он сохраняет положение ромбов и отверстий. Поскольку это .NET, я определил несколько сеттеров и геттеров.

Карта классов очень важна, использовал ее очень часто. Этот класс используется каждый раз, когда алгоритм вносит небольшие изменения в движения. В программе две матрицы. Один, чтобы показать пользователю ситуацию, каждый раз, когда нужно было что-то показать матрице платы. А второй переписывает все из матрицы решения mapdata. Было решено использовать его, потому что картографические данные содержат только цифры, а с цифрами проще использовать A*. Мягко говоря, сначала он сохраняет только G (F=G+H), но G из ближайшего соседа Функция InitMap просто инициализирует mapdata. Функция GetMap возвращает верхнее и нижнее измерения матрицы. PrintSolution необходим для отображения решения.

Теперь главный важный Node Class. Поскольку это A*, дерево обновляется при каждом следующем движении. Сначала была мысль о структуре (нужно меньше памяти, чтобы держать один узел в дереве). Из-за проблем с реализацией было решено использовать объект в качестве узла. Дерево состоит из узлов. На первом этапе проекта у него есть только тот код, который указан ранее. Позже он превратился в планировщик ИИ. Некоторые функции действительно говорят то, что они делают. Например, totalCost возвращает стоимость перемещения (G+H), а общедоступные переменные представляют эту стоимость. Переменный ромб выхода связан с роботом. Он говорит, покидает ли он в этом движении алмаз. Проще говоря, это связано с той частью программы, которая создает парсер строк с командами, которые будут у робота. Переменные parent и _goalNode используются при каждом последующем движении. Во время каждого движения проверяется, совпадает ли текущий узел с _goalNode. Если да, значит, решение найдено. Parent используется для сохранения родительского узла текущего узла. Каждый узел без первого (корневого) имеет родительский узел. Функция InitNode просто вычисляет стоимость G и H для каждого узла. CompareTo возвращает cFactor, используемый в эвристике.

IsMatch означает, что объект соответствует второму. Последняя, ​​но не менее важная функция — GetSuccessors. Он добавляет соседей преемника к каждой позиции. Мы могли бы использовать этот класс узла с планировщиком ИИ и изменить только представление состояния. Теперь это позиция робота, но это должно быть матричное представление. Класс NodeComparer используется для сравнения узлов в дереве. У него есть только одна функция для сравнения объектов, возвращается их отрицательное действие. Программа класса связана с платформой .NET. Это не будет описано здесь. Он генерируется автоматически. Та же ситуация и с разделяемым классом Form1.

RoadSolver — действительно важный класс. Это алгоритм A* для перемещения от точки к точке. Мы могли бы использовать этот класс и как планировщик ИИ, но класс Node немного изменился. Это должно быть представлено не только как положение робота, а как все матрицы - это изменение. Кроме того, если необходимо использовать его в качестве планировщика ИИ, необходимо определить начальный и целевой узлы по-разному.

Сначала загружается карта, после этого идет определение старта и цели узла. Когда первый узел нажимается, запускается обычный a*. После цикла while, который следует от родительского узла к начальному узлу. Вы видите, что это инверсия, поэтому, чтобы избежать этой проблемы, он помещал каждый узел в стек.

После этого его нужно было вытолкнуть в правильном порядке. Если он не может следовать из конечного узла в начальный, он не нашел решения. 5 будет возвращено. Пожалуйста, имейте в виду, что некоторые функции в классах являются статическими. Так что не нужно говорить об объекте. Этот класс является статическим. Так что он был создан только для того, чтобы разделить код на маленькие части. Был доступен объект решателя дорог. В конце вы можете увидеть парсер. Как было сказано выше, узел имеет только действие движения. Посмотрите на пример ниже:

РРЛЛ: Это означает, что нужно сделать один шаг вправо, снова вправо, затем влево и снова влево. Но робот не может этого сделать. У него должна быть переменная, связанная с ориентацией, и синтаксический анализатор должен изменить строку на.

RSRRSS: Результат этого действия тот же: поверните направо, идите прямо, поверните (просто поверните на раз) и пройдите два раза прямо.

Последний класс SortedCostNodeList. Он выбрал наименьшее значение F на следующем шаге в a*. Тогда у него был своего рода открытый и закрытый список узлов. Это тот класс. Он имеет функции push, pop, index и remove at для выполнения основных операций со списком.

В основном это описано в коде a*. На самом деле планировщик ИИ не закончен из-за ограниченного времени проекта. Поэтому было решено поставить рабочий код файла *. AI планировщик кода сделан с некоторыми изменениями:

1. Изменен узел класса. В матрице узла хранились не только x и y
2. Начальный и целевой узлы разные, пришлось создать начальную и точечную матрицу и во время приложения сравнить, похожа ли матрица в узле на целевую. Таким образом, это была та же самая идея сравнения узла, как сейчас
3. GetAccessors() немного отличалась, потому что добавляла всю матрицу, которая есть внутри узла, но в основном это было различие с узел, но не с этой функцией
4. Все внутри оператора RoadSolverif следует удалить:
if (tempPrevious!= null && tempPrevious.action!=null) 5. Парсер строк будет другим, потому что мы нажимаем узел с матричным состоянием
6. Вот и все, потому что это нормально a*, нужно было просто определить другое состояние, в основном говоря Node.

Исходный код NXT:

Код классов:

Искусственный интеллект-Sokoban Game

Сокобан — классическая игра, придуманная в Японии. Первоначальная версия игры была написана Хироюки Имабаяши, выигравшим её с…