🔒 Locked

Unit Positioning Algorithm

Started by TenshiS Jul 4, 2009 at 3:14 PM 2 replies 1.7k views

Original Post

Jul 4, 2009 at 3:14 PM

Hey everybody! For all of you who know the Total-War series: I am trying to get the same effect you get when moving a unit around in Rome or Medieval 2. I'm trying to make 2D squares arrange in the best possible way when moved from one point to another. For example, if I have 3 rows of 4 soldiers each, and want to turn that into 2 rows (6 soldiers each), I want it to look and feel realistic, so I don't want soldier number 5 (first one on 2nd row) to walk all the way to the right on first row near soldier 4, instead, I need the first row (soldiers 2,3 and 4) to move to the right and make place for him. They also have to make room for one more, but I can't even figure out for which one and how, how is this solved in the real army? So, you see my problem is a bit complex, I was thinking about making an array of all the "free future positions", and then, starting from the left, occupying them one by one by the closest soldier to that position, soldiers on different rows being prefered (in case of same distance). Has anybody tried this before? Would it work this way? Or is there another way? Thanks for your help! :)

Peter5897

Jul 4, 2009 at 3:56 PM

I did something like the solution you described for a simple 2D pathfinding demo I made. In the program I'd allow you to create units and then select and move them.

If I recall correctly... I used an invisible entity in the world that acted as the desired position of the group. All other units in the group would be assigned an offset position from that point and they'd do their best to stay in that position. I made it so that the point moved at a slower rate of speed than the max speed of my units so as to allow units that had fallen behind to catch up. It looked fairly cool and my guess is that it would work fine for other formations as well.

As for determining who should be placed where, I think I started out with a "closest point goes to closest unit" algorithm but didn't like how it turned out in all cases (most looked fine though). Unfortunately, I forget what those cases where and what my fix was... sorry.

erissian

Jul 4, 2009 at 5:39 PM

Quote:
Original post by TenshiS
Hey everybody!

For all of you who know the Total-War series: I am trying to get the same effect you get when moving a unit around in Rome or Medieval 2. I'm trying to make 2D squares arrange in the best possible way when moved from one point to another.

For example, if I have 3 rows of 4 soldiers each, and want to turn that into 2 rows (6 soldiers each), I want it to look and feel realistic, so I don't want soldier number 5 (first one on 2nd row) to walk all the way to the right on first row near soldier 4, instead, I need the first row (soldiers 2,3 and 4) to move to the right and make place for him. They also have to make room for one more, but I can't even figure out for which one and how, how is this solved in the real army?

So, you see my problem is a bit complex, I was thinking about making an array of all the "free future positions", and then, starting from the left, occupying them one by one by the closest soldier to that position, soldiers on different rows being prefered (in case of same distance). Has anybody tried this before? Would it work this way? Or is there another way?

Thanks for your help! :)

That's not a typical change of formation, but what would probably happen is the last row would move to the left. The leftmost two soldiers would join the first row, the other two would join the back row.

At least, that's what would be smoothest. What a marching formation would probably do, (actually, they wouldn't organize like this, but if they did) is something like this:

Because the way the soldiers form is by squads. In this case, soldiers 1,5, and 9 are (probably) squad leaders, and stay to the right of the formation. So no matter what crazy shape you stick them in, these guys will be to the front and right of their group. The order that the rest of their squad is in is likely to be random.

So the way you stack them is by placing the key figures, and letting their subgroup form around them, instead of considering the whole thing one big mess.

For more information than you probably care for, here's the D&C manual:

http://rotc.okstate.edu/.../FM%203-21.5%20Drill%20and%20Ceremony.pdf

TenshiS

Jul 5, 2009 at 4:02 AM

Hey,

thanks for the replies!

Peter, that's exactly what I'm looking for, do you happen to have that demo somewhere or at least some code from it? If you remember the way you solved that, please let me know! :)

Erissian, thanks for the detail-work :) . The drill manual has some interesting things in it, but this is all too modern, I'm not looking for small mobile groups of armed soldiers, instead I'm looking at units of over 100 sword-infantry. Moving the whole unit twice its width to the right to make place for the last row would be too inefficient. That's why I need something more natural, like soldiers walking to positions near them and arranging anew, leaving small gaps for soldiers coming from behind.

For your conveniance, this is "approximately" how I imagine it, a smooth transition from one position to another (here in 3 different situations):
http://www.geocities.com/viocos2001/formations.PNG

[Edited by - TenshiS on July 5, 2009 6:02:36 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.