I really like using layered grids to create maps. This may not be the optimal way to approach the problem, but I find it delightfully systematic.
Basically what I always end up doing is creating a number of same sized grids, each with it’s role towards the goal of creating a map – the basic grid (only empty and filled spaces, whatever function they might have), grid with special objects of type “A”, type “B”, grid with height deviations, calculated from some game balance constants, a grid that splits the map into areas, important for something else, a grid that holds probability for different spawns and so on and so forth.
So far – pretty standard. What I am not sure is whether I really need to keep them up at all times. What I do with the grids is combine different sets of them whenever I need to, but may be that’s just showing off – “See, we have enough memory now to afford being inefficient”. Who knows. For a small project it’s certainly not a problem. But I keep thinking I should spend some time exploring optimization for optimization sake, just to ensure I have the mental tool when I need it.
Otherwise – it works fine. I have the map now (kind of) and it’s ready to be tested.
How did I get here? I’m glad you asked…
I have a map that (stripped from any additional functionality) is basically a grid in which random cells are unwalkable. And I have to select two of the walkable cells to use for starting points. Additionally, I had to make sure there’s a way to trace a path between the two starting points.
Well… The naive approach was not expected to work and it did not – I tried selecting a random point and checking whether it’s available. If not – select a new random one. “Taking too long” to find a good point happened even more often than expected, so… What else.
I figured I have no interest in the non-walkable points, so why not put all available points in a list (only Vector3 representations, cause I only need the coordinates), then select from that list. The first point is kind of OK. I need it to end up roughly in one part of the map, so… given that the values in the list are meaningful coordinates, that was not hard. But then I wanted to select the second point such that it is not too close to the first. And I spent a couple of hours brain fried after work trying to construct the perfect .FirstOrDefault() to do the job. I ended up not entirely sure I’m not chasing the wrong idea.
Back to selecting the points directly from the grid, then checking for path between them.
Improvement – the “Blast radius” method. Select a point and check if it’s available. If not – check for available points within radius one. That’s orthogonal adjacency, cause no one needs trigonometry for this particular task. For radius one – check in order the cells on the left, above, right and below the first one. If those are not available – check for radius 2 – a rhomboid perimeter around the first cell. And so on. This worked, eventually. Find two separate points, each as close as possible to a point, that is randomly selected to match some vague constraint (as in “close to the center of the right half of the map”). Then you run an A* pathfinding algorithm to ensure the two points can be connected.
***
Intermission – I have problem using x and y for grids – the problem is that x and y don’t mean anything, which makes them easy to mix. And they do not allow you to take advantage of the fact that those are representing values that have real meaning – dimensions of a grid. So I always use width and depth (which can be height, depending on your setup). So… width and depth is it. It turns out when you have so many grids and so many separate operations on them, it is very hard to find where exactly you have switched the places of the two variables – either as indexes or as counters in some for loop or as boundaries in a for loop.
A week of “index out of range” errors and I have now officially adopted a new name – Off-By-1 Kenobi!
***
And of course right after I made it all work, I came up with a better idea. What is the current problem? You find two points, blast-radiusing, if needed, then run the path finder and you may find that there is no available path, so… right, you don’t have to select two new points. From the list of cells, checked by the pathfinder, select the one that is closest to the point you could not connect to. So there!
But!
Why then go through all the trouble of not knowing if there will be a path? What if you could combine the pathfinding and the random points and avoid the possibility of needing a blast-radius after all?
Yeah. What I’m about to try now is simply flood-fill the map, starting from any available point. At this point I have to check if I have indeed flooded the map, and not one small isolated puddle. The density of the map makes it very unlikely to generate an available spot with 4 unavailable neighbors, but still, not impossible. So I flood, I check, then I choose two points, using my initial vague requirements (as seen above: “close to the center of the right half fof the map”).
Something like that.
