Posts for MattShepcar

Joined: 1/9/2019
Posts: 2
Location: UK
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
Post subject: Level escapes
Joined: 1/9/2019
Posts: 2
Location: UK
Hi, interesting progress, especially the improved ice 2 time. I think mohoc's idea about how the wall clip works is mostly right, i.e. it relies on residual velocity from a previous impact. Looking at my implementation of the game physics it would seem to work like this: 1. When you bump a wall the game resets any user movement of the helirin BUT it does not reset any movement caused by residual velocity from a previous collision. This is the bug that makes it possible. 2. It then moves the helirin by 2 pixels along its axis in the direction away from the end that collided. This 2 pixel thrust velocity is saved and on each subsequent frame it is reduced by 25% and applied again. This is the velocity that must be used to enter a wall. 3. The final ingredient that allows the 'wall zips' and level escapes is that if the centre point of the helirin is in collision then a 4 pixel thrust in the opposite direction to the current user input is applied. I guess this was probably an attempt to prevent level escapes but in fact does the opposite. It essentially allows you to move at 7 pixels per frame along walls because the 4 pixel thrust is applied not only on the current frame but also on the next frame at 75% power as described in step 2 above. 4. If you're playing kururin paradise then the game resets the integer parts of the X & Y position back to their values from the previous frame making level escapes and wall zips impossible (they patched the bug, but did not fix the real cause!) The important thing is to ensure that the 2 pixel correction in step 2 does not push the helirin back out of the wall and counteract the residual velocity from the previous collision. This is why the helirin needs to be at more or less the same angle as the wall you are trying to enter. It's also vitally important to get the centre of the helirin inside the wall to give you control over the 4 pixel thrust, again making it important that the helirin is aligned with the wall. My solver did not properly account for level escapes or wall zips because I didn't really understand what the mechanism was until now. The code is a real mess too. I might try and tidy up the part that deals with the game physics so it could be used to write a new solver that can properly understand wall clips although that could be quite a tough challenge. I look forward to seeing what you guys come up with in the meantime. Matt