Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Raycasting again...  (Read 3489 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd
« Posted 2012-01-04 16:15:36 »

I know there was a thread about this a while ago, but I don't think the problem was really solved.

Basically I need to do an insane but manageable number ray-casts each frame. The problem is that I can't use something "simple" like Bresenham's line algorithm, because I need it to check all tiles touched by the line, similar to conservative rasterisation. My current implementation pretty much sucks, since it relies on lots of special cases and the direction of the line. For now I only need a boolean result, so computing the actual intersection point is not necessary. Any code someone is willing to share? I've been scratching my head about this for way too long now...

EDIT:
Forgot some requirements...
 - Checks all tiles touched by line
 - Line start and end coordinates are doubles, and cannot be rounded to ints before ray-casting.
 - Well, it has to be pretty fast. Most lines are <10 tiles long though.

Myomyomyo.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2012-01-04 17:14:06 »

http://www.java-gaming.org/topics/line-logic/24593/view.html

AFAICS it solves all corner cases.

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

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2012-01-04 17:16:55 »

For a more readable solution, why don't you try:

Create a Rectangle instance for every tile.
Create a Circle instance that fully contains the rectangle of every tile. (bounding circle)

For every tile (or use a heuristic...) do a line/circle intersection test, and if it matches, do a line/rectangle intersection test (basically 4x line/line).

Whether that is fast enough, depends on whether unitCount*avgScanLength is high, not what avgScanLength actually is.


You can also add a hardcoded 2 or 3 level quadtree that prevents you from testing way too many individual tiles.

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 theagentd
« Reply #3 - Posted 2012-01-04 19:33:00 »

The Rectangle/Circle idea is interesting, I would still have to solve the ray-casting problem for actually querying the quadtree containing the circles, so I don't think it's a very good solution performance-wise in my case...

I looked through the Line Logic thread again. I must've fallen asleep when it was about to die, because I think it was actually solved. However, Cylab's solution (and Counterp's too) take int arguments, not floats. I'll see what I can do to change that tomorrow, but damn, I need to sleep now...

Myomyomyo.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2012-01-04 19:41:17 »

The Rectangle/Circle idea is interesting, I would still have to solve the ray-casting problem for actually querying the quadtree containing the circles, so I don't think it's a very good solution performance-wise in my case...
The nice thing of such a hierarchy is that you don't need to write something intelligent: write your rect/circle/line intersection and recurse into the tree.

And don't tell me it's too slow before you actually tried it. It should take 10 minutes to implement this stuff. Remember you only need to check rect/line intersections in the deepest nodes of your tree. With circle/line there will will be some false positives but it will still be faster.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Danny02
« Reply #5 - Posted 2012-01-05 00:57:48 »

did a quick simple implementation of this algorithm
come down to just 33 loc, yeah.

The orange colored tiles get selected in addition to the blue when the CONSERVATIVE_RASTERISATION flag is set


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  
import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import static java.lang.Math.*;

/**
 *
 * @author Daniel Heinrich <DannyNullZwo@gmail.com>
 */

public class Main
{
    private static final boolean CONSERVATIVE_RASTERISATION = false;

    private static class Line
    {
        final Point2D.Double start, end;
        final double xshift;

        public Line(Double s, Double e) {
            start = s.y > e.y ? s : e; // ensures that the starting point of the lines is always above(>y) the end point
           end = s.y > e.y ? e : s;
            double mul = 1. / (start.y - end.y);
            xshift = (end.x - start.x) * mul;
        }
    }

    static void findCells(Line l) {
        final double startXShift = l.xshift * (l.start.y - floor(l.start.y));//amount of x delta in the first tile of the line
       final double endXShift = l.xshift * (ceil(l.end.y) - l.end.y);//amount of x delta in the last tile of the line
       double x = l.start.x;
        double y = l.start.y;
        x = printTiles(x, x + startXShift, y);//gets all Tiles, in the row of the start point, which the line passes
       y = floor(y) - 0.5;
        while (y > ceil(l.end.y))// iterates over all rows which lie between the start and end point of the line
           x = printTiles(x, x + l.xshift, y--);//gets all Tiles in the row which the line passes
       printTiles(x, x + endXShift, y);//gets all Tiles, in the row of the end point, which the line passes
   }

    static double printTiles(double x1, double x2, double y) {
        int firstTile, tileCount;
        if (CONSERVATIVE_RASTERISATION) {
            firstTile = (int) ceil((x2 > x1 ? x1 : x2) - 1.);
            tileCount = (int) floor(abs(x2 - x1) + 1.) + 1;
        } else {
            firstTile = (int) floor((x2 > x1 ? x1 : x2));
            tileCount = (int) ceil(abs(x2 - x1));
        }
        int tileYPos = (int) floor(y);
        for (int i = 0; i < tileCount; ++i)
            printTile(firstTile + i, tileYPos);
        return x2;
    }

    static void printTile(int x, int y) {
        System.out.println("[" + x + ',' + y + ']');
    }

    public static void main(String[] args) {
        Line line = new Line(new Double(0, 2), new Double(4, 0));
        findCells(line);
    }
}
Offline theagentd
« Reply #6 - Posted 2012-01-05 04:41:39 »

The Rectangle/Circle idea is interesting, I would still have to solve the ray-casting problem for actually querying the quadtree containing the circles, so I don't think it's a very good solution performance-wise in my case...
The nice thing of such a hierarchy is that you don't need to write something intelligent: write your rect/circle/line intersection and recurse into the tree.

And don't tell me it's too slow before you actually tried it. It should take 10 minutes to implement this stuff. Remember you only need to check rect/line intersections in the deepest nodes of your tree. With circle/line there will will be some false positives but it will still be faster.
I think the real problem is the performance characteristics. If I'm raycasting through a diagonal corridor for example, I would be checking a lot more tiles since the corridor walls may be solid rock for 10+tiles. What I'm afraid about is a worse case scenario that's worse than actually "rastering" a line between the two points. Maybe I'm wrong, but it seems kind of far-fetched to expect it to be better than rastering. Then again, it might not be that much worse and actually faster in many cases. Still, rastering seem to have more predictable performance, since the Rect/Circle algorithm depends on both line length and the number of nearby walls, while rastering is only dependent on distance (both may end quickly if a wall is encountered though).

@Danny02 Nice! I like your scan-line-like approach to the problem! Seems like a very nice solution, but I'll have to test it before being able to tell. And after writing this, I pretty much have 10 minutes to get dressed, eat, go shopping and come back before my parents come here. Well, SHIT.

Myomyomyo.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2012-01-05 04:44:44 »

What about the quick-and-dirty line drawing algorithm (with lots of false negatives) and checking all neighbouring cells?

It's simple and probably extremely fast.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline theagentd
« Reply #8 - Posted 2012-01-05 05:10:41 »

What about the quick-and-dirty line drawing algorithm (with lots of false negatives) and checking all neighbouring cells?

It's simple and probably extremely fast.
That's what I have right now, but it doesn't work very well at all at the moment. It got really hacky and nasty, so I really need to throw it out and try something new. We'll see how it goes...

Myomyomyo.
Offline theagentd
« Reply #9 - Posted 2012-01-06 14:09:11 »

Danny02, I tested your ray-casting method a lot now. It has some problems... T__T It explodes when start.y = end.y but worst of all, for vertical lines it causes an extra tile to the right or the line being covered. However, the way you tackled the problem has lead me on the right way to solving the problem, so thanks a lot for the code!!!

EDIT: If anyone's interested, here is my perfect quality raycaster with special cases and directions. Like I said, based on Danny02's 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  
public void raycast(double sx, double sy, double ex, double ey){

       if(sx > ex){
          double temp;

          temp = sx;
          sx = ex;
          ex = temp;

          temp = sy;
          sy = ey;
          ey = temp;
       }

       int xsInt = (int)sx;
       int xeInt = (int)Math.ceil(ex);

       double k = ex - sx;
       double divider = ey - sy;

       if(divider == 0){
          //Special case for dy == 0
         int y = (int)sy;
          for(int x = xsInt; x < xeInt; x++){
             printTile(x, y);
          }

       }else{
          k /= divider;
       }

       double left;
       double right = sx;

       if(sy < ey){

          int ysInt = (int)sy;
          int yeInt = (int)Math.ceil(ey);

          right -= (sy - ysInt) * k;

          for(int y = ysInt; y < yeInt; y++){
             left = right;
             right = left + k;

             int lineStart = Math.max((int)left, xsInt);
             int lineEnd = Math.min((int)(right+1), xeInt);
             for(int x = lineStart; x < lineEnd; x++){
                printTile(x, y);
             }
          }

       }else{
          int ysInt = (int)Math.ceil(sy);
          int yeInt = (int)ey;

          right += (ysInt - sy) * k;

          for(int y = ysInt-1; y >= yeInt; y--){
             left = right;
             right = left - k;

             int lineStart = Math.max((int)left, xsInt);
             int lineEnd = Math.min((int)(right+1), xeInt);
             for(int x = lineStart; x < lineEnd; x++){
                printTile(x, y);
             }
          }
       }
    }

Now I just need to benchmark it... >___>

Myomyomyo.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Danny02
« Reply #10 - Posted 2012-01-07 16:18:03 »

mm true, there are some bugs with some corner cases, damn^^

didn't tested it very well, but nice that u fixed(hopefully) all of them
Offline theagentd
« Reply #11 - Posted 2012-01-07 17:30:16 »

Yeah, I think it works perfectly now. Slightly slightly slower than my old (inaccurate) version, but the precision makes up for it! Thanks again!

Myomyomyo.
Pages: [1]
  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.

Dwinin (21 views)
2014-09-12 09:08:26

Norakomi (55 views)
2014-09-10 13:57:51

TehJavaDev (66 views)
2014-09-10 06:39:09

Tekkerue (33 views)
2014-09-09 02:24:56

mitcheeb (54 views)
2014-09-08 06:06:29

BurntPizza (38 views)
2014-09-07 01:13:42

Longarmx (24 views)
2014-09-07 01:12:14

Longarmx (30 views)
2014-09-07 01:11:22

Longarmx (28 views)
2014-09-07 01:10:19

mitcheeb (37 views)
2014-09-04 23:08:59
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

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!