A comparative study of partitioning methods for crowd simulations

The simulation of large crowds of autonomous agents with realistic behavior is still a challenge for several computer research communities. In order to handle large crowds, some scalable architectures have been proposed. Nevertheless, the effective use of distributed systems requires the use of partitioning methods that can properly distribute the workload generated by agents among the existing distributed resources.In this paper, we analyze the use of irregular shape regions (convex hulls) for solving the partitioning problem. We have compared a partitioning method based on convex hulls with two techniques that use rectangular regions. The performance evaluation results show that the convex hull method outperforms the rest of the considered methods in terms of both fitness function values and execution times, regardless of the movement pattern followed by the agents. These results show that the shape of the regions in the partition can improve the performance of the partitioning method, rather than the heuristic method used.