There are several ways passages can be drawn on a two dimensional grid. A first task might be to create a stub program that supports the display of such, with a means to step through the generation of a passage so that the steps can be more closely observed, animations constructed, etc.
#!/usr/bin/env perl
# draws twisty passages
use 5.36.0;
use Curses;
initscr;
noecho;
curs_set 0;
my $running = 1;
my %commands = ( q => sub { $running = 0 }, );
my ( $start, $end );
while ($running) {
unless ( defined $start ) {
( $start, $end ) = two_points();
clear;
addch @$start, '1';
addch @$end, '2';
}
my $step = conn( $start, $end );
if ( defined $step ) {
addch @$step, '#';
} else {
undef $start;
}
my $ch = getchar;
if ( defined $ch ) {
my $fn = $commands{$ch};
$fn->() if defined $fn;
}
}
END { endwin }
########################################################################
#
# SUBROUTINES
# Stub function that will step through "wiring" up the start and end
# points via some method or the other.
sub conn ( $start, $end ) {
# TODO
return undef;
}
# Create two unique [y1,x1],[y2,x2] points within some limit. "y" is
# before "x" as that's the ordering curses uses for mvaddch(3) and such
# calls. $LINES and $COLS are only available after curses init.
sub two_points ( $y_limit = $LINES, $x_limit = $COLS ) {
my ( @p, @d );
@p = map int, rand($y_limit), rand($x_limit);
do {
@d = map int, rand($y_limit), rand($x_limit);
} while ( $p[0] == $d[0] and $p[1] == $d[1] );
return \@p, \@d;
}=> skeleton.pl
Not too interesting, but also not very hard to write, and getting some numbers onto the screen can be a good start.
1
2A next thing one might think to use is a Dijkstra Map, mainly because I have a module that already handles such.
#!/usr/bin/env perl
# draw twisty passages - Dijkstra Map version
use 5.36.0;
use Curses;
use Game::DijkstraMap;
initscr;
noecho;
curs_set 0;
my $running = 1;
my %commands = ( q => sub { $running = 0 }, );
my ( $start, $end );
while ($running) {
unless ( defined $start ) {
clear;
refresh;
( $start, $end ) = two_points();
init_conn( $start, $end );
addch @$start, '1';
addch @$end, '2';
}
my $ch = getchar;
if ( defined $ch ) {
my $fn = $commands{$ch};
$fn->() if defined $fn;
}
my $step = conn( $start, $end );
if ( defined $step ) {
if ( same_point( $step, $end ) ) {
undef $start;
} else {
addch @$step, '#';
@$start = @$step;
}
} else {
undef $start;
}
}
END { endwin }
########################################################################
#
# SUBROUTINES
{
my $dm;
# Pick the "best" route; this may involve random choice when there
# is more than one equally valid option.
sub conn ( $start, $end ) {
my $next = $dm->next_best(@$start);
}
# Make an empty map with no obstacles that cannot be moved into
# (such as walls); mark the destination (there can be multiple
# destinations with a Dijkstra Map).
sub init_conn ( $start, $end, $y_limit = $LINES, $x_limit = $COLS ) {
$dm = Game::DijkstraMap->new;
$dm->next_m('next_sq'); # no diagonal moves allowed!
my @grid;
for my $y ( 0 .. $y_limit - 1 ) {
for my $x ( 0 .. $x_limit - 1 ) {
$grid[$y][$x] = $dm->max_cost;
}
}
$grid[ $end->[0] ][ $end->[1] ] = $dm->min_cost;
$dm->dimap( \@grid );
$dm->recalc;
}
}
sub same_point ( $p, $d ) { $p->[0] == $d->[0] and $p->[1] == $d->[1] }
sub two_points ( $y_limit = $LINES, $x_limit = $COLS ) {
my ( @p, @d );
@p = map int, rand($y_limit), rand($x_limit);
do {
@d = map int, rand($y_limit), rand($x_limit);
} while ( $p[0] == $d[0] and $p[1] == $d[1] ); # inlined same_point
return \@p, \@d;
}=> dimap.pl
One downside is that the code is very slow, but for a game one would doubtless write the pathfinding in a faster language or optimize the heck out of it. Being able to quickly prototype things and to have a lot of fiddly features can however be benefits in other contexts.
####### 2
#
####
1The path will vary randomly when presented with next steps of equal weight. Other games may want to give more preference to moving in the same direction, and still others may want to vary the path even more. A Dijkstra Map will not wander outside the minimum values, though one could pick the best direction and then continue that direction for a while before returning to the Dijkstra Map method. Additional complications could be created by pre-seeding the level map with random noise or rooms, though these may also create sources and destinations that are impossible to reach. A Dijkstra Map can also be used to detect such unconnected regions: unconnected cells will still have the "max cost" or "no cost" value that indicates the map did not reach those cells. Many games demand a fully connected level map; others may instead give the player a pickaxe and maybe some remote sensing options.
Dijkstra Maps are good when there are multiple destinations, though are more expensive than other pathfinding methods if you simply need to get from point A to point B. Einstellung is also a thing, or me reaching for a Dijkstra Map as I've used those before.
rogue(6) uses a "conn" function to run a passage to another room, or sometimes creates a dead-end. The code assumes the rogue room grid (a three by three grid containing up to nine rooms), and only draws passages down, or to the right. Rooms in rogue may sometimes be omitted. In this case a random point is used from which to draw the passage from or to.
-------- -------- --------
| room |------->| room |------->| room |
-------- -------- --------
| | |
v v v
-------- -------- --------
| room |------->| room |------->| room |
-------- -------- --------
| | |
v v |
-------- -------- v
| room |------->| room |-----------># (a fake room point)
-------- --------A single turn is (perhaps) made; this is used to line the passage up with the other door (or fake room point) of the target room at some random point. This explains how "crossed passages" can emerge in rogue, as show below. Starting from the fake room point "!" the passage is either wired up downwards, or to the right. The downwards passage makes a turn after two steps, then lines itself up with the door below before reverting to the original downwards motion. The passage to the right does similar; coincidentally the "end of the turned direction run" point is the same, so the two passages cross one another. Had the rightwards run continued for a bit longer, or the downwards had gone down more before the turn, or if the starting point had been different the passages would have missed one another, as they usually often do.
############### ---------
# # |.......+#######
#################################+.......| #
# |.......| #
# |.......| #
# ----+---- #####################
# # ######
# ## ---------+---
------+----- --+-- |...........|
|..........| |...| |...........|
|..........| |...| |...........| ------------->Right
!##############v -
|# #R---------------->|
v#################################+
D------------>D# |
o |# |
w |# -
n |#
v#
------+-----From this one should be able to explain the passage on the right side of the level map. Where do you think the fake room point was?
The code in rogue can be made more generic; given start "S" and end "E" points a passage can be woven across the level map, incorporating random turns and accounting for various complications such as having a stopping point should it run on for far too long, much like this sentence does, or having gotten itself into a dead end with no valid moves, or when it has looped back onto itself, then it should also end. A downside here is that the code can get pretty complicated, and there may be no guarantee that the passage will wire itself up correctly.
0123456789
0..........
1.S##......
2.###......
3.###.-----
4.###.|
5.###.E
6...#.|
7...##-----
8....#...##
9....######Here the algorithm, which draws a line of some random length in some direction more likely to be towards the end, missed the end and got stuck. The algorithm could be run multiple times until a good solution is found, and then maybe only for some number of iterations, which may not be ideal for energy use nor for how long it takes to maybe not work. On the other hand, quite diverse lines can be drawn, and an algorithm that moreso makes a beeline for the end will likely create a less diverse set of passages, and will waste less energy in so doing.
0123456789
0..........
1#S........
2#.........
3#....-----
4#....|
5#...#E
6#####|
7.....-----
8..........
9..........
0123456789
0..........
1.S........
2.#........
3##...-----
4#####|
5..###E
6..##.|
7..##.-----
8..##......
9..##......
0123456789
0...#####..
1.S######..
2....#.....
3....#-----
4....#|
5....#E
6.....|
7.....-----
8..........
9..........Depending on where the rooms are there may be no solution for a passage whatsoever, so not placing rooms too close together or blocking off sections of the map might be good. Some algorithms simply draw lines through walls and rooms and whatever to link things up, which does get the job done but may have too much of a "followed a roguelike tutorial" feel about it.
=> passager.pl
Maybe someone can do a better job with something like that algorithm, it was getting too complicated and fiddly for me.
Another option would be to draw a maze that includes the start and end points, solve the maze between those two points, and then erase all or most of the maze. Assuming the maze algorithm produces twisty passages (some tend not to), the passage should be reasonably twisty. The maze would also need to account for any existing rooms or other such obstacles (the pits of despair, etc) on the level map. This may be more useful if you use more than a little of such a maze so aren't throwing most of the work away, or use the maze code for something else as well. On the other hand maze algorithms tend to be more studied and implemented than random procgen code that maybe can draw some lines sometimes.
What if closer distances to the target got a better score, so the passage would be more likely to take that route? One problem will be the passage still getting stuck in a local minimum. Backtracking to less favorable and longer routes around some obstacle will therefore be necessary. This is or eventually will become an A-Star search, so maybe use that instead? Maybe some funk (or soul) could be added to the scoring function to make for passages with more bends in them, at some additional CPU cost over a more direct approach.
rogue(6) has the advantage that the room locations are known and do not conflict with one another (once enough of the errors were removed). That is, there's no capital-H shaped obstacles where one must go a long way around to reach the other indentation of that letter. Nor are there cases where motion through an area is impossible because something has blocked off that entire section of the map, and passages never need to get to a room at the other side of another room. Designing the larger level map a certain way can avoid problems that a more generic solution will have to deal with.
...............
....#.....#....
....#..S..#....
....#.....#....
....#######....
....#.....#....
....#..E..#....
....#.....#....
...............A useful technique is to divide a level map into smaller rectangles and then run some algorithm with each rectangle. This way a large area can be divided into smaller ones, and one space may have a passage, another a room, and still another both rooms and passage, down to some minimum rectangle size. Here one will probably have designated points where other rectangles link up with the rectangle, and perhaps a border so that adjacent rectangle contents do not conflict with one another, besides the doorlikes connecting them. Pre-fabs could also be placed into such rectangles, though these may need to be picked first if the pre-fabricated room has static points of entry and exit that other things must wire up to: proc gen content can (in theory) build itself out from a random starting point.
Pre-fabs may also go by the name of "Dungeon Geomorphs" and could replace random generation if there are enough geomorphs to allow building a dungeon by random selection of geomorphs that fit to the exiting geomorphs in play. Another advantage of pre-fabs is that the player will begin to recognize known rooms, which can help avoid the dungeon being either too regular, or too much of an alphabet soup. This is somewhat like the Real World™ where there will be interminable and mostly forgettable trails that link resources such as a stream or pond, that place where the bee hives are, etc.
Pre-fabs are thus something like a theme or motif in music. My god, they killed Kenny!
=> https://www.kenney.nl/assets This content has been proxied by September (ba2dc).Proxy Information
text/gemini