Have you considered using multiple levels or scales of generation?
In my system I use [levels[room_arrays[rooms[walkable_tiles]]]]
I use a room system that handles room sized blocks of the map (10x10) and also larger "room arrays" such as a 4x4 spiral or a 2x3 "L" shaped room. I'm working with a 3d program but I'm sure it could be converted easily to work with a 2d game engine. A room array looks like this:
[[1,1],[0,1],[0,7]]]
####
#oo#
##o#
##e#
####
The border walls are implicit in the generator and don't have to be defined in the array. The 1's =Ordinary rooms and the 7= Exit, a special square which is used as the linking point with other room arrays. A room array may have one or several exit squares, but most contain at least one otherwise the room won't be connected (a function could be added to automatically add an exit square if one is not present).
The result looks like this:
The crosses are just simple visual representations of a single tile for quick testing for the main algorithm, the final result uses a NorthEastSouthWest tile picker to ensure rooms and corridors have the right shape:
http://www.youtube.com/watch?v=NfzyUwUDFmwFor example if the northern neighboring tile is an ordinary room and the current tile is an ordinary room it uses a ordinary room transition tile for the northern quadrant. If the eastern neighboring tile is a corridor and the curent square is an exit square it will use a doorway complete with pre-placed door or the Easternmost quadrant of that room. If the current tile was not an exit it would use a wall quadrant instead, blocking access to the corridor from that tile.
My rooms are 3d objects with a walk mesh, but it would be easy to specify rooms as arrays, and even to randomly generate room types or room quadrants (with alcoves, doors, pillars etc...) to form a dictionary which could then be sampled to provide rooms for the level builder. Because the generator works with 10x10 chunks instead of individual tiles it's quite fast, for example you can work with a 200x200 graph as easily as with a 20x20 graph.
I use A* to generate corridors and a couple of simple functions to randomly rotate and mirror the room arrays so they don't get too repetitive. when running the A* pathfinder I can give existing corridors a lower movement cost to encourage the path finder to use existing corridors whenever possible (increasing connectedness). I can also use some additional rules when calculating the paths:
(room_list is a list of all rooms tagged as exits from the list of room_arrays when generating the map)
1: forwards single connectedness (all rooms are connected to the start room, no extra incentive for A*to use existing corridors) start tile for A* is room_list[0], end tile is room_list[room_index] (sounds like the algorithm the OP was complaining about, not really a bad algorithm, unless it's the ONLY algorithm).
2: backwards single connectedness (all rooms are connected to the end room, no extra incentive for A*to use existing corridors) start tile for A* is room_list[-1], end tile is room_list[room_index]
3: Multiple cyclic connectedness (all rooms connected in sequence) start tile for a* is room_list[room_index-1] end tile is room_list[room_index]
4: Random multiple connectedness (as above but randomly select the room index from a temporary list and .pop() each index as you go through the list.
You could also run multiple corridor generation functions with different rules to be sure of multiple connectedness.
Some things to consider:
- The script could be much faster, I learned a lot about A* during development of my game and I'm sure I could cut the generation time to just milliseconds just by implementing a few improvements, something I plan to do later when I've got time to spend on optimizing features that work already (such as using python's heapq in the A* algorithm or using smaller graph sections i.e. limiting the search area, or just by using a more efficient graph style, as I currently use an array of lists). Anyway, the slowest one you can see there is a 60x60 grid which would be a 600x600 tile dungeon, covering an area of 360,000 tiles and generated in just 6 seconds.
- The corridors are a little boring, if you check out the video above you'll see I also experimented with adding granularity to the map on order to make corridors snake and turn a little more to avoid areas of hard rock.
- Having more rooms and less corridors may be preferable, if so just raise the target number of rooms or reduce the graph size.
- I used 10x10 chunks with double square doors and corridors in this particular generator as that's what the tile set is designed for, but you could use 5x5 chunks and single square doors and corridors quite easily (something else I plan on implementing in the future when making a different tile set).
- This is still in testing, so I have quite a limited variety of room arrays, so you can see lots of repetition (only 58 unique room arrays, max size 4x4). In the final game there will be lots and lots of potential room arrays, I may even write script to automate generation of new arrays.
- If you're going to be working with big levels like this you'll need to speed up how your game handles such things as path finding, LOS or rendering of the dungeon. The program I use, Blender game engine does this by only rendering tiles in the camera view fulstrum, and I help it along by disabling animations and logic for objects outside that area. I also use dictionaries to store my level and skip any tile which is not a room or corridor tile when building the dictionary. When building a graph for LOS or pathfinding I first check a tile to see if it is in the dictionary and if not I can ignore it or have it return False to any boolean check. In that case the room at the beginning of my post would be a dictionary of 4 entries instead of a 4x5 array of 20 tiles, as only those 4 tiles are important. You can do other things such as using Bresenham lines to pre-explore a route to a target tile before kicking in the A* pathfinder, if the route is clear you don't need to use the more time consuming algorithm.
I'm sure you guys know all this stuff already, but I wanted to be thorough in my explanation as I'm rather new to coding and don't know all the terminology, and I don't know what is commonly done in roguelikes to speed up performance. You probably do all the things I suggested already, or can tell me why they are a bad idea and you don't use them.
