A number of puzzle games around the 00s had mechanics based around manipulating streams of objects towards sinks on a grid map, with the level being passed when a certain number of objects had been successfully. For the sake of explanation I'll talk about 1999's Star Wars: Pit Droids, but there were others that were functionally very similar.
Specifically, a level had the following elements and behaviours, played on a grid, either square or hex:
- sources (in PD's case, "launchers") that emit a stream of objects (droids) in a particular direction. The objects continue travelling in the given direction "until told otherwise," at a fixed velocity, in lockstep with all others. More on that in a moment.
- Sinks (holes) which will capture a droid that walks over them, removing it from the level. The level is passed once a certain number (in PD's case, often 48) droids successfully reach a sink that accepts them.
- The player's interaction comes from placing arrows into the level, which will then make a droid that walks over them change to the indicated direction. (There are no "relative turn" arrows, all three/five incoming directions will direct them the same way.) The level designer may also have placed pre-existing fixed arrows. The player's "inventory" of freely usable arrows is also finite - a level designer might give the player say, exactly 2 arrows to place. However, placed arrows can be rotated freely. Two arrows cannot be placed on the same grid space.
- the droids have attributes - in Pit Droids' case, the droids can carry tools, and can have their heads and bodies (separately) painted different colours.
- There are "transformer" elements that set the attributes of the droids that walk through them, and "barrier" elements that block droids that do not have the appropriate attribute from passing. Transformers can similarly be placed from the player's inventory or be fixed at level design time - the former can be freely placed, but their effect on the droid's attributes cannot be modified. Both types are omnidirectional.
- Arrows and holes can also be filtered by attribute - droids of the appropriate attribute will be directed/captured, others will carry on unaffected. As with transformers, what attributes a filtered arrow detects can't be changed, only its location and facing.
- Holes and arrows can also be stateful, affecting either the first N droids that pass over them and then becoming inert, or affecting N droids followed by having no effect on the next M droids, then affecting the next N and so on. (There can only be a single on-off ratio, not an arbitrary pattern)
- there are also "keys" and "locks" - locks are all impassable until all the keys have been walked over at least once, not necessarily by the same droid as walking over the lock.
- the stream of droids coming out of a given launcher could have defined values for a given attribute (all red, say), a repeating sequence (green, blue, green, etc) or randomly chosen from a set. The total number emitted can be finite or unbounded.
- the stream of droids is not necessarily dense - a launcher can leave gaps of any size (or pattern) in the stream, i.e. a launcher can leave a gap of a single "tick" between every two droids it produces, which means two such streams can zipper-merge together if they both converge on the same grid space and they are arranged to be out of phase with each other.
- If a droid tries to move into a blocked space (impassible terrain, another droid, a closed barrier, a launcher, not an inactive hole) it either stops until the way is clear, or is destroyed, at the level designer's option. Barriers close immediately after an appropriate droid passes them, and cannot be "tailgated" by a droid with an incorrect attribute even in the former case. This means that the zipper-merge from earlier with the two streams in phase either successfully creates a stream with no gaps, or destroys both streams, at the designer's choice.
As an example, here is a Pit Droids screenshot from IMDB:
The inventory we're given is four arrows, one of each colour, and it's evident we need to use the four arrows to filter droids by their colour to the appropriate hole.
There is a Let's Play here as well.
I know that, you know that, but my question is, if I wanted a computer to know that and solve that setup algorithmically, how do I represent it? Brute-forcing the puzzle by trying every arrow in every position is just about feasible for a scenario this simple if we know to only try positions along the launcher's path, but quickly becomes infeasible - the possibilities explode as soon as there are two turns involved, let alone more complex situations. A puzzle like the one in the screenshot appears simple enough that it should be deducible, with little if any backtracking.
My feeling is that there's some sense in which this is a graph problem, because we only care about "nodes" where there is some puzzle element, and the exact distances (and times) between things are irrelevant, but I don't know how to then incorporate the "paths" of the droids having different attributes, especially in the context where multiple streams might cross over each other. (i.e. the graph must be planar except sometimes.) The constraint that two arrows cannot be placed on the same space is also hard to model in this view, and (IIRC) several of the game's puzzles exploit that particular issue for their difficulty.
I also suspect that given arbitrary grid space and arbitrary number of possibilities for each attribute, one could construct a constraint-solving problem that's established as somehow difficult, like being NP-hard, but I haven't been able to prove anything in that regard. There's a level that does something in this regard in this video.
Can anyone offer insight about this sort of problem might be represented for better analysis?