Thanks Codingame for this challenge! I really appreciated the fact that the game was easy to play but hard to master. The UI was really nice and easy to visually debug in my opinion.
There were many discussions in discord and I appreciated that also. Thanks to everyone which participated in the discussions.
It's my third challenge and first time I reach Legend during the challenge, so I'm really happy about that.
I hope my gold boss was well chosen and that the indications it gave helped you to improve your code.
To end the introduction, GG to Recurse for the victory and everyone else to have made this challenge interesting.
To be able to reduce at its minimum the rectangle where could be the fish, I compute the intersection of all next rectangles:
- the habitat of the fish
- a new rectangle based of the last rectangle : increase the height and weight by 400 (fish speed: up, down, left, right)
- both of the radar
- rectangle of the foe drone scan if it scanned a new fish
- rectangle if my radar for this fish changed from last radar
Then I use the symmetric of the fish to reduce again the possible rectangle.
If a drone use light and find a new Fish, it must be in rectangle of height and weight of 4000 (image is wrong). Then we can compute the intersection between the predicted rectangle of the fish and the rectangle of the scan to reduce the possible rectangle.
When my radar of a fish change, between the last turn and the current turn, it means that the fish is in a rectangle as showed in the image below.
The height or weight of this rectangle can not be greater than 200 + Min(200, droneVelocity(X or Y))
Each fish has a symmetric. I use it to reduce the possible rectangle.
The red rectangle is for the left fish and the blue one for the right fish. I create a symmetric rectangle for the symmetric fish and compute the intersection between the red rectangle and the symmetric blue rectangle. The intersection is the green rectangle.
I do that for both fish and I compare the resulting green rectangles. If there are symmetric, then I keep it. If not, I continue to create symmetric rectangles until both rectangles are symmetric.
My condition to do that was turn * 600 + 1400 > range where range is bottom fish range.
I have implemented the code to be able to simulate the fish movement and to be able to predict where the fish will be in the future after I scanned the fish.
I use that for two purposes:
- remove a fish. It's easier when you know where he is exactly.
- finding a symmetric fish. When you scan a fish, if there is no drones able to make the fish flee, then you know exactly where the symmetric fish is and which velocity it has.
I have implemented the getCollision function from the referer to be able to check if my drone will get hit or not.
If my drone is near a monster, I will create 16 positions around a circle which center is my drone center and the radius is 600. Then I will simulate the drone's movement, the monster's movement and check if there is a collision. If not, I will take the position which is the closest from the target I want to go.
It doesn't work well on the edge of the maps as you often need to check with two depths. But I didn't manage to make it work.
I compute three scores:
- myPredictedScore: the score if I go return the fish scanned now and will retrieve the last fish after my opponent. It is based on the position of myDrones and the foe drones to know if I will be able to retrieve the fish before my opponent.
- foePredictedScore : the score which will have my opponent if I manage to have myPredictedScore
- myPredictedScoreWithNotScannedOut : the score if the fish I don't have will be moved out the map by the opponent. If myPredictedScoreWithNotScannedOut > foePredictedScore I'm 100% sure to win the game if I go up.
My strategy is a succession of ifs which are checked in order for each drone in a greedily way. If a if return an action (a target and a boolean to use or not the light), we execute this action and we don't check the next ifs.
- checkAndEarlyReturnScan
- findDangerousFish
- findClosePredictedFish
- findCloseFishToRemove
- forceMoveFishOutsideMap
- goNextFish
- returnScan
- wait
Each drone are completely independent from each other and it causes me some annoying issues that I don't really manage to fix.
- If myPredictedScoreWithNotScannedOut > foePredictedScore : I go up
- If each of my drones has scanned a type 2, I go up
- If the foe drone seems to go up and i'm higher than it, I go up to scan my fishes before him
- If myPredictedScore > foePredictedScore and I'm higher than the foe drone I go up
If there is a center of a rectangle which is too close from a border, I will go after it.
If there is one fish the position is known because I scanned the symmetric one and I can get it the next turn, I will go after it.
If I scanned a fish which is still not scanned by the opponent and I can remove it in the next 2 turns, I will try to remove it from the map.
If there are fish which are not scanned by the opponent and scanned by me and far away from the opponent, I will try to remove them.
If there are nothing to do, I will go after the next fish. I sort all fishes by their types (2 then 1 then 0) and by their distance to the border. So this function begins to search the closest type 2 fish to the border. It means that this function will first go deep to find the fish and then go up if needed.
For each movement of my drones, I check if I have to use the light or not. The decision is the following:
- If all points of a predicted rectangle are contained by the circle of light, I will light because i'm 100% sure to scan the fish.
- If the center is contained by the circle of light, I will light only if I didn't use light the previous turn. Without this condition, I use light too often and I lose ranks. The issue is that for the type 2 fish, sometimes I will light one turn too late and then lose the game. I think I could improve that and gain ranks but I don't manage to make it work.
I think this challenge was really interesting even with only simple heuristics and rectangles intersections.
I'm just a bit disappointed that after reaching legend, I didn't manage to improve my code. So the gold boss is very close to my actual code in legend.
I'm grateful to Codingame to host such challenges and i'm looking forward to the next one.
Next goal : Top 10 maybe? :D