2
\$\begingroup\$

DEFINITIONS:

Any "Point (x, y)" mentioned below is really the bottom left coordinates of a 1 unit by 1 unit rectangle. A "Line" is a defined as a rectangle that is either 1 unit tall and 1 unit or greater wide, or 1 unit wide and 1 unit or greater tall. These rectangles are constructed given a Rectangle(bottomLeftX, bottomLeftY, width, height). The height and/or width can be negative. If either are it will shift the start x or y accordingly as so:

public Rectangle(int x1, int y1, int width, int height) {
  _left = x1;
  _right = x1;
  if(width < 0)
    _left += width;
  else
    _right += width;

  _bottom = y1;
  _top = y1;
  if(height < 0)
    _bottom += height;
  else
    _top += height;
}

THE GOAL:

Given two arbitrary points, define two lines (as rectangles) connecting the two points. The two lines need to randomly 'bend' at one of the two possible connections (see below). The two points aren't in any specific order. Point A's X and/or Y can be above, below or even the same as Point B's X and/or Y.

Example Setup

THE PROBLEM:

I have made a solution that only partially works. There is a bug in my method below where sometimes the two lines do not connect at the bend/junction. It seems to only be when the bend/junction is in the bottom right of the points' bounds.

WHAT I HAVE NOW:

A little background: I'm working on a random dungeon generator. I create rooms randomly, and then I am going to connect them using the described point and line system above. Here's what I have now. "graph" is a Map>, technically it's directional, but the reason was so that I wouldn't draw the same lines twice.

int x, y, dx, dy;
Rectangle a, b;
// loop through each edge of the graph
for(Rectangle outer:graph.keySet()) {
  for(Rectangle inner:graph.get(outer)) {
    // randomly set a and b
    if(random.nextBoolean()) {
      a = outer;
      b = inner;
    } else {
      a = inner;
      b = outer;
    }

    // generate the origin points based on a
    x = (int) a.getCenterX();
    y = (int) a.getCenterY();
    // and the delta of b to a
    dx = (int) b.getCenterX()-x;
    dy = (int) b.getCenterY()-y;

    // create line starting at a, then
    // create line starting at end of above line
    lines.add(new Rectangle(x, y, dx, 1));
    lines.add(new Rectangle(x+dx, y+dy, 1, -dy));
  }
}

Here's what it produces. Most of the time it works, however there are cases where the corners do not line up. I'm not sure how to fix this.

enter image description here

Any input is much appreciated.

\$\endgroup\$
  • \$\begingroup\$ Your problem is just the gap in the lines ? Or there is something else ? Because I understood that everything works but this. \$\endgroup\$ – Heckel May 20 '14 at 14:49
  • \$\begingroup\$ @Heckel I've updated the question with a more clearly defined problem. But yes, it is the disconnect of the two lines that is the issue. \$\endgroup\$ – Fisher Evans May 20 '14 at 14:59
  • \$\begingroup\$ Please wait until you can answer your own question to post an answer. Answers should only go in the answers section, not the question body. This will not only make the question/answer more clear for future visitors, but it'll also likely result in more reputation for you :). \$\endgroup\$ – MichaelHouse May 20 '14 at 17:42
1
\$\begingroup\$

I think the problem comes from the rectangle width. See on the image below, the two lines are suposed to connect at the red cross. The dark blue lines represent the rectangles if they had no width. When you enlarge the line it creates a gap.

enter image description here

To avoid this, you can make the horizontal line larger.

enter image description here

lines.add(new Rectangle(x, y, dx+lineWidth, 1)); // here lineWidth = 1

Although my code creates a problem. I don't think it is very important but when the lines are like the image below the darker area is covered twice (by both line).

enter image description here

\$\endgroup\$
  • \$\begingroup\$ I edited, my first post was wrong. \$\endgroup\$ – Heckel May 20 '14 at 15:15
  • \$\begingroup\$ I tried this out and it fixed the cases where there was a disconnect, but caused the opposite cases in other places (over shooting by 1). I'm betting that it's because the A and B have a random relationship. I'm trying out a solution where A is guaranteed to be further left or the same as B. Will update shortly. Thanks for the help. \$\endgroup\$ – Fisher Evans May 20 '14 at 15:40
  • \$\begingroup\$ You can test if dx is positive or negative, the line width should not be added a the same place in each case. \$\endgroup\$ – Heckel May 20 '14 at 15:44
  • \$\begingroup\$ I've found a solution. Wouldn't have gotten to it without your illustration pointing out the widthless rectangles. See my question for my solution as I cannot answer my own question yet. \$\endgroup\$ – Fisher Evans May 20 '14 at 15:53
1
\$\begingroup\$

So, the problem was occurring due to the fact the A could be on either side of B, thus adjusting the width would fix the cases where A was to the left of B, but break the cases where A was to the right of B. So I ensure A is always to the left of B, allowing the additional width to always produce the desired result.

This could have been done reverse as well, whether A was always to the right of B, or even to the Top or Bottom, but having that guarantee allows the logic to work 100% of the time.

THE SOLUTION:

// define variables
int dx, dy, x, y;
Rectangle a, b;
// loops through each "edge"
for(Rectangle outer:keys) {
  for(Rectangle inner:graph.get(outer)) {
    // ensure A is never to the right of B
    if(outer.getCenterX() < inner.getCenterX()) {
      a = outer;
      b = inner;
    } else {
      a = inner;
      b = outer;
    }
    // the starting points
    x = (int) a.getCenterX();
    y = (int) a.getCenterY();
    // the deltas to get from A to B
    dx = (int) b.getCenterX()-x;
    dy = (int) b.getCenterY()-y;
    // randomly bend clockwise or counter clockwise
    if(random.nextInt(1) == 1) {
      halls.add(new Rectangle(x, y, dx+1, 1)); // start at a
      halls.add(new Rectangle(x+dx, y, 1, dy)); // start at the end of the last line
    } else {
      halls.add(new Rectangle(x, y+dy, dx+1, 1)); // same as above
      halls.add(new Rectangle(x, y, 1, dy)); // swapped horizontal and vertical
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.