Anonymous user
Maze generation: Difference between revisions
→{{header|D}}: one more
m (→{{header|Ada}}: oops, wrong works-with Ada version) |
(→{{header|D}}: one more) |
||
Line 294:
=={{header|D}}==
===First version===
{{works with|D|2}}
<lang d>import std.stdio, std.random, std.array;
Line 433 ⟶ 434:
| | | |
+---+---+---+---+---+---+---+---+---+---+---+</pre>
===Second version===
{{works with|D|2.050}}
<lang d>import std.stdio, std.random ;
immutable string[] Tiles =
["\u2003","╞","╥","╔","╡","═", "╗","╦","╨","╚","║","╠","╝","╩","╣","╬"] ;
alias ubyte Room ;
enum Open { EMPTY = 0U , EAST = 1, SOUTH = 2, WEST = 4, NORTH = 8,
ENTRY = 16, EXIT = 32, Visited = 64 }
struct Where {
immutable int x, y ;
Where opBinary(string op)(Where rhs) if (op=="+") {
return Where(x + rhs.x, y + rhs.y) ;
}
bool bounded(int w, int h) {
return (x >= 0 && y >= 0 && x < w && y < h) ;
}
}
struct Door { Open opening = Open.EMPTY ; Where where ; }
Room[][] genMaze(uint w, uint h, ref Door entry = Door.init, ref Door exit = Door.init) {
Room[][] r = new Room[][](h, w) ; // default value = 0 means un-visited empty room
immutable Open[Open] Opposite = [Open.EAST:Open.WEST, Open.SOUTH:Open.NORTH,
Open.WEST:Open.EAST, Open.NORTH:Open.SOUTH] ;
immutable Where[Open] NeibrPos = [Open.EAST:Where( 1,0), Open.SOUTH:Where(0, 1),
Open.WEST:Where(-1,0), Open.NORTH:Where(0,-1)] ;
void breakWall(Door d) {
r[d.where.y][d.where.x] |= d.opening ;
auto there = d.where + NeibrPos[d.opening] ;
if(there.bounded(w,h))
r[there.y][there.x] |= Opposite[d.opening] ;
}
bool validDoor(Door d) {
if(d.where.bounded(w,h))
switch(d.opening) {
case Open.EAST : return (d.where.x == w - 1) ;
case Open.WEST : return (d.where.x == 0) ;
case Open.NORTH: return (d.where.y == 0) ;
case Open.SOUTH: return (d.where.y == h - 1) ;
}
return false ;
}
Door makeDoor() { // create door at random edge
switch([Open.EAST, Open.WEST, Open.NORTH, Open.SOUTH][uniform(0,4)]) {
case Open.EAST : return Door(Open.EAST , Where(w-1, uniform(0,h))) ;
case Open.WEST : return Door(Open.WEST , Where( 0, uniform(0,h))) ;
case Open.NORTH: return Door(Open.NORTH, Where(uniform(0,w), 0)) ;
case Open.SOUTH: return Door(Open.SOUTH, Where(uniform(0,w), h-1)) ;
}
}
Open[] neibrDir ;
foreach(d; NeibrPos.keys)
neibrDir ~= d ;
// depth-first search algorithm to generate maze
void visit(Where here) {
r[here.y][here.x] |= Open.Visited ;
randomShuffle(neibrDir) ;
foreach(dir; neibrDir) {
auto there = here + NeibrPos[dir] ;
if(there.bounded(w,h)) // bounded?
if((r[there.y][there.x] & Open.Visited) == 0) { // un-visited?
breakWall(Door(dir, here)) ;
visit(there) ;
}
}
}
// make entry & exit doors if not provided or invalid
while(entry.opening == Open.EMPTY || entry.where == exit.where || !validDoor(entry))
entry = makeDoor() ;
while( exit.opening == Open.EMPTY || entry.where == exit.where || !validDoor(exit))
exit = makeDoor() ;
r[entry.where.y][entry.where.x] |= (entry.opening | Open.ENTRY) ;
r[ exit.where.y][ exit.where.x] |= ( exit.opening | Open.EXIT) ;
// generate maze starting from entry
visit(entry.where) ;
return r ;
}
void printMaze(Room[][] maze, bool withMark = false) {
foreach(row ; maze) {
foreach(cell;row)
if(withMark && (cell & Open.ENTRY))
write("S") ;
else if(withMark && (cell & Open.EXIT))
write("G") ;
else
write(Tiles[cell & 0xf]) ;
writeln() ;
}
}
void main() {
Door entry, exit;
auto maze = genMaze(40, 12, entry, exit) ;
writefln("Entry - x:%2d y:%2d", entry.where.x, entry.where.y) ;
writefln("Exit - x:%2d y:%2d", exit.where.x, exit.where.y) ;
printMaze(maze) ;
writeln() ;
printMaze(maze, true) ; // with entry/exit mark
}</lang>
output:
<pre style="line-height:1em; font-size:200%; font-family:Courier New;">Entry - x:18 y: 0
Exit - x:22 y: 0
╔═╗╔╗╔═╡╔═╦═╗╞══╦╡╚═╗╔╩═╗╔╡╔╗╔══╗╔══╗╔═╗
╨╔╣║╚╣╥╔╝╔╝╥╚╗╔═╣╔╗╥║║╞╗║║╔╝╚╣╔╡╚╩═╡╠╝╔╝
╔╝║║╥╚╣║╥║╔╣╞╣╚╗╨║║╠╝╚╗║╠╝║╞╗║╚═╗╔═╗║╥╠╡
╠╗║║╚╗╚╝║║║╨╔╝╔╝╔╝║╚╗╔╝║╚╗║╔╝╚═╗║║╥║╚╝╚╗
╨║╨║╔╣╞╦╝║║╔╝╥║╔╝╥╚═╝╚╗╠═╝╠╝╔═╗╚╝║╚╩══╗║
╔╩╗╚╝╚╗╠╡║╚╣╔╩╝║╥╠═══╗║╚╡╔╝╔╝╞╣╞═╬═══╗╚╝
║╔╩╡╔╗║╚╗║╔╩╩═╡║╚╩═╗╔╝╠╗╔╝╥║╔╗╚═╦╝╔═╗║╞╗
║╚══╝╚╝╥║║║╔═══╝╥╔═╣║╞╝╠╝╞╣╚╝╚═╗╨╔╩╡║╚═╣
╚════╦╡╠╝║╨║╞╗╔╡╠╝╔╝╚╦╡╚═╗╠╗╞═╗╚═╝╔═╝╞╦╝
╞════╩╦╩╡╚═╩═╣╠═╝╔╝╔╗╚═╗╞╣║║╔╗║╔═╡╚══╗╚╗
╔═╗╔╦╡╚════╗╔╝╚╡╔╝╔╝╚═╗╚╗╚╝╚╝╚╩╝╔══╗╔╝╔╝
╚╡╚╝╚══════╝╚═══╝╞╝╞══╩═╩═══════╝╞═╩╝╞╩╡
╔═╗╔╗╔═╡╔═╦═╗╞══╦╡S═╗╔G═╗╔╡╔╗╔══╗╔══╗╔═╗
╨╔╣║╚╣╥╔╝╔╝╥╚╗╔═╣╔╗╥║║╞╗║║╔╝╚╣╔╡╚╩═╡╠╝╔╝
╔╝║║╥╚╣║╥║╔╣╞╣╚╗╨║║╠╝╚╗║╠╝║╞╗║╚═╗╔═╗║╥╠╡
╠╗║║╚╗╚╝║║║╨╔╝╔╝╔╝║╚╗╔╝║╚╗║╔╝╚═╗║║╥║╚╝╚╗
╨║╨║╔╣╞╦╝║║╔╝╥║╔╝╥╚═╝╚╗╠═╝╠╝╔═╗╚╝║╚╩══╗║
╔╩╗╚╝╚╗╠╡║╚╣╔╩╝║╥╠═══╗║╚╡╔╝╔╝╞╣╞═╬═══╗╚╝
║╔╩╡╔╗║╚╗║╔╩╩═╡║╚╩═╗╔╝╠╗╔╝╥║╔╗╚═╦╝╔═╗║╞╗
║╚══╝╚╝╥║║║╔═══╝╥╔═╣║╞╝╠╝╞╣╚╝╚═╗╨╔╩╡║╚═╣
╚════╦╡╠╝║╨║╞╗╔╡╠╝╔╝╚╦╡╚═╗╠╗╞═╗╚═╝╔═╝╞╦╝
╞════╩╦╩╡╚═╩═╣╠═╝╔╝╔╗╚═╗╞╣║║╔╗║╔═╡╚══╗╚╗
╔═╗╔╦╡╚════╗╔╝╚╡╔╝╔╝╚═╗╚╗╚╝╚╝╚╩╝╔══╗╔╝╔╝
╚╡╚╝╚══════╝╚═══╝╞╝╞══╩═╩═══════╝╞═╩╝╞╩╡
</pre>
=={{header|J}}==
| |||