Jump to content
  • Advertisement
Sign in to follow this  
JEJoll

Unity Grid-Based Map Generator

This topic is 871 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement

sounds complicated.

 

if you're trying to generate dungeons, it seems to be best to do it on a room by room basis. it can still be tile based, but is generated one room at a time.

 

for caverns and caves, algos that carve out open space from a level that is initially all impassable seem to work well.

 

you'll need a 2d map for the dungeon level (doors, open space, walls, etc).

 

you'll need a list of items on the level.

 

and a list of actors (might be lumped with items as generic game objects list - depends on engine used).

 

A*  tests or simple inspection can guarantee a path from random entrance to random exit.

 

since your primary goal is to generate maps for further human editing, i'd just let the humans erase walls as needed to ensure a path from entrance to exit and forget about A*. humans are still much better than A* at that kind of stuff. especially about which walls to erase to fix things.

Share this post


Link to post
Share on other sites

Thinking about what you've said, it seems like creating the rooms first would be quite a great deal simpler. It would save a lot of checks that rooms don't 'corrupt' the path. 

 

Granted, humans are better than A*, but I'd like to still have the paths be generated, if for nothing more than completeness--especially if I wind up trying to sell the generator. The developer can always modify the paths some time after generation. Maybe I'll simply add generatePaths flag that toggles the whole A* thing. 

 

However, what you've said has made me realize that instead of using pathComplexity to make the paths more random, using each room as a point in the path would accomplish the same goal, but save some fiddling. 

 

You mentioned cave/cavern algorithms... Are there any algorithms that come directly to mind?

 

Thanks for the input!

Share this post


Link to post
Share on other sites

-Render a simplex texture at several different scales

-Render a path texture from a to b

-Do a flood fill based on both the simplex and path

In other words the path just helps the flood get to point b in-case it didn't otherwise lie in the flood zone

All of this work can be done on the gpu many times faster than as a cpu algorithm. If this is something you might be interested in I can give more detail 

Share this post


Link to post
Share on other sites

-Render a simplex texture at several different scales

-Render a path texture from a to b

-Do a flood fill based on both the simplex and path

In other words the path just helps the flood get to point b in-case it didn't otherwise lie in the flood zone

All of this work can be done on the gpu many times faster than as a cpu algorithm. If this is something you might be interested in I can give more detail 

I have to be honest: most of what you just said is completely foreign to me. However, it does sound interesting. Could you elaborate?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!