[REL] Cover that line

Discussion in 'Released Mods' started by cola_colin, July 23, 2015.

  1. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    Allow to drag a line with rightclick, selected units will more or less evenly spread on that line. (Damn getting that work really well isn't actually that easy xD)

    Get Cover the line on pamm now.
    The code is on github: https://github.com/pamods/CoverTheLine



    older version, it may work slightly better by now:

    It's clearly not perfect. Probably a combination of my stupidity causing bugs and the fact that I decided to flat out ignore that planets are kinda like spheres and not like flat ground.
    Maybe I'll look into the algorithmns that googlefrog posted below, but for now this is somewhat "decent" and there is so much else to do. Also notice the preview line is a line of blue mines. That could be made to look a lot better with a custom effect or something. If somebody has an idea what to put there please suggest it, atm the puppet is defined like this:
    Code:
    {
                    model:{
                        "filename": "/pa/units/land/land_mine/land_mine.papa"
                    },
                    material: {
                        shader: 'pa_unit_ghost',
                        constants: {
                            Color: [1,0,1,0.8],
                            GhostColor: [0,0,1,0.5],
                            BuildInfo: [0, 10, 0, 0]
                        }
                    },
                    location: {
                        planet: 0, // TODO API for current focused planet
                        pos: loc3D.pos,
                        orient_rel: true,
                        snap: true
                    }
                }
    
    older version:
    Last edited: July 31, 2015
    huangth, elodea, tatsujb and 14 others like this.
  2. Killerkiwijuice

    Killerkiwijuice Post Master General

    Messages:
    3,827
    Likes Received:
    3,573
    fiahnsjkdnaskjdbasdsa

    nice
    Raevn and cdrkf like this.
  3. stuart98

    stuart98 Post Master General

    Messages:
    6,020
    Likes Received:
    3,902
    KL;SDJKL;FJASL;DKFJL;ASDLPFASFasdffgsdsdfsdw

    @GoogleFrog

    YES YES YES YES YES
    Nicb1 and cdrkf like this.
  4. cdrkf

    cdrkf Post Master General

    Messages:
    5,750
    Likes Received:
    4,831
    @cola_colin if you pull this off... You sir are a total legend!
  5. dom314

    dom314 Post Master General

    Messages:
    894
    Likes Received:
    1,208
    How are you distributing the units? Bipartite matching?
  6. cdrkf

    cdrkf Post Master General

    Messages:
    5,750
    Likes Received:
    4,831
    @cola_colin just a thought, how does your mod handle multiple way points? In spring you can queue up multiple line commands and it automatically maintains the unit positions between moves (e.g. a unit on far left will stay far left through multiple way points queued using shift with line commands). Will your mod do the same or is it a 'one at a time' kinda thing?
  7. doud

    doud Well-Known Member

    Messages:
    922
    Likes Received:
    568
    Simply terrible !!!!!!!!! Thx !!!!!
  8. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    It's not actually that hard to do with the new API.

    The current code does this:
    1. collect 2d locations from the mouse move
    2. raytrace them to the 3d locations on the planet
    3. interpolate over the 3d path and place the units evenly distributed onto it

    Though it still sometimes has some holes in the line. Need to do more tests. I lost a lot of time to a pretty stupid javascript mistake.

    PA does not keep the formation when you give new commands and the placement of every unit on the line is currently random, so it's only a static line. It might be possible to improve that a little, but it won't be perfect. I guess the main problem will involve to do a lot of "which unit should get which move command exactly". Hmm.
    I guess I'd need to make it detect which unit is closes to which target location and then give each unit the move command to the closes target location.

    EDIT:
    No that's wrong. I need to basically compare the old and the new formation and figure out which locations in them are "similar".
    Last edited: July 24, 2015
    cdrkf likes this.
  9. dom314

    dom314 Post Master General

    Messages:
    894
    Likes Received:
    1,208
    Yeah, that matching has an algorithm called 'bipartite matching'. It is also called the assignment problem. It runs in O(n^3)
  10. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    That is horrible
  11. dom314

    dom314 Post Master General

    Messages:
    894
    Likes Received:
    1,208
    Yes, it's also optimal for the assignment problem :p. I guess heuristics would be the way to go.
  12. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    I am not quite sure how to find which node should match which other node as well though.

    Like for example:
    Code:
    X                                         Y
    X                                         Y
    X      should move to        Y
    X                                          Y
    X                                         Y
    
    Here it should connect them line by line.
    But here:
    Code:
    ABCD should move to EFGH
    
    It will need to connect A with E, B with F, C with G and D with H.
    So I guess the weight function needs to be about "how much would it change the formation".
    Maybe define it as "how much would taking that new position change the location inside the formation".
    Calculating that weight itself in a naive way at least won't be exactly cheap either.
  13. dom314

    dom314 Post Master General

    Messages:
    894
    Likes Received:
    1,208
    Yeah it isn't an easy problem. Perhaps O(n^3) is enough, you just need to make sure that units are split up into groups such that n < what ever bound you desire. So instead of matching each unit, you might match a group of k units that are close.

    Otherwise you need to use a heuristic to solve this problem in less than n^3 time. Some google searches haven't revealed much.

    The heuristic I am thinking of is the overall distance traveled.
  14. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    After eating I've come up with this idea:

    Given an array of location A and B, which define the start and end locations. Both have n locations, created by the interpolation step I already have.

    1.) Calculate the middle of A and B. Takes O(n)
    2.) Using the middle of A and B calculate local coordinates, scale them to the range of -1 to 1. Takes O(n)
    3.) Iterate all locations in A. Search a location in B that is closest as possible in local coordinates and connect them. Naive version takes O(n^2). Actually not full n^2 since I can remove the points I already connected in B. So it's like 1/2 * n^2. Still inside O(n^2) but that half factor is nice to have.
    Might be able to use spatial hashing to push this down further, but I suspect it might be okay with hundreds of units at least.

    Let's see if this works... It's probably not optimal in all cases but might yield an okay looking solution. I guess a more refined concept would need O(n^3) in the last step. Maybe I can combine that with the spatial hash somehow to push it down again.
    Last edited: July 24, 2015
    cdrkf likes this.
  15. GoogleFrog

    GoogleFrog Active Member

    Messages:
    676
    Likes Received:
    235
    Was that meant to summon me?

    I like this mod and it is a decent step towards a much better UI. I did not realize the API was to be improved and I was quite disappointed at the initial modding API. Would you be able to draw the line-in-progress on the terrain?

    Algorithms for custom formation unit assignment have already been thought about and implemented here: https://github.com/ZeroK-RTS/Zero-K/blob/master/LuaUI/Widgets/cmd_customformations2.lua

    I did not write that widget but it seems to use the Hungarian algoritm for few units with No X for the many units case. The Hungarian algorithm is probably the perfect O(N^3) algorithm which has already been referenced. I cannot track down the origin of the No X algorithm but I can attest that it works. This is because the cutoff for switching to No X seems to be rather low so I would use it a lot and have not noticed any problems with it.

    Here is No X: https://github.com/ZeroK-RTS/Zero-K/blob/master/LuaUI/Widgets/cmd_customformations2.lua#L893

    It is GPL so feel free to use it. Perhaps you will even find a bug in the algorithm and feed it back as an improvement.
    stuart98, cola_colin and cdrkf like this.
  16. cdrkf

    cdrkf Post Master General

    Messages:
    5,750
    Likes Received:
    4,831
    You should check out the patch notes for the latest PTE.... Uber have added a ton of stuff to the modding API (which I don't think anyone was expecting)... The next version of PA is going to be good :)

    My only slight concern is I wonder if this is intended as a 'finishing up' version? I wouldn't hold it against Uber if that's the case as they have supported PA pretty well since launch adding in a load of good stuff, although I'm still hoping they might keep developing it for a little while longer.
  17. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    Yes
  18. cola_colin

    cola_colin Moderator Alumni

    Messages:
    12,125
    Likes Received:
    16,255
    updated OP
  19. Killerkiwijuice

    Killerkiwijuice Post Master General

    Messages:
    3,827
    Likes Received:
    3,573
    Ah great, now we'll see people drawing dicks with their doxen.

    Kappa
    stuart98, cdrkf and cola_colin like this.
  20. cdrkf

    cdrkf Post Master General

    Messages:
    5,750
    Likes Received:
    4,831
    You think thats bad.... you shoulda seen the first few days after they added the ability to paste sketches using the map drawing tools in spring :p
    stuart98 likes this.

Share This Page