How do I avoid collisions with my better navigation code?


#1

My score is above 50 now so I’ve stopped using naiveNavigate; instead, I wrote my own navigate function that defines a “safe” cell as a cell that no other ship decides to move to. Ships mark the cells they want to move to as unsafe. (Essentially what all the top players do)
There’s the issue where one bot decides to move into another ship’s cell before the other ship decides to stay still, thus creating a crash. I then created another function, only ships that stay still mark theirs as unsafe. I run that function in a for loop, and I then run the actual navigation function in another loop. I am still getting lots of crashes. How should I avoid these collisions?


#2

An imperfect solution but not terrible is: don’t let the second ship stay still when there’s a ship incoming.


#3

Thanks. I tried doing that, but it 1.) reduced the efficiency and 2.) the second ship could crash into another third ship, and so on…


#4

Try this Improving upon naive_navigate to get in top 400


#5

I managed to keep the efficiency by adding a priority property like:
Who wants to move to same position? -> ship 0 and 2 ->
If ship 0 has less halite than ship 2, than the ship 2 should move first.

“Lady’s first” :slight_smile:


#6

Heyo I know exactly what you’re talking about, I had the same problem. Now you don’t really want to force ships to move if they can’t/it isn’t optimal so the best way of doing this is with a while loop.

But before you do that, you absolutely must make sure that your ships do not try to move when they don’t have enough halite, because say you have a future_positions list, and you assume the ship can move, but it can’t because of the halite, then you’ll never be able to catch it, and your code will assume the ships are fine when in reality they will crash. That is what leads to the strange bug where the ships appear to not collide but do.

The way I did it is have a future_positions list that stores, you guessed it, future positions. Then I had a conflicts variable that was only 1 on the first iteration, and after that if any conflicts arise. Using that, iterate over using a while conflicts loop and then a for position in future_positions nested inside. If you find future_positions.count(position) > 2, then there’s a conflict and something needs to be done. Up to you how to fix that, but know that keeping the ships still if they’re about to collide works with this loop, however can cause inefficient clumping.

Hope this helps!