Random Instantiation Without Overlapping with Unity3D

Objects are cloned onto the scene via instantiation. An enemy character, an obstacle or various props that the player has to maneuver in the scene as part of the game play experience. Mass random instantiation deployed in match 3 and shooter games sees the algorithm produces up to hundreds of spawns in a single run. There are many challenges in securing the most optimized run in such cases as the determinants or variables that affect the spawning process is synonymous with game play. The codes of the methods applied in the WebGL application below are explained here.

Some challenges in algorithm design :

  • keeping the dispersed clones from intersecting with one another in a confined environment;
  • ensuring the consistency and integrity of distribution that takes place usually inside a container like a panel (2D) or a sphere (3D);
  • finding the balance in representation among the list of items;

The containers’ area and volume is readily translated into local position and scale in Unity. Personally I find that it can be confusing for beginners in game programming understanding the principles of world space and local space in object scaling and positioning. Perhaps, it would help to keep that in mind.

There are 2 methods to prevent randomly spawned objects from intersecting:

  • Begin the run by mathematically subdividing the space within the container and captured the centered positions (Vector2 or Vector3) of these subdivided lots into a master List. In every single spawn, a randomly selected position from the master List is matched against a randomly selected game object from the spawn list. The match is done by checking the available lots in the master List using conditional loops for every spawn allocation. This method could fill up the entire container with evenly aligned spawned objects as seen in Candy Rush in a grid-like situation. The final number of spawned objects is predictable and exact.
  • The other method deploys a less orderly approach in allocation. The area or volume of the container is calculated when the program first started, much like the first method, but instead of subdivision, we include a padded perimeter around the container to keep the spawns from intersecting with the boundaries of the container. The maximum number of spawns are instantiated in a single main loop run with randomly selected locations (Vector2 or Vector3). A master List is used to contain these spawned objects. The intersected spawns are removed, replenished and rechecked against the master List using a nested loop. The final number of spawned objects depends on the iterative processing within the nested loop and the number of counts decided by the programmer beforehand, among other determinants. The spawns are disorderly distributed throughout the container and the final result is not certain.

The second method is further illustrated with a running example included:

A larger instantiation size is applied here that could spawn up to a maximum target of 100 objects at 100 iterative nested loop runs. Depending on other factors, a larger number of iterative loop counts could only produces the maximum number of end objects to a certain point. Other determinants include:

  • Size of container (panel used in the illustration;
  • the size of perimeter padding;
  • the scale of the spawned objects relative to the container’s size;
  • the targeted number of spawned items;
  • the number of iterations programmed to check, remove and randomly replenished the intersected items. It is a repetitive process that doesn’t come with the programmed intelligence to undo previous mistakes (like machine learning). Hence the randomly selected replenishment may also create further intersections. The end result is thus not warranted.

The viability of this method needs further validation. While repeated runs seem to indicate a fairly even distribution of reds, blues and greens, some minor investigative, statistical check could establish if there exists oddities in patterns that could affect game play. Presumably we could design an AI for that in a scope beyond this level.

Leave a Reply

Your email address will not be published. Required fields are marked *