Since the beginning, the Spring engine APIs have provided a helper function closestbuildsite. Poorly documented, this API call does not work as one would expect, and is understood by few ( hence the lack of documentation ).
For lack of time to implement something more comprehensive, Shard uses this API.
Because of the way this API works, these issues can appear, sometimes all at once:
- Units are spaced apart by large distances
- Maps are built in such a way that those large distances prevent a position being found in the search radius
- Wide open plains are ignored because they aren’t inside the search radius
- A builder in the middle of an island might not have any valid water in its radius when requesting a shipyard
- Units are built too close to each other
These are symptomatic of how the API works.
Closestbuildsite requires a position, a radius, a unit definition, a facing direction and a spacing parameter, but has the following problems:
- If you pass the builders position, you will likely get the builders position back, and the builder will block itself, preventing construction
- As the search radius goes up, the cost and performance degradation rises exponentially, it performs no caching, and employs no special mechanisms to optimise
- The spacing parameter is counter intuitive. The unit of measurement is how footprints worth of the specified unit
- Spacing doesn’t take account of terrain or units, anything that blocks counts, so if there’s a buildable area with a small bump in the middle, it will not be valid.
So if we specify a spacing value of 5, and build a light laser tower with a footprint of 1, it must be 5 from the nearest unbuildable square. If we build a kbot factory with a footprint of 8, and a spacing of 5, it must be 40 squares away from any unbuildable blocked position.
Shard attempts to mitigate this by doing some math on the footprint values and giving different values as spacing depending on how big or small a footprint is, but they’re approximate, and hard to optimise. Failures are inevitable. You can use the API to pass in your own position, but few do, and it moves the optimisation of spacing issue to lua rather than the C++ component.
So What’s The Longterm fix?
Implement a building placement algorithm. Possible mechanisms include:
- Brute force test each square, starting at a position and radiating outwards ( expensive )
- Split the map up into a grid, and mark larger grid squares as free or not free, with data on wether they’re valid for unit types. Generate valid positions ahead of time
I will likely take the latter approach, and I’m sure there are other routes, but those are simple and easy to implement, and importantly, to expand on for each games purposes. In the future it also leads to basic landmass detection using a basic flood algorithm, to help prevent things such as shipyards in ponds, land factories on islands, and other silly construction decisions.
It could also be a good idea to delete the method from the API. This may break some old AIs, but most encountered this issue and built their own algorithm. Doing this would prevent new developers falling into the same trap and force new algorithms to be built ( and more clever AI features )
– Lead image source: http://www.flickr.com/photos/metrolibraryarchive/4128220971/sizes/o/