So, maybe not a quick and easy puzzle, but I think it's a common problem relevant to many genre's.
I have a grid (tiles arranged in [row][col] format) that are say 100 px by 100 px (for example) and a routine that runs on a timer (say 5 minutes) fills in a tile at random. There are no rules where the first few tiles are placed. Completely random.
However, as more tiles get placed and the grid fills up, the algorithm needs to ensure that every filled tile can access (i.e. draw a path) to every other tile without crossing another filled tile. Length/distance doesn't matter. Can not path diagonally.
Put in plain english: think of a city builder where buildings are built on tiles but tiles must be placed in such a way that roads provide access to every other tile so no tile is isolated and cut off from a road.
The initially random placement of the first few tiles dictates the roads are initially unknown and potentially anywhere. As the grid fills, the final permutations for roads is reduced until no more tiles can be filled without breaking the only rule.
I haven't given this much thought yet but I think it's something like counting the neighbours for each neighbouring tiles and then ... ???
Might be a fun challenge for you.
Coding challenge for coding challenge ppl
Coding challenge for coding challenge ppl
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
Re: Coding challenge for coding challenge ppl
I still don't understand. Do you mean that after each new tile is placed, all of the empty tiles should be reachable by one single flood-fill starting on any empty tile?
Once I wrote such a thing as a maze generator in a 320x200 screen. I considered that "the ultimate random maze generator". This was the result (it's toroidal, i.e. it wraps from top to bottom and from left to right; white is walls):
Since it was made for mazes, this image has the additional constraint that no 2x2 block of walls is created. You can't place any more white cells without either creating a 2x2 block, or dividing the black cells into two regions that can't reach each other.
Edit: OK; after re-reading you, I think I get what you mean. I think you mean that every filled tile should have an empty neighbour that is reachable by a flood-fill. A question remains though, should all empty tiles *also* be reachable by a single flood fill? Because if not, islands can happen. Consider this case:
In order for the top-left tile to be reachable, no tile can be placed on the inside. This can be solved by forbidding islands, i.e. requiring also empty tiles to be reachable.
And if that's what you mean, I've also got bad news for you. Something like reachability is not a local phenomenon. It's not possible to determine it just by examining the nearest neighbours. Consider this situation:
Suppose that the o is empty, but you're considering whether to place an X in that place or not. The validity of that placement depends on the presence of each of the Xs that form the rectangle (except the corners). You can't just check the neighbours of the o. I can't imagine how to implement in any other way than flood-filling after each placement (which is what I did in the program that generated the image).
This suggests a board game. Two players place tiles/counters in a grid in turns. The first one who places a tile that makes any tile unreachable, loses. It could be played with a Go board, I guess, but a computer can probably check the losing condition better than humans.
Once I wrote such a thing as a maze generator in a 320x200 screen. I considered that "the ultimate random maze generator". This was the result (it's toroidal, i.e. it wraps from top to bottom and from left to right; white is walls):
Since it was made for mazes, this image has the additional constraint that no 2x2 block of walls is created. You can't place any more white cells without either creating a 2x2 block, or dividing the black cells into two regions that can't reach each other.
Edit: OK; after re-reading you, I think I get what you mean. I think you mean that every filled tile should have an empty neighbour that is reachable by a flood-fill. A question remains though, should all empty tiles *also* be reachable by a single flood fill? Because if not, islands can happen. Consider this case:
Code: Select all
.X......
.XXXXXX.
.X....X.
.X....X.
.X....X.
.X....X.
.X....X.
.X....X.
.XXXXXX.
........
And if that's what you mean, I've also got bad news for you. Something like reachability is not a local phenomenon. It's not possible to determine it just by examining the nearest neighbours. Consider this situation:
Code: Select all
.X......
........
.XXXXXX.
.X....X.
.X....o.
.X....X.
.X..X.X.
.X....X.
.XXXXXX.
........
This suggests a board game. Two players place tiles/counters in a grid in turns. The first one who places a tile that makes any tile unreachable, loses. It could be played with a Go board, I guess, but a computer can probably check the losing condition better than humans.
Re: Coding challenge for coding challenge ppl
> I think you mean that every filled tile should have an empty neighbour that is reachable by a flood-fill.
Yes.
> should all empty tiles *also* be reachable by a single flood fill? Because if not, islands can happen.
Islands are not acceptable so, again, the floodfill is a part of the requirement.
I was thinking (not very long or hard) that a tile can be filled after an initial and 'light' check that at least one neighbour was not filled. This is low processing effort. I was then thinking that a second check, instead of a floodfill, I could execute a 'jumper' (A* path finder) to an origin or fixed point (that was not filled). If the path was found then you're good. If the path was not found then you've likely created an island dead end. This assumes of course there will be some sort of origin to path to. It can also result in 'forks' or dead-end streets (not circuits), which is fine - because the requirement is still satisfied.
Would something like jumper be more processing efficient than a flood fill?
Yes.
> should all empty tiles *also* be reachable by a single flood fill? Because if not, islands can happen.
Islands are not acceptable so, again, the floodfill is a part of the requirement.
I was thinking (not very long or hard) that a tile can be filled after an initial and 'light' check that at least one neighbour was not filled. This is low processing effort. I was then thinking that a second check, instead of a floodfill, I could execute a 'jumper' (A* path finder) to an origin or fixed point (that was not filled). If the path was found then you're good. If the path was not found then you've likely created an island dead end. This assumes of course there will be some sort of origin to path to. It can also result in 'forks' or dead-end streets (not circuits), which is fine - because the requirement is still satisfied.
Would something like jumper be more processing efficient than a flood fill?
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
Re: Coding challenge for coding challenge ppl
(removed, cannot remove)
Last edited by darkfrei on Tue Aug 24, 2021 7:34 am, edited 1 time in total.
Re: Coding challenge for coding challenge ppl
Fill the field with black and magenta tiles. Black is for building, the magenta is for temporary road.
Mark one of middle magenta tiles as white tile.
Add nearest magenta tiles to the queue list.
Take one magenta tile from this list (check if it is not already white), trace the line to the nearest white tile. Set this tile and this line as white.
Add nearest magenta tiles to the queue list.
Repeat until something is in the queue list.
How about the DLA-clusters? It has ONLY floodfillable tiles, other cannot exist at all.
Found (at least) one
Re: Coding challenge for coding challenge ppl
White is walls. You've found a 2x2 block of spaces, not of walls.
Re: Coding challenge for coding challenge ppl
A cell surrounded by at most 1 filled cell can be filled. Yes, that can save time in the beginning, good thinking. I think that if it's surrounded by 2 cells and these 2 cells are contiguous, then it can also be filled. 2 neighbours that are not adjacent to each other do not guarantee that adding a cell will not create an isolation. Consider this:
Code: Select all
XXXX.
X..X.
XY.o.
XXX..
I don't know. In the first stages, maybe, but then the simple neighbourhood rule will also help in these stages. It's quite possible that when the complexity of the shape grows, a flood-fill can outperform it. It may well depend on grid size and algorithm implementation.togFox wrote: ↑Tue Aug 24, 2021 2:58 am I was then thinking that a second check, instead of a floodfill, I could execute a 'jumper' (A* path finder) to an origin or fixed point (that was not filled). If the path was found then you're good. If the path was not found then you've likely created an island dead end. This assumes of course there will be some sort of origin to path to. It can also result in 'forks' or dead-end streets (not circuits), which is fine - because the requirement is still satisfied.
Would something like jumper be more processing efficient than a flood fill?
Who is online
Users browsing this forum: No registered users and 44 guests