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