@normen: Nope, I implemented some asset-functionality into the graph-builder. It’s everytime the same palm-tree, but rotated and scaled by random values. So it look like there are various trees.
Are you generating the maps or are they fixed? Random mission generation done well could certainly add variety and it looks like it should be achievable on that sort of map with the right constraints.
@zarch: no, there are created by hand. Random creation would be cool but it’s really difficult to generate the bounding-polygons for the isles (see the image from the first post)
@Sploreq: definitly yes. There will be different ship types you can choose from and much equipment to upgrade your ship.
Tricky maybe, I can think of at least one algorithm that would work though and it doesn’t need to be super-fast since it is done once at map creation. In fact both these algorithms would also apply: http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm
My first thought was that it would probably be enough to create the initial stage of a convex hull if you just selected each point around the edge of the island and joined them into a chain and then picked a point and went around the chain clockwise. If the angle of the point is less than 180 delete that point, join the adjacent points and then go back to the previous point and repeat.
Any of those algorithms are going to produce a more complex polygon than needed though so some sort of “simplify” step would then be needed. Again that could be as simple as removing angles below a certain threshold although it would also require moving the adjoining points out so the line between them is now outside the point it was just removed from.
Just a thought though, your game is looking pretty epic already