Saturday, April 30, 2011

Sound Programming - Part 4

This is part 4 of the series. It is suggested to read the whole series from the beginning.



Rhythm


The program in the previous article is able to replay simple melody. However, the interpretor doesn't have ways to define rhythm. That means every musical note has the same duration. In order to play simple song, we need to define duration modifier in our simple interpretor. Let's define the modifiers as follows :
  • "-" The duration of the previous note is doubled
  • "/" The duration of the previous note is reduced by half
  • "." The duration of the previous note is extended by a factor of 1.5

With the above modifier, the song "Jingle Bells" can be represented by the following string :
String m="eee-eee-egc.d/e---fff.f/feee/e/edded-g-eee-eee-egc.d/e---fff.f/feee/e/ggfdc---";

Jingle Bells

The following is a program that play the song "Jingle Bells". It is a modification of the program in the previous post.
/******************************************************************************
* File : Jingle.java
* Author : http://java.macteki.com/
* Description :
*   Play "Jingle Bells"
* Tested with : JDK 1.6
******************************************************************************/
   
class Jingle
{
   
  static void beep(double frequency, int duration) throws Exception
  {
       
    int nChannel = 1;         // number of channel : 1 or 2
   
    // samples per second
    float sampleRate = 16000;  // valid:8000,11025,16000,22050,44100
    int nBit = 16;             // 8 bit or 16 bit sample
   
    int bytesPerSample = nChannel*nBit/8;
   
    double durationInSecond = (double) duration/1000.0;
    int bufferSize = (int) (nChannel*sampleRate*durationInSecond*bytesPerSample);
    byte[] audioData = new byte[bufferSize];
   
    // "type cast" to ShortBuffer
    java.nio.ByteBuffer byteBuffer = java.nio.ByteBuffer.wrap(audioData);
    java.nio.ShortBuffer shortBuffer = byteBuffer.asShortBuffer();
   
   
    int sampleLength = audioData.length/bytesPerSample;
   
    // generate the sine wave
    double volume = 8192;   // 0-32767
    double PI = Math.PI;
    for(int i = 0; i < sampleLength; i++){
      double time = i/sampleRate;
      double freq = frequency;
      double angle = 2*PI*freq*time;
      double sinValue = Math.sin(angle);
   
      double fade=1;
      int decay=sampleLength*1/3;  // start fade out at 2/3 of the total time
      if (i>=sampleLength-1-decay) fade=(double)(sampleLength-1-i)/decay;
   
      short amplitude = (short) (volume*fade*sinValue);
  
      for (int c=0;c<nChannel;c++)
      {
        shortBuffer.put(amplitude);
      }
   
    }//end generating sound wave sample
   
   
    boolean isSigned=true;
    boolean isBigEndian=true;
   
    // Define audio format
    javax.sound.sampled.AudioFormat audioFormat =
      new javax.sound.sampled.AudioFormat(sampleRate, nBit, nChannel, isSigned,isBigEndian);
   
   
    javax.sound.sampled.DataLine.Info dataLineInfo =
      new javax.sound.sampled.DataLine.Info(
         javax.sound.sampled.SourceDataLine.class, audioFormat);
   
    // get the SourceDataLine object
    javax.sound.sampled.SourceDataLine sourceDataLine = 
      (javax.sound.sampled.SourceDataLine)
      javax.sound.sampled.AudioSystem.getLine(dataLineInfo);
   
    sourceDataLine.open(audioFormat);
    sourceDataLine.start();
   
    // actually play the sound
    sourceDataLine.write(audioData,0,audioData.length);
   
    // "flush",  wait until the sound is completed
    sourceDataLine.drain();
   
  }
   
     
  public static void main(String[] args) throws Exception
  {
 
    java.util.Hashtable<String,Integer> frequencyTable=
      new java.util.Hashtable<String,Integer>();
 
    frequencyTable.put("c",262);   // frequency of middle C
    frequencyTable.put("d",294);
    frequencyTable.put("e",330);
    frequencyTable.put("f",349);
    frequencyTable.put("g",392);
    frequencyTable.put("a",440);
    frequencyTable.put("b",494);
    frequencyTable.put("C",523);
    frequencyTable.put("D",587);
    frequencyTable.put("E",659);
 
    String song="eee-eee-egc.d/e---fff.f/feee/e/edded-g-eee-eee-egc.d/e---fff.f/feee/e/ggfdc---";
 
    int full=250;  int half=full/2;
    for (int i=0;i<song.length();i++)
    {
      int duration=full;
      String s=song.substring(i,i+1);
 
      // get pitch
      Integer freq = frequencyTable.get(s);

      // get duration modifier
      int j=i+1;
      while (j<song.length())
      {
        String s1=song.substring(j,j+1);
        if (s1.equals("/")) { duration-=half;  }
        else if (s1.equals(".")) { duration+=half;  }
        else if (s1.equals("-")) duration+=full; 
        else break;
        j++;
      }

      if (freq!=null) beep(freq, duration);
    }
 
  }
}

Thursday, April 21, 2011

Sound Programming - Part 3

This is part 3 of the series. It is suggested to read the whole series from the beginning.


Musical Notes

So far we have implemented a beep() method which will produce a sound with specified frequency. Different frequencies corresponds to different pitches. If we predefine a table of frequency for every musical notes. We can play simple melody in our program.

    java.util.Hashtable<String,Integer> frequencyTable
      = new java.util.Hashtable<String,Integer>();

    frequencyTable.put("c",262);   // frequency of middle C
    frequencyTable.put("d",294);
    frequencyTable.put("e",330);
    frequencyTable.put("f",349);
    frequencyTable.put("g",392);
    frequencyTable.put("a",440);
    frequencyTable.put("b",494);
    frequencyTable.put("C",523);
    frequencyTable.put("D",587);
    frequencyTable.put("E",659);


Playing the melody

We can write a simple interpretor for playing simple melody.
    String melody="c d e f g a b C b a g f e d c";

    for (int i=0;i<melody.length();i++)
    {
      int duration=250;
      String s=melody.substring(i,i+1);
      Integer freq = frequencyTable.get(s);
      if (freq!=null) beep(freq, duration);
    }


Full Source Code

/******************************************************************************
* File : MusicalNote.java
* Author : http://java.macteki.com/
* Description :
*   Play simple musical note
* Tested with : JDK 1.6
******************************************************************************/
  
class MusicalNote
{
  
  static void beep(double frequency, int duration) throws Exception
  {
      
    int nChannel = 1;         // number of channel : 1 or 2
  
    // samples per second
    float sampleRate = 16000;  // valid:8000,11025,16000,22050,44100
    int nBit = 16;             // 8 bit or 16 bit sample
  
    int bytesPerSample = nChannel*nBit/8;
  
    double durationInSecond = (double) duration/1000.0;
    int bufferSize = (int) (nChannel*sampleRate*durationInSecond*bytesPerSample);
    byte[] audioData = new byte[bufferSize];
  
    // "type cast" to ShortBuffer
    java.nio.ByteBuffer byteBuffer = java.nio.ByteBuffer.wrap(audioData);
    java.nio.ShortBuffer shortBuffer = byteBuffer.asShortBuffer();
  
  
    int sampleLength = audioData.length/bytesPerSample;
  
    // generate the sine wave
    double volume = 8192;   // 0-32767
    double PI = Math.PI;
    for(int i = 0; i < sampleLength; i++){
      double time = i/sampleRate;
      double freq = frequency;
      double angle = 2*PI*freq*time;
      double sinValue = Math.sin(angle);
  
      double fade=1;
      int decay=sampleLength*1/3;  // start fade out at 2/3 of the total time
      if (i>=sampleLength-1-decay) fade=(double)(sampleLength-1-i)/decay;
  
      short amplitude = (short) (volume*fade*sinValue);
 
      for (int c=0;c<nChannel;c++)
      {
        shortBuffer.put(amplitude);
      }
  
    }//end generating sound wave sample
  
  
    boolean isSigned=true;
    boolean isBigEndian=true;
  
    // Define audio format
    javax.sound.sampled.AudioFormat audioFormat =
      new javax.sound.sampled.AudioFormat(sampleRate, nBit, nChannel, isSigned,isBigEndian);
  
  
    javax.sound.sampled.DataLine.Info dataLineInfo =
      new javax.sound.sampled.DataLine.Info(
         javax.sound.sampled.SourceDataLine.class, audioFormat);
  
    // get the SourceDataLine object
    javax.sound.sampled.SourceDataLine sourceDataLine = 
      (javax.sound.sampled.SourceDataLine)
      javax.sound.sampled.AudioSystem.getLine(dataLineInfo);
  
    sourceDataLine.open(audioFormat);
    sourceDataLine.start();
  
    // actually play the sound
    sourceDataLine.write(audioData,0,audioData.length);
  
    // "flush",  wait until the sound is completed
    sourceDataLine.drain();
  
  }
  
    
  public static void main(String[] args) throws Exception
  {

    java.util.Hashtable<String,Integer> frequencyTable=
      new java.util.Hashtable<String,Integer>();

    frequencyTable.put("c",262);   // frequency of middle C
    frequencyTable.put("d",294);
    frequencyTable.put("e",330);
    frequencyTable.put("f",349);
    frequencyTable.put("g",392);
    frequencyTable.put("a",440);
    frequencyTable.put("b",494);
    frequencyTable.put("C",523);
    frequencyTable.put("D",587);
    frequencyTable.put("E",659);

    String melody="c d e f g a b C b a g f e d c";

    for (int i=0;i<melody.length();i++)
    {
      int duration=250;
      String s=melody.substring(i,i+1);
      Integer freq = frequencyTable.get(s);
      if (freq!=null) beep(freq, duration);
    }

  }
}

Tuesday, April 19, 2011

Sound Programming - Part 2

This is part 2 of the series. It is suggested to read the whole series from the beginning.

Attack, Decay, Sustain, Release

Let's recall the sound wave of a pure tone.


The amplitude of the vibration doesn't change. Hence the sound volume doesn't change over time.
In reality, sound volume is seldom constant. For example, if we hit a key on the piano, the sound volume go through four phases.
  1. Attack
    The volume bursts to the maximum level in a short period of time
  2. Decay
    The volume drops a little bit
  3. Sustain
    The volume holds constant for a period
  4. Release
    The sound starts to fade out.

This is known as the ADSR envelope. The following is a visualization of the ADSR envelope.


You may think of the envelope as a multiplier function. If we apply the envelope to our pure tone sine wave, the result would become :


Simplified Model

While ADSR is a good mathematical model for musical intrusment, it is a bit too complicated for our simple program. Hence we will use a simpler model. Our new model will contain two phases only, the sustain and the release phase. To further simplified the model, we will use linear fade out. The multiplier function would become :

Implementation


The implementation of linear fade out is very simple. It just involves a few lines of modifications of the beeping program in part 1.
// modifications of Beep.java
      double fade=1;
      int decay=sampleLength*1/3;  // start fade out at 2/3 of the total time
      if (i>=sampleLength-1-decay) fade=(double)(sampleLength-1-i)/decay;
 
      short amplitude = (short) (volume*fade*sinValue);


Full Source Code

/******************************************************************************
* File : FadeBeep.java
* Author : http://java.macteki.com/
* Description :
*   Play a pure tone with specified frequency, with fade out effect
* Tested with : JDK 1.6
******************************************************************************/
 
class FadeBeep
{
 
  static void beep(double frequency, int duration) throws Exception
  {
     
    int nChannel = 1;         // number of channel : 1 or 2
 
    // samples per second
    float sampleRate = 16000;  // valid:8000,11025,16000,22050,44100
    int nBit = 16;             // 8 bit or 16 bit sample
 
    int bytesPerSample = nChannel*nBit/8;
 
    double durationInSecond = (double) duration/1000.0;
    int bufferSize = (int) (nChannel*sampleRate*durationInSecond*bytesPerSample);
    byte[] audioData = new byte[bufferSize];
 
    // "type cast" to ShortBuffer
    java.nio.ByteBuffer byteBuffer = java.nio.ByteBuffer.wrap(audioData);
    java.nio.ShortBuffer shortBuffer = byteBuffer.asShortBuffer();
 
 
    int sampleLength = audioData.length/bytesPerSample;
 
    // generate the sine wave
    double volume = 8192;   // 0-32767
    double PI = Math.PI;
    for(int i = 0; i < sampleLength; i++){
      double time = i/sampleRate;
      double freq = frequency;
      double angle = 2*PI*freq*time;
      double sinValue = Math.sin(angle);
 
      double fade=1;
      int decay=sampleLength*1/3;  // start fade out at 2/3 of the total time
      if (i>=sampleLength-1-decay) fade=(double)(sampleLength-1-i)/decay;
 
      short amplitude = (short) (volume*fade*sinValue);

      for (int c=0;c<nChannel;c++)
      {
        shortBuffer.put(amplitude);
      }
 
    }//end generating sound wave sample
 
 
    boolean isSigned=true;
    boolean isBigEndian=true;
 
    // Define audio format
    javax.sound.sampled.AudioFormat audioFormat =
      new javax.sound.sampled.AudioFormat(sampleRate, nBit, nChannel, isSigned,isBigEndian);
 
 
    javax.sound.sampled.DataLine.Info dataLineInfo =
      new javax.sound.sampled.DataLine.Info(
         javax.sound.sampled.SourceDataLine.class, audioFormat);
 
    // get the SourceDataLine object
    javax.sound.sampled.SourceDataLine sourceDataLine = 
      (javax.sound.sampled.SourceDataLine)
      javax.sound.sampled.AudioSystem.getLine(dataLineInfo);
 
    sourceDataLine.open(audioFormat);
    sourceDataLine.start();
 
    // actually play the sound
    sourceDataLine.write(audioData,0,audioData.length);
 
    // "flush",  wait until the sound is completed
    sourceDataLine.drain();
 
  }
 
   
  public static void main(String[] args) throws Exception
  {
    int frequency=400;   // hz
    int duration =2000;  // milliseconds
    beep(frequency,duration);
  }
}

Result

The program will play a sound for 2 seconds, which will fade out gradually. The sound waveform is something like this (illustration only, not in accurate scale):

Monday, April 18, 2011

Sound Programming - Part 1

Beeping in Java

The objective of this article is to write a beep() method in Java. It will just play a tone in a specified frequency. Before we look into the details of the beep() method, let's have a look at the caller first.

  // main program to call the beep() method
  public static void main(String[] args) throws Exception
  {
    int frequency=400;   // hz
    int duration =2000;  // milliseconds
    beep(frequency,duration);
  }

Physics of Sound

Before we can define the beep() method, we must know the mathematical modeling of a sound wave. Mathematically, a "pure tone" can be represented by a sine wave. The following program will generate a sine wave. Just compile the program and go to the "Visualize" section below.

/******************************************************************************
* File : Sine.java
* Author : http://java.macteki.com/
* Description :
*   Create sample data points of a Sine wave
* Tested with : JDK 1.6
******************************************************************************/

class Sine
{

  static short[] makeSineSample()
  {
    double frequency = 400;
    double sampleRate = 16000;  // 16000 samples per second

    int bytesPerSample = 2;
    short[] audioData = new short[160];   // 160 sample points = 10 ms 

    int sampleLength = audioData.length;


    double volume = 8192;
    for(int i = 0; i < sampleLength; i++){
      double time = i/sampleRate;
      double angle = 2*Math.PI*frequency*time;
      double sinValue = Math.sin(angle);
      short amplitude = (short) (volume*sinValue);
      audioData[i]=amplitude;
    }

    return audioData;
  }

  public static void main(String[] args) throws Exception
  {
    short[] buffer=makeSineSample();

    for (int i=0;i<160;i++)
    {
      System.out.println(buffer[i]);
    }
  }
}

The above program will create 160 sample pixels of the sine wave with frequency 400hz. That is, the sine wave will complete 400 cycles in 1 second. If we generate 10 ms of data, there would be 4 cycles. Since the sampling rate is 16000 samples per second, 160 samples will contains 10 ms of data.

Visualize the Sample Data

First execute the program :

java Sine >out.txt
Load the output file into a excel file, then insert a graph with the sample data. You should see 4 cycles of sine wave as expected.

Java Sound API

The javax.sound.sampled package provides API to play a sound wave. All we have to do is to feed the sound wave sample data points to a SourceDataLine object. The following is a complete sample of playing a beep sound.

/******************************************************************************
* File : Beep.java
* Author : http://java.macteki.com/
* Description :
*   Play a pure tone with specified frequency
* Tested with : JDK 1.6
******************************************************************************/

class Beep
{

  static void beep(double frequency, int duration) throws Exception
  {
    
    int nChannel = 1;         // number of channel : 1 or 2

    // samples per second
    float sampleRate = 16000;  // valid:8000,11025,16000,22050,44100
    int nBit = 16;             // 8 bit or 16 bit sample

    int bytesPerSample = nChannel*nBit/8;

    double durationInSecond = duration/1000;
    int bufferSize = (int) (nChannel*sampleRate*durationInSecond*bytesPerSample);
    byte[] audioData = new byte[bufferSize];

    // "type cast" to ShortBuffer
    java.nio.ByteBuffer byteBuffer = java.nio.ByteBuffer.wrap(audioData);
    java.nio.ShortBuffer shortBuffer = byteBuffer.asShortBuffer();


    int sampleLength = audioData.length/bytesPerSample;

    // generate the sine wave
    double volume = 8192;   // 0-32767
    double PI = Math.PI;
    for(int i = 0; i < sampleLength; i++){
      double time = i/sampleRate;
      double freq = frequency;
      double angle = 2*PI*freq*time;
      double sinValue = Math.sin(angle);

      short amplitude = (short) (volume*sinValue);

      for (int c=0;c<nChannel;c++)
      {
        shortBuffer.put(amplitude);
      }

    }//end generating sound wave sample


    boolean isSigned=true;
    boolean isBigEndian=true;

    // Define audio format
    javax.sound.sampled.AudioFormat audioFormat =
      new javax.sound.sampled.AudioFormat(sampleRate, nBit, nChannel, isSigned,isBigEndian);


    javax.sound.sampled.DataLine.Info dataLineInfo =
      new javax.sound.sampled.DataLine.Info(
         javax.sound.sampled.SourceDataLine.class, audioFormat);

    // get the SourceDataLine object
    javax.sound.sampled.SourceDataLine sourceDataLine = 
      (javax.sound.sampled.SourceDataLine)
      javax.sound.sampled.AudioSystem.getLine(dataLineInfo);

    sourceDataLine.open(audioFormat);
    sourceDataLine.start();

    // actually play the sound
    sourceDataLine.write(audioData,0,audioData.length);

    // "flush",  wait until the sound is completed
    sourceDataLine.drain();

  }

  
  public static void main(String[] args) throws Exception
  {
    int frequency=400;   // hz
    int duration =2000;  // milliseconds
    beep(frequency,duration);
  }
}

Wednesday, April 13, 2011

Sorting in Java - Part 6

Concurrent MergeSort


This is part 6 of the series. It is suggested to read the whole series from the beginning.

The need for concurrency

In the past, parallel processing is a luxury for home user. Nowadays most newly made home computers are equipped with multi-processors. Mastering the technique of concurrent programming is becoming more and more important.

Multi-threading in Java

Suppose we have two processors in our system, how would we control which CPU to use ? Actually, we don't have to bother about this. The thread scheduling system should evenly distribute the running threads to the available processors. All we have to do is to create a thread for each of the independent task that can be executed concurrently.

Designing concurrent algorithm

If an algorithm is sequential in nature, multi-threading won't help to improve performance. The best way to learn concurrent programming is to try to implement an algorithm which is concurrent in nature. That is, the sub-problems are independent to each other and the sub-problems are of similar complexity. Merge Sort falls in this category.

Simple Threading in Java

  1. Implement a Runnable interface or extend a Thread class.
  2. Implement the run() method, which is the thread entry point.
  3. Start the thread.
  4. Wait for the running thread to complete.

/******************************************************************************
* File : SimpleThread.java
* Author : http://java.macteki.com/
* Description :
*   Simple Thread Demonstration.
* Tested with : JDK 1.6
******************************************************************************/

class SimpleThread extends Thread  // step 1, extends the Thread class
{
  // step 2, implements the run() method
  public void run()
  {
    System.out.println("Count down thread started.");
    String delimiter="";
    for (int i=10;i>=0;i--)
    {     
      System.out.print(delimiter+i);
      delimiter="...";
      try {Thread.sleep(1000); } catch (Exception ignore) {}      
    }
    System.out.println("\nThread end !!!");
  }

  public static void main(String[] args) throws Exception
  {
    // step 3, start the thread
    SimpleThread thread=new SimpleThread();  
    thread.start();
    
    // step 4, wait for the thread to complete,
    thread.join();

    System.exit(0);
  }
}

Writing two concurrent threads

Actually, almost all Java programs are multi-thread in nature. Even we don't start any thread explicitly, a running Java program will start many System Threads such as the IO thread and the GC thread.

System threads are handled by the system. As a multi-threading programmer, we are interested in user thread only. The main thread is the first user thread for all Java programs, its entry point is the main() method. Inside the main thread, we may start another thread. In this case, the main thread is known as a parent thread and the newly started thread is known as the child thread. And they are running in parallel.

To demonstrate this, we could rewrite the above sample so that the main thread is not just waiting. While the child thread is counting down, we may let the main thread counts up, in a faster step.

/******************************************************************************
* File : SimpleThread.java (version 2)
* Author : http://java.macteki.com/
* Description :
*   Simple Threads Demonstration.
* Tested with : JDK 1.6
******************************************************************************/

class SimpleThread extends Thread  // step 1, extends the Thread class
{
  // step 2, implements the run() method
  public void run()
  {
    System.out.println("Count down thread started.");
    String delimiter="";
    for (int i=10;i>=0;i--)
    {     
      System.out.print(delimiter+i);
      delimiter="...";
      try {Thread.sleep(1000); } catch (Exception ignore) {}      
    }
    System.out.println("\nThread end !!!");
  }

  public static void main(String[] args) throws Exception
  {
    // step 3, start the thread
    SimpleThread childThread=new SimpleThread();  
    childThread.start();

    // step 3.5, let the main thread do something so that we
    // know we are running parallel threads.
    for (int i=0;i<=10;i++)
    {
      System.out.print("[MAIN:"+i+"]");
      try { Thread.sleep(500); } catch (Exception ignore) {}
    }
    
    // step 4, wait for the child thread to complete,
    childThread.join();

    System.exit(0);
  }
}

Synchronization

In the above sample, the main thread counts up faster than the child thread. Hence the main thread completes it tasks faster and the method childThread.join() would put the main thread in a sleeping state. It will be sleeping until the child thread finish. What if the main thread is doing a more time consuming tasks ? For example, if we change Thread.sleep(500) into Thread.sleep(2000), then the child thread will complete the task much faster, in that case, there is no problem. childThread.join() will return immediately and the main thread will just continue, since it has no more task to do, it will just call System.exit(). The join() method is said to be a synchronization point because after the join() method returns control to the caller, we can be sure both the parent and the child thread have completed their tasks, no matter which thread actually completed the task earlier.

Concurrent Merge Sort

Let's recall the sequential merge sort algorithm in the previous article.

mergeSort(a,low,low+mid-1,helper,depth+1);      // sort the left sub-list
mergeSort(a,low+mid,high,helper,depth+1);       // sort the right sub-list
merge(a,low,high,helper);      // merge the sorted lists
Both sub-list are sorted in the main thread, one after another. Since they are independent tasks, why not start a child thread to sort one of the sublist ?
// sort the left sub-list using a child thread
SortingThread bThread=new SortingThread(a,low,low+mid-1,helper,depth,"bThread ");

// sort the right sub-list in the parent thread
mergeSort(a,low+mid,high,helper,depth+1);      

bThread.join();                // parent-child synchronization

merge(a,low,high,helper);      // merge the sorted lists

One important point, we don't want to start too many threads. For a system with two processors, two concurrent threads is optimal. This can be done by adding a depth variable which is increased by 1 for each recursive call. If we limit the program to start a thread only at depth <=0, then at most 1 child thread will be started.

Source code

/******************************************************************************
* File : ConcurrentMergeSort.java
* Author : http://java.macteki.com/
* Description :
*   Concurrent Merge Sort
* Tested with : JDK 1.6
******************************************************************************/

class ConcurrentMergeSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }


  public static void mergeSort(int[] a,int low,int high,int[] helper,int depth) 
  throws Exception
  {
    int length=high-low+1;
    if (length<=1) return;   // a list with only 1 element is already sorted
    int mid=length/2;

    if (depth<=0)
    {
      // sort the left sub-list using a child thread
      SortingThread bThread=new SortingThread(a,low,low+mid-1,helper,depth,"bThread ");

      // sort the right sub-list in the parent thread
      mergeSort(a,low+mid,high,helper,depth+1);      

      bThread.join();                // parent-child synchronization

      merge(a,low,high,helper);      // merge the sorted lists
    }
    else  // sequential merge sort
    {
      mergeSort(a,low,low+mid-1,helper,depth+1);      // sort the left sub-list
      mergeSort(a,low+mid,high,helper,depth+1);       // sort the right sub-list
      merge(a,low,high,helper);      // merge the sorted lists
    }
  }

  public static void merge(int[] a, int low,int high,int[] helper)
  {
    int mid=(high-low+1)/2;
    int ai=low,bi=low,ci=low+mid;

    while (ai<=high)
    {
      if (bi<=low+mid-1 && ci<=high)  // both lists contains element
      {
        helper[ai++]=(a[bi]<a[ci])?a[bi++]:a[ci++];
      }    
      else if (bi<=low+mid-1)    // only list B contains element
      {
        while (ai<=high) helper[ai++]=a[bi++];
      }
      else                    // only list C contains element
      {
        while (ai<=high) helper[ai++]=a[ci++];      
      }
    }

    // copied back the helper to the input array
    for (int i=low;i<=high;i++)
    {
      a[i]=helper[i];
    }
  }


  public static void main(String[] args) throws Exception
  {
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};

    int[] helper=new int[a.length];
    mergeSort(a,0,a.length-1,helper,0);    
    
    printArray(a);
  }
}


class SortingThread extends Thread
{
  static int threadCount;
  int threadID;
  int[] subArray=null;
  int[] helper=null;
  int depth=0;
  int low=0,high=0;
  String name="null";

  public SortingThread(int[] a, int low,int high,int[] helper,int depth, String name)
  {
    this.subArray = a;
    this.depth = depth;
    this.name = name;
    this.low=low;
    this.high=high;
    this.helper=helper;
    this.threadID=threadCount++;
    this.start();  // start the thread immediately
  } 

  // thread entry point
  public void run()
  {
    try
    {      
      ConcurrentMergeSort.mergeSort(subArray,low,high,helper,depth+1);
      subArray=null;  helper=null;  // garbage collection friendly
    } catch (Exception e)
    {
      e.printStackTrace();
    }
  }
}

Performance

Concurrent Merge Sort does not improve performance in a single processor platform. In a multi-processor platform, it has a good speed up. The following is the result of sorting 20 million integers in my single processor computer (Pentium M 1.73Ghz).

  • (Part 1)JavaSort n=20000000 elapse=7.341s
  • (Part 3)ShellSort n=20000000 elapse=12.438s
  • (Part 4)SimpleMergeSort n=20000000 elapse=31.966s
  • (Part 5)HelperMergeSort n=20000000 elapse=13.149s
  • (Part 6)ConcurrentMergeSort n=20000000 elapse=13.299s
Since the Insertion Sort introduced in Part 2 may takes hours or even days to sort 20 million integers, it is omitted in the test.

From the above test, concurrent merge sort is not faster than the sequential merge sort introduced in Part 5.

Let's start another test on a multiprocessor environment. The following is the result of running the test in my macbook air 2010, which is equipped with 1.86GHz Intel Core 2 Duo processor.

  • (Part 1)JavaSort n=20000000 elapse=4.593s
  • (Part 3)ShellSort n=20000000 elapse=7.925s
  • (Part 4)SimpleMergeSort n=20000000 elapse=14.329s
  • (Part 5)HelperMergeSort n=20000000 elapse=6.515s
  • (Part 6)ConcurrentMergeSort n=20000000 elapse=4.323s

This time concurrent merge sort is running significantly faster than helper merge sort(4.323s vs 6.515s). Of course we cannot expect a double speed up because the final merge() step is still sequential. For such a simple modification, it is worth the effort for this speed up.

Tuesday, April 12, 2011

Sorting in Java - Part 5

This is part 5 of the series. It is suggested to read the whole series from the beginning.

Simple Merge Sort Revisited

The simple merge sort described in the previous article allocate memory for holding the sub-lists inside the recursive function.



Under many platforms, memory allocation is expensive and sequential in nature. Hence allocating array inside recursive function would kill performance and concurrency. A better method is to allocate the memory in the initialization phase and pass the helper array as temporary storage.

The first modification is stop allocating memory for the sublists. Instead of using physical storage for the sublists, we divide the original array into two logical sublists. We accomplish this by first finding the mid point of the array index. For example, if the array contains 8 elements, then the mid point is
mid = n/2 = 8/2 = 4 
It follows that a[0] .. a[3] should be in the left sublist, and the element a[4] .. a[7] should be in the right sublist. Put it in a more precise way :
left sublist  = { a[0], a[1], ... a[mid-1] }
right sublist = { a[mid], a[mid+1], ..., a[n-1] }
For an array of 8 elements, we don't have to start with 0 and ends with 7. For example, we may want to sort the partial array a[2]..a[4]. Hence we can extend the above formula.
If we want to sort the partial array a[low]..a[high], then
mid = length / 2 = (high - low + 1) /2
left sublist  = { a[low], a[low+1], a[low+2], ... a[low+mid-1] }
right sublist = { a[low+mid], a[low+mid+1], a[low+mid+2], ... a[high] }
The above observation immediate leads to the following modification to the MergeSort algorithm.

/******************************************************************************
* File : HelperMergeSort.java
* Author : http://java.macteki.com/
* Description :
*   Implementation of Merge Sort with a helper array
* Tested with : JDK 1.6
******************************************************************************/

class HelperMergeSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }

  

  public static void mergeSort(int[] a,int low,int high,int[] helper)
  {
    int length=high-low+1;
    if (length<=1) return;   // a list with only 1 element is already sorted
    int mid=length/2;    
    
    mergeSort(a,low,low+mid-1,helper);      // sort the left sub-list
    mergeSort(a,low+mid,high,helper);       // sort the right sub-list
    merge(a,low,high,helper);      // merge the sorted lists
  }

  // merge the left and right sublists into the helper array.
  // the sorted helper is then copied back to the original array a[].
  public static void merge(int[] a, int low,int high,int[] helper)
  {
    int mid=(high-low+1)/2;
    int ai=low,bi=low,ci=low+mid;

    while (ai<=high)
    {
      if (bi<=low+mid-1 && ci<=high)  // both lists contains element
      {
        // append the smaller one to the result.  
        helper[ai++]=(a[bi]<a[ci])?a[bi++]:a[ci++];
      }    
      else if (bi<=low+mid-1)    // only the left sub-list contains element
      {
        while (ai<=high) helper[ai++]=a[bi++];
      }
      else                      // only the right sub-list contains element
      {
        while (ai<=high) helper[ai++]=a[ci++];      
      }
    }

    // copied back the helper to the input array
    for (int i=low;i<=high;i++)
    {
      a[i]=helper[i];
    }
  }


  public static void main(String[] args) throws Exception
  {
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,
             23,97,94};

    int[] helper=new int[a.length];
    mergeSort(a,0,a.length-1,helper);    
    
    printArray(a);
  }
}

Next

We have removed the big concurrency killer with the helper array. We should go concurrent now. In the next section we will implement a concurrent merge sort that performs much better in multiprocessor environment.

Sunday, April 10, 2011

Sorting in Java - Part 4

This is part 4 in the series. It is suggested to read the whole series from the beginning.


Simple Merge Sort


Merge Sort is an example of divide and conquer strategy for problem solving. It divides a big problem into smaller sub-problem, until the small problem has a trivial solution. Let's take the following unsorted list as an example.
[86,29,29,20,91,78,73,13]

We divide the list into two smaller sub-lists, by chopping it in the middle.
[86,29,29,20]  [91,78,73,13]

Sort the individual sub-lists with any methods you have on hand. (For example, shell sort in the previous article.)
[20,29,29,86]  [13,73,78,91]

Then merge the sub-lists to create a sorted list. Here is the merging algorithm.
  • Compare the first element of both lists
  • [20,29,29,86]  [13,73,78,91]
    
  • Remove the smaller element and append it to the result list.
    Sublist : [20,29,29,86]  [73,78,91]
    Result  : [13]
    
  • Repeating the above steps, compare the first element of both lists.
    [20,29,29,86]  [73,78,91]
    
  • Remove the smaller element and append it to the result list.
    Sublist : [29,29,86]  [73,78,91]
    Result  : [13 20]
    
  • Repeating the above steps until one of the sub-lists is empty, then append the rest of the other sub-list to the result. That will finally produce a merge sorted list.
    Sublist : [] []
    Result  : [13 20 29 29 73 78 86 91]
    


The merge() method

The above algorithm leads directly to the following implementation.

// merge list B and list C, result stored in list A
  // Note that list B and list C are already sorted.
  public static void merge(int[] a, int[] b, int[] c)
  {
    int ai=0,bi=0,ci=0;  // index of list A,B and C

    while (ai<a.length)
    {
      if (bi<b.length && ci<c.length)  // both lists contains element
      {
        // append the smaller one to the result.
        a[ai++]=(b[bi]<c[ci])?b[bi++]:c[ci++];  
      }    
      else if (bi<b.length)    // only list B contains element
      {
        while (ai<a.length) a[ai++]=b[bi++];
      }
      else                    // only list C contains element
      {
        while (ai<a.length) a[ai++]=c[ci++];      
      }
    }
  }

Merge Sort - the first implementation

Once we have the merge() method ready, we can use the divide and conquer strategy to implements the mergeSort() method. The algorithm is :

  • Divide the list into two halves (two sublists)
  • Sort the two sublist with any sorting method on hand, that of course includes mergeSort() !
  • Merge the two sorted sublist


The problem size is reduced by half for each recursive call, until it reach a trivial problem, a list that contains only 1 element. Then we can stop the recursion there.

public static void mergeSort(int[] a)
  {
    if (a.length<=1) return;   // a list with only 1 element is already sorted
    int mid=a.length/2;        // divided into half
    int r=a.length%2;          // remainder

    // split into two lists
    int[] b=new int[mid];
    int[] c=new int[mid+r];

    for (int i=0;i<mid;i++)
    {
      b[i]=a[i];
      c[i]=a[mid+i];
    }
    
    c[mid+r-1]=a[a.length-1];  // handle the case when a.length is odd

    mergeSort(b);      // sort the sub-list
    mergeSort(c);      // sort the sub-list
    merge(a,b,c);      // merge the sorted lists
  }

Complete Source Code

/******************************************************************************
* File : SimpleMergeSort.java
* Author : http://java.macteki.com/
* Description :
*   A straight forward implementation of Merge Sort
* Tested with : JDK 1.6
******************************************************************************/

class SimpleMergeSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }



  public static void mergeSort(int[] a)
  {
    if (a.length<=1) return;   // a list with only 1 element is already sorted
    int mid=a.length/2;        // divided into half
    int r=a.length%2;          // remainder

    // split into two lists
    int[] b=new int[mid];
    int[] c=new int[mid+r];

    for (int i=0;i<mid;i++)
    {
      b[i]=a[i];
      c[i]=a[mid+i];
    }
    
    c[mid+r-1]=a[a.length-1];  // handle the case when a.length is odd

    mergeSort(b);      // sort the sub-list
    mergeSort(c);      // sort the sub-list
    merge(a,b,c);      // merge the sorted lists
  }

  // merge list B and list C, result stored in list A
  public static void merge(int[] a, int[] b, int[] c)
  {
    int ai=0,bi=0,ci=0;  // index of list A,B and C

    while (ai<a.length)
    {
      if (bi<b.length && ci<c.length)  // both lists contains element
      {
        // append the smaller one to the result.
        a[ai++]=(b[bi]<c[ci])?b[bi++]:c[ci++];  
      }    
      else if (bi<b.length)    // only list B contains element
      {
        while (ai<a.length) a[ai++]=b[bi++];
      }
      else                    // only list C contains element
      {
        while (ai<a.length) a[ai++]=c[ci++];      
      }
    }
  }


  public static void main(String[] args) throws Exception
  {
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};

    mergeSort(a);    
    
    printArray(a);
  }
}

Advantages of Merge Sort

Merge Sort has several advantages :
  1. It is fast. It has n log(n) computation complexity.
  2. It is stable. Elements with equal value don't change their relative position during sorting. This is a desirable feature for multiple keys sorting. For example, sort the list of members by zip code first, then by name. In this case, members with same name should not change relative order because their zip code is already sorted.
  3. It is intuitive and the idea is easy to understand.
  4. The divide and conquer strategy is parallel in nature and we can easily implement a concurrent merge sort in multiprocessor environment.

Disadvantages

  1. merge sort typically requires additional storage space proportional to the length of the original array.
  2. The straight forward implementation repeatedly allocate memory, which is a performance killer. It is also a concurrency killer since memory allocation leads to heap contention problem. That is, multiple threads are competing to access the same heap.

Next

We will present a better version of merge sort which is more concurrency friendly. And a simple concurrent implementation will be shown.

Sorting in Java - Part 3

This is part 2 in the series. It is suggested to read the whole series from the beginning.


Sorting by phases


First let's define the term "h-sorted list". An h-sorted list is a list of numbers which have the following properties.
  • If we start at any point, highlight every h-th number in the sequence, the highlight list would look sorted.
Consider the following list of numbers.
[86,29,29,20,91,78,73,13]

Let's start at position 0 and look at every 3-rd element.
[86,29,29,20,91,78,73,13]

In order to fulfill the 3-sorted criteria, we sort the highlighted elements now.

[20,29,29,73,91,78,86,13]

The criteria requires that we can start at any point, so we start at position 1 and highlight every 3-rd element.
[20,29,29,73,91,78,86,13]

Sort them :
[20,13,29,73,29,78,86,91]

The next step is highlighting every 3-rd element starting at position 2. Since the highlight list is already sorted, nothing need to be done.
[20,13,29,73,29,78,86,91]

At this point, we have highlight every element once, so we could stop here.
We have just created a 3-sorted list. That means we can start at any point, highlight every 3-rd elements, and the highlight list will look sorted.

2-sorted list

A 2-sorted list can be created in a similar way. Start at position 0 and highlight every 2nd element.
[20,29,29,73,91,78,86,13]

Sort the highlighted elements.
[20,29,29,73,86,78,91,13]

We must also start at position 1 and highlight every 2nd element.
[20,29,29,73,86,78,91,13]

Sorting the highlight element, and we now have a 2-sorted list.
[20,13,29,29,86,73,91,78]

1-sorted list

A 1-sorted list is just a sorted list, that means no matter which point we start, we can highlight every single element, and the highlight list would look sorted.

So, we just highlight every element.
[20,13,29,29,86,73,91,78]

Sort them, this is a 1-sorted list, and this is the desired result
[13,20,29,29,73,78,86,91]


In the sample above, we create h-sorted lists for h={3,2,1}. The sequence 3,2,1 is the h-sequence. We can use any h-sequence as long as it ends with 1. Of course, it must start with a number less than the length of the unsorted list.

Creating h-sorted list is very simple, we may use a modified version of Insertion Sort, which was described in the previous article.

The idea is that we can start at any element, LOOK BACKWARDS at every h-th element, and those elements should look sorted.

// create h-sorted list using insertion sort
  public static void insertionSort(int[] a,int h)
  { 
    for (int i=0;i<a.length;i++)   // we can start at any point in the list
    {
      int element=a[i];     // get the element
      int j=i;              // j : the scanning pointer
      for (j=i;j>=h;j-=h)   // scan backwards, look at every h-th element
      {
        if (element<a[j-h]) // not the correct position yet
        {
            a[j]=a[j-h];    // shift to the right to make room for element
        }
        else break;     // correct position found, break the scanning loop
      }
      a[j] = element;    // insert element in the correct position
    }
  }

Note that when h=1, it is just the normal insertion sort. You may look at the insertionSort() method in the previous article side by side with this one.

Why do we generate 3-sorted list and 2-sorted list before generating the 1-sorted list ? It is because the performance of Insertion Sort is very much depends on the initial ordering of the list. A nearly sorted list performs much better than a randomly order list. Generating 3-sorted and 2-sorted list will improve the initial ordering, with relatively little effort. It is because the scanning process is much faster. Instead of scanning every single element, we just need to scan every 3rd elements.

Shell Sort


Shell sort is name after its inventor, Donald Shell, who published the algorithm in 1959. The idea behind Shell Sort is we can significantly improve the performance of Insert Sort if we can find some ways to improve the ordering of the list. Intuitively, generating h-sorted list is a effective way to improve the ordering.

Shell sort typically uses a decreasing h-sequence which ends with 1. One such sequence is {16,8,4,2,1}. That means it will gradually improve the ordering of the list by first generating the 16-sorted list, then the 8-sorted list, then the 4-sorted list, then the 2-sorted list, and finally the 1-sorted list, which is the desired result.

However, computer scientists found that it is not a particularly good sequence in terms of sorting efficiency. A better sequence typically in use is :
1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9,1

This sequence is derived from the Fibonacci sequence :

For n = 1, 1, 2, 3, 5, 8, 13, 21,...(Fibonacci sequence)
let g=1.618 (golden ratio)
compute h=n2g  for every n
So h = 1,1,9,34,182,836,... 
Removing the first 1 yields our h-sequence (in reverse order)

For example, for a initial list of 50 elements, we will first generate the 34-sorted list, then the 9-sorted list and finally the 1-sorted list.


Source code

/******************************************************************************
* File : ShellSort.java
* Author : http://java.macteki.com/
* Description :
*   Demonstration of Shell Sort
* Tested with : JDK 1.6
******************************************************************************/

class ShellSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }


  // Fibonacci seq (n) :1,1,2,3,5,8,13,21,34,55,89,144,233,377
  // pow(n, 2*golden_ratio) : 1,1,9,34,182,836,... (this is the h-sequence in reverse order)
  static int[] hTable={
    1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 
    90358, 19001, 4025, 836, 182, 34, 9,1 };

  public static void shellSort(int[] a)
  {
    int n=a.length;
    int k=0;
    for (k=0;k<hTable.length;k++)
    {
      int gap=hTable[k];
      if (gap < n) insertionSort(a,gap);
    }
  }

  public static void insertionSort(int[] a,int h)
  {
    for (int i=0;i<a.length;i++) // we can start at any position in the list
    {
      int element=a[i];     // get the element
      int j=i;              // j : the scanning pointer
      for (j=i;j>=h;j-=h)   // scan backwards, looking at every h-th element
      {
        if (element<a[j-h]) // not the correct position yet
        {
            a[j]=a[j-h];    // shift to the right to make room for element
        }
        else break;     // correct position found, break the scanning loop
      }
      a[j] = element;    // insert element in the correct position
    }
  }

  public static void main(String[] args) throws Exception
  {
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};

    shellSort(a);    
    
    printArray(a);
  }

}

Performance

Although Shell Sort is just a modified version of Insertion Sort, its idea is not as trivial. Does it worth the effort to complicate the algorithm ? The answer is "yes" for most of the time. Because it is much faster than the ordinary insertion sort in many cases. To give a rough idea, in one of my test, Insertion Sort toke 22.8 minutes to sort a million random integers, whereas ShellSort just toke 0.5 second on the same set of input. That is a impressive speed up and therefore ShellSort is a worthy modification of Insertion Sort.

Thursday, April 7, 2011

Sorting in Java - Part 2

This is part 2 in the series. It is suggested to read the whole series from the beginning.

Insertion Sort


It is one of the simplest sorting algorithm and the idea is straight forward. And it is a more human way of sorting. Alright, bubble sort is also simple to code but few humans would actually use bubble sort to sort physical objects in real world. Since Insertion Sort is more human-like and therefore it would be more easy to understand, so we will first implement this algorithm.

Algorithm

For any unsorted arrays, split it into two lists, one is known as the sorted list, the other is the unsorted list, initially the sorted list contains no element. Repeat the following :
  • Pick an element from the unsorted list, this is the insertionElement.
  • Scan from the end of the sorted list, until the correct position for the insertion element is found.
  • Insert the element at the correct position

During the scanning process, the entries in the sorted list is shifted to the right one by one to make room for the insertionElement.

Insertion Sort in Action

As I said, Insertion Sort is a more human way of sorting. So let's look at a real life example. Suppose we are playing the game of Mahjong. And we have a list of four sorted tiles in front of us. We draw a new tile, the five of circle from the closed tiles (think of it as an unsorted list).

  • Pick an element from the unsorted list, this is the insertionElement.





  • Scan from the end of the sorted list, until the correct position for the insertion element is found.




  • Insert the element at the correct position






  • Source code


    The following is a straight forward implementation.

    /******************************************************************************
    * File : InsertionSort.java
    * Author : http://java.macteki.com/
    * Description :
    *   Demonstration of Insertion Sort
    * Tested with : JDK 1.6
    ******************************************************************************/
    
    class InsertionSort
    {
    
      public static void printArray(int[] a)
      {
        String delim="";
        for (int i=0;i<a.length;i++)
        {
          System.out.print(delim+a[i]);
          delim=",";   // add delimiter after first element
        }
        System.out.println();
      }
    
      public static void insertionSort(int[] a)
      {
        // i=size of the sorted list, it is increased by 1 for every pass
        for (int i=0;i<a.length;i++) 
        {
          int element=a[i];    // get an element from the unsorted list
          int j=i;             // j : the scanning pointer
          for (j=i;j>=1;j--)   // scan backwards from the end of the sorted list
          {
            if (element<a[j-1]) // not the correct position yet
            {
                a[j]=a[j-1];    // shift to the right to make room for element
            }
            else break;     // correct position found, break the scanning loop
          }                 
          a[j] = element;   // insert element in the correct position
        } // loop for next i, the sorted list size will be increased by 1
      }
    
      public static void main(String[] args) throws Exception
      {
        int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};
    
        insertionSort(a);    
        
        printArray(a);
      }
    }
    

    Sorting in Java - Part 1

    Information on sorting algorithms can be found everywhere. Nevertheless, I would still include a section on this topic for the following reasons.
    1. This is a programming blog. It looks "more complete" if it contains a section on sorting.
    2. Something new can always be learned by looking at other people's source code. So why not have a look at how Macteki implements various sorting algorithms in Java ?

    Sorting in Java - The Easy Way

    The easiest way to sort in any programming language is, of course, using the language API if it is available. Therefore, let's start our journey with a simple API, java.util.Arrays.sort().

    /******************************************************************************
    * File : JavaSort.java
    * Author : http://java.macteki.com/
    * Description :
    *   Demonstrate the use of java.util.Arrays.sort
    * Tested with : JDK 1.6
    ******************************************************************************/
    
    class JavaSort
    {
    
      public static void printArray(int[] a)
      {
        String delim="";
        for (int i=0;i<a.length;i++)
        {
          System.out.print(delim+a[i]);
          delim=",";   // add delimiter after first element
        }
        System.out.println();
      }
    
    
      public static void main(String[] args) throws Exception
      {
        // array to be sorted
        int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};
    
        java.util.Arrays.sort(a);   // sort using java API
    
        // print the sorted array    
        printArray(a);
    
      }
    }
    


    Descending Sort

    The above sample sorts the integer array in ascending order. There are at least two ways to make a descending output using the same API. The first way is simple : use special indexing technique to change the order of output in the printArray() method.

    // printArray in reverse order
      public static void printArray(int[] a)
      {
        String delim="";
        for (int i=0;i<a.length;i++)
        {
          int reindex = a.length-i-1;
          System.out.print(delim+a[reindex]);
          delim=",";   // add delimiter after first element
        }
        System.out.println();
      }
    

    This is a kind of "logical sorting". Physically we don't change the position of the elements in the array. But logically we sort it in descending order using a implied "index" array. You can create explicit index array if you wish, but that's just a waste of space in this simple example.

    Descending Sort - Using customized Comparator

    If you wish to sort the array physically, it is still possible to use the API. However, we need to pass an additional parameter to tell Java how to compare two elements.

    java.util.Arrays.sort(a, new DescendingComparator());
    

    We must implement the DescendingComparator. Here is a simple implementation.
    class DescendingComparator implements java.util.Comparator<Integer>
    {
      public int compare(Integer a,Integer b)
      {
        return b-a;
      }
    }
    

    According to the official documentations, we must implements the compare method such that it has the following properties :

    1. It must return a negative value if element a is logically smaller than element b
    2. It must return a positive value if element a is logically bigger than element b
    3. It must return zero if element a is logically equal to element b

    Note the term "logically". For example, 5 is physically greater than 3, but in our logical order (descending order), it is smaller than 3, smaller in the sense of its logical position, not in the sense of its value.

    Full sample given below.

    /******************************************************************************
    * File : DescendingSort.java
    * Author : http://java.macteki.com/
    * Description :
    *   Demonstrate the use of java.util.Arrays.sort with a customized Comparator
    * Tested with : JDK 1.6
    ******************************************************************************/
    
    class DescendingSort
    {
    
      public static void printArray(Integer[] a)
      {
        String delim="";
        for (int i=0;i<a.length;i++)
        {
          System.out.print(delim+a[i]);
          delim=",";   // add delimiter after first element
        }
        System.out.println();
      }
    
    
      public static void main(String[] args) throws Exception
      {
        Integer[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};
    
        java.util.Arrays.sort(a, new DescendingComparator());
        
        printArray(a);
    
      }
    }
    
    // Use a separate source file if you wish.
    class DescendingComparator implements java.util.Comparator<Integer>
    {
      public int compare(Integer a,Integer b)
      {
        return b-a;
      }
    }
    

    Next

    Some simple sorting algorithms in Java will be presented in the next article.

    Monday, April 4, 2011

    Moving Objects and Sprite Manager - Part 7

    This will be the end of the series. It is suggested to read the whole series from the beginning.


    Extending the Sprite class


    In the conclusion of the previous article, I said you could do really interesting thing if you understand the basic Sprite class well enough. Let's make a small sample on this. Up to now all bunnies look the same, we are going to add a "panic" bunny to the sprite list.

    How does a "panic" bunny look like ? It face will turn red and it will be moving restlessly. Let make a reddish sprite first. How to make a sprite looks more reddish ? It is simple. For every pixel, we just reduce the green and blue component by half. This effectively increases the weighting of the red component in the image. And it will look reddish.

    We don't have to rewrite the Sprite class. All we need is to extend it.
    /******************************************************************************
    * File : ReddishSprite.java
    * Author : http://java.macteki.com/
    * Description :
    *   A sprite which is more "reddish" than normal
    * Tested with : JDK 1.6
    ******************************************************************************/
    
    import java.awt.image.BufferedImage;
    
    class ReddishSprite extends Sprite
    {
      public ReddishSprite(BufferedImage img)
      {
        super(img);
        this.image = makeReddishImage(this.image);
      }
    
      // make it reddish
      private BufferedImage makeReddishImage(BufferedImage tmpImage)
      {
        int h=tmpImage.getHeight(null);
        int w=tmpImage.getWidth(null);
    
        BufferedImage resultImage=new BufferedImage(w,h,BufferedImage.TYPE_INT_ARGB);
     
        for (int y=0;y<h;y++)
          for (int x=0;x<w;x++)
          {
            int color=tmpImage.getRGB(x,y);
            // get A,R,G,B value
            int A=color & 0xff000000;
            int R=(color & 0x00ff0000) >>> 16;
            int G=(color & 0x0000ff00) >>> 8;
            int B=color & 0x000000ff;
            // reduce the green and blue component by half
            G/=2;
            B/=2;
            // packed back to a color value
            color = A | (R<<16) | (G<<8) | B;
            
            resultImage.setRGB(x,y,color);
          }
     
     
        return resultImage;
      }
      
    }
    
    Next, we modify the method initSpriteList() in SpriteManager.java. Originally it just adds 50 bunnies to the list, now it adds one more "panic" bunny to the list.
    // add 50 bunnies sprites to the sprite list  
      public void initSpriteList() throws Exception
      {
        BufferedImage image = javax.imageio.ImageIO.read(new java.io.File("bunny_sprite.png"));
     
        java.util.Random random=new java.util.Random();
        for (int i=0;i<50;i++)
        {
          Sprite sprite=new Sprite(image);
          sprite.x=50+16*random.nextInt(20);
          sprite.y=250+4*random.nextInt(20);
          sprite.relativeSpeed=1+(i%3);   // range from 1 to 4
          sprite.gestureWait=8;           // change it to 1 to see what happen
          spriteList.add(sprite);
        }
    
        // add a panic bunny
        ReddishSprite redSprite=new ReddishSprite(image);
        redSprite.x=0;
        redSprite.y=250;
        redSprite.relativeSpeed=1;   // full speed  (look more panic)
        redSprite.gestureWait=2;     // fast rhythm (look more restless)
        spriteList.add(redSprite);   // add to the sprite list just like the normal sprite
      }
    

    Adding a Boss

    To make thing more interesting, we extend the Sprite class again and make a "boss" bunny. It is double in size and it it moving slower. It also has the ability to fly in the sky.

    /******************************************************************************
    * File : BigSprite.java
    * Author : http://java.macteki.com/
    * Description :
    *   A "Boss" Sprite
    * Tested with : JDK 1.6
    ******************************************************************************/
    
    import java.awt.image.BufferedImage;
    
    class BigSprite extends Sprite
    {
    
      // pre-defined source regions
      private int[][][] frameRect = // [direction][gesture][x,y,w,h]
        {
        {{ 0,  0,64,64}, {64,  0,64,64}, {128,  0,64,64}, {192,  0,64,64} },  // left
        {{ 0, 64,64,64}, {64, 64,64,64}, {128, 64,64,64}, {192, 64,64,64} },  // right
        {{ 0,128,64,64}, {64,128,64,64}, {128,128,64,64}, {192,128,64,64} },  // down
        {{ 0,192,64,64}, {64,192,64,64}, {128,192,64,64}, {192,192,64,64} }   // up
        };  
    
      public int[] getImageBound(int direction, int gesture)
      {
        return frameRect[direction][gesture];
      }
    
      public BigSprite(java.awt.image.BufferedImage img)
      {
        super(img);
        this.image = makeBlue(this.image);
        this.image = makeDoubleSizeImage(this.image);
      }
    
      // make it blue
      private BufferedImage makeBlue(BufferedImage tmpImage)
      {
        int h=tmpImage.getHeight(null);
        int w=tmpImage.getWidth(null);
    
        BufferedImage resultImage=new BufferedImage(w,h,BufferedImage.TYPE_INT_ARGB);
     
        for (int y=0;y<h;y++)
          for (int x=0;x<w;x++)
          {
            int color=tmpImage.getRGB(x,y);
            // get A,R,G,B value
            int A=color & 0xff000000;
            int R=(color & 0x00ff0000) >>> 16;
            int G=(color & 0x0000ff00) >>> 8;
            int B=color & 0x000000ff;
            // reduce the red and green component by half
            // double the blue component
            R/=2;  G/=2;  B*=2;
            // packed back to a color value
            color = A | (R<<16) | (G<<8) | B;
            
            resultImage.setRGB(x,y,color);
          }
     
     
        return resultImage;
      }
    
      // scale up the image by a factor of 2
      private BufferedImage makeDoubleSizeImage(BufferedImage tmpImage)
      {
        int h=tmpImage.getHeight(null);
        int w=tmpImage.getWidth(null);
     
        BufferedImage resultImage=new BufferedImage(w*2,h*2,BufferedImage.TYPE_INT_ARGB);
    
        java.awt.Graphics2D gr=(java.awt.Graphics2D) resultImage.getGraphics();
        java.awt.geom.AffineTransform transform=gr.getTransform();
        transform.scale(2,2);
        gr.setTransform(transform);
        gr.drawImage(tmpImage,0,0,null);
     
        return resultImage;
      }
    
      // Boss Sprite is flying in the sky
      public int[] getActiveRegion()
      {
        // upperLeft corner(x,y),  lowerRight corner(x,y)
        return new int[]{ 0,0,750,150};  // upper area of the screen.
      }
      
    }
    

    Of course we need to modify initSpriteList() again, add the boss sprite code just below the panic sprite code.

    // add a panic bunny
        ReddishSprite redSprite=new ReddishSprite(image);
        redSprite.x=0;
        redSprite.y=250;
        redSprite.relativeSpeed=1;   // full speed (look more panic)
        redSprite.gestureWait=2;     // fast rhythm (look more restless)
        spriteList.add(redSprite);   // add to sprite list just like a normal sprite
    
        // add a Boss Bunny
        BigSprite bossSprite=new BigSprite(image);
        bossSprite.x=50;
        bossSprite.y=100;             // boss is flying in the sky
        bossSprite.relativeSpeed=8;   // boss move much slower due to its size
        bossSprite.gestureWait=16;    // boss is more reluctant to change gesture
        spriteList.add(bossSprite);   // add to sprite list just like a normal sprite
    

    Result

    If you are doing everything correctly, you should see a flying boss and a panic(red) bunny inside the crowd of the normal bunnies.

    Acknowledgement

    1. bunny_sprite.png is provided by Moosader :
      http://moosader.deviantart.com/art/Public-domain-bunny-sprite-151156167

    2. background.jpg is provided by Jesccia Crabtree
      http://www.jessicacrabtree.com/journal1/public-domain-nature-photos

    Next

    This is the end of the series. If you like it, post a comment. If you don't like it, also post a comment. Right now I am thinking of the next programming topic. So I cannot tell what is going next. Anyway, I would try hard to update this site frequently. If you'd like to propose a topic, you can leave a comments in this blog under any articles. I may share something on it if I have the necessary skills and knowledges.

    Sunday, April 3, 2011

    Moving Objects and Sprite Manager - Part 6

    This is part 6 of the series. It is suggested to read the whole series from the beginning.

    Sprite Manager


    If you have only one sprite, you may not need a sprite manager. Sprite Manager is a program that handle multiple sprites. With today computer power, it is possible to make animation or game with hundreds or even thousands of moving sprites using a high level language like Java.


    Encapsulation

    Encapsulation is a information hiding principle in object oriented programming. A Sprite is a good candidate for encapsulation. We will define the Sprite class in a top down approach. First we define the attributes of the sprite.

    class Sprite 
    {
      public BufferedImage image = null;   // image of the sprite
    
      // initial coordinates and velocity of the sprite
      public int x=50, y=250;
      private int xv=2;
      private int yv=0;
      
      private int animationFrame=0;   // incremented for every frame.
      private int gesture=0;          // animation gesture (0-3)
      public  int relativeSpeed=2;    // update position at every 2 frames (moving half slower)
      public  int gestureWait=8;      // update animation gesture at every 8 frames
    }
    

    Using too many public variables is considered bad programming practices. But as I said, this site is focused on simplicity and readability. Using too many getters and setters will mess up the source code. I am making a demonstration for programmers, not creating a text book for university students. By the way, you may always convert the public variables to private and create getters and setters for them if you wish.

    This class is going to handle 128x128 pixels sprite only. And the sprite must be evenly divided into 16 regions of 32x32 pixels.

    // pre-defined source regions
      private int[][][] frameRect = // [direction][gesture][x,y,w,h]
        {
        {{ 0, 0,32,32}, {32, 0,32,32}, {64, 0,32,32}, {96, 0,32,32} },  // left
        {{ 0,32,32,32}, {32,32,32,32}, {64,32,32,32}, {96,32,32,32} },  // right
        {{ 0,64,32,32}, {32,64,32,32}, {64,64,32,32}, {96,64,32,32} },  // down
        {{ 0,96,32,32}, {32,96,32,32}, {64,96,32,32}, {96,96,32,32} }   // up
        };  
    

    How about sprite of other sizes ? You may extends the Sprite class. An example is given below.
    // handle sprite with 256x256 pixels, composed of 16 regions with 64x64 pixels.
    class BigSprite extends Sprite
    {
    
      // pre-defined source regions
      private int[][][] frameRect = // [direction][gesture][x,y,w,h]
        {
        {{ 0,  0,64,64}, {64,  0,64,64}, {128,  0,64,64}, {192,  0,64,64} },  // left
        {{ 0, 64,64,64}, {64, 64,64,64}, {128, 64,64,64}, {192, 64,64,64} },  // right
        {{ 0,128,64,64}, {64,128,64,64}, {128,128,64,64}, {192,128,64,64} },  // down
        {{ 0,192,64,64}, {64,192,64,64}, {128,192,64,64}, {192,192,64,64} }   // up
        };  
    
      public int[] getImageBound(int direction, int gesture)
      {
        return frameRect[direction][gesture];
      }
    
    }
    

    Artificial Intelligence

    Simple intelligence will be given to the bunny sprite. It is defined in the move() method of the Sprite class. It follows two simple rules :

    1. It changes direction if it hit the border of the active region.
    2. It changes direction if it feels bored. It has 0.5% chance of feeling bored while moving.

    What is active region ? That depends on the context. For the bunny sprite, it should be running on the ground but not flying in the sky, therefore the active region is the lower half of the background.

    You may extend the Sprite class and override the move() method to include more sophisticated intelligence.

    List of Sprites

    Sprite Manger manges multiple sprite. It naturally forms a list of sprite and the data structure java.util.ArrayList is a good choice for holding the sprites. Adding and deleting sprite can be done with standard ArrayList API. For the animation part, we need to loop over all sprite in an animation frame.

    // spriteList is of type java.util.ArrayList
      private void animateFrame()
      {
        java.awt.Graphics2D gr=(java.awt.Graphics2D) drawingBoard.getGraphics();
        gr.drawImage(backgroundImage,0,0,this);
    
        for (int i=0;i<spriteList.size();i++)
        {      
          Sprite sprite=spriteList.get(i);
          sprite.move();
          sprite.draw(gr);
        }
      }
    

    The move() method and draw() method of the Sprite class is straight forward. It is not difficult to understand if you have read the complete series of the articles. Details will be presented in Sprite.java in the source code section.

    The spriteList is initialized as follows :

    // add 50 bunnies sprites to the sprite list  
      public void initSpriteList() throws Exception
      {
        BufferedImage image = javax.imageio.ImageIO.read(new java.io.File("bunny_sprite.png"));
     
        java.util.Random random=new java.util.Random();
        for (int i=0;i<50;i++)
        {
          Sprite sprite=new Sprite(image);
          sprite.x=50+16*random.nextInt(20);
          sprite.y=250+4*random.nextInt(20);
          sprite.relativeSpeed=1+(i%3);   // range from 1 to 4
          sprite.gestureWait=8;           // change it to 1 to see what happen
          spriteList.add(sprite);
        }
    
      }
    

    The above method adds 50 sprites to the list. As I said, the sprite manager is capable of handling thousands of sprites. So you may change the value from 50 to 1000 to see what happened.

    Demonstration

    The background image in the previous articles is too small. We need a bigger background now otherwise it would be too crowded for hundreds of bunnies. Here is the background we used in this demonstration.

    Save the above image as "background.jpg"

    The bunny sprite is same as the previous articles.

    bunny_sprite.png

    The result of the demonstration is as follows. Note that the bunnies are actually running in different direction at different speed, of course I cannot show this in a static photo.

    Source code

    /******************************************************************************
    * File : SpriteManager.java
    * Author : http://java.macteki.com/
    * Description :
    *   Sprite Manager.
    *   required Sprite.java, background.jpg, bunny_sprite.png
    * Tested with : JDK 1.6
    ******************************************************************************/
     
    import java.awt.image.BufferedImage;
     
    class SpriteManager extends javax.swing.JPanel implements Runnable
    {
      // list of sprite
      java.util.ArrayList<Sprite> spriteList=new java.util.ArrayList<Sprite>();
     
      // image object for double buffering
      private BufferedImage drawingBoard;
     
      BufferedImage backgroundImage;
     
      private boolean running=false;  // animation thread
     
      public SpriteManager() throws Exception
      {
     
        // read background image 
        String jpeg_file="background.jpg";
        backgroundImage = javax.imageio.ImageIO.read(new java.io.File(jpeg_file));
     
        // set panel size to dimension of background image
        int w=backgroundImage.getWidth(this);
        int h=backgroundImage.getHeight(this);
        setPreferredSize(new java.awt.Dimension(w,h));
     
        // resize the drawing board to fit the background
        drawingBoard=new BufferedImage(w,h,BufferedImage.TYPE_INT_RGB);
     
      }
     
      // add 50 bunnies sprites to the sprite list  
      public void initSpriteList() throws Exception
      {
        BufferedImage image = javax.imageio.ImageIO.read(new java.io.File("bunny_sprite.png"));
     
        java.util.Random random=new java.util.Random();
        for (int i=0;i<50;i++)
        {
          Sprite sprite=new Sprite(image);
          sprite.x=50+16*random.nextInt(20);
          sprite.y=250+4*random.nextInt(20);
          sprite.relativeSpeed=1+(i%3);   // range from 1 to 4
          sprite.gestureWait=8;           // change it to 1 to see what happen
          spriteList.add(sprite);
        }
    
      }
     
      // override the paint() method
      public void paintComponent(java.awt.Graphics gr)
      {
        gr.drawImage(drawingBoard,0,0,this);
      }
     
      // animation thread
      public void run()
      {
        while (running)
        {
          try {
            animateFrame();
            repaint();
            Thread.sleep(30);
          } catch (Exception e)
          {
            e.printStackTrace();
          }
        }
      }
     
      private void animateFrame()
      {
        java.awt.Graphics2D gr=(java.awt.Graphics2D) drawingBoard.getGraphics();
        gr.drawImage(backgroundImage,0,0,this);
     
        for (int i=0;i<spriteList.size();i++)
        {      
          Sprite sprite=spriteList.get(i);
          sprite.move();
          sprite.draw(gr);
        }
     
      }
     
      public void start() throws Exception
      {
        initSpriteList();
        running=true;
        new Thread(this).start();
      }
     
      public void stop()
      {
        running=false;
      }
     
     
     
      public static void main(String[] args) throws Exception
      {
        javax.swing.JFrame window=new javax.swing.JFrame();
        window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
        window.setTitle("Macteki Sprite Manager");
     
        SpriteManager manager=new SpriteManager();
        window.add(manager);
        window.pack();
     
        window.setVisible(true);
     
        manager.start();
      }
      
    }
    

    Sprite.java

    /******************************************************************************
    * File : Sprite.java
    * Author : http://java.macteki.com/
    * Description :
    *   The sprite object
    * Tested with : JDK 1.6
    ******************************************************************************/
     
    import java.awt.image.BufferedImage;
     
    class Sprite 
    {
      public BufferedImage image=null;   // image of the sprite
     
      // initial coordinates and velocity of the sprite
      public int x=50, y=250;
      private int xv=2;
      private int yv=0;
      
      private int animationFrame=0;   // incremented for every frame.
      private int gesture=0;          // animation gesture (0-3)
      public  int relativeSpeed=2;    // update position at every 2 frames (moving half slower)
      public  int gestureWait=8;      // update animation gesture at every 8 frames
     
      java.util.Random random=new java.util.Random();
     
      // pre-defined source regions
      private int[][][] frameRect = // [direction][gesture][x,y,w,h]
        {
        {{ 0, 0,32,32}, {32, 0,32,32}, {64, 0,32,32}, {96, 0,32,32} },  // left
        {{ 0,32,32,32}, {32,32,32,32}, {64,32,32,32}, {96,32,32,32} },  // right
        {{ 0,64,32,32}, {32,64,32,32}, {64,64,32,32}, {96,64,32,32} },  // down
        {{ 0,96,32,32}, {32,96,32,32}, {64,96,32,32}, {96,96,32,32} }   // up
        };  
     
     
    
      public Sprite(BufferedImage img)
      {
        this.image = makeTransparent(img);
      }
    
      public BufferedImage makeTransparent(BufferedImage tmpImage)
      {
        int h=tmpImage.getHeight(null);
        int w=tmpImage.getWidth(null);
     
        BufferedImage resultImage=new BufferedImage(w,h,BufferedImage.TYPE_INT_ARGB);
     
        // assume the upperleft corner of the original image is a transparent pixel
        int transparentColor=tmpImage.getRGB(0,0);  
        for (int y=0;y<h;y++)
          for (int x=0;x<w;x++)
          {
            int color=tmpImage.getRGB(x,y);
            if (color==transparentColor) color=color & 0x00FFFFFF; // clear the alpha flag
            resultImage.setRGB(x,y,color);
          }
     
        return resultImage;
      }
     
      // activeRegion is defined by corners coordinates (x1,y1) and (x2,y2)
      public int[] getActiveRegion()
      {
        // upperLeft corner(x,y),  lowerRight corner(x,y)
        return new int[]{ 0,250,750,440};  // lower area of the screen.
      }
    
      public void move()
      {
        animationFrame++;    
        if (animationFrame % relativeSpeed==0) // control when to update the position
        {
          int bored=random.nextInt(200);
          if (bored==1) // the sprite is bored for 0.5% of the time
          {
            // if it feels bored, it changes direction
            int[] xvTable={-2,2,0,0};
            int[] yvTable={0,0,2,-2}; 
            int dir = random.nextInt(4);
            xv=xvTable[dir];  yv=yvTable[dir];
          }
     
          // move sprite to new position
          x+=xv;
          y+=yv;
     
          // get Sprite dimension
          int w=frameRect[0][0][2];  // 32
          int h=frameRect[0][0][3];  // 32
    
          int rightBound=getActiveRegion()[2];
          int leftBound=getActiveRegion()[0];
          int upperBound=getActiveRegion()[1];
          int lowerBound=getActiveRegion()[3];
           
          if (x>rightBound-w || x<leftBound) // hit border
          {
            x-=xv;      // undo movement
            xv=-xv;     // change direction of velocity
          }
     
          if (y>lowerBound-h || y<upperBound) // don't move too high or too low
          {
            y-=yv;      // undo movement
            yv=-yv;     // change direction of velocity
          }
     
        }
     
        if (animationFrame % gestureWait==0)  // control when to update gesture
        {
            gesture=(gesture+1)%4;
        }
        
      }
     
      public int[] getImageBound(int direction, int gesture)
      {
        return frameRect[direction][gesture];
      }
     
      public void draw(java.awt.Graphics2D gr)
      {
        // draw sprite at new position
     
        int direction=0;
        if (xv>0) direction=1; else if (xv<0) direction=0;
        if (yv>0) direction=2; else if (yv<0) direction=3;
        int[] srcBounds=getImageBound(direction,gesture);
        int w=srcBounds[2], h=srcBounds[3]; 
        int dx2=x+w;
        int dy2=y+h;
        int sx1=srcBounds[0], sy1=srcBounds[1], sx2=sx1+w, sy2=sy1+h;
        gr.drawImage(image,x,y,dx2,dy2,sx1,sy1,sx2,sy2,null);
     
      }
     
    }
    

    Acknowledgement

    1. bunny_sprite.png is provided by Moosader :
      http://moosader.deviantart.com/art/Public-domain-bunny-sprite-151156167

    2. background.jpg is provided by Jesccia Crabtree
      http://www.jessicacrabtree.com/journal1/public-domain-nature-photos

    Conclusion

    This article provides a simple yet flexible Sprite Manager. If you understand it well enough, you could override the Sprite class and make modifications to the SpriteManager to do really interesting things. The first thing you should try is adding more Sprites to the spriteList. You could add up to 1000 sprites without noticeable performance degradation. If you want 3000 sprites, you may need to increase the heap size. Run the program with the following parameter if memory error occurs :

    java -Xmx128m SpriteManager
    

    Moving Objects and Sprite Manager - Part 5

    This is part 5 of the series. It is suggested to read the whole series from the beginning.


    Partial drawing of image

    Let's begin by recalling our sprite image.

    bunny_sprite.png

    by Moosader


    The image is actually 128x128 pixels in size. And it is evenly divided into 16 regions. Each region is a partial image of 32x32 pixels. That composes 4 animation frames for each of the four moving directions.

    By default, the drawImage() method of a Graphics2D object will draw the whole image. You may think of a Graphics2D object as a drawing board. The drawImage() API is in fact very flexible. It allows us to select partial region of the source image to be drawn.

    Compare the following examples :
    1. gr.drawImage(spriteImage,50,50,this);
    2. gr.drawImage(spriteImage,50,50,82,82,0,0,32,32,this);
    Both versions will draw the image at position(50,50) inside the graphics object(just think of it as a drawing board). But the second version contains more parameters. It is of the form :
    gr.drawImage(spriteImage,dx1,dy1,dx2,dy2,sx1,sy1,sx2,sy2,imageObserver);
    
    where (dx1,dy1,dx2,dy2) is the bounding rectangle in the destination (the drawing board)
    (sx1,sy1,sx2,sy2) is the bounding rectangle of the source image.


    Let's write a simple example to show the two drawImage() methods.

    We just need to change the paintComponent() method in TransparentImage.java in the previous article.

    // override the paint() method
      public void paintComponent(java.awt.Graphics gr)
      {
        // draw background
        gr.drawImage(backgroundImage,0,0,this);
    
        // draw whole image (128x128 pixels)
        gr.drawImage(spriteImage,50,200,this);
        
        // draw a partial image (32x32 pixels)
        int dx1=100,dy1=100,dx2=dx1+32,dy2=dx1+32;  // target position
        int sx1=0,sy1=0,sx2=sx1+32,sy2=sy1+32;      // source region
        gr.drawImage(spriteImage,dx1,dy1,dx2,dy2,sx1,sy1,sx2,sy2,this);
      }
    

    And here comes the result.


    Defining the source regions


    The original source image actually contains 16 regions. For each directions there are four gestures for the moving sprite. We could pre-define those regions in advance using a 3 dimensional array.

    int[][][] bunnyRect = // [direction][gesture][x,y,w,h]
        {
        {{ 0, 0,32,32}, {32, 0,32,32}, {64, 0,32,32}, {96, 0,32,32} },  // left
        {{ 0,32,32,32}, {32,32,32,32}, {64,32,32,32}, {96,32,32,32} },  // right
        {{ 0,64,32,32}, {32,64,32,32}, {64,64,32,32}, {96,64,32,32} },  // down
        {{ 0,96,32,32}, {32,96,32,32}, {64,96,32,32}, {96,96,32,32} }   // up
        };
    
    

    In the animation loop, we just need to select the correct region according to the moving direction and the animation gesture. The gesture number will be incremented while the bunny is moving. And it goes back to zero when gesture>3.

    Running Bunny


    In part 2 we have a bouncing ball moving in the sky, the following sample added a running bunny on the ground.

    /******************************************************************************
    * File : MovingSprite.java
    * Author : http://java.macteki.com/
    * Description :
    *   A ball flying in the sky and a bunny running on the ground
    *   required background.jpg and bunny_sprite.png
    * Tested with : JDK 1.6
    ******************************************************************************/
    
    
    import java.awt.image.BufferedImage;
    
    class MovingSprite extends javax.swing.JPanel implements Runnable
    {
      // image object for double buffering
      BufferedImage drawingBoard=new BufferedImage(300,300,BufferedImage.TYPE_INT_RGB);
    
      // image object for holding the background JPEG
      BufferedImage backgroundImage;
      
      BufferedImage bunnySprite;
    
      int xBall=100, yBall=100;   // initial coordinates of the moving ball
      int xVelocity=3;            // moving 3 pixels per frame (to the right)
    
      // initial coordinates and velocity of the bunny sprite
      int xBunny=50, yBunny=250;
      int xvBunny=2;
    
      public MovingSprite() throws Exception
      {
        int w=drawingBoard.getWidth(this);
        int h=drawingBoard.getHeight(this);
        this.setPreferredSize(new java.awt.Dimension(w,h));
    
        // read background image 
        String jpeg_file="background.jpg";
        backgroundImage = javax.imageio.ImageIO.read(new java.io.File(jpeg_file));
    
        // read the sprite image
        BufferedImage tmp = javax.imageio.ImageIO.read(new java.io.File("bunny_sprite.png"));
        bunnySprite = makeTransparent(tmp);
      }
    
      private BufferedImage makeTransparent(BufferedImage tmpImage)
      {
        int h=tmpImage.getHeight(null);
        int w=tmpImage.getWidth(null);
    
        BufferedImage resultImage=new BufferedImage(w,h,BufferedImage.TYPE_INT_ARGB);
    
        // assume the upperleft corner of the original image is a transparent pixel
        int transparentColor=tmpImage.getRGB(0,0);  
        for (int y=0;y<h;y++)
          for (int x=0;x<w;x++)
          {
            int color=tmpImage.getRGB(x,y);
            if (color==transparentColor) color=color & 0x00FFFFFF; // clear the alpha flag
            resultImage.setRGB(x,y,color);
          }
    
        return resultImage;
      }
    
     
      // override the paint() method, we don't count on the system.
      // We draw our own panel.
      public void paintComponent(java.awt.Graphics gr)
      {
        // Redraw the whole image instead of redrawing every object in the screen.
        // This technique is commonly known as "double buffering"
        gr.drawImage(drawingBoard,0,0,this);
      }  
    
    
      // start the bouncing thread
      public void start()  
      {
        new Thread(this).start();
      }
    
      // thread entry point
      public void run()
      {
        try
        {
          while (true)
          {
            redrawBackground(); // redraw the background
            moveBall();         // move the ball to a new position
            moveSprite();       // move the bunny sprite
            repaint();          // redraw the panel.
            Thread.sleep(30);   // delay for persistence of vision.
          }
        }
        catch (Exception e)
        {
          e.printStackTrace();
        }
      }
    
    
      // redraw the background image.
      // this effectively erase all sprites.
      public void redrawBackground()
      {
        java.awt.Graphics2D gr=(java.awt.Graphics2D) drawingBoard.getGraphics();
        gr.drawImage(backgroundImage,0,0,this);
      }  
    
      public void moveBall()
      { 
    
        int diameter=10;  // diameter of the ball
    
        // update ball position
        xBall+=xVelocity;
        if (xBall>=300-diameter || xBall<0) // hit border
        {
          xBall-=xVelocity;        // undo movement
          xVelocity=-xVelocity;    // change direction of velocity
        }
    
        // draw ball at new position
        java.awt.Graphics2D gr = (java.awt.Graphics2D) drawingBoard.getGraphics();
        gr.setColor(java.awt.Color.RED);  // this is the ball color
        java.awt.geom.Ellipse2D newCircle=
          new java.awt.geom.Ellipse2D.Double(xBall,yBall,diameter,diameter);
    
        gr.fill(newCircle);
      }
    
      // Yes, it is very ugly to declare variable here.
      // Don't worry, everything will be moved to a Sprite class soon.
      int animationFrame=0;   // incremented for every frame.
      int gesture=0;          // animation gesture (0-3)
      int relativeSpeed=2;    // update position at every 2 frames (moving half slower)
      int gestureWait=8;      // update animation gesture at every 8 frames
    
      // pre-defined source regions
        int[][][] bunnyRect = // [direction][gesture][x,y,w,h]
        {
        {{ 0, 0,32,32}, {32, 0,32,32}, {64, 0,32,32}, {96, 0,32,32} },  // left
        {{ 0,32,32,32}, {32,32,32,32}, {64,32,32,32}, {96,32,32,32} },  // right
        {{ 0,64,32,32}, {32,64,32,32}, {64,64,32,32}, {96,64,32,32} },  // down
        {{ 0,96,32,32}, {32,96,32,32}, {64,96,32,32}, {96,96,32,32} }   // up
        };
    
      public void moveSprite()
      {
        animationFrame++;    
        if (animationFrame % relativeSpeed==0) // control when to update the position
        {
     
          // move bunny to new position
          xBunny+=xvBunny;
          if (xBunny>=300-32 || xBunny<0) // hit border
          {
            xBunny-=xvBunny;      // undo movement
            xvBunny=-xvBunny;     // change direction of velocity
          }
        }
    
        if (animationFrame % gestureWait==0)  // control when to update gesture
        {
            gesture=(gesture+1)%4;
        }
    
        // draw bunny at new position
        java.awt.Graphics2D gr = (java.awt.Graphics2D) drawingBoard.getGraphics();
    
        int w=32, h=32; 
        int dx2=xBunny+w;
        int dy2=yBunny+h;
        int direction;
        if (xvBunny>0) direction=1; else direction=0;
        int[] srcBounds=bunnyRect[direction][gesture];
        int sx1=srcBounds[0], sy1=srcBounds[1], sx2=sx1+32, sy2=sy1+32;
        gr.drawImage(bunnySprite,xBunny,yBunny,dx2,dy2,sx1,sy1,sx2,sy2,this);
      }
    
      public static void main(String[] args) throws Exception
      {
        javax.swing.JFrame window = new javax.swing.JFrame();
        window.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
        window.setTitle("Macteki moving sprite");
    
        MovingSprite spritePanel=new MovingSprite();
        window.add(spritePanel);
    
        window.pack();
        window.setVisible(true);
        
        spritePanel.start();
      }
    }
    


    Acknowledgement

    1. bunny_sprite.png is provided by Moosader :
      http://moosader.deviantart.com/art/Public-domain-bunny-sprite-151156167

    2. background.jpg is provided by Jesccia Crabtree
      http://www.jessicacrabtree.com/journal1/public-domain-nature-photos



    Next

    We will have a sprite manager that handle thousands of sprites in the next section.

    Part 5 completed. To be continued...