2D logical/thinking challenge

[zapat 56]

Excuse me for the non-descriptive title, I need a pic to explain.

A) there are some positions given (not in a line, kind of randomly) the X

B) there are some units given (not necesseraly in formation) the O

What is the algorithm to tell the units which position to move to without crossing each other/with the least effort?

For a human its extremely obvious (the grey lines), but I am struggling hard to define the ruleset for coding.

- I tried to move them to closest, but its not good at all, it causes crossing

- I tried to move tho the point with the least dir difference, but units can face any direction, so there is no reference direction (or I couldn't find one, but it seemed a promising idea).

- I wanted to tell the leftmost to go to leftmost, but how to tell leftmost in a 360 degree environment?

So this would be the challenge... :)

[jshock 513]

Maybe sort the positions (from left to right, or vice versa) based on their x(horizontal) values, from one extreme to the other? And if the x is the same then secondary sort the y:

Position 1 = [1,2,0]
Position 2 = [4,1,0]
Position 3 = [-3,6,0]
Position 4 = [4,10,0]

Sort(farthest left to farthest right): Pos3, Pos1, Pos2, Pos4

Then do the same for the unit's position and the point "closest" in just the x direction the unit moves towards?

[killzone_kid 1332]

p = [p1, p2, p3, p4];

{generate positions from left to right} foreach p;

{place units from left to right; _x moveto (p select _forEachIndex)} foreach [u1,u2,u3,u4];

u1 goes to p1, u2 goes to p2 etc

[zapat 56]

Kk: it's in a dynamic environment so I don't have the possibility to place units or poses.

Jshock: it's in a dynamic environment so leftmost only helps on this picture.

But as I'm typing this there is an idea: the two farthest positions are the two extremes for sure. The direction of the line between them + 90° would be a good reference direction.

Then for a unit, the position with the smallest dir difference would be the best position, right?

[killzone_kid 1332]

If it is dynamic environment you have no control over, what are you going to do when positions and units align

X

X

X

X

O

O

O

O

that is extreme case but there could be other combinations when you cannot avoid line crosses.

[zapat 56]

Here is a video what I need it for:

If there is a cross, that's not a problem. Most of the time it's not extreme case, so I need an algo to make them move in the most natural fashion.

[jshock 513]

Well, I have an idea, but just can't put it to code just yet but I'm thinking an algorithm using both the relative direction to the position from the unit, along with the distance the unit is from that position.

These are the commands/funcitons I'm thinking will get the needed info:

https://community.bistudio.com/wiki/BIS_fnc_relativeDirTo

https://community.bistudio.com/wiki/distanceSqr

Where relativeDirTo would return a degree direction where straight in front of the unit is 0 degrees, 90 is straight right, 180 is straight behind, 270 straight left, and all the other directions in between. And then use the distance to decide between choosing the closer position or the further position, based on what you would want.

[killzone_kid 1332]

Maybe there is some answer there: http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

[zapat 56]

KK: okay, let's assume that I can determine if two finite line segments (any two X---O) cross or not.

How could I put this to work here? I'd need to check all combinations, to see which gives the least crosses, wouldn't I?

For some reasons I feel that the directionDifferences is the way to go, but I am getting too tired and have a jelly instead of my brain. :)

It seems so easy when I look on that picture, I just can't figure it out, and would love to see this in action. :D

---------- Post added at 10:32 PM ---------- Previous post was at 10:18 PM ----------

Ok, I have a solution, but a costy one:

The two farthest elements are always on the sides.

1. determine side poses

2. determine side units

3. units go to the side, where there is no cross

4. remove units, and poses from array

5. return to 1.

Step 1 and 2 are both O(n^2)/2. For a max 10 element array it's not a problem.

And I am still thinking on step 3...

And it's not always true: the two farthest elements are always on the sides. There can be a unit tailing away... Still this is the closest I got.

Edited January 28, 2015 by zapat

[killzone_kid 1332]

checked your vid, don't understand why you think units crossing each other path going for positions is not natural.

[zapat 56]

Maybe I should 've left it a bit longer. With Benny Hill music it's actually quite funny with the guys stepping on each other's feet all the time...

[dreadedentity 278]

Hello zapat! I have recorded a video for you. I saw this post about 2 hours after you made it and now, 28 hours later, I am here. Practicing my lines was grueling and empires rose and fell during this time. However, once the dust and nuclear fallout had settled, a single video remained. I bring that video to your attention now:

(watch in 720 or 1080)

[zapat 56]

DreadedEntity: lol for the description and wow for the work that went into this video. It's a great help indeed Thank you. I had a similiar idea at one time, but now I see where I failed.

I could make it work, but in a primitive way, so I'll recode according to your more sophisticated method, with one addition needed I guess:

We should calc the regression for the Xes and the Os separate, and transform them separate. Just look at this image. I think the regression line would be the blue one, thus an incorrect rotation would happen.

My solution was - as I said - a lot more primitive one: I don't calculate regression (which I should) but take the two farthermost points (which must be the two points from the sides) to gain a reference direction. Then I don't rotate the points, but I go for the leftmost if reference direction is in quadrant A and D and the bottom ones in quadrant B and C. Sometimes it fails though.

[Ed! 13]

Based on the video above

MEN = [man1, man2, man3, man4];
POSITIONS = [getPos pos1, getPos pos2, getPos pos3, getPos pos4];

_xTot = 0;
_yTot = 0;
{
_xTot = _xTot + ((getPos _x) select 0);
_yTot = _yTot + ((getPos _x) select 1);
}foreach MEN;

_avgMenPos = [_xTot / count(MEN), _yTot / count(MEN)];

_xTot = 0;
_yTot = 0;
{
_xTot = _xTot + (_x select 0);
_yTot = _yTot + (_x select 1);
}foreach POSITIONS;

_avgTargetPos = [_xTot / count(POSITIONS), _yTot / count(POSITIONS)];

_angle = ((_avgTargetPos select 0) - (_avgMenPos select 0)) atan2 ((_avgTargetPos select 1) - (_avgMenPos select 1));

_adjustedXMen = [];
{
_tmp = [(_avgMenPos  select 0) - ((getPos _x) select 0), (_avgMenPos select 1) - ((getPos _x) select 1)];
_adjustedXMen pushBack [_x, ((_tmp select 0) * cos(_angle)) - ((_tmp select 1) * sin(_angle))];
}foreach MEN;

_adjustedXTarget = [];
{
_tmp = [(_avgTargetPos  select 0) - (_x select 0), (_avgTargetPos select 1) - (_x select 1)];
_adjustedXTarget pushBack [_x, ((_tmp select 0) * cos(_angle)) - ((_tmp select 1) * sin(_angle))];
}foreach POSITIONS;

//sort by X
for[{_o = 0},{_o < count(_adjustedXMen)},{_o = _o + 1}] do
{
for[{_i = 0},{_i < count(_adjustedXMen)},{_i = _i + 1}] do
{
	if((_adjustedXMen select _o select 1) > (_adjustedXMen select _i select 1)) then
	{
		_a = _adjustedXMen select _o;
		_b = _adjustedXMen select _i;
		_adjustedXMen set [_o, _b];
		_adjustedXMen set [_i, _a];
	};
};
};

for[{_o = 0},{_o < count(_adjustedXTarget)},{_o = _o + 1}] do
{
for[{_i = 0},{_i < count(_adjustedXTarget)},{_i = _i + 1}] do
{
	if((_adjustedXTarget select _o select 1) > (_adjustedXTarget select _i select 1)) then
	{
		_a = _adjustedXTarget select _o;
		_b = _adjustedXTarget select _i;
		_adjustedXTarget set [_o, _b];
		_adjustedXTarget set [_i, _a];
	};
};
};

LINES = [];
{
_pos1 = getPos (_x select 0);
_pos1 set [2, 1];
_pos2 = (_adjustedXTarget select _foreachIndex) select 0;
_pos2 set [2, 1];
LINES pushBack (call compile format["{drawLine3D [%1, %2, [1,0,1,1]];}", _pos1, _pos2]);
}foreach _adjustedXMen;

onEachFrame {
{
call _x;
}foreach LINES;
};

https://dl.dropboxusercontent.com/u/56725922/nolinecross.Stratis.rar

http://i.imgur.com/cKV73ut.jpg

Edited January 30, 2015 by Ed

[zapat 56]

Have you just spared me like 2 hours?

I love you guys. :-)

[dreadedentity 278]

with one addition needed I guess:

We should calc the regression for the Xes and the Os separate, and transform them separate.

Yes, exactly! This was my intention, but I forgot to mention it in the video (I had to re-record it 9 times!!!). As an interesting side-note, after you graph your point, rotate it and graph the new point, when you draw a circle that goes through both points, this is how you create a perfect circle by hand in MS Paint. I tried to record this part and add it onto the video before I rendered, but there was a loud movie in the background audio :(

EDIT: I'd love to see another video like the one you posted above, but using the new algorithm :)

Edited January 30, 2015 by DreadedEntity

[zapat 56]

If Ed's code works fine, I can put it to work today/tomorrow. If I need to code it, it'll take a bit longer..

[Ed! 13]

It works when the positions and units are placed North/South from each other, but it doesn't when they are West/East from each other. It's something to do with those quadrants things I guess. Will fix it quick :P

Edit: I updated that script now. Should work for all crazy angles now.

Edited January 30, 2015 by Ed

[dreadedentity 278]

Quadrants are a little bit of an issue, fortunately there's an easy way to get around that. I drew another picture to help clarify things:

http://i.imgur.com/a5wfXHv.png (844 kB)

Basically, you're trying to create a "local" virtual plane, so your calculations don't have to work with huge numbers, then rotate that. Going back to quadrants, you can tell which quadrant you should end up by looking at the slope of your line of best fit. The idea is to keep your virtual graphed points in either Q2 or Q1 and never have your points in the other 2 quadrants. We can do this by looking at graphed points that are placed into the wrong quadrant:

In Q2 you are trying to rotate your local plane to 0°, but,

In Q1 you are trying to rotate your local plane to 180°. If you standardize the rotation, all of your points will end up in either Q2 or Q3 no matter if they started in Q1 or Q2 with a positive or negative regression.

EDIT: Picture links fixed

Edited January 30, 2015 by DreadedEntity