상태 머신은 유한한 수의 상태를 포함하는 추상적인 모델입니다. 모든 명령의 실행 흐름을 나타내고 제어하는 ​​데 사용됩니다. 상태 머신은 게임에서 인공 지능을 구현하는 데 이상적이며, 번거롭고 복잡한 코드를 작성하지 않고도 깔끔한 솔루션을 얻을 수 있습니다. 이 기사에서는 이론을 다루고 간단한 스택 기반 상태 머신을 사용하는 방법도 배웁니다.

우리는 이미 상태 머신을 사용하여 인공 지능을 작성하는 방법에 대한 일련의 기사를 발표했습니다. 아직 이 시리즈를 읽지 않았다면 지금 읽을 수 있습니다.

유한 상태 기계 란 무엇입니까?

유한 상태 기계(또는 간단히 FSM - 유한 상태 기계)는 가상 상태 기계를 기반으로 하는 계산 모델입니다. 한 번에 하나의 상태만 활성화될 수 있습니다. 따라서 어떤 작업을 수행하려면 기계가 상태를 변경해야 합니다.

상태 머신은 일반적으로 무언가의 실행 흐름을 구성하고 표현하는 데 사용됩니다. 이는 게임에서 AI를 구현할 때 특히 유용합니다. 예를 들어 적의 "두뇌"를 쓰려면 각 상태는 일종의 행동(공격, 회피 등)을 나타냅니다.

유한 자동자는 그래프로 나타낼 수 있으며, 정점은 상태이고 가장자리는 이들 사이의 전환입니다. 각 가장자리에는 전환이 발생해야 하는 시기를 나타내는 레이블이 있습니다. 예를 들어 위의 이미지에서 플레이어가 근처에 있는 경우 자동 장치가 상태를 "방황"에서 "공격"으로 변경하는 것을 볼 수 있습니다.

스케줄링 상태 및 해당 전환

유한 상태 기계의 구현은 상태와 이들 사이의 전환을 식별하는 것으로 시작됩니다. 개미집으로 나뭇잎을 옮기는 개미의 행동을 설명하는 상태 기계를 상상해 보십시오.

시작점은 "잎 찾기" 상태로 개미가 잎을 찾을 때까지 활성 상태를 유지합니다. 이 경우 상태가 "집으로 이동"으로 변경됩니다. 개미가 개미집에 도착할 때까지 동일한 상태가 활성 상태로 유지됩니다. 그 후 상태는 "잎 찾기"로 다시 변경됩니다.

"잎 찾기" 상태가 활성화되어 있지만 마우스 커서가 개미 옆에 있으면 상태가 "도망치다"로 변경됩니다. 개미가 마우스 커서에서 충분히 안전한 거리에 있으면 상태가 "잎 찾기"로 다시 변경됩니다.

집으로 향하거나 집 밖으로 나갈 때 개미는 마우스 커서를 두려워하지 않습니다. 왜요? 그리고 해당 전환이 없기 때문입니다.

간단한 상태 머신 구현

상태 머신은 단일 클래스를 사용하여 구현할 수 있습니다. FSM이라고 합시다. 아이디어는 각 상태를 메서드 또는 함수로 구현하는 것입니다. 또한 activeState 속성을 사용하여 활성 상태를 결정합니다.

Public 클래스 FSM ( private var activeState:Function; // 오토마톤의 활성 상태에 대한 포인터 public function FSM() ( ) public function setState(state:Function) :void ( activeState = state; ) public function update() :void ( if ( activeState != null) ( activeState(); ) ) )

모든 상태는 함수입니다. 또한 게임 프레임이 업데이트될 때마다 호출됩니다. 이미 언급했듯이 activeState는 활성 상태 함수에 대한 포인터를 저장합니다.

FSM 클래스의 update() 메서드는 모든 게임 프레임에서 호출되어야 합니다. 그리고 그는 차례로 그 상태의 기능을 부를 것입니다. 이 순간활성.

setState() 메서드는 새 활성 상태를 설정합니다. 게다가, 오토마톤의 어떤 상태를 정의하는 각 함수는 FSM 클래스에 속할 필요가 없습니다. 이것은 우리 클래스를 보다 보편적으로 만듭니다.

상태 머신 사용

개미 AI를 구현해 봅시다. 위에서 우리는 이미 일련의 상태와 이들 사이의 전환을 보여주었습니다. 다시 설명하지만 이번에는 코드에 집중하겠습니다.

우리의 개미는 뇌 영역이 있는 Ant 클래스로 표현됩니다. 이것은 FSM 클래스의 인스턴스일 뿐입니다.

공용 클래스 Ant(공용 var 위치:Vector3D; 공용 var 속도:Vector3D; 공용 var brain:FSM; 공용 기능 Ant(posX:Number, posY:Number)(위치 = new Vector3D(posX, posY); 속도 = new Vector3D( -1, -1); brain = new FSM(); // 잎사귀를 찾아 시작합니다. brain.setState(findLeaf); ) /** * 상태 "findLeaf" * 개미가 잎사귀를 찾도록 합니다. */ public function findLeaf( ) :void ( ) /** * "goHome" 상태 * 개미가 개미집으로 들어가게 함 */ public function goHome() :void ( ) /** * "runAway" 상태 * 마우스 커서에서 도망치는 개미 * / public function runAway() :void ( ) public function update():void ( // 상태 머신을 업데이트합니다. 이 함수는 // 활성 상태 함수를 호출합니다: findLeaf(), goHome () 또는 runAway().brain.update( ); // 개미의 움직임에 속도를 적용합니다. moveBasedOnVelocity(); ) (...) )

Ant 클래스에는 속도 및 위치 속성도 포함되어 있습니다. 이러한 변수는 오일러 방법을 사용하여 모션을 계산하는 데 사용됩니다. update() 함수는 게임 프레임이 업데이트될 때마다 호출됩니다.

아래는 잎사귀 찾기를 담당하는 상태인 findLeaf()로 시작하는 각 메서드의 구현입니다.

Public function findLeaf() :void ( // 개미를 나뭇잎으로 이동합니다. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance (게임 .instance.leaf, 이것)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

goHome() 상태는 개미가 집으로 돌아가도록 하는 데 사용됩니다.

Public function goHome() :void( // 개미를 홈으로 이동합니다. velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance( 게임.인스턴스.홈, 이것)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

마지막으로 runAway() 상태 - 마우스 커서를 피할 때 사용됩니다.

Public function runAway() :void ( // 커서에서 멀리 떨어진 개미를 이동합니다. velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // 커서가 여전히 주위에 있습니까? ? if ( distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // 아니요, 이미 멀었어요. 이제 나뭇잎을 찾을 시간입니다. brain.setState(findLeaf); ) )

FSM 개선: 스택 기반 자동화

집으로 가는 길에 개미도 마우스 커서에서 도망쳐야 한다고 상상해 보십시오. FSM 상태는 다음과 같습니다.

사소한 변화처럼 보입니다. 아니요, 그러한 변화는 우리에게 문제를 만듭니다. 현재 상태가 "도망"이라고 상상해보십시오. 마우스 커서가 개미에게서 멀어지면 어떻게 해야 할까요? 집에 갈까요, 아니면 잎사귀를 찾을까요?

이 문제에 대한 해결책은 스택 기반 상태 머신입니다. 위에서 구현한 간단한 FSM과 달리 이러한 종류의 FSM은 스택을 사용하여 상태를 관리합니다. 스택의 맨 위에는 활성 상태가 있으며 스택에서 상태가 추가/제거될 때 전환이 발생합니다.

다음은 스택을 기반으로 하는 상태 머신의 작동에 대한 시각적 데모입니다.

스택 기반 FSM 구현

이러한 유한 상태 기계는 간단한 것과 같은 방식으로 구현될 수 있습니다. 차이점은 필요한 상태에 대한 포인터 배열을 사용한다는 것입니다. 더 이상 activeState 속성이 필요하지 않습니다. 스택의 맨 위는 이미 활성 상태를 가리킵니다.

공개 클래스 StackFSM( 비공개 var 스택:배열, 공개 함수 StackFSM()( this.stack = new Array(); ) 공개 함수 update() :void( var currentStateFunction:Function = getCurrentState(), if (currentStateFunction != null) ( currentStateFunction(); ) ) public function popState() :Function ( return stack.pop(); ) public function pushState(state:Function) :void ( if (getCurrentState() != state) ( stack.push(state) ; ) ) 공개 함수 getCurrentState() :Function ( return stack.length > 0 ? 스택 : null; ) )

setState() 메서드는 pushState()(스택 맨 위에 새 상태 추가) 및 popState()(스택 맨 위에서 상태 제거)로 대체되었습니다.

스택 기반 FSM 사용

스택 기반 상태 머신을 사용할 때 각 상태는 필요하지 않을 때 스택에서 자신을 제거해야 합니다. 예를 들어, 공격() 상태는 적이 이미 파괴된 경우 스택에서 자체적으로 제거되어야 합니다.

Public class Ant ( (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // 리프 브레인을 찾는 것으로 시작합니다. pushState( findLeaf); (...) ) /** * 상태 "findLeaf". * 개미가 나뭇잎을 찾도록 합니다. */ public function findLeaf() :void ( // 개미를 나뭇잎으로 이동합니다. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // 아니요, 이미 멀리 있습니다. 나뭇잎 검색으로 돌아갈 시간입니다. brain.popState(); ) ) (...) )

결론

상태 머신은 게임에서 인공 지능 로직을 구현하는 데 확실히 유용합니다. 개발자가 가능한 모든 옵션을 볼 수 있도록 그래프로 쉽게 나타낼 수 있습니다.

상태 기능으로 상태 머신을 구현하는 것은 간단하지만 강력한 기술입니다. 훨씬 더 복잡한 상태 얽힘은 FSM을 사용하여 구현할 수 있습니다.

유한 자동 장치의 복잡성에 대한 기준 중 하나는 상태의 수입니다. 이 숫자가 작을수록 이 자동 장치를 구현하는 개별 장치가 더 단순해집니다. 따라서 유한 오토마타 이론에서 중요한 문제 중 하나는 상태 수가 가장 적은 오토마타를 구성하는 것입니다.

현대 컴퓨터에서 모든 정보는 이진 코드의 형태로 표시되므로 자동 장치를 구축하기 위해 두 가지 다른 안정 상태를 가진 요소를 사용할 수 있습니다. 그 중 하나는 숫자 0에 해당하고 다른 하나는 숫자 1에 해당합니다.

다음은 유한 오토마타의 몇 가지 예입니다.

예 1. 지연 요소(메모리 요소).

지연 요소는 하나의 입력과 하나의 출력이 있는 장치입니다. 또한, 당시의 출력 신호의 값은 티 이전 순간의 신호 값과 일치합니다. 도식적으로 지연 요소는 다음과 같이 나타낼 수 있습니다(그림 2).

입력과 출력 알파벳이 다음과 같다고 가정합니다. 엑스 ={0, 1}, 와이 =(0, 1). 그 다음에 큐 =(0, 1). 당시의 딜레이 요소 상태에서 티 현재 메모리 요소의 내용이 이해됩니다. 이런 식으로 큐 (티 )= 엑스 (티 1), 와이 (티 )= 큐 (티 )=엑스 (티 1).

테이블로 지연 요소를 설정해 보겠습니다. 여기서 ㅏ 1 =0, ㅏ 2 =1, 큐 1 =0, 큐 2 =1,

(ㅏ 1 , 큐 1)= (0, 0)=0,  (ㅏ 1 , 큐 1)= (0, 0)=0;

(ㅏ 1 , 큐 2)= (0, 1)=0,  (ㅏ 1 , 큐 2)= (0, 1)=1;

(ㅏ 2 , 큐 1)= (1, 0)=1,  (ㅏ 2 , 큐 1)= (1, 0)=0;

(ㅏ 2 , 큐 2)= (1, 1)=1,  (ㅏ 2 , 큐 2)= (1, 1)=1;

큐 ㅏ
	=0,  =0	=0,  =1
	=1,  =0	=1,  =1

무어 다이어그램은 그림 1에 나와 있습니다. 삼

부울 함수 시스템으로 이 자동 장치를 나타내기 위해 자동 장치 테이블과 위의 알고리즘을 사용합니다. 이 경우 입력 및 출력 알파벳과 상태가 이미 인코딩되어 있으므로 인코딩이 필요하지 않습니다.

이라는 사실에 주목하자. m=p=p =2. 그 다음에 케이 =아르 자형 =에스 =1이므로 지연 요소는 두 가지 함수로 제공됩니다.  그리고  . 이 함수의 진리표는 2를 포함합니다. 케이 + 아르 자형 =2 2 =4 행 및 케이 +아르 자형 +아르 자형 +에스 =4 열:

엑스	지

예 2. 이진 순차 가산기.

이 직렬 가산기는 이진법에서 두 개의 숫자를 더하는 장치입니다. 숫자는 가산기의 입력에 공급됩니다. 엑스 1 및 엑스 2, 최하위 숫자부터 시작합니다. 출력에서 숫자 입력에 해당하는 시퀀스가 ​​형성됩니다. 엑스 1 +엑스 2 이진 계산 시스템에서 (그림 4).

입력 및 출력 알파벳은 다음과 같이 고유하게 정의됩니다. 엑스 ={00; 01; 10; 11}, 와이 =(0,1). 상태 집합은 숫자의 해당 비트를 추가할 때 전송 값에 의해 결정됩니다. 엑스 1 및 엑스 2. 일부 숫자를 추가하는 동안 캐리가 형성되면 가산기가 상태로 전달되었다고 가정합니다. 큐 하나 . 캐리가 없으면 가산기가 상태에 있다고 가정합니다. 큐 0 .

가산기는 테이블로 제공됩니다.

큐 ㅏ	큐 0	큐 1
	큐 0 , 0	큐 0 , 1
	큐 0 , 1	큐 1 , 0
	큐 0 , 1	큐 1 , 0
	큐 1 , 0	큐 1 , 1

순차 가산기의 무어 다이어그램은 그림 1에 나와 있습니다. 5.

입력 및 출력 문자는 이미 인코딩되어 있습니다. 상태를 다음과 같이 인코딩합니다.  (큐 0)=0,  (큐 1)=1. 따라서 순차 가산기는 두 개의 부울 함수로 제공되며 그 진리표는 다음과 같습니다.

엑스 1	엑스 2	지

예 3. 평등 비교 체계.

동등 비교 회로는 두 숫자를 비교하는 장치입니다. 엑스 1 및 엑스 2, 2진법으로 주어진다. 이 장치는 다음과 같이 작동합니다. 장치의 입력에서 가장 높은 것부터 순차적으로 숫자의 자릿수가 공급됩니다. 엑스 1 및 엑스 2. 이 순위가 비교됩니다. 비트가 일치하면 출력 신호 0이 회로의 출력에서 ​​생성되고 그렇지 않으면 신호 1이 출력에 나타납니다. 엑스 1 및 엑스 2 다른. 출력 시퀀스가 ​​0이고 길이가 비교된 숫자의 자릿수와 일치하면 엑스 1 및 엑스 2 .

이 기계의 경우 엑스 ={00, 01, 10, 11}; 와이 ={0,1}.

회로의 기능은 두 가지 상태에 의해 결정됩니다. 상태 큐 0 현재 비교된 비트의 동등성에 해당합니다. 이 경우 기계는 동일한 상태를 유지합니다. 다음 순간에 비교되는 숫자가 다르면 자동 장치는 새로운 상태로 이동합니다. 큐 숫자가 다르다는 것을 의미하기 때문에 1과 그 안에 남아 있습니다. 따라서 비교 체계는 다음 표로 지정할 수 있습니다.

큐 엑스	큐 0	큐 1
	큐 0 , 0	큐 1 , 1
	큐 1 , 1	큐 1 , 1
	큐 1 , 1	큐 1 , 1
	큐 0 , 0	큐 1 , 1

평등에 대한 비교 체계의 무어 다이어그램이 그림 1에 나와 있습니다. 6.

다음과 같이 상태를 인코딩합니다.  (큐 0)=0,  (큐 1)=1. 자동 장치에는 두 가지 기능이 제공됩니다.

엑스 1	엑스 2	지

예 4. 불평등 비교 체계.

부등식 비교 회로는 비교 여부를 알 수 있는 장치입니다. 엑스 1 및 엑스 2 , 그리고 그것들이 같지 않다면 어느 것이 다른 것보다 큰지 알아내십시오. 이 장치에는 2개의 입력과 2개의 출력이 있습니다. 출력 신호 와이 1 (티 ) 그리고 와이 2 (티 )는 다음 규칙에 따라 결정됩니다.

와이 1 (티 )=와이 2 (티 )=0인 경우 엑스 1 (티 )=엑스 2 (티 );

와이 1 (티 )=1, 와이 2 (티 )=0인 경우 엑스 1 (티 )>엑스 2 (티 ), 그건 엑스 1 (티 )=1, 엑스 2 (티 )=0;

와이 1 (티 )=0, 와이 2 (티 )=1인 경우 엑스 1 (티 )<엑스 2 (티 ), 그건 엑스 1 (티 )=0, 엑스 2 (티 )=1.

따라서 숫자의 부등식에 대한 비교 회로의 입력에 적용하면 엑스 1 =엑스 1(l)… 엑스 1 (티 ) 그리고 엑스 2 =엑스 2(l)… 엑스 2 (티 ) 이 숫자의 자릿수는 가장 높은 자릿수부터 순차적으로 비교됩니다. 출력 신호는 위의 규칙에 따라 공식화됩니다. 또한 출력 시퀀스가 ​​0 쌍으로 구성된 경우 엑스 1 =엑스 2. 첫 번째 값이 0과 다른 경우 쌍은 다음 형식을 갖습니다. , () 그 다음에 엑스 1 >엑스 2 (엑스 1 <엑스 2).

회로 설명에서 다음과 같습니다.

엑스 ={00, 01, 10, 11}, 와이 ={00, 01, 10}.

스키마 상태는 다음과 같이 정의됩니다. 우리는 초기 시간에 티 =1 기계가 상태에 있음 큐 1 . 숫자를 비교한 경우 엑스 1 그리고 엑스 2가 일치하면 기계가 이 상태를 유지합니다. 신호 00이 출력에 나타날 것이라는 점에 유의하십시오. 엑스 1 숫자의 해당 자릿수보다 작습니다(보다 큼). 엑스 2, 그러면 기계가 상태로 이동합니다. 큐 2 (큐 삼). 이 경우 신호 01(10)이 출력에 나타납니다. 앞으로 남은 자릿수를 제출할 때 엑스 1 그리고 엑스 2 자동 장치의 입력에 대해 자동 장치는 상태를 유지합니다. 큐 2 (큐 3) 출력 기호 10(01)을 생성합니다. 위로부터 불평등에 대한 비교 체계는 다음 표로 지정할 수 있습니다.

큐 엑스	큐 1	큐 2	큐 3
	큐 1 , 00	큐 2 , 01	큐 3 , 10
	큐 2 , 01	큐 2 , 01	큐 3 , 10
	큐 3 , 10	큐 2 , 01	큐 3 , 10
	큐 1 , 00	큐 2 , 01	큐 3 , 10

해당 무어 다이어그램은 그림 1에 나와 있습니다. 7.

입력 및 출력 알파벳은 이미 여기에 인코딩되어 있습니다. 상태 큐 1 , 큐 2 및 큐 3 인코딩:  1 (큐 1)=00,  (큐 2)=01,  (큐 3)=10.

따라서 이 회로는 4개의 변수에 의존하는 4개의 부울 함수로 구성된 시스템으로 정의할 수 있습니다. 이 함수는 부분적으로 정의되고 진리표에 의해 제공됩니다.

	엑스 1	엑스 2	지 1	지 2

표에서 기호 *는 변수 집합을 표시합니다. 엑스 1 , 엑스 2 , 지 1 , 지 2 , 기능  1 ,  2 ,  1 ,  2는 정의되지 않습니다. 넣어보자 함수 값  1 ,  2 ,  1 ,  이 세트의 2는 1과 같습니다.

이 기사에서는 스위치 구성, 런타임 테이블 및 Boost Statechart 라이브러리를 사용하여 C++에서 간단한 상태 머신과 구현에 대해 설명합니다.

소개

대략적으로 말하면, 유한 상태 기계(Finite State Machine)는 사용자의 눈에 무언가를 전송하고 거기에서 무언가를 받을 수 있는 블랙박스입니다. 이것은 복잡한 알고리즘을 숨길 수 있는 매우 편리한 추상화이며 상태 머신은 매우 효율적입니다.

유한 오토마타는 상태와 전이로 구성된 다이어그램으로 묘사됩니다. 간단한 예를 들어 설명하겠습니다.

짐작하셨겠지만 이것은 전구 상태 다이어그램입니다. 초기 상태는 검은색 원으로 표시되고 전환은 화살표이며 일부 화살표는 서명됩니다. 이는 기계가 다른 상태로 전환된 후의 이벤트입니다. 따라서 초기 상태에서 즉시 상태에 들어갑니다. 불을 끄다- 램프가 켜지지 않습니다. 버튼을 누르면 기계가 상태를 변경하고 표시된 화살표를 따릅니다. 누름 단추, 주에 불을 켜다- 램프가 켜져 있습니다. 버튼을 누른 후 화살표로 이 상태에서 다시 상태로 이동할 수 있습니다. 불을 끄다.

점프 테이블도 널리 사용됩니다.

기계의 실용화

상태 머신은 프로그래밍에 널리 사용됩니다. 예를 들어, 자동 장치의 형태로 장치의 작동을 상상하는 것은 매우 편리합니다. 이렇게 하면 코드를 더 간단하고 쉽게 실험하고 유지 관리할 수 있습니다.

또한 유한 오토마타는 텍스트의 모든 종류의 파서 및 분석기를 작성하는 데 사용되며, 이들의 도움으로 하위 문자열을 효과적으로 검색할 수 있으며 정규 표현식도 유한 오토마톤으로 변환됩니다.

예를 들어, 텍스트에서 숫자와 단어를 세기 위한 오토마톤을 구현할 것입니다. 우선, 숫자가 공백 문자(공백, 탭, 줄 바꿈)로 둘러싸인 임의 길이의 0에서 9까지의 숫자 시퀀스로 간주된다는 데 동의합니다. 단어는 문자로 구성되고 공백 문자로 둘러싸인 임의 길이의 시퀀스로 간주됩니다.

다이어그램을 고려하십시오.

초기 상태에서 우리는 상태에 도달합니다. 시작. 현재 문자를 확인하고 문자이면 상태로 이동합니다. 단어로 표시된 화살표를 따라 편지. 이 상태는 우리가 단어를 고려하는 순간에 추가 기호의 분석이 이 가정을 확인하거나 반박할 것이라고 가정합니다. 따라서 다음 문자를 고려하십시오. 문자인 경우 상태는 변경되지 않습니다(다음으로 표시된 원형 화살표 참고). 편지). 문자가 문자가 아니지만 공백 문자에 해당하는 경우 이는 가정이 정확하고 단어를 찾았음을 의미합니다(화살표를 따라 이동 우주상태로 시작). 기호가 문자도 공백도 아닌 경우 가정에 실수가 있고 고려 중인 시퀀스가 ​​단어가 아닙니다(화살표를 따릅니다. 알려지지 않은상태로 건너뛰다).

할 수 있는 건너뛰다우리는 공백 문자를 만날 때까지 머문다. 간격을 찾은 후 화살표를 따라갑니다. 우주상태로 시작. 이것은 우리의 검색 패턴과 일치하지 않는 줄을 완전히 건너뛰기 위해 필요합니다.

상태로 전환한 후 시작, 검색 주기가 처음부터 반복됩니다. 숫자 인식 분기는 단어 인식 분기와 유사합니다.

스위치 명령을 사용한 자동화

첫 번째는 가능한 상태입니다.

그런 다음 문자열을 반복하여 현재 문자를 자동 장치로 밀어 넣습니다. 자동 장치 자체는 현재 상태 섹션으로의 전환을 먼저 수행하는 switch 문입니다. 섹션 내부에는 이벤트(들어오는 문자)에 따라 현재 상태를 변경하는 if-else 구문이 있습니다.

const size_t 길이 = text.length() ; for (size_t i = 0 ; i != 길이; ++ i) ( const char current = text[ i] ; switch (state) ( case State_Start: if (std:: isdigit (current) ) ) ( state = State_Number; ) else if (std:: isalpha (current) ) ( state = State_Word; ) break ; case State_Number: if (std:: isspace (current) ) (

여기서 우리는 다이어그램을 봅니다 - 현재 상태 숫자, 이벤트 우주(공백 문자가 발견됨), 이는 숫자가 발견되었음을 의미합니다.

발견 번호() ; 상태 = State_Start; ) else if (! std:: isdigit (current) ) ( state = State_Skip; ) break ; 케이스 State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (current) ) ( state = State_Skip; ) break ; 케이스 State_Skip: if (std::isspace (current) ) ( state = State_Start; ) break ; ) )

결과:

고효율

간단한 알고리즘에 대한 구현 용이성

- 유지하기 어렵다

런타임 해석

이 접근 방식의 아이디어는 간단합니다. 전환 테이블을 만들고 채우고 이벤트가 발생하면 테이블에서 다음 상태를 찾아 전환해야 합니다.

열거형 이벤트( Event_Space, Event_Digit, Event_Letter, Event_Unknown ) ; 무효 ProcessEvent(이벤트 이벤트) ; ... 구조체 전환(상태 BaseState_, 이벤트 이벤트_, 상태 TargetState_;) ; 무효 AddTransition(State fromState, 이벤트 이벤트, State toState) ; ... typedef 표준::벡터< transition>전환 테이블; 트랜지션 테이블 트랜지션_; 상태 CurrentState_;

표 채우기:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip) ; AddTransition(State_Number, Event_Unknown, State_Skip) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

그것은 꽤 명확하게 밝혀졌습니다. 명확성에 대한 지불은 기계의 더 느린 작동이 될 것이며, 이는 종종 중요하지 않습니다.

특정 이벤트가 발생하면 자동 장치가 일부 코드에 알릴 수 있도록 전환에 대한 정보를 구조에 추가할 수 있습니다( 이행) 함수 포인터( 동작) 다음과 같이 호출됩니다.

typedef void (DynamicMachine:: * 액션) () ; struct Transition(상태 BaseState_, 이벤트 Event_, 상태 TargetState_, 작업 Action_, ) ; ... void AddTransition(State fromState, 이벤트 이벤트, State toState, 액션 액션) ; ... AddTransition (State_Number, Event_Space, State_Start 및 DynamicMachine:: FoundNumber ) ;

결과:

유연성 및 가시성

유지보수 용이

- 스위치 블록에 비해 성능이 떨어짐

실행 시간 해석. 속도 최적화

가시성과 속도를 결합할 수 있습니까? 오토마톤이 스위치 블록을 기반으로 하는 오토마타만큼 효율적일 가능성은 없지만 격차를 좁힐 수는 있습니다. 이렇게하려면 전환에 대한 정보를 얻기 위해 검색을 수행하지 않고 상태 및 이벤트 번호로 선택하도록 테이블에서 행렬을 작성해야합니다.

결과는 메모리 소비를 희생하여 달성됩니다.

결과:

유연성, 가시성

효과적인

- 메모리 소비(아마도 중요하지 않음)

부스트 상태 차트

상태 머신을 직접 구현하는 몇 가지 방법에 대해 논의했습니다. 변경을 위해 Boost에서 오토마타를 빌드하기 위한 라이브러리를 고려할 것을 제안합니다. 이 라이브러리는 매우 강력하며 제안된 기능을 사용하면 매우 복잡한 유한 상태 기계를 구축할 수 있습니다. 다소 간략하게 살펴보도록 하겠습니다.

먼저 이벤트를 정의해 보겠습니다.

네임스페이스 이벤트( struct Digit : boost::statechart::event< Digit>( ) ; 구조체 문자: boost::statechart::event< Letter>( ) ; 구조체 공간: boost::statechart::event< Space>( ) ; structUnknown : 부스트:: 상태 차트:: 이벤트< Unknown> { } ; }

기계 자체(템플릿의 두 번째 매개변수는 초기 상태임):

struct Machine : boost::statechart::state_machine< Machine, States:: Start > { } ;

그리고 국가 자체. 상태 내부에서 전환을 설명하는 유형을 정의해야 합니다( 반응), 여러 전환이 있는 경우 boost::mpl::list 유형 목록에 나열합니다. 두 번째 템플릿 매개변수 단순 상태– 차를 설명하는 유형. 전환은 전환 템플릿 매개변수 쌍으로 설명됩니다. 이벤트 - 다음 상태:

네임스페이스 상태( 구조체 시작: boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> 반응; ) ; 구조체 번호: boost::statechart::simple_state< Number, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, 부스트::상태 차트::전환< Events:: Letter , States:: Skip >, 부스트::상태 차트::전환< Events:: Unknown , States:: Skip >> 반응; ) ; struct Word: boost::statechart::simple_state< Word, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, 부스트::상태 차트::전환< Events:: Digit , States:: Skip >, 부스트::상태 차트::전환< Events:: Unknown , States:: Skip >> 반응; ) ; 구조체 건너뛰기: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >반응; ) ; )

기계가 구축되고 초기화만 하면 되며 다음을 사용할 수 있습니다.

기계 기계; machine.initiate(); ...기계 .process_event(이벤트::공간() ) ;

결과:

유연성, 확장성

- 효율성

성능

구축한 오토마타의 속도를 확인하는 테스트 프로그램을 작성했습니다. 기계를 통해 ~ 17MB 크기의 텍스트를 구동했습니다. 실행 결과는 다음과 같습니다.

단순 로드 텍스트 텍스트 길이: 17605548 바이트 0.19 s 실행 중인 BoostMachine Words: 998002, 숫자: 6816 0.73 s 실행 중인 DynamicMachine Words: 998002, 숫자: 6816 0.56 s Running FastDynamicMachine Words02: 69 numbers 에스

검토되지 않은 상태로 남아 있는 것

유한 오토마타의 몇 가지 더 많은 구현이 아직 밝혀지지 않았습니다(저는 http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml 및 http://www.rsdn.ru/article/alg/FiniteStateMachine.xml을 권장합니다). 설명에서 자동 빌드, Boost 버전 1.44.0의 메타 상태 머신 라이브러리 및 상태 머신에 대한 공식 설명. 호기심 많은 독자는 위의 모든 내용을 숙지할 수 있습니다.

Automata 이론은 이산 정보 변환기의 모델을 연구하는 이산 수학의 한 분야입니다. 이러한 변환기는 실제 장치(컴퓨터, 생물체)와 가상 장치(공리 이론, 수학 기계)입니다. 본질적으로 유한 상태 기계는 장치로 설명될 수 있습니다. 중 , 입력 및 출력 채널이 있는 반면 클록 모멘트라고 하는 개별 시간 모멘트 각각에서 최종 상태 중 하나에 있습니다.

언제든지 입력 채널에서 티 =1, 2, ... 장치로 중 입력 신호가 도착합니다(일부 유한한 신호 세트에서). 다음 순간으로의 상태 변화 법칙은 현재 순간의 입력 신호와 장치의 상태에 따라 설정됩니다. 출력 신호는 현재 시간의 상태와 입력 신호에 따라 다릅니다(그림 1).

상태 머신은 실제 개별 정보 처리 장치의 수학적 모델입니다.

상태 머신 시스템이라고 불리는 답= (엑스 , 큐 , 와이 ,  ,  ), 어디 엑스 , 큐 , 와이 비어 있지 않은 임의의 유한 집합이며,  그리고  - 기능:

많은 엑스 ={ㅏ 1 , ..., ㅏ 중 )라고 한다 알파벳 입력 , 그리고 그 요소는 입력 신호 , 그들의 시퀀스는 선전 구호 ;

많은 큐 ={큐 1 , ..., 큐 N )라고 한다 많은 주 자동 장치 및 그 요소 - 상태 ;

많은 와이 ={비 1 , ..., 비 피 )라고 한다 알파벳 출력 , 그 요소는 출력 신호 , 그들의 시퀀스는 종료 단어 ;

기능  : 엑스  큐 큐 ~라고 불리는 전환 기능 ;

기능  :엑스  큐 와이 ~라고 불리는 출력 기능 .

이런 식으로,  (엑스 , 큐 )큐 ,  (엑스 , 큐 )와이 을 위해 엑스 엑스 , 큐 큐 .

가상 장치는 다음과 같이 작동하는 상태 머신과 연결됩니다. 그것은 세트에서 상태에있을 수 있습니다 큐 , 세트에서 신호 수신 엑스 세트에서 신호를 발행합니다. 와이 .

2. 유한 자동자 정의 방법

추상 오토마타를 정의하는 몇 가지 동등한 방법이 있으며 그 중 세 가지는 다음과 같습니다. 표의 , 기하학적 그리고 기능의 .

2.1 기계의 테이블 할당

그것은 항상 다음을 포함하는 두 개의 입력이 있는 테이블에 의해 정의될 수 있다는 오토마톤의 정의에 따릅니다. 티 선과 피 기둥, 기둥의 교차점에서 큐 그리고 선 ㅏ 기능 값은 가치가 있습니다  (ㅏ 나 , 큐 제이 ),  (ㅏ 나 , 큐 제이 ).

큐 ㅏ	큐 1		큐 제이		큐 N
ㅏ 1	(ㅏ 1 , 큐 1),  (ㅏ 1 , 큐 1)		(ㅏ 1 , 큐 제이 ),  (ㅏ 1 , 큐 제이 )		(ㅏ 1 , 큐 N ),  (ㅏ 1 , 큐 N )
ㅏ 나	(ㅏ 나 , 큐 1),  (ㅏ 나 , 큐 1)		(ㅏ 나 , 큐 제이 ),  (ㅏ 나 , 큐 제이 )		(ㅏ 나 , 큐 N ),  (ㅏ 나 , 큐 N )
ㅏ 중	(ㅏ 중 , 큐 1),  (ㅏ 중 , 큐 1)		(ㅏ 중 , 큐 제이 ),  (ㅏ 중 , 큐 제이 )		(ㅏ 중 , 큐 N ),  (ㅏ 중 , 큐 N )

2.2. 무어 다이어그램으로 오토마톤 정의하기

유한 상태 기계를 지정하는 또 다른 방법은 그래픽, 즉 그래프를 사용하는 것입니다. 자동 장치는 레이블이 지정된 방향 그래프로 표시됩니다. G(큐 , 디 ) 많은 정점 큐 그리고 많은 호 디 ={(큐 제이 ,  (ㅏ 나 , 큐 제이 ))| 큐 제이 큐 , ㅏ 나 엑스 ), 호( 큐 제이 ,  (ㅏ 나 , 큐 제이 )) 쌍( ㅏ 나 ,  (ㅏ 나 , 큐 제이 )). 따라서이 방법을 사용하면 자동 장치의 상태가 상태 기호가 입력되는 원으로 표시됩니다. 큐 제이 (제이 = 1, …, N ). 각 원에서 수행됩니다. 티 화살표(방향 모서리)는 입력 알파벳의 문자에 일대일로 대응 엑스 ={ㅏ 1 , ..., ㅏ 중 ). 문자에 해당하는 화살표 ㅏ 나 엑스 그리고 원을 떠나 큐 제이 큐 , 한 쌍 ( ㅏ 나 ,  (ㅏ 나 , 큐 제이 )), 이 화살표는 에 해당하는 원으로 연결됩니다.  (ㅏ 나 , 큐 제이 ).

결과 도면은 오토마톤 그래프 또는, 무어 다이어그램 . 그다지 복잡하지 않은 오토마타의 경우 이 방법이 표의.

오늘 우리는 기관총에 대해 이야기 할 것이지만 결코 군인들이 손에 들고있는 것은 아닙니다. 러시아군. 우리는 자동 프로그래밍과 같은 흥미로운 프로그래밍 마이크로 컨트롤러 스타일에 대해 이야기 할 것입니다. 더 정확하게는 이것은 프로그래밍 스타일이 아니라 전체 개념이기 때문에 마이크로 컨트롤러 프로그래머가 자신의 삶을 훨씬 쉽게 만들 수 있습니다. 프로그래머에게 제시되는 많은 작업으로 인해 훨씬 ​​쉽고 간단하게 해결되어 프로그래머의 두통을 덜어줍니다. 그건 그렇고, 자동 프로그래밍은 종종 스위치 기술.

이 글을 쓰게 된 동기는 SWITCH 기술에 대한 일련의 기사 블라디미르 타타르체프스키. 일련의 기사는 "응용 개발에 SWITCH 기술의 응용"이라고합니다. 소프트웨어 for microcontrollers "따라서 이 기사에서는 대부분의 경우 작동하는 코드의 예와 설명을 제공하려고 노력할 것입니다.

그건 그렇고, 나는 프로그래밍에 관한 일련의 기사를 계획했으며 ABP 마이크로 컨트롤러의 프로그래밍 기술을 자세히 고려할 것입니다. 놓치지 마세요…. 자 가자!

프로그램은 프로그래머가 지정한 명령을 순차적으로 실행합니다. 일반용 컴퓨터 프로그램프로그램이 완료되고 실행이 중지되고 작업 결과가 모니터에 표시되는 것은 지극히 정상입니다.

마이크로컨트롤러 프로그램은 단순히 실행을 종료할 수 없습니다. 플레이어나 녹음기를 켰다고 상상해 보십시오. 전원 버튼을 누르고 원하는 노래를 선택하고 음악을 즐깁니다. 그러나 음악이 고막을 울리는 것을 멈추면 플레이어가 멈추고 버튼을 눌러도 반응하지 않으며 탬버린으로 춤을 춰도 더욱 그렇습니다.

그리고 이것은 무엇입니까? 모든 것이 정상입니다. 플레이어의 깊숙한 곳에 있는 컨트롤러가 프로그램 실행을 막 마쳤습니다. 여기서 얼마나 불편한지 알 수 있습니다.

따라서 여기에서 우리는 마이크로 컨트롤러용 프로그램이 단순히 중지되어서는 안 된다는 결론을 내립니다. 본질적으로 무한 루프여야 합니다. 이 경우에만 플레이어가 올바르게 작동합니다. 다음으로 어떤 디자인인지 보여드리겠습니다. 프로그램 코드마이크로컨트롤러의 경우 디자인이 아니라 일부 프로그래밍 스타일입니다.

프로그래밍 스타일.

"프로그래밍 스타일"은 이해할 수 없는 것처럼 들리지만 글쎄요. 내가 이것으로 무엇을 말하고 싶습니까?어떤 사람이 전에 프로그래밍을 한 번도 해본 적이 없다고, 즉 일반적으로 완전한 더미라고 상상해 봅시다.

이 사람은 프로그래밍에 관한 많은 책을 읽었고 언어의 모든 기본 구성을 배웠습니다.그는 정보에 대한 액세스가 무제한이기 때문에 조금씩 정보를 수집했습니다. 이 모든 것이 좋지만 그의 첫 번째 프로그램은 어떤 모습일까요? 그는 철학하지 않을 것이지만 단순한 것에서 복잡한 것으로의 길을 따를 것입니다.

따라서 이러한 스타일은 단순한 수준에서 더 복잡한 수준으로 이어지는 단계이지만 동시에 더 효과적입니다.

처음에는 아무 생각 없이 디자인 특징프로그램들. 방금 프로그램의 논리를 구성했습니다. 순서도를 그리고 코드를 작성했습니다. 끊임없이 갈퀴를 가로 질러 온 것에서. 그러나 이것은 내가 증기 목욕을하지 않고 "단순한 루핑"스타일을 사용한 첫 번째 때였습니다. 그 다음 인터럽트를 사용하기 시작했습니다. 그 다음에는 자동 장치가 있었고 우리는 떠났습니다 ...

1. 간단한 루핑. 이 경우 프로그램은 복잡하지 않고 루프되며 장단점이 있습니다. 또한 접근 방식의 단순성에서만 교활한 디자인을 발명 할 필요가 없으며 생각하는대로 씁니다 (점진적으로 자신의 무덤을 파고 있음).

Void main(void) ( initial_AL(); //주변초기화 while(1) ( Leds_BLINK(); //LED 플래셔의 기능 signal_on(); //신호를 켜는 기능 signal_off(); // 신호를 끄는 기능 l=button(); //버튼을 누르는 변수 switch(l) //변수의 값에 따라 하나 또는 다른 작업이 수행됩니다( case 1: ( Deistvie1(); / /함수 대신에 조건 연산자 deistvie2(); //또는 더 많은 분기가 case를 전환합니다. Deistvie3(); deistvie4(); deistvie5(); ); 사례 2: ( Deistvie6(), Deistvie7(), Deistvie8(), Deistvie9(), Deistvie10(), ), . . . . . . . . ) ) )

프로그램의 작업점이 순서대로 이동합니다. 이 경우 모든 동작, 조건 및 사이클이 순차적으로 실행됩니다. 코드가 느려지기 시작하고 많은 추가 조건을 삽입해야 하므로 인식이 복잡해집니다.

이 모든 것이 프로그램을 크게 혼란스럽게 하여 코드에서 복잡한 조건을 만듭니다. 결과적으로 이 코드는 추가하거나 제거할 수 없으며 단일 조각처럼 됩니다. 물론 볼륨이 크지 않은 경우 코드를 수정할 수 있지만, 더 어렵습니다.

이 접근 방식을 사용하여 여러 프로그램을 작성했는데 크기가 크지 않고 제대로 작동했지만 가시성은 많이 부족했습니다. 새로운 조건을 추가하려면 모든 것이 묶여 있었기 때문에 전체 코드를 삽질해야 했습니다. 이로 인해 많은 오류와 골칫거리가 발생했습니다. 컴파일러는 가능한 한 빨리 그러한 프로그램을 디버깅하는 것이 지옥이 될 것이라고 맹세했습니다.

2. 사이클 + 인터럽트.

인터럽트를 사용하여 무한 제동 사이클을 부분적으로 해결할 수 있습니다. 인터럽트는 악순환을 끊고 중요한 이벤트를 놓치지 않도록 돕고 추가 기능(타이머의 인터럽트, 외부 인터럽트)을 추가합니다.

버튼 처리를 중단하거나 인터럽트에서 중요한 이벤트를 추적할 수 있다고 가정해 보겠습니다. 결과적으로 프로그램은 더 시각적이지만 덜 혼란스럽습니다.

불행히도, 인터럽트는 프로그램이 엉망이 되는 상황에서 당신을 구해주지 못할 것입니다. 하나의 전체를 부분으로 나누는 것은 불가능합니다.

3. 자동 프로그래밍.

그래서 우리는이 기사의 주요 주제에 도달합니다. 유한 상태 기계에서 프로그래밍하면 처음 두 예제에 내재된 결점으로부터 프로그램을 구할 수 있습니다. 프로그램이 더 간단해지고 수정하기 쉽습니다.

오토마톤 스타일로 작성된 프로그램은 조건에 따라 한 상태 또는 다른 상태로 전환하는 스위치와 같습니다. 상태의 수는 처음에 프로그래머에게 알려져 있습니다.

대략적으로는 전등 스위치와 같습니다. 켜짐과 꺼짐의 두 가지 상태와 켜짐과 꺼짐의 두 가지 조건이 있습니다. 글쎄, 먼저 일을 먼저.

스위치 기술의 멀티태스킹 구현.

마이크로 컨트롤러는 부하를 제어하고 LED를 깜박이며 키 입력을 추적하는 등의 작업을 수행할 수 있습니다. 그러나 이 모든 작업을 동시에 수행하는 방법은 무엇입니까? 이 문제에 대한 많은 솔루션이 있습니다. 내가 이미 언급한 이들 중 가장 간단한 것은 인터럽트를 사용하는 것입니다.

프로그램 중에 인터럽트가 발생하면 컨트롤러는 프로그램 코드의 실행에서 주의를 분산시키고 인터럽트가 담당하는 프로그램의 다른 부분을 잠시 실행합니다. 인터럽트가 작동하면 프로그램의 작업 지점은 컨트롤러가 인터럽트에 의해 중단된 위치에서 계속됩니다(단어 자체는 컨트롤러가 중단되었음을 나타냄).

멀티태스킹을 구현하는 또 다른 방법은 다음을 사용하는 것입니다. 운영체제. 예, 저전력 컨트롤러에서 사용할 수 있는 소형 OS가 이미 등장하기 시작했습니다. 그러나 종종 이 방법은 다소 중복되는 것으로 판명됩니다. 결국, 약간의 유혈 사태로 버틸 수 있는 상황에서 불필요한 작업으로 컨트롤러 리소스를 낭비하는 이유는 무엇입니까?

스위치 기술을 사용하여 작성된 프로그램에서 이러한 멀티태스킹의 "환상"은 메시징 시스템 덕분에 얻을 수 있습니다. 프로그램이 물리적으로 동시에 코드의 다른 부분을 실행할 수 없기 때문에 "환상"이라고 썼습니다. 메시징 시스템에 대해 조금 더 이야기하겠습니다.

메시징 시스템.

여러 프로세스를 파괴하고 메시징 시스템을 사용하여 멀티태스킹의 환상을 만들 수 있습니다.

LED가 전환되는 프로그램이 필요하다고 가정해 보겠습니다. 여기에 두 개의 기계가 있습니다. LEDON(LED를 켜는 기계)과 LEDOFF 기계(LED를 끄는 기계)라고 부르겠습니다.

각 자동 장치에는 두 가지 상태가 있습니다. 즉, 칼 스위치가 켜져 있거나 꺼져 있는 것처럼 자동 장치는 활성 상태 또는 비활성 상태일 수 있습니다.

한 기계가 활성화되면 LED가 켜지고 다른 기계가 활성화되면 LED가 꺼집니다. 작은 예를 고려하십시오.

Int main(void) ( INIT_PEREF(); //주변기기(LED) 초기화 InitGTimers(); //타이머 초기화 InitMessages(); //메시지 처리 메커니즘 초기화 InitLEDON(); //LEDON 오토마톤 초기화 InitLEDOFF(); // LEDOFF 오토마톤 초기화 SendMessage(MSG_LEDON_ACTIVATE); //LEDON 오토마톤 활성화 sei(); //인터럽트 활성화 //프로그램 메인 루프 while(1) ( ProcessLEDON(); //LEDON 반복 automaton ProcessLEDOFF(); //LEDOFF 자동화 ProcessMessages()의 반복; //메시지 처리 ); )

3-7행에서 다양한 초기화가 발생하므로 지금은 특별히 관심을 두지 않습니다. 그러나 다음과 같은 일이 발생합니다. 메인 루프를 시작하기 전에(while (1)), 자동 장치에 메시지를 보냅니다.

메시지 보내기(MSG_LEDON_ACTIVATE)

LED 조명을 담당합니다. 이 작은 단계 없이는 우리의 허디거디가 작동하지 않을 것입니다. 다음으로 주요 무한 while 루프가 대부분의 작업을 수행합니다.

작은 탈선:

메시지에는 세 가지 상태가 있습니다. 즉, 메시지 상태는 비활성, 설정되었지만 비활성 및 활성일 수 있습니다.

메시지는 초기에 비활성화된 것으로 나타났습니다. 메시지를 보낼 때 "설치되었지만 비활성화됨" 상태를 받았습니다. 그리고 이것은 우리에게 다음을 제공합니다. 프로그램이 순차적으로 실행될 때 LEDON 오토마톤은 메시지를 수신하지 않습니다. 메시지를 단순히 수신할 수 없는 LEDON 자동 장치의 유휴 반복이 발생합니다. 메시지 상태가 "설치되었지만 비활성"이므로 프로그램이 계속 실행됩니다.

모든 오토마타가 유휴 상태가 된 후 대기열은 ProcessMessages() 함수에 도달합니다. 이 함수는 모든 자동 반복이 완료된 후 항상 루프의 끝에 배치됩니다. ProcessMessages() 함수는 단순히 "설정되었지만 비활성" 상태에서 "활성" 상태로 메시지를 변경합니다.

무한 루프가 두 번째 라운드를 완료하면 이미 완전히 다른 그림입니다. ProcessLEDON 자동화의 반복은 더 이상 유휴 상태가 아닙니다. 기기는 메시지를 수신하고 켜진 상태로 전환한 다음 메시지를 차례로 보낼 수도 있습니다. LEDOFF 기계로 전달되며 라이프 사이클메시지가 반복됩니다.

"활성" 상태의 메시지는 ProcessMessage 함수와 만날 때 소멸된다는 점에 유의하고 싶습니다. 따라서 메시지는 하나의 자동 장치에서만 받을 수 있습니다. 또 다른 유형의 메시지가 있습니다. 이는 브로드캐스트 메시지이지만 고려하지 않겠습니다. Tatarchevskiy의 기사에서도 잘 다루고 있습니다.

타이머

적절한 메시징을 사용하면 상태 머신이 작동하는 순서를 제어할 수 있지만 메시지 없이는 할 수 없습니다.

이전 예제 코드 스니펫이 의도한 대로 작동하지 않는다는 것을 눈치채셨을 것입니다. 기계는 메시지를 교환하고 LED는 전환되지만 우리는 이것을 볼 수 없습니다. 희미하게 켜진 LED만 보입니다.

지연에 대한 유능한 처리를 고려하지 않았기 때문입니다. 결국 LED를 교대로 켜고 끄는 것만으로는 충분하지 않으며 LED는 예를 들어 1초 동안 각 상태에서 머물러 있어야 합니다.

알고리즘은 다음과 같습니다.

클릭하면 확대할 수 있습니다

이 블록 다이어그램에 타이머가 똑딱 거리면 물론 LED를 켜거나 끄는 작업이 수행된다는 점을 추가하는 것을 잊었습니다.

1. 메시지를 수신하여 상태로 들어갑니다.

2. 타이머/카운터 판독값을 확인하고 똑딱거리면 작업을 수행하고, 그렇지 않으면 우리 자신에게 메시지를 보냅니다.

3. 다음 오토마톤에게 메시지를 보냅니다.

4. 나가기

다음 항목에서는 모든 것이 반복됩니다.

SWITCH 기술 프로그램. 세 단계입니다.

유한 오토마타로 프로그램을 작성해 보겠습니다. 이를 위해 세 가지만 수행하면 됩니다. 간단한 단계. 프로그램은 간단하지만 간단한 것부터 시작할 가치가 있습니다. 우리를 적합한 프로그램스위칭 LED 포함. 이것은 매우 좋은 예그러니 새로운 것을 발명하지 맙시다.

나는 C 언어로 프로그램을 작성할 것이지만 이것이 유한 오토마타에서 C로만 작성해야 한다는 의미는 아니며 다른 프로그래밍 언어를 사용하는 것이 상당히 가능하다는 의미는 아닙니다.

프로그램은 모듈식이므로 여러 파일로 나뉩니다. 우리의 모듈은 다음과 같습니다:

• 프로그램의 메인 루프 모듈에는 leds_blink.c, HAL.c, HAL.h 파일이 포함되어 있습니다.
• 타이머 모듈 timer.c, timers.h 파일 포함
• 메시지 처리 모듈 파일 messages.c, messages.h 포함
  
• 기계 모듈 1 ledon.c, ledon.h 파일 포함
• 기계 모듈 2 ledoff.c 파일 포함, 리드오프 .h

1 단계.

우리는 프로젝트를 만들고 즉시 정적 모듈의 파일을 여기에 연결합니다: timers.c, timer.h, messages.c, messages.h.

프로그램의 주요 주기 모듈의 leds_blink.c 파일.

#include "hal.h" #include "messages.h" //메시지 처리 모듈 #include "timers.h" //타이머 모듈 //타이머 인터럽트 //############# # ################################################### ############################# ISR(TIMER0_OVF_vect) // 인터럽트 벡터 전환(T0 카운터 타이머 오버플로) ( ProcessTimers(); / /타이머 인터럽트 핸들러) //############################################ ################################################### int 메인 (void) ( INIT_PEREF(); //주변(LED) 초기화 InitGTimers(); //타이머 초기화 InitMessages(); //메시지 처리 메커니즘 초기화 InitLEDON(); //LEDON 오토마톤 초기화 InitLEDOFF(); StartGTimer( TIMER_SEK); //타이머 시작 SendMessage(MSG_LEDON_ACTIVATE); //FSM1 오토마톤 활성화 sei(); //인터럽트 활성화 //프로그램 메인 루프 while(1) ( ProcessLEDON(); //반복 LEDON 자동화 ProcessLEDOFF(); ProcessMessages( ); //메시지 처리 ); )

첫 번째 줄에서 나머지 모듈은 주 프로그램에 연결됩니다. 여기에서 타이머 모듈과 메시지 처리 모듈이 연결되어 있음을 알 수 있습니다. 프로그램의 다음은 오버플로 인터럽트 벡터입니다.

int main (void) 줄에서 우리는 메인 프로그램이 시작된다고 말할 수 있습니다. 그리고 모든 것과 모든 것의 초기화로 시작됩니다. 여기서 우리는 주변 장치를 초기화합니다. 즉, 초기 값을 비교기의 입력 / 출력 포트와 컨트롤러의 다른 모든 내용으로 설정합니다. 이 모든 것은 INIT_PEREF 함수에 의해 수행되며, 본문이 hal.c 파일에 있지만 여기에서 실행합니다.

다음으로 타이머 초기화, 메시지 처리 모듈, 오토마타 초기화를 봅니다. 여기에서 함수 자체가 해당 모듈의 파일에 작성되더라도 이러한 함수도 간단히 실행됩니다. 얼마나 편리한지 보십시오. 프로그램의 주요 텍스트는 읽기 쉬운 상태로 유지되며 다리가 부러지는 중복 코드로 복잡하지 않습니다.

메인 초기화가 끝났습니다. 이제 메인 루프를 시작해야 합니다. 이를 위해 시작 메시지를 보내고 시계를 시작합니다. 타이머를 시작합니다.

시작GTimer(TIMER_SEK); // 타이머 시작 SendMessage(MSG_LEDON_ACTIVATE); //FSM1 머신 활성화

그리고 내가 말했듯이 메인 루프는 매우 간단해 보입니다. 우리는 모든 자동 장치의 기능을 기록하고 순서를 따르지 않고 열에 씁니다. 이러한 함수는 자동 핸들러이며 자동 모듈에 있습니다. 메시지 처리 모듈의 기능은 이 자동 피라미드를 완성합니다. 물론 이전에 메시징 시스템을 다룰 때 이미 말했습니다. 이제 메인 프로그램 루프 모듈의 두 파일이 어떻게 생겼는지 알 수 있습니다.

할.h는 헤더 파일프로그램의 메인 루프의 모듈.

#ifndef HAL_h #HAL_h 정의 #포함 #포함 //인터럽트를 포함한 표준 라이브러리 #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

보시다시피, 이 파일은 본질적으로 한 줄의 실행 코드를 포함하지 않습니다. 이는 모두 매크로 대체 및 라이브러리 연결입니다. 이 파일을 사용하면 삶이 매우 좋아지고 가시성이 향상됩니다.

하지만 Hal.c 파일은 이미 실행 가능한 파일이며, 이미 언급했듯이 다양한 주변 장치 초기화가 포함되어 있습니다.

#include "hal.h" void INIT_PEREF(void) ( //I/O 포트 초기화 //############################ ################################################### # ##### Komparator = ViklKomparator; //비교기 초기화 - DDRD 끄기 = 1<

글쎄, 나는 프로그램의 메인 사이클의 모듈을 보여 주었다. 이제 우리는 마지막 단계를 밟아야한다. 우리는 오토마타의 모듈 자체를 작성해야한다.

3단계

유한 오토마타(우리의 경우 LEDON 오토마톤 및 LEDOFF 오토마톤)의 모듈을 작성하는 것은 우리에게 남아 있습니다. 먼저 LED를 켜는 기계의 프로그램 텍스트인 ledon.c 파일을 제공하겠습니다.

//파일 ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //상태 변수 void InitLEDON(void) ( ledon_state=0; // 여기에서 다른 자동 변수가 있는 경우 초기화할 수 있습니다. ) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //inactive state if(GetMessage (MSG_LEDON_ACTIVATE) )) //메시지가 있으면 수락됩니다. ( //타이머가 확인됩니다. if(GetGTimer(TIMER_SEK)==one_sek) // 타이머가 1로 설정되어 있으면 실행( StopGTimer(TIMER_SEK); 포트 = 1<

여기에서 첫 번째 줄에는 항상 그렇듯이 라이브러리가 연결되고 변수가 선언됩니다. 다음으로, 우리는 이미 만났던 기능을 이미 수행했습니다. 이것은 InitLEDON 오토마톤의 초기화 기능이며 ProcessLEDON 오토마톤 핸들러 자체의 기능입니다.

핸들러의 본문에서 타이머 모듈과 메시지 모듈의 기능은 이미 처리 중입니다. 그리고 자동 장치 자체의 논리는 스위치 케이스 설계를 기반으로 합니다. 그리고 여기에서 몇 가지 케이스 스위치를 추가하여 자동화 처리기가 복잡해질 수도 있음을 알 수 있습니다.

자동 장치의 헤더 파일은 훨씬 더 간단합니다.

//fsm1 파일 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); 무효 프로세스LEDON(무효); #endif

여기에서 링크 파일 hal.h를 연결하고 함수의 프로토타입도 지정합니다.

LED 끄기를 담당하는 파일은 미러 이미지에서만 거의 동일하게 보이므로 여기에 표시하지 않습니다 - 꺼림 🙂

이 링크에서 모든 프로젝트 파일을 다운로드할 수 있습니다. ====>>> 링크.

다음은 세 단계이며 우리 프로그램은 완성된 모습을 얻었습니다. 즉, 오늘의 임무는 끝났고 마무리할 시간입니다. 이 기사에 제공된 정보가 귀하에게 매우 유용할 것 같습니다. 그러나 이 지식을 실천에 옮길 때만 진정한 유익을 얻게 될 것입니다.

그건 그렇고, 나는 특히 흥미로운 여러 흥미로운 프로젝트를 계획 했으므로 새 기사 구독 . 추가 자료도 보내드릴 예정이라 많은 분들이 이미 메인페이지를 통해 구독중입니다. 여기에서도 구독할 수 있습니다.

글쎄, 이제 나는 모든 것을 가지고 있으므로 행운을 빕니다. 기분이 좋고 다시 만나십시오.

N/A 블라디미르 바실리에프