代写地牢游戏，实现一个随机的地牢生成器。
Requirement
It’s time to start developing our Roguelike game. We’ll begin by generating a
dungeon. Some details are specified below, but generating a good-looking
dungeon is largely a matter of taste. The figure shows an example generated by
(an old version of) my game.
Because it’s so much a matter of taste, you may decide how you want your
dungeon to look and come up with your own heuristics to generate that look.
Things to keep in mind are playability and realism. Yeah, it’s a fantasy game
where we fight monsters in underground dungeons, but that doesn’t mean there’s
no realism! Corridors that are too straight are probably unrealistic; after
all, veins of harder minerals occur in the rock, and miners will probably
tunnel around them. On a more practical note, large open areas, wide
corridors, and overly straight corridors give advantages to monsters in play
because the player does not have architectural features to use to tactical
advantage. A poor dungeon leads to an unplayable game. Players need places to
rest and hide out of sight of fire-breathing dragons and balrogs, spell-
casting necromancers, and arrow-loosing orc hordes. On the other hand, often
line of sight is useful for your own attacks, so you don’t want your passages
too twisty.
Your dungeon generator should be written with an eye toward extensibility.
Remember that you will be.
—————————————————————————–
| …………. ….. |
| …………. ###….. |
| ……… …………. #### ….. |
| …. ……… …………. ## ….. |
| …. ……… …………. # ….. |
| …. ……… …………. ### ….. |
| ….################# ……… …………. # ….. |
| # #######……… …………. ## ….. |
| # # #……… # ### # |
| # ## ######## ##### # |
| # ## ######## ## #…….. |
| ## # # # # ##############…….. |
| # …. ## # # # |
| ## …. # …. #….. |
| ….####…. ### …. #….. |
| ….# ….# ### …. #….. |
| ….# ## |
| ….######## |
| |
—————————————————————————–
An example randomly-generated dungeon from my code. Rock is represented by
spaces, room floor by periods, and corridor floor by hashes. The border was
added artificially to demarcate the map from the page. While you’re welcome to
draw a border around your dungeon (and many students do), this one is only
here so that you can see the bounds of my dungeon in this document.
Adding functionality on top of this next week, and for the rest of the
semester (see the roguelike roadmap on the assignments page). For this step,
you generate a dungeon, draw it on the standard output, and exit. Here are the
requirements:
- All code is in C.
- Dungeon measures 80 units in the x (horizontal) direction and 21 units in the y (vertical) direction. A standard terminal is 80 24, and limiting the dungeon to 21 rows leaves three rows for text, things like gameplay messages and player status, which come later.
- Require at least 5 rooms per dungeon
- Each room measures at least 3 units in the x direction and at least 2 units in the y direction.
- Rooms need not be rectangular, but neither may they contact one another. There must be at least 1 cell of non-room between any two different rooms.
- The outermost cells of the dungeon are immutable, thus they must remain rock and cannot be part of any room or corridor.
- Room cells should be drawn with periods, corridor cells with hashes, and rock with spaces.
- The dungeon should be fully connected, meaning that from any position on the floor, your adventurer should be able to walk to any other position on the floor without passing through rock.
- Corridors should not extend into rooms, e.g., no hashes should be rendered inside rooms.
Here is an informal description of a dungeon generator that I wrote to produce
the figure; I’ve played with dungeon generation enough to know that much
simpler methods can do the job, but this method does a nice job of balancing
aesthetically-pleasing (to me) dungeons and having a small, straightforward
imple- mentation. There are certain tunable parameters, for example,
determining the size of a new room, that I leave out of the description. You
may use this algorithm, something you find online, or something of your own
devising.
To implement my algorithm, you will need an array of rooms and an 80 21 matrix
of cells representing the dungeon. I initialize the dungeon by setting an
immutable flag on the outermost cells and assigning a hardness to the material
in every cell. I then attempt to randomly place random rooms in the available
space, checking that the room can be placed legally each time, until some
termination criterion is reached. Example criteria: the dungeon is at least 7%
open (not rock); there were 2000 failed placement attempts in a row; a create
new room() predicate failed; etc.
After placing rooms, move through the room array of n rooms, connecting room 1
with room 2, then room 3 with rooms 1-2, . . . until you’ve connected room n
with rooms 1-(n 1). Okay, so how do we make that connection? Find the closest
room in the already connected set using Euclidean distance to its centroid
then carve a path to it by changing rock to open space; this can always be
done with zero or one change of direction. If you get that working, then add
some random changes of direction in there to make it look a little more
exciting.
So why do I have that rock hardness? Well, our adventurer and monsters will
eventually be able to tunnel through the dungeon, so hardness will be a useful
notion to influence tunneling, but for now I use it to drive a corridor
heuristic. I use Dijkstra’s algorithm where my edge weights are rock
hardnesses and modified with penalties for direction changes to find shortest
paths between 1-2, 2-3, . . ., (n 1)-n. If you implement this, you’ll find
that your code will draw corridors directly to nearby rooms too oftenthe
dungeon ends up connected, but there are never any loops, and I think that’s
kind of boringso you need to weight empty space close to the hardness of the
softest rock to get more satisfying results. You may be thinking that this is
an interesting method, but it requires a priority queue, so it’s too much
work. That may be trueup to you to decidehowever: 1) A priority queue is easy
to implement; and 2) You’ll need one eventually, anyway, in order for monsters
to move around the dungeon without getting stuck in corners.
