Before re-inventing the wheel I figured I'd ask:
I'm working on a tile-based 2d-maze level generator for cocos2d + box2d. The idea is:
- I'm using one of the well-known graph traversal algorithms to generate a random maze.
- This data gets encoded as an XML of the type that both Tiled and cocos2d can work with.
- Based on the generated maze tile data, my program should also generate the polygonal data (vertices) that define the walls of the maze so that I can get them from, for instance, a Tiled's XML's object layer and into Box2d for defining bodies.
However, I'm at step 3 and so far, I'm thinking of solving this step with something along the lines of a flood/segmentation/magic wand algorithm. That is, from step 2 I get the graph's nodes which translate in Tiled's XML to, for instance, a 2d array where walls are marked with a number and open spaces are 0s. This is in the cvs non-compressed XML representation for instance.
So what I need to do now is sort of solve the convex-hull problem for a bunch of points (the non-zero numbers in this 2d array), but actually creating different polygons. I also need to then break any concave ploys into convex, but that can be done easiest with ear-clipping and, should I decided to get fancier, Delaunay or something.
Let me illustrate with images:
And in the next image you can see A the set's convex-hull (approximately), and B what I'm trying to achieve (concave subsets of the hull):
That is, I need to be able to distinguish separate polys. Of course, but for one, these also turn out to be concave which Box2d will not like. But like I said, I'll turn them to convex sets afterwards.
The question is, is there anything built-in or tested/tried that I could just grab and use or do I need to implement my magic wand algorithm?
I'm also open to different approaches all together.