Recursion
and Blobs
With GUI

Nicholas Duchon: Feb 16, 2019.

Outline

Uses JOptionPane for input


Blob Counting

This is the Blob counting algorithm developed in DJW 2nd edition, with a few modifications to make it a little easier to see how the algorithm works.

Grid (pp 257-259) to GridND: I have modified the visited array to show the order in which the elements in the array are visited, and changed the toString method to also print this array. Also added another constructor that will accept a 2-D int array (1's as true and 0's as false) to make it possible to examine a specific array.

BlobApp (pg 260) to BlobAppND: This will support the 2-D constructor, and has a simple example. The default array size is different also.

Note that the algorithm goes in this order:

  1. up
  2. down
  3. left
  4. right

And the recursion acts like a stack, remembering branches that were taken in the search by leaving the current cell to go to the next unmarked adjacent cell in the order shown above.

The checking order here is: up --> down --> left --> right. You can follow this by starting at 1 in this example and tracing the first blob through 76, the second blob from 77 through 79 and so on.


GridND3

// File: GridND3.java
// Date: Mar 18, 2017, Feb 15, 2019
// Author: Nicholas Duchon
// Based on Dale/Joyce/Weems Chapter 4, BlobApp.java and Grid.java

//----------------------------------------------------------------------
// BlobApp.java          by Dale/Joyce/Weems                   Chapter 4
//
// Instantiates a Grid based on a percentage probability provided by the
// user and reports the number of blobs in the Grid.
//----------------------------------------------------------------------
// Nick Duchon - modifications
// Date: Oct 5, 2008
//----------------------------------------------------------------------
// Grid.java              by Dale/Joyce/Weems                  Chapter 4
//
// Supports grid objects consisting of blob and non-blob characters.
// Allows the number of blobs it contains to be counted.
//
// Modifications by Nicholas Duchon
//----------------------------------------------------------------------

// Notes:
// Feb 16, 2019 - added GUI interface

import java.util.Scanner;
import java.util.Random;
import java.util.ArrayList;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JButton;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;
import java.awt.BorderLayout;
import java.awt.GridLayout;

class PairND3 {
   int r, c;
   int index;

   PairND3 (int a, int b, int i) {
      r = a; c = b;
      index = i;
  
}

   public String toString () {
      return index + " " + r + " " + c;
  
}
} // end class PairND3

class BlobND3 {
   ArrayList <PairND3> set = new ArrayList <> ();
   int group;

   public BlobND3 (int g) {group = g;
}

   public String toString () {
      String st = String.format ("\n%5d = ", group);
      for (PairND3 p: set) st += p + ": ";
      int ix = st.lastIndexOf (":");
      st = st.substring (0, ix);
      return st;
  
} // end method toString
} // end class BlobND

public class GridND3 {
   static final int GRIDR = 20;   // number of grid rows
   static final int GRIDC = 20;   // number of grid columns
  
   int rows; // number of grid rows
   int cols; // number of grid columns
    
   boolean [][] grid;     // the grid containing blobs
   int     [][] visited;  // used by blobCount
   int     [][] id;       // the id of each blob
   int index = 1;         // number the order of visits to active cells
   int count = 0;         // number of the blob
   ArrayList <BlobND3> blobs = new ArrayList <> ();
   BlobND3 bnd;
  
   public static void main(String[] args) {
      // Get percentage probability of blob characters
      int percentage;
      while (true) {
         String name = javax.swing.JOptionPane.showInputDialog(
                null, "Input percentage probability (0 to 100): ");
         Scanner s = new Scanner (name);
         if (s.hasNextInt()) {
            percentage = s.nextInt();
            if (percentage > 0 && percentage <= 100)
               break;
         }
      } // end geting input from the user
     
      // create grid
      GridND3 grid = new GridND3 (GRIDR, GRIDC, percentage);
      new GridGUIND3 (grid); // show GUI
  
} // end main method

   public GridND3 (int prows, int pcols, int percentage) {
      rows    = prows;
      cols    = pcols;
      grid    = new boolean [rows][cols]; // true means cell part of a blob
      visited = new int     [rows][cols]; // true if location visited
      id      = new int     [rows][cols]; // which blob?
  
      // to generate random numbers
      Random rand = new Random();
  
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            grid [i][j] = (percentage > rand.nextInt(100));
      blobCount();
  
} // end int/int/int constructor

   public String toString() {
      String gridString = "";
      for (int i = 0; i < rows; i++) {
         for (boolean b: grid[i])
            gridString += b?"X":"-";
         gridString += "     ";
         for (int m: visited[i]) {
            gridString += String.format ("%4d", m);
         } // end for each row in the visited matrix also
         gridString = gridString + "\n";   // end of row
      } // end for each row of the grid
     
      for (int [] r: id) {
         gridString += "\n";
         for (int v: r)
            gridString += (v==0)?"  .":String.format ("%3d", v);
      } // end for each row
      gridString += "\n";
      for (BlobND3 b: blobs) gridString += b;
      gridString += "\nThere are " + count + " blobs.\n";
      return gridString;
  
} // end method toString

    // counts number of blobs in this grid
   public void blobCount() {
      // initialize visited and id arrays
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++) {
            visited [i][j] = 0;
            id      [i][j] = 0;
         } // init visited and id arrays
       
      // count blobs
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            if (grid[i][j] && visited[i][j] == 0) {
               count++;
               bnd = new BlobND3 (count);
               blobs.add (bnd);
               markBlob(i, j);
            } // end for each unvisited blob cell
  
} // end method blobCount
  
    // Mark position row, col as having been visited.
    // Check and if appropriate mark locations above, below, left,
    // and right of that position.
   private void markBlob(int row, int col) {
      if (row <  0   ) return; // these are out of grid locations
      if (row >= rows) return;
      if (col <  0   ) return;
      if (col >= cols) return;
     
      if (!  grid [row][col]     ) return; // not in blobs
      if (visited [row][col] != 0) return; // already visited
     
      bnd.set.add (new PairND3 (row, col, index));
      visited [row][col] = index++;
      id      [row][col] = count;
     
      markBlob(row - 1, col    ); // up
      markBlob(row + 1, col    ); // down
      markBlob(row    , col - 1); // left
      markBlob(row    , col + 1); // right    
  
} // end method markBlob

} // end class GridND2

class GridGUIND3 extends JFrame {
   public static final long serialVersionUID = 1; // ND: junk
   String name = "Grid GUI ND 3";
   java.awt.Color [] colors = {
      new java.awt.Color(100, 100, 255),
      java.awt.Color.getHSBColor (.10f, 1f, 1f),
      java.awt.Color.getHSBColor (.20f, 1f, 1f),
      java.awt.Color.getHSBColor (.30f, 1f, 1f),
      java.awt.Color.getHSBColor (.40f, 1f, 1f),
      java.awt.Color.getHSBColor (.50f, 1f, 1f),
      java.awt.Color.getHSBColor (.60f, .5f, 1f),
      java.awt.Color.getHSBColor (.70f, .5f, 1f),
      java.awt.Color.getHSBColor (.80f, 1f, 1f),
      java.awt.Color.getHSBColor (.90f, 1f, 1f),
      java.awt.Color.getHSBColor (.15f, 1f, 1f),
      java.awt.Color.getHSBColor (.25f, 1f, 1f),
      java.awt.Color.getHSBColor (.35f, 1f, 1f),
      java.awt.Color.getHSBColor (.45f, 1f, 1f),
      java.awt.Color.getHSBColor (.55f, 1f, 1f),
      java.awt.Color.getHSBColor (.65f, .5f, 1f),
      java.awt.Color.getHSBColor (.75f, .5f, 1f),
      java.awt.Color.getHSBColor (.85f, 1f, 1f),
      java.awt.Color.getHSBColor (.95f, 1f, 1f),
      java.awt.Color.getHSBColor (.13f, 1f, 1f),
      java.awt.Color.cyan,
      java.awt.Color.green,
      java.awt.Color.magenta,
      java.awt.Color.orange,
      java.awt.Color.pink,
      java.awt.Color.red,
      java.awt.Color.yellow
   };
  
   JButton buttons [][];
   GridND3 g;
  
   public GridGUIND3 (GridND3 gp) {
      try {
         javax.swing.UIManager.setLookAndFeel(
         javax.swing.UIManager.getCrossPlatformLookAndFeelClassName() );
      } catch (Exception e) {
         e.printStackTrace();
      }
     
      g = gp;
     
      JPanel jpb = new JPanel (); // control buttons
      JButton jba = new JButton ("show visits");
      JButton jbb = new JButton ("show blobs");
      jpb.add (jba); jpb.add (jbb);
      add (jpb, BorderLayout.NORTH);
      jba.addActionListener (e -> showVisits());
      jbb.addActionListener (e -> showBlobs());
     
      JPanel jp = new JPanel ();
      jp.setLayout (new GridLayout (g.grid.length, g.grid[0].length));
      buttons = new JButton [g.grid.length][g.grid[0].length];
      for (int i = 0; i < g.grid.length; i++)
         for (int j = 0; j < g.grid[0].length; j++) {
            int v = g.id[i][j];
            JButton jb = buttons [i][j] = new JButton ("");
            if (v ==0) {
               jp.add (jb);
               continue;
            }
            jb.setText ("" + g.visited[i][j]);
            jb.setBackground (colors[v%colors.length]);
            jp.add (jb);
         } // end for each button
        
      setTitle (name);
      setSize (400, 200);
      add (jp, BorderLayout.CENTER);
      pack ();
      setLocationRelativeTo (null);
      setVisible (true);
      setDefaultCloseOperation (JFrame.EXIT_ON_CLOSE);
     
      // Text display?:
      JFrame jf = new JFrame ();
      jf.setTitle (name + " text");
      jf.setSize (400, 200);
      JTextArea jta = new JTextArea ();
      JScrollPane jsp = new JScrollPane (jta);
      jta.setFont (new java.awt.Font ("Monospaced", java.awt.Font.PLAIN, 12));
      jta.setText (g.toString());
      jf.add (jsp, BorderLayout.CENTER);
      jf.setLocation (10, 10);
      jf.setVisible (true);
     
  
} // end BlobND3 constructor
  
   void showBlobs () {
      for (int i = 0; i < g.grid.length; i++)
         for (int j = 0; j < g.grid[0].length; j++) {
            int v = g.id[i][j];
            if (v ==0) {
               continue;
            }
            buttons[i][j].setText ("" + v);
         } // end for each button
  
} // end method showVisits
  
   void showVisits () {
      for (int i = 0; i < g.grid.length; i++)
         for (int j = 0; j < g.grid[0].length; j++) {
            int v = g.id[i][j];
            if (v ==0) {
               continue;
            }
            buttons[i][j].setText ("" + g.visited[i][j]);
         } // end for each button
   } // end method showBlobs
} // end class GridGUIND3


Output:

At 44%:
Visits:



Blobs:


ND.