Cavex

Cavex is a 2D side-scrolling platform game. I started creating it back in 2005 as a hobby project. The 2D version was abandoned in 2009, but recreated with a new name and look as EaS, which you can read about on the blog. Cavex was made with inspiration from classic platform games such as Sonic the Hedgehog and in particular Commander Keen. To lesser extend, Super Mario is an inspiration too, although the levels in Mario tended to scroll mostly in one direction only, while the levels in Cavex must be explored in all directions, like in Sonic and Commander Keen.

Cavex is different from other platform games in two respects:

• The enemies are highly mobile.
  Most of them can follow you everywhere in the level. They don't cheat though - if they loose track of you, they have to search around.
• The levels are randomly generated.
  Every time you play, you can play a fresh new level. The levels are generated automatically at runtime from a complex set of rules and algorithms.

Note: Cavex is not a finished game! It's a demonstration of the progress I've made so far. You can't beat the game. You can't even beat a level yet. But you can run around and explore the levels and battle the AI enemies for fun. Note that the gems and locked doors are only visual place-holders at the moment.


A lot of aspects of the game are not yet decided on. The story, the environment, the different types of enemies and the visual style are still at the brainstorm stage. At the moment the game is more of a technical experiment. What I have spend my time on is mostly the random level generation and the enemy AI. But who knows what it might end up becoming.

Credits:

Concept, Art, and Programming

Rune Skovbo Johansen

Cavex is a personal project I have worked on in my spare time.

Screenshots

Screenshots from Cavex at various stages of development. The newest are at the top.

Level maps

Maps of entire levels from Cavex at various stages of development. The newest are at the top.

Discussion of concept

In Cavex the levels are randomly generated. The idea is to have a few similar randomly generated levels; then proceed to a new zone in the game with a new tileset, new enemies and traps, and new features in the terrain, just as in the classic side-scrolling platform games. The algorithms can be given very specific input for each level. The number of traps, pits and enemies of each kind, the number of locked doors, bonuses and so on. That way the difficulty of levels can be roughly controlled despite their random nature, but of course not completely precisely, due to the perceived difficulty being more than just the sum of the parts.

I know that random level generation has its limits. I know that randomly generated levels will never completely match the variation and brilliance found in manually crafted levels created by highly skilled level artists.

However, Cavex is supposed to be a bit different from most other platform games. When you play a fighter game (Street Fighter, Virtua Fighter, Tekken) in single player mode you don't beat a level - you beat the AI enemy. When you play real-time strategy games in single player mode, the level (or "map") gives a lot of variation and challenges, but ultimately it's the AI enemy you're up against. Take this element of beating the AI and make it just as important in a platform game as beating the level itself. This is the idea in Cavex. Randomly generated levels with complex AI that creates a gameplay with elements from typical platform games, as well as small-scale strategic elements in order to beat the AI. The strategic elements will mostly be about using the terrain and obstacles to your advantage.

It's a different type of game where randomly generated levels fit in more naturally. It's also a type of game I've never seen before, so it's impossible to really know if it'll work out to be a great entertaining game or not. But I want to try make something new rather than just reinvent what's been done perfectly lots of times before.

The random level generation explained

I've come up with a ton of different algorithms that build upon each other to form the random levels. They all include lots of tweaking and practically no math, so it's not so much algorithms in the computer science sense. I do generate the levels in such a way that they are provable solvable though.

The entire level is based on a simple maze representation in a two-dimensional array. The maze is generated with a modified depth first search.


Based on the maze, a binary tree data structure is created where internal nodes represent T-junctions and leaf nodes represent dead ends (as well as the goal). In this data structure the arrangement of locked doors and keys is computed, and then planted in the corresponding places in the array. After that the array maze is modified in several steps, cutting down certain wall sections to create shortcuts (which then form loops) - making sure that it doesn't connect sections separated by a door.


After this, "air space" is calculated to form wide open spaces and prevent the level consisting of narrow tunnels only. This makes it look less like a maze.


Now the actual level is created based in the simple maze. The maze is made out of 16 basic types of cells. Every second index in the maze array (in both directions, meaning one fourth total) marks the center of a cell in the level. The 16 cell types are thus formed by the combination of there being a passage to the neighbour cells or not (2*2*2*2 = 16). The floor and ceiling is made uneven using an algorithm I won't go in details with, and each cell type has rules for the creation of "stepping platforms", based on the height of the floor etc.


The sections of overground and underground terrain follow the cell borders. Initially each cell is overground or underground at random (with more underground cells at the bottom) and then an iterative algorithms modifies this pattern by comparing neighbour cells, in order to have the areas "cluster" and give preference to overground terrain in open spaces and underground terrain in confining spaces. After implementing wide open spaces, this cleaning procedure became highly necessary and helps a lot making the levels look natural. So far, the difference between overground and underground cells is purely visual, but there could also be differences in the kinds of traps that are likely to be encountered in the two areas. (Enemies too, but many enemies are supposed to be highly mobile and thus not confined to a specific area.)

And then there's the tiling. So far the level has consisted of only generic types of blocks, stepping blocks (which are only solid when coming from above), and sloped blocks. This makes it easy to generate the level, and the physics system have only these few different types of blocks to handle. However, to the player, there must be grass at the top of blocks, and other details for walls and ceilings, and everything must tile in a nice, yet random looking way without too recognizable patterns. An algorithm takes care of that as the very last step.


The jump design-wise to include wide open spaces in the levels really improves the variation and helps to hide the synthetic maze-like origins of the design. Although there are still no traps or enemies, nor any semi-dynamic things like moving platforms or fireball spewing lava pits, the terrain itself almost begin to match the complexity and variation I have seen in classic platform games with handcrafted levels. (The site vgmaps.com really helps make it easy to study the levels in those old games.)