Smart Area Reclaim

[Gota]

Dizekat.
Its not a bad idea cause mods should be bale to unify the experiance for all that play the mod.
And believe it or not im sur esome modders would like that.
Would it be somehow possible to contain it using another tool?
like the lobby or some way..

[aegis]

http://www.math.sfu.ca/~goddyn/Courses/ ... istics.pdf

Nearest neighbour is what you want, I guess. It's not good.

I actually came up with a decent one, but I don't like the command spam
the widget could poll the unit's queue and update when it's done with each reclaim order or sth...

[dizekat]

Dizekat.
Its not a bad idea cause mods should be bale to unify the experiance for all that play the mod.
And believe it or not im sur esome modders would like that.
Would it be somehow possible to contain it using another tool?
like the lobby or some way..

I never said it was a bad idea per se, only that it is very very stupid idea.

[dizekat]

http://www.math.sfu.ca/~goddyn/Courses/ ... istics.pdf

Nearest neighbour is what you want, I guess. It's not good.

I actually came up with a decent one, but I don't like the command spam
the widget could poll the unit's queue and update when it's done with each reclaim order or sth...

Well your last image looked kinda inefficient. There shouldn't be any long parallel paths in efficient solution...

I don't think the problem is just traveling salesman related. If trees densely cover the reclaim area, for instance, the optimal path isnt visiting every tree, it is spiraling around reclaiming stuff within reclaim range.
This is a problem of painting specific shape (dots for tree/wreck locations) over with a brush of specified size (nanorange radius of cons doing the reclaiming thats it).

edit: btw you dont need to poll. I used widget:UnitCmdDone(unit_id, unitDefID, unitTeam, cmdID, cmdTag)
to get notified when command is done.
Keep some 2 orders in queue so that theres no lag pauses...

[aegis]

I made a massive algorithm improvement but didn't feel like posting more pictures because the main problem was still command spam :)

I didn't know about CmdDone... I'll see what I can do

[imbaczek]

It's not strictly TSP, but it reduces to it in the limit, so from algorithmic complexity perspective it's still a hard problem. Also, I don't believe that the difference is that huge, it should be a straightforward (not necessarily simple, though) transformation of features in the area into TSP input.

[dizekat]

It's not strictly TSP, but it reduces to it in the limit, so from algorithmic complexity perspective it's still a hard problem. Also, I don't believe that the difference is that huge, it should be a straightforward (not necessarily simple, though) transformation of features in the area into TSP input.

Well some situations (dense forest, reclaim circle with cons outside it) have simple very close to optimal solution (spiral towards the center eating all the trees near path)