|
|
Post by Jackattack on Jan 6, 2021 22:32:49 GMT -5
A bot tthat cann beat levels on its first try?
How it would work
1. Fisrt It wouldd find all objects with hitboxes. Then it places them on a new level. It then runs thriugh senerios on ehere it needs to jump based on the physics of gd. All of this happens when you are loadingthe level
2. With all of the senerios done, the one that works has a click petern made. Then it tests this click pattern. This still hapens when you are loading the level.
3. It executes the click pattern
Pros:
Could be a way to see if levels are really impossible
way to show case levels
Cons:
Longer loadinging time because of the calculations it has to make
May not work on levels with spikes inside the blocks
|
|
|
|
Post by Bagley on Jan 7, 2021 3:58:54 GMT -5
Is it theoretically possible? Yes, here is a very impractical solution with a very weak upper bound (worst case is O(2^n) respective to the length of the level, average case is a bit more complicated, and I don't feel like calculating it, especially since the list of all possible click patterns that work on a GD level is likely not a random sample of all 2^n click patterns, but have some regularity to them).
First fix the refresh rate that you want to test (say 60 hz), because some levels could be possible on one refresh rate and impossible on another. Now, we're going to be using a depth first search, rather than breadth first, because there might be more than one way to pass a part in a level that need not be calculated every time up to the next reset point, and once you've found a path to a reset point, there's no need to look for another one. We're not trying to figure out what the humanly "easiest" path is, we only care about finding one path that exists.
Now, at the end of any frame (in this case 1/60 of a second), the mouse button can either be pressed (1) or not pressed (0). For this exercise we can ignore 2 player levels that require both mouse and spacebar, but it should be easy to see how to expand the following method to those levels. Let's say for the sake of the argument that we are analyzing a 10 second long level (so 600 total frames of input). Then we have 2^600 possible click patterns, although this number can be greatly reduced. We represent a possible click pattern by a binary string, for example, the string 00000000111100011111 represents the click pattern where we keep the button released for 8 frames, hold for 4 frames, release for 3 frames, and hold for 5 frames to finish the level (of course this string would be 600 digits long for our level). We will use the letter X as a placeholder that can mean 0 or 1.
Now the first click pattern we will test is 0X..., which means that we release for frame 1, and see if we die on frame 2. If we do die, what does that tell us? It means that we HAVE to hold on the first frame, or else we die. So try 1X..., which means that we hold for frame 1 and see if we die on frame 2. If we die on BOTH patterns, then the level is impossible - there is no way to pass frame 2. However, suppose that for at least one of them, we do NOT die (if we don't die on either, we prioritize a 0 over a 1). Then we continue that process by searching further, for example, suppose that 0X... works. Then try 00X... (release for frame 1 and 2) and 01X... (release for frame 1, hold for frame 2), and test each of these to see if we die on frame 3. If either (or both) work, continue. If neither work, then try 10X... and 11X..., unless 1X... was previously found not to work, in which case the level is impossible as before. Eventually, by frame 600 (or however many frames we are dealing with), we will find a path for any possible level. Interestingly, the resulting binary string is the smallest (as when converted to decimal) possible click pattern that will work for that level.
I'm sure there are some optimizations that you could make to this algorithm, but the purpose was to prove that such an algorithm exists, and I believe that I have done so.
|
|
|
|
Post by Despey on Jan 11, 2021 12:42:12 GMT -5
We could call this Zbot. I can code. Lemme get a carbon copy started.
|
|
|
|
Post by Jackattack on Jan 12, 2021 21:58:05 GMT -5
More:
I got inspired by pizza bot
anyways, I thought about this more. Lets use stero maddness and back on track as our example.
In the begining, there is this: /\ /\/\
This program.knows that you can jump over this: /\/\/\ so it times it will jump like this: ^ /\ ^/\/\ (^ is a jump) that way treating every spike as a triple. Ship is more complex though
stero madness ship:
| | [] \/\/\/\/\/\/\/\/[]
| |
[]
[]
| |
| | []/\/\/\/\/\/\/\[]
(or something)
Based on how mush space iss betwen the obsicles, it will either
1) strightfly.
or
2) go up and down
like this
for the part is stero maddness like this,
[]\/\/\/\/\/[]
[]/\/\/\/\/\[]
ot would know that they aare far apart and try and stright fly. likee thiss
[]\/\/\/\/\/[]
- - - - - - - - - - -
[]/\/\/\/\/\[]
(- is the ships path.)
but in back on track you cant do that. It would figure out this and do the up/down option.
[] []
[] [] /----------------------
[][][][] / [][][][]
---------/ [] []
[] []
(- and/ is the ships path)
TAHNK you for reading and engoying my amazing art. (sory about any miss spelling)
|
|
|
|
Post by Jackattack on Jan 12, 2021 21:58:51 GMT -5
LOL that didnt format right
ehhhhhhh illI'll just fix it tommoro
|
|
|
|
Post by Despey on Jan 13, 2021 8:13:24 GMT -5
I can add this in *pushes glasses up to face* lol
|
|
|
|
Post by Jackattack on Jan 13, 2021 21:49:52 GMT -5
gosh It looked soooo good when I was writing it. what do you mean?
|
|
|
|
Post by Jackattack on Jan 14, 2021 23:01:39 GMT -5
I can add this in *pushes glasses up to face* lol wait are you axtualy writing a program? if so lets have it beat sonic wave as our test level |
|
|
|
Post by Despey on Jan 15, 2021 8:51:33 GMT -5
gosh It looked soooo good when I was writing it. what do you mean? I can add this in *pushes glasses up to face* lol wait are you axtualy writing a program? if so lets have it beat sonic wave as our test level Sure thing. |
|
|
|
Post by Despey on Jan 15, 2021 8:52:34 GMT -5
gosh It looked soooo good when I was writing it. what do you mean? I can add this in *pushes glasses up to face* lol wait are you axtualy writing a program? if so lets have it beat sonic wave as our test level Also i made it have built in fps bypass just in case it need different fps. |
|
|
|
Post by Jackattack on Jan 15, 2021 23:48:06 GMT -5
that could be useful
|
|
|
|
Post by TheSynner on Jan 17, 2021 12:15:59 GMT -5
Is it theoretically possible? Yes, here is a very impractical solution with a very weak upper bound (worst case is O(2^n) respective to the length of the level, average case is a bit more complicated, and I don't feel like calculating it, especially since the list of all possible click patterns that work on a GD level is likely not a random sample of all 2^n click patterns, but have some regularity to them). First fix the refresh rate that you want to test (say 60 hz), because some levels could be possible on one refresh rate and impossible on another. Now, we're going to be using a depth first search, rather than breadth first, because there might be more than one way to pass a part in a level that need not be calculated every time up to the next reset point, and once you've found a path to a reset point, there's no need to look for another one. We're not trying to figure out what the humanly "easiest" path is, we only care about finding one path that exists. Now, at the end of any frame (in this case 1/60 of a second), the mouse button can either be pressed (1) or not pressed (0). For this exercise we can ignore 2 player levels that require both mouse and spacebar, but it should be easy to see how to expand the following method to those levels. Let's say for the sake of the argument that we are analyzing a 10 second long level (so 600 total frames of input). Then we have 2^600 possible click patterns, although this number can be greatly reduced. We represent a possible click pattern by a binary string, for example, the string 00000000111100011111 represents the click pattern where we keep the button released for 8 frames, hold for 4 frames, release for 3 frames, and hold for 5 frames to finish the level (of course this string would be 600 digits long for our level). We will use the letter X as a placeholder that can mean 0 or 1. Now the first click pattern we will test is 0X..., which means that we release for frame 1, and see if we die on frame 2. If we do die, what does that tell us? It means that we HAVE to hold on the first frame, or else we die. So try 1X..., which means that we hold for frame 1 and see if we die on frame 2. If we die on BOTH patterns, then the level is impossible - there is no way to pass frame 2. However, suppose that for at least one of them, we do NOT die (if we don't die on either, we prioritize a 0 over a 1). Then we continue that process by searching further, for example, suppose that 0X... works. Then try 00X... (release for frame 1 and 2) and 01X... (release for frame 1, hold for frame 2), and test each of these to see if we die on frame 3. If either (or both) work, continue. If neither work, then try 10X... and 11X..., unless 1X... was previously found not to work, in which case the level is impossible as before. Eventually, by frame 600 (or however many frames we are dealing with), we will find a path for any possible level. Interestingly, the resulting binary string is the smallest (as when converted to decimal) possible click pattern that will work for that level. I'm sure there are some optimizations that you could make to this algorithm, but the purpose was to prove that such an algorithm exists, and I believe that I have done so. Some comments ig: Regarding the DFS/BFS part (if I've understood it correctly): I suppose this is just a heuristic and it doesn't reduce the worst-case complexity of the algorithm (i.e., using DFS instead of BFS), so it doesn't really matter which one you use if you just want to show the problem is theoretically solvable, but it probably helps a lot to use DFS for most types of levels indeed. Also, what do you mean by "humanly easiest path"? Is it a path wherein there are as few 0's as possible (i.e., wherein we click as little as possible)? Is that why, below, you chose to prioritise a 0 over a 1? First off, I don't think a "humanly easiest path" would even be a meaningful term to use here, since a human couldn't really press a button *exactly* at some frame, thus always dying in the end if they were to use this algorithm (for a sufficiently hard/long level, anyway). Second, if we do use a DFS, and if we prioritise a 0 over a 1 (i.e., in our current binary string, we first try to "append" a 0 and *then* a 1), then, if we append a 0 and *don't* die, we'll just continue with this path to the next frame, and *won't* try appending a 1, unless, of course, the path where we had appended a 0 eventually fails at some frame (no matter what we would do, we'd still die), so if the current option works, we won't be trying the other one, unless the current option only leads to failures (this is how a DFS would work), whereas it seems that you implied that you'd *always* test both options, and if both worked, we'd first go with the "0" option (this is more like a BFS). Also, regarding the fact that the resulting binary string is the smallest number possible (in any base, actually ;p): this is a pretty easy consequence of the fact that we prioritise a 0 over a 1 in our algorithm, which means that the resulting binary string the algorithm will return will be the lexicographically smallest one for which we can pass the level using the algorithm. Anyway, this stuff isn't that important, I was mostly just making sure I understood everything, and found some simplifications along the way apparently. |
|
<3 <3333 <33 uWu wwwwuuuwuwuw uwu UwuA owowo0w0 ^_^ r@@@wwwrr mewoww meowmwwwwwmwma awoooooowwoowooou :VVVVV P_P 
