0

I am making this android app which requires solving puzzle8 using A star algorithm. In order to implement this, I used a comparator as shown below:

public class PuzzleBoardComparator implements Comparator<PuzzleBoard> {
@Override
public int compare(PuzzleBoard A, PuzzleBoard B) {
    Integer priorityA=A.priority();
    Integer priorityB=B.priority();
    if(priorityA.compareTo(priorityB)<0)
        return -1;
    if(priorityA.compareTo(priorityB)>0)
        return 1;
    else
        return 0;
    }
}

This comaparator uses a priority() which is based on calculating Manhattan Distance and is given below:

public int priority() {
    int manhattanDistance=0;
    for(int x=0;x<NUM_TILES;x++){
        for(int y=0;y<NUM_TILES;y++){
              if(tiles.get(XYtoIndex(x,y))!=null){
                    int numTile=tiles.get(XYtoIndex(x,y)).getNumber();
                    numTile-=1;
                    int xNumTile=numTile/NUM_TILES;
                    int yNumTile=numTile%NUM_TILES;
                    manhattanDistance+=Math.abs(x-xNumTile)+Math.abs(y-yNumTile);
              }
        }
    }
    return manhattanDistance+steps;
}

Now, this is the implementation of A-star algorithm to solve the puzzle:

public void solve() {
    //Log.d("DEMO1","LOOP");
    PuzzleBoardComparator comparator=new PuzzleBoardComparator();
    //Log.d("DEMO2","LOOP");
    PriorityQueue<PuzzleBoard> queue=new PriorityQueue<>(10,comparator);
    //Log.d("DEMO3","LOOP");
    puzzleBoard.steps=0;
    puzzleBoard.previousBoard=null;
    queue.add(puzzleBoard);
    while(!queue.isEmpty()){
          //Log.d("DEMO4","LOOP");
          PuzzleBoard cBoard=queue.remove();
          if(cBoard.resolved()){
               ArrayList<PuzzleBoard> solution=new ArrayList<>();
               //solution.add(cBoard);
               while(cBoard.getParent()!=null){
                     solution.add(cBoard);
                     cBoard=cBoard.getParent();
               }
               solution.add(cBoard);
               Collections.reverse(solution);
               animation=solution;
               break;
          }
          ArrayList<PuzzleBoard> neigh;
          neigh=cBoard.neighbours();
          Iterator<PuzzleBoard> it=neigh.iterator();
          while(it.hasNext()){
               queue.add(it.next());
          }
    }
}

But, My application is not working at all. Whenever I press a button to solve the puzzle, nothing happen. After certain amount of time I get this error message on logcat:

07-14 15:14:08.491 6172-6172/com.google.engedu.puzzle8 E/dalvikvm-heap: Out of memory on a 64-byte allocation.
    07-14 15:14:09.482 6172-6172/com.google.engedu.puzzle8 E/dalvikvm-heap: Out of memory on a 184-byte allocation.
    07-14 15:14:09.662 6172-6172/com.google.engedu.puzzle8 E/AndroidRuntime: FATAL EXCEPTION: mainProcess: com.google.engedu.puzzle8, PID: 6172
    java.lang.IllegalStateException: Could not execute method of the activity
    at android.view.View$1.onClick(View.java:3823)
    at android.view.View.performClick(View.java:4438)
    at android.view.View$PerformClick.run(View.java:18422)
    at android.os.Handler.handleCallback(Handler.java:733)
    at android.os.Handler.dispatchMessage(Handler.java:95)
    at android.os.Looper.loop(Looper.java:136)
    at android.app.ActivityThread.main(ActivityThread.java:5017)
    at java.lang.reflect.Method.invokeNative(Native Method)
    at java.lang.reflect.Method.invoke(Method.java:515)
    at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:785)
    at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:601)
    at dalvik.system.NativeStart.main(Native Method)
    Caused by: java.lang.reflect.InvocationTargetException
    at java.lang.reflect.Method.invokeNative(Native Method)
    at java.lang.reflect.Method.invoke(Method.java:515)
    at android.view.View$1.onClick(View.java:3818)
    at android.view.View.performClick(View.java:4438) 
    at android.view.View$PerformClick.run(View.java:18422) 
    at android.os.Handler.handleCallback(Handler.java:733) 
    at android.os.Handler.dispatchMessage(Handler.java:95) 
    at android.os.Looper.loop(Looper.java:136) 
    at android.app.ActivityThread.main(ActivityThread.java:5017) 
    at java.lang.reflect.Method.invokeNative(Native Method) 
    at java.lang.reflect.Method.invoke(Method.java:515) 
    at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:785) 
    at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:601) 
    at dalvik.system.NativeStart.main(Native Method) 
    Caused by: java.lang.OutOfMemoryError: [memory exhausted]
    at dalvik.system.NativeStart.main(Native Method)

Please help me to resolve the issue

EDIT 1: This is the element of xml file where onclick attribute is present.

<Button
    android:layout_width="wrap_content"
    android:layout_height="wrap_content"
    android:text="@string/solve_button_label"
    android:id="@+id/solve_button"
    android:onClick="solve"
    android:layout_alignParentBottom="true"
    android:layout_toRightOf="@+id/shuffle_button"
    android:layout_toEndOf="@+id/shuffle_button" />

EDIT 2: This is the github link to the project https://github.com/akhileshydv/Puzzle8.git

Akhilesh Yadav
  • 87
  • 11
  • You are not calling your `solve()` on the GUI-Thread, are you? – Fildor Jul 14 '16 at 10:39
  • It is called in xml using onclick attribute of the button. – Akhilesh Yadav Jul 14 '16 at 10:45
  • InvocationTargetException is due to your argument list wasn't valid and a failure within the method called. Your error probably lies in the solve() function call from xml.check for misspelling of function in xml attribute – Dijish U.K Jul 14 '16 at 11:10
  • I uploaded the element of the xml file where call to solve() is present. It's not misspelled. – Akhilesh Yadav Jul 14 '16 at 11:43
  • 1
    `onClick` attribute in xml file works as `OnClickListener`. Basically it's called in the view's parent activity which is attached to. Since your algorithm is time consuming operation it shouldn't be called in UI thread. You must debug your code, check your algorithm, log some points in code (maybe queue size?), analyze android memory manager etc. – Luke Jul 14 '16 at 12:07
  • I am not able to debug the solve() using logging since the log cat isn't showing even my first log point i.e., Log.d("DEMO1","LOOP"). I analyzed memory in monitors tab where allocated memory kept on increasing. It went beyond 64MB. And, I didn't understand what you do you mean by saying "it shouldn't be called in UI thread". Should I call solve() from java file? @qbeck – Akhilesh Yadav Jul 14 '16 at 12:55
  • Any code that executes in an event handler is running on the UI thread unless you spin up another thread to execute it. Add logging to determine if this loop ever exits `while(!queue.isEmpty())` – Paul MacGuiheen Jul 14 '16 at 13:13
  • [Here](http://stackoverflow.com/questions/3652560/what-is-the-android-uithread-ui-thread) you can find good explanation of Android UI thread. And then check [this](https://developer.android.com/guide/components/processes-and-threads.html) article on Android dev. I meant to move your algorithm to a separated thread otherwise long time operation may block UI. But I'm not sure if that's the problem. What kind of objects were created that led you to out of memory? – Luke Jul 14 '16 at 13:17
  • You were right earlier the loop is getting executed infinitely. I missed my log points earlier. I made a wrong choice of tags. @qbeck – Akhilesh Yadav Jul 14 '16 at 16:11

1 Answers1

-1

You nedd to just add this line in manifest.xml

<application
      android:largeHeap="true">
Kintan Patel
  • 1,230
  • 8
  • 15