Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (595) Games in Android Showcase (168) games submitted by our members Games in WIP (646) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: 1 [2]
 ignore  |  Print
 Line Logic  (Read 10941 times) 0 Members and 1 Guest are viewing this topic.
cylab

JGO Wizard

Medals: 85

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

Looks nice, but:

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

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

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"
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?
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"
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
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"
cylab

JGO Wizard

Medals: 85

 « 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!
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

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

JGO Wizard

Medals: 85

 « 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!
counterp

Senior Devvie

Medals: 11

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

It does, and there are no boundaries

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)
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.
counterp

Senior Devvie

Medals: 11

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

that's very slow
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1001
Projects: 4
Exp: 16 years

 « 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

 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 rankings!
cylab

JGO Wizard

Medals: 85

 « 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!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1001
Projects: 4
Exp: 16 years

 « 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 rankings!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1001
Projects: 4
Exp: 16 years

 « 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 rankings!
cylab

JGO Wizard

Medals: 85

 « 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!
cylab

JGO Wizard

Medals: 85

 « 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!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1001
Projects: 4
Exp: 16 years

 « 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 rankings!
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
Riven
« League of Dukes »

« JGO Overlord »

Medals: 1001
Projects: 4
Exp: 16 years

 « 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 rankings!
cylab

JGO Wizard

Medals: 85

 « 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.

 deepthought (49 views) 2015-06-30 15:39:44 deepthought (56 views) 2015-06-30 15:39:09 deepthought (65 views) 2015-06-30 15:36:52 Za\'Anzabar (42 views) 2015-06-29 05:44:54 TritonDreyja (49 views) 2015-06-24 17:10:40 CopyableCougar4 (49 views) 2015-06-23 00:34:45 BurntPizza (57 views) 2015-06-21 20:36:46 cookiecompiler (98 views) 2015-06-11 15:42:53 cookiecompiler (57 views) 2015-06-11 15:41:14 NegativeZero (81 views) 2015-06-11 09:49:18
 princec 31x wessles 23x orangepascal 19x CopyableCougar4 19x BurntPizza 18x opiop65 17x EgonOlsen 16x ags1 15x nsigma 15x Riven 13x KaiHH 12x Jesse 11x SauronWatchesYou 11x theagentd 11x KevinWorkman 11x sunburn 11x
 How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14
 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