Concurrent Cellular Automata actors moving

185 views Asked by At

I have a two-dimensional cellular automata. In some cells there may be an actor (agent). Each actor is a thread. I need to move actor based on the 9 cells around the actor's cell. I want to do this concurrently so the actor in a cell (4,5) can use neighbors cells (3,4), (4,4), (5,4), (3,5), (5,5), (3,6), (4,6), (5,6) and no other actors can use this cells. If some actor has these cells in his neighborhood, he has to wait until the first actor moved. But I want to allow moving the actor, who has no common neighborhood, concurrently. So the actor in (4,5) can move at the same time as an actor in (10,5) because they have no common neighborhood.

What is the best solution of that? Can you propose something?

1

There are 1 answers

1
Anton Dovzhenko On

The rough idea is below.

  1. Create matrix of Cell objects, which will be used for synchronization
  2. Assign Actors to the cells
  3. Whenever Actor moves to another cell it must get a monitor on the cell

Note that the cell, from which Actor starts to move, is not protected in the code below. Also, what would you expect if every cell is populated has an Actor?

import java.util.ArrayList;
import java.util.List;

public class CellularAutomata {

    public static void main(String ... args) throws InterruptedException {
        final int rows = 5;
        final int cols = 5;
        Cell[][] matrix = new Cell[rows][cols];
        List<Actor> actors = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = new Cell();
                //populate actors
                if ((i + j) % 2 == 0) {
                    Actor actor = new Actor(matrix, i, j);
                    actor.setName(String.format("Actor %d %d", i, j));
                    actors.add(actor);
                }
            }
        }
        for (Actor actor : actors) {
            actor.start();
        }
        for (Actor actor : actors) {
            actor.join();
        }
    }

    public static class Cell {}

    public static class Actor extends Thread {

        private final static int[][] circleMoves = {
                {-1, -1}, {-1, 0}, {-1, 1}
                , {0, 1}, {1, 1}, {1, 0}
                , {1, -1}, {0, -1}, {0, 0}
        };
        private final Cell[][] matrix;
        private final int row;
        private final int col;

        public Actor(Cell[][] matrix, int row, int col) {
            this.matrix = matrix;
            this.row = row;
            this.col = col;
        }

        @Override
        public void run() {
            for (int i = 0; i < circleMoves.length; i++) {
                int nextRow = row + circleMoves[i][0];
                int nextCol = col + circleMoves[i][1];
                if (nextRow >= 0 && nextRow < matrix.length
                        && nextCol >= 0 && nextCol < matrix[nextRow].length) {
                    Cell targetCell = matrix[nextRow][nextCol];
                    System.out.println(Thread.currentThread().getName() + " waiting for cell (" + nextRow + ";" + nextCol + ")");
                    synchronized (targetCell) {
                        try {
                            System.out.println(Thread.currentThread().getName() + " moved to cell (" + nextRow + ";" + nextCol + ")");
                            Thread.sleep(1000);
                        } catch (InterruptedException e) {
                            throw new IllegalStateException(e);
                        }
                    }
                }
            }
        }

    }

}