I thought a second post explaining a little more about my implementation of the marching squares algorithm. As basic as it is, it could still be a resource to other people out there. I know personally it took me quite some time to figure out how it all works, and then longer to understand a way to implement that in code form.
At its simplest, the marching squares algorithm really is very simple. There are steps required.
1) Create a grid.
2) For each square in this grid, See if any object intersect with its corners.
3) For each of these intersected corners, draw the line contours according to the rules.
Okay, so on their own, those points don’t make much sense, so let me explain it in the context of my little example.
Create a Grid
So I’ve said that the first step is to create a grid, and it really is. For my example I used a 2d array. Currently it’s a purely logical grid, and doesn’t store any data, in future versions however it will combine with our ‘spatial grid’, which only does calculations for relevent squares ( more on which squares are relevent in the next section ). And that’s section one. Now, obviously the scale of your grid is dramatically going to affect your performance ( 800×600 may look pretty, but that’s a *lot* of calculations ), however all I want out of my grid are some coordinates, the detail I plan on adding later – as long as I have the bounding coordinates, All is good.
This is where things start to get interesting. Let me first talk about my particles, They’ve got two properties that matter. The Radius, and the ‘energy’.
This ‘energy ring’ is the important part. In the blob examples, we’ve called it our ‘threshold’, that is, the distance particles want to be away from other particles. And so I figured I would use the same concept for this example. When the blobs are placed on the grid, They look like this :
As you can see, with a blob placed directly in the centre of a grid square, the energy radius neatly fits around the whole particle. I’ve made the grid size relative to the particle radius. Obviously if you changed this, you would get different results, possibly with particles not even registering at all – but you can get some interesting effects.
From here, I check every grid square to see how many of the corners are within the energy threshold. ( This is a simple point to point distance check – nothing fancy as of yet ).
So in the above example, there were 9 squares to check. The First one ( top left ), had only one corner in, the next ( top middle ), had its bottom points, the next ( top right ), only it’s bottom left point. etc etc. Move the blob slightly, and the dot change accordingly
Each of the squares has to be calculated individually ( though I just realised an idea that could potentially save a lot of time ). As I said, my version is very very basic – and so, my implementation is very simple.
ANYWAY moving on, this is where this little table will come in handy :
Now you see why we calculated those corners ? Note case 5, and case 10 have 2 different possibilities, I’ve gone with the non-red versions for all of my particles. I think it wll give a ‘goopier’ feel once it’s been properly implemented.
The next step in the implementation is to calculate which case is relevent for what square. Draw the lines, and voila – you’ve got :
And you get the picture. I told you it was fundamentally simple. Now, I believe I am cheating a little. ‘true’ marching squares traverses surface lines ( or so some resources lead me to believe – though others, didn’t ). I’m merely drawing lines with flash’s inbuilt this.graphics.moveTo / lineTo methods.
This is just a very basic post to explain how my current iteration works. Though since making that original version I’ve made various changes to the implementation to speed it up a bit. Snookle is working on bitwise operations to help speed up the square search, and I’m going to work on a faster searching method tonight ( one that doesn’t do calculations twice, as mine currently does ).
I hope this explained something to those out there who are still confused, It might be a little disjointed – it’s something like 38 degrees in here at the moment – But yes.