# Creating Measurably "Fun" Maps

This idea is not originally mine. I read about it several years ago in a paper an undergraduate student had written in England. I forget the college, the student's name, the title of the paper and even the year I read it. It had something to do with automatically generating Quake maps which had measurable "fun" ratings using a level description language and a special compiler which generated dungeons.

I chose to disregard the compiler/grammar topics because the underlying idea of the paper was so appealing without it. Basically the premise was this:

Q. What makes a dungeon level *NOT* fun?

A. If the player can "beat" the level without having to explore all the areas you as the programmer have created for them and avoids all the tough monsters and traps and just gets to the "end" of that dungeon level with no effort.

To prevent that kind of problem, this approach measures the amount of "fun" to be had in a dungeon by the percentage of the dungeon that the player must explore (or wants to explore) before that level can be "beat".

For my game ADND, I actually implemented the algorithm I describe below and use it to very good effect to create mission-style dungeons.

First of all, a little bit of graph theory is necessary, so read up about Dijkstra's shortest path algorithm and find a good fast version of it.

The basic premise is to treat the dungeon level as a non-directed graph, where each "cell" is a node and the connections between the "cells" are the edges. You should have a version of DSP (Dijkstra's Shortest Path) that when given an (x, y) coordinate of the start and end cells, will return the list of (x, y) coordinates that trace the shortest path from (x_start, y_start) to (x_end, y_end) (if one exists).

This function is going to be your "tool" for implementing the rest of this algorithm.

First connect the dungeon beginning to the dungeon ending. The beginning is generally the cave entrance or the stairs up or wherever the player begins that dungeon level at. The end cell is up to you to define. Connect these two cells using DSP and stash the returned path. Now you have two sets of nodes. Nodes on the path (path nodes) and nodes not on the path (pointless nodes). The key idea is to "solve" the pointless nodes such that the player either wants to or has to visit most of those pointless nodes (thereby adding them to the path nodes).

There are many ways to "solve" pointless nodes. Before we discuss them, you must group the pointless nodes into pointless areas. A pointless area is a collection of all pointless nodes that can reach each other without crossing any path nodes. For example, if your dungeon is a square and the start node is at the bottom left and the goal node is at the top right, then the path is a straight diagonal line from left to right and it creates two large pointless areas (the triangle above the path and the tiangle of nodes below the path).

Anyway, perform the following actions in a loop until all pointless areas have less than some threshold of pointless nodes and then call it a day.

1. Select the largest pointless area (the one with the most number of pointless nodes).

2. "Solve" that pointless area by

a. Selecting the node with the greatest distance from any path node
b. Performing one of the following actions (feel free to dream up others):
i. Depending on the size of the pointless area, drop a small, medium or large reward in this pointless node.
ii. Pick a node on the path that borders this pointless area and block the path with a door. Place
the key to the door in this pointless node. (replace key/door with anything you want - ADND
uses levers/gates).
iii. If the size of the pointless area is fairly small, it can simply be marked "solved" without doing anything.
iv. Place a nasty trap or other red-herring in the cell to keep the player guessing.
c. Recompute the path from dungeon start to dungeon end, such that it now first visits this "solved" node.
This will create a cycle in your graph (and you must figure out how to deal with that) and it should also
remove this node and several others from the pointless list.

3. Now recompute the pointless areas and sort them by size. 4. As mentioned earlier, if the pointless area with the largest size (number of pointless nodes) is less than a threshold, than the algorithm is complete.

Well, that's the basic idea. In my game ADND, I very rarely perform completely random dungeon stocking. I always run through the above algorithm and everything you meet in the dungeon was placed in a certain spot to "solve" some group of pointless nodes. The same idea can be applied to wilderness areas, underwater areas or what have you.

A final thing I did with my implementation was to "theme" my dungeons by creating the following inhabitant categories: