Cellular Rules

As was discussed, potential fields provide a means for deducing the optimal direction for any point on the map. This essentially provides each entity with a feel for the best direction of travel, but what we would really like, is for each entity to make its decision based on more than just a feel for the best direction. This means that each entity will thus be required to query the state of its environment and make decisions based on this. This is not unlike how a human would consider its choice of movement. Given that someone is leaving a building, this person has a sense of which direction provides the shortest path to the exit. This is global routing information, essentially the same as what the potential field provides. The person would then make a series of quick decisions based on its surroundings. This could involve checking whether a direction is occupied, prioritising directions based upon how much they deviate from the desired direction, and whether the state of nearby people will affect their choice.


In order to build up a successful CA rule-set, it makes sense to start with the simplest example possible and then build upon each example and evaluate the incremental changes in order to verify its correctness.

One of the beauties behind CA is the emergent complexity that can arise from very simple rules being applied to many concurrent interacting entities. This is observed best in the Game of Life, where 3 rules were defined to determine whether a cell would, grow, live, or die. There is no reason why the same concept shouldn't apply to the behaviour of pedestrians, thus I will be investigating `bare bones' rule-sets.

I will be testing simple `if cell is empty then move into cell' rules. Given the flexibility and scope available for rule-set design, this may seem like an over simplification -- however, as stated before I aim to find the simplest rules possible that achieve the desired results, thus extra complexities may not be necessary.

Below are three simple rules, each check represents an occupancy test, that if is empty, the entity moves into it.


Ruleset 1

  • Check cell directly ahead

The simplest rule-set possible that results in a move being made is to check directly ahead, and if this cell is empty, move into it. This rule-set provides no real intelligence for each entity, since the move made is always in the suggested direction provided by the potential field.


Ruleset 2

  • Check cell directly ahead
  • Check diagonals cells (with no preference to either side)

For a large crowd to use `rule-set 1', one can easily see that there is not going to be any overtaking or jostling for position; this intelligence has not yet been incorporated into the rule-set. Thus the next logical step is to check diagonals after checking the forward direction. This allows pedestrians to overtake others and jostle for better positions.

Ruleset 3

  • Check cell directly ahead
  • Check diagonals cells (with no preference to either side)
  • Check adjacent cells (with no preference to either side)

The next step from `rule-set 2', upon all checks forward and diagonal failing, is to consider the cells on either side. This adds a more mobile element to the entity, due to the new ability for sidestepping around crowds. This is likely to lend itself to a more turbulent crowd, since sidestepping is likely to occur in very crowded situations.

I will not consider any movements where the entity considers cells behind itself since I believe this an unrealistic scenario. Very rarely have I seen pedestrians queuing up, only to take a step away upon realising they can't move forward anymore.

next >> Software