Search algorithms (DFS,BFS,A star etc.). How to update the GUI (with updated state) without “freezing”?

Question

My question is rather simple.

Let's suppose I'm executing the algorithm "A star" (search algorithm using a heuristic function to calculate next state to visit).

I want to show in a grid the updates (I will apply it to 8-puzzle problem). How should I do that? I want changes to be clearly visible.. but in my experience if I just do something like Grid[6].showValue(newValue) the GUI will just "stand-by".

I'm sure this could be done with multi-threading (maybe?) but is there any simpler way?

And one more very easy question if possible: I wonder if in Java (my IDE is Netbeans) there is any class containing methods for searching like BFS, DFS and A star? If so, could you provide a link to the code of the algorithms (I need to use them as a base for my code.. I can't include them directly.. you know.. university assignment). I suppose this code is easy to find since Java is a open-source language. Am I wrong?

Thank you very much

Answer 1

Don't do the processing in the GUI thread.

If we're talking about swing here, that's the Event Dispatch Thread; use worker threads as described in the Concurrency in Swing tutorial.

Answer 2

You should do the processing in a separate thread, like MДΓΓ БДLL suggested. Basically, you'll have to implement your search related code in a class that implements Runnable, which "marks" a class to be executable within a thread.

To do so, you can use a SwingWorker:

SwingWorker<Integer[], Void> worker = new SwingWorker<Integer[], Void>() {
    public Integer[] doInBackground() {
        //do the computation here. This will be executed in a different thread; 
        //thus allowing the event dispatch thread (=GUI thread) to ensure responsiveness of the UI.
        //NEVER update your GUI here since this could cause strange errors that are sometimes hard to track down.
    }
    public void done() {
        try {
            Integer[] result = get(); //this is executed in the GUI thread after 
            //execution if the doInBackground method finished and fetches the result of 
            //that method. You should update your GUI here.
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        } catch (ExecutionException ex) {
            ex.printStackTrace();
        }
   }
}

For your second answer: It's rather hard to implement an algorithm in such a generic way that it's usable for different data types, especially since the tree you are using BFS, DFS and A-Star may contain any kind of data. I think you should find the algorithms in pseudocode in a textbook or lecture nodes; if not, look it up somewhere and try to implement it yourself.