AN INTERACTIVE MODEL FOR STEERING BEHAVIORS OF GROUPS OF CHARACTERS

Abstract

This article presents an approach for generating steering behaviors of groups of characters based on the space colonization algorithm that has been used in the past for generating leaf venation patterns and tree structures. In this article, the underlying idea of the space colonization algorithm is adapted to control the motion of virtual characters, providing robust and realistic group behaviors by adjusting just a few parameters. The main contributions of this work are the robustness, flexibility, and simplicity of the proposed approach to control groups of characters in an interactive way, providing path planning and a series of group behaviors, such as group formation, alignment among others. We also introduce a possible extension of this model to provide collision avoidance among agents, mainly focused on crowd simulation. In addition, an interactive tool is provided to allow an easy manner for controlling the motion of virtual characters.

INTRODUCTION

Intelligent virtual agents (IVAs) are virtual characters that try to mimic several characteristics of real humans, such as interaction with other agents and the environment, and that present some level of autonomy. Within the context of IVAs, the development of easy and interactive manners to control the motion of virtual objects is an important open problem that present application in different areas, such as computer graphics and robotics. In particular, steering behaviors of groups of characters is important in games, movie productions, simulation tools, among others. Indeed, this technology can be applied in any situation in which mobile entities can be simulated.

Many models have been proposed in the past years, aiming to provide different ways to steer behaviors of groups, as discussed in Section 2. However, in spite of all existing methods, the current state-of-the-art lacks of flexibility. This article presents an approach for steering groups of virtual agents that can be used to generate different types of behaviors with simple changes in the proposed model. In fact, the main advantages of proposed model are (i) robustness, allowing the simulation of realistic behaviors in low and medium density of virtual agents; (ii) simplicity, since the just a few parameters are required; and (iii) flexibility to simulate a series of different behaviors, ranging from path planning to group formations. In addition, this article presents an interactive tool to create and control characters motion and behaviors in real time that could be used to control groups of any type of entities (fishes, birds, humans, etc.) in virtual spaces.

The proposed approach is an extension of our work published recently (Rodrigues et al., 2009), that was inspired in a biological algorithm, based on competition for space in a coherent growth of veins and branches (Sachs, 1969). We adapted this idea to generate motion behavior of groups, which also compete for space to move realistically, avoiding collisions, as described in Section 4. It should be noticed that the main scope of this article is focused on individuals motion by proposing tree paths and group behaviors. The main point in Rodrigues et al. (2009) is that groups of individuals can only be recognized if density of people is not high, because group structures are not visible in highly dense crowds. This article extends the previous work in Rodrigues et al. (2009) by proposing a free-of-collision motion of crowds of people. In addition, an interactive tool to facilitate characters control is described, and new experimental results are presented.

The remainder of this article is organized as follows. In the next section we discuss some works found in literature, whereas in Section 3 the space colonization algorithm is described. In Section 4 we describe our model to provide characters motion and in Section 5 the steering behaviors of groups. Section 6 presents an extension of the original conference article (Rodrigues et al., 2009) to crowds, as well as an interactive tool to create the virtual agents and environments. Section 7 discusses some obtained results, whereas Section 8 draws final considerations.

RELATED WORK

The simulation and control of virtual groups have been studied since the early days of behavioral animation. Two seminal articles are related to models based on agents, which have some level of autonomy and individuality. Reynolds (1987) simulated flocks of bird-like entities called boids, obtaining realistic animation by using only simple local rules. Tu and Terzopoulos (1994) created groups of artificial fishes endowed with synthetic vision and perception of the environment, which control their behavior.

A specific problem related to path planning is the generation of realistic motion along the path. LaValle (1998) introduced the concept of a rapidly exploring random tree (RRT) as a randomized data structure for path planning problems. An RRT is iteratively expanded by applying control inputs that drive the system slightly toward randomly-selected points. Choi et al. (2003) proposed a model based on a probabilistic path planning and hierarchical displacement mapping to generate a sequence of realistic movements of a human-like biped figure to move from a given start position to a goal with a set of prescribed motion clips. Metoyer and Hodgins (2004) proposed a method for generating reactive path following based on the user's examples of the desired behavior. Dapper et al. (2007) proposed a path planning model based on a numerical solution for boundary value problems (BVP) and field potential formalism to produce steering behaviors for virtual humans. Rodríguez et al. (2007) proposed a heuristic approach to planning in an environment with moving obstacles using dynamic global roadmap and kinodynamic local planning. Kallmann and Mataric (2004) proposed dynamic roadmaps for online motion planning in changing environments. When changes are detected in the workspace, the validity state of affected edges and nodes of a precomputed roadmap are updated accordingly.

More specifically concerning the motion of groups, Kamphuis and Overmars (2004) introduced a two-phase approach, where a path for a single agent (a backbone path) is generated by any motion planner. Next, a corridor is defined around the backbone path and all agents stay in this corridor. Rodríguez et al. (2007) proposed a model using a roadmap providing an abstract representation of global environment information to achieve different complex group behaviors that cannot be modeled with local information alone. Lien et al. (2005) proposed ways using roadmaps to simulate a type of flocking behavior called shepherding behavior in which outside agents guide or control members of a flock. Data-driven models are quite recent in comparison with other methods and aim to record motion in a preproduction stage or to use information from real life to calibrate the simulation algorithms. One example is the work proposed by Lien et al. (2005), describing a model for controlling groups motion based on automatic tracking algorithms.

Despite the existence of several algorithms for path planning and steering of groups, interfaces are usually not interactive, and sometimes even the parameters are not easy to be defined. This article proposes a new model for steering behaviors, where group behaviors can be easily calibrated, through an interactive interface, while keeping diversity of generated results. Considerations about the methods proposed here are presented in the next sections.

BIOLOGICALLY INSPIRED ALGORITHM

The basic model for agents navigation is based on the space colonization algorithm, which has been previously used to develop leaf venation patterns (Runions et al., 2005) and tree structures (Runions et al., 2007). The venation model simulates three processes within an iterative loop: leaf blade growth, the placement of markers in the free space, and the addition of new veins. The markers correspond to sources of the plant hormone auxin, which, according to a biological hypothesis, emerge in the growing leaf regions not penetrated by veins. The markers that are approached by the advancing veins are gradually removed, because the space around them is no longer free. As the leaf grows, markers in the free space are added in the space between existing veins and markers. This process is detailed previously in Runions et al. (2005). Here, the venation model has been adapted to animate groups of characters (Rodrigues et al., 2009). Indeed, the key idea is to represent the space in an explicit way, using a set of markers (dots in the space). The markers define the “walkable space” through a discrete set of points, which are used to compute the paths of agents. These markers should be randomly distributed (according to a uniform probability density function) over the portions of the space that can be effectively occupied by the virtual agents, meaning that obstacles and other regions where agents should not move must not be filled with markers. Figure 1(a) illustrates an environment populated with markers. The markers allow the organization and facilitates the steering of group behaviors, as discussed in next sections.

FIGURE 1 (a) Markers (dots) are discrete representation of walkable space; (b) Darker dots describe key positions, lighter dots are related with each simulated step that generates path nodes, and between two path nodes there is the path segment.

MODEL FOR CHARACTERS MOTION

This section describes our model to provide the motion of the virtual characters. ¹ Our model based on space colonization algorithm can be used to provide path planning (from initial position to a fixed or mobile goal) as well as to direct motion of virtual agents without specific goals. The main difference between these two cases is that motion planning generates one or more coherent paths (called tree paths in this work) to reach a specific position, whereas the direct motion takes into account desired directions. So, in the last possibility, local minima are allowed, because a global path is never planned. The main application of direct motion is in situations where a specific goal is not possible, like group behavior for alignment, for instance.

Following there are the definitions of our model:

	I denote an agent in the group, having a position p (t) at each iteration t. 2
	If an agent have objectives, these positions at each time are denoted by g (t).
	If an agent does not have specific goals, it should have a direct motion d m , like in a desired group alignment.
	There is a personal space for each agent, modeled as a circular region (with radius R), that represents a “perception field” that limits the range of markers which can be used by each agent.
	G denote the tree path for an agent, computed by using the venation model proposed by Runions et al. (2005) and adapted to group animation.

A tree path is a set of locations (key positions) organized in a directional graph. Each step created in the path corresponds to a path node, whereas a path segment joins two path nodes. In our model, paths from the current position of a given agent to its goal are described through a tree, as illustrated in Fig. 1(b). In this figure, the goal is illustrated through a red flag, darker dots describe key positions where bifurcations occur, and lighter dots are related with each simulated step that generates path nodes. Between two path nodes there is a path segment, and all segments have the same length. Drawing all segments we can see the tree path generated from one agent to a specific goal.

Generating Tree Paths for Agents

The tree path G is computed through a two-stage algorithm within an iterative loop: (i) markers processing and (ii) the addition of new path nodes. The markers in Runions's (2005) model correspond to sources of the plant hormone auxin, which emerge in the growing leaf regions not penetrated by veins, according to a biological hypothesis. For path planning markers describe the “walkable space” to define the direction of a path node. During each iteration, a path node is influenced by all the markers closer to it than any other path node. Figure 2 illustrates the process of tree paths creation and evolution from agent current position to a specific goal.

FIGURE 2 In 1) agent a) in position b) goes to its goal d) avoiding collision with obstacle c). In 2) and 3) we show the evolution of tree paths growing toward to the goal avoiding collision with obstacle. In 4) the goal is reached by the tree path while agent walks into the path. It is possible to see branches of tree path that have been deleted from the tree.

For a path node n, located at the position n , the set of markers (located at positions m _i ) that are closer to n than any other node is denoted by

where N is the number of markers associated with node n. If S(n) is not empty, a new path node n′ can be created and attached to n through an edge representing a path segment. Each path node has a circular action region with radius A _r , ³ that limits the markers that must be evaluated (if they are not closer to any other path node) to compute the new direction of growth of the tree path. Figure 1(b) shows an example of a tree path computed from an agent to its goal. To provide a diversity of branch orientations generated for G, increasing the space occupation, the markers closer to each segment are allocated to it, and they cannot be used by other path segments that originate from the same agent I. On the other hand, the tree path G* associated to another agent I* can use the same markers of the tree path G. Consequently, tree paths from different agents can intercept each other. However, this fact could bring a collision situation, which is not desirable. To deal with collision-free behaviors, we used the method for minimum distance enforcement among agents, proposed by Treuille et al. (2006) and detailed in Section 4.2.

Mathematically, the algorithm for building the tree path is described as follows. Given a tree node n and a nonempty set S(n), a decision must be made whether a child node n′ related to n will be created or not. This decision is made in such a way that nodes closer to the goal are more likely to have children, achieving a wider variety of paths in the vicinity of the goal.

In the proposed approach, the node n _g that is the closest to the goal will certainly have a child, guaranteeing that the goal will be reached by at least one trajectory. The probability P(n) of any other node n having a child is given by

where ‖·‖ is the L ² norm of a vector. To decide whether a child will be created for n, a random variable ξ with uniform distribution in the interval [0, 1] is generated, and the the child is created if

It can be observed that P(n) = 1 when n = n _g , which guarantees that n _g will certainly have a child, regardless of the random value selected for ξ. Also, it is easy to verify that P(n) is monotonically decreasing with respect to the distance between n and the goal g, so that child nodes that are closer to the goal tend to have more children. If a given node n is granted a child n′, it will be created at a position n ′ through

where d (n)/‖ d (n)‖ is a unit vector representing the growth direction of the branch at node n, and α is a constant step that controls the length of the path segments. Vector d (n) is obtained based on the markers in S(n) and their coherence to the goal g :

where

are the weights of the markers computed based on a non-negative function f. This function should prioritize both markers that lead to the goal, and those that are closer to the current node n. Our choice for f that satisfies these conditions is

where θ is the angle between x and y , and ⟨·, ·⟩denotes the inner product. It can be observed that f decreases as the angle between ( g  −  n ) and ( m _k  −  n ) increases (so that markers that are aligned with the goal carry a larger weight), and also as ‖ m _k  −  n ‖ increases (so that markers closer to the node carry a larger weight as well). If the number of markers is large, d (n) will point approximately toward the goal (in fact, it can be shown that d (n) points directly toward the goal if the number of markers grow to infinity). However, if the amount of markers is small, d (n) may deviate from the goal, generating a variety of paths.

The procedure described so far creates a sequence of nodes connected by path segments but no bifurcations in the tree. To create bifurcations, one father node n must be connected to at least two different children nodes and . When the first child node is created, it retrieves the markers around it according to a “restriction distance” (so that the number of markers available to n is reduced). Then, S(n) is recomputed with this reduced set of markers.

To define if the node n will have another child, a new random variable ξ is generated, and the test in condition (3) is applied. If the condition is verified, a new child is granted to n, and it is obtained through Eq. (4), using the reduced set of markers (i.e., the remaining markers around n that were not restricted by n ₁). This node also retrieves the markers around it, and the process for creating child nodes for n is repeated until there are no markers available to n, or condition (3) fails. It should be noticed that, at each iteration, a new random variable ξ is created and compared with the probability P(n) given in Eq. (2) to decide if node n will have a child or not. Hence, some nodes may have more children than others (usually, the number of children increases near the goal, as explained before). In fact, some nodes may have just one child and do not present any bifurcation at all. Nodes that present at least two children are called “key positions,” and there is a unique path between adjacent key positions (see darker dots in Fig. 1(b)).

While a tree path is being computed, the agent is able to walk along the generated paths. Although other path planning algorithms can also be used (such as the A* search algorithm), the proposed model presents some advantages. First, for group behaviors (follow, escape, and collaborative actions such as surround behavior), one important aspect is the diversity of paths (it is desirable that a group walks to a specific goal by occupying the space with different possible paths). Another interesting aspect is that we are able to recompute our trajectories from the needed position; for example, when the target of the agent (in follow behavior) crosses the tree path, we can recompute the path from the intersection point. Further details can be found elsewhere in Rodrigues et al. (2009). The next section describes how the agents move along the tree, after the path has been computed.

Computing the Motion of Agents

Tree paths provide local goals for agents. However, an important challenge in groups motion should be treated in this model: collision avoidance. As mentioned before, tree paths G and G* related to different agents can share markers, consequently agents walking in tree paths can collide, passing by closer (or the same) path nodes. To address this problem, we used the method for minimum distance enforcement among agents, proposed by Treuille et al. (2006). Their method proposes iterations over all pairs of agents within a threshold distance t _min, symmetrically pushing them apart, so that the minimum distance is enforced, as describes in Eq. (8).

where t _min is the minimum threshold distance allowed (that was set experimentally to 0.5 m), d _ij is the distance between agents i and j, and #A _i is the number of elements in the set A _i . Consequently, modifying the position of one character impacts all other characters. We implemented a translation for pairs of agents that are closer than the minimum distance. Indeed, this strategy does not present any compromise in the computational time for a small number of agents (main focus of this work). Anyway, more details about computational time are discussed in Section 7.

There are two manners to provide agents motion. The first one is used when agents have specific goal location; the second, when there are no goals. In the later case agents are affected by the markers, which can have different weights. Indeed, markers are used as discretized information of the available space, but also they can affect differently the motion of agents, depending on associated weights. Given an agent I at the position p (t) and goal g (t), at each time iteration t and given its computed tree paths G, the next agent position is computed by

where β is a constant that controls the length of the agent step, d ( p (t)) is an orientation vector from the agent's current position p (t) to the next path node coming from tree path, indicating its local goal (and attaining the global goal g (t)). Also, we compute d _enf( p (t)), a result vector for minimum distance enforcement among agents, proposed by Treuille et al. (2006) to avoid collisions.

In the goal-based motion of the agent, which includes the tree path computing, three events should be iteratively managed:

1.	Agent's decision: When an agent reaches a key position, it should take a decision to which tree branch it should follow. This decision is considered taking into account how close to the goal the tree branch brings the agent.
2.	Branch death: There are two reasons to remove the branches in a tree: (i) when a branch was not chosen by the agent (last item), the branch and its children are removed; and (ii) when the goal changes position, branches far away from the goal (defined by the recomputing distance R d ) are removed and then recomputed to take into account the new goal position.
3.	Branch reaches agent's goal: Tree path stops growing, but the agent keeps walking along the paths until it reaches the goal.

In addition to goal-based motion, there is another manner to compute the motion agents that is useful when goals are not explicit (e.g., in formation and alignment behaviors). In this case there is no goal vector but an agent motion direction m _d , which is computed based on a variation of the weights of the markers within the agent's personal space. Given an agent I at the position p (t) at each iteration t, and given the set of M markers S( p (t)) = { m ₁, m ₂,…, m _M } within the personal space of the agent I (all markers are considered), we first find the set S′( p (t)) of M orientation vectors from agent I to all the markers in S( p (t)), to compute the agent direct motion m _d :

The motion direction m _d of the agent is computed by

which is very similar to the branch growing procedure given by Eq. (5). However, the weights w _k in Eq. (11) are not related to any goal but instead selected according to the desired behavior (see Sections 5.2 and 5.3 for details). The next position of the agent is given by

where β and d _enf( p (t)) are the same parameters used in Eq. (9). Next, we present some examples of behaviors that can be obtained using the two strategies for the motion of agents described in this section: based on goals and based on directions.

GROUPS STEERING BEHAVIORS

In addition to tree paths described in the last section, we propose group behaviors that derives from that. First, behaviors of pursuing, escaping and surrounding are described. Second, we show the possibility of representing various groups formation that can be used in entertainment as well as other applications. Then, an approach for group alignment is described, which is also important in group formation. Section 7 presents several examples of those behaviors.

Behaviors: Pursue, Escape, and Surround the Goal

The best way to describe the pursuit action takes into account a path between only two individuals (one follower and one target agent). Moreover, as a target location can change dynamically, the path between follower and target should be recomputed iteratively (as described in the last section). Figure 3(a) illustrates such behavior in two scenarios with obstacles.

FIGURE 3 (a) Pursue behavior: one agent tries to reach another one; (b) The illustrated tree path shows the way for follower agent to achieve the target.

In this behavior, once the target agent crosses the tree path of a follower agent, the tree path is recomputed from the intersection point. This behavior can be easily scaled with more than one follower agent. In the case of a group of agents following the same target, it is desirable to provide a surround behavior. A simple change in the rule to allocate markers can be used to obtain interesting results: Instead of sharing the markers among the tree paths of the pursuer agents, each tree path gathers markers from disjoint sets of markers. With this simple choice, the pursuer agents fight for space, and must find other possibilities to move. Hence, the pursue behavior arises as a consequence, as illustrated in Fig. 4.

FIGURE 4 Surround behavior: two agents try to reach another one. It is possible to observe the diversity of generated tree paths causing the surround behavior.

Finally, another small change in the path planning algorithm can provide escape behavior. In path planning, the path node is accepted in tree path when it brings the agent closer to its goal. In a escape behavior, all agents should try to get away from a predefined position c . To cope with this condition, wider variety of branches should be created far from the position c , and not close to the goal as described in Eq. (2). In fact, this behavior can be achieved by replacing P(n) in Eq. (2) by a new function P _e (n):

where n _c is the node located the farthest away from c .

If there is just one follower agent, c is exactly the position of the follower. If more than one follower agent is present, then c is obtained as the centroid of all the agents' position. Figure 5 illustrates such behavior. In this figure the escape region is automatically computed based on three follower agents, and consequently the tree path algorithm tries to bring agent outside such region.

FIGURE 5 Escape behavior: one agent tries to escape from a circular region, in which three follower agents are included.

Behavior: Groups Formation

This behavior aims to provide the formation of specific shapes, which is relevant in several entertainment applications. For instance, games and movies, as well as theatrical performances, can use such characteristics to provide group motion. There are at least two different ways to model such behavior. The predefined one considers the generation of specific goals into a shape, and the posterior distribution of the individuals into the group. The drawback of this approach is the low flexibility if a shape changes dynamically or if more agents want to participate in the performance, because it requires the recomputation of specific goals for each agent. The second approach describes an emergent behavior of agents to occupy the space corresponding to the desired shape. We adopted the last approach in our model by using markers in the space.

Initially, a shape region should be defined (as illustrated in Fig. 6, where the shapes are the letters V and H). It can be done by using our markers spray (more details can be found in Section 6.1). At the beginning, the environment has markers to allow the agents motion. Then, the user can spray markers to define the shape formation. Consequently, markers are painted over the environment, increasing the density of markers in formation shape. Yet, the markers into the target shape have increased weight to a defined constant w _max ≥ 1. The consequence is that markers into the target shape will have more importance in Eq. (11) than markers outside.

FIGURE 6 Agents form explicit shapes of letters V and H.

The algorithm is described in two steps. The first one takes into account the tree path algorithm described previously. In this case, an automatic goal into the target shape is attributed for each agent in the simulation, providing motion stimulus for each individual. The automatic goal takes into account the convex hull of the target shape, and it is selected as a random position within it. When the agent gets close to the shape region (it is identified through markers analysis, i.e., if one agent has a target marker into its personal space), the orientation vector computed in tree paths algorithm is not any more taken into account. In other words, Eq. (9) is used initially to guide the motion of agents, and then it is replaced by a modified version of Eq. (12), using the following weights w _k to obtain the motion direction m _d :

where w _max is the increased weight within the desired formation region. Larger values for w _max result in a more direct motion of each agent toward its goal, whereas smaller values lead to smoother (and slower) movement. Experimentally, we observed w _max = 10 presented good results, and used this value in all experiments.

When other agents arrive in formation shape, they fight for space, but they tend to keep inside the formation shape, because the weight of the markers is greater than outside target shape markers. Moreover, if all agents should present same specific orientation in target shape, their distribution is easily regulated after the agent entries in the shape region. The final distribution of agents for the VH shape is given in Fig. 6(c).

Behavior: Groups Alignment

This behavior, as the one described in last subsection, is useful to provide group performances in entertainment applications. Alignment of people is an interesting feature that can be used in several applications. In our model we are able to have people moving based on specific goals (using tree path algorithm; Section 4.1) as well as without goals, by changing the weights of markers into agent personal space, and then generating the motion of agents, as in last section.

For our group formation, we are able to create alignment regions with predefined weight masks for markers. One possible mask used to provide horizontal and vertical alignment is illustrated in Fig. 7, on the left. In this case, the markers into the formation mask have their weights increased according to w _k  = dist(I, k), where dist(I, k) is the Euclidean distance from the current position of agent I to the marker m _k . These weights are used to obtain the motion direction m _d used in Eq. (12). If a given marker is within the personal space of more than one agent, these agents compete for the marker. In fact, the same marker may present different weights when viewed by different agents, depending on their goals and relative position w.r.t. the marker. To minimize the chance of more than one agent reaching the same marker at the same time, the weight of the marker is increased for the agent that is the closest to it. More specifically, this weight is recomputed as the sum of the weights of that specific marker as viewed by all agents having the marker within their personal spaces, so that the closest agents tends to reach the marker faster than the others.

FIGURE 7 Left: Weight masks are used to define alignment behavior. Right: An example of generated behavior.

EXTENSION TO CONTROL CROWDS

The space colonization algorithm, briefly described in Section 3, has inspired the method we introduced in the previous sections for tree paths and steering behaviors presented in this article. The key idea is to represent empty space explicitly, using a set of markers, and to treat these points as a resource for which the agents paths in the simulation compete. Consequently, tree paths are generated as a function of free space, goals, and group behavior to be applied. Such paths present discretized goals that are achieved progressively by the agents as they move along the path. As described in Section 4.2, tree paths can share markers, so collisions among agents can happen. In the original article (Rodrigues et al., 2009), we proposed the use of an enforcement distance d _enf, defined in Eq. 8, that is used to avoid collision with other agents. In fact, the motion for each agent along its path is given by Eq. (9). On the other hand, when agents have no specific goals (e.g., groups formation and alignment), agents move according to weights defined in the space, as explained in Section 4.2. In this case, the enforcement distance is also used to avoid collisions with other agents, as shown in Eq. (12).

Although there is no theoretical limit on the maximum number of agents that can be simulated using either of the above-mentioned approaches (with or without goals), the enforcement term d _enf in Eq. (8) requires the computation of all pairwise interactions of agents within a threshold distance. Hence, the cost to compute the enforcement grows quadratically as a function of the number of agents, which could be prohibitive when dealing with crowds.

To overcome this problem in the first situation (agents with goals), this extended version of the article eliminates the enforcement term d _enf when computing the motion of agents. In this situation, the markers that were used to generate the tree paths are also considered to guide the agents. In fact, the set of markers used to generate each node of the tree path is stored in a database when the path is created. When an agent I _i reaches a node n _{i, k} in its tree path G _i , it retrieves all the corresponding markers. When it is time to move to the following node n _{i, k+1}, the motion is only possible if all the markers related to the destination node are not retrieved by any other agent I _j , j ≠ i (meaning that there is no other agent in the vicinity of its path). If that happens, agent I _i also retrieves all the markers related to n _{i, k+1}, and it keeps moving. If not, agent I _i stays still in its current position, until all the markers of the destination node are released.

If the radius A _r of the action region is greater than or equal to half the distance α between adjacent nodes n ₁ and n ₂, i.e., if A _r  ≥ α/2, then the set of markers related to either n ₁ or n ₂ covers the whole segment between these two nodes. Hence, any other pair of adjacent nodes and that intersects the segment would also share markers with either n ₁ or n ₂. Hence, if an agent moving along the nodes n ₁ and n ₂ captures the markers related to those nodes, another agent moving along and could not move, avoiding any possible collision. In all experiments, we used A _r  = α/2. Section 7 presents some experimental results in crowded scenarios.

Interactive Interface to Control Crowds

An important aspect in virtual human simulation is the behavior control. Some existing models produce interesting results; however, interfaces are not interactive and sometimes even the parameters are not easy to be defined. In our work we took considerable effort to develop an interactive tool where groups and individual behaviors could be easily defined through a sketch interface.

First, markers are in the center of our model, because they produce high impact in generated trajectories as well as in agents' behaviors. The amount of markers and their position in the space can be easily modified using the sketch interface, by interactively spraying or erasing markers. Figure 8 shows a screenshot of our prototype system that implements such interaction.

FIGURE 8 Prototype system for crowd simulation with interactive control. The user “sprays” markers (dots) on the floor. The distribution of markers directs the agents.

We used dart-throwing algorithm for generating the markers (Cook, 1986). This process is performed in preprocessing stage and recorded in a file, because it is not necessary to recompute it for same scenario. If new markers are sprayed/erased during the simulation, the changes can also be recorded in the file. This algorithm presents a computational complexity (nlog n), so we investigate the possibility of using a random distribution of markers in scenario to improve computational time. In this case we consider initialization of a grid of markers and the random process acts as a noise in markers position, providing linear complexity. Results indicate that grids and random techniques can be used without high impact in group behaviors. The evaluation included agents linear and angular velocity and trajectories smoothness. Although these analysis present similar results in both markers distribution techniques when density of markers is 60 markers/m², here we keep using dart-throwing algorithm as originally used by Runions et al. (2005). One reason for that is the fact that markers density cannot be fixed in interactive tool, because users can spray again in the same space.

Agents tend to follow paths with higher density of markers, so that local control can be achieved by increasing the number of markers along preferred paths. When markers are removed, agents immediately adjust their paths, as shown in Fig. 9.

FIGURE 9 Removing markers in the environment affect the virtual humans' trajectories (the first and second agents are influenced by the new configuration of markers.) The circle represents the marker eraser, and it has been used to narrow down the region where the agents can walk.

Besides the interactions with markers, other features are also presented, such as creation of agents, selection of one or multiple agents, definition of group behaviors to be applied, and definition of goals and paths for agents. In addition, other functionalities like illumination, texture, and camera animation are possible, as described in Musse et al. (2007).

EXPERIMENTAL RESULTS

This section presents additional results to the ones previously published (Rodrigues et al., 2009). First, we describe the main variables of the model. It is important to emphasize that these variables do not need to be recalibrated when environment or simulation scenario changes. However, they can be changed if users want to generate different results.

Parameter R is related with circular region around an agent and represents its perception field. This variable, set experimentally to 1.2 m, is used when agents are not walking in the tree path, and their motion is based on markers weight (e.g., group formation and alignment). Coherent with R, the radius of the action region A _r related to each path node, is set to the same value 1.2 m. Variables β and α are related respectively with agents step motion in the tree path and the size of path segment of tree path. Values used in all simulations are β = 0.05 m (assuming a simulation at 24 FPS) and α = 2.0 m.

Figure 10 shows an illustration of combined behaviors for formation and alignment applied together. It is interesting to perceive that in the beginning 1) agents apply a hybrid behavior (goal-based) until they have markers of interest region (star formation) into their perception region. Then, in 2) it is possible to see agents into formation region, then applying the alignment behavior, when weight masks are visible 3). Finally, agents occupy the formation region and in the same time they keep aligned as shown in 4). The possibility of combine different behaviors (with or without tree paths and goals) is a great potential of our method.

FIGURE 10 This figure shows four different time steps in the formation and alignment behaviors applied together. In 1) and 2) agents are going into a shape region. In 3) and 4) agents align their locations as a function of other agents.

The escape behavior is implemented based on a small change in tree paths algorithm. Indeed, instead to be attracted by the goal, the escape behavior is attracted by the nodes which are far away from a specific location, as described in Section 5.1. Figure 11 illustrates this behavior when one target agent is followed by four other agents.

FIGURE 11 In 1), a, b, c, and d are related, respectively, with follower agent, target agent, obstacle, and a circular region, which includes all follower agents. In 2) and 3) tree path is evolving and in 4) target agent is walking and escaping from follower agents.

The computational performance of tree path technique is very dependent on the number of generated nodes, which also takes into account the simulated environment (obstacles, number of agents, distance to the goal). In Fig. 12 we show the time ⁴ consumed for 1, 5, and 10 agents, including the number of iterations performed in the simulation. It is important to note that maximum number of iterations observed in our simulations is 49, meaning that at most 49 iterations are required by the agents to reach their goals in the simulated environment. Because our model is focused on low density scenarios, we have tested a maximum of 50 agents to better visualize the groups behavior, achieving real-time performance. However, according to the worst possibility (49 iterations to reach the goal) in Fig. 12, it is theoretically possible to compute tree paths for thousands of agents.

FIGURE 12 Computational time (ms) for processing 1, 5, and 10 agents, considering the evolution of tree paths.

Figure 13 shows crowd simulated using our method. In these images it is possible to see lane formation, which is an emergent behavior expected in crowds. Indeed, this effect is created because it takes less effort for people to follow immediately behind someone who is already moving in their direction than it does to push their own way through a crowd. Emerged as a function of least effort hypothesis, the formation of lanes arises, because people change trajectory whenever they encounter an entity moving in the opposite direction. This action forms chains of entities walking in line, as we would expect.

FIGURE 13 Left: Two groups are approaching to another. Right: Lanes can be visualized.

FINAL REMARKS

This article presented an algorithm to provide motion of groups of agents. It is based on a biologically inspired technique used in the past for generating leaf venation patterns and tree structures, simulating the competition for space between growing veins or branches. Here, we presented some behaviors to simulate groups of agents, such as group path planning (we called tree paths), pursue behavior, surround behavior, escape behavior, groups formation, and groups alignment. The key innovation is the simple way in which the paths are created, by “observing” and “occupying” free space, which is represented using a set of marker points, which leads to a simple yet computationally effective implementation of the competition for space. Global tree path is modeled by biasing the influence of the captured marker points according to their agreement with each agent's direction to its goal, which can be assigned to individual agents or groups. In addition, agents motion can be goal based or influenced by variation of weights attributed to markers, originating alignment and formation behaviors.

Comparing with other models, although RRT (LaValle, 1998) explores uniformly the “walkable space,” defining positions randomly in this space that will guide the expansion of the search tree, in the proposed model the space is previously discretized using a uniform distribution. Once the space is known, the proposed model considers weighted positions so that the growth of branches is directed to the goal. This difference allows optimizing the construction of the tree and the search for the path in this structure. Compared with roadmaps, the proposed model allows the generation of a connected tree using a small amount of edges. In a roadmap (Lien et al., 2005), the performance of the connected graph is impaired due to the number of edges necessary to explore the entire space. The proposed model also requires single nearest-neighbor queries, whereas roadmaps require more-expensive k-nearest neighbor queries.

This article also presents an extension to the method providing collision avoidance among agents into a crowd. This extension is naturally integrated with markers and their association in the space, which path nodes. In this idea, as described in Section 6, the markers associated to specific path nodes can only be used by agents in such nodes. Consequently, agents avoid collision with others. As future work, we intend to provide other group behaviors, focused on individualities, such as agents skills.

Acknowledgments

This work was developed in collaboration with HP Brazil R&D and Brazilian research agencies CNPq, FINEP, and CAPES.

Notes

Details are described in PhD thesis authored by Bicho (2009).

For the sake of clarity, the time index t will be removed from this point on and used only when necessary.

Its size can be calibrated, but normally we use the same radius R defined for the agent personal space.

Average of 20 simulated experiments. These results were obtained using monothread implementation without characters' rendering on Intel® Core™ 2 Duo 2.2 GHz, 3 GB DDR2 at 667 MHz and NVIDIA® GeForce® 8400 M GS 128 MB.