As you know, I'm working on this game engine. One of the missing parts in the engine is to quickly calculate the angle between two points on the plane.
In my gaming logic, I'm already able to calculate the deltas for X and Y based on a given angle, using sin and cosin tables, but my biggest hurtle was to understand how to find the right way to make an enemy shoot a bullet from his machine to the player machine with a relevant accuracy (but not too accurate)...

That brought me to the topic of the arctan2 function, of which a lot is written. Every programming language imaginable has this function implemented. However ... that did not solve my issue for the CX16. How to quickly calculate a usable angle from two points on a plane on an 8 bit machine, where multiplication and division takes CPU time.

The latter drew my immediate interest, and the more I started to analyze the assembly code, the less I understood what was going on...

;; Calculate the angle, in a 256-degree circle, between two points.
;; The trick is to use logarithmic division to get the y/x ratio and
;; integrate the power function into the atan table. Some branching is
;; avoided by using a table to adjust for the octants.
;; In otherwords nothing new or particularily clever but nevertheless
;; quite useful.
;;
;; by Johan Forslöf (doynax)
octant = $fb ;; temporary zeropage variable
atan2 lda x1
sbc x2
bcs *+4
eor #$ff
tax
rol octant
lda y1
sbc y2
bcs *+4
eor #$ff
tay
rol octant
lda log2_tab,x
sbc log2_tab,y
bcc *+4
eor #$ff
tax
lda octant
rol
and #%111
tay
lda atan_tab,x
eor octant_adjust,y
rts

This routine seems not to be a blast from the past, as it appears to be posted in 2015 somewhere on the site.
However, the way how the angle is calculated is rather genius ... (Although the creator is saying it's nothing special ..., I admire the intellect behind this).

So I decided to study it a bit more in depth what is going on here ...

The routine accepts two 8 bit 2D coordinates, so an (x1,y1) and (x2,y2), and calculates an "angle" between 0 and 255!

It first calculates the "slope" between the two points.
As we all know, to calculate a slope, one needs to "divide the y over x" (or the other way around), and executing a division on an 8-bit machine requires a proprietary algorithm to be written with the risk of consuming too much CPU. However, what this algorithm does, is uses a base 2 logarithm table that applies the Logarithm quotient rule:

In other words, using the logarithm table, it is very fast to calculate the quotient of the X/Y by subtracting the logarithm of X over the logarithm of Y.

lda log2_tab,x
sbc log2_tab,y

The other concept that the atan2 routine implements, is the angle calculation over 8 "octants" in a circle (there are 4 quadrants in a circle) ... It does this by examining 3 essential parameters of the input: the sign of the x and y coordinates, and then when x is divided over y, to determine if x is greater than y or vise versa. This takes most of the code, and instead of writing a lot of branches, the logic implements the selection of the octant segment using an assembler trick using the carry flag!

octant = $fb ;; temporary zeropage variable

The logic builds up the octant variable gradually, which essentially contains the results of the carry flag shifted to the left at each of the calculation steps.

First, the absolute value of x is determined, and the corresponding segments in the octant model is determined, whether x1 is smaller than x2. When x1 is smaller than x2, then the carry will be set and will be shifted into the octant variable! So if x1 < x2, then the carry will be set, and the eor #$ff will make the negative result "positive", but it seems not to do this using the 2s complement rule (eor $#ff, clc, adc $#01). I think he did not implement 2s complement because the logic anyway achieves an approximation, and 2nd the carry bit would be cleared when clc would be used for the octant determination ...
Anyway, the octant variable will get a value %1 or %0 at this stage..., depending on the value of x1 and x2.

Second, the absolute value of y is determined, and the corresponding segment in the octant model, whether y1 is smaller than y2. The resulting carry is left shifted into the octant variable, but bare in mind that the octant has already the octant segments of the x value embedded! So the octant values now will get a value %00, %01, %10 or %11, depending on the value of y1 and y2. Thus the quadrant in the octant model is calculated here.

lda y1
sbc y2
bcs *+4
eor #$ff
tay
rol octant

Third, the logaritmic devision is applied (as explained above) but also here the 3rd dimension in the octant model is determined, depending whether x is smaller than y. So the octant now can get value %000, %001, %010, %011, %100, %101, %110 or %111, and the resulting octant segment now is fully calculated.

lda log2_tab,x
sbc log2_tab,y
bcc *+4
eor #$ff
tax
lda octant
rol
and #%111
tay

Note that the x register will contain the position to calculate the angle using the arctan table, and the y register will contain the 3 bit index to adjust the calculated 5-bit angle with the resulting octant segment!

The octant variable now has 8 possible values to calculate the angle, based on the calculated angle containing out of 5 bits in the 8-bit range using the arctan table ... Depending on the resulting value:

The last point to be explained is how the angle is calculated ... this is done using the pre-defined arctan table. The author does a trick, as the arctan table normally has a domain -pi/2 < y < pi/2, the atan table has the values populated in exponential order base 2 in 5 bits, but only from the lower domain (-pi/2 < y), excluding the value x = 0! In other words, it models a table of the values between x = -256 and x = -1 where the arctan table is populated with the expondential results of arctan(2^(x/32))*128/pi. A closer look will quickly identify that 128 is actually a simplification of 256/(pi*2) ... Thus, the resulting table contains values from $00 till $1f, which calculates the angle for octant segment 0. Again, $20 is not included as this would be the starting value of octant 1. The atan table actually models the resulting angle of the first segment in the octant model. The octant variable then will adjust the resulting angle to the correct octant depending on x1 - x2 values, y1 - y2 value and the resulting x and y value comparison.

I've modelled this out in geogebra, as part of the study, to fully understand what the arctan function is doing and how the angle is calculated for the first octant segment!
See attached, but here is how the geogebra model looks like. Note that the functions implement the "floor()" method to eliminate any fractional number and to simulate how it would run on the 8 bit machine ...

The green liine models the logarithm function log2(x)*scale, which is set in this example to 32.
The blue line is the actan function arctan(2^(x/scale))*width/(pi*2), with a width set to 256. This will result in angles between 0 and 63 for two octant segments 0 and 1.

Point A and B are the two points for which the atan is calculated. Move A and/or B but the function only implements the arctan, not the arctan2!

The geogebra model explains that when the AT point is in the lower domain of the arctan function, it returns the angle of point B from 0 to 31 degrees.

Now, I find that an angle of 256 possible values is too much, so my game logic implements and angle of 64 angle values, and that is more than enough! So, the actual octant model would be a subdivision of 3 bits instead of 5 bits, from 0 to 7.

Other point is the "resulution", it is not necessary to store for the log2 table 256 values, as the only thing I'm trying to accomplish, is to find the angle, and i can downsize the resolution from 640x480 to 160x120 for example. (by shifting the bits with 2 positions to the right), which requires me to only populate a table of 160 bytes ...,

This would result in geogebra in the following settings (see the sliders) and the resulting angle). A scale of 16 and a width of 64 would allow me to only require 64 records in the arctan table, and 160 records in the log2 table, to calculate the angle between 0 and 7. I'm still studying a bit on how to optimize this and to actually implement all this in a working CX16 atan2 function, but i'll put that in a later post (as I'm progressing) ... Otherwise it becomes too much to write it all down ...

I'm not a mathematician, so not sure if the above explanation makes sense and any adjustment, recommendation or addtional info you want to share is welcome in this very interesting topic. I'm sure there are people here who have been doing this in the past already ...

## Question

## svenvandevelde

As you know, I'm working on this game engine. One of the missing parts in the engine is to quickly calculate

the anglebetween two points on the plane.In my gaming logic, I'm already able to calculate the deltas for X and Y based on a given angle, using sin and cosin tables, but my biggest hurtle was to understand how to find the right way to make an enemy shoot a bullet from his machine to the player machine with a relevant accuracy (but not too accurate)...

That brought me to the topic of the arctan2 function, of which a lot is written. Every programming language imaginable has this function implemented. However ... that did not solve my issue for the CX16. How to quickly calculate a usable angle from two points on a plane on an 8 bit machine, where multiplication and division takes CPU time.

So I've been seaching the internet for a solution (I am not a matematician but learned sufficient maths in my studies, but forgot most of it).

Then one day, I stumbled on these two algorithms:

- Z80 CPU architecture - 8-bit atan2 | MSX Resource Center (Page 1/3)

- 6502 CPU architecture - base:8bit_atan2_8-bit_angle [Codebase 64 wiki]

The latter drew my immediate interest, and the more I started to analyze the assembly code, the less I understood what was going on...

This routine seems not to be a blast from the past, as it appears to be posted in 2015 somewhere on the site.

However, the way how the angle is calculated is rather genius ... (Although the creator is saying it's nothing special ..., I admire the intellect behind this).

So I decided to study it a bit more in depth what is going on here ...

The routine accepts two 8 bit 2D coordinates, so an (x1,y1) and (x2,y2), and calculates an "angle" between 0 and 255!

It first calculates the "slope" between the two points.

As we all know, to calculate a slope, one needs to "divide the y over x" (or the other way around), and executing a division on an 8-bit machine requires a proprietary algorithm to be written with the risk of consuming too much CPU. However, what this algorithm does, is uses a base 2 logarithm table that applies the Logarithm quotient rule:

In other words, using the logarithm table, it is very fast to calculate the quotient of the X/Y by subtracting the logarithm of X over the logarithm of Y.

The other concept that the atan2 routine implements, is the angle calculation over 8 "octants" in a circle (there are 4 quadrants in a circle) ... It does this by examining 3 essential parameters of the input: the sign of the x and y coordinates, and then when x is divided over y, to determine if x is greater than y or vise versa. This takes most of the code, and instead of writing a lot of branches, the logic implements the selection of the octant segment using an assembler trick using the carry flag!

The logic builds up the octant variable gradually, which essentially contains the results of the carry flag shifted to the left at each of the calculation steps.

First, the absolute value of x is determined, and the corresponding segments in the octant model is determined, whether x1 is smaller than x2. When x1 is smaller than x2, then the carry will be set and will be shifted into the octant variable! So if x1 < x2, then the carry will be set, and the eor #$ff will make the negative result "positive", but it seems not to do this using the 2s complement rule (eor $#ff, clc, adc $#01). I think he did not implement 2s complement because the logic anyway achieves an approximation, and 2nd the carry bit would be cleared when clc would be used for the octant determination ...

Anyway, the octant variable will get a value %1 or %0 at this stage..., depending on the value of x1 and x2.

Second, the absolute value of y is determined, and the corresponding segment in the octant model, whether y1 is smaller than y2. The resulting carry is left shifted into the octant variable, but bare in mind that the octant has already the octant segments of the x value embedded! So the octant values now will get a value %00, %01, %10 or %11, depending on the value of y1 and y2. Thus the quadrant in the octant model is calculated here.

Third, the logaritmic devision is applied (as explained above) but also here the 3rd dimension in the octant model is determined, depending whether x is smaller than y. So the octant now can get value %000, %001, %010, %011, %100, %101, %110 or %111, and the resulting octant segment now is fully calculated.

Note that the x register will contain the position to calculate the angle using the arctan table, and the y register will contain the 3 bit index to adjust the calculated 5-bit angle with the resulting octant segment!

The octant variable now has 8 possible values to calculate the angle, based on the calculated angle containing out of 5 bits in the 8-bit range using the arctan table ... Depending on the resulting value:

The last point to be explained is how the angle is calculated ... this is done using the pre-defined arctan table. The author does a trick, as the arctan table normally has a domain -pi/2 < y < pi/2, the atan table has the values populated in exponential order base 2 in 5 bits, but only from the lower domain (-pi/2 < y), excluding the value x = 0! In other words, it models a table of the values between x = -256 and x = -1 where the arctan table is populated with the expondential results of arctan(

2^(x/32))*128/pi. A closer look will quickly identify that 128 is actually a simplification of 256/(pi*2) ... Thus, the resulting table contains values from $00 till $1f, which calculates the angle for octant segment 0. Again, $20 is not included as this would be the starting value of octant 1. The atan table actually models the resulting angle of the first segment in the octant model. The octant variable then will adjust the resulting angle to the correct octant depending on x1 - x2 values, y1 - y2 value and the resulting x and y value comparison.I've modelled this out in geogebra, as part of the study, to fully understand what the arctan function is doing and how the angle is calculated

for the first octant segment!See attached, but here is how the geogebra model looks like. Note that the functions implement the "floor()" method to eliminate any fractional number and to simulate how it would run on the 8 bit machine ...

The green liine models the logarithm function log2(x)*scale, which is set in this example to 32.

The blue line is the actan function arctan(2^(x/scale))*width/(pi*2), with a width set to 256. This will result in angles between 0 and 63 for two octant segments 0 and 1.

Point A and B are the two points for which the atan is calculated. Move A and/or B but the function only implements the arctan, not the arctan2!

The geogebra model explains that when the AT point is in the lower domain of the arctan function, it returns the angle of point B from 0 to 31 degrees.

Now, I find that an angle of 256 possible values is too much, so my game logic implements and angle of 64 angle values, and that is more than enough! So, the actual octant model would be a subdivision of 3 bits instead of 5 bits, from 0 to 7.

Other point is the "resulution", it is not necessary to store for the log2 table 256 values, as the only thing I'm trying to accomplish, is to find the angle, and i can downsize the resolution from 640x480 to 160x120 for example. (by shifting the bits with 2 positions to the right), which requires me to only populate a table of 160 bytes ...,

This would result in geogebra in the following settings (see the sliders) and the resulting angle). A scale of 16 and a width of 64 would allow me to only require 64 records in the arctan table, and 160 records in the log2 table, to calculate the angle between 0 and 7. I'm still studying a bit on how to optimize this and to actually implement all this in a working CX16 atan2 function, but i'll put that in a later post (as I'm progressing) ... Otherwise it becomes too much to write it all down ...

I'm not a mathematician, so not sure if the above explanation makes sense and any adjustment, recommendation or addtional info you want to share is welcome in this very interesting topic. I'm sure there are people here who have been doing this in the past already ...

Sven

ATAN2.ggb

Edited by svenvandevelde## Link to comment

## Share on other sites

## 20 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.