current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 0 down vote favorite

I am trying to make a program that goes through a sprite image, and then makes each shape in it a new image. For example, if we took Mario, I want the hat to be one image, the face to be another, and so on. I have gotten my program to work on small 32x32 images, but if I want to run this on a larger image, it causes a Stack Overflow Error. If I was using C++, I would just go about this by clearing the stack after each recursive call, but as far as I know, Java does not let you directly clear the stack. I want my program to run on Windows, Linux and Mac so I thought Java would be the best option, so I don't really want to switch the language I am using. Is there a way to delete whatever was stored on the stack after each recursive call in Java? Here is my code, just in case there is an error with it.

 private void makeShape(int x, int y)
    {
        if(x < 0 || y < 0 || y >= sprite.getHeight() || x >= sprite.getWidth())
        {
            return;
        }
        if(sample == colorData[y][x] && table[y][x])
        {
            tempBlankImage[y][x] = sample;
            table[y][x] = false;
            makeShape(x, y - 1);
            makeShape(x, y + 1);
            makeShape(x - 1, y);
            makeShape(x + 1, y);
        }
        else
        {
            return;
        }

    }

The x and y points are generated from a for loop that goes through the image and checks if a point has been added to a shape, and if not it makes a shape from its surrounding pixels.

UPDATE:

    private int[][] makeShape(int sample, int x, int y)
    {
        int[][] tempBlankImage = blankImage();
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(x,y));
        while(!queue.isEmpty())
        {
            Point point = queue.remove();
            if(sample == colorData[point.y][point.x] && table[point.y][point.x])
            {
                tempBlankImage[point.y][point.x] = sample;
                table[point.y][point.x] = false;
                if(point.y < sprite.getHeight() -1)
                    queue.add(new Point(point.x, point.y+1));
                if(point.y > 0)
                    queue.add(new Point(point.x, point.y-1));
                if(point.x < sprite.getWidth()-1)
                    queue.add(new Point(point.x+1, point.y));
                if(point.x > 0)
                    queue.add(new Point(point.x-1, point.y));
            }

        }
        queue = null;
        return tempBlankImage;
    }

The Stack Overflow Error has stopped, now I am getting out Out of Memory: Java Heap Space, even though I increased it to 2 GB. I am adding each int[][] to an ArrayList, which I am guessing is the issue. How else can I store the data?

share|improve this question
    
This doesn't directly answer your question, but; any reason not to just use a nested loop, outer for x and inner for y? That would be simpler, and more efficient. (You could also do a single-dimension index, with one loop; each index is y*width + x). – yshavit Dec 17 '15 at 2:38
    
I do have one in a different method, and it looks at the table array and once there is a cell that returns true, it calls makeShape – Jedi_Maseter_Sam Dec 17 '15 at 2:40
1  
I'd suggest looking up iterative floodfill algorithm to avoid recursion – Christian R. Dec 17 '15 at 2:55
    
What does "clearing the stack after each recursive call" mean? – Andreas Dec 17 '15 at 3:21
    
Although the correct answer is certainly to write this iteratively rather than recursively, you may be able to avoid the stack overflow by swapping the second and third calls to makeShape, so that not every cell is on the stack at once. – David Wallace Dec 17 '15 at 7:10
up vote 1 down vote accepted

Java is well known for it's automatic well defined and tested memory management system - it is generally not good idea to manage memory on your own even if it is possible (because in some level it actually is).

What will clearing stack give you if the alghoritm execution time will let you get a beard and be able to tell stories about it to your grand children?

Do not make it as recursive - think about some iterative form of an alghoritm. You can for example iterate over all image's pixels and add them to the appropriate image (due to it's color) that will be stored in some HashMap like in this pseudo code

    HashMap<Color, Image> images= new HashMap<Color, Image>();

    for(Pixel pixel : originImage)
        Color color = pixel.getColor();
        images.get(color).put(pixel)

Do not waste your life for bad code

share|improve this answer
    
If I did that, how would I go about separating the pixels by the ones that touch, so I can have all the shapes of a color on separate layers, instead of each layer containing all the shapes of the given color. – Jedi_Maseter_Sam Dec 17 '15 at 2:47
1  
of course - it is only simple example - read about Flood fill alghoritm or Smith's alghoritm (not Smith–Waterman text alghoritm) - I had implemented this one somewhere and was good but it is hard to find implementation – m.antkowicz Dec 17 '15 at 2:52
    
I came up with something based on the Wiki, but now I run out of heap space. – Jedi_Maseter_Sam Dec 17 '15 at 11:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.