[D's problem] It's time to rock your brain, fellows!

[Kazeon]

Illustration:

Hint:

It's some kind of circular array. Actually it's just normal array but we will return to the first index (1) when reaches max size (12).​

Problem:

Imagine there are 2 nodes in the list. The first node is static (non-moving), we call it "target". While the other one is dynamic, we call it "missile". The "missile" will be moved towards the "target" (moved to the next or previous node) periodically. However, it must have the shortest path as possible. Example:

1. If the "missile" starts at index-3 and the "target" is at index-8, the "missile" will be moved to the next node on every tick.
2. If the "missile" starts at index-8 and the "target" is at index-3, the "missile" will be moved to the previous node on every tick.
However,
3. If the "missile" starts at index-11 and the "target" is at index-3, the "missile" will be moved to the next node on every tick.​

Halt if "missile" and "target" have a same index.​

Quest:

Create an algorithm to solve the problem perfectly with the best efficiency as possible. Good luck.
(Note: you can write the code in JASS.)​

Disclaimer:

I haven't successfully solved this as well. This is not a challenge, it's more like I'm asking for help here.​

 

[Cokemonkey11]

The problem is much easier if you think about it in radians.

let s = start node
let t = target node
let d = val(t) - val(s) // eg 5 - 12 = -7

next we normalize d to be on [-n/2, n/2] - normally we'd change a radian value from [0, 2pi] to [-pi/2, pi/2].

To do this:

let n = 12 // so, we wish to normalize on [-6, 6]
let d_n = -7 + 12 = 5 // normalized version of d

since d_n > 0, use next_node strategy.

---

another example:

s = 1
t = 12
d = 12 - 1 = 11
d_n = 11 - 12 = -1

since d_n < 0, use prev_node strategy

---

Edit:

here's the code I use for normalizing radians in my map Hunter's Hall:

		public static method RadiansNormalizeHalf takes real n returns real
			set n = RadiansNormalizeHalfModulo(n)
			if n > bj_PI then
				return n - 2.*bj_PI
			endif
			return n
		endmethod
		
		public static method RadiansNormalizeHalfModulo takes real n returns real
			return ModuloReal(n, 2.*bj_PI - DELTA)
		endmethod

 

[Kazeon]

Well, this is the first time I'm failed to solve a problem

I will try your algorithm. I'm just trying to create a simple homing rocket missile actually. But it takes 2 days already for me to solve it ._. Thanks a lot for the help. You have just saved my sanity.

 

[Cokemonkey11]

No problem! I actually recall struggling with the same issue a few years ago

 

[rulerofiron99]

Not sure why exactly you want a tracking system with such a low resolution, but another very easy way would be to divide your angle by 30 (to scale 12), convert to integer to lose the decimals and convert back to give you one of the 12 exact angles.

For a smoother tracking system, there are two very easy methods (among others):
1. Make the dummy unit turn to face its target using some turn rate value and move in its facing direction.
2. Use a component movement system and just apply the acceleration in the direction of the target.

 

[Dr Super Good]

This is node pathing. Use a node based pathfinder.

Only difference is unlike node pathing where each node may have 1 or more connections, this problem has nodes with exactly 2 connections.

Codemonkey11's probably only works if the nodes are in a perfect circle. A node path finder could solve it if the nodes are any circular configuration, or even if there are other nodes branching off.

There will be some biased towards one direction if both ways round have the same distance. This however is minimal and probably will not be noticed.

 

[Cokemonkey11]

This is node pathing. Use a node based pathfinder.

Only difference is unlike node pathing where each node may have 1 or more connections, this problem has nodes with exactly 2 connections.

Codemonkey11's probably only works if the nodes are in a perfect circle. A node path finder could solve it if the nodes are any circular configuration, or even if there are other nodes branching off.

There will be some biased towards one direction if both ways round have the same distance. This however is minimal and probably will not be noticed.

I'm just trying to create a simple homing rocket missile actually.

DSG what kind of non-cartesian world do you live in?

 

[Nestharus]

I just assumed you were in a linked list and had to move either left or right depending on where the target is.

If it's an array, determining the direction is easy. If it's an arbitrary linked list where the pointers are unknown, then the direction can only be determined in O(n).


From either the missile's position or the target's position, loop until you find the other.

If you start at the missile, loop until you find the target. Be sure to count how many spaces you go.

local integer count = 0

loop
    exitwhen target != null // where is the target?

    set this = next
    set count = count + 1
endloop

// length is the length of the list
if (count < length/2) then
    // use next
else
    // use prev
endif

edit
Here is the O(1) solution for a circular linked list ; ).

Take a boolean array. Set 6-11 to true.

Take a linked list with n links. As you add links, number them from 0 to n - 1.

The target will be at a link with a number. The link the target is at is stored on the target, not the link. The link only contains the number.

The missile or whatever will be at another link with a number. Sub the numbers with absolute value. |n1 - n2|. Store this number on the missile.

While the missile is not on the same link as the target, if boolean array[number] is true, advance the unit by 1 on the list. If not true, go to the previous node on the list. Increment the number each time via (n + 1)%length.


There is a way to avoid the mod as well. If in the array you instead store it like this

[0] = 0
[1] = -1
[2] = -2
[3] = -3
[4] = -4
[5] = -5
[6] = 6
[7] = 5
[8] = 4
[9] = 3
[10] = 2
[11] = 1

Then rather than doing an if true, you simply store the number from the array.

missile.off = array[|n1 - n2|]

Then while missile.off != 0, go either next or prev. If the number is positive, go next and sub 1. If the number is negative, go prev and add 1.