Problem Statement |
| | You work with a team of ichthyologists, and you study the possibility of using flocking behaviour to separate certain fish species from other fish found in the same area.
Modeling fish movement
The state of the fish i after step number t is described with its position pi,t on a plane and its velocity vi,t (note that both p and v are vectors). These parameters are updated according to the following equations:
vi,t+1 = vi,t + Fi,t
pi,t+1 = pi,t + vi,t+1
The force Fi,t which affects the movement of fish i during step t+1 is calculated using the positions and velocities of all fish after step t according to the following rules:
-
separation: the fish is repelled by other fish and obstacles. Fish of the same species repel fish i if they are closer than its separation range, while fish of other species repel fish i if they are closer than its detection range. The separation force generated by fish j Fsj=(pi-pj)/d2,
d=max(rij-A*sR,B), where
rij is the distance between fish i and fish j,
sR is the separation range of fish i,
A and B are 0.5 and 1 for fish of the same species and 1 and 0.1 for fish of other species.
The total separation force is a sum of individual separation forces.
-
alignment: the fish aligns with other fish of the same species which are closer than its detection range. The alignment force generated by fish j Faj=(vj-vi). The total alignment force is an average of individual alignment forces.
-
cohesion: a fish moves toward the average position of other fish of the same species which are closer than its detection range but further than its separation range. The cohesion force generated by fish j Fcj=(pj-pi). The total cohesion force is an average of individual cohesion forces.
-
sides avoidance: a fish is repelled by the sides of the area if it is closer than 25 units to one of the walls. The repulsive force generated by the walls Fg=(1,0)*(1/max(1,px)-1/max(1,600-px))+(0,1)*(1/max(1,py)-1/max(1,600-py)).
-
random component: a fish adds a random acceleration of its own Fr, x and y component of it being between -50 and 50 each.
-
force calculation: the overall force F=0.05*Fs+0.15*Fa+0.075*Fc+5*Fg+0.025*Fr. Both force F and velocity v are truncated to their maximal values Fmax and vmax if necessary: F is truncated to min(Fmax/abs(F),1)*F after it is calculated but before it is applied to velocity, and v is truncated to min(vmax/abs(v),1)*v after it is calculated but before it is applied to position.
You can influence fish movement by placing obstacles. The obstacles come in two kinds: obstacle of kind 0 repels all fish, while obstacle of kind i (i between 1 and Nc) looks like a fish of species i which doesn't move.
Your task is to drive fish of one certain species away from other species and to a certain destination area.
Implementation
species gives you information about Nc species of fish. Element i of species describes species i+1 and is formatted as "V_MAX F_MAX DETECTION_RANGE SEPARATION_RANGE".
fish gives you information about the state of fish before the start of the simulation. Each element of fish is formatted as "POSITION_X POSITION_Y VELOCITY_X VELOCITY_Y SPECIES".
wanted gives you the index of the wanted species and the destination area as a rectangle {x1<=x<=x2, y1<=y<=y2} and is formatted as "X1 Y1 X2 Y2 INDEX".
You must return the data about the obstacles you want to place as an int[]. To place No obstacles, the return must have 3*No elements, elements 3*i, 3*i+1 and 3*i+2 of return being x and y-coordinates and type of obstacle i, respective.
Scoring
After the obstacles are placed, the step-by-step simulation starts. At each step the positions and the velocities of fish are updated accordingly to the fish movement rules. The simulation runs for 500 steps, and after that the score is calculated.
Your score for a test case will be Nw*Nw/(Nw+Nuw)/(No+1), where Nw is the number of fish of wanted species within the destination area, Nuw is the number of fish of other species there, and No is the number of placed obstacles. Your overall score will be the sum of your individual scores, divided by the greatest score achieved by anyone for that test case.
Test Case Generation
First, the species data is generated. The number of species is chosen between 1 and 6, and for each species its parameters are chosen: vmax between 5 and 20, Fmax between 5 and 10, detection range between 20 and 45, separation range between 5 and 10.
After this, the fish data is generated. The number of swarms is chosen between 1 and 20, and each swarm is generated as a set of 5 to 30 individuals of the same species with approximately equal velocities. The fish of one swarm are located within a random square with the length of the side equal to (4*separation range of their species) which, in turn, is located within the square {150<=x<=450, 150<=y<=450}.
Finally, the wanted species is chosen among the existing ones, and the destination rectangle is generated randomly so that it is sized between 50x50 and 100x100 and is located within the square {50<=x<=550, 50<=y<=550}.
Get the Visualizer! |
| |
Definition |
| | | Class: | FlockingBehaviour | | Method: | placeObstacles | | Parameters: | String[], String[], String | | Returns: | int[] | | Method signature: | int[] placeObstacles(String[] species, String[] fish, String wanted) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Fish are considered to be material points of zero size. Two fish, two obstacles or a fish and an obstacle can occupy the same position. |
| - | All initial data is integer, but the calculations are made in doubles. |
| - | It is possible to have no fish of one of the species, including the wanted one. |
| - | For more details on the test case generation and simulation implementation see the visualizer source. |
| - | The time limit is 20 seconds and the memory limit is 1024M. |
| - | There is no explicit source code length limit. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Examples |
| 0) | |
| | | Returns:
"5 species
17 9 41 7
7 7 36 9
19 5 41 6
20 10 31 6
17 7 45 8
295 fish
wanted = '391 394 457 444 3'" | |
|
| 1) | |
| | | Returns:
"4 species
15 8 45 5
10 9 40 9
14 8 33 9
10 9 42 9
184 fish
wanted = '199 55 281 109 2'" | |
|
| 2) | |
| | | Returns: "2 species
9 7 42 7
14 9 45 6
191 fish
wanted = '247 125 317 208 1'" | |
|
| 3) | |
| | | Returns:
"4 species
11 6 42 9
7 6 34 8
10 7 40 8
7 10 41 7
88 fish
wanted = '180 89 230 158 1'" | |
|
| 4) | |
| | | Returns: "3 species
5 8 27 5
6 6 40 9
19 9 27 5
243 fish
wanted = '488 108 548 173 2'" | |
|
| 5) | |
| | | Returns: "1 species
8 7 35 10
132 fish
wanted = '230 253 282 350 1'" | |
|
| 6) | |
| | | Returns: "1 species
18 8 34 5
138 fish
wanted = '311 99 371 182 1'" | |
|
| 7) | |
| | | Returns: "2 species
14 10 42 6
13 9 40 5
74 fish
wanted = '145 109 240 160 1'" | |
|
| 8) | |
| | | Returns:
"5 species
7 8 38 8
8 8 32 9
14 5 21 10
14 7 45 7
7 8 26 5
198 fish
wanted = '396 87 485 147 4'" | |
|
| 9) | |
| | | Returns: "2 species
5 5 37 10
8 9 21 10
107 fish
wanted = '373 270 437 361 1'" | |
|