rec.games.roguelike.development FAQ
Ido Yehieli
Find it on the web at:
http://roguebasin.roguelikedevelopment.org/index.php?title=Roguelike_Dev_FAQ
# # ## #
### ## ## ## ## ### ## ## # ###
#### ## ## # # ## ## ## # # ### ##
# ### ## ## ## ## # ## ### # # #### ###
# ## ## ## ## #### ## ## ###### ## # ## #######
### ## ## ## ## ## ## ## ## # #### ###
# ## ### #### ##### ## ### ## ## ### ##
## ## ## ### ## # ###### ## ## ## ##
##
## ### ### ### ## #
#### ## ## ## ###### ### ###
## ## ## ## # # ## ## # ## ###
## ## ####### ## ## ### ## # ## #
## ## ### # ## ##### #### # ## ##
## ### ## ### ## ## ## ## ##
#### ### ### ### ## ## #####
## ## ###
# Roguelike Dev FAQ ##
# v. 0.0.2
By Damjan Jovanovic
Table of contents
1 GENERAL
1.1 What is rogue?
1.2 What is a roguelike game?
1.3 What are the major roguelike games today?
1.3.1 ADOM
1.3.2 Moria
1.3.3 Angband
1.3.4 Nethack
1.3.5 Dungeon Crawl
1.4 What roguelikes games websites / newsgroups are there?
1.5 What should I know when first posting to r.g.r.d?
2 GENERAL DEVELOPMENT QUESTIONS
2.1 How and by how are roguelike games generally made?
2.2 Which programming language are roguelikes generally made in?
2.3 Do you have to know programming to make your own roguelike?
2.4 How do you make a variant to a roguelike?
3 DESIGN ISSUES
3.1 Do you have to design a roguelike game before you program it?
3.2 Why do many roguelikes later undergo a major rewrite?
3.3 What needs to be planned in advance?
3.4 What do people like about roguelikes?
3.5 How do you finish making your roguelike?
4 OUTPUT AND REPRESENTATION
4.1 Do roguelikes have to be done in ASCII text?
4.2 How do you add graphics?
4.3 How do you make a 3D roguelike?
4.4 Which libraries let you position the cursor and change text
colours?
5 STORY AND SETTING
5.1 Which stories are possible for a roguelike?
5.2 What themes and settings are possible for a roguelike?
5.3 What is / how do I make a good atmosphere?
5.4 What are quests and how are they diffrent from other forms of
plot?
5.5 What are the standard types of quests?
5.6 How do I make good quests?
5.7 How do I make a good quest randomizer?
6 DUNGEON MECHANICS
6.1 How are dungeons represented?
6.2 How are dungeons generated?
6.3 How do you make dungeons with a theme?
6.4 How do you make sure all your rooms and passages are reachable?
6.5 How do you make a town?
6.6 How do you make wilderness?
6.7 How do you make persistant dungeons / worlds?
6.8 How do you store a really BIG world?
6.9 How do you deal with stuff happening far from the player?
6.9.1 Monsters
6.10 What is LOS, and how and why do you do it?
6.11 How do you store the list of all the items in the game?
6.12 How do you store the items in the player's inventory?
6.13 How do you make randomly generated items?
6.14 Which kinds of monsters should I use in my roguelike?
6.15 How do you create a monster AI?
6.16 How do you create a good monster AI?
6.17 How do they find / follow the player?
6.18 How do you add variety to your monsters?
6.19 How do you make your battle system?
6.20 How do you represent, store and process monsters?
7 SPELLS
7.1 How do you represent a magic system?
7.2 What is a good magic system to use?
7.3 How do you enchant objects or make "enchanted" objects?
7.4 How do you make random spells?
GENERAL
What is rogue?
Rogue is a text-based game made in the 1970's that started it all. You
explored a dungeon, gathering items, fighting monsters and getting
stronger. There was no point to this all; but eventually they made it
so the main quest was to find the Amulet of Yendor.
What separated rogue from most similar text-based games of its time
was
how it handled the output. Most adventure games described the
environment (eg. "You are in a small room, with a passage out behind
you"); rogue "drew" it using text. For instance, if you were standing
in the room described above, this is how it would look (the "@" being
you):
#####
# ######
# @
# ######
# #
#####
Back at the time, PC's were virtually unheard of, and most computers
were just dumb terminals connected to a mainframe, with no graphics.
Drawing with text was a big novelty. Rogue was incredibly addictive in
its time. It was eventually distributed with Unix.
What is a roguelike game?
This is a topic that has caused vehement debates in the
rec.games.roguelike.development newsgroup. I will just explain it as
simply as possible.
Let's see about the features of rogue:
* Single player
* Text based
* Randomly generated dungeon levels
* Turn based (ie. nothing happens until yyou press a key that does
something)
* The emphasis is on good gameplay rather than good graphics
* Death is permanent. No loading saved games, no coming back to
life. Once you die, you can only start from the beginning with a new
character.
Firstly, you have to realise that games are not as easy to classify
into genres as books or films are. There is a lot of games that don't
belong into any one genre. Purists may argue that any game that is
graphical and real-time (as opposed to turn-based) cannot be a
roguelike, but not everyone agrees.
There is some overlap between roguelikes and role-playing games,
adventure games, and so on.
Briefly then, "roguelike" is more of a feeling you get in a game
rather
than a set of criteria that have to be followed. Just to make things
more confusing, here are some more things that can be found in modern
roguelikes:
* "Dungeons and dragons" style of skills
* The maker is usually 1 person. The moree popular games have "dev
teams" which work on them later.
* Magic systems usually implemented
* Usually set in fantasy middle ages (exceptions exist; sci-fi
roguelikes do exist, see Theme)
What are the major roguelike games today?
ADOM
Website: http://www.adom.de/
ADOM is Thomas Biskup's one-man effort. Inspired by the D&D universe,
ADOM is a fantasy romp with a quaintly humorous mood. It has a
handmade
overworld map called the Drakalor Chain. It's player's job to track
down the source of Chaos overtaking the land. The closer the player
gets to the source, the more tainted with Chaos he becomes.
Moria
"Mines of Moria" or just "Moria" is around. It is loosely set in
Tokien's mines of Moria in "Lord of the Rings". It is not being
developed any more; only "maintained".
Angband
Website: http://www.thangorodrim.org/
"Angband", is a newer roguelike based on Moria but even more loosely
based on "Lord of the Rings". There is probably more variants to this
one than to any other roguelike. The variants often used entirely
different monsters and goals; not all of them involve Tolkien's works.
Nethack
Website: http://www.nethack.org/
NetHack is the modern roguelike which is the most direct descendant of
the original Rogue. NetHack offers a very varied and sometimes
whimsical playing experience; a favourite saying amongst players is
that the Dev Team "have thought of everything". The focus of the game
is relatively narrow - there's no town or wilderness, but just a
single
dungeon to get down to the bottom of and retrieve the Amulet of Yender
from - however, individual levels are more varied than is typical of
many roguelikes. The game is relatively short; it's possible to win in
8 hours of play if you put your mind to it - partly because the
dungeon
levels are static during the game, so unlike in other games you have
little choice but to press on past explored levels deeper into the
dungeon.
Dungeon Crawl
Website: http://www.dungeoncrawl.org/
What roguelikes games websites / newsgroups are there?
rec.games.roguelike.angband
Discusses the roguelike game Angband and its variants.
rec.games.roguelike.nethack
Discusses the roguelike game Nethack and its variants.
rec.games.roguelike.adom
Discusses the roguelike game ADOM.
rec.games.roguelike.misc
Discusses all roguelike games which don't have a newsgroup of
their
own yet.
rec.games.roguelike.development
Discusses all topics which are related to the development of
roguelike games.
rec.games.roguelike.announce
A moderated group for announcements about roguelike games.
rec.games.roguelike.moria
Discusses the roguelike game Moria, parent of Angband. This
newsgroup is almost dead.
rec.games.roguelike.rogue
Discusses the original roguelike, Rogue. This newsgroup is almost
dead.
alt.games.omega
Discusses the roguelike game Omega. Activity is rare. Development
discussion has a Yahoo group.
The best resource when it comes to roguelikes is the Roguelike News,
which lists the games in development, development articles and news
about the latest releases of major roguelikes. Unfortunately, the news
site presumably shut down some time ago, but an alternative news is
available (http://arns.freeservers.com/). An even better alternative
with more development articles that are often updated is
http://roguelikedevelopment.org/
What should I know when first posting to r.g.r.d?
Some places are more newbie-friendly than others. The developers at
rec.games.roguelike.development may sometimes show little patience
with
questions which have been asked many times. Here are two simple things
you can do to ensure that you get off to a good start:
- Do some research before you ask a question. If the answer is
available via a search engine, why ask here? If the research does not
turn up a satisfactory answer, then by all means ask, and you will be
able to ask a better, more focused question as a result of your
earlier
work. Demonstrate that you have some initiative, and you will get a
much more helpful response. As well as searching the web in general,
search r.g.r.d.
- Don't ask what the best programming language for a roguelike is, or
if a particular language is suitable for roguelike programming. If you
want to know why, search r.g.r.d via Google Groups for "best
programming language" and you will find many flamewars sparked by that
question and its variants. The topic has been done to death, and many
developers are tired of it.
GENERAL DEVELOPMENT QUESTIONS
How and by how are roguelike games generally made?
By a selection of people from all over the world, with too much free
time on their hands =). People looking to learn a programming
language,
people who play games for a while and end up wanting to make it their
way, people who want to make a game by themselves and have no artistic
talent (if you're gonna use text at least =).
Usually by people learning computer programming; originally it was
students of computer science or similar courses at college or
university. Of couse, anyone can make them who wants to.
Which programming language are roguelikes generally made in?
Traditionally, C, because of its portability and because other
programming languages weren't available at the time. Nowdays, a
variety: Java, C++, Pascal, scripting languages etc. The best language
for your roguelike is the one you know well.
Do you have to know programming to make your own roguelike?
Yes. There is no other way. Read books. Read articles and tutorials on
the Internet. Look at lots of source code. Most of all, get yourself a
compiler (most are available for free on the Internet) and practise. A
lot.
>From here on onwards, I will assume the reader of this FAQ is familiar
and fairly proficient with computer programming and related concepts.
How do you make a variant to a roguelike?
Firstly, a variant is a roguelike game based on the source code of
another roguelike game, with some changes.
Making a variant isn't easy for several reasons. Most roguelike
sources
I've looked at are VERY badly written; lots of poor programming
techniques, hacks (more than 1600 in Angband), lack of comments,
difficult to understand variable and function names, and so on.
However, making a variant is much easier than starting from the
beginning by yourself.
Firstly, make sure that it is allowed for the particular roguelike you
are interested in, and that you aren't breaking any law by making this
variant. You will most likely need to change the name of the game, to
comment every source file you change with something like "Changed by
on
", and log the changes you make to the history file.
Secondly, play the game A LOT. Decide what exactly you would like to
change. Make a list of things to change. Then obtain a copy of the
source code, and see which compilers will compile it. Get one of
those.
Compile the game without changing anything. If it doesn't compile, get
it to compile before changing anything.
Then go throught the source files. Find the section you want to
change.
Make small changes first, then recompile and see what happens. Then
make progressively bigger changes until you have what you wanted.
Variants usually never reach the fame and glory of the original game,
but they are a good way to learn about how roguelikes work, and making
them is usually easier and faster than starting from the beginning.
DESIGN ISSUES
Do you have to design a roguelike game before you program it?
Typically, roguelikes are written without much design or planning.
Once
the programming is complete, you decide what you can do with your
program (eg. what items/monsters/spells you can support) and go ahead
and make those. Some people believe this is still the way to do
things.
Others believe differently. If you ever do a course in computer
programming at school, college or university, the first thing they
teach you is how to make an algorithm, how to plan your program, and
how to design in before you start programming. For some kinds of
commercial games, the designers make a 300 page design brief before
the
artists or the programmers even start work! Games that rely
intensively
on story usually have a complete play script written before the design
brief. Of course, most roguelikes are free, and nowhere near this
amount of work is invested in them, so this amount of design is
ridiculous. But note that most roguelikes in development have a design
document on their web pages.
I believe that planning is essential to any program, particularly a
big
one like a roguelike game. Before you start programming (at least,
programming anything big or particular), make a list of things you
want
in the game. What kinds of items do you want? Spells? Monsters? How
will your game world look? You don't have to plan the particulars like
the colour of your orcs or the exact number of your spells; just look
at general categories (eg. "some of my monsters will use spells on the
player", "there will be plants growing in the wilderness that you can
eat" and so on), and then decide how you are going to implement those
things.
Why do many roguelikes later undergo a major rewrite?
* Poor design. If you planned enough from the beginning, you would
cater for everything, or at least most of the things, that you want to
implement. Then you might only need a small rewrite.
* Change of maintainer. Most popular roguelikes go through long
chains of maintainers and dev teams. As soon as one guy gets the
source
code, the first thing he does is rewrite it so that it fits his ideas.
* Poor programming techniques. I would say most of the rewrites
are
there to fix bugs. Some programming languages are better structured
and
better suited for use for long programs like roguelikes. It has been
shown that when your code exceeds 100000 lines, the cost of
maintaining
it and debugging it exceeds the cost of programming new things. Object
orientated programming, functions and splitting up into files help to
reduce this problem.
What needs to be planned in advance?
* The story, theme and setting. These determines practically
everything.
* The world. How it will look. How big it will be.
* The terrain (eg. town, wilderness, dungeons, special places...)
* The items. Major categories (eg. weapons, armour, potions,
scrolls, food...). Leave detail (eg. how much the minor healing potion
heals you by) for later. Think about how the items will be used and by
who. Plan the basic rules (eg. you can only wield 2 weapons if you are
a fighter, you need space for arrows if you equip a bow).
* The magic system. Spell types. Who uses spells and when. How you
learn spells. What they cost. Which classes can use them. How to
implement permanent spells (eg. enchantments that last, like
recharging
a staff).
* The systems. Battle system. Shopping system. Interaction with
NPC's and monsters (maybe negotiating your way out of battles?). Level
loading system. How to finish the game and what happens when you do.
What do people like about roguelikes?
Replayability. If the game is random enough, it is always fun to play
and replay, because every time it is like a different game.
Freedom. There is a lot of it. You can kill just about anything. There
is a lot of actions you can take. Many strategies.
Complexity. There is a lot of items, skills, classes, areas, spells.
Difficulty. While this can be off-putting, it gives you a tremendous
sense of achievement to finish a roguelike or even to get far. You
always have to be careful - it is easy to die, and all that playing
time was for nothing.
How do you make people like your roguelike? Make it easy to get into
and play; no reading through 50 page files to learn how to play. Keep
the controls simple. The gameplay must be good. This generally
distinguishes roguelikes from similar games - the emphasis is on the
gameplay. Once your character dies, that's it - no coming back to life
(or maybe you are reincarnated back without items and with reduced
skills). This makes the game exciting when you are in danger. Keep it
balanced. If it gets too difficult, people are discouraged. If it is
too easy, there isn't much fun in it. Make a big world, with plenty of
items and monsters so it is interesting to explore. Make an
interesting
story. And, most of all, don't make it like some or other roguelike
that already exists. Use fresh, new ideas. Make it original and
different.
How do you finish making your roguelike?
Basically, have a plan. Decide in which order to program it, and stick
to the plan as much as possible. Keep it fun for yourself. If you get
bored, work on another aspect. If you are bored on programming, work
on
the story, or on the graphics (if you use them). Take a break. It
should be fun. If it isn't, ask yourself why, and do something about
it. If you are stuck, get other people to help you.
OUTPUT AND REPRESENTATION
Do roguelikes have to be done in ASCII text?
That depends. Utumno is an Angband variant (according to the Angband
variants FAQ, and I doubt the writers of it don't know what a
roguelike
is), and when people want to argue that things with graphics can't be
roguelike, I always quote it as an example of a roguelike with
graphics. Now compare Utumno and Diablo or Diablo 2. You will notice
they are not that different (graphically).
So NO, roguelikes don't have to have to be in ASCII text. Why are 100%
of them done that way (at least partly)?
* Text is very portable.
* It's traditional. Most people programmiing roguelikes come from
a
tradition of playing other roguelikes, and they are done the same way.
* It's fast. A museum style computer can probably show text at the
same speed as the latest one.
* It's quick and easy to make. You don't have to have lots of
artist friends to draw for you. You don't have to spend hours
modelling.
How do you add graphics?
There is several different graphical systems you might consider.
The simplest and most often used method is with square tiles.
Basically, instead of filling rows and columns of the screen with
text,
they are filled with small bitmap pictures. No animation is used, ie.
when you hit a monster, you don't see a swinging sword. You can make
an
animation system, but it will get difficult. To properly animate a
character, you need pictures of every single action from at least 4
different position (facing front, back, right and left) and the sizes
of your picture / animation files get big very quickly. To produce
smooth animations, you need even more pictures... It is obvious why
Angband and Nethack use only front facing pictures with no animation.
The other method uses isometric tiles. These are like square tiles
rotated 45 degrees, like they are seen from above and to the side.
Just
look at Utumno or Diablo to see what I mean. They are harder to
program
and to make, but they look better. Here you run into an even bigger
problem if you want to implement animation - you really need 8
different direction (up, up-right, right, down-right, down, down-left,
left and up-left) to face in, and you need every frame of every action
in each of those directions. Nevertheless, Utumno, Falcon's eye and
Diablo all use this.
Then there is 3D graphics...
How do you make a 3D roguelike?
There is only one game so far that uses this: Egoboo
(http://egoboo.sourcefourge.net). Even Diablo and Diablo 2, although
they look 3D, are really only 2D. All the monsters and characters for
Diablo 2 were modelled in a 3D package, and snapshots were taken in
different positions and at different times to create the animations.
So
good luck making one of the world's only 3D roguelikes.
But here is some ideas. A good cross-platform 3D library is OpenGL.
You
generally program it in C or C++. It is easy to learn, but requires
hardware 3D acceleration for good performance. Good free modelling /
animation software is difficult to come by. Try Blender and Anim8or.
In a way, designing monsters / characters in 3D is easier than in 2D,
because you don't need to draw actions from all directions; only from
one, then you can rotate them by any angle you like. Also, you don't
need to draw every frame of an animation, just the keyframes, and your
software calculates the rest.
However, the mathematics of 3D is difficult, and includes linear
algebra, vectors, matrices, quarternions, geometry and trigonometry.
Which libraries let you position the cursor and change text colours?
Most programming languages come with a library of their own. In C and
C++, you can use conio.h. This is DOS specific, however, and not
portable to other systems. The "curses" libraries are a better choice.
For a windowed system, it gets a whole lot more complicated...
STORY AND SETTING
Which stories are possible for a roguelike?
Moria and Angband are (loosely) based on J.R.R. Tolkien's "Lord of the
rings", but the except for a few characters, items and monster types
taken from Tolkien's work, they implement very little story. Hethack
hardly has any story (except for a one-liner you get at the beginning,
like "You are looking for the Amulet of Yendor, a legendary artifact
which grants immortality to the wearer").
In general, role playing games are the ones where story is important.
For a roguelike, it is nice to have a story, and a good one will keep
your player interested and provide more to the game, but it isn't the
game's biggest component.
Good ideas are:
* You are trapped in a virtual reality woorld, where the computer
has gone mad, and is making monsters, which can kill you. The goal is
to stay alive and find a way out.
* You are in a post-apocalyptic future (nno guns; or very few of
them with limited ammunition). There is a war between humans and
robots. You are on the losing side...
What themes and settings are possible for a roguelike?
Ones that involve killing a great number of enemies.
Most roguelikes are set in the middle ages. There are ones in a
science
fiction setting in the future, but they aren't very popular.
Relatively unexplored themes are:
* The Wild West
* The Far East
* The distant past (stone ages)
* Alternative histories (eg. Atlantis)
* The modern era
* Science fiction settings
What is / how do I make a good atmosphere?
Atmosphere, (noun): the psychological environment, the feeling and
tone
created by something. The atmosphere in roguelikes varies. In Angband
it is often dark and desparate - you're kilometres under the earth
with
a failing source of light, near death and with no way to escape your
foes... In Nethack, it is quite challenging but somewhat humorous. The
Diablo's are very dark and ominous - your cause is basically hopeless.
The best way to create an atmosphere is suitable music. Of course, I
have yet to hear of a roguelike with music :-) (see DoomRL) (besides,
music is difficult to port) so that's not an option. If your roguelike
has graphics, use them. The story also goes a long way towards
creating
an atmosphere.
What are quests and how are they diffrent from other forms of plot?
A quest is a set of actions you have to do in order for something to
happen. For instance, once you've completed the quest "kill Morgoth",
you've finished Angband. Quests have some sort of reward, or story
element with them.
What are the standard types of quests?
* Assassination quests:
o "Kill X"
o "Capture X alive"
* Searching quests:
o "Find X"
o "Get to X"
o "Gather X of gold"
* Competition quests:
o Do any of the above queasts, but before your adversary
(eg.
get to a town before your adversary)
* Story quests:
o "Talk to X"
* Any of the above, but they do something special (eg. there is a
story associated with finding a special item)
How do I make good quests?
Make them relevant and provide a good reason to do them. Integrate
them
with the story. Give good rewards. Avoid repetition.
Example: avoid things like "kill 5 orcs". Why? Maybe it is relevant if
you are in the assassin's guild, but if you're not? On the other hand,
if the orcs robbed you and took 500 gold, it is far more relevant and
you want
How do I make a good quest randomizer?
No idea. Someone help?
DUNGEON MECHANICS
How are dungeons represented?
This is a question worthy of a long article or maybe even a small
book.
Nevertheless, you can get the basics from this FAQ.
This FAQ only discusses traditional systems, ie. simple 2D tile-based
dungeons. If you're making something different (eg. a 3D roguelike)
you
can still use this, though.
Firstly, dungeons are made of rows and columns of tiles. If you plan
to
have variable sized dungeons, use dynamic arrays instead of the usual
static kind.
The tiles store:
* The type of tile (eg. wall, grass, flooor, river)
* The properties of the tile (Can you wallk through it? Is it
illuminated? Has it been explored by the player?)
* A list of items on the tile
* The monster on the tile
* Any other data (eg. a trap, a hole in tthe floor, stairs)
You should keep your tiles as small as possible. Angband has around 16
bytes per tile. Don't go much further than that; you'll see why in a
moment.
How does this work?
The type of tile is a small variable (1 byte or less) that determines
what the tile is. The type determines what is drawn - if you are on a
river, you draw a blue letter or graphic. A fast way to do this is to
store an array of the letter / colours / graphics of all the types,
and
just substitute the type into this array to determine what to draw.
The properties should be set per-bit; use bit fields or bit flags. How
are properties used? Initially set the "explored" flag of all tiles to
false, then when the tile is explored, set it to true. Only explored
tiles are drawn. If the tile can be walked through (ie. it is not a
wall or something), set the "passable" flag to true. When the player
tries to walk somewhere, check the tile in that direction. If it is
not
"passable", don't allow the player to move there. This allows you to
make illusionary walls if you want - ie. walls which aren't really
there and you can walk through them. This should be 1 byte or less.
For the list of items, use a linked list. This allows many items to
exist on the same tile. Store a pointer to the beginning of the list.
The pointer takes up 4 bytes of memory.
For the monsters, it depends. If you have more than one monster per
tile, you also need a linked list. Otherwise, just keep a pointer to
the monster, or some way to quickly find the monster occupying the
tile. This is vital in combat. A pointer takes up 4 bytes of memory.
What other data is needed? I would use another 1 byte to determine any
special dungeon features the tile carries, such as traps, stairs,
glyphs, chests and so on. Store all of these in an array, and
substitute this value into the array to find what, if anything, is at
the tile. If something is, take further actions...
So altogether, my system here uses 11 bytes. If I decided to make a
dungeon that is 100 by 100 tiles big, I would need 100*100*11 = 110000
bytes of memory. This increase is quadratic as width and height
increase, so be careful that you don't run out of memory. If you need
to squeeze your tile size down further, use bit fields. They let you
use less than 1 byte of memory for a variable.
How are dungeons generated?
In most games, levels or stages are designed and hard coded in
advance.
In a roguelike, you want as much randomness and variety as possible
(you also want to make walkthroughs impossible to create :-), so you
need to generate the dungeon randomly during gameplay.
There is many algorithms that will generate a dungeon. What they all
basically do is fill a dungeon with rooms and passages, then add
dungeon features like stairs, traps, doors and so on, then fill the
dungeon with items and populate it with monsters.
This all sounds very simple, but if you've tried to program it you
will
know it is not.
The first thing you have to decide if you are going to recreate each
level every time you visit it, or if you are going to store a level
once it is generated and use it afterwords until the end of the game.
The latter system is more realistic, but the former ensures you never
run out of variety. Angband uses the former system. Nethack uses the
latter. The latter system will be described in question 7.4.
How do you fill a dungeon with rooms and passages? There is all kinds
of algorithms to do it. You can just start with a solid dungeon, then
randomly "dig out" rectangles until you think it is enough. Of course,
the results will be disappointing. You don't only need to generate the
dungeon, you need to make it look good. The algorithm I just described
will make one huge hole in the middle of the stage with rough edges,
and some rooms which cannot be reached. Also, there is no limit to the
size of the room, and no overlapping with other rooms is checked.
The improved "digging rectangle" algorithm would then look like this:
1. Fill the dungeon with unpassable walls.
2. Pick a random number for the number of rooms.
3. Select a random location in the dungeon (x, y).
4. Randomly select the room length (RoomLength).
5. Randomly select the room height (RoomHeight).
6. If the area of this room (calculated by RoomLength*RoomHeight)
is
greater than the maximum area for a room, go back to step 4.
7. If the room cannot fit in the dungeon, or overlaps with other
rooms, go back to step 3.
8. Fill the rectangle given by (x, y) and (x + RoomLength, y +
RoomHeight) with empty space.
9. Go back to step 3 until all the rooms are created.
10. Randomly select walls in 2 randomly selected rooms or passages.
11. A pathfinding algorithm traces a path (passage) from one wall to
the other. If no path exists, go back to step 10.
12. Repeat from step 10 until every room is reachable.
This still has several errors. For instance, you might come into a
situation where no further rooms can be added to your dungeon, and
your
dungeon generation procedure would go into an infinite loop. But the
biggest problem is the speed - it can be very slow. While the dungeons
it makes look good, they aren't very realistic - it isn't how anybody
digs a dungeon. The pathfinding algorithm used to trace passages is
slow and difficult to program. The biggest imperfection is that you
don't know whether a room is reachable. There are ways (discussed
later) to tell whether a room is reachable from elsewhere in the
dungeon, but some algorithms always make rooms that are linked to the
rest of the dungeon anyway, and this simplifies the whole thing.
How do they do it? Before a room is created, another room is randomly
selected. A passage is drawn from that room, and then the room to
create is added at the end of that passage. Mike Anderson's "Dungeon
building algorithm" at the Roguelike News sites describes it quite
well, the following is just a summary.
1. Fill the dungeon with solid walls.
2. Make a room in the dungeon.
3. Randomly select a room (or passage) wall in the dungeon.
4. Decide on whether to build a passage or a room.
5. Check there is enough space to make the passage or room. If
rooms
are in the way, reduce the passage/room length so that it joins the
room(s). If the passage/room runs out the dungeon, go back to step 3.
6. Draw the passage/room (by filling it with empty space).
7. Go back to step 3 until enough rooms/passages are drawn.
Passages that zig-zag or twist can simply be handled by selecting a
wall at end of the passage when you reach the end of step 6, and going
to step 5 and building a passage from that wall.
Good looking dungeons can also be made with a fractal algorithm. The
fractal algorithm will produce any kind of pattern - for landscapes,
forests, rivers, islands, coastlines or whatever else you plan to use.
I don't recommend using fractals for dungeon generation, as they can
make rooms that are unreachable from somewhere in the dungeon. But
have
a look at question 7.5 if you are interested.
How do you make dungeons with a theme?
How do you make sure all your rooms and passages are reachable?
Some algorithms always generate rooms and passages that are reachable
from every other room and passage. If yours does not, you need a way
to
check this specifically. This is one.
The flood-fill algorithm is probably the best way to do it. It
involves
recursively calling a procedure that fills all empty tiles until it
encounters a boundary (like a wall). When the flood-fill is complete,
just check all the rooms for having a tile which is filled. Those that
do not not are unreachable from the tile where you started the
flood-fill (as well as from the rooms which are filled).
An example (C) is:
void FloodFill(int x, int y)
{
if ((Dungeon[x][y].Content == FLOOR) && (Dungeon[x][y].Flags != 1))
Dungeon[x][y].Flags = 1;
else
return;
FloodFill(x+1, y);
FloodFill(x-1, y);
FloodFill(x, y+1);
FloodFill(x, y-1);
}
bool AreAllRoomsFilled(void)
{
for (int Count1 = 0; Count1 < DungeonWidth; Count1++)
for (int Count2 = 0; Count2 < DungeonHeight, Count2++)
if ((Dungeon[Count1][Count2].Content == FLOOR) &&
(Dungeon[Count1][Count2].Flags != 1))
return false;
return true;
}
Note that in some cases you might *want* a secret room or passage
which
is cut off from the rest of the dungeon, and to which you can only get
through a special spell or complicated digging. If so, make provisions
for it.
How do you make a town?
How do you make wilderness?
Fractals.
How do you make persistant dungeons / worlds?
A persistant dungeon, as mentioned earlier, is a dungeon that doesn't
change. In Angband, every time you visit level 1 it will look
completely different, which is unrealistic. In Nethack, the levels are
stored, so level 1 always looks the same. That is persistance.
Obviously you have to save the levels to disk to ensure they don't
change. But is it realistic for levels never to change at all? Sure,
the walls should keep the same shape and the dungeon features should
be
in the same place, but should an item be where you left it months ago?
Should all monsters "freeze up" and stay in exactly the same place,
ready to do exactly what they were doing when you last visited that
level? Should spells that affect the dungeon, eg. "destroy trap",
still
be in effect when you re-enter a level? You need to think carefully
about what should be stored, and what should not.
To save a dungeon, all you do is create a file and then write to it,
in
order, everything that needs to be written to file. To load it, just
read everything back from the file in the same order that it was
written.
Of course, it isn't as straightforward as that. When you don't know
how
many structures (eg. items, monsters) will be written to the file, you
should count them, then write the count before you write those
structures. That way, when you read from the file, you just read the
count, and so you know exactly how many structures you need to read
from the file.
Pointers are another problem. When you read a structure containing
pointers from file, you have to reassign new memory addresses to those
pointers. In most computers, a program can be loaded into memory
starting at any address, and so the memory addresses contained by your
pointers will be wrong if your program is loaded at some other
address.
In fact, try to avoid writing any pointers to file - they waste disk
space, and do nothing useful. Instead, write a data structure to file
field by field instead of just writing it as a whole.
How do you store a really BIG world?
You might be encouraged to make a big world and make it "persistant"
(ie. the levels don't change every time you visit them), but this
takes
up a lot of disk space. For instance, if each tile in your game is 20
bytes, and your dungeon is 256 by 256 tiles, and you have 100
dungeons,
they will take up about 131 megabytes of disk space, items and
monsters
and other things excluded.
So how do you reduce the disk space taken up? Well, you can either
compress your level files, or you can change the way levels are stored
and generated.
Compressing your level files is pretty simple. There is many
compression methods, but I will discuss one that reduces your file
size
considerably while at the same time not taking too long to do it. It's
called RLE (Run Length Encoding), and it is used in many file types.
What it basically is, is replacing a repeating sequence of data, with
a
count and one sample of the that data. For instance, the string
"AAAAA"
would be stored as "5A".
So to RLE compress a structure, count the number of repetitions and
store it with whatever is repeated. Repeat until you've stored the
entire structure. To decompress an RLE compressed file, simply read in
the count, and set that many data structures to whatever comes after
the count. Repeat until you've loaded the entire structure.
This method works best on:
1. Large quantities
2. Similar data
In other words, small quantities of data with lots of variety will not
work well, and may even get bigger with RLE compression ("ABC" would
be
stored as "1A1B1C", which is double the size!).
Since most things in your roguelike should be stored as structures or
classes, it might seem like you should compress / store structures as
a
whole. But there is usually a lot more differences between structures
as a whole than there is between the fields those structures contain.
In this case, it is better to RLE compress and store the fields
separately. On the other hand, in some cases it is better to compress
whole structures. You have to try it out and see what works better.
If there is a lot of similar data, with very few exceptions, leave out
those exceptions and store them later with the location they should be
at. For instance, if the string was "-*-------", you could just store
"9- 2*", which means the string contains 9 minus signs, and the sign
at
the second position is a star. If you decide to use this, find some
way
to separate the exceptions from the rest of the data. In this case I
used a space. You could just assume that the exceptions will be read
in
when the string has been filled completely. Remember to count the
exception and write the count to the file before them so that you know
how many to expect.
One last tip. You can use a bit-packed array, with 1's where there is
unusual values, followed by those values, in order. If you want, you
can compress those values or even the bit-packed array, but remember
to
decompress them somewhere before you try to decipher them.
The best data type to store the count is a 1 byte variable, but that
can only store a maximum value of 255. So be careful that you don't go
over that, because it will just cycle back to 0 and you will have a
wrong count.
But while this method works well, there is an even better way to store
levels, which takes up far less space. Firstly, how do you generate a
level? You randomly select a number of things, like room and passage
location and size, directions your passages run in, locations of your
items and features and so on. Now the thing to remember is that there
is no such thing as a random number in a computer. The only way you
get
a truly random number is through a radioactive decay counter, and no
computer has one of those. Basically, what a computer does to get a
random number is take a "seed" value, and calculate a sequence of
numbers based on that seed. Given the same seed, a computer always
produces the exact same sequence of "random" numbers. So if you knew
the seed used to generate a dungeon level, and you reset the random
number generator with the same seed and then ran the dungeon
generation
procedure, you will get the *exact* same dungeon.
In C, if you include stdlib.h in your program, you get the srand()
procedure, which takes a number between 0 and 65535 (both included) to
use as a random number seed, and the rand() procedure which gets a
random number in the same range. If you need to select any seed, use a
timer function to get a value in this range. So the stdlib.h library
gives you 65536 unique "random" number sequences, which means you can
use it to create 65536 unique dungeon levels. If your game only uses
100, chances are, your player will never recognise two dungeon levels
being the same. Still, I would keep a list of seeds used to generate
each of the levels so far and make sure the seed I use to generate a
new level has not been used already. If you need a greater variety of
levels, find another random number library that gives you more
possibilities.
Now this really helps you reduce the size of your save file. The
random
number seed used by srand() can be stored in only 2 (!!!) bytes. If
you
decide to use this method, remember not to use random numbers seed for
your monsters and items (ie. reset the random number generator after
the dungeon layout is generated), because you don't want to have the
exact same monsters in exact same places every time you walk into the
level, and also to have the exactly same items in the exact same
places.
Why would you NOT want to use this method? Well, while every random
number seed has a unique sequence of numbers associated with it, the
reverse is not true. This method therefore assumes that the dungeon
layout hasn't changed, ie. that you haven't dug holes in the walls,
that you haven't destroyed any doors or changed any features. If you
have, the changes will be lost. You can, of course, save the changes
to
file with the random number seed, even compress the changes, but if a
lot of changes are made, the file size can exceed that of a normally
stored file.
There is a way to fix that too, of course. You can decide only to
store
a certain number of changes, and whatever changes occur after those,
undo the changes that occur furthest back in time. For instance, if
you
store 10 changes, when you make the 11th change, the first change is
undone (lost). One problem is that this can be exploited. For
instance,
if you dig though 10 walls, and you dig 1 wall further, the first wall
will reappear and trap you. You can probably use this to trap monsters
or do other things. This can be fixed by storing a lot of changes
(like
100 or more) so the player will probably never encounter this
situation. Even if you store 1000 changes, and each requires 20 bytes,
you will use up about 20 kilobytes at most, which is still far smaller
than 1.3 megabytes that you would have without any compression.
How do you deal with stuff happening far from the player?
That depends.
Monsters
Monsters on the same level as the player should be "processed" (ie.
decide whether to move, attack, pick up items or whatever) each turn.
You simply keep a list of all the monsters on the level, and every
turn
you go through the list and decide what should be done for each
monster.
Monsters on different levels usually do nothing. When the level is
loaded, you can decide to process the monsters say 50 times (without
them being able to sense the player, or they will kill him!) just to
make it realistic. This way, monsters will not end up in the same
place
and involved in the same actions they were in when the player last
visited that level. You could also keep the levels above and below the
level the player is on (as well as any other levels that can be
reached
through say teleport traps) in memory, and process the monsters on
those levels. This makes it more realistic: the longer the player is
not on a level, the greater the amount of changes made to that level
and the more the monsters change / disperse.
The exact monster processing will be discussed later.
What is LOS, and how and why do you do it?
LOS (Line Of Sight) is a way to determine what is visible to the
player
/ monster.
In most (all?) roguelikes, the dungeon starts in complete darkness.
When you walk around, you reveal some of it. But you only see monsters
that are illuminated by your light at a particular time. This
illumination area is usually circular (or octagonal -- Angband). Also,
the light scatters realistically - shadows form when there is
something
in the way, you can't see around corners, and so on. Another important
point is that some light sources cover more area than others - a
normal
torch covers a circle with radius 1, the Phial of Galadriel has radius
3 and so on.
How do you determine what is visible? For a monster, you simply pass
through the area and when something of interest is found, trace a line
back to the monster. If there are obstacles along this line, the
monster doesn't see it and so doesn't react. For a player, it gets
more
complicated.
The simplest and most inefficient algorithm traces out a circle of the
desired radius (using trigonometric functions - sine and cosine) and
draws rays of light from the player to the circumference. Initially
the
whole area is made dark, and when the rays are traced, everything up
to
and including an obstacle is illuminated, and everything after is
ignored (because some other ray could be illuminating it). The problem
is that you don't know how many points you have to evaluate to draw a
good circle (for a radius 10 light, you need hundreds), and using sine
and cosine is very slow.
Another way to do it is to draw a square on the dungeon tiles whose
width and height are double the light radius, and which is centred on
the player. Then trace rays of length radius from the player to each
tile which makes up the square, treating intersections with objects as
above.
Yet another method uses shadow casting.
How do you "trace rays"? Just draw a line, and pass along it.
Bresenham's line algorithm is very good - it can handle vertical
lines,
and it uses no multiplication or division - only fast integer addition
/ subtraction.
A good way to optimise these algorithms is to use the fact that a
circle is symmetrical about its horizontal and vertical diameter, as
well as the 45 degree and 135 degree diameter. So you only need to
evaluate (x;y) from 0 to 45 degrees, then trace rays to (x;y), (y;x),
(-x;y), (y;-x), (x;-y), (-y;x), (-x;-y) and (-y;-x). This makes the
algorithms about 8 times faster.
There is a problem with these algorithms, and that is that a corner
tile at the end of a passage is never lit (unless you stand right next
to it). It looks like this:
###
.@.#
###
when in roguelikes you usually see:
####
.@.#
####
Hacks can fix this pretty quickly. If the tiles next to the corner
tile
are all illuminated, illuminate the corner tile too.
How do you store the list of all the items in the game?
You should know what kinds of items you are going to have in the game.
You should also have your magic system well planned, and any other
systems involving items (battles, shopping, stealing) also well
planned.
Decide on the exact categories of items, and the similarities and
differences between them. Decide what each item category needs to
contain. For instance, while most items should be able to carry
enchanments, foods and potions should not (unless, of course, a potion
works the same way as a spell does). Your weapons and armor should
store info relevant to the battle system (like attack power, damage
type, defensive rating and so on), but scrolls should not. I think a
good way to represent all the different item categories is to use
object orientated programming, because that allows inheritance,
polymorphism and so on, which is very useful.
Now one way to store the item list is to just keep a huge list of all
the items in the game, in some kind of array, and to represent an
item,
you just store a number, which is the position of that item in this
array. While this system works well for some kinds of items where
there
is no difference between two items of the same kind, the problem
arises
when you want to store something individual about an item. For
instance, you might want items to carry an enchantment that makes them
do extra damage, or that heals you faster. You might want a damage
system, where as you use your items, they take damage, and when that
damage reaches zero, they fall apart and become unusable. In both
these
systems, the items have to carry individual enchantments and damage
ratings. So you can't store such items in the array, you would have to
store all the settings for each item with the item.
The best way to do it, then, is to split up your items into 2
categories. In the first category are items which carry no individual
properties. These are simply represented by a number which is
substituted into the item array to find out about them. In the second
category are items which have some individual properties. They are
represented by both a number which get substituted into the item
array,
and by the individual settings they carry.
Since you will most likely end up with different sizes for different
item types, you can't use 1 massive array for all the items. You will
most likely have to use an array for each item category. You store
these arrays in a file, and read them in from the file when the game
is
started.
How do you store the items in the player's inventory?
The previous question discusses how to generally store the items. One
more thing to remember is that if the player / monster is carrying
more
than one item that is the same (eg. 5 arrows), you should allow the
items to stack. So you need one more structure per item, and that is
the number (for the arrows, it would be 5). If you want to check total
inventory weight, remember to multiply each item's weight by its
number
to get the correct weight, otherwise you will just get the weight of 1
item.
But now how do you store all those items in the player's inventory?
You
can use:
1. A static array
2. A dynamic array
3. A linked list
A static array is simply array with a fixed number of elements. It is
easy to read and write to a file, because it is one continuous
structure and you always know how long it is. You only need to still
store the number of items in the array so that you know where the stop
reading the items back from file. It is also very easy to sort. The
disadvantage is that memory is always wasted. If the array has 50
elements, and you only carry 5 items, 45 elements worth of memory is
sitting there unused. Also, you can't carry more than 50 items, so you
constantly have to check this when buying / picking up / doing
anything
that adds items to the inventory.
A dynamic array is an array that can be of any size, because it is can
be created and destroyed at any point in your program (using "new" and
"delete" in C++, and "malloc()" and "free()" in C). When you create
it,
you specify the size. Unfortunately, you can't change the size of the
array when it is created. So when you decide to add or remove the item
from the inventory, you need to create another array with the right
number of elements, and then copy everything from the old array, and
delete the old array. This is slow. Sorting a dynamic array and
writing
it to file is just as simple as sorting a static one, though.
A linked list is a more advanced programming structure. It consists of
a bunch of "nodes" created dynamically (ie. whenever you like, not all
at a specific time like with arrays), and each one containing a
pointer
to the next one in the list (and sometimes the previous) and
containing
data (like your item info). The cool thing about linked lists is that
there can be as many as you like, they will never waste any memory,
and
adding and removing items is easy and quick. They can only be accessed
sequentially, ie. you have to go through them in order from beginning
to end. However, sorting linked lists, although harder to program, is
even faster than sorting arrays, because you don't need to swap the
actual data, only the pointers' memory addresses. Writing this to file
is slightly harder, as you have to do it item by item, you can't just
write the whole list at once, and you don't know how many items you've
got (unless you keep count). Linked lists can be used for a whole lot
of other things too. This is the recommended structure for those who
know about it and how to use it. If you don't, it's quite difficult,
learn pointers and dynamic memory allocation first.
How do you make randomly generated items?
* Decide what percentage of items in the game should be random
* Decide what categories of items should be randomly generated
* Decide what things should be random in each category
* Decide what the range for those random values should be
* At the start of a game, generate the raandom items and put them
in the big item array
Which kinds of monsters should I use in my roguelike?
It depends on the setting and story. Most roguelikes use monsters
taken
out of Tokien's work: orcs, trolls, wargs, hobbits, dwarves, elves,
dragons and so on. Traditional creatures taken out of various
mythologies and religions are also used: nagas, medusas, gorgons,
angels, demons and so on. Some are taken out of "Dungeons and
dragons",
such as the infamous kobold. Plenty of animals are used: from the
normal cave-dwelling creatures like bats and spiders, to the
ridiculous
lice and ants.
Make up your own if these are not enough.
How do you create a monster AI?
AI (artificial intelligence) is not so easy to create. There is
several
different techniques you might want to use.
State machines are probably the easiest way to do AI. Firstly, get a
piece of paper. Then write a set of states (eg. attacking, walking
somewhere, running away, stealing), circle those states, and draw
arrows (with directions) from each state to every state you can get to
from that state. These arrows are called transitions. Label each
transition with the circumstances under which it occurs. An example:
+-----------------+ +---------------+
| player runs away| | healthy again |
| v v |
+-- ATTACK APPROACH PLAYER RUN AWAY
| ^ | ^
| | close enough | |
| +-----------------+ likely to die |
+-------------------------------------------+
Of course, it would be a lot more complicated. There is far more
decisions to be made, and there is more actions (one for each item /
spell). Now how do you implement this? Instead of using the usual
massive nested "if" or "switch" statement, you make a 2 dimensional
array, with the number of states being its width and height. This is
the state transition table.
ATTACK APPROACH RUN
ATTACK Player runs away Likely to die
APPROACH Close enough
RUN Healthy again
You keep a variable with each monster that tells you which state it is
in. This tells you about the row of the state transition table. You
then go through that row, and run tests to see if the circumstances in
it are fulfilled. If they are, pick the one with the highest priority,
and switch to that state. For instance, you are in the "ATTACK" state.
Look in the left-most column for "ATTACK" (it's at the top). Right,
now
look along the row. Under the first column ("ATTACK") there is a blank
space, so there is nothing to check there. Under the "APPROACH" column
there is "Player runs away". Say that is true - the player is leaving.
Under the "RUN" column there is "Likely to die". Say that is also true
- the monster is badly hurt. The monster's life takes priority over
the
player's pursuit, so the state machine switches to the "RUN" state
(you
could of course make the monster's life less important :-). Behavior
is
then based on the states. This is also where big "if" statements can
come in. If you want to avoid them, use function pointers as well in
your state transition table, and make a function for each action /
state.
State machines are very good, and unlike a quick AI you make using
hacks, they stand up well to difficult situations and don't require a
lot of processing or calculation. They are used in many programming
situtations, so it is worthwhile to learn them.
Other techniques, like neural networks are described in question 8.x.
How do you create a good monster AI?
The previous question describes how you make an AI. This one will
discuss how to improve it and make it interesting.
Firstly, plan. Do you want some monsters to attack each other? Do you
want to make some co-operate with the player? Do you want group
tactics? Various strategies?
How do they find / follow the player?
Let's see. The player is always moving. The monster is always moving.
The other monsters are always moving. Doors are opening and closing,
new obstacles are coming around. This seemingly simple problem of "now
the monster follows the player" is actually a real challenge.
Different roguelikes have tried different things. In Angband, the
monsters sleep (do nothing) when they are created. When the player
comes around making noise, they wake up. This way, far away monsters
don't constantly have to look for the player. Also, monsters only move
to attack you if they see you (I think), and if you temporarily
disappear, they go to where they last saw you.
How do they move closer to you if they know where you are (ie. can see
you)? If their X value on the map is smaller than yours, they take a
step that increases their X value; if their X value is bigger than
yours, they take a step that decreases it, and if it is the same, they
don't take a step which changes the X value. The same thing happens
with the Y value. The combination of X and Y changes makes the
monsters
walk the best possible way (ie. diagonally or in a straight line,
depending on the situation). This, of couse, doesn't help when it
comes
to obstacles. How do you get around obstacles? Several ways will be
discussed here.
I am going to assume the monsters want to find you, and you are far
away. One way to do it is to tract you by scent. Every game turn, the
player deposits some scent on the tile he is standing on. The smell
spreads (by somehow averaging the scent value of a tile with all the
surrounding tiles) and fades (a small value is subtracted from each
tile's scent value every turn). When a monster picks up a scent, it
finds the tile around it with the highest scent value, and goes there.
If you don't put scent on tiles with obstacles, monsters will never
find obstacles blocking their way to the player, because obstacles
have
a scent of zero. The problem with this method is that it is pretty
slow. Averaging involves division, which is (together with
multiplication) the slowest simple arithmetic operation a computer can
do. But if you optimise it somehow, it could work well. If you make
some monsters more sensitive to smell than others, it could work very
well, and it prevents all the monsters in the stage from coming after
you at the same time :-). Monsters should track by sight (described in
the previous paragraph) when they finally see you.
Tracking by sound also works. For each action that makes a sound,
calculate the amount of sound, and spread it like you would smell
(except for that sound has no duration, so it only lasts for 1 turn
and
then disappears). Monsters go in the direction of the tiles with the
highest amount of sound. Maybe every time they hear sound, they start
listening better for new sounds, and becoming more aware of smells?
What is nice about sound and smell is how you magic and items which
change them bring in all kinds of new strategies (eg. an invisibility
spell isn't enough any more, because some monsters can sniff you out
and attack anyway).
The proper way to do pathfinding is through a pathfinding algorithm
like A* or Djkstra. These will find the shortest path (if any) between
two points on the map. You might want to use these for some special
monsters that know the location of the player (through magic or
something). The problem with pathfinding is that it is generally slow,
and it is difficult to learn and program (unless you know a lot of
Graph Theory). Also, since the player is moving, and monsters are
moving, and new obstacles are coming around, you would have to trace a
path every couple of turns to make sure it is still possible (no new
obstacles). This is very computationally expensive, so like I said, it
isn't good to use for every single monster, only for some. It can also
be used for moving the player; in some games (a.k.a. Diablo/2), you
click with the mouse where you want the player to go, and he walks
there using the shortest path and avoiding obstacles and everything
else in the way.
A quick algorithm and explanation of pathfinding (since I couldn't
find
any and had to learn the hard way): This is something like Djkstra's
algorithm. What happens is there is 2 lists: OPEN and CLOSED. The OPEN
list stores a list of tiles which are possible candidates for a
shortest path, and the CLOSED list stores the tiles we've been
through,
so they aren't unnecessarily repeated. The "movement cost" is the
number of steps the monster has to take to get to that tile, walking
on
the path associated with that tile. New tiles are only added to the
OPEN list if they don't exist, and tiles only replace other tiles if
they have shorter paths. Anyway, the algorithm is:
1. Find the destination tile (where the player is).
2. Put the starting tile (where the monster is) on the OPEN list.
It's starting cost is zero.
3. While the OPEN list is not empty, and a path isn't found:
1. Get the tile from the OPEN list with the lowest movement
cost. Let's call it the CURRENT tile.
2. If this is the destination tile, the path has been found.
Exit the loop now.
3. Find the tiles to which you can immediately walk to from
this tile. These would the the tiles around this tile, which don't
contain obstacles. Call these tiles "successors".
4. For each successor:
1. Set the successor's parent to the CURRENT tile.
2. Set the successor's movement cost to the parent's
movement cost, plus 1 (for diagonal movements, add more if it takes
longer to go diagonally in your game).
3. If the successor doesn't exists on either the OPEN
list or the CLOSED list, add it to the OPEN list. Otherwise, if the
successor's movement cost is lower than the movement cost of the same
tile on one of the lists, delete the occurences of the successor from
the lists add the successor to the OPEN list Otherwise, if the
successor's movement cost is higher than that of the same tile on one
of the lists, get rid of the successor
5. Delete the CURRENT tile from the OPEN list, and put it on
the CLOSED list.
4. If the while loop has been ended because the OPEN list is empty,
there is no path.
5. If this is not the case, the last tile pulled from the OPEN
list,
and its parents, describe the shortest path (in reverse order - ie.
from the player to the monster - you should read the list of tiles
back
to front).
How do you add variety to your monsters?
A big problem with monsters in roguelikes is that they are just too
predictable. You know one hit with a sword will kill every mouse, one
arrow will kill every yeek, and it takes a lot from both weapons and
spells to kill a dragon. Even though there is often lots of monsters,
once you've seen each one, that's it, you've seen it all.
A number of different techniques therefore exist to make monsters more
unique and add more variety to them. Making monsters carry items is
one
of them. So is a good monster AI. There is several more. Here I will
discuss genetics and neural networks.
In real life, animals and people carry genes, which adds a lot of
differences between them. Some are faster, some are smarter, some are
healthier and so on. What happens over a period of time is that the
fittest survive and the rest die out. So when your player walks into
the dungeon and starts killing monsters, he will find they are not all
the same, and they get stronger over time, because as the weaker die,
the stronger live on to reproduce and have stronger children. How do
you make monster genetics? Decide what the "genes" should be. Maybe
extra health points. Resistances to various elements and spells.
Stronger attack and defence. Intelligence and eventually the ability
to
use magic? Then decide what each gene does. For instance, each health
gene affects health points by 5%. For each good health gene, the
health
points go up 5%, and with a bad health gene, they go down 5%. So if
you
gave an orc 4 health genes, and they all turned out "good", the orc
would have 120% of its normal health points. If they all turned out
"bad", he would only have 80%.
Now, using genetic algorithms, when you create a monster, randomly
select 2 parents. Somehow combine the parent's genes (usually using
random selection and averaging). If there isn't enough parents,
randomly create genes. How does this help? Well, the orcs with 80% hit
points will get killed more by the player, and so fewer will survive
to
have sickly children. The children will thus become healthier, because
only healthy parents have survived to reproduce. As they grow
healthier, they are more of challenge for the player.
Neural nets are a way for a computer to learn. They are a difficult
and
complicated topic, which is why they are rarely used in any games, but
simple ones should be manageable with a little research. What
basically
happens is that a neural net takes a number of inputs, and produces a
number of outputs. Unlike a program which you make, however, a neural
net learns from experience and corrects its mistakes, so a good one
should make a really challenging opponent.
The inputs to a monster neural net could be:
* Current state of health (hit point perccentage)
* Current opponent's state of health (proobably also a percentage)
* Distance from opponent
* Damage done by previous attack
The outputs:
* Movement towards the opponent
* Movement away from the opponent (runninng away :-)
* Some or other attack
* A spell
You train the net by comparing the damage done to the opponent, with
the damage received from the opponent. With a little practise, the
neural net would learn to run when it is near dead, to go closer to
the
opponent when it is far, to use attacks which do the most damage and
so
on. One thing to remember, is that if you plan to have neural nets for
each creature, don't destroy the net when the creature dies. Then all
the learning is lost. Rather use a net for all kinds of that creature
(eg. a neural net for all orcs).
How do you make your battle system?
The heart of any roguelike is the battle system. What makes most
roguelikes fun, is killing thousands of monsters. The better the
battles, the better the game. So a good battle system is not only nice
to have, it is essential.
Planning a battle system, however, is no easy job. Every single spell,
every usable item, every monster type, and many many other things, can
completely change the way battle works. For instance, say you have
this
spell called "haste" that makes the player take one extra action per
turn. That's easy: one "if" statement checks if haste is active, and
if
so, the player takes another action. But now say you decide to change
the haste spell so monsters can use it too. Now things can really
complicated when you have multiple monsters and the player with
"haste". Your entire battle system might have to change. So the point
is, while you should have some idea of how a battle goes from the
beginning, you should only program the battle system when the item,
magic and monster lists are complete.
Basically, combat works like this. Everybody gets a certain number of
turns, they do what they think will inflict the most damage on their
opponent while minimising their own damage taken. Damage is inflicted
with weapons, and it is reduced (or blocked entirely) with armour.
The point of combat is very simple. Kill as many opponents as possible
while staying alive yourself. When do you die? Every roguelike (and
most other games) I've seen use a "hit point" (or "health point")
rating, abbreviated HP. You have a certain amount of HP, and a
maximum.
The maximum grows when you reach the next level, and the current HP
grows when you rest/drink healing potions/use healing spells and so
on.
When your current HP is maxed out, you are completely healthy. When it
drops to 0, you die. Damage reduces it by the amount of damage taken,
and healing increases it by the amount of health points gained. How do
you calculate this? Instead of the slow and problematic way of
checking
overflows like roguelikes usually do it, do this: When a hit occurs:
If
the damage is greater than or equal to the current HP, the HP drops to
zero and you die. Otherwise subtract the damage from the current HP.
When you are healed: If the health gained is greater than the
difference between your maximum and your current HP, your current HP
takes on the value of the maximum HP. Otherwise, you add the health
gained to the current HP.
When you process you monsters, the monster AI decides what action to
take.
How do you represent, store and process monsters?
This is a good question, but I don't think very many articles have
been
written on this.
Firstly, to represent the monster, you need to take everything into
consideration (which is why this is the last article about monsters).
Does each monster have a name, or do only some? How do you deal with
different AI's? How do you store and use spells? How does your monster
carry items? And can all monsters do all of these things? If not, how
do you know and what do you do about it? Planning (at least each kind
of monster), object orientated proramming and good structures should
do
the job for a large variety system such as this. For the items section
in this FAQ, a system was discussed where items were split into 2
categories: properties unique to each item, and properties which are
the same throughout the same item (eg. two ordinary swords will do the
same damage, but one might have a spell acting on it that the other
does not). This system works well for monsters too - all orcs have so
many maximum hit points, but each one can have different current hit
points (because they have been hurt). So splitting up monsters this
way
can be a good idea.
Most monsters are stored in some kind of data (or text) file. They are
read in when you play the game. Inside the game, monsters will change
often - the player will kill them, they might multiply, more will be
created, reading a scroll of monster summoning will call up more and
so
on. So you must make considerations for this from the start. A linked
list is very good for storing the monsters inside the game; arrays are
going to run into size problems very quickly. If you are programming
using object orientated programming, linked lists can store any object
derived from a base class, and the right virtual method will still be
activated for each monster. Adding new monsters to a linked list is a
piece of cake, removing dead ones is just as easy. So linked lists are
the storage system of choice.
How do you process monsters? Just pass through the linked list and run
some or other function or method for each monster in it.
Alternatively,
since each map tile points to a monster (if any is standing on it), go
through each map tile and process the monster on it.
One problem that could occur is that you get dangling pointers: each
spell/person/monster/item attacking/working on/flying towards the
current monster points to the monster. When the monster dies, you
delete the monster from the list, and those pointers point to who
knows
where. Unpredictable things could happen. Use "reference
counting" (see
www.memorymanagement.org). Basically, each monster keeps a count of
its
"users", initially set to zero. When something new points to the
monster, increment the monster's user count by 1. Each turn, those
items/spells/whatevers pointing to the monster must check if the
monster is dead (marked somehow on the monster without removing it
from
memory), and if so, stop pointing to the monster, and decrease the
monster's user count by 1. Only when the monster's user count is zero,
can it be safely deleted from the list and removed from memory.
Another problem you might run into is how to deal with monsters which
have different speeds. A monster that takes 3 actions per turn can
either make all 3 when it is processed, or you can use the more
realistic (and difficult) system where those turns are spread out
among
everyone else's turns. For this, you might want to keep a separate
list
for monsters of different speeds, and pass through the linked lists
with different speeds more than once, taking only one action each
time.
Then there are the "haste" and "slow" types of spells that change the
number of actions you normally take...
SPELLS
How do you represent a magic system?
You plan it very well in advance first. Don't make magic a black box
device - explain it somehow, and integrate it into your story. Decide
on the magic system, categories of spells, all of that.
What is a good magic system to use?
Your own. I would not copy from "Dungeons and dragons", other
roguelikes, other games, New Age books, Internet websites on magic and
paganism, and whatever other sources you might think are good. Maybe
get ideas from them, but don't copy spell names or statistics.
Traditionally, most roguelikes work magic similarly to "Dungeons and
Dragons", with a few exceptions. Each spell has a level. You have to
be
on the same or higher level (experience wise) to learn it, and you
have
to be a class that can learn spells, and have the appropriate spell
book. You have a certain amount of magic points. They increase when
you
level up. Each spell uses some magic points, and when you run out, you
can't cast spells. Magic points are restored by resting and with some
potions.
How do you enchant objects or make "enchanted" objects?
With great difficulty.
How do you make random spells?
Similarly to random items.
Can you make any money from your roguelike game?
Of course you can. Look at "Dungeon Hack" or "Diablo" for example.
Realtime combat and nice looking graphics are heavily recommend if you
want to reach out for a broader (paying) audience, though. But all the
major roguelikes are free of charge, and all except Adom also permit
free distribution and modification of the source code - something that
is probably necessary unless you plan to write your game by yourself
List of contributors:
* David Damarell (Nethack description, question about money from
roguelikes)
* Bridget (list of newsgroups)
* Jens Baader (list of roguelike games and newsgroups)
* Philip Swartzleonard (who makes roguelikes)
* Kornel Kisielewicz (wikified)
zai...@zaimoni.com
First, thanks -- this needed a fairly major update.
> What are the major roguelike games today?
>
> ....
>
> Angband
>
> Website:http://www.thangorodrim.org/
Website:http://www.rephial.org/ is more current; it actually
distributes versions after V3.0.5 .
Pfhoenix
specifically. Reference websites that have code available. You simply
can't properly avoid going in-depth into algorithms if you start
talking about what you consider the most popular ones are.
Also, as a general rule-of-thumb for writing, the FAQ answers should
always be from an impartial third-person perspective. This means no
"I" or "we" statements.
- Pfhoenix
http://adeo.pfhoenix.com
Ido Yehieli
> distributes versions after V3.0.5 .
> Also, as a general rule-of-thumb for writing, the FAQ answers should
> always be from an impartial third-person perspective. This means no
> "I" or "we" statements.
Thanks for the input, you can edit the FAQ at:
http://roguebasin.roguelikedevelopment.org/index.php?title=Roguelike_Dev_FAQ
-Ido.
Krice
> Thanks for the input, you can edit the FAQ at:
I wrote a new section for items. This is jus a suggestion which
probably will never be used:)
ITEMS
How do you store the list of all the items in the game?
Use a linked list. The list may be owned by a terrain tile, a
container
or the current level. The last option is usually slower, because there
are more items in one big list. In addition to level list or terrain
lists
you will usually have container lists associated to a container item
or monster inventory.
How do you store the items in the player's inventory?
Use a linked list to store items in the inventory. Don't try to re-
invent
the wheel, use existing implementations found in your programming
language such as std::list in C++.
How do you make randomly generated items?
Decide what items are made randomly by giving them data such as
how rarely and where they are made and possible other conditions.
Items may be created according to level and room themes, and/or
randomly scattered in the level. The level properties like size should
also affect the random item generation.
Ido Yehieli
Isn't there already a section describing just that?
http://roguebasin.roguelikedevelopment.org/index.php?title=Roguelike_Dev_FAQ#How_do_you_store_the_list_of_all_the_items_in_the_game.3F
-Ido.
Pfhoenix
asked on r.g.r.d? Is it to provide people looking to start writing a
roguelike initial direction on libraries and algorithms? I definitely
think the former should be the primary purpose and not the latter. It
is outside the bounds of a FAQ to talk about algorithms in any truly
beneficial way (analysis of algorithms, their efficiency, comparing
and contrasting them based on characteristics and performance, etc).
Talking about libraries shouldn't involve personal bias (I don't like
SDL, for example, even though a lot of people use it), but should
instead simply be informative and provide external links to sites that
are dedicated to more in-depth information.
- Pfhoenix
http://adeo.pfhoenix.com
Ido Yehieli
> What is the exact purpose of the FAQ? Is it to answer common questions
> asked on r.g.r.d? Is it to provide people looking to start writing a
> roguelike initial direction on libraries and algorithms? I definitely
> think the former should be the primary purpose and not the latter.
But the latter is one of the *most* frequently asked questions ;)
IIRC "where/how to start?" kind of questions are posted on this
channel several times a year, every year.
-Ido.
Pfhoenix
> IIRC "where/how to start?" kind of questions are posted on this
> channel several times a year, every year.
Sure, so you would a question such as :
Q: Where/How do I get started writing a roguelike?
A: The process and methodology of writing a roguelike is such a
technical topic, that adequately answering this question is outside
the scope of this FAQ. This site (link to some URL) lists commonly
used libraries, algorithms, and compilers, with links to each
respectively, and represents the constantly growing roguelike
development resource pool you have ready access to.
This presumes, of course, that someone somewhere is maintaining such a
potentially valuable resource.
- Pfhoenix
http://adeo.pfhoenix.com
Gerry Quinn
@b1g2000hsg.googlegroups.com>, Ido.Y...@gmail.com says...
> do Yehieli <ido.yehi...@gmail.com>
>
> Find it on the web at:
> http://roguebasin.roguelikedevelopment.org/index.php?title=Roguelike_Dev_FAQ
The coding advice is out of place IMO, and also is somewhat incomplete -
and while most of what you say there is generally good advice, it
incorporates more of your own prejudices than a FAQ should. However it
could be a good basis for a separate roguelike programming FAQ.
- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>
Ido Yehieli
> The coding advice is out of place IMO, and also is somewhat incomplete -
> and while most of what you say there is generally good advice, it
> incorporates more of your own prejudices than a FAQ should.
It's not mine, it's a pretty old FAQ that people in the community have
been updating and changing for years.
-Ido.
Ray Dillinger
Really? Where are the previous versions? I think I may want to
look at them.
I think it's more appropriate for the FAQ to talk about the design
process than to give advice at the algorithm level. Because advice
at the algorithm level winds up being advice about how to implement
some particular (existing) game, and not advice about designing a
new game.
And, honestly, I've found some of the things you advise here are not
the way I want to do it. That's because code (algorithms, data
structures, etc) follow from design, and your code doesn't follow
from my design. If you feel qualified to give people advice on
what algorithms and data structures achieve their game design, then
you have to start out knowing their design better than they do.
And -- well -- you don't. Not in a FAQ. Heck, you don't even
know what language someone intends to use for development.
And that matters, because a lot of algorithm choices are impractical
in some languages: For example, using linked lists of items in multiple
contexts is a Bad Plan in C, because sooner or later you'll need
to refer to the same item from more than one place (from a floor
tile and a scheduled event affecting the item, for example), and
you'll need to spend a lot of sweat figuring out exactly when it's
okay to deallocate without causing anything to dereference a stale
pointer. It is a less-bad plan in Java or Perl, which have refcount
garbage collection. With refcounting, you don't get into trouble
unless items refer to each other. But that again depends on your
game design; if you want certain kinds of item interactions, they
are loads easier to code in terms of items that refer to each other,
and then you've got a pointer loop that your refcounting GC can't
collect. The same strategy, though, works perfectly in Lisp, or
any fully garbage-collected language, no matter what kind of pointer
loops you have.
Bear
Ido Yehieli
> Really? Where are the previous versions? I think I may want to
> look at them.
I don't keep the old versions on my computer, I just post the current
one here every several months(and not nearly often enough) :)
So far there have been 13 contributers since September 2006.
I guess you can search the archive for my old posts with google-
groups, but by the time I started posting it the faq was already
almost the same as it is now. I guess the roguebasin history might
give you more insight, but AFAIK the first version Kornel uploaded
there was also already almost complete.
And really, if you think something is suboptimal (which you obviously
do) just create a roguebasin account and change the things you don't
like - it wouldn't be reverted without discussion and explaining why
it was reverted (at least not by me).
Just give it a go - donate your time and effort to make it better for
the benefit of the community!
-Ido.
Paul Donnelly
> It is a less-bad plan in Java or Perl, which have refcount garbage
> collection.
I don't think Java uses a reference-counting GC. It's mark/sweep, if I'm
not mistaken.
Ray Dillinger
Noted. I went and looked it up, and refcount GC is not the
default. That makes the linked-list of objects in multiple
contexts work just fine in Java, too, no matter if some of
the objects refer to each other.
Bear