0
\$\begingroup\$

I have to create an algorithm which will fill a board, which is made of square cells, with elements. Board can have different sizes and it doesn't have to be a square. Elements fall from top to bottom. Spots where elements are spawned are predefined, but that doesn't matter in my question, so we can focus on a simple square board where elements spawn at the top.

Board can have special cells, including "blocked" and "slide". Blocked cell is a cell which cannot be filled with an object nor an object can pass through it. Slide cell is a cell which cannot be filled with an object, but objects can pass through it.

I've created plenty of algorithms which handle board, including hexagon cells, but this slide cell is giving me a hard time.

Before I start to dwell on the subject, here's an example on how the cells will work. Red cells are blocked, yellow cells are slides.

board fill

Elements can fall straight down and diagonally left or right. Element A can only move diagonally if in the column it will fall to, no other element is falling down or there's an Element B falling down, but a blocked cell exists between A & B -> like brown and grey elements in my animation.

To make things simpler, let's skip definition of the diagonal movement priority algorithm and just assume we are processing rows from left to right and if an element can move diagonally to the right, it will fall right, if it cannot it will try to fall to the left. It's irrelevant to the problem.

As I mentioned, the part that make things tricky are the slides. Elements falling through a slide cell, fall at the same speed as through regular cells. So if there're 3 slide cells - one over another - element will fall through them with the same duration as another element through 3 regular cells. Since slide cells cannot be filled with elements, I have to know exactly how many elements must fall through the slides.

Elements which fall through slides behave like other elements, and don't "wait" in front of a slide. This means I cannot fill the board below slides first, calculate how many cells are empty and try to fill them through slide, because some of the cells would be filled with elements coming from other paths (in my example, green and grey elements would fill some of the cells which should contain purple elements).

Since this is a game, some of the elements can be removed by the user and will have to be filled with existing elements + new ones. Let's imagine a scenario where all of the purple elements are removed below slides. Some of the cells which were filled with purple elements, will now be filled with green and grey elements. Only 7 cells will be filled with purple elements.

after removal of purples

And now the final question. What would be the best algorithm to handle the board fill?

Some additional things:

  • assume there's a function canFall(cellA, cellB) which returns true/false indicating if element can fall from cellA to cellB.
  • assume there's a function isSlide(cell) which returns true/false indicating if cell is a slide or not

Some weird scenarios I've tried and failed:

  • Virtually filling the board treating slide cells as regular cells, counting how many elements could fall through the slide and then during animated fill making the slide cells only pass as many elements as I have counted. Unfortunately, when slide cells are blocked, it means elements can start to fall diagonally so the board will be filled in a different way then during virtual fill.
  • Virtually filling the board by falling down only a single row of elements [actually lowest element of a column]. Once all of the elements cannot be moved elsewhere - take another set of elements [again only one per column]. This allowed me to check any possible route through slides [because there can be blocks of 3x3 slide cells, and elements can fall diagonally through slides]. Unfortunately, even though quite sophisticated, this algorithm caused clashes of two elements on a single cells, because when an element is falling, it doesn't know the route of other elements. I might try a variation and add routes to the algorithm, but it's already insanely complex.

I've dealt with this for so long, my mind is probably wrapped around some ways of dealing with this and I cannot see anything else. I'm open for suggestions, hints or existing algorithms.

Thanks, Krystian

\$\endgroup\$
  • \$\begingroup\$ Have you tried a backtracking algorithm for your virtual fill step? Fill as normal, and then if you find an item gets stuck in a slide, rewind to the step before that item entered the slide and have it treat the entrance as blocked instead, then continue the sim from there. This might still have a problem if slides can be arranged in a contradictory manner (so that if the slide is marked as blocked, the other items flow a different way so that the area below the slide never fills to the blocking point), but in such a case I think the best we can do is flag the level insolvable. \$\endgroup\$ – DMGregory Jul 10 '15 at 13:18
  • \$\begingroup\$ @DMGregory thanks for your comment. I've tried some of the usual algorithms I use for grid based games, and unfortunately had to cross it off. I've had scenarios which caused problems on very simple levels with 2 sets of slides when user removed some of the elements from board and the board had to be filled again :( \$\endgroup\$ – Krystian Jul 10 '15 at 14:16
  • \$\begingroup\$ Can you define what those problems were? From your comment, I can't identify a specific case where a suitable backtracking algorithm would go wrong, so I can't offer any improvements to fix the problem. \$\endgroup\$ – DMGregory Jul 10 '15 at 14:54
  • \$\begingroup\$ @DMGregory sorry about that. I did a backtracking algo before but it only involced the paths that actually had slides in them. I deemed stepping back on all paths as too time and resource consuming, however later on I've tried more complex solutions and never got back to this idea. I'll try that now. Thanks for pointing it out. \$\endgroup\$ – Krystian Jul 12 '15 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.