Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  traversing all pixels in an area  (Read 5858 times)
0 Members and 1 Guest are viewing this topic.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Posted 2003-10-24 12:41:20 »

I need an algorithm to travel through all the cells, in an area which has been defined, in a 2 dimenional map (i.e. image)

Currently i have made and am using a wall following routine with a stack of "Multiple Direction Fork" co-ordinates. My problem is that the stack can get very large.

basically the algorithm is:


0. set current pixel to (0,0)
1. set Direction to none.
2. if pixel above current is empty and pixel left is non-empty, Direction = UP
3. else if pixel left of current is empty and pixel below is non-empty, Direction = LEFT
4. else if pixel below current is empty and pixel right is non-empty, Direction = DOWN
5. else if pixel right of current is empty and pixel above is non-empty, Direction = RIGHT
6. if Direction is UP
6a. if pixels (-1,-1) and (+1,-1) or (+1,+1) are non empty then add current pixel to stack.
7. if Direction is DOWN
7a. if pixels (-1,+1) and (+1,+1) or (-1,-1) are non empty then add current pixel to stack.
8. if Direction is RIGHT
8a. if pixels (+1,-1) and (+1,+1) or (-1,+1) are non empty then add current pixel to stack.
9. if Direction is LEFT
9a. if pixels (-1,-1) and (-1,+1) or (+1,-1) are non empty then add current pixel to stack.
10. if direction is not none process current pixel
10a. else if there are pixels in the stack then pop a pixel and set the current pixel to it.
10b. else exit algorithm
11. move current pixel in direction specified.
12. repeat 1


Does anyone know how to reduce the number of pixels entering the stack or indeed know of a better algorithm to traverse all the pixels in a shape.

The following pictures illusrate my problem:

With out stack pixel indicator(Blue):
www.geocities.com/budgetanime/lena.gif.txt

With stack pixel indicator (Blue)
www.geocities.com/budgetanime/lena1.gif.txt
www.geocities.com/budgetanime/server1.gif.txt

(shaded pixels are the pixels that have been processed, solid blue pixels are pixels that had been in the stack at some point, grey/white pixels define the bounding areas and black pixels are unprocessed pixels)

(you will have to change the file extension after you have downloaded it)

As you can see there are long diagonal lines of (blue) pixels that have been in the stack.

Any suggestions are welcome!

Thanks
Offline Markus_Persson

JGO Wizard


Medals: 14
Projects: 19


Mojang Specifications


« Reply #1 - Posted 2003-10-24 13:46:21 »

Do you mean a flood fill?

Play Minecraft!
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #2 - Posted 2003-10-25 01:14:03 »

Thanks for putting me on to flood fill, it is more than 50% faster than my current fill method.

However it seems cause stack overflows when filling large areas Sad

the flood fill method as it stands:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
      public void FloodFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)
      {

            count=0;
            java.util.Random r=new java.util.Random();
            int colourR= r.nextInt(240);
            int colourG= r.nextInt(240);
            int colourB= r.nextInt(240);
            LinearFloodFill4(x,y,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);
      }


      private void LinearFloodFill4(int x, int y,int width,int height,boolean[][] PixelsChecked,byte[][] frame,int count,int colourR,int colourG,int colourB)
      {
        
    
    
            //FIND LEFT EDGE OF COLOR AREA
           int LFillLoc=x; //the location to check/fill on the left

            while(true)
            {
                   //fill with the color
                 count+=1;
                  frame[y*width+LFillLoc][0]=(byte) (colourR+count%15);
                  frame[y*width+LFillLoc][1]=(byte) (colourG+count%15);
                  frame[y*width+LFillLoc][2]=(byte) (colourB+count%15);
                  PixelsChecked[LFillLoc][y]=true;
                  LFillLoc--;               //de-increment counter

                  if(LFillLoc<=0 ||
                        (PixelsChecked[LFillLoc][y]))
                              //exit loop if we're at edge of bitmap or color area
                             break;
        
            }
            LFillLoc++;
    
            //FIND RIGHT EDGE OF COLOR AREA
           int RFillLoc=x; //the location to check/fill on the left

            while(true)
            {
                   //fill with the color
                 count+=1;
                  frame[y*width+RFillLoc][0]=(byte) (colourR+count%15);
                  frame[y*width+RFillLoc][1]=(byte) (colourG+count%15);
                  frame[y*width+RFillLoc][2]=(byte) (colourB+count%15);
                  PixelsChecked[RFillLoc][y]=true;
                  RFillLoc++;          //increment counter

                  if(RFillLoc>=width ||
                        (PixelsChecked[RFillLoc][y]))
                              //exit loop if we're at edge of bitmap or color area
                             break;
        
            }
            RFillLoc--;
    
    
            //START THE LOOP UPWARDS AND DOWNWARDS            
           
            for(int i=LFillLoc;i<=RFillLoc;i++)
            {
              //START LOOP UPWARDS
             //if we're not above the top of the bitmap

              if(y>0 &&
                  (!(PixelsChecked[i][y-1])))
                     LinearFloodFill4(i,y-1,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);

              //START LOOP DOWNWARDS
             if(y<(height-1) &&
                      (!(PixelsChecked[i][y+1])))
                     LinearFloodFill4(i,y+1,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);
            }
        
      }  


it is modified code from the Flood Fill Algorithms in C# and GDI+ tutorial by jdunlap:

http://www.codeproject.com/cs/media/floodfillincsharp.asp

i will now try using the queued floodfill rather than the linear flood fill as it is not going to cause a stack over flow, however it apparantly is much slower than the linear method...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #3 - Posted 2003-10-25 02:09:14 »

I have now implemented the Queued Flood Fill and have recieved quite dissapointing times Sad

Flood Fill - queue - 4 dir:   406 msec
Flood Fill - queue - 8 dir:   3187 msec
Flood Fill - linear  -  4 dir:   47 msec
Follow Wall (my Algrthm):   125 msec

hmm, does anyone know of another filling algorithm which may peform better than my follow wall algorithm?

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #4 - Posted 2003-10-25 03:21:45 »

A person suggested filling by rows, i.e. go left->right filling pixels until you hit a boundary pixel. then look above you to see if there are row(s) that are to be filled and then fill each of those.

then do the same for rows below you.

I have implemented a row Fill however it does not seem to improving processing time...

here is how i implemented it

Recursive Row Fill:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
      public void RecRowFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)
      {

            count=0;
            java.util.Random r=new java.util.Random();
            int colourR= r.nextInt(240);
            int colourG= r.nextInt(240);
            int colourB= r.nextInt(240);
            rowFill(x,y,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);
      }
     
      public void rowFill(int x,int y,int width, int height,boolean[][] processedPixel,byte[][] frame,int count,int colourR,int colourG,int colourB)
      {
            int sx=x;
           
            while (sx<width && !processedPixel[sx][y])
            {
                  count+=1;
                  frame[y*width+sx][0]=(byte) (colourR+count%15);
                  frame[y*width+sx][1]=(byte) (colourG+count%15);
                  frame[y*width+sx][2]=(byte) (colourB+count%15);
                  processedPixel[sx][y]=true;
                  sx++;
            }
            if (y>0)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y-1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y-1]) tx--;
                              rowFill(tx+1,y-1,width,height, processedPixel,frame,count,colourR,colourG,colourB);
                        }
                  }
            }
            if (y<height-1)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y+1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y+1]) tx--;
                              rowFill(tx+1,y+1,width,height, processedPixel,frame,count,colourR,colourG,colourB);
                        }
                  }
            }
           
      }


Queued Row Fill:
     
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
      public void QueueRowFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)
      {
            LinkedList CheckQueue=new LinkedList();
           

            Integer Count=new Integer(0);
            java.util.Random r=new java.util.Random();
            int colourR= r.nextInt(240);
            int colourG= r.nextInt(240);
            int colourB= r.nextInt(240);
     

                  //start the loop
                 rowFillQ(x,y,width,height, PixelsChecked,frame,Count,colourR,colourG,colourB,CheckQueue);
                  //call next item on queue
                 while(CheckQueue.size()>0)
                  {
                        x=((Item) CheckQueue.get(0)).freq;
                        y=((Item) CheckQueue.get(0)).value;
                        CheckQueue.remove(0);
                        //System.out.println (CheckQueue.size());
                       rowFillQ(x,y,width,height, PixelsChecked,frame,Count,colourR,colourG,colourB,CheckQueue);
                  }

      }
     
      public void rowFillQ(int x,int y,int width, int height,boolean[][] processedPixel,byte[][] frame,Integer Count,int colourR,int colourG,int colourB,LinkedList queue)
      {
            int sx=x;
           
            while (sx<width && !processedPixel[sx][y])
            {
                  count =Count.intValue()+1;
                  Count=new Integer(count);
                  frame[y*width+sx][0]=(byte) (colourR+count%15);
                  frame[y*width+sx][1]=(byte) (colourG+count%15);
                  frame[y*width+sx][2]=(byte) (colourB+count%15);
                  processedPixel[sx][y]=true;
                  sx++;
            }
            if (y>0)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y-1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y-1]) tx--;
                              queue.add(new Item(tx+1,y-1));
                        }
                  }
            }
            if (y<height-1)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y+1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y+1]) tx--;
                              //rowFill(tx+1,y+1,width,height, processedPixel,frame,count,colourR,colourG,colourB);
                             queue.add(new Item(tx+1,y+1));
                        }
                  }
            }
           
      }


I have re-calculated the each algorithm times using a large image (1792x1200)

Recusive Row Fill: FAILED (Stack Overflow)
Queued Row Fill: 6496 msec
Linear Row Fill: FAILED (Stack Overflow)
Queued Flood Fill 8 dirs: 33047 msec
Queued Flood Fill 4 dirs: 14140 mesc
Wall Following Fill: 1328 msec


hmm, it is looking like my wall following fill is the best peformer on average. (i.e. linear Flood Fill easily beats it on small areas, however fails on larger areas, while my wall following fill seems to work very well on large areas)

It looks like i will be staying with the wall following fill unless anyone knows of another filling aglorithm.


Offline tom
« Reply #5 - Posted 2003-10-25 12:40:22 »

I think your queue is hurting your performance. All that new'ing of Items adds up. There is no need to use a queue as a stack will do the same. You can implement you own stack using an int array. It's easy, just double the stack size when it needs to grow.

This way you will hopefully get the same execution time as the recursive versions, but without the stack overflows.

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #6 - Posted 2003-10-25 23:48:07 »

hmm, i was thinking the same thing (that the new operation was the bottleneck)

you suggest an int array? i would need to use two i am thinking, one for the x co-ordinate and one for the y co-ordinate.

I will impelment the array stack (for all the algorithms) and see what the performance is like.

Cheers
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #7 - Posted 2003-10-26 04:35:44 »

i have implemented a stack of my own based on int arrays... however it has had a major negative impact on peformance.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
      class MyStack
      {
            int[] x;
            int[] y;
            int index;
            public MyStack()
            {
                  x= new int[1024];
                  y= new int[1024];
                  index=0;
            }
           
            public int size()
            {
                  return index;
            }
           
            public void add(int x1,int y1)
            {
                  if (index==x.length)
                  {
                        int[] temp= new int[2*x.length];
                        System.arraycopy(x,0,temp,0,x.length);
                        x=temp;
                        temp= new int[2*y.length];
                        System.arraycopy(y,0,temp,0,y.length);
                        y=temp;
                  }
                  x[index]=x1;
                  y[index]=y1;
                  index++;
            }
           
            public int getX() throws Exception
            {
                  return x[index-1];
            }
           
            public int getY() throws Exception
            {
                  return y[index-1];
            }
           
            public void remove() throws Exception
            {
                  index--;
            }
      }



the wall following algorithm using MyStack gives 37547 msecs as compared to the previous 1328.

The Flood Fill using My stack comes to 37672 msec which is worse than using the queue ( 4 direction )

Is there something inheritly wrong with my stack?

Offline tom
« Reply #8 - Posted 2003-10-26 16:04:13 »

Quote
However it seems cause stack overflows when filling large areas


I think it has some bugs.

1  
2  
3  
4  
if(LFillLoc<=0 || (PixelsChecked[LFillLoc][y]))
if(RFillLoc>=width || (PixelsChecked[RFillLoc][y]))
if(y>0 && (!(PixelsChecked[i][y-1])))
if(y<(height-1) &&  (!(PixelsChecked[i][y+1])))

All of the listed lines are missing a check to see if it is still inside the fill area.

Here is my version: (memeber variables not listed)
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
      private void linearFloodFill4(int x, int y) {
            int LFillLoc=x;
            while (true) {
                  image[y][LFillLoc] = fillcolor;
                  pixelsChecked[y][LFillLoc] = true;
                  LFillLoc--;
                  if (LFillLoc<=0 || (image[y][LFillLoc] != startcolor) || (pixelsChecked[y][LFillLoc]))
                        break;
            }
            LFillLoc++;
            int RFillLoc=x;
            while (true) {
                  image[y][RFillLoc]=fillcolor;  
                  pixelsChecked[y][RFillLoc] = true;
                  RFillLoc++;
                  if (RFillLoc>=width || (image[y][RFillLoc] != startcolor) || (pixelsChecked[y][RFillLoc]))
                        break;
            }
            RFillLoc--;
            for (int i=LFillLoc;i<=RFillLoc;i++) {
                  if ((y>0) && (image[y-1][i]==startcolor) && !pixelsChecked[y-1][i]) {
                        linearFloodFill4(i, y-1);
                  }
                  if (y<(height-1) && (image[y+1][i] == startcolor) && !pixelsChecked[y+1][i]) {
                        linearFloodFill4(i, y+1);
                  }
            }
      }


Quote
A person suggested filling by rows, i.e. go left->right filling pixels until you hit a boundary pixel. then look above you to see if there are row(s) that are to be filled and then fill each of those.

This is exactly what the linear flood fill does.

Quote
I think your queue is hurting your performance.

I take that back. I implemented a non recursive linear flood fill using an array of int stack and a linked list. The linked list version was much faster.

As a conclusion I will suggest to get the linear flood fill working. It should not be as heavy on the stack as other methods. However, here is a non recursive version, if you still get stack overflows:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
      public void linearFloodFill(int startx, int starty, int image[][], boolean pixelsChecked[][], int fillcolor) {
            LinkedList stack = new LinkedList();
            int height = image.length;
            int width = image[0].length;
            int startcolor = image[starty][startx];
            stack.addLast(getLineSeg(startx, starty, width, image, pixelsChecked, startcolor, fillcolor));
            while (stack.size() > 0) {
                  LineSeg nextLine = (LineSeg) stack.getLast();
                  if (nextLine.x >= nextLine.right) {
                        if (nextLine.doneTop == 0) {
                              nextLine.x = nextLine.left;
                              nextLine.doneTop = 1;
                        } else {
                              stack.removeLast();
                        }
                  }
                  int x = nextLine.x;
                  int y = nextLine.y;
                  nextLine.x++;
                  if (nextLine.doneTop == 0) {
                        if ((y>0) && (image[y-1][x]==startcolor) && !pixelsChecked[y-1][x]) {
                              stack.addLast(getLineSeg(x, y-1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  } else {
                        if ((y<height-1) && (image[y+1][x]==startcolor) && !pixelsChecked[y+1][x]) {
                              stack.addLast(getLineSeg(x, y+1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  }
            }
      }

      private LineSeg getLineSeg(int x, int y, int width, int image[][], boolean pixelsChecked[][], int startcolor, int fillcolor) {
            int left=x;
            while (true) {
                  image[y][left] = fillcolor;
                  pixelsChecked[y][left] = true;
                  left--;
                  if (left<=0 || (image[y][left] != startcolor) || (pixelsChecked[y][left])) {
                        break;
                  }
            }
            left++;
            int right=x;
            while (true) {
                  image[y][right]=fillcolor;  
                  pixelsChecked[y][right] = true;
                  right++;
                  if (right>=width || (image[y][right] != startcolor) || (pixelsChecked[y][right])) {
                        break;
                  }
            }
            right--;
            return new LineSeg(left, right, y);
      }

      class LineSeg {
            int left, right, x, y, doneTop;
            LineSeg(int left, int right, int y) {
                  this.left = left;
                  this.right = right;
                  this.x = left;
                  this.y = y;
            }
      }


Hope this helps. Although I'm not sure if it's faster than your wall following method Smiley

Offline tom
« Reply #9 - Posted 2003-10-26 18:47:42 »

Correction. The linearFloodFill method should look like this:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
      public void linearFloodFill(int startx, int starty, int image[][], boolean pixelsChecked[][], int fillcolor) {
            LinkedList stack = new LinkedList();
            int height = image.length;
            int width = image[0].length;
            int startcolor = image[starty][startx];
            stack.addLast(getLineSeg(startx, starty, width, image, pixelsChecked, startcolor, fillcolor));
            while (stack.size() > 0) {
                  LineSeg nextLine = (LineSeg) stack.removeLast();
                  int y = nextLine.y;
                  int right = nextLine.right;
                  for (int x=nextLine.left; x<=right; x++) {
                        if ((y>0) && (image[y-1][x]==startcolor) && !pixelsChecked[y-1][x]) {
                              stack.addLast(getLineSeg(x, y-1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  }
                 
                  for (int x=nextLine.left; x<=right; x++) {
                        if ((y<height-1) && (image[y+1][x]==startcolor) && !pixelsChecked[y+1][x]) {
                              stack.addLast(getLineSeg(x, y+1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  }
            }
      }


Now it executes almost at the same speed as the recursive version. Only a 5% overhead because of the linked list.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #10 - Posted 2003-10-26 21:05:00 »

Thanks! your effort in creating a working implementation was unexpected is very much appreciated!

I will try your method and see if i gain processing speed.

will let you know.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #11 - Posted 2003-10-26 21:41:04 »

I have implemented a slighyly modified version of your code Smiley

the changes:

image -> frame
checkedPixel[][] now
  • [y] instead of [y]

  • checkedPixel contains the boundary points when first sent the the flood fill algorithm
    added green shading for a processed pixel

    1  [/li][/list]
    2  
    3  
    4  
    5  
    6  
    7  
    8  
    9  
    10  
    11  
    12  
    13  
    14  
    15  
    16  
    17  
    18  
    19  
    20  
    21  
    22  
    23  
    24  
    25  
    26  
    27  
    28  
    29  
    30  
    31  
    32  
    33  
    34  
    35  
    36  
    37  
    38  
    39  
    40  
    41  
    42  
    43  
    44  
    45  
    46  
    47  
    48  
    49  
    50  
    51  
    52  
    53  
    54  
    55  
    56  
    57  
    58  
    59  
    60  
    61  
    62  
    63  
          public void linearFloodFill(int startx,int starty,int width, int height,boolean[][] pixelsChecked,byte[][] frame) { 
           LinkedList stack = new LinkedList();
           int fcount=0;
           stack.addLast(getLineSeg(startx, starty, width, frame, pixelsChecked,fcount));
           while (stack.size() > 0) {
            LineSeg nextLine = (LineSeg) stack.removeLast();
            int y = nextLine.y;
            int right = nextLine.right;
            for (int x=nextLine.left; x<=right; x++) {
             if ((y>0)  && !pixelsChecked[x][y-1]) {
                stack.addLast(getLineSeg(x, y-1, width, frame, pixelsChecked,fcount));
             }
            }
        
            for (int x=nextLine.left; x<=right; x++) {
             if ((y<height-1) && !pixelsChecked[x][y+1]) {
                stack.addLast(getLineSeg(x, y+1, width, frame, pixelsChecked,fcount));
             }
            }
           }
          }
          
          private LineSeg getLineSeg(int x, int y, int width, byte[][] frame, boolean pixelsChecked[][],int fcount) {
           int left=x;
           while (true) {
            //image[y][left] = fillcolor;
           fcount+=5;
            frame[y*width+left][0]=(byte) 0;
            frame[y*width+left][1]=(byte) (50+fcount%55);
            frame[y*width+left][2]=(byte) 0;
            pixelsChecked[left][y] = true;
            left--;
            if (left<=0 || (pixelsChecked[left][y])) {
             break;
            }
           }
           left++;
           int right=x;  
           while (true) {
            //image[y][right]=fillcolor;
           fcount+=5;
            frame[y*width+left][0]=(byte) 0;
            frame[y*width+left][1]=(byte) (50+fcount%55);
            frame[y*width+left][2]=(byte) 0;    
            pixelsChecked[right][y] = true;
            right++;
            if (right>=width || (pixelsChecked[right][y])) {
             break;
            }
           }
           right--;
           return new LineSeg(left, right, y);
          }
     
          class LineSeg {
           int left, right, x, y, doneTop;
           LineSeg(int left, int right, int y) {
            this.left = left;
            this.right = right;
            this.x = left;
            this.y = y;
           }
          }  



    however it seems to be not filling each row correcty... and more than likely a problem due to my modifications  Tongue  I cannot see the error myself, maybe you can?

    see www.geocities.com/budgetanime/lena.tif.txt for an example of what i mean.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #12 - Posted 2003-10-26 21:50:59 »

damn you copy&paste!  Grin

The problem was that when i copied:

1  
2  
3  
        frame[y*width+left][0]=(byte) 0; 
        frame[y*width+left][1]=(byte) (50+fcount%55);
        frame[y*width+left][2]=(byte) 0;  


for the right fill, i forgot to chage the left variable to right  Roll Eyes

now for some comparisons....
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #13 - Posted 2003-10-26 22:19:08 »

Looks good!!

for all the tests i run with both my wall following and your linear flood fill, your flood fill consistantly peformed faster than my wall following in some cases 50% or more. This is the same as for the original linear flood fill earlier in this post.

The good news is that your version is superior to the previous version as you implement your own stack and thus have no overflow errors. (worked on images 2360x2100)

thanks heaps!
Offline tom
« Reply #14 - Posted 2003-10-26 23:03:29 »

Quote
checkedPixel[][] now
  • [y] instead of [y]

I used [y]
  • because the algorithm iterates over the x variable. Then it will touch only memory in the same area, and that can give better cach performance. But I haven't tested it so the gain is probably to smal to notice. But the other thing is that you can do this: "boolean line[] = checkedPixels[y]". This will reduce array lookups.

    I've also come up with a new optimazation that increased the speed with ~25%. It's where the new LineSeg is added to the stack. X is set to newLineSeg.right, because it's known that all pixels to the left is set. Also the loop is getting so tight that an int[] stack implementation is another 20% faster than the LinkedList. Here is the latest int[] stack version. It's hopefully twice as fast as the last one I posted Smiley

    The stack:
    1  [/li][/list]
    2  
    3  
    4  
    5  
    6  
    7  
    8  
    9  
    10  
    11  
    12  
    13  
    14  
    15  
    16  
    17  
    18  
    19  
    20  
    21  
    22  
    23  
    24  
    25  
    26  
    27  
    28  
    29  
    30  
    31  
    32  
    33  
    34  
    35  
    36  
    37  
    38  
    39  
          private static final int elementSize = 4;
          private static final int xOff           = 0-elementSize;
          private static final int yOff           = 1-elementSize;
          private static final int leftOff       = 2-elementSize;
          private static final int rightOff   = 3-elementSize;

          class LineSegStack {
                int[] data;
                int size = 0;
                int offset;
               
                public LineSegStack() {
                      data= new int[1024*elementSize];
                      offset=0;
                }

                public void push(int left, int right, int y) {
                      if (offset == data.length) {
                            int[] temp = new int[2*data.length];
                            System.arraycopy(data, 0, temp, 0, data.length);
                            data = temp;
                      }
                      offset+=elementSize;
                      data[offset+leftOff] = left;
                      data[offset+rightOff] = right;
                      data[offset+xOff] = left;
                      data[offset+yOff] = y;
                      size++;
                }

                public void pop(LineSeg s) {
                      s.x = data[offset+xOff];
                      s.y = data[offset+yOff];
                      s.left = data[offset+leftOff];
                      s.right = data[offset+rightOff];
                      offset -= elementSize;
                      size--;
                }
          }


    1  
    2  
    3  
    4  
    5  
    6  
    7  
    8  
    9  
    10  
    11  
    12  
    13  
    14  
    15  
    16  
    17  
    18  
    19  
    20  
    21  
    22  
    23  
    24  
    25  
    26  
    27  
    28  
    29  
    30  
    31  
    32  
    33  
    34  
    35  
    36  
    37  
    38  
    39  
    40  
    41  
    42  
    43  
    44  
    45  
    46  
    47  
    48  
    49  
    50  
    51  
    52  
    53  
    54  
    55  
    56  
    57  
    58  
    59  
    60  
    61  
     // members are initalized in constructor
         private int fillcolor = 0xffff00ff;
          private boolean pixelsChecked[][]; //[y][x]
         private int image[][]; //[y][x]
         private int startcolor = 0xffffffff;
          private int startx = 0;
          private int starty = 0;
          private int width;
          private int height;
          private LineSegStack stack = new LineSegStack();
         

    public long floodStack() {
                LineSeg nextLine = new LineSeg(0, 0, 0);
                addLineSegToStack(startx, starty);
                while (stack.size > 0) {
                      stack.pop(nextLine);
                      int y = nextLine.y;
                      int right = nextLine.right;
                      if (y>0) {
                            int topLine[] = image[y-1];
                            boolean topChecked[] = pixelsChecked[y-1];
                            for (int x=nextLine.left; x<=right; x++) {
                                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                                        x = addLineSegToStack(x, y-1);
                                  }
                            }
                      }
                     
                      if (y<height-1) {
                            int botLine[] = image[y+1];
                            boolean botChecked[] = pixelsChecked[y+1];
                            for (int x=nextLine.left; x<=right; x++) {
                                  if ((botLine[x]==startcolor) && !botChecked[x]) {
                                        x = addLineSegToStack(x, y+1);
                                  }
                            }
                      }
                }
          }
         
          private int addLineSegToStack(int x, int y) {
                int line[] = image[y];
                boolean checked[] = pixelsChecked[y];
                int left=x;
                do {
                      line[left] = fillcolor;
                      checked[left] = true;
                      left--;
                } while (left>=0 && (line[left] == startcolor) &&  !checked[left]);
                left++;
                int right=x;
                do {
                      line[right]=fillcolor;  
                      checked[right] = true;
                      right++;
                } while (right<width && (line[right] == startcolor) && !checked[right]);
                right--;
                stack.push(left, right, y);
                return right;
          }


    Enjoy!

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #15 - Posted 2003-10-27 01:48:43 »

I have implemented your latest vesion.

I have quite interesting results:

1  
2  
3  
4  
5  
6  
            image size   Flood_new   Flood_old   Wall_Follow 
 
            640x337         172         78           105
            512x512         140         78           141
            1280x1024       203         609          985
            2482x2688       1390        6110         5344


where:
Flood_new is your latest Linear Flood Fill Alg
Flood_old is your previous Linear Flood Fill Alg
and Wall_Follow is my wall following algorithm.

Time is measured in millisec and is the avg of 5 runs.

It seems for lower resolution images, your first method seems to out peform your newer version, however it is drastically faster once the image starts getting large.

There must be an inital over head with your second method which becomes less of an impact when more pixels are processed.

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #16 - Posted 2003-10-27 01:51:50 »

and that the old method seems to get progressivly worse as compared to the wall following as the image gets very large.
Offline tom
« Reply #17 - Posted 2003-10-27 11:09:31 »

The only extra overhead with the new method is the int stack. You could try reusing it, if thats acceptable. Make it a static member, and reset it at the start of the flood fill. Reducing the inital stack size on smal images might also help.

Not sure why the old method slows downs that much.

There is one more improvement that can be made to the algorithm. It is to not check for "collision" from where it come from. Here's an extract from the code:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
if (y>0) {
 // fill the line above this line
     int topLine[] = image[y-1];
      boolean topChecked[] = pixelsChecked[y-1];
  // did we come from there?
     if (nextLine.fromtop == 1) {
   // check on the left side of where we come from
           int min = Math.min(nextLine.prevleft, right);
            for (int x=nextLine.left; x<=min; x++) {
                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                  }
            }
   // check on the right side of where we come from
           for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {
                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                  }
            }
      } else {
  // did not come from this side: check the whole line
           for (int x=nextLine.left; x<=right; x++) {
                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                  }
            }
      }
}


Gave me a 10-15% improvement.

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #18 - Posted 2003-10-27 21:28:32 »

Wow!  Shocked just by using the same instance of the stack the fill operation has improved effeciency another 50% (the 512x512 image is filled in 68 msec and the 2482x2688 is filled in 609 msec.

From the latest code snippet, related to the do not "collision" detect from the line you have come from, i am unsure how the extra parameters are used in addLineSegToStack.

i.e. addLineSegToStack(x, y-1, nextLine.left, right, 0)

Offline tom
« Reply #19 - Posted 2003-10-27 22:04:14 »

Well, it has kind of a cascading effect, so everything is changed. I'll post the changes.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
class LineSeg:
// additianal members.
int prevleft, prevright, fromtop;

class LineSegStack:
private static final int elementSize = 7; // changed
private static final int prevleftOff  = 4-elementSize; // added
private static final int prevrightOff = 5-elementSize; // added
private static final int fromtopOff   = 6-elementSize; // added

// 3 extra paramters
public void push(int left, int right, int y, int prevleft, int prevright, int fromtop) {
 ...
 data[offset+prevleftOff] = prevleft;
 data[offset+prevrightOff] = prevright;
 data[offset+fromtopOff] = fromtop;
 ...
}

public void pop(LineSeg s) {
...
s.prevleft = data[offset+prevleftOff];
s.prevright = data[offset+prevrightOff];
s.fromtop = data[offset+fromtopOff];
}

// addLineSegToStack(): only change is that the 3 extra parametrs are pushed on the stack
private int addLineSegToStack(int x, int y, int prevleft, int prevright, int fromtop) {
...
stack.push(left, right, y, prevleft, prevright, fromtop);
return right;
}

// the meat of floodStack(), which has grown a bit:
           while (stack.size > 0) {
                  stack.pop(nextLine);
                  int y = nextLine.y;
                  int right = nextLine.right;
                  if (y>0) {
                        int topLine[] = image[y-1];
                        boolean topChecked[] = pixelsChecked[y-1];
                        if (nextLine.fromtop == 1) {
                              int min = Math.min(nextLine.prevleft, right);
                              for (int x=nextLine.left; x<=min; x++) {
                                    if ((topLine[x]==startcolor) && !topChecked[x]) {
                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                                    }
                              }
                              for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {
                                    if ((topLine[x]==startcolor) && !topChecked[x]) {
                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                                    }
                              }
                        } else {
                              for (int x=nextLine.left; x<=right; x++) {
                                    if ((topLine[x]==startcolor) && !topChecked[x]) {
                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                                    }
                              }
                        }
                  }
                 
                  if (y<height-1) {
                        int botLine[] = image[y+1];
                        boolean botChecked[] = pixelsChecked[y+1];
                        if (nextLine.fromtop == 0) {
                              int min = Math.min(nextLine.prevleft, right);
                              for (int x=nextLine.left; x<=min; x++) {
                                    if ((botLine[x]==startcolor) && !botChecked[x]) {
                                          x = addLineSegToStack(x, y+1, nextLine.left, right, 1);
                                    }
                              }
                              for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {
                                    if ((botLine[x]==startcolor) && !botChecked[x]) {
                                          x = addLineSegToStack(x, y+1, nextLine.left, right, 1);
                                    }
                              }
                        } else {
                              for (int x=nextLine.left; x<=right; x++) {
                                    if ((botLine[x]==startcolor) && !botChecked[x]) {
                                          x = addLineSegToStack(x, y+1, nextLine.left, right, 1);
                                    }
                              }
                        }
                  }
            }


prevleft, prevright and fromtop is used to remember where the function was called from. The you don't need to test that area again.

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #20 - Posted 2003-10-27 22:10:44 »

lol, i kinda went and made changes where i thought it would be appropriate to implement the check.... I should have waited abit too see if you responded before it did it Smiley

Well, here are my changes, however it seems that there is no measureable difference... i may have done something wrong...

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
      class LineSegStack { 
            private static final int elementSize = 7;
            private static final int xOff      = 0-elementSize;
            private static final int yOff      = 1-elementSize;
            private static final int leftOff  = 2-elementSize;
            private static final int rightOff   = 3-elementSize;
            private static final int prevLeftOff   = 4-elementSize;
            private static final int prevRightOff   = 5-elementSize;
            private static final int fromTopOff   = 6-elementSize;  
       int[] data;  
       int size = 0;
       int offset;  
   
       public LineSegStack() {
        data= new int[1024*elementSize];  
        offset=0;  
       }  
       
 
       public void push(int left, int right, int y,int fromTop) {
        if (offset == data.length) {
         int[] temp = new int[2*data.length];  
         System.arraycopy(data, 0, temp, 0, data.length);  
         data = temp;  
        }
       
        if (offset>0)
        {
       
              offset+=elementSize;  
              data[offset+leftOff] = left;
              data[offset+prevLeftOff] = data[offset+prevLeftOff-elementSize];
              data[offset+rightOff] = right;
              data[offset+prevRightOff] =data[offset+prevRightOff-elementSize];
              data[offset+xOff] = left;
              data[offset+yOff] = y;
              data[offset+fromTopOff]=fromTop;

        }
        else
        {
            offset+=elementSize;  
            data[offset+leftOff] = left;
            data[offset+prevLeftOff] = 0;
            data[offset+rightOff] = right;
            data[offset+prevRightOff] =0;
            data[offset+xOff] = left;
            data[offset+yOff] = y;
            data[offset+fromTopOff]=fromTop;
        }
        size++;
         
       }  
 
       public void pop(LineSeg s) {
        s.x = data[offset+xOff];
        s.y = data[offset+yOff];
        s.left = data[offset+leftOff];
        s.right = data[offset+rightOff];
        s.prevLeft= data[offset+prevLeftOff];
        s.prevRight= data[offset+prevRightOff];
        s.fromTop= data[offset+fromTopOff];
        offset -= elementSize;  
        size--;
       }
      }
     
     
      class LineSeg {
       int left, right, x, y, doneTop,prevLeft,prevRight,fromTop;
       
       LineSeg(int left, int right, int y) {
        this.left = left;
        this.right = right;
        this.x = left;
        this.y = y;
       }
      }  

 
 
   public void linearFloodFill1(int startx,int starty,int width, int height,boolean[][] pixelsChecked,byte[][] frame,LineSegStack stack ) {
      //LineSegStack stack = new LineSegStack();
     LineSeg nextLine = new LineSeg(0, 0, 0);
      int fcount=0;
      java.util.Random r=new java.util.Random((startx+starty)*(starty-startx));
      int RColour = r.nextInt(240);
      int GColour = r.nextInt(240);
      int BColour = r.nextInt(240);
      int fromTop=0;
      int y,right;
      boolean topChecked[];
      boolean botChecked[];
      addLineSegToStack(startx, starty,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);
      while (stack.size > 0) {
       stack.pop(nextLine);
       y = nextLine.y;
       right = nextLine.right;
       fromTop=0;
       
       if (y>0) {
            fromTop=1;
        // fill the line above this line
       //int topLine[] = image[y-1];
       topChecked = pixelsChecked[y-1];
         // did we come from there?
       if (nextLine.fromTop==1) {
            // check on the left side of where we come from
        int min = Math.min(nextLine.prevLeft, right);
         for (int x=nextLine.left; x<=min; x++) {
            if (!topChecked[x]) {
             x = addLineSegToStack(x, y-1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);
            }
         }
            // check on the right side of where we come from
        for (int x=Math.max(nextLine.prevRight, nextLine.left); x<=right; x++) {
            if (!topChecked[x]) {
             x = addLineSegToStack(x, y-1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);
            }
         }
        } else {
         // did not come from this side: check the whole line
        for (int x=nextLine.left; x<=right; x++) {
            if (!topChecked[x]) {
             x = addLineSegToStack(x, y-1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);
            }
         }
        }
       }
       
/    
       if (y<height-1) {
            fromTop=2;
        //int botLine[] = image[y+1];
       botChecked = pixelsChecked[y+1];
        for (int x=nextLine.left; x<=right; x++) {
         if ( !botChecked[x]) {
            x = addLineSegToStack(x, y+1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);  
         }
        }
       }
       

       
       
      }
   }
 
   private int addLineSegToStack(int x, int y,int width, int height, byte[][] frame, boolean pixelsChecked[][],int fcount,int RColour, int GColour,int BColour,LineSegStack stack,int fromTop)
    {
      //int line[] = image[y];
     boolean checked[] = pixelsChecked[y];
      int left=x;
      do {
            fcount++;
            frame[y*width+left][0]=(byte) (RColour+(fcount%15));
            frame[y*width+left][1]=(byte) (GColour+(fcount%15));
            frame[y*width+left][2]=(byte) (BColour+(fcount%15));
       checked[left] = true;
       left--;
      } while (left>=0 &&  !checked[left]);
      left++;
      int right=x;  
      do {
            fcount++;
            frame[y*width+right][0]=(byte) (RColour+(fcount%15));
            frame[y*width+right][1]=(byte) (GColour+(fcount%15));
            frame[y*width+right][2]=(byte) (BColour+(fcount%15));    
       checked[right] = true;
       right++;
      } while (right<width && !checked[right]);
      right--;
      stack.push(left, right, y,fromTop);
      return right;
   }




by comparing our two codes, it looks like we are effectivly doing the same thing.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #21 - Posted 2003-10-27 22:12:56 »

thinking that we would do the same if coming from a bottom line, i implemented the same checking, however it made the algorithm slightly slower so i removed it.
Offline tom
« Reply #22 - Posted 2003-10-27 22:57:50 »

The differance is that I also push prevleft and prevright on the stack. I use dummy values in the first push:

1  
2  
3  
addLineSegToStack(startx, starty, -1, -1, 0)
while (stack.size > 0) {
 ...


which means that the previus left and right of the first call is outside the image. That way it will not effect the algorithm.

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #23 - Posted 2003-10-28 00:29:55 »

hmm, i thought that is what i was doing...

The previous left and right values are the values of left and right of the last stack push operation, So i set the current previous left and previous right to the left and right of the last push operation.

If the current push operation is the beginning of the stack then i just add dummy prev left and prev right, just like you do.
Offline tom
« Reply #24 - Posted 2003-10-28 09:38:55 »

Well the variable names is a bit misleading I'm afraid  Embarrassed

With "previous" I mean the LineSeg that was prosessed when this LineSeg was added to the stack. It makes more sense in the recursive version. Where the previously prosessed lineSeg is the caller, or previous function.

A better name would be "callerLeft, callerRight and callerY", representing the line segment prosessed by the caller of this "function". Here a function is the code inside the "while (stack.size > 0)" loop. You do a function call by pushing a lineSeg onto the stack. It will be processed by the while loop later.

Thats why you can't use the previous lineSeg on the stack, as it is probably not the caller.

fromTop can also be made more clear. It's a boolean representing from what direction the current function was called. The caller is known to be on a neighbouring side, so it is used to find out if the caller is the top or bottom line. It would be better to just store the callers y, and check against that.

Hope this clears it up. If not, I can post a working version.

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #25 - Posted 2003-10-28 19:35:32 »

ah, i understand now Smiley

I am currently on my home computer due to being sick today, so i cannot compare the filling times now with the previous times i have given, however as an indicator, that 2482x2688 image is being fillled in 469 msec on my Athlon XP2100. And the 512x512 is done in 47 msec.

I believe we have achieved a very fast fill!


Offline tom
« Reply #26 - Posted 2003-10-29 02:11:13 »

Yeah, it's a lean, mean flood-filling machine  Smiley

Offline Jeff

JGO Coder




Got any cats?


« Reply #27 - Posted 2003-11-03 22:03:02 »

Okay, here's a key difference between Java and C...

In C, recursion is kinda slow, and random access to an array is very fast (a stack is effectively random access as the next access is not deterministicly determinable at compile time).

In a Modern Java VM, thanks to array bounds checking and great JIT compilers, the reverse is true.

Fastest way to speed up something based on an array stack is to recode it as a true recursive routine.  It'll be simpler code, too.

For this and other great insights see:
http://java.sun.com/docs/books/performance

Wink

JK

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline tom
« Reply #28 - Posted 2003-11-03 23:06:41 »

That's true Jeff, and the recursive and non recursive version is equally fast. But it was made non recursive because of stack overflow problems, not speed.

Offline Jeff

JGO Coder




Got any cats?


« Reply #29 - Posted 2003-11-04 00:06:48 »

So why not just increase your stack size?

is this in the main thread or a launched thread?


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (15 views)
2014-07-30 21:08:39

Riven (21 views)
2014-07-29 18:09:19

Riven (14 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (32 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (42 views)
2014-07-23 21:16:32

Riven (30 views)
2014-07-23 21:07:15

Riven (31 views)
2014-07-23 20:56:16
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!