• 13
• 27
• 9
• 9
• 20

# Jezz sectioning algorithm

This topic is 2924 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
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 on other sites
Maybe you could flood-fill out from the balls, and then close anything that wasn't reached? I always wondered how that worked.

##### Share on other sites
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 on other sites
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 on other sites
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 on other sites
ahh you sent your edit while I was writing the other one. Thank you, I will see what I can do with the information so far.

##### Share on other sites
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.