Next unit cycling should avoid bouncing around map

[rrenaud]

Sometimes I have two separate groups of units fighting at about the same vertical position on the map. When I cycle through units with the n key, the focus bounches violently through the map repeatedly to and from each cluster, and it's a bit disorienting.

The game should not neccesarily scroll left to right and then top to bottom all the time. Ideally, the game would do something like a travelling salesman approximation to figure out how to scroll through units minimizing the total scrolled distance. But simply picking the ordering by minimizing the difference from both left to right, up to down or up to down, left to right would probably almost completely avoid the bouncing effect and would be (I assume...) fairly straight forward to implement.

Does this seem like something that would be accepted if I coded up the patch? I want some revenge on my failed patch at https://gna.org/patch/?589

[commanderkeen]

Why not? If you make your own patch I don't see how people wouldn't accept it. Sure, it's not something most people care about, but your idea does sound better, and since you have done the code...

I think it sounds good, less scrolling, especially during healing before your turn, would be good.

[Ken_Oh]

I wouldn't like it. When I press "n", I more often than not want to see the unit's whole movement range. I could see this leading to a lot of useless scrolling to see where a unit could move, simply because it's near another unit.

I don't find jumping around disorienting at all, though I think this would be nice as an option for those that do.

[irrevenant]

I wouldn't like it. When I press "n", I more often than not want to see the unit's whole movement range. I could see this leading to a lot of useless scrolling to see where a unit could move, simply because it's near another unit.

I believe rrenaud meant that the screen would still 'jump to' (ie. autocentre on) the newly selected unit, just that the algorithm would select the nearest unit to jump to, rather than the next one to the right. You would still have the best possible view of where a unit can move.

I'm not sure how such an algorithm would work (eg. what would stop the algorithm from leaping back and forth between the same few units) but it sounds pretty handy.

[Ken_Oh]

My bad entirely.

[Darth Fool]

It sounds like a good idea if you can find a reasonably quick and good algorithm for approximating a traveling salesman solution. Whether it gets accepted will, of course, depend on the details and how well it works.

[Eleazar]

Ideally, the game would do something like a travelling salesman approximation to figure out how to scroll through units minimizing the total scrolled distance. But simply picking the ordering by minimizing the difference from both left to right, up to down or up to down, left to right would probably almost completely avoid the bouncing effect and would be (I assume...) fairly straight forward to implement.

Does this seem like something that would be accepted if I coded up the patch? I want some revenge on my failed patch at https://gna.org/patch/?589

I would like to see something like this. Such "intelligent" scrolling would also be nice during the healing phase, if you have a few healers.
The unnecessary bouncing around annoys me too.

[tsr]

I'd say that the traveling salesman is an extreme overkill to accomplish that.

It would be enough to:
1. get all units with actions left in a two dimensional array
2. pick the first one in the list and focus on that and mark it as already focused
3. for the next one cycle through the array
3.1 award each unit (that is not marked as already focused) points according to how far it is from the current unit and keep a pointer for the unit with fewest points (where 1 point is for each difference in x and y)
3.2 if a unit is reasonably within reach (say 4 points) pick that and continue from 3 otherwise pick the unit with least points and continue from 3.
4. if there are no units left to focus on clear the already focused flag on all units and do it all again.

There is no need to find the path with least total movement. What we are trying to do is for the units that are close to each other to get selected before units that are far away do.

/tsr

[Jetrel]

And it should be noted that it's okay if on very rare occasions, the code fails on certain corner cases, and flies across the map to a distant unit, because that's no worse than what we have now.

[RCG Tiburon]

can we also have some sort of transition? I know when I hit 'n' it takes me a second to figure out my position relative to the previous one. maybe scrolling at double speed or something like that.

[Eleazar]

maybe scrolling at double speed or something like that.

i think scrolling would be good

[irrevenant]

Thought:

We don't necessarily want to move to the strictly nearest unit, we just want to handle things in sensible clusters.

I can think of two ways to do that:

1. Just divide the map up into sectors (where a sector ~= 1 screen) , scroll through all the units in sector 1, then all the units in sector 2, etc. in a left->right, up->down pattern.

2. Get a bit more fancy and figure out where the clusters of units are, and work through the clusters in a left->right, up->down pattern. I dunno the math, I guess there's probably statistical functions that'd work this out...

[MSchmahl]

Why wouldn't this simple algorithm work?

1. Select an arbitrary unit to start the unit list (possibly the leftmost, or uppermost, or the leader).
2. While there are units left to be added to the list:
2.1. Find the unit, that is not in the list, closest to the last unit added.
2.2. Add that unit to the list.

I believe this is called the "nearest-neighbor" algorithm.

[rrenaud]

Yeah, I will implement nearest neighbors, once I get some free time.

From

http://en.wikipedia.org/wiki/Travelling ... an_problem

"In 2D Euclidean TSP, NN algorithm result in a length about 1.26*(optimal length)."

[JW]

Yes, please do this. Scrolling would also be nice, but just this would be an improvement. Even just scrolling would be better, but let's jump 1 hurdle at a time. (Unless you're great at jumping over coding hurdles and can do both at once!)