I'm making a standalone bound game. I've been thinking about how to detect if a level is solvable for a while. What I mean by that is that you can consider a bound solvable if you can reach the other side (your end location).

Right now, I've come up with some sort of math that defines where a player could be. If I know where someone is at a certain time, then I can start to compute the area that the player could be in after a certain amount of time. Where explosions are located, I remove from the area. That area keeps growing over time (growth speed is defined by the player movement speed) and if it grows to reach the end, then the level is solvable. Hopefully that makes sense. The problem is that coding something like that is pretty complicated.

I'm interested to know if you guys have other ideas for the way I could tackle the problem.

Edit: Bonus point if your solution allows you to rate a level with a difficulty rating. (A good rating system would probably not have any upper limit.)

Personally, I consider a level harder if:

• the solution requires many steps
  
• the window of action is really small
  
• the explosions are really obfuscated and it's hard to notice the pattern (That's probably really abstract though.)
  

Post has been edited 2 time(s), last time on May 1 2017, 4:48 pm by Apos.

This sounds like a fun problem to solve

I will try to think of a way to approach it, but in the meantime: don't forget to take into account zergling turn-rate and other similar nuances (if there are any others O_O)

In my game, there is no turn-rate. The speed is always constant.

If I understand correctly, your scenario is as follows: you allow users to submit custom-made obstacles for other people to play, but you don't want people submitting impossible obstacles. Therefore you need to determine if the obstacle is possible before it is published.

There's actually a really simple way around this problem: before you're allowed to publish your obstacle, you have to beat it once. This is the way Super Mario Maker, for example, handles user-submitted content. Now, this limits creators to submitting only what they're capable of beating, which may or may not be an ideal solution. You could allow the creator to play at a reduced speed (say, 0.5x normal speed) for the purposes of proving that the obstacle is possible without requiring the creator to be nearly as skilled as the players the obstacle would be designed for.

Super Mario Maker doesn't have a difficulty rating, but instead has completion rates, from which difficulty can be assumed as players attempt the obstacle (e.g., a level with a 0.48% completion rate is probably harder than one with a 51.40% completion rate). And of course it uses user ratings to figure out which levels are well-received.

This seems like the most straight-forward approach. Rather than every possible location a player could be, you would want to figure out every useful location a player could be, which would be at the edge of an area where an explosion could occur. You may have to include both outer and inner edges for the sake of "safe spots" (walkable areas/gaps in the obstacle).

It may seem complicated, but it's actually (fortunately) able to be represented by something very familiar: you have a graph where each node is a possible move on a given sequence of the obstacle. You can build the graph in an iterative process until you either find a move that reaches the end, or all the moves have already been mapped to the given sequence. At the moment I'm not sure how I'd apply weight between each node, so I'd just assume equal weight and just grind it all out.

So really, you need two algorithms:

1) Find each useful edge for all existing explosion areas
2) While new moves are discovered and the end hasn't been reached, find possible useful moves for the current sequence and continue to the next sequence

Conceptually I'm describing a breadth-first search, but you could also go depth-first if you think it makes more sense, using a Stack for the current step and popping whenever you reach a dead-end or duplicate node (remember that a node's uniqueness pertains not only to the location but also the obstacle sequence).

Oh man! my brain just exploded. You pretty much nailed it, the reason I don't want to force people to be able to beat their own levels is because I don't want to restrict people to their own skills (thought letting them play it at a reduced speed is a clever alternative). Also, eventually, it would make sense to have AIs play the game.

Having a rating based on the percentage of how many people beat a level is pretty smart.

I managed to model the problem in 3D.





A single start point looks like a cone when seen over a certain amount of time.

Edit: There's an other reason I want that. Eventually, there's a point where I need to make hundreds of levels. If I want all the levels to be high quality, I need to make sure that levels aren't runnable. Also, sometimes it's fine where there are many solutions, but sometimes the alternate solution is boring. Instead of brute testing each one thousand of times, it would be nice if the game showed me the solutions right away.

Can the explosions be at any possible (x,y) coordinate, or are they on a grid? If you could find a way to discretize (or whatever--I'm not sure if that's the right word) their positions in to cells, you could instead check reachable cells using the minimum timestep between explosions and this would greatly reduce the complexity of the problem.

... Except rereading what Roy said, he seems to be suggesting to generate such cells in way so that they are not locked to a definite grid (in algorithm #1) which is definitely more versatile xD. But if the explosions are regularly positioned, using a predefined grid may be easier.


Also measuring the difficulty wouldn't be too hard using Roy's method... you could probably take the minimum/average reaction time of each of the steps (something like the time until the next explosion minus how long it takes the unit to move to the next safe spot, giving the maximum amount of time before the command needs to be safely issued), and counting the steps would be trivial. I'm not sure how to take in to consideration the complexity of crazy patterns, though ... Unless you were to measure things like changes in angle and distances between commands xD (if you have to just step forward in a line after each explosion, that's not complex or difficult. But if you have to zig-zag back and forth, or go in all sorts of crazy directions, then that's probably difficult)
Also in your post you mention obfuscated patterns, you could count the number of failed paths ... if there are lots of dead ends to otherwise potentially passable paths (i.e., you can follow a safe path, but then it stops being safe), that could be indicative of something.

Post has been edited 6 time(s), last time on May 4 2017, 6:08 am by FaRTy1billion.

If you discretize the game like Farty said, there's a pretty simple solution you can try.

Let's say your playable area is a NxM grid represented as a matrix, and you treat any place a player can be as 1 and any place they can't be as 0:

1) Perform a 2D-Convolution on the grid, where your convolution kernel is a KxK matrix of a circle. (Pixels in circle are 1, the player's speed and game's resolution determines how large K is.)
2) Clip all values in the grid to at most 1.
3) Mask away the game's boundaries and any bound "explosion."
4) Iterate until at least one pixel in the end area is 1.

This should process fairly quickly, is easy to prototype, and should give you a pretty good estimate of the answer.

The main problem with this solution is if your kernel is too large, it will allow the player to jump around corners or over thin walls, but this is also a problem with the diagram you animated above. It could be mitigated or removed entirely with a smaller kernel size or finer-grain resolution. If you want to animate the problem I'm talking about for yourself, move the player's starting position to a corner close to the bound's beginning:

XXXXXXX
X_____X
X_____XXXX
X
X_____XXXX
X____OX
XXXXXXX

Post has been edited 1 time(s), last time on May 4 2017, 6:50 am by Lethal_Illusion.

This is an awesome read. I am not good a math but hell, I am looking forward to your outcome.

I wrote up a quick proof-of-concept in Matlab.
* bound.m: matlab code that solves a given bound
* bound.gif: gif generated by running bound.m

Light-gray is the playable area, and black is the border. The expanding white area is all possible positions the player could occupy for a given frame. The dark-gray is the obstacle, eg. an explosion in a bound map.

Let me know what you think.

Attachments:

that gif is really fun to watch xD

Wow, that's some really nice imdilate() magic! I was considering doing it like that (using bitmap). This simplifies the algorithm really well.

I'm guessing there could be errors around corners, or if it was possible to make a very thin wall?

Edit: Here is a classic one:



Before you posted this code, I was using Gimp's selection tools. You can select and grow a selection.

Edit2: Here is a wall jump glitch test. For my imdilate() implementation, I'll need to code something that will be more accurate.



Post has been edited 2 time(s), last time on May 7 2017, 9:52 pm by Apos.

So it turns out that it's pretty slow to run this in game. The algorithm is pretty expensive. I might be able to use the pathfinding data to only compute the frames before and after an explosion.

Yeah, thin walls and corners are one problem with this approach, and I mentioned something similar in my first post. I thought of a few hackish solutions, but nothing too elegant or fast.

Also, I wouldn't expect it to run too slowly for you. What's your game's resolution? Are you using a library to do convolution (or imdilate), or did you make a convolution yourself?

If you want it to run much faster, you can try to blur with a gaussian filter, and accept any value above a threshold. Since guassian kernels are rank 1, they can be separated into an X-convolution and Y-convolution, which will run much faster. In Matlab, it would look something like:
1) K = fspecial('gaussian', [1 speed*2+1]); % Generate 1D gaussian kernel
2) areaX = imfilter(area, K)'; % Apply 1D convolution along X and transpose result
2) areaXY = imfilter(areaX, K)'; % Apply 1D convolution along X (previously Y) and transpose result
3) area = areaXY > THRESHOLD; % Binarize with threshold

Also, I might have the order backwards: it might be faster in Matlab to convolve twice along Y. I'll try it later this week if you haven't by then.

I'm new to the concept of a convolution matrix. It's very interesting to read about it. For now, I just coded my own thing quickly. I'm not using walls or obstacles yet. I just hard-coded a temporary movement matrix. I based my code on this: http://angeljohnsy.blogspot.com/2012/09/image-dilation-without-using-imdilate.html

    class BitmapSolver
    {
        /**
         * Goal: Using bitmap image dilation operation, we can solve a level.
        **/

        int[,] area;
        int[,] walls;
        List<int[,]> obstacles;
        int[,] movement;

        public BitmapSolver(Level l, int width, int height) {
            int tileWidth = l.getTerrain().GetLength(0);
            int tileHeight = l.getTerrain().GetLength(1);

            //New arrays in C# are always filled with 0s.
            area = new int[tileWidth * width, tileHeight * height];
            walls = new int[tileWidth * width, tileHeight * height];

            area[l.start.X * width, l.start.Y * height] = 1;

            movement = new int[,] {
                {0, 0, 0, 1, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 1, 1, 0},
                {1, 1, 1, 1, 1, 1, 1},
                {0, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 1, 1, 0},
                {0, 0, 0, 1, 0, 0, 0}
            };
        }
        public void Update() {
            area = dilateArray(area, movement);
        }
        public int[,] dilateArray(int[,] a, int[,] b) {
            int[,] d = new int[a.GetLength(0), a.GetLength(1)];

            int[,] aPad = padArray(a, b.GetLength(0) / 2, b.GetLength(1) / 2);

            for (int i = 0; i < a.GetLength(0); i++) {
                for (int j = 0; j < a.GetLength(1); j++) {
                    d[i, j] = logicalAND(selectArrayPart(aPad, i, j, b.GetLength(0), b.GetLength(1)), b);
                }
            }

            return d;
        }
        public int[,] padArray(int[,] a, int paddingX, int paddingY) {
            int[,] b = new int[a.GetLength(0) + paddingX * 2, a.GetLength(1) + paddingY * 2];
            for (int i = 0; i < a.GetLength(0); i++) {
                for (int j = 0; j < a.GetLength(1); j++) {
                    b[i + paddingX, j + paddingY] = a[i, j];
                }
            }

            return b;
        }
        public int logicalAND(int[,] a, int[,] b) {
            if (a.GetLength(0) != b.GetLength(0) || a.GetLength(1) != b.GetLength(1)) {
                //ERROR
                Console.WriteLine("Error");
                return 0;
            }
            for (int i = 0; i < a.GetLength(0); i++) {
                for (int j = 0; j < a.GetLength(1); j++) {

                    int c = a[i, j] == 1 && b[i, j] == 1 ? 1 : 0;

                    if (c == 1) {
                        return 1;
                    }
                }
            }

            return 0;
        }
        public int[,] selectArrayPart(int[,] a, int x, int y, int width, int height) {
            int[,] b = new int[width, height];

            for (int i = x; i < x + width; i++) {
                for (int j = y; j < y + height; j++) {
                    b[i - x, j - y] = a[i, j];
                }
            }

            return b;
        }
        public Texture2D createTexture(GraphicsDevice g, int width, int height) {
            SpriteBatch s = new SpriteBatch(g);

            RenderTarget2D renderTarget = new RenderTarget2D(g, area.GetLength(0), area.GetLength(1));
            g.SetRenderTarget(renderTarget);

            g.Clear(Color.Transparent);

            s.Begin();

            for (int i = 0; i < area.GetLength(0); i++) {
                for (int j = 0; j < area.GetLength(1); j++) {
                    if (area[i, j] == 0) {
                        s.FillRectangle(new RectangleF(i, j, 1, 1), Color.Black * 0.5f);
                    } else {
                        s.FillRectangle(new RectangleF(i, j, 1, 1), Color.White);
                    }
                }
            }

            s.End();

            g.SetRenderTarget(null);

            return renderTarget;
        }
    }

Edit: The in game size for a single tile is 100px (pretty much). A lot of levels are around 1400x600px.

Post has been edited 1 time(s), last time on May 9 2017, 6:42 pm by Apos.

Changing imdilate to conv2 had a 3-4x speedup, and changing it to two 1D convolutions had a 13x speedup. How long does it take to compute a single frame in your game? I think if you optimize a 1D convolution function and try reusing buffers, it should compute fairly quickly.

I've attached the updated code which operates on a higher-resolution area and the gif it produces.

Attachments:

If I don't run the solver, the game runs at 3000 FPS, or ~0.3 milliseconds per frame.

If I call the Update() function, I drop below 1 FPS. I started optimizing, but instead I'll do what you said above.

I'm not actually sure how to adjust the speed in the new version. Smaller values seem to break the "circle". Higher values don't really seem to go faster. I've been playing with the sigma from:

fspecial('gaussian', [1, speed*2+1]', sigma);

and lower values seems to help with lower speed.

Also, how did you pick '1e-16' as the threshold?

That was a little bit of a rush job, so 1e-16 was just a random number that worked for me after trying a few. You might able to get more flexible results with something like:
movement = fspecial('gaussian', [1, speed*2+1]', 2);
THRESHOLD = movement(1) * movement(speed+1);

Let me know if that doesn't work, and I'll try to upload a better version of the code tomorrow.

As far as I can tell, it's pretty hard to get a reliable result. sigma is what controls the blur amount. Higher sigma means more blur. The movement matrix (vector?) is what controls how big of an area is affected. If sigma is too big for the "movement" matrix, it does clipping and the blur looks bad (and is hard to use since information is lost?).

In this context, from what I understand, the speed should become the sigma value. But maybe I'm doing something wrong.

I'm exploring the clipper library: http://www.angusj.com/delphi/clipper.php

Perhaps I'll be able to work with only the border lines instead of the whole area's shape. It's a polygon clipping and offsetting library. (The offsetting is what grows the shape.)

Okay, so I have a new way of solving this problem based on the image dilate, 1D gaussian function. As far as I can tell, this should be super fast.

With the Sagitta circle formula (http://www.mathopenref.com/sagitta.html), I can turn a circle into a 1d array. Essentially, given a point, I can compute a circle's half length vertically.



In this case, my circle has a radius of 5 (speed of 5). The array has a size of 5 * 2 + 1 -> 11.

In a first pass, loop through an array the same size as the level and set the numbers down.

In a second pass, loop through the array again and a cell lights up if it's within the range of those numbers horizontally. No need to look further than the radius' size.



Anyway, this is sort of a bad explanation (I might have skipped a step), but it will most-likely work.

Edit: I can confirm that this code works. I get some really nice circles. My implementation is still really slow though, I wonder how Matlab manages to have really fast convolution matrix code even with really big kernels. I wonder if they do their computations on the GPU.

Post has been edited 2 time(s), last time on May 18 2017, 4:54 am by Apos.