A Proper Building Placement Algorithm

[tomjn]

At the moment Shard uses closestbuildsite, which is an algorithm implemented by the engine for figuring out where to place buildings. It does the job, but it's a bit rubbish.

It also looks like eronoobos' version has some issues, as demonstrated with a quick chat with the EvoRTS players.

So, we need a building placement algorithm with these requirements:

• Configurable grid size
• Handles spacing around buildings
• Can have temporary blocking zones to define areas that shouldn't be built on, e.g. some games have control points, or units that are planned but haven't been started yet
• Is aware of the builders foot print and accounts for it. Units don't move out of the way if they're on top of the target and it can break Shard
• Is aware that different buildings need different places to build, e.g. extractors, shipyards, vehicle factories, etc
• Maintains a map that's updated as units are built and die

Bonus optimisations:

• Instead of searching the entire map, break the map up into landmasses and bodys of water so that it doesn't waste time searching nearby inaccessible places
• Be able to place certain structures right next to each other
• A widget to visually see this map ingame for debugging purposes
• Precalculating stuff
• A behaviour for deployed units and construction units so that when they're stationary they block out the position they're at so other units don't try to build on top of them and fail
• Paths and corridors?

[tomjn]

Example of one of the issues the ShardLua placement algorithm has:

NTai tried to solve this by beginning the search at a random offset from the builder. I wonder if it's wise to use the position of the builder as the search location? Perhaps if extractors and other predefined units could be used as starting points?

There's also the option of instead trying to find the edge of the nearest cluster of buildings and then try to place a structure closest to that?

I'm also mindful that some games may have limitations that need to be accounted for. E.g. in Starcraft, Zerg can only build on Creep, and Protoss need to place pylons

[tomjn]

Recent advances have resolved this