Shooting projectiles at the player from predefined angles
Moderator: Moderators
Shooting projectiles at the player from predefined angles
In my game, an opponent shoots projectiles that are supposed to go into the direction of the hero. For this, the opponent can shoot in several pre-determined angles:
0°, 15°, 30°, 45°.
This means the opponent can shoot into the four cardinal directions, the four diagonal directions and two directions between every cardinal and diagonal direction, and he can use this in all possible combinations:
(The way, i.e. the pixels, of the 15° and the 30° lines are pre-calculated in arrays.)
I already managed to implement all the 24 directional movements themselves.
And I'm already able to decide which 45° "triangle" section the opponent shall choose, based on the hero's position. (I.e. the setion that is enclosed between one straight and one 45° line.)
The part where I'm stumped is this:
If I calculated that the hero is within this triangle:
How do I decide, without using multiplication or division, at which of the four angles the opponent shall shoot?
For example, if the hero is on one of the lowest blocks, then the straight line will probably be shoot at the hero if he's on the first 2.5 blocks or so.
The 15° angle will be shoot if he's on the next 3.5 blocks.
The 30° angle gets shot for the next 5.5 blocks.
And the 45° angle for the rest.
But if the hero is in the 10th block row from the bottom, then each degree is chosen based on the hero's horizontal position for appoximately the length of one block each.
So, to summarize:
I have the weapon start position. I have the current hero position.
I already found out in which triangle area between a hypothetical straight shot and a hypothetical 45° shot the hero is enclosed.
How do I decide, based on the hero's x and y position, whether the weapon uses its 0°, 15°, 30° or 45° shot?
The goal is of course that, if the hero doesn't move anymore, the projectile would come as close as possble to the hero.
It's pretty much the same principle that the Zoras (the water enemies) in "The Legend of Zelda" use. They also seem to have predefined angles for their projectiles. And they don't shoot randomly, they aim at Link as precisely as they can with their predefined arcs.
(In case anybody actually knows the general method used for the Zora projectiles, I'd be eager to know.)
0°, 15°, 30°, 45°.
This means the opponent can shoot into the four cardinal directions, the four diagonal directions and two directions between every cardinal and diagonal direction, and he can use this in all possible combinations:
(The way, i.e. the pixels, of the 15° and the 30° lines are pre-calculated in arrays.)
I already managed to implement all the 24 directional movements themselves.
And I'm already able to decide which 45° "triangle" section the opponent shall choose, based on the hero's position. (I.e. the setion that is enclosed between one straight and one 45° line.)
The part where I'm stumped is this:
If I calculated that the hero is within this triangle:
How do I decide, without using multiplication or division, at which of the four angles the opponent shall shoot?
For example, if the hero is on one of the lowest blocks, then the straight line will probably be shoot at the hero if he's on the first 2.5 blocks or so.
The 15° angle will be shoot if he's on the next 3.5 blocks.
The 30° angle gets shot for the next 5.5 blocks.
And the 45° angle for the rest.
But if the hero is in the 10th block row from the bottom, then each degree is chosen based on the hero's horizontal position for appoximately the length of one block each.
So, to summarize:
I have the weapon start position. I have the current hero position.
I already found out in which triangle area between a hypothetical straight shot and a hypothetical 45° shot the hero is enclosed.
How do I decide, based on the hero's x and y position, whether the weapon uses its 0°, 15°, 30° or 45° shot?
The goal is of course that, if the hero doesn't move anymore, the projectile would come as close as possble to the hero.
It's pretty much the same principle that the Zoras (the water enemies) in "The Legend of Zelda" use. They also seem to have predefined angles for their projectiles. And they don't shoot randomly, they aim at Link as precisely as they can with their predefined arcs.
(In case anybody actually knows the general method used for the Zora projectiles, I'd be eager to know.)
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Re: Shooting projectiles at the player from predefined angles
I believe there is no way to do this without division (or at least a normalization step that quacks like division). However, you don't need to do the full division: just calculate the first two bits of the quotient to get a passable approximation (atan(1/4)=14°, atan(2/4)=26°, atan(3/4)=37°)
Galaxian uses a "real" division routine to make the tiles (appearance of bearing) match the velocity of the enemies when they charge.
Galaxian uses a "real" division routine to make the tiles (appearance of bearing) match the velocity of the enemies when they charge.
Re: Shooting projectiles at the player from predefined angles
Depends on what you have time and space for, but I use this routine to compute the angle between two points.
https://codebase64.org/doku.php?id=base ... -bit_angle
Once you have an estimate of the angle between them, you could just round it somehow, or use a lookup table, or whatever, to translate it into one of the discrete angles that you support.
https://codebase64.org/doku.php?id=base ... -bit_angle
Once you have an estimate of the angle between them, you could just round it somehow, or use a lookup table, or whatever, to translate it into one of the discrete angles that you support.
My games: http://www.bitethechili.com
Re: Shooting projectiles at the player from predefined angles
The aiming routine in Thwaite and RHDE reflects the slope into the first octant (as you are doing), uses a division to calculate the slope, compares this slope to thresholds to narrow down the arctangent to 0/32, 1/32, 2/32, 3/32, or 4/32 turns, and undoes the reflection.
Re: Shooting projectiles at the player from predefined angles
I don't really understand how it works. Can you please put it into a formula where I have HeroX, HeroY, WeaponX, WeaponY and then the calculation?
(The function definition in C also just takes one parameter, so I don't get it. But even if I did, I don't use C library functions, so I would still want to know the actual formula.)
Yeah, "Galaxian" is a minimalistic game on a free playing field. It has enough CPU time to do this stuff. Not so much in a "Zelda"-like game with enemies, weapons, items, walls, doors etc.
Wow! I have literally no idea what's going on there.
Also, even though I do have space to spare, I don't know if I want to use so much ROM space (those lookup values) for such a relatively niche function in my game.
Sure, some opponents can shoot in arcs, but it's just one among many features and movement patterns and I'd like to keep stuff like this as simple as possible.
Maybe I might use a simple lookup table:
If you're 12 to 14 blocks below the opponent:
Use 0° for 0 to 2 blocks right from the opponent, 15° for 3-5 blocks, 30° for 6-11 blocks and 45° for 12-15 blocks.
If you're 10 to 11 blocks below the opponent: Use 0° for 0 to 1 block right from the opponent, ...
Those would then just be a few bytes: The horizontal max block value for each angle (four values). Multiplied with the number of vertical block groups (maxbe six). 4 x 6 lookup values. Wouldn't be too bad.
But I don't know if it's good enough for gameplay.
I'm also thinking of only using 12 directions instead of 24: The 30° directions and the four cardinal directions.
Since the program can already choose the correct 30° angle, I would then simply use the straight directions in a way where I ask whether the difference between HeroX and OpponentX (or HeroY and OpponentY, depending on your placement) is smaller than a certain value, then use the straight angle, else use the 30° angle, without including the Y (or the X) position at all for this decision.
But I need to see whether my graphic artist would be fine with only 12 directions.
Sorry, those are too many technical terms for me. Can you put it into a formula please, so that I can imagine it better?tepples wrote: ↑Thu Jun 25, 2020 2:10 pm The aiming routine in Thwaite and RHDE reflects the slope into the first octant (as you are doing), uses a division to calculate the slope, compares this slope to thresholds to narrow down the arctangent to 0/32, 1/32, 2/32, 3/32, or 4/32 turns, and undoes the reflection.
For the formula, just pretend that the player is down-right from the projectile, with the difference between the y values being greater than the difference between the x values (i.e. the player is in the octant from my second image). This way you can use the fix names x and y and don't need to include the fact that x and y might be y and x in another octant.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Re: Shooting projectiles at the player from predefined angles
What defines the angle between two points is the ratio between the vertical and horizontal distances between them. Normally you'd divide the greater distance by the smaller one and look up the angle from the result, but that's overkill since you have so few possible angles.
You can probably get away with taking the 3 or 4 most significant bits of the largest distance, then the respective bits of the smallest distance, and combine them into an index that you can use to look up the angle in a table. For example:
X distance: 00110101 -> 1101 (bits 5, 4, 3 and 2)
Y distance: 00000101 -> 0001 (bits 5, 4, 3 and 2, as dictated by the X distance)
Put them together to form an index: 00011101
And finally look up the angle from a table using this index.
You can probably get away with taking the 3 or 4 most significant bits of the largest distance, then the respective bits of the smallest distance, and combine them into an index that you can use to look up the angle in a table. For example:
X distance: 00110101 -> 1101 (bits 5, 4, 3 and 2)
Y distance: 00000101 -> 0001 (bits 5, 4, 3 and 2, as dictated by the X distance)
Put them together to form an index: 00011101
And finally look up the angle from a table using this index.
Re: Shooting projectiles at the player from predefined angles
O.k., this would be a simple calculation. But does this lookup index really mean I have to manually hardcode 256 array entries?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Re: Shooting projectiles at the player from predefined angles
You could easily generate it in JavaScript using the atan2 function.
Re: Shooting projectiles at the player from predefined angles
Do you find the following any easier to understand?DRW wrote: ↑Thu Jun 25, 2020 2:17 pmSorry, those are too many technical terms for me. Can you put it into a formula please, so that I can imagine it better?tepples wrote: ↑Thu Jun 25, 2020 2:10 pm The aiming routine in Thwaite and RHDE reflects the slope into the first octant (as you are doing), uses a division to calculate the slope, compares this slope to thresholds to narrow down the arctangent to 0/32, 1/32, 2/32, 3/32, or 4/32 turns, and undoes the reflection.
For the formula, just pretend that the player is down-right from the projectile, with the difference between the y values being greater than the difference between the x values (i.e. the player is in the octant from my second image). This way you can use the fix names x and y and don't need to include the fact that x and y might be y and x in another octant.
Code: Select all
Slope = (Hero_X - Projectile_X) * 256 / (Hero_Y - Projectile_Y)
If Slope < 256 * tan(1/64 Turn):
Return 0/32 Turn
If Slope < 256 * tan(3/64 Turn):
Return 1/32 Turn
If Slope < 256 * tan(5/64 Turn):
Return 2/32 Turn
If Slope < 256 * tan(7/64 Turn):
Return 3/32 Turn
Return 4/32 Turn
All this executes in about 400 cycles, or less than 4 scanlines. If you have one or two projectiles aiming per frame, it won't use up too many cycles.
Re: Shooting projectiles at the player from predefined angles
My angle functions are "accurate and full division", and they don't take massive time. I don't remember how many lines exactly, maybe 10-20, but that's still quite below the optimization threshold. Several enemies can shoot at accurate angles without the frame breaking a sweat. So perhaps measure a naive implementation first, before prematurely optimizing.
Re: Shooting projectiles at the player from predefined angles
Yeah, I struggle a bit to give such a relatively unimportant side functionality such a huge amount of "handwritten" individual data if simpler stuff is possible.
I cannot really imagine that Zora's projectile in "Zelda" has a huge lookup table with hundreds or even tens of values behind it. (I might be mistaken, of course.)
Yes, I guess so.
Is "1/64 Turn" supposed to be 1 / 64 * 360?
And if I have only the 24 angles from the screenshot above, would the following be correct?
Code: Select all
Slope = (Hero_X - Projectile_X) * 256 / (Hero_Y - Projectile_Y)
If Slope < 256 * tan(1/48 Turn):
Return ANGLE_STRAIGHT_LINE_ID
If Slope < 256 * tan(3/48 Turn):
Return ANGLE_15_DEGREE_ID
If Slope < 256 * tan(5/48 Turn):
Return ANGLE_30_DEGREE_ID
Return ANGLE_DIAGONAL_ID
I'm willing to give it a try. If you actually show me your function.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Re: Shooting projectiles at the player from predefined angles
360 of what? If degrees, then you are correct, as one turn equals 360 degrees. However, the trig functions in <math.h> of the C standard library or <cmath> of the C++ standard library are defined to take radians, not degrees, and there are τ ≈ 6.28318 radians in a turn.
I believe so.DRW wrote: ↑Fri Jun 26, 2020 12:27 am And if I have only the 24 angles from the screenshot above, would the following be correct?Code: Select all
Slope = (Hero_X - Projectile_X) * 256 / (Hero_Y - Projectile_Y) If Slope < 256 * tan(1/48 Turn): Return ANGLE_STRAIGHT_LINE_ID If Slope < 256 * tan(3/48 Turn): Return ANGLE_15_DEGREE_ID If Slope < 256 * tan(5/48 Turn): Return ANGLE_30_DEGREE_ID Return ANGLE_DIAGONAL_ID
Re: Shooting projectiles at the player from predefined angles
Yeah, that's why I asked what this means in practice. I have no idea about that stuff.tepples wrote: ↑Fri Jun 26, 2020 11:06 am 360 of what? If degrees, then you are correct, as one turn equals 360 degrees. However, the trig functions in <math.h> of the C standard library or <cmath> of the C++ standard library are defined to take radians, not degrees, and there are τ ≈ 6.28318 radians in a turn.
So, to understand it, I need you to convert this:
256 * tan(1/64 Turn)
into an expression that can be interpreted by C.
I understand that tan is a function (although I need to check the implementation behind it since I want it to be a compile time calculation and not a function call).
However, "1/64 Turn" is not valid C. That's why I was asking: What does this expression mean? How do you write it in a programming language? What calculation does "1/64 Turn" represent?
You said one turn is 360 degrees or 2 * Pi radians. So, I thought 1 / 64 Turn might mean 1 / 64 * 360. Or maybe 1 / 64 * 2 * Pi. If not, what is it instead?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Re: Shooting projectiles at the player from predefined angles
The <math.h> routines use radians. There are M_PI * 2.0 radians in one turn. This means the translation of "1/64 Turn" into the C programming language is 1.0 / 64.0 * M_PI * 2.0.
But the C language has no counterpart to the the constexpr keyword in the C++ language. This means that if you use the tan() function in software, the compiler is allowed to emit a call to the tan() function even if the argument is constant, which would cause the executable to include the entire object code of the tan() function. The NES CPU also has no support for floating-point numbers, and I don't know to what extent cc65's implementation of the C standard library emulates floating-point numbers in software. This means that you will probably not be able to use the tan() function directly within a source code file intended to run on the NES. Instead, you will need to write a program that runs on the PC, which calculates trigonometric constants and writes them out in a form that can be included in the program that runs on the NES.
What build tooling are you using? GNU Make? Command Prompt batch file? Do you have both a C compiler targeting your computer's native instruction set and operating system and a C compiler targeting 6502 installed? For example, do you have GCC or Clang installed? If you use Windows, do you have MinGW-w64 (a distribution of GCC) installed?
Or are you willing to introduce another programming language for calculation of lookup tables at build time? I've used Python for this purpose for most of my NES projects since fourth quarter 2009, save those few where I was deliberately avoiding Python to illustrate a point.
But the C language has no counterpart to the the constexpr keyword in the C++ language. This means that if you use the tan() function in software, the compiler is allowed to emit a call to the tan() function even if the argument is constant, which would cause the executable to include the entire object code of the tan() function. The NES CPU also has no support for floating-point numbers, and I don't know to what extent cc65's implementation of the C standard library emulates floating-point numbers in software. This means that you will probably not be able to use the tan() function directly within a source code file intended to run on the NES. Instead, you will need to write a program that runs on the PC, which calculates trigonometric constants and writes them out in a form that can be included in the program that runs on the NES.
What build tooling are you using? GNU Make? Command Prompt batch file? Do you have both a C compiler targeting your computer's native instruction set and operating system and a C compiler targeting 6502 installed? For example, do you have GCC or Clang installed? If you use Windows, do you have MinGW-w64 (a distribution of GCC) installed?
Or are you willing to introduce another programming language for calculation of lookup tables at build time? I've used Python for this purpose for most of my NES projects since fourth quarter 2009, save those few where I was deliberately avoiding Python to illustrate a point.
Re: Shooting projectiles at the player from predefined angles
Thanks. That's what I was looking for.
That's why I was hoping that the tan function is just a mathematical formula, without any ifs and fors. In this case, I could have taken the implementation and put it into a macro, so that the value is calculated at compile time if you use a constant parameter.tepples wrote: ↑Fri Jun 26, 2020 1:42 pmBut the C language has no counterpart to the the constexpr keyword in the C++ language. This means that if you use the tan() function in software, the compiler is allowed to emit a call to the tan() function even if the argument is constant, which would cause the executable to include the entire object code of the tan() function.
If that's not possible, i.e. if the function is not a single-line return in its C implementation, yeah, I could simply create a little C++ program in Windows that does this:
Code: Select all
for (int i = 1; i <= 7; i += 2)
{
cout << "#define TURN_" << i << " " << (int)(256 * tan((double)i / 64 * M_PI * 2)) << "\n";
}
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html