Yes, it's been two and a half months since my last update. I suddenly got weirdly busy again.
Anyway, in my earlier entry "I Just Accidentally a Roguelike" I discussed a system I had concocted for assembling levels (or really any structure) from premade parts with attachment nodes. I mostly rambled on and on about the ComputePenetration function exposed in Unity's PhysX implementation and didn't illustrate the actual level generation process very clearly. To rectify that before I continue with new information, here's an image of a level the system generates:
This level is in the process of being generated. In the center is the starting room, which I placed manually. Branching off of it are randomly selected other pieces - in this case, simply small square rooms and straight hallways.
Observe how near the top right is a room with its attachment nodes visible. There are actually four here, though one is obscured. This and the other two green nodes are unoccupied and can accept new pieces, while the orange node is occupied by the hallway running toward the lower left. The hallway is not selected and thus its own attachment nodes are hidden, but they too are occupied, one by the selected room and the other by the second segment of hallway that in turn connects to the starting room. Every room and hallway in the level has its own set of attachment nodes in similar situations.
The level generator runs in iterations, during each of which it pulls from the set of all existing nodes, ignores those that are already occupied (This is not an optimal approach and I don't recommend copying it! This was an experiment.) and then performs roughly the same process as this one beautifully illustrated by Lived 3D:
My version naturally has a few differences; for instance as I detailed before, I use a more precise collision detection technique, but on the other hand my system doesn't currently have the ability to automatically prune rooms in the event that it cannot add an end cap. For now this latter issue is easily accommodated by simply having a small "wall" piece that fits within the doorway of any room and can safely be inserted without risk of overlapping another room.
Both my and Lived 3D's systems work fairly well for levels of a limited size, but since I first made mine (two years ago already, wow) I've become aware of a major limitation they have.
In very basic mathematical terms, the structure usually described as a "level" in a game boils down to something called a graph.
No, not that kind of graph. I mean the type studied by mathematicians in the field of Graph Theory. In short, a graph is a data structure that follows these three rules:
- Some number of vertices exist; a vertex is the intersection of some number of edges. This can be zero edges, and the number of vertices in the graph can be zero as well.
- Some number of edges exist; an edge is usually a connection between two vertices, though in certain types of graph an edge can connect a vertex to itself or form a ray extending infinitely.
- Edges can only exist where they are connected to vertices: no edge can exist "alone."
In technical terms, edges and vertices, while generally visualized as dots and lines in 2D or 3D space, do not need to exist in any type of space at all, and the positions at which vertices are drawn is immaterial. In level design, the physical space and the vertices' and edges' places in it tend to be very important, but for the moment I'm bringing up this topic because of a very important concept in graph theory - that of a tree. No, not that kind of tree. Observe these two graphs:
The first graph is called a "tree" because any vertex within it can be called the "trunk" or "root" and all of the edges connected to it "branches." In theoretical terms, the defining feature of a tree is that it does not contain any cycles, i.e. regions within the graph where it is possible to begin at a vertex, follow a path of connected edges, and return via that path to the starting vertex. Real trees tend not to grow branches in loops back into the trunk, after all. Note how in the second graph, two closed loops exist where one can create a path from one vertex back to that same vertex.
In level design, if one imagines rooms as vertices and doorways (or portals, or bridges, or whatever) between them as edges, pretty much any game level forms a graph and very often these graphs contain cycles. One game in which this is made very obvious is The Talos Principle:
The goal of this level is to solve a puzzle and thereby gain access to the area pictured and the T-shaped gold block therein. Once the player walks onto it and collects it, the fence at the right falls down, allowing the player to return to the beginning of the puzzle and leave through the front door instead of having to backtrack the whole way. This layout is necessary due to a design choice by the developers to have the puzzles be accessed in a non-linear fashion and all connect to a central hub. The underlying graph structure is also easily visible in many games via an overhead view of the level layout, as illustrated on Jared Mitchell's blog in regard to the game Amnesia: The Dark Descent:
Many level design tutorials exist that refer to graphs and cycles in this manner, and there are strong arguments for why this is a major boon for many games.
The system I made, however, can only generate trees. Once rooms are added, it only checks to see if more rooms can be attached onto their attachment nodes, and it has no way to examine their spatial relationship to other rooms' attachment nodes to see if it's possible to connect a new part of the level to an older part and thereby form a cycle. Much of the time, this isn't even possible because the doorways of these rooms won't line up with those on existing rooms. Alignment can be assured, or at least made much easier, by restricting level generation to a grid, as many games do very successfully, but I'm interested in exploring ways to keep the level free from grids wherever possible, meaning that the positions (and orientations) of attachment nodes can be highly variable and will almost never align perfectly by chance. Examining the first image in this post, for instance, reveals hallways that end in walls or converge in a way that seems like they could connect, except that there is no connector piece available that would fit in that space and complete the connection.
Therefore, in order to achieve this functionality, I've set out to engineer ways to make level pieces more flexible so that they can move their own doorways (and attachment nodes) to align with those of other pieces. I plan to go into more detail on the strategies I've begun to explore in a future entry.
No comments:
Post a Comment