Procedural generation methods have found their way into video games for a
broad range of content types. One challenge that developers and researchers are
still struggling with is emergence and the generation of game narrative and missions
(quests). Only little research has been conducted on generating non-trivial
side-quests aside of the main plot of narrative-driven games, although it can be observed
that the structure of these quests shows similarities across games and genres
and that they could thus be an easy target for procedural methods. A big challenge
in research for quest generation is ensuring the causality of non-trivial quests and
relations between quest elements with the game world and the main plot, as well as
providing usable concepts for commercial products that enable control of designspecific
constraints and extending of contents and features by game designers.
The goal of this thesis is to describe, implement and analyze a procedural method
for generation of side quests in a role playing game. This method is evoked ”semionline”,
meaning that quest lines are generated at the approach of certain areas in
a play session. The generation is NPC-focused and takes into account Smart Entities
in the game level, which provide actions that result in game state changes.
These entities can be locations, the player, other NPCs, monsters, items or any
other entity type that appears in an RPG. The method results in an appealing presentation
to the player with dynamic textual dialogues and objective descriptions.
The resulting algorithm is able to generate solvable, interesting, challenging and
meaningful quests, and encourages replay of the game.
The implementation of the proposed concept is conducted in cooperation with a
video game company on a commercial role-playing game title with free-roaming
areas and turn-based combat. This allows to validate the usefulness of the approach
in a full non-linear game with a lot of different entities, and also enables further
evaluation of its effects on players of the product at a later point.