Improving upon naive_navigate to get in top 400


#1

Hi folks,

So I’ve managed to throw together some code which is able to get me past the 500 mark.

I think my strategies are good, but I’m struggling with the code side of things (Python).

The one area that I think needs the most improvement, is to improve upon the naive_navigate - which marks a cell as unsafe when it is occupied only. This means that two ships cannot swap positions (even though they are allowed to), which sees a lot of standing around the shipyard waiting for ships to vacate - The top players obviously do this and I think it’s my biggest hinderance.

I’m struggling on the coding side. Would it make sense to store in a dictionary the list of moves (for the next turn), then check and revert conflicts? What are others doing to achieve this?


Does naiveNaviate suck? I should just create my own pathfinding right?
#2

I seperate movement logic into 3 parts:

  1. Get dict with {ship_id: list_of_directions_to_move} (from any sort of path finding algoritm)
  2. while flag is True: make safe movements and update ships positions (GameMap class has mark_unsafe() method, but no mark_safe() so you should added it and used it). If any movement is made flag is True otherwise is False.
  3. If some chips want to swap - find them in remaining movements and do it.
  4. repeat 2 and 3 if you want to minimize deadlocks situations and you don’t hit time limit.

Steps 2 and 3 is moved to another function and simply takes dict from step one and return commands