A Discretized Overlap Resolution Algorithm (DORA) for resolving spatial overlaps in individual-based models of microbes

Individual-based modeling (IbM) is an instrumental tool for simulating spatial microbial growth, with applications in both microbial ecology and biochemical engineering. Unlike Cellular Automata (CA), which use a fixed grid of cells with predefined rules for interactions, IbMs model the individual behaviors of cells, allowing complex population dynamics to emerge. IbMs require more detailed modeling of individual interactions, which introduces significant computational challenges, particularly in resolving spatial overlaps between cells. Traditionally, this is managed using arrays or kd-trees, which require numerous pairwise comparisons and become inefficient as population size increases. To address this bottleneck, we introduce the Discretized Overlap Resolution Algorithm (DORA), which employs a grid-based framework to efficiently manage overlaps. By discretizing the simulation space further and assigning circular cells to specific grid units, DORA transforms the computationally intensive pairwise comparison process into a more efficient grid-based operation. This approach significantly reduces the computational load, particularly in simulations with large cell populations. Our evaluation of DORA, through simulations of microbial colonies and biofilms under varied nutrient conditions, demonstrates its superior computational efficiency and ability to accurately capture microbial growth dynamics compared to conventional methods. DORA’s grid-based strategy enables the modeling of densely populated microbial communities within practical computational timeframes, thereby expanding the scope and applicability of individual-based modeling.Author summary: In microbial ecology and biochemical engineering, individual-based models (IbMs) are essential for simulating population dynamics at the cellular level. A key challenge is resolving spatial overlaps among cells in large-scale simulations. We introduce DORA, an algorithm that translates cell positions into a grid-based occupancy matrix, applies a diffusion-like process to resolve overlaps, and then translates the resulting adjustments back to individual cell movements. This approach reduces computational complexity, making large-scale IbM simulations more feasible.