Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (581)
games submitted by our members
Games in WIP (500)
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 8012 times)
0 Members and 1 Guest are viewing this topic.
Offline counterp

Senior Member


Medals: 11



« Posted 2011-08-05 22:54:04 »



In this beautiful illustration I made with my vast graphical skills, there are 4 regions (rightly labeled) and a line that passes through 3 of them (regions 2-4).

What is the best way to check which regions the line pass through. Do I have to manually loop through the 4 regions to see if the line lies in its boundaries? Can I take the starting and end point of the line to see which regions it lies in? Is there example code? I'm a bit too tired to think logically.
Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #1 - Posted 2011-08-05 23:01:44 »

Hello!

You can check out my topic: http://www.java-gaming.org/topics/avoiding-looping-through-everything/24587/view.html
where pseudocode was given, and apply it to the lines ends. However, that doesn't tell if it passes through any other regions.

Offline counterp

Senior Member


Medals: 11



« Reply #2 - Posted 2011-08-05 23:43:50 »

I need to know all regions a line lies on, and it can be on infinitely many regions.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #3 - Posted 2011-08-06 04:50:21 »

I am not sure if that is it or not
http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm

But I do know that a seperating axis theorem check of "Line vs AABB" will work if you just compare the line to a group of AABBs (Axis Aligned Bounded Boxes) as each region.


I can write a small little code for it come Monday thatll do exactly this. About to head out of town for weekend right now though.

edit:
Although I think their code might be in C# or C++ I Am sure you can hack it together to work in Java.
http://www.gamedev.net/topic/338987-aabb---line-segment-intersection-test/

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

Senior Member


Medals: 11



« Reply #4 - Posted 2011-08-06 13:19:54 »

Ahh well, I ended up doing it by myself (namrog I would still appreciate if you write your code so I can compare speeds).

Heres 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  
   private static final void getRegionsOfLine(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize) {
      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--;
         // Region is: (regX, regY)
        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 == -1 || dY == (steep ? regionXSize : regionYSize))
                  break;
            }
         }
      }
   }


EDIT: bug fixes
Offline counterp

Senior Member


Medals: 11



« Reply #5 - Posted 2011-08-08 19:18:38 »

Are there any faster solutions?
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #6 - Posted 2011-08-08 19:31:10 »

Ill write something up this week sometime.
I officially just got kicked out of gf's place and I can't move into my new apartment for a few more days so I am officially the homeless bum on JGO right now Tongue

"Experience is what you get when you did not get what you wanted"
Offline theagentd
« Reply #7 - Posted 2011-08-08 21:57:06 »

 Undecided Tough luck, man...

Myomyomyo.
Offline counterp

Senior Member


Medals: 11



« Reply #8 - Posted 2011-08-08 22:06:03 »

Aww sorry to hear that  Cry
Online Riven
« League of Dukes »

JGO Overlord


Medals: 606
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2011-08-08 23:46:09 »

Ill write something up this week sometime.
I officially just got kicked out of gf's place and I can't move into my new apartment for a few more days so I am officially the homeless bum on JGO right now Tongue

I want to share some words of wisdom, I recently picked up:
'Experience is what you get when you did not get what you wanted' -namrog84


Goodluck! Emo and enjoy your hotel!



if you want, you can seek closure in the JGO vault.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #10 - Posted 2011-08-09 15:06:34 »

haha thanks everyone. Great advice Riven Smiley  sorry for hijacking the line logic thread counterp.
p.s. I slept in my car last night Smiley Yay for work computer!


counterp, I didn't write these but compare speeds of these 2 methods. 1 is from the internals of the java's rect2d


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
Line2D.Double line = new Line2D.Double(20,40,600,400); I chose this at random number
//should use a custom linetype to reduce casting for int
int rX=20;  //how many X rect
int rY=20;  //how many Y rect
int spacing=25; //you can separate this into xSpace and ySpace for non squares
 
public void render(Graphics g) {
    g.drawLine((int)line.x1, (int)line.y1, (int)line.x2, (int)line.y2);
    for(int i=0;i<rX;i++){
      for(int j=0;j<rY;j++){

            //if(SegmentIntersectRectangle(i*spacing,j*spacing,i*spacing+spacing,j*spacing+spacing,line.x1,line.y1,line.x2,line.y2)){
           //other test to compare
        if(intersectsLine(line.x1, line.y1, line.x2, line.y2,i*spacing, j*spacing, spacing, spacing)){
            g.setColor(Color.red); //hit!
        }else{
            g.setColor(Color.white); //miss!
        }
         
         g.drawRect(i*spacing, j*spacing, spacing, spacing);
      }
   }
}

//could throw a few of the rectX/Y and sizes into constants of some kind to help improve efficiency a little of having to not redo multiplication.



first test
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  
private static final int OUT_LEFT = 1;
private static final int OUT_TOP = 2;
private static final int OUT_RIGHT = 4;
private static final int OUT_BOTTOM = 8;

   
   
private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) {
        int out = 0;
        if (rectWidth <= 0) {
            out |= OUT_LEFT | OUT_RIGHT;
        } else if (pX < rectX) {
            out |= OUT_LEFT;
        } else if (pX > rectX + rectWidth) {
            out |= OUT_RIGHT;
        }
        if (rectHeight <= 0) {
            out |= OUT_TOP | OUT_BOTTOM;
        } else if (pY < rectY) {
            out |= OUT_TOP;
        } else if (pY > rectY + rectHeight) {
            out |= OUT_BOTTOM;
        }
        return out;
    }

public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) {
        int out1, out2;
        if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) {
            return true;
        }
        while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) {
            if ((out1 & out2) != 0) {
                return false;
            }
            if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
                double x = rectX;
                if ((out1 & OUT_RIGHT) != 0) {
                    x += rectWidth;
                }
                lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1);
                lineX1 = x;
            } else {
                double y = rectY;
                if ((out1 & OUT_BOTTOM) != 0) {
                    y += rectHeight;
                }
                lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1);
                lineY1 = y;
            }
        }
        return true;
    }



2nd test
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  
boolean SegmentIntersectRectangle(double a_rectangleMinX,
         double a_rectangleMinY, double a_rectangleMaxX,
         double a_rectangleMaxY, double a_p1x, double a_p1y, double a_p2x,
         double a_p2y) {
      // Find min and max X for the segment

      double minX = a_p1x;
      double maxX = a_p2x;

      if (a_p1x > a_p2x) {
         minX = a_p2x;
         maxX = a_p1x;
      }
      // Find the intersection of the segment's and rectangle's x-projections
     if (maxX > a_rectangleMaxX) {
         maxX = a_rectangleMaxX;
      }
      if (minX < a_rectangleMinX) {
         minX = a_rectangleMinX;
      }
      if (minX > maxX) // If their projections do not intersect return false
     {
         return false;
      }
      // Find corresponding min and max Y for min and max X we found before

      double minY = a_p1y;
      double maxY = a_p2y;

      double dx = a_p2x - a_p1x;

      if (Math.abs(dx) > 0.0000001) {
         double a = (a_p2y - a_p1y) / dx;
         double b = a_p1y - a * a_p1x;
         minY = a * minX + b;
         maxY = a * maxX + b;
      }

      if (minY > maxY) {
         double tmp = maxY;
         maxY = minY;
         minY = tmp;
      }
      // Find the intersection of the segment's and rectangle's y-projections
     if (maxY > a_rectangleMaxY) {
         maxY = a_rectangleMaxY;
      }
      if (minY < a_rectangleMinY) {
         minY = a_rectangleMinY;
      }
      if (minY > maxY) // If Y-projections do not intersect return false
     {
         return false;
      }
      return true;
   }



edit:
I still can see a custom solution in my head that I feel like is way quicker and like 5 lines tops.  Itd use

double m=(line.y1-line.y2)/(line.x1-line.x2);
double b = m*line.x1-line.y1;

then a return function with 4 or 8 &&|| sets of ?<x<?

I also could imagine another one, that doesn't need to blunt force your way through ALL the rectangles(as clearly some have 0 chance of ever being in it, but by using the slope calculation,  directly hit numbers in simple boolean grid[][]; So you wouldnt need a nested for loop(this should be the fastest) for detection? but a direct  grid[pointY/rectHeight] = HIT;




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

Senior Member


Medals: 11



« Reply #11 - Posted 2011-08-09 15:55:49 »

Ahh well, I don't think bruteforcing will work well, I tested yours and it's rather slow with small lines and large lines alike.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 606
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2011-08-09 16:01:13 »

Quote
1  
double m=(line.y1-line.y2)/(line.x1-line.x2);
this will explode if x1==x2

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

Senior Member


Medals: 11



« Reply #13 - Posted 2011-08-09 16:30:21 »

it's on the tip of my mind (lol) but I KNOW that some important optimizations can be done to mine to avoid the second loop.
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #14 - Posted 2011-08-09 17:04:15 »

I suppose you'd need a special case for vertical/horizontal lines

easiest way would probably just nudge the line slightly non vertical anytime it equals vertical.
otherwise special case code Sad



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

JGO Knight


Medals: 34



« Reply #15 - Posted 2011-08-09 17:49:55 »

Are there any faster solutions?

I assume your regions are laid out in a regular grid, so you can calculate the start and end cell like:
1  
2  
3  
4  
5  
int col0 = (int) ((float)x0/regionWidth);
int row0 = (int) ((float)y0/regionHeigth);

int col1 = (int) ((float)x1/regionWidth);
int row1 = (int) ((float)y1/regionHeigth);


line equation is
1  
2  
3  
y=m*x+b
=>
x=(y-b)/m


with x0/y0, x1/y1 you can solve this to
1  
2  
m=(y0-y1)/(x0-x1)
b=y0-m*x0  


now everything you have to do is to sample from col0/row0 to col1/row1 with regionWidth or regionHeight stepping (depending on |m|<>1)

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  
int col0 = (int) ((float)x0/regionWidth);
int row0 = (int) ((float)y0/regionHeigth);

int col1 = (int) ((float)x1/regionWidth);
int row1 = (int) ((float)y1/regionHeigth);

float m=(float)(y0-y1)/(x0-x1)
float b=y0-m*x0

// a "steep" line
if(Math.abs(m)>1)
{
  // does it go up or down?
 int dir=(y0<y1)1:-1;
  for(int row=row0; row!=row1; row+=dir)
  {
    float y= row*regionHeight;
    float x= (y-b)/m;
    int col = (int) (x/regionWidth);
    // TODO store row and col somewhere
 }
}
// a "flat" line
else
{
  // does it go right or left?
 int dir=(x0<x1)1:-1;
  for(int col=col0; col!=col1; col+=dir)
  {
    float x= col*regionWidth;
    float y=m*x+b;
    int row = (int) (y/regionHeight);
    // TODO store row and col somewhere
 }
}


Haven't tested it, but should work

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

Senior Member


Medals: 11



« Reply #16 - Posted 2011-08-09 18:01:53 »

perrrrrrrfect-o

although it's a shame that you aren't as gifted in italian cuisine as I am Tongue

EDIT: ahh well yours doesn't fill all the required squares
Offline counterp

Senior Member


Medals: 11



« Reply #17 - Posted 2011-08-09 18:33:33 »

You can visualize it with this (contains both of our methods side by side, mine seems to be a bit inaccurate :\ )

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  
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 Main {

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

   private static int alternate = 0;

   public static void main(String[] args) {
      JFrame frame = new JFrame("Line Test");
      frame.setVisible(true);
      final int w = 1000;
      final int h = 500;
      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 regionWidth, int regionHeight, Graphics g) {
      int col0 = (int) ((float)x0/regionWidth);
      int row0 = (int) ((float)y0/regionHeight);
       
      int col1 = (int) ((float)x1/regionWidth);
      int row1 = (int) ((float)y1/regionHeight);
       
      float m=(float)(y0-y1)/(x0-x1);
      float b=y0-m*x0;
       
      // a "steep" line
     if(Math.abs(m)>1)
      {
        // does it go up or down?
       int dir=(y0<y1)?1:-1;
        for(int row=row0; row!=row1; row+=dir)
        {
          float y= row*regionHeight;
          float x= (y-b)/m;
          int col = (int) (x/regionWidth);
          g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
          g.fillRect(col * REGION_X, row * REGION_Y, REGION_X, REGION_Y);
        }
      }
      // a "flat" line
     else
      {
        // does it go right or left?
       int dir=(x0<x1)?1:-1;
        for(int col=col0; col!=col1; col+=dir)
        {
          float x= col*regionWidth;
          float y=m*x+b;
          int row = (int) (y/regionHeight);
          g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
          g.fillRect(col * REGION_X, row * REGION_Y, REGION_X, REGION_Y);
        }
      }
      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);
   }

}


EDIT: modified the code to make it easier to spot differences

EDIT2: OK one last modification to show coordinates
Offline cylab

JGO Knight


Medals: 34



« Reply #18 - Posted 2011-08-09 18:58:04 »

The missing squares of my implementation are due to only sampling when entering a col/row. To match all the squares the code has to be modified to also sample when leaving the col/row. This then can be optimized to only being done when the sampled row/col differs from the last one. Maybe I'll find some time this eve.

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

JGO Knight


Medals: 34



« Reply #19 - Posted 2011-08-09 20:43:17 »

Here's the accurate version:

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  
    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 = (int) ((float)x0/cellWidth);
        int row0 = (int) ((float)y0/cellHeight);
         
        int col1 = (int) ((float)x1/cellWidth);
        int row1 = (int) ((float)y1/cellHeight);
         
        // fill start and end cell
       g.setColor(new Color(0, 127,127));
        g.fillRect(col0 * cellWidth, row0 * cellHeight, cellWidth, cellHeight);
        g.fillRect(col1 * cellWidth, row1 * cellHeight, cellWidth, cellHeight);
       
        float m=(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; row!=row1; row+=dir)
          {
            float y= row*cellHeight;
            float x= (y-b)/m;
            int col = (int) (x/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-1;
              x= (y-b)/m;
              int missedCol = (int) (x/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; col!=col1; col+=dir)
          {
            float x = col*cellWidth;
            float y = m*x+b;
            int row = (int) (y/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-1;
              y = m*x+b;
              int missedRow = (int) (y/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);
    }

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

Senior Member


Medals: 11



« Reply #20 - Posted 2011-08-09 22:43:20 »

Is there anyway to get it wholly accurate.

Consider the arguments: line(45, 45, 300, 12, REGION_X, REGION_Y, g);

It is just barely in region (8, 1) but the method doesn't flag this region.

Or will it never happen because of using floats?

I fixed the accuracy problem with my version

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  
    private static final void line(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize, Graphics g) {
       int alternate = 0;
       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);
            System.out.println(regX + " " + regY);
            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 - 1;
            for (; x < ceil; x++) {
                error -= deltay;
                if (error < 0) {
                    y += ystep;
                    error += deltax;
                    dY += ystep;
                    if (dY <= -1 || dY >= (steep ? regionXSize : regionYSize))
                        break;
                }
            }
        }
    }
Offline cylab

JGO Knight


Medals: 34



« Reply #21 - Posted 2011-08-09 23:30:59 »

Yeah, the float to int casting always rounds down, while the drawLine() rounds more accurate. I simply added a 0.5f bias before casting - that should do the trick. I also fixed an error where the missed cells don't get detected correctly on negative direction: 

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  
    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;
         
        // fill start and end cell
       g.setColor(new Color(0, 127,127));
        g.fillRect(col0 * cellWidth, row0 * cellHeight, cellWidth, cellHeight);
        g.fillRect(col1 * cellWidth, row1 * cellHeight, cellWidth, cellHeight);
       
        float m=(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; 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; 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);
    }

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

Senior Member


Medals: 11



« Reply #22 - Posted 2011-08-09 23:41:40 »

1  
line(0, 0, 400, 390, REGION_X, REGION_Y, g);


cuts off the last box after changing rows (15, 15) :p

I wish I knew how your code worked so I could do these changes myself but I could never quite wrap my head around this kind of geometry :\

well thanks for your help so far
Offline cylab

JGO Knight


Medals: 34



« Reply #23 - Posted 2011-08-09 23:54:30 »

btw. did some benchmarking:

1  
2  
Tested line1 (cylab), 3000000 iterations. Took 869ms
Tested line2 (counterp), 3000000 iterations. Took 3185ms


Edit: Just found some infinite loop with my implementation on some values, so needs more work.

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

JGO Knight


Medals: 34



« Reply #24 - Posted 2011-08-09 23:58:14 »

cuts off the last box after changing rows (15, 15) :p

That's because the missing match check is not done for the endpoint (since it is calculated beforehand and not in the loop)

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

Senior Member


Medals: 11



« Reply #25 - Posted 2011-08-10 02:58:13 »

Ahh well it was an easy enough fix.

Is the infinite loop in the current version you posted? If so, when does it occur?
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #26 - Posted 2011-08-10 15:21:13 »

arghh cylab!
 Angry hate you! Cranky
I was thinking last night this morning, it finally came to me to use a slope with a xSpacingStepping or for y and do it that way. I am all excited coming into work, and then boom. You come out of no where and present exactly what I had been all excited to write!
 Grin arghhh!  Huh


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

Senior Member


Medals: 11



« Reply #27 - Posted 2011-08-10 17:39:57 »

well his still has an infinite loop glitch and still doesn't work with negatives if you want to give it a shot Tongue
Offline cylab

JGO Knight


Medals: 34



« Reply #28 - Posted 2011-08-10 22:51:05 »

well his still has an infinite loop glitch and still doesn't work with negatives if you want to give it a shot Tongue

* fixed infinite loop
* fixed last missed cell
* work accurate with x0 > x1, x0 < x1, y0 > y1, y0 < y1
* won't explode on x0==x1 (quickfix - should be an own special case)

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  
  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);
  }


benchmarked with

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  
    int iter=3000000;
    {
      long start=System.nanoTime();
      for(int i=0; i<iter; i++)
      {
        int x0 = (int) (Math.random()*1000);
        int y0 = (int) (Math.random()*1000);
        int x1 = (int) (Math.random()*1000);
        int y1 = (int) (Math.random()*1000);
        line1(x0, y0, x1, y1, REGION_X, REGION_Y);
      }
      long end=System.nanoTime();
      System.out.println("Tested line1 (cylab), "+iter+" iterations. Took "+(end-start)/1000000+"ms");
    }
    {
      long start=System.nanoTime();
      for(int i=0; i<iter; i++)
      {
        int x0 = (int) (Math.random()*1000);
        int y0 = (int) (Math.random()*1000);
        int x1 = (int) (Math.random()*1000);
        int y1 = (int) (Math.random()*1000);
        line2(x0, y0, x1, y1, REGION_X, REGION_Y);
      }
      long end=System.nanoTime();
      System.out.println("Tested line2 (counterp), "+iter+" iterations. Took "+(end-start)/1000000+"ms");
    }


(removed all graphics for benchmarking)

Result
1  
2  
Tested line1 (cylab), 3000000 iterations. Took 637ms
Tested line2 (counterp), 3000000 iterations. Took 8127ms

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

Senior Member


Medals: 11



« Reply #29 - Posted 2011-08-11 19:41:42 »

EDIT: must fix bug
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.

xsi3rr4x (64 views)
2014-04-15 18:08:23

BurntPizza (62 views)
2014-04-15 03:46:01

UprightPath (75 views)
2014-04-14 17:39:50

UprightPath (58 views)
2014-04-14 17:35:47

Porlus (76 views)
2014-04-14 15:48:38

tom_mai78101 (101 views)
2014-04-10 04:04:31

BurntPizza (161 views)
2014-04-08 23:06:04

tom_mai78101 (256 views)
2014-04-05 13:34:39

trollwarrior1 (209 views)
2014-04-04 12:06:45

CJLetsGame (216 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
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!