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:

  1. I'm using one of the well-known graph traversal algorithms to generate a random maze.
  2. This data gets encoded as an XML of the type that both Tiled and cocos2d can work with.
  3. 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:

enter image description here

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):

enter image description here

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.

  • \$\begingroup\$ given the unanimous silence... at this point I think the way I'll go about it is with blob extraction, which I'll either code myself or use OpenCV's \$\endgroup\$ May 21, 2012 at 17:46

1 Answer 1


Make a square body for each tile. Box2D scales up very well when using a large number of static bodies.

If you are very concerned, you could make rectangular bodies along each scanline. This would result in 14 bodies for your sample picture, down from 42 if you make a body per tile. This generates only convex polygons so you don't need more postprocessing, and is also faster than just a flood fill.

(But because of the spatial partitioning algorithms involved it's really not that big a deal - 14 to 42 is only two powers of two.)

  • \$\begingroup\$ makes sense, but I had discarded that idea thinking eventually I could very well have bigger mazes and maybe even arbitrary poly shapes. If that were the case, do you agree the most practical thing would be blob extraction (connected-component labeling basically) ? \$\endgroup\$ May 22, 2012 at 18:13
  • \$\begingroup\$ I think you'd have to get really big before simple scanlines would not work efficiently. A static fixture in Box2D is essentially free if nothing is near it. \$\endgroup\$
    – user744
    May 22, 2012 at 19:41
  • \$\begingroup\$ well but this rectangles are going to be adjacent to each other. Is that still kosher? \$\endgroup\$ May 23, 2012 at 20:25
  • \$\begingroup\$ Yes. Static bodies don't interact with each other. \$\endgroup\$
    – user744
    May 23, 2012 at 20:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .