Project Description - neelimnovo/LightTheWaySolver GitHub Wiki

Description of the game and its mechanics

Prism: Light the Way is a 2D puzzle game where the objective is to use the light sources (in-game name: Bulboids1) to redirect light on to the receivers (in-game name: Glowbos1). To aid that process, additional items can be used to manipulate the light such as mirrors, T-junctions (in-game name: T-Splitters1), Prisms, Colour Filters and Colour Shifters (in-game name: Cycloids1).

I struggled with some of later levels as they became extremely difficult to solve without doing rough work on a piece of paper (at least for me). Hence I made an app to solve the levels for me (which took much longer than expected). By the time I was done, I wanted to be able to answer the following questions:

  • Can I solve the levels in the game with zero human intervention?
  • How hard would it be?
  • Can I solve the levels in a reasonable amount of time?

Solving mechanics

Solving the level uses a few rules extrapolated from the mechanics of the game. There is a static layout to each level, where the location of walls, empty spots, and light receivers are fixed. The dynamic, interactable objects can NOT be rotated, they can only be placed on the empty spots on the grid. As such, there is a fixed set of permutations of all possible dynamic objects placed on the empty spots of the static layout. The input to the solve function is hence

  • The static 2D grid layout

  • The list of all empty spots on the grid layout

  • A queue of dynamic objects which are placed one by one the on grid, the order of which is follows:

    1. Prisms
    2. Filters
    3. Colour Shifters
    4. Light Sources
    5. T-Junctions
    6. Mirrors

An analysis of the level solving algorithm, its shortcomings, and potential alternative approaches to solving:

Let us denote:

  • the size of the grid as g,

  • the number of empty spots as m

  • the number of interactable objects (referred here on dgoQueue) as n.

This is a recursive function with a base case and a recursive case:

The base case occurs when the dgoQueue is empty, and light projection is done on the level to see if it is solved. This has a cost of c1.

In the recursive case,

  1. We first remove an dynamic object from the dgoQueue (Cost: O(1))

  2. We get a filtered list of valid spots, removing the invalid ones as much as possible (Cost: O(m))

We iterate through the list of valid empty spots, steps 3-7 are part of this loop which occurs m times

  1. If the current empty spot already has a dynamic object, attempt to place it on the next one (Cost: O(1)) (because of the level design, there will always be a valid empty spot to place the dynamic object in) . Otherwise,

  2. Track the light source if it is one (Cost: O(1))

  3. Create a copygrid so dynamic objects can be placed differently on each grid without having to reset them (Cost: O(g))

  4. Create a copyQueue for recursive purposes (Cost: O(n))

  5. Recursively call solveLevel with the same grid, same empty spots (m), but dgoQueue of size n - 1

In essence, the runtime of the solve function is approximately O((g+n)m). To demonstrate with an example,

If we are to distribute 6 dynamic objects amongst 50 empty spots, the number of possible grid permutations are: or approximately

That's over 10 billion permutations, just with 6 dynamic, interactable objects. Some of the levels consist of 10+ objects.

Taking the average based on levels the algorithm has solved so far, the algorithm can do approximately permutations each second on my local machine.

My current method of reducing the permutations is filtering the empty spots to eliminate obviously invalid spots (explained in the filter page). Let us take the example of a level with 30 filtered empty spots for each dynamic object, and 7 dynamic objects. The algorithm in its current state would take 1.6 hours to find a solution, which is unacceptable because some levels are much more complex.

So what possible options do I have to further optimise the solving approach?

  • Look for further abstractions in the solutions of each level (which are rare because of the diverse nature of the solutions).

  • Add human-interaction based solving, where a user will pre-fix the location of some objects (hence reducing the number of iterations by magnitudes of 10 or more for each object pre-fixed).

  • If possible, implement parallelism for the solve function so 2-10 threads can be running concurrently.

  • If possible, somehow port the entire solving algorithm so it can be used by a quantum computing model, because quantum brute-force is much faster.

  • Optimise minor line by line intricacies in the code for the algorithm, so each iteration takes even less time. Of all these steps, step 2, 5 and 6 are particularly costly. Possibly step 2 could be implemented with parallelism to observe a performance benefit. Step 5 could be changed to simply resetting the original grid instead of creating a new one everytime.

Having received partial answers to my original questions, I will probably focus on implementing the first two optimisations such that I can at least obtain the solution for every level.

1 In-game actual names are retrieved from the wikipedia page

⚠️ **GitHub.com Fallback** ⚠️