Tuesday, May 05, 2009

Fast flood fill implementation

I'm keeping an array of bytes (unsigned char) to keep some collision map. I could probably later on improve on it to make it use a bit for each pixel, but for now I'm going to keep it simple.

At first I was going to create a gray scale CGBitmapContext to store the data, but I wasn't going to actually draw it. Just wanted a collision map to be used underneath so I opted for a simple array.

Of course this meant that I needed some Bresenham line algorithm implementation and also a quick floodfill for the game prototype I'm doing. For the floodfill I first did a naive recursive version of it, but that can easily give you a stack overflow. So I did some searches on faster implementations. I found a couple. The QuickFill algorithm seemed a bit overkill to convert it to Objective-C (and looked complicated as well). Remember I'm still prototyping, so it's not the right time for a lot of optimizations. I settled for the implementation found at codecodex which seems to be a compromise between recursive and iterative approach. Seems to do the job for now. Not the fastest, but better than the pure recursive version.

Need to fix some collision detection problems next, and also double check the line algorithm, since I think it's not behaving right at the edges right now.

1 comment:

Jonathan Brown said...

Hi there,

I am trying to come up with the same thing and have run into a wall. Is there any chance I could compare my code against yours to see where I'm getting hung up?