Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

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

share|improve this question
    
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 –  SaldaVonSchwartz May 21 '12 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.)

share|improve this answer
    
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) ? –  SaldaVonSchwartz May 22 '12 at 18:13
    
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. –  user744 May 22 '12 at 19:41
    
well but this rectangles are going to be adjacent to each other. Is that still kosher? –  SaldaVonSchwartz May 23 '12 at 20:25
    
Yes. Static bodies don't interact with each other. –  user744 May 23 '12 at 20:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.