Editor, Skilled player (1537)
Joined: 7/9/2010
Posts: 1319
Since this is a open problems topic, here are some problems that are in need to be solved to get my bot working. 1. Calculating the best (X;Y) positions on the analoag stick for a given angle and a given minimum radius. The analog stick only having one byte range in each direction makes this a problem, we can only get a rough aproximation to the needed input angle. The method in my current script is:
Language: lua

InputAngle = ((FollowAngle - CamAngle - 90) % 360) X = math.floor(math.cos(InputAngle)*Radius+0.5) Y = math.floor(math.sin(InputAngle)*Radius+0.5)
It calculates the input angle depending on the angle the character should follow and the current camera angle, then it calculates the closest (X;Y) positions for the anaolg stick by rounding it. But it isn't the best solution as I will show in an example. Let's say the angle the follow angle is 100°, the camera angle is 12.78° and the radius is 127 (That is the radius for calculating, not the minimum radius that is possible to get max speed, the game Chameleon Kid, which I used for testing has a minimum radius of ~70, which is good). The optimal input angle will be 357.22, which is not possible to get, because the calculated analog stick position will be (127; -6) and this is an input angle of 357.295124 (close but it goes better). After trying several combinations it's possible to get something better, in my script there's a routine which does that, but it's bruteforcing by rotating around the found position.
(X;Y): input angle
(-6;126): 357.2737
(-6; 125): 357.2516
(-6; 124): 357.2298
(-6; 123): 357.2073
...
(-5; 103): 357.2208
Now (-5; 103) is the closest that occured, but it has a really low radius, but again it depends on the game and it's minimum radius, if it was Chameleon Kid it was fine. So the question is can the best analog stick position actually calcualted without brute-forcing? 2. At a given analog stick position and a given minimum radius, what is the next analog stick position that gives the next greater/smaller input angle and how can it be calculated. This is something for games or sections that don't have a rotating camera. It isn't just one right, left, up or down. Look at the example above. The next possible angle from 357.2298 would be 357.2208, which is 1 up and 20 to the left. Again calculating the analog stick position, not bruteforcing it. 3. Preventing walking in the wrong direction. Let's say the player want to walk at 145°, but the script only gives an analog stick position that is slightly bigger than 145°, so the player essentially end up walking in a the wrong direction. So it's needed to keep track of the distance between the perfect movement vector and the actual position of the player, basically "zig-zaging" around this perfect movement vector is needed to accomplish this. How can this be done? 4. Rotate the coordinate system, so that there's an axis that is the player position on that axis depending on the angle the player wants to follow( and another axis that is not interesting). This is something to give the TASer a better visualisation of what's happening and better comparing of their work. Here's a picture of what I mean: I already tried to solve all these on my own, but didn't accomplished much.
Favorite animal: STOCK Gt(ROSA)26Sortm1.1(rtTA,EGFP)Nagy Grm7Tg(SMN2)89Ahmb Smn1tm1Msd Tg(SMN2*delta7)4299Ahmb Tg(tetO-SMN2,-luc)#aAhmb/J YouTube Twitch
Skilled player (1653)
Joined: 7/25/2007
Posts: 299
Location: UK
Well I don't quite understand your initial formulae, but the information we need is where you want to end up. Regarding (3) at least, you'd have to know the coordinates of where you're going. EG if we want to go at angle Red, but the script is off by angle Blue, thus we need an angle of Purple to compensate, this will depend on how far we want to go in the intended direction. We'd need to know initial/final location.
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
TASeditor wrote:
Since this is a open problems topic, here are some problems that are in need to be solved to get my bot working. 1. Calculating the best (X;Y) positions on the analoag stick for a given angle and a given minimum radius.
This is a well-known mathematical problem called "Diophantine approximation"; you're attempting to find a Diophantine approximation of the tangent of the angle in question (for which X and Y are within the range of the analog stick). Apparently the standard solution to this is to find a continued fraction for the number you're trying to approximate, then take the first few terms and evaluate the resulting rational. The continued fraction for tangent was found in 1768; it's: a / (1 - (a**2 / (3 - (a**2 / (5 - (a**2 / (7 - and so on (where a is the angle, in radians). Unfortunately, radians are exactly the wrong unit of measurement for this (because pi is irrational), and I'm not sure what the continued fraction looks like in degrees or 1/256ths of a circle or whatever unit of measurement the game in question is using. (Probably much more complicated; maths has a tendency to be simplest in radians.) I've tried to look it up, but not got a simple answer. The whole standard solution to this is probably also flawed due to convergence speed; I fear that even the smallest continued fraction solution would have a numerator and denominator too large for the relatively small range of an analog stick. I wonder if there are other Diophantine approximation algorithms which work better for smaller results?
Joined: 8/1/2006
Posts: 428
TASeditor wrote:
So the question is can the best analog stick position actually calcualted without brute-forcing?
You can search only the area near the angle; use the loop you had, at the minimum distance, until you cross the angle, then follow the crossover line outwards: Assume the angle is up and to the right; if not, rotate it start with x, y, bestX and bestY at 0 and bestAngle at 180 degrees. loop until x>maxCoordinate or y>maxCoordinate { if currentAngle(x,y) > searchAngle: x++ else: y++ if distance(x,y) > minDistance, and currentAngle is closer than bestAngle to searchAngle, set a new bestX, bestY and bestAngle. } output bestX, bestY, searchAngle
Trying 127.0.0.1... telnet: connect to address 127.0.0.1: Connection refused telnet: Unable to connect to remote host
Editor, Skilled player (1537)
Joined: 7/9/2010
Posts: 1319
Flip wrote:
Regarding (3) at least, you'd have to know the coordinates of where you're going. EG if we want to go at angle Red, but the script is off by angle Blue, thus we need an angle of Purple to compensate, this will depend on how far we want to go in the intended direction. We'd need to know initial/final location.
Do we really need to know the final destination? I thought about using two straight lines, one with the direction of the angle we want to follow and one with the actual angle. The offset is then determined by the distance between the first line and a point of the second line. Instead of using the actual positions we can also use relative positions starting from the origin, since it shouldn't matter where the lines are placed. But considering that the destination is most of the time not a single point, we can assume that it's not necessary to correct the offset and use the angle with the highest part toward the follow angle.
ais523 wrote:
The whole standard solution to this is probably also flawed due to convergence speed; I fear that even the smallest continued fraction solution would have a numerator and denominator too large for the relatively small range of an analog stick. I wonder if there are other Diophantine approximation algorithms which work better for smaller results?
That's unfortunate, the analog stick range is indeed a huge problem. I knew that it would be rough. In the end it might not even save a frame with this extreme optimisations due to error tolerance and the distance from one frame before the destination to the destination is too big to save a frame, but it could happen that one is just a tiny bit off saving a frame.
JSmith wrote:
Assume the angle is up and to the right; if not, rotate it
Writing a loop for each quadrant would prevent the need to rotate.
Favorite animal: STOCK Gt(ROSA)26Sortm1.1(rtTA,EGFP)Nagy Grm7Tg(SMN2)89Ahmb Smn1tm1Msd Tg(SMN2*delta7)4299Ahmb Tg(tetO-SMN2,-luc)#aAhmb/J YouTube Twitch
marzojr
He/Him
Experienced player (762)
Joined: 9/29/2008
Posts: 964
Location: 🇫🇷 France
TASeditor wrote:
1. Calculating the best (X;Y) positions on the analoag stick for a given angle and a given minimum radius. [snip details]
Here is an unorthodox idea: you know the "perfect" angle (357.22 in your example), and you have your "calculation radius" (127 in your example). So you draw a line using Bresenham's line drawing algorithm from (0, 0) to (radius*cos(angle), radius*sin(angle)). At each step in the line, you take the computed (x, y) values; if they are such that x**2 + y**2 < minimum_radius, you just go to the next point in the line; otherwise, you compute newangle = atan2(y, x) and see how close it is to the perfect angle, picking it if it is better than the best one seen so far. When you reach the endpoint of the line, you don't need to go any further (as it will be outside of the analog stick's range) and you will have the best angle possible. This is guaranteed because Bresenham's algorithm minimizes the error between the ideal line and the raster approximation it computes, so you will always be checking the points closest to the ideal line. In a more algorithmic, pseudo-C fashion:
var findOptimalAnalogPosition(var minRadius, var maxRadius, var idealAngle) {
	var point_list = Bresenham(0.0 , 0.0, maxRadius * cos(idealAngle), maxRadius * sin(idealAngle));
	var bestPt;
	var bestDist = INFINITY;
	for each (pt in point_list) {
		if ((pt.x * pt.x + pt.y + pt.y) >= minRadius) {
			var newDist = abs(atan2(pt.y, pt.x) - idealAngle);
			if (newDist < bestDist) {
				bestDist = newDist;
				bestPt = pt;
			}
		}
	}
	return pt;
}
Using this, I was able to find your optimal position of (103, -5) (you flipped the values at some point). In an actual implementation, you could "inline" Bresenham's algorithm and check the angle as you go about the line. For a byte-per-direction analog stick, you will need at most 127 steps to find the optimal angle.
TASeditor wrote:
2. At a given analog stick position and a given minimum radius, what is the next analog stick position that gives the next greater/smaller input angle and how can it be calculated.
The above can be used for this: you have the initial analog position, so you can use the (x, y) to compute the angle and use same algorithm above.
TASeditor wrote:
3. Preventing walking in the wrong direction.
The best way to do this for sure is to use a target position and periodically (every frame?) recompute the ideal angle from current position to target position and change the analog stick to point that way.
TASeditor wrote:
4. Rotate the coordinate system, so that there's an axis that is the player position on that axis depending on the angle the player wants to follow( and another axis that is not interesting).
I am not sure I understand what you want here. Can you elaborate?
Marzo Junior
Site Admin, Skilled player (1255)
Joined: 4/17/2010
Posts: 11495
Location: Lake Char­gogg­a­gogg­man­chaugg­a­gogg­chau­bun­a­gung­a­maugg
There can even be a (C# implemented) lua function for the above, in hopes to speed it up a bit.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Editor, Skilled player (1537)
Joined: 7/9/2010
Posts: 1319
marzojr wrote:
(you flipped the values at some point)
Ah, I remember, it was because I wrote it as (Y;X) on my sheet.
marzojr wrote:
TASeditor wrote:
4. Rotate the coordinate system, so that there's an axis that is the player position on that axis depending on the angle the player wants to follow( and another axis that is not interesting).
I am not sure I understand what you want here. Can you elaborate?
Simply to just have one axis the TASer needs to view, instead of two. For example the player moves along on the x-axis, only this axis needs to be viewed. But when moving at e.g. 35°, the TASer needs to view both x- and y-axis. So I want there to be an axis that eleminates the need of viewing two axises.
Favorite animal: STOCK Gt(ROSA)26Sortm1.1(rtTA,EGFP)Nagy Grm7Tg(SMN2)89Ahmb Smn1tm1Msd Tg(SMN2*delta7)4299Ahmb Tg(tetO-SMN2,-luc)#aAhmb/J YouTube Twitch
Editor, Skilled player (1537)
Joined: 7/9/2010
Posts: 1319
marzojr wrote:
This is guaranteed because Bresenham's algorithm minimizes the error between the ideal line and the raster approximation it computes, so you will always be checking the points closest to the ideal line.
So I finally added the algorithm, but it does some weird things. First it gives most of the time a (X, Y) coordinate which has a higher movement error according to the RAM variables than the old method, but the error from the ideal angle is lower; and second it often chooses a (X, Y) coordinate that is so bad that the angle is off by 10% or more. File for reference: User movie #30053802212310494
Favorite animal: STOCK Gt(ROSA)26Sortm1.1(rtTA,EGFP)Nagy Grm7Tg(SMN2)89Ahmb Smn1tm1Msd Tg(SMN2*delta7)4299Ahmb Tg(tetO-SMN2,-luc)#aAhmb/J YouTube Twitch