Search-based Procedural Content Generation
Julian Togelius
I just wanted to announce a little overview/taxonomy paper that I
recently wrote together with Georgios, Ken and Cameron. It's called
"Search-based Procedural Content Generation", and is an attempt to
situate the sort of PCG that's based on various search and
optimization algorithms (such as evolution) with respect to other
types of PCG, and outline some research issues. Along the way, we
introduce a partial taxonomy of PCG in general.
The paper is available here
http://julian.togelius.com/Togelius2010Searchbased.pdf
It will be presented at EvoGames (
http://dces.essex.ac.uk/research/evostar/evogames.html ) in Istanbul
in April and published in Springer LNCS.
Any comments highly appreciated!
Best,
Julian
--
Julian Togelius
Assistant Professor
IT University of Copenhagen
Rued Langgaards Vej 7, 2300 Copenhagen S, Denmark
mail: jul...@togelius.com, web: http://julian.togelius.com
mobile: +46-705-192088, office: +45-7218-5277
Andrew Doull
wrote:
> Hi all,
>
> I just wanted to announce a little overview/taxonomy paper that I
> recently wrote together with Georgios, Ken and Cameron. It's called
> "Search-based Procedural Content Generation", and is an attempt to
> situate the sort of PCG that's based on various search and
> optimization algorithms (such as evolution) with respect to other
> types of PCG, and outline some research issues. Along the way, we
> introduce a partial taxonomy of PCG in general.
>
>
> It will be presented at EvoGames (http://dces.essex.ac.uk/research/evostar/evogames.html) in Istanbul
> in April and published in Springer LNCS.
>
> Any comments highly appreciated!
There are at least two examples I can think of (both from Angband &
variants) with algorithms which at least produce elements of the
fitness function that you might be interested in.
Chris Carr & Chris Robertson created a set of evaluation functions to
determine monster and artifact power for an optional randart.c module
which was later incorporated into Angband proper. For random
artifacts, a set of flags and scalar values associated with an item in
the game is turned into a single scalar value (it's power) which is
used to place the artifact at a random depth and rarity in the
dungeon. Monster power evaluation was necessary to determine the
relative effectiveness of each of a set of flags which contributed a
damage multiplier against a subset of monsters (e.g. slay demon
contributes a higher artifact power if demons are more powerful in the
game).
The artifact power algorithm is based on the damage the artifact can
inflict in a single turn. Where artifacts had abilities other than
inflicting damage, an estimate is used to approximate a 'damage
equivalence'. This estimate was provided and refined by members of the
Angband player community.
The monster power algorithm is attempts to determine the total damage
output a monster can inflict over 10 turns using a very simple
simulation (the monster starts at range 10 and approaches a simulated
player, attacking as permitted), multiplied by it's hit points. Where
monster attacks have effects other than damage, an estimate is used to
approximate a 'damage equivalence', and where monsters have abilities
that increased their durability, their hit points are similarly
increased.
I then modified the monster power evaluation function so that it was
used to similarly place monsters in the dungeon. This meant that
(provided the algorithm was accurate) that monsters were ranked
according to their lethality and survivability: easiest to hardest.
The monster power algorithm has several consequences:
1. Although monsters are not procedurally generated, I could much more
quickly design monsters by hand, and rely on the monster power
algorithm to place them at the appropriate challenge depth for the
player. Previously, monsters placed at the wrong depth would be seen
as being poorly designed, and unbalancing and therefore harder to
design.
2. Algorithmic placement of monsters increases their
'interestingness'. Contrast the current Angband monster list - where a
large number monsters are uninteresting because they can be easily
killed - with a revised list which simply consisted of reordering the
depths at which monsters are encountered based on the power algorithm.
3. Attempting to get Angband to adopt the more challenging ordering
was actively resisted by long term players. It seems that having a
constantly interesting game, where every monster would be a challenge
to the player, was not necessarily the best choice for the game.
In Angband, it is very easy for a player to set their own difficulty
level. This is because of the ability to travel between different
difficulties (depths) with relative ease. In addition, a number of
common abilities within the game allow an experienced player to detect
and decide to either engage or evade particular monsters. Although
there is no explicit generation of new content based on the fitness of
previous content, the player has the ability to select which new
content to experience, which is dependent on their previous experience
with existing content, as well as the accrual of experience from
fighting monsters earlier in the dungeon.
BTW: Did you get my email?
Andrew