Thanks for such a thorough reply, Anitarf.
While this genre of the map is called a "maze", I assume you don't really want it to be a maze, that is, a heavily branching path with a lot of dead ends. Rather, you want it to be an obstacle course, a linear path assembled out of random obstacles
that's correct with a few changes
it is linear only in that there exists a path from the start to the end. i would much rather not constrain it to being necessarily a single path -- the data structure that resembles a level most is much more a Graph with sets of nodes and edges instead of a list with a set of one-in, one-out nodes.
but this is not so much a requirement as a "wouldn't it be awesome if..."
The goal is to have a randomly assembled winding path that fills up the available space as much as possible. In this case, the task can be broken down somewhat: you can first lay out the course of the path on a grid, then fit maze elements on top of this path.
i didn't think of it all like this but i like the idea. obviously for it to work in an maze environment it would need a minimum length between turns, but that's totally doable. can you think of any other cons besides the natural bias towards small elements? as i said above, i think a graph representation would be cool as it would give the game a adventure-game type feel. by effectively laying out the "main" branch of the graph we limit the space that the smaller off shoot branches can occupy to potentially trivial and un-fillable dimensions (hard drive fragmentation makes a good parallel to this). do you have any ideas on how to keep the main branch as interesting as possible while attempting to eliminate pointlessly-trivial side branches (this isn't the main concern but would be a very cool bonus)
Even with probability modifiers, this approach would likely mostly ignore larger maze elements because they are much less likely to fit the path than a simple 1x1 element. A 1x1 element only moves the current position forward by 1 grid space so that's not by itself a problem but a 2x1 element moves forward by 2 spaces which can cause an algorithm to miss one of the rare spaces where a larger 3x2 element could have fitted. One possible improvement of such an algorithm would therefore be, when inserting a medium-sized maze element, to check if any of the covered path positions could instead fit a larger element and if so, use a shorter element.
hmm do you think that it would really present that much of a problem or is this maybe my fault for not being clear enough
let me elaborate a bit
in this game each level will be a large rectangle -- in the picture above it is represented by the red rectangle. if anitarf's idea for an initial path composed of 1x1 squares ends up being the best way forward, than the green squares in the rectangle will represent that start and the finish. otherwise, pretend they're red
each element that composes the level will be a much smaller rectangle -- represented as the black rectangles, in the actual game there will be many more of these and with more varied sizes
each element will have specific points on it where it "makes sense" that it can join other elements -- represented as blue squares in the black rectangles. this color is kinda a pseudo color: for all other intents and purposes it is black.
for now, because it is simpler to do so, all transition points are equal. in the actual code though, this will be further defined by whether or not the point is an exit, entrance, or both. all transition points, for now, can be assumed to be both for simplicities sake.
which brings us back to the main point: help me think of an algorithm design that can arrange small maze element rectangles in the large red rectangle such that
- The first element of a level is a special checkpoint element. this can be placed wherever (unless using anitarf's initial path idea)
- The last element of a level is a special endpoint element. you must reach this point to beat a level
- Each individual element must have at least one of its transition points next to a transition point from another element
- No rectangle overlaps another rectangle
- The resulting maze is not trivial. it can branch, pivot etc freely and randomly (it is not a straight line of connected elements)
- The last element of a level does not occur "too soon" (a trivial problem if using anitarf's initial path idea)
in my experience, only a few mazing elements need to have a 1x1 entrance and exit that can occur in one spot only. it is probably this part that makes me like your initial random path generation algorithm idea so much