Shooting projectiles at the player from predefined angles

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Shooting projectiles at the player from predefined angles

Post by DRW »

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:

Lines.png

(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:

Triangle.png
Triangle.png (3.72 KiB) Viewed 6100 times

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
lidnariq
Posts: 11432
Joined: Sun Apr 13, 2008 11:12 am

Re: Shooting projectiles at the player from predefined angles

Post by lidnariq »

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.
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: Shooting projectiles at the player from predefined angles

Post by gauauu »

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.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Shooting projectiles at the player from predefined angles

Post by tepples »

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.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shooting projectiles at the player from predefined angles

Post by DRW »

lidnariq wrote: Thu Jun 25, 2020 1:14 pm (atan(1/4)=14°, atan(2/4)=26°, atan(3/4)=37°)
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.)

lidnariq wrote: Thu Jun 25, 2020 1:14 pm Galaxian uses a "real" division routine to make the tiles (appearance of bearing) match the velocity of the enemies when they charge.
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. :D

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.

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.
Sorry, those are too many technical terms for me. Can you put it into a formula please, so that I can imagine it better?
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
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Shooting projectiles at the player from predefined angles

Post by tokumaru »

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.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shooting projectiles at the player from predefined angles

Post by DRW »

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
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Shooting projectiles at the player from predefined angles

Post by tokumaru »

You could easily generate it in JavaScript using the atan2 function.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Shooting projectiles at the player from predefined angles

Post by tepples »

DRW wrote: Thu Jun 25, 2020 2:17 pm
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.
Sorry, those are too many technical terms for me. Can you put it into a formula please, so that I can imagine it better?
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.
Do you find the following any easier to understand?

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
The values 256 * tan(1/64 Turn), 256 * tan(3/64 Turn), 256 * tan(5/64 Turn), and 256 * tan(7/64 Turn) are constants. (One Turn is 360 degrees or 2*Pi radians, and every June 28 there's a movement to use the Greek letter tau to represent a turn rather than pi to represent half of one.) These are the four values under tantable in the aiming code of Thwaite.

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.
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Shooting projectiles at the player from predefined angles

Post by calima »

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.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shooting projectiles at the player from predefined angles

Post by DRW »

tokumaru wrote: Thu Jun 25, 2020 4:07 pm You could easily generate it in JavaScript using the atan2 function.
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.)
tepples wrote: Thu Jun 25, 2020 6:19 pm Do you find the following any easier to understand?
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
calima wrote: Thu Jun 25, 2020 11:37 pm My angle functions are "accurate and full division", and they don't take massive time.
[...]
So perhaps measure a naive implementation first, before prematurely optimizing.
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
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Shooting projectiles at the player from predefined angles

Post by tepples »

DRW wrote: Fri Jun 26, 2020 12:27 am Is "1/64 Turn" supposed to be 1 / 64 * 360?
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.
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
I believe so.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shooting projectiles at the player from predefined angles

Post by DRW »

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.
Yeah, that's why I asked what this means in practice. I have no idea about that stuff.
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
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Shooting projectiles at the player from predefined angles

Post by tepples »

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.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shooting projectiles at the player from predefined angles

Post by DRW »

tepples wrote: Fri Jun 26, 2020 1:42 pm 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.
Thanks. That's what I was looking for.

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.
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.

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";
}
I wouldn't even need to write this output into a source code file. Since I only have four numbers anyway, I could just calculate them once and use them directly in my program, couldn't I?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Post Reply