Jump to content
zooloo75

Scripting Competition [JUNE 10-30]

Recommended Posts

I feel bi-weekly scripting competitions here and there would be beneficial to the community, being educational and rewarding to everyone.

We're all able to judge and critique each other's work as well as ask questions.

 

To keep this short and to pilot the idea, here's a problem due by the end of the month:

Create a system which allows the retrieval of static objects (objects that won't move) that were placed in the editor (any object from allMissionsObjects), given a position and a radius (in meters).

Input example: [[5165.23, 2501.01, 0], 50] call TAG_GetNearObjects;

 

The more optimized, the better.

 

Share your solution as a zipped mission or just paste the code.

  • Like 2

Share this post


Link to post
Share on other sites


_xAxis = _this select 0;

_yAxis = _this select 1;

_zAxis = _this select 2;

_radius = _this select 3;

_convert3D = [_xAxis,_yAxis,_zAxis];

_Objects = _convert3D nearObjects _radius;

_Objects;

Share this post


Link to post
Share on other sites
_xAxis = _this select 0;
_yAxis = _this select 1;
_zAxis = _this select 2;
_radius = _this select 3; 
_convert3D = [_xAxis,_yAxis,_zAxis];
_Objects = _convert3D nearObjects _radius; 
_Objects;

*facepalm* You aren't even following the rules. You didn't include any tests or results from BIS_fnc_codePerformance, etc. Way to show off your ego.

 

Sugg. to zooloo: how about providing more structured data as the output of the function?

Filter for buildings, etc., and print out their formatted data (in table or so).

Also, it'd be cool for the function to actually identify towns within a radius and associate the buildings with those towns, so you can see what each town / location consists of...

 

Just a thought.

Share this post


Link to post
Share on other sites

It's an extremely simple problem... Although my solution didn't include ignoring non-statics. Unfortunately..

Share this post


Link to post
Share on other sites

As far as optimization goes, try to strive for a low algorithmic complexity. I've managed to create a system (still WIP) which achieves the goal in O(1) time.

Complexity is O(n) now.

Edited by zooloo75

Share this post


Link to post
Share on other sites


params ["_pos", "_rad"];

(allMissionsObjects select {(_pos distance _x) < _rad})

Share this post


Link to post
Share on other sites

You call that optimized!?   :lol:

// [getPos player, 50] call fn_nO;

fn_nO = {
    params["_p", "_r"];
    _p nearObjects _r; 
};

(Doesn't grab mission objects, but is waay shorter than that first script heh.)

Share this post


Link to post
Share on other sites

private ["_xyz","_radius","_Objects"];
_xyz = _this select 0;
_radius = _this select 1;
_Objects = _xyz nearObjects _radius;
_Objects;

Executes in 4 m/s in kavala

 

1 m/s faster.

private ["_Objects"];
_Objects = (_this select 0) nearObjects (_this select 1);
_Objects;

Executes in 3 m/s in Kavala

With a value of 50 in radius.

1 m/s

Thats about as simple as it can get.

Share this post


Link to post
Share on other sites

yeah but u guys (and me too :) )dont get editor placed objects only...

 

see the notes of nearObjects wiki entry:

If you use the first example, it will return objects many more objects such as pollen, honeybees and crucially, triggers. Triggers will show in the returned array as "no shape" but you can use typeOf to get the classname, which will give "EmptyDetector". This will not return objects that don't have classnames such as plants, stones and some map objects like vehicle wrecks. nearestObjects will find objects without classnames.

  • Like 1

Share this post


Link to post
Share on other sites

Just a tip: simple is not the same as optimized. Let's strive for a solution that can perform efficiently on every frame. In those regards, let's test with a radius of 50.

Thank you all for participating.

Share this post


Link to post
Share on other sites


_mission_str = loadFile "mission.sqm";

(((_this select 0) nearObjects (_this select 1)) select

{

((_mission_str find (typeOf _x)) > -1)

};)

that should return editor placed objects only but only works if mission.sqm is not binarized.

Share this post


Link to post
Share on other sites
that should return editor placed objects only but only works if mission.sqm is not binarized.

I tested nearObjects while standing next to a bunch of chairs I'd put down in the editor and none were detected.  In fact I had to increase the radius to 500 before I detected anything and then it was just power lines.  This was on Tanoa.

Share this post


Link to post
Share on other sites

With a 50 meter radius, my system can retrieve nearby mission objects within 0.0227ms.

Still WIP, not filtering true distances yet, but it's an approximation right now.

Share this post


Link to post
Share on other sites

With a 50 meter radius, my system can retrieve nearby mission objects within 0.0227ms.

Still WIP, not filtering true distances yet, but it's an approximation right now.

The performance times are relative to the PC spec, you cannot use it for anything but to compare one code to another on the same machine.

  • Like 6

Share this post


Link to post
Share on other sites

The performance times are relative to the PC spec, you cannot use it for anything but to compare one code to another on the same machine.

Of course, but relative to using traditional methods such as nearestObjects or allMissionObjects, my system is much faster.

What I have right now is unfinished and will be a bit slower than it is now.

It might be too early to do comparisons yet, but I think I'm at a good start for the requirements of the competition.

So far seeing about <1 millisecond execution time with my system vs traditional methods which yield approximately 30ms+ with similar arguments. This may vary throughout the development of the system. Hopefully I can get it even faster.

Execution time is tied to the executing machine, but algorithmic complexity is a major factor, and that's what I'm trying to improve upon to reduce the amount of time it takes to retrieve nearby static objects.

  • Like 1

Share this post


Link to post
Share on other sites

Of course, but relative to using traditional methods such as nearestObjects or allMissionObjects, my system is much faster.

What I have right now is unfinished and will be a bit slower than it is now.

It might be too early to do comparisons yet, but I think I'm at a good start for the requirements of the competition.

So far seeing about <1 millisecond execution time with my system vs traditional methods which yield approximately 30ms+ with similar arguments. This may vary throughout the development of the system. Hopefully I can get it even faster.

Execution time is tied to the executing machine, but algorithmic complexity is a major factor, and that's what I'm trying to improve upon to reduce the amount of time it takes to retrieve nearby static objects.

But is your algo readable and maintainable enough compared to BIS functions?

Sometimes readability and maintainability are a must because you will not be the only working with that particular piece of code.

 

Like ,for Javascript, there's an endless debate in for loop vs .map method. The first one is the fastest out of all of them, but once the code gets complicated, it looks like a mess. Needs a compromise.

 

It'd be great if you've posted some data as to compare yours vs BIS'.

Share this post


Link to post
Share on other sites

But is your algo readable and maintainable enough compared to BIS functions?

Sometimes readability and maintainability are a must because you will not be the only working with that particular piece of code.

Like ,for Javascript, there's an endless debate in for loop vs .map method. The first one is the fastest out of all of them, but once the code gets complicated, it looks like a mess. Needs a compromise.

It'd be great if you've posted some data as to compare yours vs BIS'.

You can decide that once I release the solution.

The system is quite abstracted, to use it is very easy. Code readability is very straightforward as well.

Share this post


Link to post
Share on other sites

Download: http://files.bitdungeon.org/arma/examples/DataIndexing.Tanoa.zip

Work-in-progress!

 

Here's some performance results with my method vs the traditional approach.

I call my system, "Object Indexer".

Filtering is to return objects only within the specified radius in my method, else it returns more objects than expected (an approximation -- which may not be a problem for certain uses).

 

Performance diagnostics:

ObjectIndexer: true\nFiltering: false\nFPS: 44.9438\nObjects: 193
ObjectIndexer: true\nFiltering: true\nFPS: 44.8179\nObjects: 32
ObjectIndexer: false\nFiltering: true\nFPS: 41.1311\nObjects: 32

ObjectIndexer: true\nFiltering: false\nFPS: 46.7836\nObjects: 10
ObjectIndexer: true\nFiltering: true\nFPS: 45.584\nObjects: 0
ObjectIndexer: false\nFiltering: true\nFPS: 41.5584\nObjects: 0

ObjectIndexer: true\nFiltering: false\nFPS: 50.3145\nObjects: 35
ObjectIndexer: true\nFiltering: true\nFPS: 49.0798\nObjects: 6
ObjectIndexer: false\nFiltering: true\nFPS: 43.3604\nObjects: 6

ObjectIndexer: true\nFiltering: false\nFPS: 80.8081\nObjects: 67
ObjectIndexer: true\nFiltering: true\nFPS: 79.2079\nObjects: 31
ObjectIndexer: false\nFiltering: true\nFPS: 68.0851\nObjects: 31

ObjectIndexer: true\nFiltering: false\nFPS: 47.3373\nObjects: 115
ObjectIndexer: true\nFiltering: true\nFPS: 46.7836\nObjects: 42
ObjectIndexer: false\nFiltering: true\nFPS: 42.8954\nObjects: 42

ObjectIndexer: true\nFiltering: false\nFPS: 76.9231\nObjects: 274
ObjectIndexer: true\nFiltering: true\nFPS: 73.3945\nObjects: 32
ObjectIndexer: false\nFiltering: true\nFPS: 65.0406\nObjects: 32

Here's my test code (it's sloppy, I know):

Test_AllMissionObjects = allMissionObjects "Logic";
{
    [_x] call ObjectIndexer_AddObject;
} foreach Test_AllMissionObjects;

MethodSwitch = true;
Filtering = false;
Test_Text = "";
player addAction ["Switch Methods", {MethodSwitch = !MethodSwitch}];
player addAction ["Toggle Filtering", {Filtering = !Filtering}];
player addAction ["Copy Diag", {copyToClipboard Test_Text}];

["Test_NearObjects", "onEachFrame", 
{
    _objects = [];
    if(MethodSwitch) then
    {
        _objects = [getPosATL player, 100, Filtering] call ObjectIndexer_GetObjectsInRadius;
    }
    else
    {
        _objects = Test_AllMissionObjects select { _x distance (getPosATL player) <= 100 };
    };
    Test_Text = format ["ObjectIndexer: %1\nFiltering: %2\nFPS: %3\nObjects: %4", MethodSwitch, Filtering, diag_fps, count _objects];
    hintSilent Test_Text;
}] call BIS_fnc_addStackedEventHandler; //Could have used the new EachFrame handler here, meh.
  • Like 1

Share this post


Link to post
Share on other sites

Thats an interesting solution. Looks like it requires some intricate knowledge about how the maps are actually stored though.

Share this post


Link to post
Share on other sites

Thats an interesting solution. Looks like it requires some intricate knowledge about how the maps are actually stored though.

How so? Please elaborate on what you mean. 

Share this post


Link to post
Share on other sites

I can't say I've ever dealt with the WorldSize tile information from config files what does it correspond to? How many tiles exist on the map? that are a 100M * 100M?

Share this post


Link to post
Share on other sites

I'm a little bit late, but...

As far as optimization goes, try to strive for a low algorithmic complexity. I've managed to create a system (still WIP) which achieves the goal in O(1) time.

Complexity is O(n) now.

How is that? If you have linear complexity, then it takes linear (not constant!) time to execute algorithm. And as long as it has linear complexity it is always easier to just loop through what allMissionObjects returns than spend additional time to create additional data structure (which is, in general, quite not optimal in your case).

 

What you really need is probably KD trees. You can build a tree in O (N log N) and find neighbors in O (log N).

The code? Check Â§21.2 of Numerical recipes, 3rd Ed.

  • Like 1

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now

×