Jump to content
  • Topics

  • Posts

    • You mean the overlap of fields you see in game?  They actually are not overlapping.  The "core" part of a field is smaller, and I'm computing based on that core part only.  In game, they render a bit more field outside of that core part.  That part cannot be farmed, and is for aesthetic effect only.
    • You are not considering Field overlapping?
    • Six months has passed.  Development of stevenlauBot did not stop, but I have been dealing with a really difficult problem - optimal field placement around CC.  The algorithm improved over and over, and now reaches an optimal solution worth sharing.  Before I go into technical details, here are some screenshots of optimal placements in random Mainland.  Pink represents the region where we can place field freely, and blues are the fields. Now I am writing some technical details.  I first define Gap and Hang. Gap Ideally we want to let a field to touch (snap) the CC (or actually any dropsite), so that farmers can efficiently drop resources without walking.  However, since farmers have a size and dropping range, we can actually leave a gap (around 5.6m) between field and CC and the farmer can still drop resources without walking.  Leaving such a gap might allow more fields to be placed. Hang In games, we often see players put field snapping at the corner of CC.  This is not ideal, because farmers will have a walk a bit to drop resources.  We name this case "hanging" entirely outside of CC.  If we now shift that field a little inward toward the CC, it is still hanging, but only part of it is hanging.  Then farmers can farm in the part where the field is not hanging, and they can drop resources without walking.  That non-hanging part is around 8m. Now to state our problem more precisely, we want to place maximum number of fields around CC, allowing gap between CC, but keep certain non-hanging part.  We disallow rotation.  Although rotation might give better arrangement, the problem will become too difficult.  In fact, disallowing rotation is the sole assumption of our algorithm.  Under such assumption, our algorithm gives optimal placement.  I also claim that if we allow rotation, no efficient algorithm exists. People who are familiar with algorithm, especially computational geometry, should realise this is a very difficult problem.  This is shape arrangement in continuous 2D space, and deterministic algorithm might not even exist.  Scientists usually do heuristics to find good-enough (but not optimal) solution in these problems.  I had also been working on heuristics, but as I keep improving my heuristics, I found that our problem is quite special and is much simplified.  It turned out that we can work out a combinatorial algorithm to really find the optimal placement.  We basically do trapezoidal decomposition of the region, that we do sweep line algorithm over all such trapeziums, exhaust all combinations, and merge linearly related constraints.  The algorithm is super complicated, but I think I made it.  Do you like it?    
    • EDIT: In the Settings I found a Hotkey to activate a build-in FPS counter, which works just fine, so I guess this can be considered solved.
×
×
  • Create New...