Proceedural Content Generation prototype for creating DOOM-like level maps
Uses simple graph-rewrite and iterative force relaxation to generate game-like levels which make topological (e.g. playable) sense.
Retains meaningful topology by applying re-writes which by definition do not alter any constrains that were already added. e.g. if a corridor joins two rooms, the corridor can be rewriten into a more-complex construct (say an obstacle of some sort) with the proviso that the corridor remains passable. Similarly two rooms which are not directly joined cannot become joined as a result of a rewrite.
Example:
START -> [expandable] -> END
Can rewrite to:
START -> JUNCTION -> RED_DOOR -> END
\
--> [obstacle] -> RED_KEY
And subsequent rewrites will not add any connections to END or RED_KEY that byepass the RED_DOOR or the [obstacle] respectively.
Layout of the graph on the 2D plane is achieved iteratively as the graph is complexified.
A forcefield approach is used, where constrained distances are driven towards their required range by forces and a simple Newtonian integration approach is used to iteratviely relax the layout. This iterative approach works because:
- the rewrite rules only add local topology, which preserves more-distance topology
- edges can become stressed, e.g. when forced longer than desired by other constrains -- typically this is because they edge
form part the boundary to a sub-region that wants to contain more area than there is room for
- when this happens the most stressed edge is split into two similar edges which permit a greater length, then the geometry is relaxed some more
- and this is repeated until no stressed edges remain
Edges have maximum and minimum lengths. Edges also have a width which ensures there is enough space for whatever the edge represents to be inserted (e.g. a corridor must be at least as wide as the player.)
Nodes have a simple radius, the idea of which is to reserve enough space for some contained room (or nest of rooms) of more complex shape.
Once a desired graph skeleton and "ball and stick" geometrical arrangement has been achieved, the plan is to expand the geometry into a full representation of all rooms, and corridors, in the form of edges and corners. Possibly using more relaxation to fit these tightly together...
e.g.
ROOM -> ROOM (graph)
N1----e1------N2 (ball and stick, N1, N2 have radii, e1 has a width)
_ ______
__| |_____| |
|_ x_____x | (full geometry, the "x"s may indicate where doors should be,
|__| |______| there may also be some geometry associated with doors)
- rewrite mechanism created and working
- could be more sophisticated
- uses concept of in and out edges to indicate "forwards" and "backwards" through level, may need more than this to correctly accommodate side-turns and loops
- only a few simple rules tried so far, no doors or conception of different types of non-terminal (such as [obstacle] and [reward]
- iterative rewrite/relaxation mechanism created, prototyped and under more-finished construction
- I have seen it working however :-)
- many unit tests created, a fair few still to go
- detailed geometry not even thought of
- finish tidying rewrite/relaxation system
- write detailed geometry layout system
- add primitive elements of playability such as doors/monsters/user avatar/hit-points
- play, I may see if I can get something demoable for https://itch.io/jam/procjam
- more types of expandable node as in 1-iii
- some sort of measure of difficulty of created level above just "size"
- different discriptions of edge directions as in 1-ii (if required)
- edges serving roles other than "corridor", e.g. an area can be wrapped in edges of type "fortified wall" and edges of type "corridor" pass through that only at nodes of type "gate"...
- one-way edges can be introduced, as long as the output of a rewrite always leaves some an overall connectivity the same as it started with
- teleporters are easy, they are just a pair of nodes tagged as having that property, this can be leveraged in re-write rules if we want to add some new "remote" area