[Java] How to form a line for ships going to drop off


#1

How would you prioritize drop off ships. I’ve assigned those ships with a status “depositing” but they just rush to drop off and collide on the shipyard.


#2

Just create moves queue (ship + direction pairs) with ship’s halite as priority.


#3

Oh so like you should be adding the commands to the command Que after the for each ship loop?


#4

Something like this. I answer to similar question a while ago. Search through forum for “movement” or cmth similar


#5

After some experimentation, I settled on first doing a greedy search of everywhere the ships want to go and preferring destinations no one else wants if all other things are equal.

I then move all those conflict-free ships at once and mark their positions occupied. This resolves swaps and cycles (the big (but rare) sibling of swaps).

After that, I pick something random for the stragglers that isn’t backwards.

I like the idea of resolving conflict by halite priority though. You are ahead of me on the leaderboard after all!


#6

Thank you, I think I have a good idea on how I would like to approach this problem.


#7

So basically, the safe moving ships first, and possibly problematic moving ships second. That sounds like a great addition to my algorithm. Thanks!


#8

@scottlegrand interesting what you say about cycles… i’ve worked out swaps, but sometimes I see 20 ships get locked into a complicated jigsaw puzzle with the ships returning to base traffic-jammed and locked into ships going out to collect halite in complicated ways that very very slowly unlock by one ship at a time on the periphery deciding to go someplace else.

similar to the problem that…for example… if 4 ships wanted to rotate in a circle the problem can’t be solved by recursively finding empty positions. I’ve added a ‘plan b’ to my ships but that often makes things worse in small jam ups argh.


#9

But how would the swapping work. I’ve tried making the ships go to the position of one another but one ship always goes before the other and makes them collide. Command que looks like this {m 29 e, m 25 w} So ship id 29 and ship id 25 are swapping but 29 collides into 25 before they could make the swap. How would you make them move simultaneously?


#10

Make sure that both of the ships can actually move when you’re attempting to swap their positions. If one of the ships doesn’t have enough halite to move, you’ll end up with the other ship crashing into it.


#11

Yes! That’s a big bug! Fixing that was worth half a point of ratings for me. And it rears its ugly head the most when all your ships are rushing back to the base at the end of the game.

@ScottChristensenHanp That sounds a lot like what ought to be part of the logic for building additional dropoffs, no? It’s all about harvesting the most halite in the shortest time. This is still a matter of research for me. My first attempt at additional dropoff code lost me about 0.7 points.