Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (542)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (606)
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  
  Line Logic  (Read 9388 times)
0 Members and 1 Guest are viewing this topic.
Offline cylab

JGO Ninja


Medals: 56



« Reply #30 - Posted 2011-08-11 17:53:42 »

Looks nice, but:

1  
2  
3  
Tested line1 (cylab), 3000000 iterations. Took 619ms
Tested line2 (counterp), 3000000 iterations. Took 7857ms
Tested line3 (counterp), 3000000 iterations. Took 25071ms (!)

Mathias - I Know What [you] Did Last Summer!
Offline counterp

Senior Devvie


Medals: 11



« Reply #31 - Posted 2011-08-11 18:06:00 »

Sorry there was a bug with it. here's updated one:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
   private static final void line2(int x1, int y1, int x2, int y2, int resX, int resY) {
      int dist = Math.max(Math.abs(x2-x1),Math.abs(y2-y1));
      float dx = (float)(x2-x1)/dist;
      float dy = (float)(y2-y1)/dist;
      int lastRegX = (int) (x1 + dx + 0.5f) / resX;
      int lastRegY = (int) (y1 + dy + 0.5f) / resY;
      for (int d = 2; d <= dist; d++) {
         int x = (int) (x1 + 0.5f + dx*d);
         int y = (int) (y1 + 0.5f + dy*d);
         int regX = x / resX;
         if (x < 0)
            regX--;
         int regY = y / resY;
         if (y < 0)
            regY--;
         if (regX != lastRegX || regY != lastRegY) {
           
         }
         lastRegX = regX;
         lastRegY = regY;
      }
   }


I honestly have no idea what caused it to be insanely slow. Compare the above with this in a benchmark:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
   private static final void line2(int x1, int y1, int x2, int y2, int resX, int resY) {
      int dist = Math.max(Math.abs(x2-x1),Math.abs(y2-y1));
      float dx = (float)(x2-x1)/dist;
      float dy = (float)(y2-y1)/dist;
      int lastRegX = (int) (x1 + dx + 0.5f) / resX;
      int lastRegY = (int) (y1 + dy + 0.5f) / resY;
      for (int d = 2; d <= dist; d++) {
         int x = (int) (x1 + 0.5f + dx*d);
         int y = (int) (y1 + 0.5f + dy*d);
         int regX = x / resX;
         if (x < 0)
            regX--;
         int regY = y / resY;
         if (y < 0)
            regY--;
         if (regX != lastRegX || regY != lastRegY) {
            lastRegX = regX;
            lastRegY = regY;
         }
      }
   }


isn't that crazy weird, or am I missing something?
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #32 - Posted 2011-08-11 18:08:42 »

Tested most recent cylab and counterp

Tested line1 (cylab), 3000000 iterations. Took 2449ms
Tested line2 (counterp), 3000000 iterations. Took 11980ms

However,  because I personally feel that they should be checking against the same x0,x0,x1,y1  because if you are doing a speed test, you need to check against SAME numbers, at least in my opinion. So giving different random numbers to each is a bad idea in my opinion. arghh wordy

anyways
I extracted the randomness
1  
2  
3  
4  
5  
6  
for(int i=0;i<iter;i++){
    x0[i] = (int) (Math.random()*1000);
    y0[i] = (int) (Math.random()*1000);
    x1[i] = (int) (Math.random()*1000);
    y1[i] = (int) (Math.random()*1000);
}



Then I ran the tests using the exact same numbers
Tested line1 (cylab), 3000000 iterations. Took 1925ms
Tested line2 (counterp), 3000000 iterations. Took 11438ms

saw a 500ms increase
so in my opinion these are more accurate speed of the tests,  because in real world you should already have existing numbers not generate numbers for the sake of the test


edit: snipped

edit2x: counterp sometimes your code gives me a divide by zero error (It only occurs when the line is a dot i.e. 885 125 885 125) so I think its a non issue personally.

Work computer is: Intel core i7 860 2.8ghz with 8gb of ram on 64 bit OS
I don't know how your guys numbers are so much lower than mine. I do have a lot of things open but minimal background cpu usage


"Experience is what you get when you did not get what you wanted"
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline counterp

Senior Devvie


Medals: 11



« Reply #33 - Posted 2011-08-11 18:11:11 »

really? I'm getting that mine is faster :\

and you have to cast it or else it will end up dividing integers which will give an integer

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  
public class Benchmark {

   public static void main(String[] args) {
      long start, end;
      double trials = 10000000;
      int[][] lines = new int[4][(int) trials];
      for (int n = 0; n < 4; n++)
         for (int i = 0; i < lines.length; i++) {
            lines[n][i] = (int) (Math.random() * 1000);
         }

      start = System.nanoTime();
      for (int i = 0; i < trials; i++)
         line(lines[0][i], lines[1][i], lines[2][i], lines[3][i], 25, 25);
      end = System.nanoTime();
      System.out.println("Test 1: " + ((end - start) / 1000000D));

      start = System.nanoTime();
      for (int i = 0; i < trials; i++)
         line2(lines[0][i], lines[1][i], lines[2][i], lines[3][i], 25, 25);
      end = System.nanoTime();
      System.out.println("Test 2: " + ((end - start) / 1000000D));
   }

   private static final void line(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight) {
      int col0 = x0 / cellWidth;
      int row0 = y0 / cellHeight;

      int col1 = x1 / cellWidth;
      int row1 = y1 / cellHeight;

      float m = x0==x1? Integer.MAX_VALUE:(float) (y0 - y1) / (x0 - x1);
      float b = y0 - m * x0;

      if (Math.abs(m) > 1) {
         int lastCol = col0;
         int dir = (y0 < y1) ? 1 : -1;
         for (int row = row0; (dir==1? row <= row1:row >= row1); row += dir) {
            float y = row * cellHeight;
            float x = (y - b) / m;
            int col = (int) (x + 0.5f * dir) / cellWidth;
            if (col != lastCol) {
               y = row * cellHeight - dir;
               x = (y - b) / m;
               int missedCol = (int) (x + 0.5f * dir) / cellWidth;
               if (lastCol != missedCol) {
               }
               lastCol = col;
            }
         }
      } else {
         int lastRow = row0;
         int dir = (x0 < x1) ? 1 : -1;
         for (int col = col0; (dir==1? col <= col1:col >= col1); col += dir) {
            float x = col * cellWidth;
            float y = m * x + b;
            int row = (int) (y + 0.5f * dir) / cellHeight;
            if (row != lastRow) {
               x = col * cellWidth - dir;
               y = m * x + b;
               int missedRow = (int) (y + 0.5f * dir) / cellHeight;
               if (lastRow != missedRow) {
               }
               lastRow = row;
            }
         }
      }
   }

   private static final void line2(int x1, int y1, int x2, int y2, int resX, int resY) {
      int dist = Math.max(Math.abs(x2-x1),Math.abs(y2-y1));
      float dx = (float)(x2-x1)/dist;
      float dy = (float)(y2-y1)/dist;
      int lastRegX = (int) (x1 + dx + 0.5f) / resX;
      int lastRegY = (int) (y1 + dy + 0.5f) / resY;
      for (int d = 2; d <= dist; d++) {
         int x = (int) (x1 + 0.5f + dx*d);
         int y = (int) (y1 + 0.5f + dy*d);
         int regX = x / resX;
         if (x < 0)
            regX--;
         int regY = y / resY;
         if (y < 0)
            regY--;
         if (regX != lastRegX || regY != lastRegY) {
         }
         lastRegX = regX;
         lastRegY = regY;
      }
   }

}


is there something wrong with this benchmark? and can any one else test it to see if they got same results?
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #34 - Posted 2011-08-11 18:19:22 »

counterp:  what is the purpose of the if in your "updated" code? if in your old code I understand, but not newer
1  
2  
3  
4  
5  
if (regX != lastRegX || regY != lastRegY) {
             
}
lastRegX = regX;
lastRegY = regY;

1  
2  
3  
4  
if (regX != lastRegX || regY != lastRegY) {
     lastRegX = regX;
     lastRegY = regY;
}


snipped/ question resolved


edit:
counter in your above posted code
Test 1: 246.949836
Test 2: 1400.469944

"Experience is what you get when you did not get what you wanted"
Offline counterp

Senior Devvie


Medals: 11



« Reply #35 - Posted 2011-08-11 18:23:43 »

That's where the region code is supposed to go (removed for the benchmark, just left the if-statement because that should be part of the benchmark:

1  
2  
3  
4  
5  
if (regX != lastRegX || regY != lastRegY) {
     Region.register(regX, regY);
}
lastRegX = regX;
lastRegY = regY;

1  
2  
3  
4  
5  
if (regX != lastRegX || regY != lastRegY) {
     Region.register(regX, regY);
     lastRegX = regX;
     lastRegY = regY;
}


but for some odd reason the second one is extremely slow on my computer as compared to the first one!?!? I am befuddled.. Can you run my benchmark and give me your results?

EDIT: ok what can be wrong with my JVM -.- why is it telling me second one is faster
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #36 - Posted 2011-08-11 18:31:07 »

counterp

for me to make your test faster I must change this:
1  
2  
float lastRegX = (x1 + dx + 0.5f) / resX;
float lastRegY = (y1 + dy + 0.5f) / resY;

from this:
1  
2  
int lastRegX = (int) (x1 + dx + 0.5f) / resX;
int lastRegY = (int) (y1 + dy + 0.5f) / resY;

I removed the int and int cast.
Can you not cast the int? or use another way of doing it, because that (int) cast is the major bottleneck.

(cylab?) Test 1: 243.20876
(counterp?) Test 2: 129.626574

(cylab?) Test 1: 254.693393
(counterp?) Test 2: 1398.737626 [ this is with the (int) cast ]

"Experience is what you get when you did not get what you wanted"
Offline cylab

JGO Ninja


Medals: 56



« Reply #37 - Posted 2011-08-11 18:33:26 »

I think we have to store the actual values, not that the benchmark is flawed by the jvm removing "unneccessary" calculations.

Mathias - I Know What [you] Did Last Summer!
Offline counterp

Senior Devvie


Medals: 11



« Reply #38 - Posted 2011-08-11 19:07:04 »

you know what, I don't even care

if this region thing becomes a problem later on, I'll fix it then  Yawn

all that's left to do now is figured out how to make your method work with negative values :\
Offline cylab

JGO Ninja


Medals: 56



« Reply #39 - Posted 2011-08-12 08:04:16 »

all that's left to do now is figured out how to make your method work with negative values :\

Does it really have to? If so I could think of offsetting coords like
1  
2  
x = x+maxNegativeCols*cellWidth;
y = y+maxNegativeRows*cellHeight;

and substract that from the result
1  
2  
col-=maxNegativeCols;
row-=maxNegativeRows;

Mathias - I Know What [you] Did Last Summer!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline counterp

Senior Devvie


Medals: 11



« Reply #40 - Posted 2011-08-13 07:27:10 »

It does, and there are no boundaries Tongue

I think I can think up some special case solution for negative values (when I come back to this, I'm working on other things now)
Offline WhenNDoubtGTFO

Junior Newbie





« Reply #41 - Posted 2011-08-13 11:42:38 »

If you made each region a rectangle and you could see if the line intersects with the rectangles with
Rectangle r = new Rectangle(x,y,width,height);
ArrayList<Point> p = new ArrayList<Point>();

then make new instances of the point class and add them to the array and have an enhanced for loop go through the points and see if any Rectangle.contains(p)

problems with this are you need an arraylist for each line and it probably is very slow compared to something but this is super fast to write.
Offline counterp

Senior Devvie


Medals: 11



« Reply #42 - Posted 2011-08-14 01:51:25 »

that's very slow
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 849
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #43 - Posted 2013-02-26 12:37:52 »

For anybody using this code as a reference, I just wanted to share with you that the algorithm in the method 'line' doesn't work at all, sadly. It skips so many pixels that it's not even remotely close to drawing a line. The other algorithm found in this thread, aptly named 'line2', however, did the job quite nicely, except that it skips the very first pixel, for which I'll generously provide a patch Wink

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  
   public static interface Plotter{
      public void plot(int x, int y);
   }

   public static final void plot(int x1, int y1, int x2, int y2, int resX, int resY, Plotter plotter) {
     if ((x1 | y1 | x2 | y2) < 0) {
        throw new IllegalArgumentException();
     }

      int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
     if (dist == 0) {
        /* we must not divide by zero (see below)
           or we always plot at ((int)NaN,(int)NaN) -> (0,0) */

        plotter.plot(x1, y1);
        return;
     }


      float dx = (float) (x2 - x1) / dist;
      float dy = (float) (y2 - y1) / dist;
      int lastRegX = (int) (x1 + dx + 0.5f) / resX;
      int lastRegY = (int) (y1 + dy + 0.5f) / resY;

     /* plot the first coordinate */
     plotter.plot(lastRegX, lastRegY);

      for (int d = 2; d <= dist; d++) {
         int x = (int) (x1 + 0.5f + dx * d);
         int y = (int) (y1 + 0.5f + dy * d);
         int regX = x / resX;
         if (x < 0) {
            regX--;
         }
         int regY = y / resY;
         if (y < 0) {
            regY--;
         }
         if (regX != lastRegX || regY != lastRegY) {
            plotter.plot(regX, regY);
         }
         lastRegX = regX;
         lastRegY = regY;
      }
   }


Thanks for doing the grunt work!

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline cylab

JGO Ninja


Medals: 56



« Reply #44 - Posted 2013-02-26 14:56:52 »

Since I tested the approach quite intensively, I am a bit surprised that you find it "not even remotely close to drawing a line"...

Are you sure you tested the one from this post:
http://www.java-gaming.org/topics/line-logic/24593/msg/208015/view.html#msg208015

Mathias - I Know What [you] Did Last Summer!
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 849
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #45 - Posted 2013-02-26 15:04:18 »

I tested this one: (with resX=32, resY=32)

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  
private static final void line(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight) {
      int col0 = x0 / cellWidth;
      int row0 = y0 / cellHeight;

      int col1 = x1 / cellWidth;
      int row1 = y1 / cellHeight;

      float m = x0==x1? Integer.MAX_VALUE:(float) (y0 - y1) / (x0 - x1);
      float b = y0 - m * x0;

      if (Math.abs(m) > 1) {
         int lastCol = col0;
         int dir = (y0 < y1) ? 1 : -1;
         for (int row = row0; (dir==1? row <= row1:row >= row1); row += dir) {
            float y = row * cellHeight;
            float x = (y - b) / m;
            int col = (int) (x + 0.5f * dir) / cellWidth;
            if (col != lastCol) {
               y = row * cellHeight - dir;
               x = (y - b) / m;
               int missedCol = (int) (x + 0.5f * dir) / cellWidth;
               if (lastCol != missedCol) {
                 plotter.plot(...);
               }
               lastCol = col;
            }
         }
      } else {
         int lastRow = row0;
         int dir = (x0 < x1) ? 1 : -1;
         for (int col = col0; (dir==1? col <= col1:col >= col1); col += dir) {
            float x = col * cellWidth;
            float y = m * x + b;
            int row = (int) (y + 0.5f * dir) / cellHeight;
            if (row != lastRow) {
               x = col * cellWidth - dir;
               y = m * x + b;
               int missedRow = (int) (y + 0.5f * dir) / cellHeight;
               if (lastRow != missedRow) {
                 plotter.plot(...);
               }
               lastRow = row;
            }
         }
      }
   }


I now see that there is a g.fillRect I missed from the 'original code' -- why anybody would want to benchmark it without that, is beyond me. Anyway, my fault!

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 849
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #46 - Posted 2013-02-26 16:26:51 »



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  
   public static interface Plotter {
      public void plot(int x, int y);
   }

   public static final void plot(int x1, int y1, int x2, int y2, int resX, int resY, Plotter plotter) {
      if ((x1 | y1 | x2 | y2) < 0) {
         throw new IllegalArgumentException();
      }

      int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
      if (dist == 0) {
        plotter.plot(x1, y1);
         return;
      }

      float dx = (float) (x2 - x1) / dist;
      float dy = (float) (y2 - y1) / dist;
      int lastRegX = (int) (x1 + dx + 0.5f) / resX;
      int lastRegY = (int) (y1 + dy + 0.5f) / resY;
     plotter.plot(lastRegX, lastRegY);

      for (int d = 2; d <= dist; d++) {
         int x = (int) (x1 + 0.5f + dx * d);
         int y = (int) (y1 + 0.5f + dy * d);
         int regX = x / resX;
         if (x < 0) {
            regX--;
         }
         int regY = y / resY;
         if (y < 0) {
            regY--;
         }
         if (regX != lastRegX || regY != lastRegY) {
           plotter.plot(regX, regY);
         }
         lastRegX = regX;
         lastRegY = regY;
      }
   }

   public static final void plot2(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Plotter plotter) {
      boolean skipMissedCells = false;

      int col0 = x0 / cellWidth;
      int row0 = y0 / cellHeight;

      int col1 = x1 / cellWidth;
      int row1 = y1 / cellHeight;

      // Shitty workaround to prevent division by 0 on x0==x1...
      float m = x0 == x1 ? Integer.MAX_VALUE : (float) (y0 - y1) / (x0 - x1);
      float b = y0 - m * x0;

      // a "steep" line
      if (Math.abs(m) > 1) {
         int lastCol = col0;
         // does it go up or down?
         int dir = (y0 < y1) ? 1 : -1;
         for (int row = row0; (dir == 1 ? row <= row1 : row >= row1); row += dir) {
            float y = row * cellHeight;
            float x = (y - b) / m;
            int col = (int) (x + 0.5f * dir) / cellWidth;
           plotter.plot(col, row);
            if (!skipMissedCells && col != lastCol) {
               y = row * cellHeight - dir;
               x = (y - b) / m;
               int missedCol = (int) (x + 0.5f * dir) / cellWidth;
               if (lastCol != missedCol) {
                 plotter.plot(missedCol, (row - dir));
               }
               lastCol = col;
            }
         }
      } // a "flat" line
      else {
         int lastRow = row0;
         // does it go right or left?
         int dir = (x0 < x1) ? 1 : -1;
         for (int col = col0; (dir == 1 ? col <= col1 : col >= col1); col += dir) {
            float x = col * cellWidth;
            float y = m * x + b;
            int row = (int) (y + 0.5f * dir) / cellHeight;
           plotter.plot(col, row);
            if (!skipMissedCells && row != lastRow) {
               x = col * cellWidth - dir;
               y = m * x + b;
               int missedRow = (int) (y + 0.5f * dir) / cellHeight;
               if (lastRow != missedRow) {
                 plotter.plot(col - dir, missedRow);
               }
               lastRow = row;
            }
         }
      }
   }

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline cylab

JGO Ninja


Medals: 56



« Reply #47 - Posted 2013-02-26 17:31:29 »

This is the output from the original test program with my algo at the left using x/yres 32 and a line from 50,50 to 400,300



Can you post your test parameters to verify?

Here is the code (I did not update the line2 though):
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  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;

import javax.swing.JFrame;
import javax.swing.WindowConstants;

public class LineTest
{

    private static final int REGION_X = 32;
    private static final int REGION_Y = 32;

    private static int alternate = 0;

    public static void main(String[] args)
    {
        JFrame frame = new JFrame("Line Test");
        frame.setVisible(true);
        final int w = 1024;
        final int h = 512;
        frame.setSize(w, h);
        frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

        Canvas canvas = new Canvas()
        {


            @Override
            public void paint(Graphics g)
            {
                g.setFont(new Font("Times New Roman", Font.PLAIN, 9));
                int fH = g.getFontMetrics().getHeight();
                for (int x = 0; x < w / REGION_X / 2; x++)
                {
                    for (int y = 0; y < h / REGION_Y; y++)
                    {
                        if (x % 2 == 0)
                            if (y % 2 == 1)
                                g.setColor(Color.red);
                            else
                                g.setColor(Color.black);
                        else if (y % 2 == 0)
                            g.setColor(Color.red);
                        else
                            g.setColor(Color.black);
                        g.fillRect(x * REGION_X, y * REGION_Y, REGION_X, REGION_Y);
                        g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
                        g.drawString(x + ", " + y, x * REGION_X + 2, y * REGION_Y + fH);
                    }
                }
                line(50, 50, 400, 300, REGION_X, REGION_Y, g);

                g.setColor(Color.white);
                g.fillRect(w / 2 - 1, 0, 2, h);

                for (int x = w / REGION_X / 2; x < w / REGION_X; x++)
                {
                    for (int y = 0; y < h / REGION_Y; y++)
                    {
                        if (x % 2 == 0)
                            if (y % 2 == 1)
                                g.setColor(Color.red);
                            else
                                g.setColor(Color.black);
                        else if (y % 2 == 0)
                            g.setColor(Color.red);
                        else
                            g.setColor(Color.black);
                        g.fillRect(x * REGION_X, y * REGION_Y, REGION_X, REGION_Y);
                        g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
                        g.drawString(x + ", " + y, x * REGION_X + 2, y * REGION_Y + fH);
                    }
                }
                line2(50 + w / 2, 50, 400 + w / 2, 300, REGION_X, REGION_Y, g);
            }
        };
        canvas.setSize(frame.getSize());
        frame.add(canvas);
    }

    private static final void line(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Graphics g) {
        // flag to get back the old slightly faster but inaccurate version
        boolean skipMissedCells = false;
        int alternate = 0;

        int col0 = x0 / cellWidth;
        int row0 = y0 / cellHeight;

        int col1 = x1 / cellWidth;
        int row1 = y1 / cellHeight;

        // Shitty workaround to prevent division by 0 on x0==x1...
        float m = x0==x1? Integer.MAX_VALUE:(float) (y0 - y1) / (x0 - x1);
        float b = y0 - m * x0;

        // a "steep" line
        if (Math.abs(m) > 1) {
            int lastCol = col0;
            // does it go up or down?
            int dir = (y0 < y1) ? 1 : -1;
            for (int row = row0; (dir==1? row <= row1:row >= row1); row += dir) {
                float y = row * cellHeight;
                float x = (y - b) / m;
                int col = (int) (x + 0.5f * dir) / cellWidth;
                g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
                g.fillRect(col * cellWidth, row * cellHeight, cellWidth, cellHeight);
                // when the sampled column changes, there might be another missed cell
                if (!skipMissedCells && col != lastCol) {
                    // sample again - slightly before the row boundary
                    y = row * cellHeight - dir;
                    x = (y - b) / m;
                    int missedCol = (int) (x + 0.5f * dir) / cellWidth;
                    // really missed that one?
                    if (lastCol != missedCol) {
                        g.setColor(new Color(127, 127, 0));
                        // must be (row-dir), since the missed cell belongs to the last sampled row
                        g.fillRect(missedCol * cellWidth, (row - dir) * cellHeight, cellWidth, cellHeight);
                    }
                    lastCol = col;
                }
            }
        } // a "flat" line
        else {
            int lastRow = row0;
            // does it go right or left?
            int dir = (x0 < x1) ? 1 : -1;
            for (int col = col0; (dir==1? col <= col1:col >= col1); col += dir) {
                float x = col * cellWidth;
                float y = m * x + b;
                int row = (int) (y + 0.5f * dir) / cellHeight;
                g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
                g.fillRect(col * cellWidth, row * cellHeight, cellWidth, cellHeight);
                // when the sampled column changes, there might be another missed cell
                if (!skipMissedCells && row != lastRow) {
                    // sample again - slightly before the column boundary
                    x = col * cellWidth - dir;
                    y = m * x + b;
                    int missedRow = (int) (y + 0.5f * dir) / cellHeight;
                    // really missed that one?
                    if (lastRow != missedRow) {
                        g.setColor(new Color(127, 127, 0));
                        // must be (col-dir), since the missed cell belongs to the last sampled column
                        g.fillRect((col - dir) * cellWidth, missedRow * cellHeight, cellWidth, cellHeight);
                    }
                    lastRow = row;
                }
            }
        }
        g.setColor(Color.pink);
        g.drawLine(x0, y0, x1, y1);
    }

    private static final void line2(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize, Graphics g)
    {
        boolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
        if (steep)
        {
            int tmp = x0;
            x0 = y0;
            y0 = tmp;
            tmp = x1;
            x1 = y1;
            y1 = tmp;
        }
        if (x0 > x1)
        {
            int tmp = x0;
            x0 = x1;
            x1 = tmp;
            tmp = y0;
            y0 = y1;
            y1 = tmp;
        }
        int deltax = x1 - x0;
        int deltay = Math.abs(y1 - y0);
        int error = deltax / 2;
        int ystep = -1;
        int y = y0;
        if (y0 < y1)
            ystep = 1;
        for (int x = x0; x <= x1; x++)
        {
            int absX;
            int absY;
            if (steep)
            {
                absX = y;
                absY = x;
            }
            else
            {
                absX = x;
                absY = y;
            }
            int regX = absX / regionXSize;
            int regY = absY / regionYSize;
            if (absX < 0)
                regX--;
            if (absY < 0)
                regY--;
            g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
            g.fillRect(regX * REGION_X, regY * REGION_Y, REGION_X, REGION_Y);
            int dX;
            int dY;
            if (steep)
            {
                dX = regionYSize - (absY - (regionYSize * regY));
                dY = absX - (regionXSize * regX);
            }
            else
            {
                dX = regionXSize - (absX - (regionXSize * regX));
                dY = absY - (regionYSize * regY);
            }
            int ceil = x + dX;
            for (; x < ceil; x++)
            {
                error -= deltay;
                if (error < 0)
                {
                    y += ystep;
                    error += deltax;
                    dY += ystep;
                    if (dY < 0 || dY > (steep ? regionXSize : regionYSize))
                        break;
                }
            }
        }
        g.setColor(Color.pink);
        g.drawLine(x0, y0, x1, y1);
    }


}

Mathias - I Know What [you] Did Last Summer!
Offline cylab

JGO Ninja


Medals: 56



« Reply #48 - Posted 2013-02-26 18:04:46 »

Actually I hackily switched the test program to your Plotter interface, but still looks good (this time the right green one is mine):


So you might have hit a corner case?

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  
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  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
import javax.swing.*;
import java.awt.*;

public class PlotTest
{
    public static interface Plotter {
        public void plot(int x, int y);
    };

    private static int alternate = 0;

    public static void main(String[] args)
    {
        JFrame frame = new JFrame("Line Test");
        frame.setVisible(true);

        final int xRes = 32;
        final int yRes = 32;

        final int w = xRes*32;
        final int h = yRes*16;

       final int x1 = 32;
       final int y1 = 64;
       final int x2 = 480;
       final int y2 = 257;

        frame.setSize(w, h);
        frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

        Canvas canvas = new Canvas()
        {
            @Override
            public void paint(Graphics g1)
            {
                final Graphics2D g=(Graphics2D)g1;

                g.setFont(new Font("Times New Roman", Font.PLAIN, 9));
                int fH = g.getFontMetrics().getHeight();
                for (int x = 0; x < w / xRes / 2; x++)
                {
                    for (int y = 0; y < h / yRes; y++)
                    {
                        if (x % 2 == 0)
                            if (y % 2 == 1)
                                g.setColor(Color.red);
                            else
                                g.setColor(Color.black);
                        else if (y % 2 == 0)
                            g.setColor(Color.red);
                        else
                            g.setColor(Color.black);
                        g.fillRect(x * xRes, y * yRes, xRes, yRes);
                        g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
                        g.drawString(x + ", " + y, x * xRes + 2, y * yRes + fH);
                    }
                }

                g.setColor(Color.white);
                g.fillRect(w / 2 - 1, 0, 2, h);

                for (int x = w / xRes / 2; x < w / xRes; x++)
                {
                    for (int y = 0; y < h / yRes; y++)
                    {
                        if (x % 2 == 0)
                            if (y % 2 == 1)
                                g.setColor(Color.red);
                            else
                                g.setColor(Color.black);
                        else if (y % 2 == 0)
                            g.setColor(Color.red);
                        else
                            g.setColor(Color.black);
                        g.fillRect(x * xRes, y * yRes, xRes, yRes);
                        g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
                        g.drawString(x + ", " + y, x * xRes + 2, y * yRes + fH);
                    }
                }
                g.setStroke(new BasicStroke(2.5f));

                Plotter plotter1=new Plotter()
                {
                    @Override
                    public void plot(int x, int y)
                    {
                        g.setColor(Color.CYAN);
                        g.drawRect(x * xRes, y * yRes, xRes, yRes);
                    }
                };

                Plotter plotter2=new Plotter()
                {
                    @Override
                    public void plot(int x, int y)
                    {
                        g.setColor(Color.green);
                        g.drawRect(x * xRes, y * yRes, xRes, yRes);
                    }
                };

               PlotTest.plot(x1, y1, x2, y2, xRes, yRes, plotter1);
               PlotTest.plot2(x1 + w / 2, y1, x2 + w / 2, y2, xRes, yRes, plotter2);

                g.setColor(Color.pink);
                g.drawLine(x1, y1, x2, y2);
                g.drawLine(x1 + w / 2, y1, x2 + w / 2, y2);
            }
        };
        canvas.setSize(frame.getSize());
        frame.add(canvas);
    }

    public static final void plot(int x1, int y1, int x2, int y2, int resX, int resY, Plotter plotter) {
        if ((x1 | y1 | x2 | y2) < 0) {
            throw new IllegalArgumentException();
        }

        int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
        if (dist == 0) {
           plotter.plot(x1, y1);
            return;
        }

        float dx = (float) (x2 - x1) / dist;
        float dy = (float) (y2 - y1) / dist;
        int lastRegX = (int) (x1 + dx + 0.5f) / resX;
        int lastRegY = (int) (y1 + dy + 0.5f) / resY;
       plotter.plot(lastRegX, lastRegY);

        for (int d = 2; d <= dist; d++) {
            int x = (int) (x1 + 0.5f + dx * d);
            int y = (int) (y1 + 0.5f + dy * d);
            int regX = x / resX;
            if (x < 0) {
                regX--;
            }
            int regY = y / resY;
            if (y < 0) {
                regY--;
            }
            if (regX != lastRegX || regY != lastRegY) {
               plotter.plot(regX, regY);
            }
            lastRegX = regX;
            lastRegY = regY;
        }
    }

    public static final void plot2(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Plotter plotter) {
        boolean skipMissedCells = false;

        int col0 = x0 / cellWidth;
        int row0 = y0 / cellHeight;

        int col1 = x1 / cellWidth;
        int row1 = y1 / cellHeight;

        // Shitty workaround to prevent division by 0 on x0==x1...
        float m = x0 == x1 ? Integer.MAX_VALUE : (float) (y0 - y1) / (x0 - x1);
        float b = y0 - m * x0;

        // a "steep" line
        if (Math.abs(m) > 1) {
            int lastCol = col0;
            // does it go up or down?
            int dir = (y0 < y1) ? 1 : -1;
            for (int row = row0; (dir == 1 ? row <= row1 : row >= row1); row += dir) {
                float y = row * cellHeight;
                float x = (y - b) / m;
                int col = (int) (x + 0.5f * dir) / cellWidth;
               plotter.plot(col, row);
                if (!skipMissedCells && col != lastCol) {
                    y = row * cellHeight - dir;
                    x = (y - b) / m;
                    int missedCol = (int) (x + 0.5f * dir) / cellWidth;
                    if (lastCol != missedCol) {
                       plotter.plot(missedCol, (row - dir));
                    }
                    lastCol = col;
                }
            }
        } // a "flat" line
        else {
            int lastRow = row0;
            // does it go right or left?
            int dir = (x0 < x1) ? 1 : -1;
            for (int col = col0; (dir == 1 ? col <= col1 : col >= col1); col += dir) {
                float x = col * cellWidth;
                float y = m * x + b;
                int row = (int) (y + 0.5f * dir) / cellHeight;
               plotter.plot(col, row);
                if (!skipMissedCells && row != lastRow) {
                    x = col * cellWidth - dir;
                    y = m * x + b;
                    int missedRow = (int) (y + 0.5f * dir) / cellHeight;
                    if (lastRow != missedRow) {
                       plotter.plot(col - dir, missedRow);
                    }
                    lastRow = row;
                }
            }
        }
    }
}


Mathias - I Know What [you] Did Last Summer!
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 849
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #49 - Posted 2013-02-26 18:16:04 »

Ofcourse I make my tests interactive, so I can test more than a handful of hardcoded examples.

In about 80% of the cases your code provides the correct path.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline sproingie

JGO Kernel


Medals: 202



« Reply #50 - Posted 2013-02-26 21:44:43 »

If you're looking for an antialiased line, there's always Wu's algorithm, or Hugo Elias's take on it:

https://bitbucket.org/chuck/jcod/src/c2e8ae6fd81bafc50bce94e2b2c9a0a26f3137d6/src/main/java/net/fishbulb/jcod/util/PlotAlgorithms.java?at=default#cl-67
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 849
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #51 - Posted 2013-03-14 12:43:44 »

Here is a plotter that supports negative values and doesn't have faulty edge cases.




Can you post your test parameters to verify?
Using your last code, these (and many more) result in incorrect plotting:


(55,46) -> (120,140)
(195,404) -> (81,498)
(218,557) -> (67,427)
(218,557) -> (100,423)
(60,403) -> (77,355)
(299,551) -> (203,487)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline cylab

JGO Ninja


Medals: 56



« Reply #52 - Posted 2013-03-14 15:47:11 »

Ah, ok - I occasionally "attach" the missed grid cells at the wrong side of the found one. I probably won't put any effort into fixing this, since I doubt it will beat your implementation.

Mathias - I Know What [you] Did Last Summer!
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.

Elsealabs (20 views)
2014-12-28 10:39:27

CopyableCougar4 (21 views)
2014-12-28 02:10:29

BurntPizza (25 views)
2014-12-27 22:38:51

Mr.CodeIt (15 views)
2014-12-27 04:03:04

TheDudeFromCI (20 views)
2014-12-27 02:14:49

Mr.CodeIt (26 views)
2014-12-23 03:34:11

rwatson462 (59 views)
2014-12-15 09:26:44

Mr.CodeIt (47 views)
2014-12-14 19:50:38

BurntPizza (98 views)
2014-12-09 22:41:13

BurntPizza (116 views)
2014-12-08 04:46:31
How do I start Java Game Development?
by gouessej
2014-12-27 19:41:21

Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50
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!