Conquest Algorithm for Stochastic Filling of Two-Dimensional Discrete Grids with Connected Regions

The object of research is the process of procedural coloring of a two-dimensional discrete space with topological constraints. A new algorithm is proposed that solves the widespread problem of generating meaningful stochastic connected regions on two-dimensional discrete fields. A study was conducted in which a clear formulation of the task was given and illustrated by constructing a game board for a modified version of the classical N-Queens problem. The task is to implement an algorithm able to create an arbitrary N x N board (for any manually specified N > 0). The board must then be filled procedurally with connected regions. An analysis of existing algorithms commonly used in procedural generation for related industries was carried out. The following methods were examined: Gradient Perlin Noise, Cellular Automata, Wave-Based Flood Fill and Random Walk. It was concluded that, in their classical form, these algorithms are not suitable for procedural construction of a game board for the chosen task, so a new method derived from the random-walk approach was proposed. The proposed algorithm introduces a set of agents, which – in this context – are the queens on a chessboard. Each agent moves in turn, but both the possibility of making a move and the choice of orthogonal direction is driven by additional criteria, as such: turn skip formula, empty cells bias against controlled ones, borderline cells bias against inner and prohibition of stepping onto the cells owned by other agents. The algorithm was implemented in the C# programming language. The program includes the ability to run several consecutive generations and to compute metrics for the shapes obtained on the grids. To evaluate the success of the proposed algorithm the following metrics were used: average elongation, average rectangularity, average roughness, maximum elongation, maximum rectangularity and minimum roughness. In addition, an efficiency metric was calculated from the complexity standpoint – namely, the total number of agents steps divided by the grid area. To measure efficiency and collect the metrics, one thousand experiments were carried out for the board sizes of N x N, where N = 8, 12 and 20. The results show that the algorithm operates correctly, fulfils the stated task, and is efficient.