I'm finishing up a game at the moment, but I've already got my next project in mind. I'm planning mentally at the moment, but wanted to share my ideas and get some feedback so I don't start on the wrong track when I actually begin developing this project.
I'm very interested in procedural generation, but have done little research. I kind of wanted to take my own stab at it first.
To provide a general overview:
I want to make a Grid-Based Map Generator as an add-on/tool in Unity. To clarify, this generator will be able to create both 2D tile-based maps, and 3D grid based maps. Essentially, I want to allow the user to provide any number of prefabs to the generator, along with parameters for each (isPassable, totalCountOfObjectInLevel, etc.). The only caveat is that each environmental prefab (walls, floor segments, doors, etc) must be a standard size (they can be any size, so long as they're all the same) that will sit inside one grid cell, and that any other items are equal to or smaller than the grid cell size.
The generator will either be run through API calls at runtime to provide random generation (on a per-level type basis) while the user plays, or in the editor, allowing the developer to randomize levels which he can easily modify as he sees fit (the latter is my primary goal).
As a first step for developing the generator, I'll simply create a 2D array of ones and zeroes, 1 representing passable, and 0 representing non-passable. This array will be initialized with passable values, and then a start and end point will be set randomly. Next (and this is one area I'd like your opinions on), I'll implement the A* pathfinding algorithm to generate a path between the points (using 4-directional, not 8-directional cell movement), filling any cell that's not in the path with non-passable values. This seems like the biggest initial hurdle.
Next, because the most efficient path between 2 points won't make for a very exciting level, I'll add a path complexity parameter to the generator, which will be an integer. This parameter will determine the number of points in the path (i.e. if complexity = 4, there will be a start and end point, plus 2 additional points). Then I'll use my A* implementation to find the path between point 1 and 2, 2 and 3, 3 and 4, and those paths combined will become the new entire path. I'll also create another parameter pathsCanIntersect, which, when false, will treat the passable values in the already solved paths as non-passable values, ensuring that no part of any one path can intersect with another (creating a single route between the start and end points, instead of a path with potentially multiple routes).
The next thing I'll have to do at this point is create rooms along the path (another set of parameters minNumRooms, maxNumRooms, minRoomArea, and maxRoomArea), ensuring that each room does not create an additional route along the path (i.e. that a room does not connect two unconnected points on the path). There will have to be some considerations taken here that the area of the map can accommodate the number of rooms of a given size, but I'm not overly concerned with that at the moment.
After all of the above has been implemented, I won't be able to do much else with the 2D value array, and will have to switch over to arrays or lists of GameObjects which will hold prefabs. Here is another area where I'm not sure of the best approach.
I'll then create an array or list that the user can drag and drop prefabs into, from which the map will be generated.
The simplest way to do this would be simply to have GameObjects in each cell, but that would require any developer using the tool to ensure that the GameObject in question had a script with 'isPassable' boolean in it which my generator could read. This would be cumbersome to any users of the tool, so an alternate solution would be to create a class similar to the following:
[System.Serializable]
public class CellPrefab {
public GameObject prefab;
public bool isPassable;
public int maxCountInMap;
//etc, etc...
}
Then, my generator would easily be able to read isPassable and instantiate from this list. Using this solution, the 2D array would also be filled with CellPrefabs instead of GameObjects at the time of generation.
I know I'll have to take other things into consideration, like ensuring that any prefabs of a similar type (item, enemy, treasureChest, etc) are distributed in a way that seems realistic throughout the map (noise generation may be a potential solution?), that any items placed don't block the already generated path, whether a given prefab is a wall, floor, door or other type, and that certain items (particularly doors) have the correct rotation.
What are your thoughts on this? Have you spotted any major issues with my thinking, and how would you tackle this project?