포스트

Boids Simulation (1)

Boids Simulation

게시 업데이트
Preview Image
By Seungmin Lee
21 분

들어가며

Boids는 Craig W. Reynolds의 1987년 논문인 Flocks, Herds, and Schools: A Distributed Behavioral Model 에서 제시된 개념으로, 조류의 군체를 시뮬레이션하는 모델이다. 해당 논문의 전문은 이곳에서 확인할 수 있다. 또한 boid는 bird-like를 뜻하는 “bird-oid”의 줄임말이다.

This paper refers to these simulated bird-like, “bird-oid” objects generically as “boids” even when they represent other sorts of creatures such as schooling fish.

Boid는 bird-like를 뜻하는 “bird-oid”의 줄임말이다. Boids model은 간단한 규칙 몇개를 따르는 agent-based model로, 이를 통해 복잡해보이는 군체(다량의 agents)의 행동을 만들어낼 수 있다. 본문에서 사용하는 Code는 서울대학교 컴퓨터공학부 원정담 교수님의 Advanced Graphics 강의 자료에 있는 Skeleton Code를 활용하여 작성되었다. 이는 py-script를 바탕으로 python을 활용한 3d interactive 환경을 javascript를 통해 인터넷 브라우저로 사용할 수 있도록 만들어져 있어 간편하게 블로그에 업로드할 수 있었다.

Boids Simulation 사용해보기

init-simulator 초기 실행 시 볼 수 있는 화면. 포식자/장애물의 추가와 여러 parameter를 조절 가능하다.

Basic Boids

논문에서 제시된 boid의 가장 대표적인 규칙은 다음과 같다.

  1. Collision Avoidance : avoid collisions with nearby flockmates
  2. Velocity Matching : attempt to match velocity with nearby flockmates
  3. Flock Centering : attempt to stay close to nearby flockmates

boid는 이 3개의 대표적인 규칙을 바탕으로 각 time step마다 새로운 Acceleration을 생성하여 다음 Vector Update에 적용한다. 논문에서는 기본적인 개념을 설명하고 있고 코드 구현은 다음의 사이트에서 확인할 수 있는 pseudo code를 참고했다.

Pseudo Code

이를 적용한 boids의 움직임은 초기 상태에서 시뮬레이션을 실행시키면 확인할 수 있다.

simple-boid

Collision Avoidance

Collision Avoidance Collision Avoidance의 시각화

당연하게도 boid는 서로 부딪히고 싶어하지 않는다. 이를 구현하는 것이 바로 규칙 1번이다. Pseudo code에서는 두 boid가 일정 거리 이상 가까워졌을 경우 서로의 반대 방향으로 밀어내는 힘을 만들어낸다. python으로 구현한 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13

def separation_rule():
  # boidsPosition, boidsVector, boidsNumber
  global boidsP, boidsV, boidsN

  sepV = np.zeros((boidsN, 3))
  
  for i in range(boidsN):
    for j in range(boidsN):
      if i != j:
        if abs(dist(boidsP[j], boidsP[i])) < 7:
          sepV[i] -= (boidsP[j] - boidsP[i])

  return sepV / 50 * separation

여기서 거리가 7 미만인 것이나 sepV를 50 * separation(사이트 상단의 slider로 조절 가능)로 나누는 것은 parameter의 일종으로 추후에 나올 규칙 2번과 3번에도 동일한 parameter가 존재한다. pseudo code에서도 적절한 parameter를 제시해주고는 있으나 구현 시에 적절하지 못한 결과가 나와서 임의로 조절하였다.

구현에서 특이한 점은 일정거리만큼 가까워졌을 경우 서로의 반대방향으로 “거리의 2배만큼의 힘”이 작용한다는 점이다. 이는 Smooth Motion과 관련이 있는데 두 개체의 거리가 매우 가까울 경우 작은 힘이 작용하기 시작하여 time step이 진행되며 서서히 빠르게 멀어지게 된다. 따라서 가까운 두 boid에 대해 부드러운 애니메이션이 만들어진다. 그렇다면 두 boid가 인지 경계에 걸쳐있을 때 너무 과한 힘이 작용하는게 아닌가 싶을 수 있는데 이는 인지 범위가 매우 작기 때문에 크게 드러나지 않는다.

물론 parameter tuning을 적절하게 해주는 것도 중요하다. 인지 범위가 너무 크거나 sepV 값이 적절하게 작지 않을 경우 정상적이지 않은 결과를 맞이할 수도 있다.

Seperation Fail sepV값이 비정상적으로 큰 경우 - boid가 서로 멀어지기 위해 통통 튀는 모습을 확인할 수 있다.

Velocity Matching

Velocity Matching Velocity Matching의 시각화 / 붉은 화살표(속도)의 평균에 focused boid의 속도를 맞춘다.

Velocity Matching은 Collision Avoidance와 상호 보완적인 관계를 지닌다. Collision Avoidance는 서로의 속도는 관계없이 상대적인 위치를 바탕으로 새로운 가속도를 계산한다면 Velocity Matching은 위치는 관계없이 주변 boids의 속도를 바탕으로 새로운 가속도를 계산한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def alignment_rule():
  global boidsP, boidsV, boidsN
  alignV = np.zeros((boidsN, 3))
  for i in range(boidsN):
    cnt = 0
    for j in range(boidsN):
      if i != j and dist(boidsP[j], boidsP[i]) < recog_range:
        alignV[i] += boidsV[j]
        cnt += 1
  if cnt > 0:
    alignV[i] /= cnt
  else:
    alignV[i] = boidsV[i]

  return (alignV - boidsV) / 600 * alignment

구현은 간단하다. recognize range 안으로 들어온 boids의 속도의 평균을 계산하여 현재의 속도와 얼마나 차이가 있는지를 계산한 뒤 그 방향으로 힘을 작용해준다. 논문에서는 규칙 1의 Collision Avoidance를 Static Collision Avoidance라고 언급하며 Velocity Matching을 Predictive Collision Avoidance라고 언급하고 있다. 왜냐하면 만약 boid 하나가 주변의 boids와 적절하게 Velocity Matching을 성공할 경우 충돌할 가능성이 매우 적어지기 때문이다. 따라서 Collision Avoidance와 Velocity Matching은 상호보완적이라고 볼 수 있다.

Flock Centering

Flock Centering Flock Centering의 시각화 / Center of the flock의 방향으로 힘이 작용한다.

Flock Centering은 boid가 주변의 boids의 중앙에 위치하고 싶어하는 경향을 나타낸 것이다. 인지하고 있는 영역 내의 “center of the flock”로 향하면 결국 주변의 boids와 가까이 가게 되기 때문에 boids가 서로 붙어서 날아다니게 되는 결과를 만든다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def cohesion_rule():
  global boidsP, boidsV, boidsN, cohesion
  cohV = np.zeros((boidsN, 3))
  for i in range(boidsN):
    cnt = 0
    for j in range(boidsN):
      if i != j and dist(boidsP[j], boidsP[i]) < recog_range:
        cohV[i] += boidsP[j]
        cnt += 1

    if cnt > 0:
      cohV[i] /= cnt
    else:
      cohV[i] = boidsP[i]

  return (cohV - boidsP) / 100 * cohesion

이 또한 recognize range 내부의 boids의 위치의 평균을 계산하여 그 곳으로 향하는 힘을 만들어준다. 따라서 center of the neighbor boids에 위치한 boid는 Flock Centering의 영향을 적게 받고 외곽에 있는 boid일수록 Flock Centering에 영향을 크게 받는다.

Update Boids

위와 같은 규칙을 통해 얻은 acceleration을 각 time step 마다 업데이트 해주면 된다.

1
2
3
4
5
6
7
8
9

 def update_boids():
  global boidsP, boidsV, boidsN
  
  vel1 = cohesion_rule()
  vel2 = separation_rule()
  vel3 = alignment_rule()

  boidsV += vel1 + vel2 + vel3
  boidsP += boidsV

Additional Fundamental Features

boid의 기본적인 구현을 끝마쳤지만 이대로 구현을 마치게 되면 다양한 문제가 발생한다. 속도가 너무 빨라지거나 우리가 simulation을 위해 구현해놓은 viewport의 경계를 벗어나버린다. 따라서 비정상적인 움직임을 할 수 없도록 여러 제약 조건이 필요하다.

Limit Velocity

위 규칙만을 적용한 채 시뮬레이션을 실행시키면 boids가 서로 상호작용하면서 속도가 끊임없이 증가하는 모습을 확인할 수 있다. 따라서 최대 속도에 제약을 줄 필요가 있다.

1
2
3
4
5
6

def limit_velocity():
  global boidsV, boidsN, max_speed

  for i in range(boidsN):
    if np.linalg.norm(boidsV[i]) > max_speed:
      boidsV[i] = boidsV[i] / np.linalg.norm(boidsV[i]) * max_speed

Limit Boundary

시뮬레이션을 쉽게 확인하기 위해 boundary를 설정해주었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def avoid_bound():
  # decrease the velocity of boids when they are close to the bound smoothly
  global boidsP, boidsV, boidsN
  bound = 5
  amount = 0.5
  for i in range(boidsN):
    if boidsP[i][0] + bound < -boundRange:
      boidsV[i][0] += amount
    if boidsP[i][0] - bound > boundRange:
      boidsV[i][0] -= amount
    if boidsP[i][1] + bound < -boundRange:
      boidsV[i][1] += amount
    if boidsP[i][1] - bound > boundRange:
      boidsV[i][1] -= amount
    if boidsP[i][2] + bound < -boundRange:
      boidsV[i][2] += amount
    if boidsP[i][2] - bound > boundRange:
      boidsV[i][2] -= amount

Additional Non-essential Features

위에서 구현한 규칙 외에도 추가적인 규칙을 추가해주었다.

  1. Goal Seeking - 설정된 목표를 향해 날아가기
  2. Avoid Predetors - 포식자를 피해 날아가기
  3. Avoid Obstacles - 장애물을 피해 날아가기

Goal, Predetors, Obstalces는 시뮬레이션 상단의 Toggle로 껐다가 켤 수 있다.

이 중 Goal Seeking과 Avoid Predetors는 단순히 goal을 향하는 힘, 그리고 predetor으로부터 달아나는 힘을 만들어주기만 하면 되기 때문에 넘어가도록 한다. 여기서 중요한 내용은 Avoid Obstacles였다.

Avoid Obstacles

다양한 형태의 Obstacle이 있을 수 있으나 가장 먼저 머리에 떠오른 것은 구 형태의 Obstacle이었다. 그래서 boid가 구 형태의 Obstacle에 가까이 다가가면 구의 중심에서 반대 방향으로 작용하는 힘을 만들어주었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def avoid_obstacles_rule():
  global boidsP, boidsV, boidsN, obstacleP, obstacleN, obsSize
  if obstacleN == 0:
    return np.zeros((boidsN, 3))
  avoidV = np.zeros((boidsN, 3))
  for i in range(boidsN):
    for j in range(obstacleN):
      distToObs = dist(boidsP[i], obstacleP[j]) - obsSize[j]
      if distToObs < recog_range:
        if distToObs < 0.1:
          avoidV[i] += 100 * normalize(boidsP[i] - obstacleP[j])
        else:
          avoidV[i] += 10 / (distToObs ** 2) * normalize(boidsP[i] - obstacleP[j])
  
  return avoidV

처음에는 그저 obstacle이 recog_range에 들어왔을 때 단순히 반대 방향의 힘을 만들어주었더니 boid가 멀리에서도 Obstacle을 인지하여 아예 Obstacle이 없는 곳에서만 멤도는 현상을 관찰할 수 있었다. 자연스럽게 날아다니다가 눈 앞에 장애물을 피하는 형태의 움직임을 원했기 때문에 이는 원하는 방향의 움직임이 아니었다. 따라서 좀 더 자연스러운 장애물 피하기를 만들기 위해 disToObs 변수를 만들어 Obstacle과 가까우면 가까워질수록 더 큰 힘을 받을 수 있도록 했다. avoidV[i] += ... / (distToObs ** 2) ... 을 통해 장애물의 멀리에 있으면 avoidV의 값이 작고, 장애물과 가까워지면 가까워질수록 더 큰 힘이 만들어질 수 있도록 했다. 이런 구현을 통해 자연스럽게 날아다니다가 장애물에 가까워지면 피하는 형태의 움직임을 완성할 수 있었다.

Avoid Obstacles 정상적으로 날아다니다가 장애물에 가까워지면 피하는 모습을 볼 수 있다.

Result

Boid를 3D 형태로 구현해보면서 Flock Simulation의 기본적인 구현 방식을 이해할 수 있었다. 특히나 적은 양의 규칙들만으로 다량의 boid가 그럴듯한 모습의 형태를 갖춘다는 것이 인상적이었다. 하지만 이렇게 구현한 내용 중에서도 부족한 내용을 확인할 수 있었다.

Complexity

Javascript base의 py-script라서 발생하는 문제인지는 모르겠지만 boid의 개수가 50을 넘어가면 눈에 띄게 시뮬레이션이 느려지는 현상을 확인할 수 있었다. (현재의 시뮬레이션에 기본적으로 설정된 boid의 수는 30마리이다.) 이는 어떻게 보면 당연한 것이 이 시뮬레이션에서 boid의 움직임을 정의하는 알고리즘은 시간복잡도가 $O(N^2)$이다. 따라서 boid가 늘어나면 느려지는 현상을 쉽게 관찰할 수 있다. 이를 해결하기 위한 방법으로는 Spartial Data Structure을 구성하여 neighbor boids search를 가속시키는 방법이 있다. 따라서 다음 게시물에서는 이를 구현해보려고 한다.

Avoid Obstacles

논문에서는 Avoid Obstacles 방법에 있어서 두 가지를 제시했다. 하나는 Force Field concept이고 또 다른 하나는 steer-to-avoid concept이다. 이 글에서 사용한 방법은 Force Field 이다. 이는 obstacle 주변에 일종의 filed of repulsion force가 존재하여 boid가 obstacle에 가까워질수록 밀어내는 힘을 받는 형태를 말한다. 하지만 이는 다양한 부작용을 야기한다. 대표적으로는 force field와 평행한 방향으로 날아들었을 경우, boid는 이를 피한다기 보다는 반대 방향의 힘이 작용하여 멀어지는 형태가 나타난다는 것이다. 최악의 형태는 돌아서지 못해서 충돌하고 마는 것이다. (이는 distToObs의 제곱으로 나누면서 반대 방향의 힘이 굉장히 크게 발생하도록 만들어 놓았다. 테스트 하는 과정에서는 충돌하지 않는 것을 확인하였다.) 또 다른 형태는 “peripheral vision”으로, boid가 벽과 평행하게 날아갈 때는 평행한 방향을 유지한 채 날아야하는데 force field는 반발력이 벽에서 발생하므로 평행하게 날아가는 움직임을 만들 수 없다는 것이다. 마지막으로는 장애물 피하기가 멀리서부터 계획된 형태의 움직임으로 나타나야 하는데 force field의 경우 먼 거리에서는 약하게, 가까운 거리에서는 강하게 나타나므로 회피하는 움직임이 충돌하기 직전이 되어서야 급작스럽게 나타난다는 것이다.

마지막 예시가 가장 크게 와닿았는데 위의 장애물 피하기 영상을 보면 알 수 있듯이 boid의 무리가 장애물이 가까워졌을 때 급작스럽게 흩어지는 모습을 볼 수 있다. 따라서 마지막에 제시된 예시가 가장 크게 드러난다고 볼 수 있다.

steer-to-avoid는 조금 더 현실적인 형태의 obstacles avoidance method이다. 이는 마치 Backward Ray Tracing 처럼 새가 눈 앞의 obstacle을 일종의 ray를 통해서 인지할 수 있도록 하는 것이다. 여러 ray를 통해 눈 앞의 obstacle의 형태를 파악하고 obstacle이 없는 방향으로 진행 방향을 조절하는 것이다. 이는 위에서 언급된 다양한 문제를 해결할 수 있지만 계산하는 과정이 Force Field에 비해 복잡하다는 것이 단점이다.

개선이 필요한 부분

KD-Tree와 같은 Spartial Data Structure을 통해 boid simulation의 속도를 끌어올려 더 많은 양의 boid를 한 번에 시뮬레이션 할 수 있도록 개선할 예정이다. 또한 steer-to-avoid method를 구현하여 더욱 현실적인 boid를 구현해보고자 한다.

참고 자료

  1. Jungdam Won, Crowd Simulation 수업 자료
  2. Reynolds, C. W. (1987) Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH ‘87 Conference Proceedings) pages 25-34.
  3. Ben Eater, Boids algorithm demonstration, https://eater.net/boids
  4. Conrad Parker, Boids Pseudocode, https://vergenet.net/~conrad/boids/pseudocode.html
  5. Wikipedia, Boids, https://en.wikipedia.org/wiki/Boids
graphics
study graphics boid
이 게시물은 저작권자의 CC BY 4.0 라이센스를 따릅니다.