Author Topic: Diagonal Hallways.  (Read 7535 times)

JayPC

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
    • Email
Diagonal Hallways.
« on: July 08, 2011, 02:06:15 AM »
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

  • Rogueliker
  • ***
  • Posts: 349
  • Karma: +0/-0
    • View Profile
    • Infra Arcana
    • Email
Re: Diagonal Hallways.
« Reply #1 on: July 08, 2011, 06:27:19 AM »
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.
« Last Edit: July 08, 2011, 06:35:21 AM by NON »
Happy is the tomb where no wizard hath lain and happy the town at night whose wizards are all ashes.

TSMI

  • Rogueliker
  • ***
  • Posts: 65
  • Karma: +0/-0
    • View Profile
    • Email
Re: Diagonal Hallways.
« Reply #2 on: July 09, 2011, 01:56:31 AM »
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

  • Rogueliker
  • ***
  • Posts: 88
  • Karma: +0/-0
    • View Profile
Re: Diagonal Hallways.
« Reply #3 on: July 09, 2011, 11:52:24 AM »
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.
« Last Edit: July 09, 2011, 12:00:08 PM by Rabiat »

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Diagonal Hallways.
« Reply #4 on: July 09, 2011, 12:24:17 PM »
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

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
    • Email
Re: Diagonal Hallways.
« Reply #5 on: August 24, 2011, 04:59:52 AM »
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...
« Last Edit: August 24, 2011, 06:33:42 AM by JayPC »

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: Diagonal Hallways.
« Reply #6 on: August 24, 2011, 06:27:47 AM »
Most people just use Bresenham's Line Algorithm or similar.

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

JayPC

  • Newcomer
  • Posts: 21
  • Karma: +0/-0
    • View Profile
    • Email
Re: Diagonal Hallways.
« Reply #7 on: August 24, 2011, 06:36:09 AM »
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!