Jezz sectioning algorithm
Author
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.
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.
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.
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.
Author
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
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
Maybe you could flood-fill out from the balls, and then close anything that wasn't reached? I always wondered how that worked.
Author
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?
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):
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:
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); ... ...}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); ... ...}
Author
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?
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?
Author
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement