Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - ZippyDee

Pages: [1] 2 3 ... 51
Math and Science / Identifying 4D intersections with two unknowns.
« on: September 27, 2017, 06:08:27 pm »
Before reading, check out this wonderful old flash game from which I blatantly stole this concept: (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 yuper 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.


ASM / Re: 83+/84+ Free Ram Areas
« on: January 05, 2014, 06:33:17 pm »
Just for clarification, are the large spans of unlabeled RAM such as at $843F or $89EC all untouchable? Or just unknown?

TI Z80 / Re: [axe] GLib model editor (WIP)
« on: December 06, 2013, 01:13:22 pm »
Heh well I guess the first step is triangulation, THEN opaque triangles.

Do you have any ideas on how you're going to specify triangles? I feel like the user would manually select a triangle by choosing the three vertices, and THAT's when the model should be gray. Points and edges would turn black once selected. Maybe you can use like a gray-black flashing cursor or something for that drawing so that it contrasts with both the gray and the black models.

The fact is that you'll almost definitely want user-selected triangles, rather than having to write any triangulation routines for arbitrary polygon selections (which would be a total bitch to write). You COULD write some triangulation routines, but I wouldn't recommend it.

TI Z80 / Re: My first game
« on: December 05, 2013, 09:33:59 pm »
Opening with notepad should not have changed the files themselves at all. TIConnect should still work

TI Z80 / Re: [axe] GLib model editor (WIP)
« on: December 05, 2013, 08:35:03 pm »
graying out the cursor is done in the grayscale version, so do you want a combination of the two where the vertices stay black but the cursor is gray?

When I add line drawing or selecting multiple vertices, would you prefer the points to stay black and the selection being indicated by multiple gray cursors? Or add gray cursors to the selected points, maybe with the real cursor being black, or do you prefer to have it all in b&w?

Yes, I'd say vertices stay black but cursor is gray, and then in multiple vertex selection I'd say either multiple gray cursors, or do the opposite and have one of them be gray point on a black cursor. It's just the contrast so that you can see the actual position of the point without the cursor getting in the way. It's totally functional the other way as well, it's mostly an issue with the further points where the length of the cursor lines are shorter.

It definitely looks great there in that Arwing video. Having everything in the model be black makes it a lot easier to see what you're doing and what you're working with.

I guess the next step is opaque polygons :O

No, it doesn't work that way, chickendude.
Think of it this way:

You have tiles ABCD in a square

You are at tile A and you want to figure out if you can move diagonally to D, which is not a wall. You check if D is bit 1 of the pattern. It is. (woo!) So you move to D.
But wait.... What about B and C? If B and C are walls, you've now walked through a wall...We can't be having that now, can we? If either B or C are walls, you can't move diagonally to D. They BOTH need to be valid in order to move.

My solution to that is to look at the valid adjacent tiles and keep that data in a byte somewhere when you move to the next tile. Let's say you're at A and you check your surrounding tiles and get Down and Right as valid directions. Your data is formatted something like %0000ULDR so you end up with %00000011 as your adjacent data for this tile.
So now you choose one of those two directions to move. Doesn't matter which. Let's say right. So you AND your data with %11111110 to reset the bit for right, and you move to that tile.

Now you're at B and you check valid directions and you end up with something like %00001011 (Up, Down, and Right). Now AND that with the byte you stored from your previous tile (which is now %00000010) and you have %00000010 as a result. That means you could have moved Down before, but you didn't, and you still can move down now. You know now that you can move diagonally to D without any issues because both B and C must be free. After moving to that diagonal tile be sure set the saved data to %00000000 so there aren't any issues!

That's the solution I've come up with so far. I think it should work if I can write it like that!

« on: December 05, 2013, 12:37:25 am »
That looks great! I think you should leave the sprites that are visibly adjacent to a wall as your originals and use the freestanding spikes as Keoni's. Also I noticed that you changed the location of that gap so it didn't have the spike issue. looks awesome!

Yeah, I've already written it with bits. I'm having trouble with the backtracking, specifically an efficient way to implement it with diagonals. I'll try to make some animated pictures to illustrate the method I have in mind.

« on: December 04, 2013, 02:30:26 pm »
Just a point I feel I should make after watching that screenie, one thing that VVVVVV makes a point to do very well is to never place spikes in a location that immediately kills you without warning when changing screens. There should never be a place where the spikes go all the way to the edge of the screen where you can enter from the other side. There should be at least a 1 tile gap so it doesn't feel like the game is cheating you.

Other than that this game honestly looks fantastic!

TI Z80 / Re: [axe] GLib model editor (WIP)
« on: December 04, 2013, 02:53:34 am »
What might be useful is to instead gray the cursor so that the point is more visible. Right now the cursor covers the point and makes it difficult to tell exactly where it is, especially at higher depths relative to the camera. If you had a way to gray out the cursor and draw the selected point over it in black then the point might be much easier to see.

The 01100110011 pattern is the value assigned to the bit in b_nodes.

You mark the starting location as closed. Then EVERYTHING that is closed so far is expanded into the surrounding nodes that aren't closed yet. Each of those are then marked as closed and given the current pattern value.

Each pass over the buffer the value is either a 1 or a 0. Every bit expanded during that pass is assigned the same value. The value then changes for the next pass to the next value in the pattern.

This doesn't work for diagonal movement because of the pattern. That pattern only works for 4-directional movement. There may be multiple paths found to the goal, but all of them will have the same length, so it doesn't matter which one you choose.

I'll make some pictures to illustrate the concept.


Here you can see that it expands every possible node each pass. The value assigned follows the pattern I described. Once the goal is found, you can follow the pattern in reverse to find your way back.

That was the path I chose to follow, but any of these paths would be valid, because they all follow the pattern:

Note that they are all the exact same length. So technically the set of valid tiles to move to is:

EDIT: I put the pictures in the first post as well

After many months, Hello! I am back with a question!

I have written an implementation of a Breadth First Search algorithm that doesn't use queues or stacks to search for the goal node, and instead uses fixed buffers! I have the search written, and now I'm writing the backtracking part of it to find a path from the goal back to the start node.

The implementation uses three bit-mapped 128 byte buffers to represent a 32x32 map. These buffers are contiguous in RAM.
(listed in order)
b_tilemap: each bit represents whether a tile is walkable or not. 0 = empty, 1 = wall.
b_closed: each bit represents whether this node has been visited or not by the search algorithm
b_nodes: each bit represents the value assigned to the node when it was visited. This value is used for backtracking, and this is why the algorithm is interesting!

When the routine starts, the bit of the starting node in b_closed is set. Each iteration of the search passes over the entire buffer. Every bit in the b_closed buffer is "expanded" into each of the 4 adjacent bits that are not walls in b_tilemap. Any newly expanded bits that were not already set in the b_closed buffer are assigned a value of either 1 or 0 in the b_nodes buffer. This value is the same for every new bit expanded during the iteration. After each pass, the bit of the goal node is tested in b_closed. If it is set, we know the goal node has been visited, so we can now backtrack from here to the start by following our b_nodes values!

The assigned b_nodes value follows the pattern 0, 1, 1, 0, 0, 1, 1, 0, etc, changing each iteration to the next value in the pattern. This is the key to this algorithm. At any given index in this pattern, the previous and next indices always have different values. With a reference of the current value and either the next value or the previous value in the pattern, the third value can always be determined.

You can walk a path by walking to adjacent nodes that match the next value in the pattern.

Obviously from the starting node every possible route follows this pattern, because it all expanded from that point. However, if we follow the pattern in the reverse direction from where we ended, it will always lead us from the goal back to the start. There may be multiple paths, but, if so, all paths will be the same length, so it doesn't matter which path is taken.

The backtracked path is the only part of this algorithm that uses variable memory, because we obviously can't know how long the path is until we've found it!

I HOPE THAT ALL MAKES SENSE... O.O If not, I would love to clarify.


Here you can see that it expands every possible node each pass. The value assigned follows the pattern I described. Once the goal is found, you can follow the pattern in reverse to find your way back.

That was the path I chose to follow, but any of these paths would be valid, because they all follow the pattern:

Note that they are all the exact same length. So technically the set of valid tiles to move to is:

This algorithm is designed to do a search in 4 directions only, however I realized that backtracking correctly can produce an 8-directional path, which I would greatly prefer. Note that any time it has multiple possible paths, all options will produce the same length of 4-directional path, so any time you can move diagonally is ALWAYS an improvement. The algorithm should always try to move in a straight line, unless it has the option to move diagonally (and is not moving diagonally in a different direction already, of course). This creates the most efficient paths with 8-directional movement and accounts for the possibility that changing direction has a cost (such as enemies having to turn to face a new direction before moving that way).

The way I thought of to implement diagonal movement is to compare the "options" from the previous node in the path with the "options of the current one. For example, let's say at node A you can move either right or down, so you choose to move right and add that node to the backtracked path. Now at node B you can move either right, down, or up. Well if you compare with the valid directions at A, you can see that down was valid for node A, too! That means the node diagonally down-right from A is valid and not blocked by any walls or corners! So instead of adding a new node to the backtracked path, we just change the last node we added to be right-down from A, instead of just right.

//EDIT: The returned path can be quite small if represented by a series of directions 0-7. The layout I have for this is 0=right, going counter-clockwise around the directions (1=up-right, 2=up, 3=up-left, etc). It's easy to expand any format of directions like that into an X and Y offset using a couple of LUTs.

Does that make sense as well? I hope so, because the question is...

How do you do that efficiently? All of it. What's the most efficient way to check the 4-directional surrounding bits recursively like that? Am I missing a more efficient way to check diagonal pathing? I just can't come up with a way to write this backtracking that I feel is very efficient.

Thanks so much for any input! I'll clarify anything that is confusing if need be!


TI Z80 / Re: Zelda resumed and almost done...a bit of help needed
« on: September 21, 2012, 03:23:20 am »
You definitely do not need advanced pathfinding of any kind for this.

Something thing to note is that most enemies who move deliberately closer to you don't begin to do so until you're within a certain distance from them, within their line of sight, etc. Otherwise, they just move randomly as well. Even so, the best they can do is simply move toward you, they never actually do any pathfinding. Ever. EVER. (Ever.)

Also........Which Zelda game specifically is this a clone of? Is it Link's Awakening? Or an older one than that?

Maximum Security / Re: DT's unnamed puzzle platformer
« on: September 21, 2012, 03:12:25 am »
Will explosions hurt the player as well? Or just remove blocks?

TI Z80 / Re: TinyCraft II (name subject to change)
« on: September 21, 2012, 03:09:25 am »
What are you using for sprites in this? Are those original? Or modified versions of the sprites used in the original TinyCraft thread?

Pages: [1] 2 3 ... 51