Procedural Map Generation
For example, diablo, torchlight, path of exile.
Start with a basic DFS or BFS algorithm to generate a maze, then extend it, add rooms, etc. Really, the number of possible solutions is huge, everyone comes up with his own.
Usually, the method is to first generate a few rooms, then connect them with passageways until they are all connected. The rooms can be in any place so that should be easy. For the passageways you will need to experiment with a few algorithms to find one that works. A lot I tried were either to slow or used to much memory, so the one I ended up with was based on just moving first the x then the y towards the target, and if you ran into a obstacle, only do X (or only do Y) until you are past it. This is probably not the best method, since it often fails to find a path, but its fast and avoids obstacles pretty well.
My program was in python, so I don't know if seeing my code would be helpful for you, if it is, just ask!
Nice link spacerat. It even has a college research paper that goes into pretty good depth explaining each of the techniques.
- Eck
Thanks, I've seen it though. Everything I can find anywhere is having to do with unity and c#. Neither of which we're using
Thanks, I've seen it though. Everything I can find anywhere is having to do with unity and c#. Neither of which we're using
Concepts typically can be extracted from such sources and used in other engines. In the case of the link above, the key concepts are DeLaunay triangulation, BSPs and cellular automata (which, themselves, provide some tasty search terms).
My personal recommendation is to take a look at the games you mentioned (Diablo, Torchlight, Path of Exile) and try to puzzle how they are doing things. There are plenty of algorithms out there (google "drunkard's walk", for example) most especially in the field of roguelike development, but many of them tend to end up in the meaningless "maze of twisty passages, all alike" category--not unlike the three methods posted above. Those types of dungeons can be great fun, but Diablo and such tend to go a different route, using large pre-built "meta tiles" or blocks from which the levels are pieced together. These pre-built blocks follow the theme of the level, be it "torture chamber", "cliffside wilderness", etc... Using such prebuilt pieces tends to dramatically reduce the possibility space of the levels, such that all variations tend to feel similar and follow similar rules.
I suggest that you don't start with the level generator; instead, you should start with the theme of the level and work backwards from there to determine the kinds of building blocks you will need, and determine a set of rules (a grammar) for putting the pieces together. A source for tasty info on such grammars is the Procedural World blog. In particular, the entries on grammars for architectural bits.
I haven't been messing with the Unreal Engine at all, but I stumbled across this while searching:
http://forums.2k.com/showthread.php?171916-No-random-maps-Well-here-s-why
This was in 2012, but if the core of the Unreal Engine stayed the same, it might explain why you're having trouble.
I recommend reading about the algorithms that were mentioned above and taking a stab at implementing them yourself.
- Eck
using large pre-built "meta tiles" or blocks from which the levels are pieced together. These pre-built blocks follow the theme of the level, be it "torture chamber", "cliffside wilderness", etc... Using such prebuilt pieces tends to dramatically reduce the possibility space of the levels, such that all variations tend to feel similar and follow similar rules.
this method is used for dungeons in oblivion. they create tiles which are geomorphic 3d sections of a level, then cobble them together to make a dungeon level. the cobbling together of the 3d tile sections could just as easily be done with code. they have 3 basic tile sets (dungeon walls, cavern walls, etc). while the level layout can vary a fair amount, the look can become repetitive, given only 3 tile sets used for probably 150+ dungeons in the game.