The implementation of the numerical algorithm for a crowd movement can be split into three major parts: (i) solving of the Eikonal equations in the domain of interest to obtain the potential; (ii) calculation of fluxes along the cell-faces of two-dimensional control volumes; (iii) calculations of the crowd density. The entire algorithm can be split into the following operations:
1.A numerical mesh of the domain is created and an initial crowd density distribution is set.
2.Using the crowd density distribution, the speed and cost distribution are calculated.
3.The Eikonal equation is solved using the speed and cost distributions, resulting in the potential ϕ.
4.The gradient of ϕ is calculated, and, combined with the speed distribution, the velocity field is obtained.
5.The fluxes in each cell are calculated from the density distribution and the velocity field in the center of control volumes.
6.Using the calculated fluxes, the density distribution at the next time (t + Δt) is calculated.
7.Steps 2 to 6 are repeated until the desired time is reached.
A graphical representation of the algorithm is shown in Fig.
1 (enclosed in red rectangle). Next, we provide some numerical details of the algorithm. The Eikonal equation is solved by applying a fast sweeping method and the Godunov upwind difference scheme, as proposed in [
15]. The discretised form of the Eikonal equation (
3) can be written as:
$$ \left( \left( \phi_{(i,j)} - \phi_{x\min}\right)^{+} \right)^{2} + \left( \left( \phi_{(i,j)} - \phi_{y\min}\right)^{+} \right)^{2} = c_{(i,j)}^{2}h^{2} $$
(17)
where
ϕ(i,j) indicates the potential in the control volume cell (
i,
j). Here, the plus sign indicates the positive part:
$$ \left( \phi_{(i,j)} - \phi_{x\min}\right)^{+} = \left\{\begin{array}{l l} \phi_{(i,j)} - \phi_{x\min} & \ \ \ \text{ if }\ \ \ \phi_{(i,j)} - \phi_{x\min}>0 \\ 0 & \ \ \ \text{ if }\ \ \ \phi_{(i,j)} - \phi_{x\min}\leq 0 \end{array}\right. $$
(18)
where
\(\phi _{x \min }\) and
\(\phi _{y \min }\) are defined as the smallest neighboring values in the
x- and
y-direction, respectively, and are calculated as:
$$ \phi_{x\min} = \min\left( \phi_{(i-1,j)},\phi_{(i+1,j)} \right), \ \ \ \phi_{y\min} = \min\left( \phi_{(i,j-1)},\phi_{(i,j+1)} \right) $$
(19)
Boundary conditions at walls are implemented by assigning numerically very high values of the potential. At exits, zero values of the potential are specified and surrounding cells are extrapolated with a radius of 2
h into the domain. The discretised form of Eq.
17 has a unique solution:
$$ {\phi}_{(i,j)}^{*} = \left\{\begin{array}{l l} \min\left( \phi_{x\min}, \phi_{y\min}\right) +c_{(i,j)}h &\ \ \ \text{ if }\ \ \ \left|\phi_{x\min} - \phi_{y\min} \right| \geq c_{(i,j)}h \\ \displaystyle\frac{\phi_{x\min} + \phi_{y\min} + D}{\displaystyle 2} & \ \ \ \text{ if }\ \ \ \left|\phi_{x\min} - \phi_{y\min} \right| < c_{(i,j)}h \end{array}\right. $$
(20)
where
$$ D = \sqrt[]{2c_{(i,j)}^{2}h^{2} - \left( \phi_{x\min} - \phi_{y\min}\right)^{2}} $$
(21)
and the potential can be updated from:
$$ \phi_{(i,j)}^{new} = \min\left( \phi_{(i,j)}^{old},{\phi}_{(i,j)}^{*} \right) $$
(22)
By sweeping the domain, alternating in four different orderings, the potential
ϕ is updated until convergence is reached. The alternating ordering used is:
$$ \begin{array}{@{}rcl@{}} (1)\ i &=& 1 : N_{x} , j = 1 : N_{y}; \ \ \ \ \ (2)\ i = N_{x} : 1 , j = 1 : N_{y}; \\ (3)\ i &=& N_{x} : 1 , j = N_{y} : 1; \ \ \ \ \ (4)\ i = 1 : N_{x} , j = N_{y} : 1; \end{array} $$
(23)
With the potential found, the velocity field along which the crowd moves can be solved. The direction is provided by the negative gradient of the potential, whereas its magnitude in each cell is given by the speed distribution provided from:
$$ \mathbf{v} = - \frac{\mathbf{\nabla} \phi}{ \left|{\nabla \phi} \right|}V\left( \rho_{crowd}\right) $$
(24)
The gradients of the potential are calculated from the central-differencing scheme as
$$ \left( \frac{\partial \phi}{\partial x} \right)_{(i,j)} = \left( \frac{\phi_{(i+1,j)} - \phi_{(i-1,j)}}{2 {\Delta} x} \right), \ \ \ \left( \frac{\partial \phi}{\partial y} \right)_{(i,j)} = \left( \frac{\phi_{(i,j+1)} - \phi_{(i,j-1)}}{2 {\Delta} y} \right) $$
(25)
With a known velocity field, the corresponding crowd density flux can be calculated as
$$ \mathbf{f}_{(i,j)} = \rho_{{crowd} (i,j)} \mathbf{v}_{(i,j)} = f_{x (i,j)} \hat{x} + f_{y (i,j)} \hat{y} $$
(26)
However, we have to evaluate the flux across the cell faces, which can be done by applying the Lax-Friedrich’s scheme as:
$$ \begin{array}{@{}rcl@{}} \left( \hat{f}_{x} \right)_{(i+1/2,j)} &=& \frac{1}{2} \left[ f_{x (i+1,j)} + f_{x (i,j)} - \alpha_{x j} \left( \rho_{(i+1,j)} - \rho_{(i,j)} \right) \right] , \\ \left( \hat{f}_{y} \right)_{(i,j+1/2)} &=& \frac{1}{2} \left[ f_{y (i,j+1)} + f_{y (i,j)} - \alpha_{y i} \left( \rho_{(i,j+1)} - \rho_{(i,j)} \right) \right] \end{array} $$
(27)
where
$$ \begin{array}{@{}rcl@{}} \alpha_{x j} = \max\limits_{i} \left( V \frac{\left|\displaystyle\frac{\partial \phi}{\partial x} \right| }{|\nabla \phi |}\right)_{(i,j)}, \ \ \alpha_{y i} = \max\limits_{j} \left( V \frac{\left|\displaystyle\frac{\partial \phi}{\partial y} \right| }{|\nabla \phi |}\right)_{(i,j)} \end{array} $$
(28)
Finally, the discretised form of crowd conservation can be written as:
$$ \begin{array}{@{}rcl@{}} \frac{d\rho_{{crowd} (i,j)}}{dt} + \underbrace{\frac{\left( \hat{f}_{x}\right)_{(i+1/2,j)} - \left( \hat{f}_{x}\right)_{(i-1/2,j)}}{{\Delta} x} + \frac{\left( \hat{f}_{y}\right)_{(i,j+1/2)} - \left( \hat{f}_{y}\right)_{(i,j-1/2)}}{{\Delta} y}}_{\displaystyle F(\rho_{crowd}, \mathbf{v} )=0} = 0 \end{array} $$
(29)
where Δ
x and Δ
y are the sizes of the control volume (
i,
j) which are taken to be equal to the grid spacing
h. The time rate of change is calculated using the implicit 3rd order Runge-Kutta method (here we applied so called Radau IA scheme, [
16]) as follows:
$$ \begin{array}{@{}rcl@{}} \rho_{crowd}^{t+{\Delta} t} = \rho_{crowd}^{t} + {\Delta} t \sum\limits_{i=1}^{r} b_{i} K_{i} \end{array} $$
(30)
with
$$ \begin{array}{@{}rcl@{}} K_{i} = -F \left( t + c_{i} {\Delta} t, \rho_{crowd}^{t} + {\Delta} t \sum\limits_{j=1}^{t} a_{ij} K_{j} \right) \end{array} $$
(31)
where all constants are given in Table
2.