Message text Hi Neko,
your algorithm is verrrrry well done and gave us some ideas on how to improve what we are thinking about.
Just a few consideration that might help optimize it.
1. We added a field called FOLLOWING that, for each ship, is filled with the id of a different ship if the hex entered by a ship is the same of the hex left free by another ship. In this case Ship A follow ship B, so if ship B is stopped, also ship A will. By doing so, we never move ship A before ship B. This is done by testing the value of the field FOLLOWING before moving a ship. If this field is not empty and the followed ship has not moved, than we try to move followed ship. The FOLLOW test is repeated on the new ship until we find a ship that do not follow any ship.
2. In the ordering of the ships, we also consider the "possible" collision between all ship that are at distance 2 or less. This is done by considering the 9 combination of hexes: for each ship we have the 2 occupied hex plus a possible third one the is the hex the ship will enter. This 9 check will ensure that for each ship pair we find all possible collision (can be optimized a bit, but not now). We give a weight to each type of collision we find (E.g. 10 points for a ship moving forward into an occupied hex, 6 point for a ship turning into an occupied hex). We sum up all the "Collisions score" and then order the ship from the heaviest.
With this two steps will be able to reduce to the minimum the looping because we start move the more "entangled" ship, the one who is involved in the highest number of collisions.
Currently, is not clear how to wheight the "Collision score" with your "Move" wheighting... any suggestion is welcome.
Have fun,
your Webmasters. |
|
|
Donate
Leagues
Gonzaga
Blue Max
Cartagena
Wooden Ships...
King Me!
VampiRing
