미로를 로봇으로 매핑하는 방법은 무엇입니까?

Question

첫 번째 - 비슷한 질문을 보았지만 문제를 해결하지 못했습니다. 반복이 아닙니다 (희망 사항).
저는 미로를 해결하기로되어있는 Arduino Nano로 로봇을 만들고 프로그래밍하고 있습니다. 그것은 미로의 어딘가에 놓인 다음 아이템을 찾아야합니다. 다음 번에 항목으로 바로 가야합니다 (가장 짧은 길 일 필요는 없지만 막 다른 길은 허용되지 않습니다).
전체 미로를 알 필요는 없습니다. 항목에 일방 통행이있는 한 좋기 때문입니다. 내가 말했듯이, 나는 가장 짧은 길을 필요로하지 않는다.
미로는 2D입니다. 검은 색 테이프를 흰색 테이블에 놓기 만하면 로봇이 라인 센서를 사용하여 라인을 따라 가게됩니다.
자신을 지향하는 다른 센서가 없습니다. 먼저 2D 배열을 만들고 미로의 각 필드를 필드에 넣을 생각을했습니다. 그러나 로봇은 보통의 라인 센서이므로 로봇은 직선이 한 두 필드 길이인지, 전체가 작동하지 않는지 알지 못합니다.
나는 DFS 같은 것을 시도했으나 유사한 문제는 여기에있다. 미로는 원형이며, 로봇은 이전에 노드가 이미 발견되었고 그것이 동일하다는 것을 어떻게 알 수 있습니까?
누구나 아이디어가 있다면 좋을 것입니다!

Answer 1

오리 엔테이션이 약간 퍼지 있지만 결정을 사용하면 가능합니다. 결정은 재현 가능해야합니다. 그것은 클래스에 의해 표현 될 수있다 :

public class Decision { 
    boolean[] directions = new boolean[2]; // 0 = left, 1 = straight, 2 = right 
    // at least 2 of them should be true or it is no decision 
    int path; // 0-2 to mark the current path 
} 

1. 의사 결정의 스택을 만듭니다.

2. 처음에는 가능한 한 방향 만 있습니다 (백은 계산되지 않고 나중에 처리됩니다). 그러면 첫 번째 결정을 만날 때까지 앞으로 이동하십시오.

3. 스택에서 가능한 모든 방향으로 결정을 푸시하십시오.

4. path을 첫 번째 가능한 방향으로 설정하고 그런 식으로 이동하십시오. 다른 결정에 끝날 경우

5. : 당신이 토큰을 찾을 경우 3.

   에 계속 : 당신은 죽은 엔드없이 재현 방법을 발견, 중단.

   가 죽은 엔드 인 경우 : 이전 결정 노드 (첫 번째 일 돌아 오는 길)과 복귀가 결정 팝 6.

6. 를 계속하고 새로운 설정 (다음 가능한 방향으로 시도 경로와, 우리가 결정을 밀어) 당신이 모든 방향을 시도하지 않는 한 5

   에서 계속 다음 다른 결정을 뒤로 이동하고 (특별한 경우는 위에서 언급 한 더 이상 의사 결정이없는 경우 6.

   계속 처음에는 잘못된 방향으로 진행) : 첫 번째 결정을 충족하고 계속 진행할 때까지 앞으로 나아갑니다. 즉, 시작 부분에서 바로 뒤로 가야 하는지를 나타내는 다른 부울 변수가 필요합니다.

   left에서 되돌아 와서 straight을 시도하고 싶을 때는 왼쪽으로 돌리지 말고 곧장 가지 않아야합니다. 따라서 약간의 계산이 필요합니다.

처음에 잘못된 길을 시작하면 알고리즘에 루프 모양의 결정에 문제가 있습니다. 나는 이것이 상한을 설정함으로써 도망 갈 수 있다고 생각한다. 아직 토큰을 찾지 못했고 앞으로 30 개의 결정 노드를 만난다면 앞으로 서클에서 돌아 다니기 시작합니다. 따라서 순서대로 시도하는 대신 시작하여 순서대로 시도해보십시오.