Home > Mobile >  How to recursively start multiple threads while killing the original thread?
How to recursively start multiple threads while killing the original thread?

Time:11-27

I am not sure how to convert a function I've written so that it will run as multiple threads concurrently in Java.

The function takes a root, which will be different for each thread that "splits off" at a given junction point (the if statement for this is within the function, each newly-created thread should be able to split off in the future as well, at the next junction).

I want all threads to die once they reach the target, but the "while" loop for checking whether they've reached the end is also within the function.

Basically, I want the function to be able to run multiple times concurrently, with a modified starting point each time, and for the "original" thread to be killed off before splitting.

I also can't extend Thread because I'm already extending another class, so I'm trying to do it by implementing Runnable.

Here is the class (the parent classes work fine so I don't think I need to post them):

public class Multithreaded extends ParentClass implements Runnable {

    @Override
    public void run() {
         executeThread(modelThreaded, new HashMap<>());
    }

    private final Set<Tile> VISITED = new HashSet<>();
    private Grid modelThreaded; //to be able to update the root?

    public Multithreaded() {
        super();
    }

    @Override
    protected int runPathfinder(Grid model, List<Tile> path) {
        HashMap<Tile, Integer> tileData = new HashMap<>();
        this.modelThreaded = model;
        this.executeThread(model, tileData);

        int cost = tileData.get(model.getTarget()) - 1;

        this.statistics.setPathFound(true, cost);
        this.painter.drawPath(path, model);

        return cost;
    }

    private void executeThread(Grid model, HashMap<Tile, Integer> tileData) {

        // Keeps track of visited tiles
        VISITED.add(model.getRoot());

        //start at the root
        Tile currentTile = model.getRoot();
        List<Tile> posNeighbors = model.getTileNeighbors(currentTile);
        List<Tile> validNeighbors = new ArrayList<>();

        int DEFAULT_DISTANCE = 1;
        tileData.put(model.getRoot(), DEFAULT_DISTANCE);
        int iteration = 0;

        while (!isVisited(model.getTarget())) {

            iteration  ;
            posNeighbors.clear();
            validNeighbors.clear();
            posNeighbors = model.getTileNeighbors(currentTile);
            validNeighbors = getForward(posNeighbors);

            //debugging
            System.out.println("Valid Neighbors for currentTile ("
                      currentTile.getX()   ", "   currentTile.getY()   "): ");
            for (Tile validNeighbor : validNeighbors) {
                System.out.println(validNeighbor.getX()   ", "   validNeighbor.getY());
            }

            // tries to split along junctions into multithreads
            // tries to kill mouse if there's a dead end
            if (validNeighbors.size() > 0) {
                for (Tile validNeighbor : validNeighbors) {
                    currentTile = validNeighbor;
                    // want to create a new thread for each validNeighbor here, but with
                    // a small change: the root changes to the current validNeighbor
                    model.setRoot(validNeighbor);
                    Runnable runnable = new Multithreaded();
                    Thread thread = new Thread(runnable);
                    thread.start();
                }
            }
            //attempt to kill/stop current thread if there are no more options left for that thread
            else {
                break;
            }


            VISITED.add(currentTile);
            tileData.put(currentTile, DEFAULT_DISTANCE   iteration);

        }
    

private List<Tile> getForward(List<Tile> posNeighbors) {
        List<Tile> validNeighbors = new ArrayList<>();

        for (Tile posNeighbor : posNeighbors) {
            if (posNeighbor != null && !posNeighbor.isWall()
                && !isVisited(posNeighbor)) {
                validNeighbors.add(posNeighbor);
            }
        }
        return validNeighbors;
    }

    private boolean isVisited(Tile posNeighbor) {
        for (Tile visitedTile : VISITED) {
            if (visitedTile == posNeighbor) {
                return true;
            }
        }
        return false;
    }
}

As you can see, I want the threads to keep going unless:

  1. one of them encounters the target (model.getTarget()) or
  2. it reaches a point where there are 0 validNeighbors.

When there's 1 validNeighbor for a thread, it should stay singular and proceed along that path until it either reaches another junction or a dead end (getForward returns only the unvisited neighbors)

So, when a thread encounters a junction (2 validNeighbors), it should split into two and kill the original thread (stopping its execution of executeThread, which is why I put a break in there), with one thread for each direction, and continue running the algorithm. With my current code, it runs down the path correctly, but doesn't split into different threads and doesn't stop running when it encounters a dead end.

What would be the best way to get this to run? Am I correct in putting executeThread() in run(), or is there somewhere else I should be putting it? I've tried just doing runnable.run() instead of Thread thread and thread.start(), but that doesn't seem to help. I'm really not sure what to do here, I feel like I'm missing something obvious...

EDIT: runPathfinder is the function called by the parent classes in order for all of this code to run

CodePudding user response:

I think the following mre(1) reproduces the multi-threading functionality required.

Each node (state / tile) is represented by an integer.
getTileNeighbors returns 3 random neighbors.
All thread share a synchronized visited collection, and should stop after target was added to visited.
(copy-paste the entire code to Main.java and run)

import java.util.*;

public class Main   {
    public static void main(String[] args) {
        new Thread(new Multithreaded(0, 20)).start();
    }
}

class Multithreaded  implements Runnable {

    // Synchronized Set (shared between threads)
    private static final Set<Integer> visited = Collections.synchronizedSet(new HashSet<Integer>());
    private final int root, target;

    //root and target assumed >=0
    public Multithreaded(int root, int target) {
        this.root = root;
        this.target = target;
    }

    @Override
    public void run() {
        executeThread(root);
    }

    private void executeThread(int root) {

        visited.add(root);
        System.out.println("New thread, root="  root);
        while (!isStopConditionMet()) {

            List<Integer> neighbors = getTileNeighbors(root);
            //todo if  neighbors is empty break out of the while loop
            
            for (Integer neighbor : neighbors) {

                if(! visited.add(neighbor)) {
                    continue; //skip is already visited
                }

                Runnable runnable = new Multithreaded(neighbor, target);
                Thread thread = new Thread(runnable);
                thread.start();
            }
        }
    }

    //returns a list o 3 random numbers between 0-target (inclusive)
    //to represent 3 random neighbors
    private List<Integer> getTileNeighbors(int currentTile) {
        Random rnd = new Random();
        int maxValue = target  1;
        return Arrays.asList(rnd.nextInt(maxValue), rnd.nextInt(maxValue), rnd.nextInt(maxValue));
    }

    private boolean isStopConditionMet() {
        return visited.contains(target);
    }
}

(1) mre should demonstrate the problem to be solved, and not a specific application.
  • Related