Sign in to follow this  
Echofiend

Jezz sectioning algorithm

Recommended Posts

Echofiend    100
Hi guys. I am currently trying to implement a function that will section off and close a portion of a map if nothing is there. Basically it is exactly what jezzball does when you create a new wall and there are no balls in the area. However, I am absolutely stuck as to how to do this. Everything I come up with there is something that will cause it to not work... anyone know how to accomplish this? I currently have a 2d array that stores my individual wall pieces as they are being built and after they are built. So any place on the screen that does not have a wall is null. Don't know that it matters but i am using c#, but mainly just looking for an algorithm that works as my head is about to explode lol. Thank you very much in advance edit: I forgot to add the subject in... I fixed it.

Share this post


Link to post
Share on other sites
szecs    2990
I don't understand the problem clearly, but try looking into "floodfill" or "flood-fill"

If fills an arbitrary shaped area (from a starting element), if it's elements fulfill a condition. In your case, they are empty cells.

Since I didn't understand the problem clearly, I can't come up with a good idea.

At first, I would do this:
look for an empty cell: then start a flood-fill from there (on a temp array). If I found a "ball", then cancel the algorithm, if no balls just walls, then it1s an empty area, so copy it to the array.

But I'm sure I misunderstood the problem, so try to explain it a bit more, or maybe thyt1s my fault.

Share this post


Link to post
Share on other sites
KulSeran    3267
Well... I did this in 3d at one point source here, and just simplified the problem, and made it so you couldn't build partial walls anywhere. That makes the problem simple, since each wall divides the "node" that it is in in half. Then check if there are any balls in the volume of each half, and delete the half if there is nothing there.

Share this post


Link to post
Share on other sites
Echofiend    100
I have thought about going the route of no partial walls, but the other members dont want that... it would be much easier.

The reason I dont think flood fill would work (and I could be wrong) is because it is not always a 4-sided area, and sometimes it would have to go in the + X direction for a while and then go in the - X direction. Of course I could just not know how to implement the flood fill correctly and that could be the case.

for a refresher on the jezzball game there is one at jezzball.net

Share this post


Link to post
Share on other sites
Echofiend    100
Quote:
Maybe you could flood-fill out from the balls, and then close anything that wasn't reached? I always wondered how that worked.


wow... I actually had not thought of that. But would I run into problems in the future when I have a lot of balls on the screen?

Share this post


Link to post
Share on other sites
szecs    2990
Flood-fill doesn't necessarily mean the area-painting algorithm. You can go in any directions with any conditions.

For example in a minesweeper game, the zero-field-self-revealing thing can be done with flood-fill. The classic square grid means 8 directions (instead of the 4, used in paint programs). Hexagonal grid means 6 directions (heavily depend on the "shape" of the whole field), and triangular grid means 3 directions (or 12).

The base of the flood-fill algorithm is that there is "branching" inside the recursing function. So you call the recursing function on an arbitrary element inside the function.

I guess that's not clear (just a pseudo example):

void RecursingFloodfill(int x, int y)
{
Do_something_with_element(x,y);

if(some_condition)
RecursingFloodfill(some_x,some_y);
if(other_condition)
RecursingFloodfill(other_x,other_y);
...
...
}
It doesn't have to be position, or the positions don't have to be neighbors etc. In the end, all conditions will fail, so all functions will exit, and recursion finishes.

The beauty of it, that this can fill any arbitrary complex shapes "by itself".
(Drawback is the possibility of stack overflow.)

I certainly hope that has to do something with the OP.

EDIT: you can even:
void RecursingFloodfill(int x, int y)
{
if(Some_important_condition)
return;

Do_something_with_element(x,y);

if(some_condition)
RecursingFloodfill(some_x,some_y);
if(other_condition)
RecursingFloodfill(other_x,other_y);
...
...
}
So you can return "immediately" from recursion. For example if you find something on the field.

Share this post


Link to post
Share on other sites
Echofiend    100
it certainly gives me somewhere to go from, thanks. I guess I just need to work on my recursing function ability(still kind of noob-ish)

But a quick question, you said when it gets to the end, it will fail and all others will fail with it, is that always true? or if it finds all of the areas and does not find a ball it should pass correct?

Share this post


Link to post
Share on other sites
szecs    2990
Sorry, I don't know about the jezz stuff.

But with this method, you have to mark the elements, that have been checked (recursed) already (and don't check them again->put it into the condition). I forgot to tell that, it's very important, otherwise the recursion can never return.

You see, all possible elements will be checked some time, so recursion ends.

Share this post


Link to post
Share on other sites
Zahlman    1682
Of course, when you're really "filling" with flood-fill, you just fill as you go, and use that as your marking. :) Naturally it's a little different if for example you're trying to find all connected blocks of a given colour, check if there are more than a certain amount, and remove them if so (i.e. typical logic for falling/rearranging block type games).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this