Coding challenge for coding challenge ppl

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
User avatar
togFox
Party member
Posts: 770
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Coding challenge for coding challenge ppl

Post by togFox »

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. :)
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Coding challenge for coding challenge ppl

Post by pgimeno »

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):
ultimate-random-maze.png
ultimate-random-maze.png (9.91 KiB) Viewed 7668 times

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.
........
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:

Code: Select all

.X......
........
.XXXXXX.
.X....X.
.X....o.
.X....X.
.X..X.X.
.X....X.
.XXXXXX.
........
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.
User avatar
togFox
Party member
Posts: 770
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: Coding challenge for coding challenge ppl

Post by togFox »

> 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?
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: Coding challenge for coding challenge ppl

Post by darkfrei »

(removed, cannot remove)
Last edited by darkfrei on Tue Aug 24, 2021 7:34 am, edited 1 time in total.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
darkfrei
Party member
Posts: 1169
Joined: Sat Feb 08, 2020 11:09 pm

Re: Coding challenge for coding challenge ppl

Post by darkfrei »

togFox wrote: Mon Aug 23, 2021 12:00 pm 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.
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.
togFox wrote: Tue Aug 24, 2021 2:58 am Islands are not acceptable so, again, the floodfill is a part of the requirement.
How about the DLA-clusters? It has ONLY floodfillable tiles, other cannot exist at all.

pgimeno wrote: Mon Aug 23, 2021 10:23 pm Since it was made for mazes, this image has the additional constraint that no 2x2 block of walls is created.
Found (at least) one
Attachments
2021-08-24T09_32_26-ultimate-random-maze.png - paint.net v4.2.1.png
2021-08-24T09_32_26-ultimate-random-maze.png - paint.net v4.2.1.png (11.5 KiB) Viewed 7620 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Coding challenge for coding challenge ppl

Post by pgimeno »

darkfrei wrote: Tue Aug 24, 2021 7:33 am
pgimeno wrote: Mon Aug 23, 2021 10:23 pm Since it was made for mazes, this image has the additional constraint that no 2x2 block of walls is created.
Found (at least) one
White is walls. You've found a 2x2 block of spaces, not of walls.
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Coding challenge for coding challenge ppl

Post by pgimeno »

togFox wrote: Tue Aug 24, 2021 2:58 am 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.
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..
The o has two cells in its Moore neighbourhood, and setting it to X will isolate the cell marked Y.
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?
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.
Post Reply

Who is online

Users browsing this forum: No registered users and 44 guests