Two random walkers on a 2d plane

Question

So I have this multithreadded program that generates 2 random walkers, each walker is a separate thread since I need them to move simultaneously. Each walker randomly moves in any of the 4 directions. The first problem is that i think stdDraw is not thread safe and therefore without having a lock around my entire function, it tends to draw random squares at random points for no reason and the whole thing become pretty glitchy. When i put a lock around my function then one thread becomes slower that the other since it sometimes has to wait for the lock. So the threas are not simultaneous anymore. Is there a solution to this? The other problem i have is I want it to break out of the loop when the two walkers intersect, but for some reason the two threads dont know about the position of the other. One thinks that the position of the other is always at (0,0). Thanks!

import java.awt.Color;
public class WalkerThread implements Runnable {

String name;
static Integer lock = new Integer(1000);
int num;
static int steps = 0, steps2 = 0;
static int x = 0, y = 0;
static int x2 = -1, y2 = -2;

public WalkerThread(String s, int n) {
    this.name = s;
    this.num = n;
}

@Override
public void run() {

    int N = 10;
    StdDraw.create(600, 600);
    StdDraw.setScale(-N, -N, +N, +N);
    StdDraw.clear(Color.gray);
    do {
        synchronized (lock) {

            if (num == 1) {
                StdDraw.go(x, y);
                StdDraw.setColor(Color.white);
                StdDraw.spot(0.9, 0.9);

                double r = Math.random();
                if (r < 0.25)
                    x--;
                else if (r < 0.50)
                    x++;
                else if (r < 0.75)
                    y--;
                else if (r < 1.00)
                    y++;

                steps++;

                StdDraw.setColor(Color.blue);
                StdDraw.go(x, y);
                StdDraw.spot(0.9, 0.9);
                StdDraw.pause(40);

            }

            if (num == 2) {
                StdDraw.go(x2, y2);
                StdDraw.setColor(Color.yellow);
                StdDraw.spot(0.9, 0.9);
                double r2 = Math.random();
                if (r2 < 0.25)
                    x2--;
                else if (r2 < 0.50)
                    x2++;
                else if (r2 < 0.75)
                    y2--;
                else if (r2 < 1.00)
                    y2++;

                steps2++;
                StdDraw.setColor(Color.green);
                StdDraw.go(x2, y2);
                StdDraw.spot(0.9, 0.9);
                StdDraw.pause(40);

            }
        }// lock
        /*String pict = steps + ".png";
        StdDraw.save(pict);*/
            //if (posX == posX2 && posY == posY2) break;


    } while ((Math.abs(x) < N && Math.abs(y) < N) && (Math.abs(x2) < N && Math.abs(y2) < N));

    System.out.printf("Total steps of %s is %d and %d \n", name, steps, steps2);

}
}

//MAIN

public class Walkers{
public static void main(String[] args) {

    Thread t1 = new Thread(new WalkerThread("one", 1));
    Thread t2 = new Thread(new WalkerThread("two", 2));

    t1.start();
    t2.start();

}
}

Answer 1

Avoid Math.random() when going multi-threaded - create an r = new Random() in your Walker constructor, and use it as r.nextDouble().

Instead of the big if, take the differences between both branches (just a couple of colors) and place them in the constructor. Also, threads have separate namespaces. You don't need to keep x and x2 separate - each thread would have its own private x, invisible from the other thread. Your code could roughly end up 1/2 the size.

As far as synchronization goes, you have two problems. The first problem is that StdDraw is built on Swing (it runs in a JFrame, for example), which is not thread-safe. In particular, all drawing must happen in something called the event thread. This means that you should place all the drawing code within something like

SwingUtilities.invokeLater(new Runnable() {
  @Override
  public void run() {
    synchronized (lock) {
      // ... your calls to StdDraw here ...
    }
  }
});

However, this opens a big can of worms. First, the drawing code needs to access your data, which you will therefore want to prevent from changing at the same time. You can protect it with yet more synchronized (lock) { ... }, but that will mean that only one thread will be executing in any given moment. That's not what multithreading is for.

The simpler answer is, taking a peek at Elyasin's answer, to forget about parallel execution (it is really not needed here), and embrace turn-taking:

do {
        bool turn = false;
        // ... current init code here
        if (turn) {
            // ... current code for num==1
        } else {
            // ... current code for num==2
        }
        turn = !turn; // reverse turn for next round
} while (/* ... */);

No threads, no locks, no synchronization, and it should work smoothly and without artifacts.

Answer 2

So I have this multithreaded program that generates 2 random walkers, each walker is a separate thread since I need them to move simultaneously. Each walker randomly moves in any of the 4 directions.

You clearly state that you want two random walkers, any of the four directions is chosen randomly by any of the two walkers. So we stick to this requirement.

The first problem is that I think stdDraw is not thread safe and therefore without having a lock around my entire function it tends to draw random squares at random points for no reason and the whole thing becomes pretty glitchy. When I put a lock around my function then one thread becomes slower than the other one, since it sometimes has to wait for the lock. So the threads are not simultaneous anymore. Is there a solution to this?

Thread safety and randomness are not really correlated here. As clarified above you want the walkers to be random. This has nothing to with thread safety in the first place. Simply put: Thread safety means that if several threads share a data structure/address space, then access to it is guaranteed to be free of race conditions. Not sure what you mean with random squares at random points for no reason. A lock is usually used to grant permissions to execute, or to grant access to one or more shared resources. Not sure why you use a lock here, I don't see a shared resource and I don't see why you use the lock to control thread execution one at a time if you don't want this in the first place.

The two random walkers are independent and the only shared resource I see is the 2D plane. If you want the two walkers to execute simultaneously/concurrently then you should not use a lock the way you did I think. I am not even sure if thread safety really is an issue here, maybe you don't need thread safety?

The other problem I have is I want it to break out of the loop when the two walkers intersect, but for some reason the two threads don't know about the positions of each other. One thinks that the position of the other one is always at (0,0).

Oh, now that is a good follow up question. Maybe there is a shared resource then? Will it have to be thread safe then?

That is the 2D plane, which would know if the two walkers intersect or not? (I did not look into the StdDraw to be honest, but you would know to find out I think.) Find a way to get the two coordinates of the two random walkers from the StdDraw and check for intersection. If that is not possible then use a shared resource, i.e. a data structure that holds both coordinates of 1st random walker and 2nd random walker.

You would not need to care much about thread safety, because one random walker would only read (and not write) the values/coordinates of the other random walker.

Try that out and let us know.