Угадай следующую позицию одновременно работающих потоков

Question

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

Вот код:

        public int[][] visitedCell=new int[15][15]; // holds how many times visited for each cell
    public boolean cntrl=true,repeat=true,end;
    public int r=0;
    public int cnt;
    public boolean find;
    public void  decision(int posX,int posY){
       int distanceToExit;
       cnt=0; // holds how many cell is free around the cell which thread is on
       r=0;
       end=false; // checks robot found exit
       find=false; // checks suitable cell found to move in next step
       posX=posX/40; // all cells are 40*40 dimension.since it is divided 40 to find poisition
       posY=posY/40; // found y position
       int[][] neighbours={{posX,posY+1},{posX+1,posY+1},{posX+1,posY},{posX+1,posY-1},{posX,posY-1},{posX-1,posY-1},{posX-1,posY},{posX-1,posY+1}}; // all 8 neighbours of a cell
       int[][] freeCellChoises = new int[8][2]; // holds free cells to move
       int[][] distanceCell=new int[8][2];
       for(int i=0;i<8;i++){ // checks which neighbour cells are free
             if((neighbours[i][0] >0 && neighbours[i][0] <14) && (neighbours[i][1] >0 && neighbours[i][1] < 14) || (neighbours[i][0]==1 && neighbours[i][1]==14) || (neighbours[i][0]==14 && neighbours[i][1]==1) ) // [1,14] = enter position and [14,1]= exit position
             {
               if(Draw.paintArray[neighbours[i][0]][neighbours[i][1]]==0){// cell is free.it is eligible
                   freeCellChoises[cnt][0]=neighbours[i][0]; // load eligible cells this array
                   freeCellChoises[cnt][1]=neighbours[i][1];
                   distanceToExit=(int) Math.sqrt((Math.pow(neighbours[i][0]-560, 2)+Math.pow(neighbours[i][1]-40,2)));
                   distanceCell[cnt][0]=cnt;
                   distanceCell[cnt][1]=distanceToExit;
                   cnt++;}
             }
       } // eligible cells are ready anymore
       if(Frame.radButSel==1){ // random movement
           int no=rndm.nextInt(cnt); // choose one of the eligible cell randomly
           x=freeCellChoises[no][0] * 40;
           y=freeCellChoises[no][1] * 40;
       }
       if(Frame.radButSel==2){ // closed way movement ( find the most clodes cell to the exit ) .Exit is [14,1].So x must be max, y must be min to a cell has priority
           int maxX=freeCellChoises[0][0];
           int minY=freeCellChoises[0][1];
           int selection1=0,selection2=0;
           for(int i=0;i<cnt;i++){ // x i byk y si kck  sec
               if(freeCellChoises[i][0]> maxX){
                   maxX=freeCellChoises[i][0];
                   selection1=i;}
               if(freeCellChoises[i][1]<minY){
                   minY=freeCellChoises[i][1];
                   selection2=i;
               }


           }
         if(cnt!=0) // checks there is a priority cell
             r=rndm.nextInt(2)+1; // selects one of the priority cell

         if(r==1 && visitedCell[freeCellChoises[selection1][0]][freeCellChoises[selection1][1]] <2){ //selection1.same cell musnt be visited more than 2 times
               x=freeCellChoises[selection1][0] * 40;
               y=freeCellChoises[selection1][1] * 40;}

         else if(r==2 && visitedCell[freeCellChoises[selection2][0]][freeCellChoises[selection2][1]] <2){//selection2
              x=freeCellChoises[selection2][0] * 40;
              y=freeCellChoises[selection2][1] * 40;}

          else{ // applies when there is not any priority cell
               System.out.println("oncelik yok");
               int repeat =0;
               while(repeat<cnt){
                  r=rndm.nextInt(cnt); // choose one of the eligible cell
                  x=freeCellChoises[r][0] * 40;
                  y=freeCellChoises[r][1] * 40;
                  if(visitedCell[freeCellChoises[r][0]][freeCellChoises[r][1]] <2){
                      repeat=10;
                  }
                  else
                      repeat++;

               }System.out.println("x="+x+"y="+y);

          }
      }
      if(Frame.radButSel==3){

      }

      if(x==560 && y==40){ // checks decided cell is exit point
           Action.pool.shutdownNow();// thread finished
           end=true;
           Main.butAct++; // when butAct=2 , "RESULT" button will be active
           timer.stopTime();} // stops time for the thread

      distance=(int) Math.sqrt(Math.pow(x-560,2) + Math.pow(y-40, 2));// calculates distance between thread - exit

}

public Action() throws InterruptedException{
    pool=Executors.newFixedThreadPool(2); // two thread in the pool
    robot1=new Robot(40,560); // starts enter position
    robot2=new Robot(40,560); // starts enter position
    pool.submit(robot1); // loads robot1 to pool
    pool.submit(robot2);// loadss robot2 to pool
}
public void run() {
    while(true){ // run threads always
    try {
        Frame.worker.pauseIfNeeded();} // checks whether pause button is pressed
    catch (InterruptedException ex) {
        Logger.getLogger(Robot.class.getName()).log(Level.SEVERE, null, ex);}
    if(end==false){// not reach exit
       try{
            System.out.println(Thread.currentThread().getName());// displays current thread name
            System.out.println("pozisyon x="+x+"y="+y);
            decision(x,y); // thread makes decision to move
            visitedCell[x/40][y/40]+=1; // increade number of visitide cell count for that cell in the array
            visCell++; //increase visited cell count for the thread
            Thread.sleep(300);} // thread sleeps for a while to observe movement changing
       catch(Exception ex){
       }
    }
    else{// found exit
            Thread.currentThread().interrupt(); // Thread killed
            if(Main.butAct==2)// after a thread found exit, checks if result button can be active anymore
               Frame.button4.setEnabled(true); // activates result button
    }
  }//end while

}

Answer 1

Или вы могли бы сделать это примерно так.Класс менеджера знает о положении обоих потоков, а метод moveTo проверяет, не совпадают ли они в одном и том же месте.

class MazeManager {
  int x1, x2, y1, y2;

  public synchronized boolean moveTo(int threadId, int x, int y) {
    ..
  }
}

Answer 2

Наиболее простым решением было бы «разделить» работу таким образом, чтобы две рабочие области (решения / пути, которые необходимо опробовать) были взаимоисключающими.Обходной путь может заключаться в одновременном наборе позиций, которые будут проверяться каждым потоком перед выполнением перемещения.

Answer 3

Вам придется использовать концепцию так называемого взаимного исключения.В языке программирования Java вам придется использовать ключевое слово synchronized, чтобы выполнить эту работу за вас.Простой пример можно увидеть в [1]:

public class SynchronizedCounter {
  private int i = 0;

  public synchronized void increment() {
    i++;
  }

  public synchronized void decrement() {
    i--;
  }

  public synchronized int value() {
    return i;
  }
}

Здесь вы видите код, который гарантирует, что только один поток может изменить значение общей переменной i.Обратите внимание, что код использует this в качестве так называемого «объекта блокировки».Вы можете переписать код следующим образом:

public class SynchronizedCounter {
  private int i = 0;

  public void increment() {
    synchronized(this) {
      i++;
    }
  }

  public void decrement() {
    synchronized(this) {
      i--;
    }
  }

  public int value() {
    synchronized(this) {
      return i;
    }
  }
}

Или вы можете создать свой собственный объект блокировки и использовать его:

public class SynchronizedCounter {
  private int i = 0;
  private Object lock = new Object();

  public void increment() {
    synchronized(lock) {
      i++;
    }
  }

  public void decrement() {
    synchronized(lock) {
      i--;
    }
  }

  public int value() {
    synchronized(lock) {
      return i;
    }
  }
}

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

[1] http://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html

Answer 4

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

Answer 5

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