So I am changing tack, and I was wondering if anyone had any feedback or (freely accessible) relevant reading...
What I am thinking is to turn the problem upside down.
So rather than:
- First construct a PCG algorithm that can create playable levels (then tune for "fun")
I am thinking instead:
- First construct a game where even wholly random levels will have some merit (then look to improve on "random")
I am thinking of games where objects have a rich set of interactions based solely on proximity. The player will have some sort of objective aided/hindered by those interactions and even randomly deploying objects will give some sort of unique situation (making some sort of sense) that the player must negotiate.
For example, suppose the objective is a simple as "cross the map and survive":
- Turrets with limited range must be avoided or destroyed.
- Cover objects merely need be within a turret's range to modulate that situation.
- Repair robots merely need be near a turret to make destroying it harder. (And create a secondary objective of "first destroy this robot"...)
- Pairs of turrets get harder to destroy the closer they are together.
- Enemies are like turrets that will chase you.
- Pairs of enemies merely need be close together and they team up forming a harder challenge.
I am also thinking that a varied set of player abilities (both built-in and via pick ups in the level) generate a variety in how the player tackles a particular situation.
- A built in "stealth" ability provides advanced options for "avoid" strategies (and interacts with lights and shadow-casting objects such that it is again modulated by the precise level configuration...)
- Rare invisibility power-ups give an even better option which must be rationed
- And the ability to throw some object as a distraction is another option with its utility highly dependent on the exact positioning of enemies and obstacles
The important concept, I think, is to have each actor in the world automatically adopt behaviours relevant to its context (and arrange that the player can do the same.) I hope such behaviours can be pretty simplistic, and complexity will emerge naturally from their interaction.
With a model like this, I think:
1) random arrangements will present distinct challenges
2) some configurations will be much more dangerous, but if the map is wide enough these can be avoided rather than overcome with force
3) increasing bad object density will increase difficulty on some sort of exponential curve (because adding separate objects gets linearly harder, but adding objects in proximity adds further difficulty on top of that)
4) increasing good object density will reduce difficulty on some sort of asymptotic curve (because there is a maximum number things you can use at the same time...)
5) modulating relative object density (like reducing the probability of lvl 1 opponents while increasing the probability of lvl 2 opponents) might give a more "nuanced" difficulty curve
5a) and can also provide a degree of "theming" (there are almost no health packs on this level but lots of potions of speed, or swap out the standard "goblin" family of opponents for "trolls" who have different strength/weaknesses but similar difficulties, or "traps, traps, traps!")
In theory this can be a playable game with only the most rudimentary level generation.
If I can make that playable then I think it will provide a richer context within which to experiment with less naïve PCG techniques.
v1 might drop impassable blocks 100% at random (giving a small chance of impossible levels, increasing with block density)
v2 might just detect impassibility and delete random blocks until the level is possible
v3 might start to look at allocating of "regions" on the map with intended passable/impassable relationships and walls filled-in accordingly
v1 will have a chance of some really difficult configuration of objects, and a lower chance that it is unavoidable
v2 might detect difficult configurations via a heuristic and apply some moderation to them, if required
v3 might map the minimal difficulty path through the level and try to control the difficulty of that, maybe even adding hints as to what the worst areas are (e.g. piles of adventurer skulls)