Before reading, check out this wonderful old flash game from which I blatantly stole this concept:
http://www.ferryhalim.com/orisinal/g2/dozen.htm (Also that site has some ridiculously adorable stuff. Check it all out. But first read my post and help me ok good thanks cool.)
The concept of the game is simple: you're in a basket, you have to jump straight up to land in the next basket. Jumps are always perfectly vertical an always the same height. In that game, the layout is all predefined and it has an end. I started thinking about how one might randomly generate the next basket to jump to in real time in order to make an infinitely scrolling game. This seemed simple at first, and certainly could be simple with an assortment of predefined cookie-cutter paths for the baskets to follow that could be used, but that doesn't make things interesting. When considering generating arbitrary paths or paths arbitrarily modified from a set of "template" path shapes (rather than exact predefined paths) with varying basket speeds and basket starting positions, the problem becomes a lot more complicated.
The first goal is to be able to determine whether a given pair of baskets makes a valid level, and then to assign the level a "difficulty" score. To do this we determine the periods of the two basket paths given path length and basket speed. Then we search through time from 0 to the LCM of the two periods, looking at the X and Y of the paths in order to locate all contiguous ranges ("windows") of t values at which jumping would land you in the upper basket. Given the set of jumping windows, difficulty can be derived with a function of number of windows total, size of windows, and time between windows. The actual difficulty scoring function isn't important here, but that's easy enough to create once we have the window data.
Let's consider a simplified case using only one positional dimension, y. Imagine a stationary basket on path y=1 directly below a basket moving up and down along path
y = sin(2t) + maxJumpHeight. Half the time, the basket will be within jumping range (when
yupper < ylower + maxJumpHeight) and the other half it will be too high. The LCM of the period of the paths is ~3.14 timesteps (seconds? sure), considering stationary paths as having a period of 1 not 0. Now for every time
t in range [0,3.14] we can plot the y values of the two baskets at
t. Now let's say it takes ~0.7s for the ball to reach a
maxJumpHeight of 2 or so. Now we can easily plot the peak jump height for a jump starting at any given t value. This can be plotted as
y = ylower(t-0.7) + 2 Plotting those should look something like this:
Blue = upper path over time
Orange = lower path over time (slanted for visibility because colors are dumb)
Red = ball max height over time (slanted to show how offset lines up)
Any point at time
ton the red line actually represents the peak of a jump if you had jumped at time
t-0.7. As long as we know this, we can ignore that offset as we only care about the ball's path and the upper basket's path at time t.
This implies that there are 2 places where you can land in the upper basket: intersections at points A and B. But that assumes you can ONLY land at the peak of your jump. We actually need to add another dimension to this because we care about all points along the ball's falling trajectory, not just the peak. To add this additional dimension, we must consider how long the ball has been falling for: a jump offset axis
j. This axis projects the falling motion forward in time for each second of j since the peak of a jump. Projecting this through the sine wave path of y
uper extended into the j dimension, we can see that there are many collisions along the falling path.
Because we care only about points after the jump peak, instead of projecting the jump paths forward in time for each timestep of j, I decided to project the falling arcs straight out along the j axis and project the basket path
backwards for each timestep of j. These should be equivalent transformations. By projecting the falling arcs straight along the j axis,
I know this is confusing as heck. I've tried to make these graphs as clear as possible but it's hard with what I'm using...
X axis = t; Y axis = y; Z axis = j
(I messed that graph up 3 times before even posting this, so I hope this time it's right)
Note that the sine wave position projects backward through X (t) for each Z (j) timestep, and the parabolic arcs project straight in the Z (j) plane. This should be equivalent to the sine wave projecting straight out in the Z axis and the jump arcs projecting forward through X for each Z step, right? I think that's right.Hopefully you can tell that at SOME point along the right hand side of the graph there is an intersection between the half parabola of the falling arc and the position vector of the upper basket. Any intersection implies that jumping at time
t-0.7 would land you in the basket at time
t.
THEREFORE, a valid value of t is one at which there is an intersection at
any j value after the peak of the jump.
In this graph, the "jump window" would be the second half of the interval. You could jump any time during that window and you would still land in the basket.
Ok, now that we've done it with a 1D position axis, add another one. Instead of only considering the Y value, we need to consider X and Y for the jump arcs and the basket paths at each time and jump offset. This makes the resulting graph 4-dimensional, meaning 3D intersections at any given t value rather than 2D.....yay....
I feel like I simply can't wrap my head around how to do any calculation for this (even in the simplified case) to effectively locate t values that contain intersections without just iterating over each one and running a 2D/3D intersection on the functions using j as the sole independent. Is there some sort of magic I could be using here?
---
I should also mention that this doesn't even begin to cover GENERATING the next path, just locating the jump windows for a given pair of paths...It's possible that it could be easier to generate a path that is guaranteed valid rather than validating an existing path, though I'm not sure how to figure that out either.
Thanks for taking the time to read all this. If there's any way I can clarify things, please ask. I think I have all the pieces in my brain to set up the situation, I just don't have the math to solve it, so hopefully I can explain any questions you might have.
-Taw
