Possible to make a smarter 'next men'?

[BomSite]

After some playing again, I want to give my 2 cents, I hope it can make it better.
In Wesnoth there is the option to press 'n' to see which men we have not already set and the spacebar to lock that unit if we don't want to set him.

Very frustrating is the way it works: click an unit, pres the spacebar to lock it, Wesnoth jumps to the next one.
But Wesnoth is taking the next unit on the same column of something like that.
Frustrating when you have 2 attacks each on the other side of the board,
then you go from the one to the other attack and back several times, that's jumpy.

Wesnoth should look for the next unit the most closed to the previous one.


I know, *everything* is possible, but is this one doable?
Thanks.

[Soliton]

Wesnoth should look for the next unit the most closed to the previous one.


I know, *everything* is possible, but is this one doable?

If you provide a proper algorithm definitely.

[BomSite]

Wesnoth should look for the next unit the most closed to the previous one.
I know, *everything* is possible, but is this one doable?

If you provide a proper algorithm definitely.

If i could, I will
but I can't

[Gambit]

Store the radii and compare them?

[Zarel]

Here's an O(n^2) algorithm that, while not perfect, is a decent way to traverse a set of units with minimal distance.

Let S be the set of units that haven't been [selected] before. Iterate through each unit, calculate W = average distance to every other unit in S minus distance from the currently [selected] unit. [Select] the next unit as the one with the largest W.

(Replace [select] with whichever operation you want to iterate through.)

It's not a solution to Travelling Salesman, but I think it might be a decent approximation. Maybe play with the weights a bit? Thoughts?

[solsword]

Why not just iterate over all possible next units (the set S) and select the one with the smallest Manhattan distance from the currently selected unit? Sure, it might be weird in some cases, but it'll be no less weird than the current algorithm, and it's O(n). Am I missing something here...?

Also, don't get me wrong: I don't expect devs to make this a priority. But the fact that it's not a high-priority issue doesn't make it a bad idea. I think that this is a good idea.

[thespaceinvader]

On this sort of issue in particular, if someone can come up with an appropriate and functioning patch, I have no doubt that it would be included, but i don't think there's a dev with time to do it at present.

[Alink]

Don't forget that any algorithm for this must also work for "next unit" and "previous unit", meaning that simply pick the nearest unit is not good, you will often cycle between 2.

Anyway, for this type of things, usually coming up with a relatively working (even if not optimal) algorithm is not the problem. The problem is more the less funny part of its implementation in wesnoth engine where units move, die, spawn, WML events change the whole map etc.. between your calls. The current dumb algo just record the last unit position and use an x,y order to get the next. Any smarter algo will probably need more bookkeeping, which must be controlled to stay consistent enough after external modifications etc..

I am not saying that there is no simple implementation (I suspect there is one and might try to check that code one day) but it's a problem of taking the time to code its details, more than a question of how to do it abstractly, even if find the best way may need some thinking.

[BomSite]

I don't know anything how WML events change the whole map etc..
But are the hex coordinates not enough, or change these also?
I will try a time: see also the screenshot below.

For the next unit (n):
->Lets say it is on [32,26]: this is the king, or I have set this one
->next player (n): Wesnoth search for the next unit, following the hex above [32,25], and than in a circle around the first unit
->Wesnoth finds nothing
->Wesnoth starts the next circle with [32,24] etc
->When he finds a unit that has not yet been set, this is temporary the new selected unit
->If I want to set that unit, I set that unit and this is the next middle point of circles
->If I don't want to set that unit, next unit (n) is just following the previous circle around previous unit

->One exception: if I select manually an other unit this one become the next center of the circles.


for the previous unit (shift+n): include a sort of log with the order of the units already selected AND skipped that turn
and delete this log when the next user begins to play

Don't forget that any algorithm for this must also work for "next unit" and "previous unit", meaning that simply pick the nearest unit is not good, you will often cycle between 2.

If you know which unit you want, I don't think you use 'next unit', but the mouse to select that unit. Isn't that easier? Or did you mean more?


something like that?


image:

[solsword]

I don't know anything how WML events change the whole map etc..
But are the hex coordinates not enough, or change these also?
I will try a time: see also the screenshot below.

For the next unit (n):
->Lets say it is on [32,26]: this is the king, or I have set this one
->next player (n): Wesnoth search for the next unit, following the hex above [32,25], and than in a circle around the first unit
->Wesnoth finds nothing
->Wesnoth starts the next circle with [32,24] etc
->When he finds a unit that has not yet been set, this is temporary the new selected unit
->If I want to set that unit, I set that unit and this is the next middle point of circles
->If I don't want to set that unit, next unit (n) is just following the previous circle around previous unit

->One exception: if I select manually an other unit this one become the next center of the circles.

The problem that Alink pointed out comes up here: if you've got two units right next to each other vertically, with the top unit adjacent only to the bottom one, your algorithm picks the top unit, then the bottom unit, then the top unit again. The same problem affects my suggested algorithm: I wasn't thinking about the whole problem to be solved here.

for the previous unit (shift+n): include a sort of log with the order of the units already selected AND skipped that turn
and delete this log when the next user begins to play

Although keeping a log can solve the problem above, it's a *lot* of work to write the code to do this, because, as Alink pointed out, your log has to deal with things like events removing or adding new units. Heck, there are probably plenty of events that kill a unit, and then add it back right where it was from a variable. These and other events have the potential to break your list, and thereby the functionality that you're trying to provide. So basically, any scheme that would include a log of which units you've visited is too complicated to be worth implementing. Now, a more clever stateless algorithm would be neat, but that's difficult to design, because the critera of "closeness to the last unit selected" is inherently stateful.

[BomSite]

The problem that Alink pointed out comes up here: if you've got two units right next to each other vertically, with the top unit adjacent only to the bottom one, your algorithm picks the top unit, then the bottom unit, then the top unit again. The same problem affects my suggested algorithm: I wasn't thinking about the whole problem to be solved here.

There is the spacebar for, to lock a unit, if you don't want to set him.

for the previous unit (shift+n): include a sort of log with the order of the units already selected AND skipped that turn
and delete this log when the next user begins to play

Although keeping a log can solve the problem above, it's a *lot* of work to write the code to do this, because, as Alink pointed out, your log has to deal with things like events removing or adding new units. Heck, there are probably plenty of events that kill a unit, and then add it back right where it was from a variable. These and other events have the potential to break your list, and thereby the functionality that you're trying to provide. So basically, any scheme that would include a log of which units you've visited is too complicated to be worth implementing. Now, a more clever stateless algorithm would be neat, but that's difficult to design, because the critera of "closeness to the last unit selected" is inherently stateful.

I see, difficult

[Zarel]

Why not just iterate over all possible next units (the set S) and select the one with the smallest Manhattan distance from the currently selected unit? Sure, it might be weird in some cases, but it'll be no less weird than the current algorithm, and it's O(n). Am I missing something here...?

Also, don't get me wrong: I don't expect devs to make this a priority. But the fact that it's not a high-priority issue doesn't make it a bad idea. I think that this is a good idea.

Yes, it's O(n), and it'll be reasonably efficient for the first few hops, but then it'll get gradually less and less efficient, and near the end it'll have some pretty big hops. I'm not sure it's all that much better than the current algorithm, since near the end it might be worse than the current random traversal (since the early small jumps might force the nodes left over to be huge jumps.

My O(n^2) algorithm produces a far better path, since the average-distance-to-other nodes factor prevents huge jumps from appearing near the end.

My proposal relies on a log as well; a list of units already iterated through, so they aren't included in the set of units that still need to be selected.

[taemyr]

How about implementing Christofides algorithm?

This should give a reasonable approximation of the traveling salesman.

The tour would have to be reevaluated each time a unit move though. (Or rather each time next is pressed after a unit have moved)

[solsword]

How about implementing Christofides algorithm?

This should give a reasonable approximation of the traveling salesman.

The tour would have to be reevaluated each time a unit move though. (Or rather each time next is pressed after a unit have moved)

Um... that looks pretty complicated to implement, although it's probably possible to work from example source somewhere. But the deeper problem is that it makes no guarantees about non-repetition when run multiple times. That is, it would need to be stateful in order to not repeat units. Which, as has been pointed out, would be a huge pain.

What we need is either a stateless algorithm that approximates traveling salesman (well, it doesn't actually have to go that far to be better than the current algorithm...) or someone willing to code one of the stateful algorithms suggested here (including Christofides', if they're up for it). I suspect that the former either doesn't exist or is extremely difficult to design...

Basically, I think that the complexity (and potential for bugs) involved in implementing a stateful algorithm means that it's not worth the dev's time to code this using a stateful algorithm, given the relatively minor benefit (eliminates a minor annoyance). So unless someone comes up with a stateless algorithm that gives a substantial improvement over the current one...

I do have an idea for a stateless algorithm that might give a *slight* average-case improvement over the current one. I don't think it's worth coding by the devs, but if someone is sufficiently interested, they could give it a try...

Each turn, calculate the arithmetic mean unit position for the player. Then, get all of the player's units and sort them using a stable sorting method over manhattan distance (or actual hex distance, if you care to calculate it) from that point (you sort from the same point every time spacebar is pressed within a single turn, so the algorithm is stateless). Jump to the unit before or after (depending on which key was pressed) the current unit within this sorted order.

The algorithm has some of the same problems as the current algorithm: i.e. there are situations in which it will jump back and forth across the map between units, and there are situations where a unit's move gives it a different placement in the list. I suspect that the first kind of situation is rarer in my scheme than in the current one, and I'm not sure about the second.

[Gambit]

I don't know what "stateful" is. But as for adjacent units and not wanting it to just flip back and forth:

A 2 tier array.

unit[x][y]

X would be whatever identifies the unit
Y would be a 0 or a 1.

On each push of n look for the next closest unit that hasn't already been selected (loop through the array). When the unit is selected set it's boolean to 1. If you can't find any that haven't been selected then set all the booleans to 0.

And of course everything resets when something moves or the player physically selects a unit.