Diagonal Hallways.

[JayPC]

its been a while but im back in town.

Diagonal hallways seem to be halting all progress on a Psudeo Rougelike Im working on. im trying to make a Map generator from scratch and Ive run into this problem.

I cant seem to find a formula to reduce slope to the least common Denominator.


I have 2 points the Slope before finding the LCD is 17/26 if point 1 is 0,0 and point 2 is 17,26 using

(0-17)/(0-26) = 1.5294117647059

My issue is then how do I convert theat into int rise; int run; ?? I cant just make it Round up or down cause a 1/1 and a 2/1 dont connect the points.

[NON]

I'm not 100% sure what the situation is here but...

Why not just:
(C++ pseudocode, type casts omitted)

Code: [Select]

const int x0 = 0;
const int y0 = 0;
const int x1 = 17;
const int y1 = 26;

//(The values above would be sent as parameters to a function doing the operations below)

const float xIncr = (x1-x0) / (y1-y0); //Of course (x1-x0) and (y1-y0) need to be separately casted to float

float x = x0;

for(int y = y0; y <= y1; y++) {
   dungeon->landscape[x][y] = stoneFloor;
   x += xIncr;
}

I don't know, maybe it's not that simple.

[TSMI]

Yeah I am really confused here as well. You already have the slope as a ratio of two integers. What do you want exactly?

[Rabiat]

Perhaps JayPC's game doesn't allow diagonal movement, so two diagonally connected floor tiles need to be connected horizontally or vertically?

In that case, using NON's example, reducing the increment of y to .5 would work, except for (nearly) 45 degree slopes.

To guarantee orthogonal connections, you could just generate a map with diagonal connections and run the result through a cellular automaton like this:

Code: [Select]

turn .#  into ..  or .#
     #.       #.     ..
Edit:

Or, you're calculating slope incorrectly. 17/26 = 0.65 after all, not 1.53. To guarantee connected floor tiles, you don't need a lowest common denominator, you need the slope to be <= 1.0.

[Z]

I am not sure whether diagonal corridors are a good idea for a game which does not allow diagonal movement. Maybe combinations of horizontal and diagonal segments would be better.

But you can guarantee orthogonal connections by making sure that if (x0,y0) and (x1,y1) are two consecutive coordinates of the corridor (calculated with some formula), then (x0,y1) is also in the corridor. This works if you know that BOTH the difference between x0 and x1 is 1 AND the distance between y0 and y1 is at most 1. If not, you can fix it further by adding all (x0,y0..y1) and (x0..x1,y1) to the corridor.

[JayPC]

Sorry for the late reply My issue was creating the Hall

Code: [Select]

A * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * B


I need to make a Hallway from "A" to "B" by turning the * into .

Im looking to create a carveDiagonalHall() method that starts at 0,0 and then goes at a rate of X/Y to reach B

The game is only a Psuedo Roguelike and angled movement is allowed.

a 1/1 rate looks like

a 1/1 ratio

Code: [Select]

A . * * * * * * * * * * * * * * * * * * * * * * * *
 * . . * * * * * * * * * * * * * * * * * * * * * * *
 * * . . * * * * * * * * * * * * * * * * * * * * * *
 * * * . . * * * * * * * * * * * * * * * * * * * * *
 * * * * . . * * * * * * * * * * * * * * * * * * * *
 * * * * * . . * * * * * * * * * * * * * * * * * * *
 * * * * * * . . * * * * * * * * * * * * * * * * * *
 * * * * * * * . . * * * * * * * * * * * * * * * * *
 * * * * * * * * . . * * * * * * * * * * * * * * * *
 * * * * * * * * * . . * * * * * * * * * * * * * * *
 * * * * * * * * * * . . * * * * * * * * * * * * * *
 * * * * * * * * * * * . . * * * * * * * * * * * * *
 * * * * * * * * * * * * . . * * * * * * * * * * * *
 * * * * * * * * * * * * * . . * * * * * * * * * * *
 * * * * * * * * * * * * * * . . * * * * * * * * * *
 * * * * * * * * * * * * * * * . . * * * * * * * * *
 * * * * * * * * * * * * * * * * . . * * * * * * * *
 * * * * * * * * * * * * * * * * * . . * * * * * *B

a 1/2 ratio

Code: [Select]

A . . * * * * * * * * * * * * * * * * * * * * * * *
 * * . . . * * * * * * * * * * * * * * * * * * * * *
 * * * * . . . * * * * * * * * * * * * * * * * * * *
 * * * * * * . . . * * * * * * * * * * * * * * * * *
 * * * * * * * * . . . * * * * * * * * * * * * * * *
 * * * * * * * * * * . . . * * * * * * * * * * * * *
 * * * * * * * * * * * * . . . * * * * * * * * * * *
 * * * * * * * * * * * * * * . . . * * * * * * * * *
 * * * * * * * * * * * * * * * * . . . * * * * * * *
 * * * * * * * * * * * * * * * * * * . . . * * * * *
 * * * * * * * * * * * * * * * * * * * * . . . * * *
 * * * * * * * * * * * * * * * * * * * * * * . . . *
 * * * * * * * * * * * * * * * * * * * * * * * * . .
 * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * *B


this alternates between 1/1 and 1/2

Code: [Select]

A . * * * * * * * * * * * * * * * * * * * * * * * *
 * . . . * * * * * * * * * * * * * * * * * * * * * *
 * * * . . * * * * * * * * * * * * * * * * * * * * *
 * * * * . . . * * * * * * * * * * * * * * * * * * *
 * * * * * * . . * * * * * * * * * * * * * * * * * *
 * * * * * * * . . . * * * * * * * * * * * * * * * *
 * * * * * * * * * . . * * * * * * * * * * * * * * *
 * * * * * * * * * * . . . * * * * * * * * * * * * *
 * * * * * * * * * * * * . . * * * * * * * * * * * *
 * * * * * * * * * * * * * . . . * * * * * * * * * *
 * * * * * * * * * * * * * * * . . * * * * * * * * *
 * * * * * * * * * * * * * * * * . . . * * * * * * *
 * * * * * * * * * * * * * * * * * * . . * * * * * *
 * * * * * * * * * * * * * * * * * * * . . . * * * *
 * * * * * * * * * * * * * * * * * * * * * . . * * *
 * * * * * * * * * * * * * * * * * * * * * * . . . *
 * * * * * * * * * * * * * * * * * * * * * * * * . .
 * * * * * * * * * * * * * * * * * * * * * * * * *B

as you can see the hybrid "kinda" works but I need to figure out what the ratio is based on the 2 points entered and then carve out that path

To clairify, Im trying to create my first Dungeon Generator. and the system Im using creates a Room and then connects the rooms with halls. that connect to the center od the room. I was going to try BSP

http://doryen.eptalys.net/articles/bsp-dungeon-generation/

But im having a hard time coding the actual generator. I understand the concept but actually doing it is harder then I thought...

[corremn]

Most people just use Bresenham's Line Algorithm or similar.

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

[JayPC]

Most people just use Bresenham's Line Algorithm or similar.

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Thanks!! Looks like it will work!