How do I keep a list of units in a path in order?

I'm working on a tower defense game and I want the defending turrets to shoot at the attacking unit thats farthest along the path within its range. I'm programming it in java and using ArrayLists for holding the units.

So far I have the path broken up into different blocks that each have a list of units in them. As a unit leaves the block it gets passed to the next block on the path. If the units all moved at the same speed it would be easy to keep track of which unit is farthest because it would be the first in the list. But I'd like the units to be able to move at different speeds.

When a unit is added to a block 开发者_StackOverflowit gets added to the end of the arraylist. So the units that were added earlier are at the front of the list and the units that were recently added are at the end of the list.

My original idea was to have each unit check the units lower than it in the arraylist to see if they're farther along the path. If they are it would move down the arraylist to the correct spot. This kind of seems like a lot additional work for the blocks to do and I'm afraid it will slow down the game alot.

Is this a good idea or should I try something else? I can post some of the code if it would help.

I'm not sure an ArrayList is your best bet. I presume at every "tick" in the game, each unit will move a designated distance which means you'll have colliding units, shifting each other in and out of position on a list.

I'm also working under the assumption that each "block" is deeper than 1. Meaning that for each "tick," a given unit could move farther within the block than another and if a unit has reached the end of a block, the next tick bumps it into the next block.

Option 1 (mediocre):

Use a Map<Integer, Set<Enemy>> where the Integer is from 0 - BLOCK_DEPTH and each sees enemies jumping from one set to another. There's no sorting here; just pointer reallocation. You also just have to do a map.get(0) and add that to nextMap.get(BLOCK_DEPTH)

Option 2 (better?):

Use a SortedSet that implements a comparator based on Enemy.position where position is an Integer from 0 - BLOCK_DEPTH. Each Enemy has a listener that updates it's position on a tick and then you start each tick by popping off the elements from the Set while Enemy.position is 0, pushing them onto the next set.

You could calculate the distance to home base when each unit is spawned, then subtract the move amount when the units move. Then each tower will just run through the list and see which unit has the least distance to home base.

You get the original distance you can use A* path finding, count the number of blocks the unit will pass over and multiply by the size of the block, or do a simple straight line distance. Depending on the layout of your game, you'd know best.

public static double Get2DDistance(float x1, float y1, float x2, float y2) {
    float dx = x2 - x1;
    float dy = y2 - y1;
    double distance = Math.sqrt(dx * dx + dy * dy);
    return distance;
}