stevenlauBot game start teleportation

[stevenlau]

I am developing an AI called stevenlauBot.  I have only made the game start move.  All units go to the tree nearest to CC, cav goes to chicken, either by walking or teleportation, whichever faster.  It looks cool!

My plan is to make the AI to play standard tactics like how I usually play (only Han).  It will be useful to practice 1v1.

[Arup]

good luck! do tell me if I can help in testing <3 as this way I won't have someone telling me we can't have smth only because dumb Petra can't use it lmao

[AlexHerbert]

Is like quick start mod

[guerringuerrin]

that's cool, @stevenlau! looking forward to hear of any advance on this

[stevenlau]

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?

 

 

Edited 1 hour ago by stevenlau

[Thalatta]

You are not considering Field overlapping?