Author Topic: Math.sqrt alternative for calculating the length of a vector2d?  (Read 433 times)

ninekorn

  • Jr. Member
  • **
  • Posts: 68
    • View Profile
Math.sqrt alternative for calculating the length of a vector2d?
« on: January 24, 2018, 10:04:39 pm »
Hi anyone who will read this.

I've been working my ass off for 1 month ever since 24rth December to try and get the Drone Mod going forward. I already had a LOT of functions for the Drone Mod working like:

1. drone, go pick near containers,
2. drone, go mine,
3. drone, go empty inventory,
4. drone, go attack enemies in range,
5. drone, follow player,
6. drone, go repair yourself if not at full hp,

but without the drone formation function, the drones would just hit each other and collide with everything around them and just it wasn't really nice to watch.

And as AI_enabled suggested to me for the drones, Drone Formations would be a great idea. Things are getting great after one month of working hard on it. I've decided to implement a simple, very very simple pathfind, that just activates when the Drone is 5-10 Void Expanse Units distance from the player. This pathfind is NOT a grid 10*10 or whatever because that would've been too much overhead if a lot of Drones on the server. It's actually a simple pathfind that iterates a selected number of times and gets the 8 neighboors out of where the Drone is and right away calculates the best node gcost - fcost - hcost. This makes it so that instead of generating a whole 10*10 grid and applying the whole gcost etc to all of those nodes, it just applies those "costs" to the neighbooring nodes and selects the best node out of that pile and just removes the rest... I make it iterate 5 times for the moment and it's VERY effective to get the drone in position (of course, I still need to code the drone speed and make it use it's thrusters to get in position near the player)... But there is an issue. I am making 3 calculations using Math.sqrt to get the length of Vector2d needed for the drone to calculate the dot product... It's complicated to explain but anyway... I've got that whole part working but you must imagine that 3 sqrt per 20 decisions per seconds is 60 sqrt calculations for each drone per seconds WHEN the drone activates it's pathfind... Which is without a doubt, out of the question, to be in the final version of the drone mod. I mean this isn't a single player game so 100++ drones would maybe/probably make the server lag ... And so searching the web to find a solution, i've stumbled upon the FAST Quake 3 inverse Sqrt function that doesn't make use of Math.sqrt. But the thing is Void Expanse, as mentionned by AI_enabled, uses ECMASCRIPT 5 (strict mode). And things like:

Float32Array
Uint32Array
Int32Array
ArrayBuffer
Float.intBitsToFloat
Float.floatToIntBits

aren't recognized by ECMASCRIPT5 which makes all of those following reference functions not work...

https://stackoverflow.com/questions/11513344/how-to-implement-the-fast-inverse-square-root-in-java
https://gist.github.com/jhermsmeier/2269511
https://gist.github.com/bga/628591/07151f342022ad413bbb0d5b2846b7d80fe103fb
https://gamedev.stackexchange.com/questions/30727/implement-fast-inverse-square-root-in-javascript
https://gist.github.com/Starfys/aaaee80838d0e013c27d
https://www.beyond3d.com/content/articles/8/

This is complicated stuff for me at my current scripting experience and so if any of you guys in this community know what the heck I am talking about (because even I don't really understand those functions anyway), please feel free to give me some hint as to HOW I could calculate a position next to a player by normalizing a Vector2d without using Math.sqrt.
The way that I am doing it works but it is bound to lag if there is a LOT of drones on the server. I am going to keep working on the Drones for sure because whatever I learn while coding some AI stuff is not a loss to me, on the contrary, because I am pretty sure I could convert my whole scripts to C# anyway when I code in Unity3d.

So yeah, the moment that the drones get in formation and that it doesn't lag the moment that they first activate their pathfind (it doesn't lag after the first pathfind generation somehow), then I will start coding the Drone "control drift" function so that the drone itself uses it's thrusters to get to it's formation position at the fastest speed possible by using the path it generated from it's pathfind.

Anyway, to anyone who read this,
Thank you in advance.
nine


ai_enabled

  • AtomicTorch Founder
  • Hero Member
  • *****
  • Posts: 1025
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #1 on: January 24, 2018, 10:17:20 pm »
Hi nine,

There are two functions to calculate the dot product between two 2D vectors A and B:
Code: [Select]
// first approach uses vector lengths and so requires expensive sqrt calculation
var dot = a.Length * b.Length * Math.Cos(angle); // it also uses angle between A and B vectors

// second approach is much simpler
var dot = a.X * b.X + a.Y * b.Y;

So you can simply use the second approach to calculate the dot product.
If you need to get the angle between them, you can use this function:
Code: [Select]
var angle = Math.Acos(dot / (a.Length * b.Length));

Regards!

UPD. Oops, I was wrong :-), corrected the post.
So you actually need vector lengths (and so sqrt) to calculate the angle between vectors with the dot product (IF the dot product alone is not enough for your case).
I think this is a premature optimization. Even thousands of sqrt calculations per second are not that slow on modern CPUs. Don't optimize until you actually can feel that it's too slow.
« Last Edit: January 24, 2018, 10:38:58 pm by ai_enabled »

ninekorn

  • Jr. Member
  • **
  • Posts: 68
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #2 on: January 24, 2018, 10:50:30 pm »
Thanks for the quick reply AI!

I'm gonna start working on that. I thought that I needed to normalize the vectors before doing the Dot product. Here is the function that I was using to calculate the Dot product which is exactly the one you just mentionned... It also happens that the function is from a reference website you had given me in earlier posts.

   
Code: [Select]
Dot: function (aX, aY, bX, bY) {
return (aX * bX) + (aY * bY);
},

Also I've found that other reference for the fast sqrt stuff that i've got no idea how to implement anyway and that I probably don't even need to use anyway.
https://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

oh and ... I was actually using 6 Math.sqrt for all the things to work... I am now trying to remove 5 of them with your suggestion. I'm still not sure though about normalizing them or not but I do need to normalize the formation position near the player though which requires 1 Math.sqrt.

ninekorn

  • Jr. Member
  • **
  • Posts: 68
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #3 on: January 26, 2018, 02:26:16 am »
I got it  ;D

I am getting the player direction from a custom function I've made and then just putting the direction in variables and also getting the "right direction":

Code: [Select]
var forward = { x: playerDirection.x, y: playerDirection.y };
var right = { x: playerDirection.y, y: -playerDirection.x };

Then I am getting a point from a circle of radius 5 to the right of the player. This point is "static"...

Code: [Select]
var pointRightX = (5*  Math.cos(0 * Math.PI / 180)) + playerCoord.x;
var pointRightY = (5 * Math.sin(0 * Math.PI / 180)) + playerCoord.y;

Then I just create a direction from that point:

Code: [Select]
var dirRightX = pointRightX - playerCoordinates.x;
var dirRightY = pointRightY - playerCoordinates.y;

Then I'm using this snipet of code to give me the angle in degrees between the right direction of the player and the direction to the static point at the right of the player:

Code: [Select]
var angleDeg = ((Math.atan2(right.y, right.x) - Math.atan2(dirRightY, dirRightX)) * 180) / Math.PI;

Then I am again calculating the point on the diameter of the circle of radius 5 with the above angle in degrees with this:

Code: [Select]
var rightWaypointX = (5 * Math.cos(angleDeg * Math.PI / 180)) + playerCoordinates.x;
var rightWaypointY = (5 * Math.sin(angleDeg * Math.PI / 180)) + playerCoordinates.y;

No need to normalize anymore. There is no need to use Math.sqrt. I have got no clue though if it's gonna be more performant then Math.sqrt...
nine



I had to search the web and found those two references that helped me:

https://stackoverflow.com/questions/839899/how-do-i-calculate-a-point-on-a-circle-s-circumference
https://gamedev.stackexchange.com/questions/69649/using-atan2-to-calculate-angle-between-two-vectors

« Last Edit: January 26, 2018, 02:40:20 am by ninekorn »

ai_enabled

  • AtomicTorch Founder
  • Hero Member
  • *****
  • Posts: 1025
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #4 on: January 26, 2018, 03:09:10 am »
atan2 is the way we're usually using to get the angle between two vectors.
Actually, atan2 call is a little bit slower than sqrt on modern CPUs.
Anyway, it's not something to worry about until you really perceive the issue with the performance.

Regards!

ninekorn

  • Jr. Member
  • **
  • Posts: 68
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #5 on: January 26, 2018, 03:24:03 am »
-_- lol and I was so proud to have found an alternative. awww man. It wasn't even this causing my lag issue anyway. It's a tiny lag spike just when the AI's pathfind activates the first time and then it doesn't lag at all. I've kept a backup of the whole sqrt script but it was actually 6 Math.sqrt per 20 decisions per second per drones. It wasn't activating all sqrt per decisions, but maybe half so 10 * 6 = 60 Math.sqrt calls per drones per second. Maybe it's my "sort" function or "contains" function. I'm gonna test some more before I head into the drone "control drift" stuff.

Thanks AI

ai_enabled

  • AtomicTorch Founder
  • Hero Member
  • *****
  • Posts: 1025
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #6 on: January 26, 2018, 03:26:25 am »
>> It's a tiny lag spike just when the AI's pathfind activates

Does it happen for every new drone AI or just a single time? Sounds like a script loading/compilation lag, in that case you can't do much.

ninekorn

  • Jr. Member
  • **
  • Posts: 68
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #7 on: January 26, 2018, 09:14:05 am »
hmm. Ok. That's exactly the issue I had with the drone market then, until i fixed it by just fractionning the market mod in like 30 scripts instead of just 1 script. I'm gonna try stuff to see if it's gonna fix it. What I'm not sure to understand then is why the drone mod scripts would lag when there is only 8 scripts for the moment and those 8 are just for the formation behavior. 2 out of those have almost no code inside of them.
« Last Edit: January 26, 2018, 09:17:44 am by ninekorn »

Lurler

  • AtomicTorch Founder
  • Hero Member
  • *****
  • Posts: 1062
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #8 on: January 28, 2018, 09:30:03 pm »
Sorry to interrupt your conversation, but I'm just amazed at seeing this kind of mods being developed for VoidExpanse :)
Please keep up the good work and I really hope to see this released when you finish everything you have planned! :)

ninekorn

  • Jr. Member
  • **
  • Posts: 68
    • View Profile
Re: Math.sqrt alternative for calculating the length of a vector2d?
« Reply #9 on: January 31, 2018, 10:07:57 pm »
    I'd love to say that I am nearing my personal deadline to release my full mod of the game. But that would also be the first game I mod and I don't have any specific deadline. The only thing I've got are goals, as in, multiple different mods that I need to finish individually and when put together, they will make something awesome. As long as I can keep working on them, I know that I will finish them. I just don't know when. Just coding the formation stuff is awefully long, because it's the first time that I code that stuff with 1 year and 9 months of coding experience overall. But the more I code, the better I become. That's what's nice about coding, as long that we have the memory to handle what we've coded in the past, nothing is ever lost.

    Some people might say that I've planified too much for Void Expanse and it could take forever to finish all those projects but the thing is I understand javascript and c#. So as long as you guys support Void Expanse, I will keep working on those mods and as a main goal, to release the full package.

    And if someday you stop supporting Void Expanse, I will just convert what I've learnt coding Javascript for Void Expanse to c# because I know that I can do it. Hopefully, you won't have plans to stop supporting Void Expanse anytime soon. As I said once to AI_enabled, Void Expanse is just a sleeper.

    Once you guys are finally having a breather from Cryofall, I will have some requests for new API functions. Easy ones. Stuff like:


    • ship.GetForwardDirection (outputs Vector2 x and y) I could get the other directions just by switching the x and y components myself. This function will increase the potency of the drone formation. because right now I am using 2 frames to capture the direction by putting the first frame coordinates and second frame coordinates in variables... The problem is when the ship doesn't move... bam, i've got no direction except the last direction that is saved in a variable.
    • ship.GetSpeed (outputs true Void Expanse speed of the ships)
    • ship.GetCurrentRotation
    would output in radians or degrees.
    • ship.IsShipStrafingLeft and ship.IsShipStrafingRight
    would output a boolean. this will make me able to code a "mimic" function for the drones to completely "mirror" the player's movements when they get into formation. I would just need the current "real ship speed" and true "ship.GetForwardDirection" to perfectly match the player's movement, but it would be more fun if the drones strafe when the player strafes.
    • ship.IsPlayerFrontLeaping
    that's when the player is pressing the key "W" twice and the player blinks/leaps to the front. which leads to the next obvious API function.
    • ship.LeapFront

    So when you've got that tiny breather please give me a shout in private, you or AI_enabled. Until then, I will behave and won't ask for new API functions. I'm just gonna keep working with what I have  ;D

EDIT: lol i reread myself and thought that my post was rude. Sorry about that. Anyway, the moment I played the game, i just fell in love with it. Hopefully when I release the mods, it will get attention from some people, just a couple people that create servers with my mods will make me happy. I just cant wait to finish everything I have planned and release it. ;)
« Last Edit: February 01, 2018, 12:54:18 am by ninekorn »