Possible to make a smarter 'next men'?

[solsword]

Stateful means the algorithm you just suggested . It means any algorithm that has to keep track of some value for each unit. As already pointed out, any such algorithm is complicated, because you have to worry about things like units dying, or being screwed with by events.

Also, the algorithm you suggested is basically the same one that I suggested, with the necessary state information added. Apart from requiring state, it's bad for the same reasons: it's a greedy algorithm, and thus might provide a very bad solution to the traveling salesman problem. To put it in less "I've taken an algorithms class" terms: your algorithm only considers what is optimal in the moment. This means that over the entire turn, it may produce unwanted results. For example, it may take a bunch of short jumps at the beginning, but then be forced to make a very long jump at the end because it didn't "think ahead". Some of the smarter algorithms suggested here are able to avoid or limit these forced longer jumps in clever ways.

A concrete example: let's say that you've got a line of 5 units from x = 1 to x = 5. Now let's say that you're iterating based on their ids, and so you happen to start with the second unit (at x = 2). And let's also say that you break ties to the left (note that both of these assumptions can be changed, but a new bad situation can be found for any counter-assumptions), so the next unit you select is at x = 3. Continuing, you next get the unit at x = 4, then x = 5, and finally x = 1. You've jumped 4 times, with distances of 1, 1, 1, and 4. Your average jump distance is 7/4. If you had been smarter, though, you could have gotten an average jump distance of 1 (by starting at either end of the line). So even though you chose what looked like the best move at each step of the way (you were "greedy" in algorithms terms) the result was worse than it could have been. Something like Zarel's algorithm would have started at one end of the line, in this case, and achieved that better result.

[Gambit]

Stateful means the algorithm you just suggested .

LOL oh man.

It means any algorithm that has to keep track of some value for each unit. As already pointed out, any such algorithm is complicated, because you have to worry about things like units dying, or being screwed with by events.

Not if the array is reset every time the player does something other than push N or spacebar (because then the whole next unit chain is broken anyway).

For a unit to die on their turn the player would have had to attack. Reset it at the end of every attack and move
And by reset I mean re-store all units that have valid moves and attacks left and that haven't been spacebared.


Except for the part where the unit is highlighted this whole thing CA(ctually)BD (very simply) in WML


As far as algorithm greed goes, I don't see why it's a problem if jumps get further with each successive push of N. It's to be expected isn't it? As you use up the closest units? 1,1,1,4 is IMO ideal.
At any rate I abandoned discussing how to actually find the next unit right after my first post. The whole thing got way over my head. I just thought that the part of avoiding repetition is being over complicated.

[Alink]

Here are random comments about some ideas that I saw here:
- We want a reliable order, if we have N units, after N steps we will have visited all units once and be back at the initial unit.

- I don't think that we want to progressively grow an order each time the user hits "next unit". The reason is that if the user clicks around and sometimes uses "next unit", he will create himself a messy order. Unless you want to create separate sub-lists and stitch them together later, but that looks complicated.

- So I think it's better to create a good cycle passing by all units at the beginning of the tour (or only at the first "next unit" event). Units moves will sometimes degrade the quality of this cycle, but I suspect that, most of times, it will not be a problem (except maybe for fast flying units). Note that some moves may also reduce total distance and our initial solution was probably not optimal anyway.

- I don't really see why people are so focused on performance. N is always small here and it's only simple math. Ok avoid O(N!), but don't bother considering O(N^3) better than O(N^2). Any scrolling will probably cost a lot more than this (there is a lot of pixels to draw, you know). Anyway, computing this only once by turn certainly give you all the time you need.

- About this distance thing, we only need the euclidian distance here, because we want to reduce scrolling. So forget hex and manhattan distance. Depending of the algo, you may even skip the square root if it was your concern. Note that it will use the fact that horizontal distance is less important because of the imbrication of hexes and their shapes. But if you really want fine tuning, don't forget that unit near border sometimes causes less scrolling

- The main problem of moving the view too much is that it disorients the user. I suspect that maximizing the intersection of the old and new view helps. That means that on most screens (and esp. widescreens) horizontal scrolling is slightly better. You may even use that as distance. Also note that the scrolling engine actually copy-paste that shared part instead of redrawing it, so it's also cheaper(but that's not important, just mention that funny fact that the rendering engine and human eye have same interest)

- I said that the bookkeeping was some work, but that doesn't mean that you must avoid it, it may even be needed. Using location make it hard to follow units and use id is a bit fragile. I thought about a simpler implementation: just store a "numbered ticket" in each unit (yes, you can add simple info in units) and use that to find the next one. Of course, refresh it each turn. Unit deaths are not a problem and you can give to new spawned unit an 'unassigned number' that you will resolve later. Finding a good place place to insert one new unit seems easy, just try each N possible places and compare how total distance changes. Obviously, that means using real numbers, so insertion between two is always possible.

- You still need to to resolve a salesman problem, but IMO no need to try too much, just do better than the current order most of the times. I am not familiar with all the algos for this, but a possible simple way somehow guaranteeing to accomplish that goal, would be to start with the dumb order and try random changes(maybe with some heuristic) until the last X changes failed to improve the solution. Starting with a better initial order, like one generated by "pick nearest", will probably give better results but not sure if worth it.

[Zarel]

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.

Um, that's a 1D array.

unit[x] = y

Although I'd personally just use

unit = {x}

where {x} is the set of units that haven't been selected yet. Encoded however you want.

[Zarel]

- You still need to to resolve a salesman problem, but IMO no need to try too much, just do better than the current order most of the times. I am not familiar with all the algos for this, but a possible simple way somehow guaranteeing to accomplish that goal, would be to start with the dumb order and try random changes(maybe with some heuristic) until the last X changes failed to improve the solution. Starting with a better initial order, like one generated by "pick nearest", will probably give better results but not sure if worth it.

I still think that my algorithm, namely:

• 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?

is a better algorithm than anything else proposed thus far.

- I don't really see why people are so focused on performance. N is always small here and it's only simple math. Ok avoid O(N!), but don't bother considering O(N^3) better than O(N^2). Any scrolling will probably cost a lot more than this (there is a lot of pixels to draw, you know). Anyway, computing this only once by turn certainly give you all the time you need.

Well, it's not like Wesnoth doesn't have issues with algorithmic complexity. I remember scenarios, such as the third-to-last NR scenario, having an AI turn that took ages because they had 100+ units. And clicking to attack takes a ridiculous amount of time, since the damage calculations weren't optimized for attacks like 50-100 ranged impact magical.

[Alink]

Well, it's not like Wesnoth doesn't have issues with algorithmic complexity. I remember scenarios, such as the third-to-last NR scenario, having an AI turn that took ages because they had 100+ units. And clicking to attack takes a ridiculous amount of time, since the damage calculations weren't optimized for attacks like 50-100 ranged impact magical.

There is strictly no link between this simple geometrical problem and all the stuff done by AI, WML, rendering etc. As I said it's just simple arithmetic operations. The number of such operations done during an AI turn in NR is astronomical compared to what we need to make this works. In fact, it helps my point: if a turn take 10 minutes and the user has 100(!) units to move, then it's ok to take a fraction of second to help him with a good unit's order.

I hope you didn't misunderstand my remark "I don't really see why people are so focused on performance". I am very focused on wesnoth's performance and often optimize it. What I meant is: for this specific isolated problem and because I don't expect it to be a concern here. If it becomes one, we may optimize it later but don't start to focus too much on it. Better concentrate on what is best for user and what is simplest for coder.

[Zarel]

And clicking to attack takes a ridiculous amount of time, since the damage calculations weren't optimized for attacks like 50-100 ranged impact magical.

Whoops, I meant "And clicking to attack in Wesband".

I still think that my algorithm, namely:

• 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?

is a better algorithm than anything else proposed thus far.

Whoops, I forgot to ask for feedback on my algorithm, or at least some idea of whether or not people agree that my algorithm is a good compromise between performance/complexity and efficiency.

There is strictly no link between this simple geometrical problem and all the stuff done by AI, WML, rendering etc. As I said it's just simple arithmetic operations. The number of such operations done during an AI turn in NR is astronomical compared to what we need to make this works. In fact, it helps my point: if a turn take 10 minutes and the user has 100(!) units to move, then it's ok to take a fraction of second to help him with a good unit's order.

The problem is, will it be a fraction of a second? With 100 units, the difference between O(n^2) and O(n^3) can be the difference between a fraction of a second, and a full minute. Would it be ok to take a minute to help him with a good unit's order? 100 units would take nearly two hours!

I hope you didn't misunderstand my remark "I don't really see why people are so focused on performance". I am very focused on wesnoth's performance and often optimize it. What I meant is: for this specific isolated problem and because I don't expect it to be a concern here. If it becomes one, we may optimize it later but don't start to focus too much on it. Better concentrate on what is best for user and what is simplest for coder.

Oh, I know. I'm somewhat subject to premature optimization. I'm just saying, I can easily see a solution for an NP-hard problem causing performance problems on Wesnoth.

[Alink]

The problem is, will it be a fraction of a second? With 100 units, the difference between O(n^2) and O(n^3) can be the difference between a fraction of a second, and a full minute. Would it be ok to take a minute to help him with a good unit's order? 100 units would take nearly two hours!

What I was saying is that even O(N^3) with N=100 should be below the second. I think that any years old computer can do millions of simple math stuff in that time. And this will be for the raw algo without any optimization (early loop break, caching, heuristic...) and with the unrealistic case of N=100 human-controlled units. But anyway, I was merely suggesting not focusing too much on performance before any test showing that it's a real problem (which can't be solved by simple optimization). Besides, since we speak about big O, for such small N, there is probably already other stuff bigger than O(N^3) done once by turn (if you allow N to be something else than units)

Oh, I know. I'm somewhat subject to premature optimization. I'm just saying, I can easily see a solution for an NP-hard problem causing performance problems on Wesnoth.

I agree but don't forget (and I think you don't) that it's finding the optimal solution which is NP-hard. We mainly want to do better than the current system or even just fix bad cases like dumb crossing or back-and-forth in the cycle etc. I suspect that such goal is much simpler.

[Sapient]

if you choose the unit order at the beginning of turn, that wouldn't account for new units created via WML (for example, freed mermen in bay of pearls).

personally, I prefer the current way it works over all of the proposals made so far.

The nice thing about a stateless traversal system is it is a lot harder to break it, and thus less bugs/maintenance (KISS).

[Zarel]

What I was saying is that even O(N^3) with N=100 should be below the second. I think that any years old computer can do millions of simple math stuff in that time. And this will be for the raw algo without any optimization (early loop break, caching, heuristic...) and with the unrealistic case of N=100 human-controlled units. But anyway, I was merely suggesting not focusing too much on performance before any test showing that it's a real problem (which can't be solved by simple optimization). Besides, since we speak about big O, for such small N, there is probably already other stuff bigger than O(N^3) done once by turn (if you allow N to be something else than units)

True, but O(N^3) could very well result in more than 1 million operations, which is the worry. Plus, multiplication isn't a simple math operation (it's about ten times slower than addition), and you have to do it twice to find quadrance for each iteration. And if you're looking for distance, then you have to find a square root. Which is an extremely slow operation. And you do it once per iteration. It adds up.

I agree but don't forget (and I think you don't) that it's finding the optimal solution which is NP-hard. We mainly want to do better than the current system or even just fix bad cases like dumb crossing or back-and-forth in the cycle etc. I suspect that such goal is much simpler.

Oh, yes, but my implication was that since the problem is NP-hard, solutions that are "good enough" could very well still unbearably slow.

if you choose the unit order at the beginning of turn, that wouldn't account for new units created via WML (for example, freed mermen in bay of pearls).

personally, I prefer the current way it works over all of the proposals made so far.

The nice thing about a stateless traversal system is it is a lot harder to break it, and thus less bugs/maintenance (KISS).

The thing about the current way is that nearly every other proposal would be better. Accounting for new units isn't a big deal. You can either recalculate, or add them to the end of the list.

[Sapient]

You say "better" as if there were not any tradeoffs worth considering. Code maintenance is a real issue. Every time a unit is selected (such as by pressing 'n') it triggers the "select" event. During the select event, such actions as unstore_unit, unit, teleport can occur (although it would probably be a bad idea to do so). Preventing any of these things from breaking your unit traversal algorithm is one problem, maybe even an easy problem in your opinion. Preventing any *future* code from breaking your unit traversal algorithm, however, is an ongoing problem-- a problem which does not exist with the current stateless algorithm.

[Zarel]

You say "better" as if there were not any tradeoffs worth considering.

Ah, yes, I thought you were talking purely about the best traversal order. Yes, a better algorithm has downsides, but I don't think they're so bad that we should stick with the current algorithm.

Code maintenance is a real issue. Every time a unit is selected (such as by pressing 'n') it triggers the "select" event. During the select event, such actions as unstore_unit, unit, teleport can occur (although it would probably be a bad idea to do so). Preventing any of these things from breaking your unit traversal algorithm is one problem, maybe even an easy problem in your opinion. Preventing any *future* code from breaking your unit traversal algorithm, however, is an ongoing problem-- a problem which does not exist with the current stateless algorithm.

With most of these algorithms, strange actions may result in an undocumented order, but if done properly, it wouldn't be any worse than the current order.

[BomSite]

You can either recalculate, or add them to the end of the list.
(...)
With most of these algorithms, strange actions may result in an undocumented order, but if done properly, it wouldn't be any worse than the current order.

1) It was my intention to make it better
2) add to the end of the list will make the same jumpiness than it is now
3) If done properly... agree; but nobody has proposed a solution that is good enough for now.




An interruption of ideas above;
is it not possible just to hold the code it is now, but insert an new rule 'on viewed screen now' to the 'next unit' command? So Wesnoth is only taking units in the current screen size, and is there none, than Wesnoth is going further than the screen
This way it is not perfect, but it is;
1) more user-friendly
2) less jumpiness than it is now
3) it could look like Wesnoth has become is a piece cleverer
4) it is a stateless algorithm

[Zarel]

1) It was my intention to make it better
2) add to the end of the list will make the same jumpiness than it is now

What I'm describing is a workaround for a corner case. In 99% of scenarios, it would be better, and in 1% in scenarios, it would be just as good. Isn't that an improvement?

3) If done properly... agree; but nobody has proposed a solution that is good enough for now.

What is wrong with my solution? I've posted it several times, and although I'm not so vain as to think it's the best solution ever, I'm kind of frustrated that no one has given me any sort of feedback.

[solsword]

I'll go ahead and agree with you (Zarel) that your solution seems like the best (stateful) algorithm proposed so far. It's got good running time, it's theoretically sound, and it's not overly complicated.

However, I'm also worried about the point that Sapient brings up. Depending on the coding, there's the potential to not just have a strange order, but to, for example, skip a unit entirely, or something else like that. I don't necessarily think that the problem is insurmountable, but if I were the one doing the coding, I'd implement a stateless algorithm for that reason.

Speaking of which, what do people think of my proposed stateless algorithm?