I want to check if a vector is within range of another vector. Simple enough with "SquareRoot((x-x2)^2 + (y-y2)^2 + (z-z2)^2) <= 32" but I have 1000 vectors to compare to 12 vectors (12000 checks). Is there another way to go about this?
I don't think there is some magical way to calculate the distance of 12000 vector pairs without requiring some CPU time/ressources. If there is please tell me, but I wouldn't be too optimistic :) If these distances are static you can preload them, if they are not you should think about when you actually need the distances and only calculate them at that point (or a combination of these 2).
If you desperately need to calculate the distance of 1000 vectors compared to 12 vectors at the same time in game time without some lag, I can't think of any way to do that, but I have to say that I am not an expert for stuff like this (yet). But if I had this problem I wouldn't wait for a magic mathematic answer which probably doesn't exist for your general case and rather try to find another way of calculating them one by one or something. If there are characteristics which apply to all of your vectors (for example they are all on the same plane) then it is of course possible to reduce the amount of calculations your computer has to do, but I don't think it is possible for your general case.
I was thinking along the same lines. I just put it out there to get any ideas. My current method for dealing with the problem is dividing the task in separate parts which are checked depending on need. For instance, bunches of units may get one single target for the whole group. Also, units far away, compared to close ones, will only get checks a fraction of the time, whereas closer units will get checks every 2 seconds or so.
Okay, sorry that I couldn't help :) Good luck getting it to work properly.
But I'm curious, why exactly do you need the exact distance of your vectors in a 3d space constantly? I really can't think of any game concept which would need something like this.
Normally yes, but, my game concept is a large-scale space game, undecided on exact game play. The problem is maps have limited space and and loading large maps is annoying, so I went a different route and designed my own system for tracking object/units off the screen. Your unit is in the center of the screen always and instead of you moving the units move around you. The system allows me to determine which units are within your range to be shown on the screen.
Just need to overcome the high demand for processing everything.
"check if a vector is within range of another vector" doesn't make sense, since vectors are homeless. I assume you mean location. And it looks like you're actually just trying to detect collision.
I would link you to my physics engine tutorial, but I haven't updated it with the more efficient sweep-and-prune algorithm yet. So maybe I'll do that tonight.
In the mean time, note that it's faster to square the other side of the inequality than to take the square root.
No collision. I don't care about that at this time.
Sorry I have no education in vector so I don't understand "In the mean time, note that it's faster to square the other side of the inequality than to take the square root.", unless you mean use (v2-v1²)^0.5 instead of SquareRoot((VectorX*2)+(VectorY*2)+(VectorZ*2))? All I know is v=v1+ms*(v2-v1)/|v2-v1|
Explain better what are you doing and how you are doing it.
I'm trying to guess.
- You store inside an array a list of 3d coordinates for each object in your universe
- When the unit moves you periodically check for nearby objects comparing the 3d distance between the ship and each object of the whole list.
- If the object position is in range you create the unit
- If a created unit is not in range you destroy it
So the main problem here is that you are using a list to store these coordinates, that means that your only way to find the points in your interested area is to loop on the whole list.
You must find a better way to index these coordinates so you can efficiently check only what you need.
For instance a good way would be to use a matrix of arrays, the problem is that the editor supports a limited size for variables.
I think that the max 3d array size supported by the editor is around 64x64x64, this must be tested.
So here is my crazy solution:
Create a custom record for SPACE OBJECTS
Assign to this record a POINT variable and all the object properties you need (size, resources, etc)
Create 1 array of type SPACE OBJECTS to store the list of planets or whatever (max size 8k, sorry)
Create a STRING array with 3 dimensions (try with 64x64x64, if it doesn't work reduce it until the game runs without errors)
Test the map and check if it runs correctly, if it doesnt reduce the 3d array index size
Remember that the memory size for variables is shared, if you make a too big array you will have less space for other variables
Now that you created all the needed variables start to generate the world:
Create your SPACE OBJECTS giving them a 3d position and all the properties
For each created space object you must now read the 3d position and approximate it to your 3d array (ex. if you have a map 128x128x128 you can divide each coordinate by 2 to find the correct position of the SPACE OBJECT inside the 3d array)
Use the 3d string array to store a textual list of your planets located on this 3d array position
Doing that you are grouping nearby SPACE OBJECTS.
Now that you have your 3d array you can easily find the planets near you:
Check the 3d array near your ship and read their list of index and use them to obtain the SPACE OBJECT informations you need (a more precise 3d position and all the properties)
Delete all created SPACE OBJECTS that are not near your ship
Interesting read using a string array. I've already have another method for checking objects/units the distances. Yous main unit/object isn't moving at all, it's all the other objects in the game moving around you. The problem I faced is that the map ITSELF is only about 64x64x64 for each player but the actual game can have a map of 1000x1000x1000 and beyond. All the objects positions are already controlled through record variables (vectors), I've simply created three groups with different timings for checking distances. Every 1 second for units within the 64x64x64 range, every 3-4 seconds for objects outside the 64x64x64 range but within about 128x128x128 range, and every 10 seconds or so for every other object. Although the number of distance checks is still very high it's been reduced greatly in the amount of checks per second. I've also separated everything into smaller triggers with threading so I ain't running long complex triggers. I would say about 1200 checks each second for 12 players or 100 for one player using just variables and no GetUnitPosition().
Here's my current map. It's just works correctly for one player right now and it don't look too pretty, but it works.
Still a lot of checks, consider that my method can be used with any map size. However you'll have approximation on the distance you create objects.
Basically you group all these objects in the 64x64x64 array, but the real position coordinates can have a higher multiplier like 20 and you get a 1280x1280x1280 space.
Then you can render sectors of this array that contain a space section. For instance with a multiplier of 20, each sector would have a size of 20x20x20.
BTW why are you moving the entire space around? Doing so you make the map work only in single player.
Why don't you reduce the size of units to fit inside the 128x128 map instead?
@ why are you moving the entire space around?
Because the map has a limited size. Instead of working within a map size of per-say 128x128 I can place objects anywhere, like at 1000x1000y1000z. The player can travel long distances without hitting a edge of a map. I can have 1000's of units across the map or more with no problems.
@ Doing so you make the map work only in single player.
Why?
@Why don't you reduce the size of units to fit inside the 128x128 map instead?
I don't really want to have reduced sizes. It doesn't look as nice.
You make the map work on single player only because the world is created around a single ship, you can't make more ships that navigate in the same world without interferring with other player world generation.
I already got why you did the move the space around the ship trick, however as I said you can shrink all the units, adjust the camera and all will look the same but with a bigger world. Doing that you won't need the move space around ship thing and you can make the map playable by more ships.
@Deaod
He can't use unit groups simply because they are used only store existing units, zandose is instead storing position of units and creating/deleting them when needed
Divide your world into small grid spaces, just large enough that a grid's diameter is equal to the twice the largest collision radius. If you need really big objects and small objects you can modify this so that large-small object pairs can collide on more grid points.
Store the current grid spot in each object and compare grid locations instead of doing the full vector distance calculation. Check the X and Y integer distance of both grid axes. If the difference is greater than 1 in either axis, do not check for collision.
This is a simple method of applying a fast integer box check to sieve the collision checks to near-hits only. You will get more speed by writing this in pure Galaxy. If C was available to us, you could write a few functions in Assembly for maximum speed.
Dammit the reply window crashed and I need to write everything again! I'll make this quick and dirty.
@DarkRevenant and Bibendus
At a later time, when I upgrade the movement system I'll add in a sector system for distance checks.
@DarkRevenant
For the optimization of "dX^2 + dY^2 + dZ^2 <= R^2" I am already aware of it and will add it at a later date. The problem is I am using GUI which doesn't have a math sign for ^2 so I have to use Pow(number, exponent). Also I and currently just working on getting it to work and don't care too much about minor optimization's. The major problem was 12000 or more distance checks a second which I thought was far to large for online play. I've since separated, threaded (actions which run in their own process instead of everything in one action and all the player waiting for it to finish), changed the timings for when things are checked by how far away they are (closer gets faster checks and far away objects take longer) and added in very small waits so there is no overload.
I use to have one trigger for updating the vectors of my unit, enemy units and distance checks every second. I've since change it to something like this:
@Bibendus - You make the map work on single player only because the world is created around a single ship, you can't make more ships that navigate in the same world without interferring with other player world generation.
I already have the work around for that. I've sectioned the map into different parts for each player and I'll apply a very large and flat black box to between each section. All maps have a height of -100 to +100. So a 64x64 map has space for each player to have 64x64x16. Later upgrades to the script will allow for more space with a 128x128 map.
I want to check if a vector is within range of another vector. Simple enough with "SquareRoot((x-x2)^2 + (y-y2)^2 + (z-z2)^2) <= 32" but I have 1000 vectors to compare to 12 vectors (12000 checks). Is there another way to go about this?
Bump
I don't think there is some magical way to calculate the distance of 12000 vector pairs without requiring some CPU time/ressources. If there is please tell me, but I wouldn't be too optimistic :) If these distances are static you can preload them, if they are not you should think about when you actually need the distances and only calculate them at that point (or a combination of these 2).
If you desperately need to calculate the distance of 1000 vectors compared to 12 vectors at the same time in game time without some lag, I can't think of any way to do that, but I have to say that I am not an expert for stuff like this (yet). But if I had this problem I wouldn't wait for a magic mathematic answer which probably doesn't exist for your general case and rather try to find another way of calculating them one by one or something. If there are characteristics which apply to all of your vectors (for example they are all on the same plane) then it is of course possible to reduce the amount of calculations your computer has to do, but I don't think it is possible for your general case.
@Bommes: Go
I was thinking along the same lines. I just put it out there to get any ideas. My current method for dealing with the problem is dividing the task in separate parts which are checked depending on need. For instance, bunches of units may get one single target for the whole group. Also, units far away, compared to close ones, will only get checks a fraction of the time, whereas closer units will get checks every 2 seconds or so.
@zandose: Go
Okay, sorry that I couldn't help :) Good luck getting it to work properly.
But I'm curious, why exactly do you need the exact distance of your vectors in a 3d space constantly? I really can't think of any game concept which would need something like this.
@Bommes: Go
Normally yes, but, my game concept is a large-scale space game, undecided on exact game play. The problem is maps have limited space and and loading large maps is annoying, so I went a different route and designed my own system for tracking object/units off the screen. Your unit is in the center of the screen always and instead of you moving the units move around you. The system allows me to determine which units are within your range to be shown on the screen.
Just need to overcome the high demand for processing everything.
"check if a vector is within range of another vector" doesn't make sense, since vectors are homeless. I assume you mean location. And it looks like you're actually just trying to detect collision.
I would link you to my physics engine tutorial, but I haven't updated it with the more efficient sweep-and-prune algorithm yet. So maybe I'll do that tonight.
In the mean time, note that it's faster to square the other side of the inequality than to take the square root.
@LosTacos: Go
No collision. I don't care about that at this time.
Sorry I have no education in vector so I don't understand "In the mean time, note that it's faster to square the other side of the inequality than to take the square root.", unless you mean use (v2-v1²)^0.5 instead of SquareRoot((VectorX*2)+(VectorY*2)+(VectorZ*2))? All I know is v=v1+ms*(v2-v1)/|v2-v1|
Also I have to go now so ttyl.
Explain better what are you doing and how you are doing it.
I'm trying to guess.
- You store inside an array a list of 3d coordinates for each object in your universe
- When the unit moves you periodically check for nearby objects comparing the 3d distance between the ship and each object of the whole list.
- If the object position is in range you create the unit
- If a created unit is not in range you destroy it
Am I correct?
@Bibendus: Go
Ah, hello there again. :)
That sounds about right.
So the main problem here is that you are using a list to store these coordinates, that means that your only way to find the points in your interested area is to loop on the whole list.
You must find a better way to index these coordinates so you can efficiently check only what you need.
For instance a good way would be to use a matrix of arrays, the problem is that the editor supports a limited size for variables.
I think that the max 3d array size supported by the editor is around 64x64x64, this must be tested.
So here is my crazy solution:
Now that you created all the needed variables start to generate the world:
Doing that you are grouping nearby SPACE OBJECTS.
Now that you have your 3d array you can easily find the planets near you:
Interesting read using a string array. I've already have another method for checking objects/units the distances. Yous main unit/object isn't moving at all, it's all the other objects in the game moving around you. The problem I faced is that the map ITSELF is only about 64x64x64 for each player but the actual game can have a map of 1000x1000x1000 and beyond. All the objects positions are already controlled through record variables (vectors), I've simply created three groups with different timings for checking distances. Every 1 second for units within the 64x64x64 range, every 3-4 seconds for objects outside the 64x64x64 range but within about 128x128x128 range, and every 10 seconds or so for every other object. Although the number of distance checks is still very high it's been reduced greatly in the amount of checks per second. I've also separated everything into smaller triggers with threading so I ain't running long complex triggers. I would say about 1200 checks each second for 12 players or 100 for one player using just variables and no GetUnitPosition().
Here's my current map. It's just works correctly for one player right now and it don't look too pretty, but it works.
@zandose: Go
Still a lot of checks, consider that my method can be used with any map size. However you'll have approximation on the distance you create objects.
Basically you group all these objects in the 64x64x64 array, but the real position coordinates can have a higher multiplier like 20 and you get a 1280x1280x1280 space.
Then you can render sectors of this array that contain a space section. For instance with a multiplier of 20, each sector would have a size of 20x20x20.
BTW why are you moving the entire space around? Doing so you make the map work only in single player.
Why don't you reduce the size of units to fit inside the 128x128 map instead?
@ why are you moving the entire space around?
Because the map has a limited size. Instead of working within a map size of per-say 128x128 I can place objects anywhere, like at 1000x1000y1000z. The player can travel long distances without hitting a edge of a map. I can have 1000's of units across the map or more with no problems.
@ Doing so you make the map work only in single player.
Why?
@Why don't you reduce the size of units to fit inside the 128x128 map instead?
I don't really want to have reduced sizes. It doesn't look as nice.
I recommend you use unitgroups.
Right on.
@zandose
You make the map work on single player only because the world is created around a single ship, you can't make more ships that navigate in the same world without interferring with other player world generation.
I already got why you did the move the space around the ship trick, however as I said you can shrink all the units, adjust the camera and all will look the same but with a bigger world. Doing that you won't need the move space around ship thing and you can make the map playable by more ships.
@Deaod
He can't use unit groups simply because they are used only store existing units, zandose is instead storing position of units and creating/deleting them when needed
Easy optimization: Get rid of the sqrt.
dX^2 + dY^2 + dZ^2 <= R^2
R^2 is precalculated.
Another easy optimization: Sectorize your space.
Divide your world into small grid spaces, just large enough that a grid's diameter is equal to the twice the largest collision radius. If you need really big objects and small objects you can modify this so that large-small object pairs can collide on more grid points.
Store the current grid spot in each object and compare grid locations instead of doing the full vector distance calculation. Check the X and Y integer distance of both grid axes. If the difference is greater than 1 in either axis, do not check for collision.
This is a simple method of applying a fast integer box check to sieve the collision checks to near-hits only. You will get more speed by writing this in pure Galaxy. If C was available to us, you could write a few functions in Assembly for maximum speed.
Dammit the reply window crashed and I need to write everything again! I'll make this quick and dirty.
@DarkRevenant and Bibendus
At a later time, when I upgrade the movement system I'll add in a sector system for distance checks.
@DarkRevenant
For the optimization of "dX^2 + dY^2 + dZ^2 <= R^2" I am already aware of it and will add it at a later date. The problem is I am using GUI which doesn't have a math sign for ^2 so I have to use Pow(number, exponent). Also I and currently just working on getting it to work and don't care too much about minor optimization's. The major problem was 12000 or more distance checks a second which I thought was far to large for online play. I've since separated, threaded (actions which run in their own process instead of everything in one action and all the player waiting for it to finish), changed the timings for when things are checked by how far away they are (closer gets faster checks and far away objects take longer) and added in very small waits so there is no overload.
I use to have one trigger for updating the vectors of my unit, enemy units and distance checks every second. I've since change it to something like this:
@Bibendus - You make the map work on single player only because the world is created around a single ship, you can't make more ships that navigate in the same world without interferring with other player world generation.
I already have the work around for that. I've sectioned the map into different parts for each player and I'll apply a very large and flat black box to between each section. All maps have a height of -100 to +100. So a 64x64 map has space for each player to have 64x64x16. Later upgrades to the script will allow for more space with a 128x128 map.
"The problem is I am using GUI which doesn't have a math sign for ^2 so I have to use Pow(number, exponent)."
Just do dX*dX + dY*dY + dZ*dZ <= Rn