Поиск в лабиринте Pacman

Question

В настоящее время я создаю программу, которая ест всю еду в лабиринте pacman. Однако моя программа вызывается каждый раз, когда Pacman делает новый ход, поэтому память не будет сохранена, когда программа закончится, и она вернет только движение: L, R, U или Down. Я новичок в AI, а также новичок в программировании на Java. Я знаю, что от поиска в Google, что лучший способ сделать это с BFS. Вопрос в следующем: как мне это сделать? Должен ли я создавать LinkedList для каждой позиции, которую я посещаю, содержащей путь, который меня туда привел? Пример: UULLDDLRRL.

Еще одно сомнение, что у меня есть, как я могу сделать pacman для поиска ближайшей пищи?

вот мой код, я удалил входную часть кода, что не имеет значения для моего вопроса. Я сохраняю карту из Pacman на char [] [].

class position{ 
    int pX=0; 
    int pY=0; 
    char direction; 
    Boolean visited = false; 


position(int pY, int pX, char direcao,Boolean visited) 
{ 
    this.pX=pX; 
    this.pY=pY; 
    this.direcao=direction; 
    this.direction=direction; 
} 

position() 
{ 
    pX=0; 
    pY=0; 
    direction='N'; 
    visited=false; 
} 

}

position current = new position(pacmany,pacmanx,'N',false); 
    LinkedList<position> analise = new LinkedList<position>(); 

    analise.addLast(current); 

    while(!analise.isEmpty()) 
    { 
     if(m[current.pY-1][current.pX]!='#') 
     { 
      analise.addLast(new position(current.pY-1,current.pX,'U',false)); 
     } 

     if(m[current.pY][current.pX+1]!='#') 
     { 
      analise.addLast(new position(current.pY,current.pX+1,'R',false)); 
     } 

     if(m[current.pY+1][current.pX]!='#') 
     { 
      analise.addLast(new position(current.pY+1,current.pX,'D',false)); 
     } 

     if(m[current.pY][current.pX-1]!='#') 
     { 
      analise.addLast(new position(current.pY,current.pX-1,'L',false)); 
     } 

     analise.get(i).visited=true; 
     current=analise.get(i); 
     analise.remove(); 
    } 

    } 

} 

Answer 1

Есть много проблем, которые вы должны иметь дело с небольшим примером является «цикл проверки» функциональность.

Loop Check
Как вы знаете, если ваш лабиринт содержит цикл? Например, ваше приложение может найти петлю в лабиринте и никогда не прекратится или займет слишком много времени, чтобы найти путь к тому, что на вашем компьютере закончится память.

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

В общем, немного сложно начать кодирование проблемы поиска, когда вы новичок в ИИ и кодировании. Но это не значит сдаться. Но вы должны начать читать некоторые книги, чтобы сначала понять концепцию Graph Theory, а затем разные Graph Traversal Algorithms (i.e BFS, DFS, A-Star и т. Д.), И тогда вы обнаружите, что ваше мышление становится легче.

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

Я нашел (а) полезный ресурс, чтобы играть с here.

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

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