The main challenge in writing a solver (apart from replicating the physics of the game precisely) is the size of the search space.
If you ignore level escapes it is not too bad. When checking for collisions the game considers only 128 possible orientations for the helirin and only checks at 1 pixel accuracy which makes it just about feasible to use A* and treat each pixel at each orientation in the maze as one A* node. You can implement a simple cost function for the A* algorithm which would be the shortest distance to the exit. For better performance I ran an initial path finding stage that found the distance to the exit from each pixel without crossing any walls by doing a kind of flood fill/dijkstra algorithm.
Even with this reduced search space and a pretty good A* cost function the solver could take hours to find a solution in large maps and required a lot of memory. Adding in the moving obstacles made things a bit slower and could also require the helirin to wait around for them to move out of the way. That meant allowing the path finder to revisit a pixel/orientation in the maze more than once in a given solution, increasing size of the search space significantly. Allowing the helirin to move at all 4 possible speeds (0, 1.5, 2.25, 3) also slows things down but it didn't ever seem to generate any improved solutions anyway.
I did a few optimisations in my solver, including storing 128 separate collision maps, one for each orientation of the helirin. In this way I was able to check if the helirin collided with the maze with a single table lookup instead of having to check all 17 hit points every time. I was also able to store additional information in this collision map such as whether the helirin might have hit a spring or a moving object meaning I could optimise out those checks when they were unnecessary.
Even with those optimisations and writing everything in C the solver still took many hours for some levels. Once wall zips are introduced the problem is compounded and A* becomes much harder to take advantage for a couple of reasons:
1. It's very hard to come up with a useful cost function. Estimating the minimum time it could take to reach the exit from any pixel is hard because now you can possibly move at 7 pixels/frame instead of the normal 3. (In fact, even without wall zips this is a bit of a problem because collisions with walls can give you a speed boost, and springs even more so.)
2. The real problem though, is that you can no longer just use pixel+orientation to represent a particular position in the maze. You also need to consider the bounce velocity. Being at pixel x=123,y=45, orientation=23 and no bounce velocity is no longer the same as being there with some non-zero bounce velocity because the latter may lead on to a position that lets the helirin enter a wall.
It's really only by chance that my solver sometimes discovered wall escapes because it happened to visit particular positions with a non-zero bounce velocity first.
I think making a brute force/A* solver truly understand wall escapes would require finding ways to significantly reduce the search space by calculating which combinations of position+orientation+velocity could potentially lead to wall escapes and collapse down duplicate states as far as possible. Also I think for such a solver to run at any decent speed it probably needs to run on GPU or at least multi-threaded SIMD.
As tempting as it is to try and write a solver to find the 'perfect' solution, it might be more realistic to write some kind of interactive tool that lets you manually guide the path finding algorithm.
I don't really have time to get involved too much anyway, I already wasted enough time messing around with this the first time around! :)
Matt