�� ���� ������ ���ǵ� Game Programming Gems 3 �ѱ�����(���� ��, ������ȭ��)�� �Ϻ��Դϴ�. �� �ۿ� ���� ��� �Ǹ��� ������ȭ�簡 ������ ������, ���� ��� ���̴� �� ����Ʈ �Խø� ����� ��� ������ ������� �����Ǿ� �ֽ��ϴ�. �� ���� ���� ���� ���� �����̹Ƿ� ��Ÿ�� ������ ���� �� �ֽ��ϴ�. ���� �� �������� �Ѱ� ��, ������ ���̿� �μ�� ���¿ʹ� �ٸ� �� �ֽ��ϴ�. ���� å������ ǥ�� ������ �� �� ��Ȯ�� ���·� ǥ�õ� ���̸� ��/��ǥ ���� ������ ������ �ѱ�ȭ�� ���Դϴ�. Game Programming Gem 3 �ѱ����ǿ� ���� ������ GPG ���͵�(http://www.gpgstudy.com/)���� ���� �� �ֽ��ϴ�. |
������ 1�ο� ������ �Ļ��ع��� �÷��̾�� ������ �� ���� �������̳� ���� �����⸦ ã�� �ȴ�. ���� ������ �����Ϸ��� �� ��뿡�� ������ �� �־�� �Ѵ�. Ȯ�强 �ִ� ������� ����Ʈ���� �� ����� ���ӿ� ���� �ϳ��� ǰ�� �������� ���ֵ� �� ������, ������ �Ϲ����� ������ ����� �÷��� �� �ִ�. ������ �װ��� RTS�̵� �ƴϸ� RPG�� ���̵�, �÷��̾ ��� ���·ε� �������� Ŀ����ȭ�ϰų� ���ο� �������� �߰��ϴ� ���� �����ؾ� �Ѵ�.
Baldur��s Gate, StarCraft, Dungeon Siege�� �Ǹ��� �������� �Ǵ� �������� �÷��̾ ���ο� ����Ʈ���� ����ų� ������� AI�� �����ϰ� Ȯ���ϴ� ���� �����ϴٴ� ���鵵 ���Եȴ�. ���� �÷��̾�� ���α��Ӱ� �ƴϹǷ� �÷��̾�鿡�� ������ ���α��� �� ��쵵�� �ϰų� ������� �����ϴ� ���� �Ұ����ϴ�. ����� �÷��̾ ������ �����̳� ����Ʈ�� ���� �� �������� �������ٵ� �ܼ����� ����Ǿ�� �ϴµ�, ���� �ܼ����� Ȯ�强�ִ� Ʈ���� �ý����� ���ؼ� ������ �� �ִ�.
Ʈ���� �ý����� �������� ���ϰ� ������ �����Ѵ١���� �� ���� ������ ���� �߾� ����ȭ�� �ڵ��̴�. �Ϸ��� ���ǵ��� �����Ǹ�, �Ϸ��� �������� ����ȴ�. �̷��� ������ �ý����� ����ϰ�, �����ϱ� �����, ������ �ֵ���[Rabin0]���� ���� ����. Ʈ���� �ý����� �پ��� ������ �������� �ذ��� �� ������, Ư�� �����̳ʿ� �÷��̾ ���� ������ �� �ִٴ� ������ �ٶ����ϴ�. Ʈ���� �ý����� �ŷ��� �������ٵ� �÷��̾ Ž���� ��̷Ӱ� ��ȣ�ۿ����̸� ���ο� ȯ���� ���� ���� �� �ֵ��� �Ѵٴ� �� �ִ�.
�ϴ��� ���谡���� ������ Ž���ϴ� ������ �����غ���. ������ ���� ������ ����ϴ� ���� ������ ���� ��տ� ������ �Ұ� �ȴ�. ���� �λ����� ������ �������� ������ �� �ٶ��� �Ҿ� �� ȶ�ҵ� ���߸���. ������ ȶ�ҿ� ���� ���� �� ������ ���� �����ſ� �����̿� �� ���� ����ϸ��ϡ���� ������ ������ ���� ���. ��� �����غ� ��, ü���� ���ſ� ��� �ϳ��� ���� ����� ��ħ�뿡 �÷����Ҵ��� ���� ������ ������.
������ ����-���� �з������� �̿��ϴ� Ʈ���� �ý������� �̷��� ��ǵ��� �����ϴ� ���� �����ϴ�. ����� Ư�� ��� ��ü�� 1���� �̳��� �����ϸ� �ٶ� �Ҹ��� �ش��ϴ� ���� ȿ���� ����ϰ� �� �ֺ��� ȶ�ҵ��� ���߸��ٴ���, �÷��̾��� ��Ƽ ����� �� �ϳ��� ���� ����� ��ħ�� ���� �ö� ���� ���� ���� ������ ���� ���� ȿ���� ����ϴ� ���� ��� ����-���� �з����ӿ� ���Ѵ�.
Ʈ���� �ý����� �� �����Ѵٸ�, �����̳ʿ� �÷��̾� ��ΰ� ��â���� �ó����� �� ����Ʈ�� �ۼ��� ���� ���� �ð� ���� �����ϵ��� ���� �� �ִ� ��ġ���� ���� �� �ִ�. StarCraft �� ������� ������ ���� ���� Ʈ���� �ý����� ���̴�. ������ �ý����� �����ϰ� ���ο� ���̵� ����� ���� ���� �������� �⺻���� �ڼ��̴�.
Ʈ���� �ý����� ó�� ���� ������ �ϳ��� ������ Ʈ���� �ý���([Orkin02]�� ���� �� ����)�� ���ø��� �� ���̴�. ���� �� �� ������ ������ ���Ѵٸ� ��� ������Ʈ�� ��ü, ����Ʈ�� ������ �� �ִ� Ʈ���� �ý��� Ŭ������ ������ �� �� �ִ�. ��� ��ü�� Ʈ���� �ý����� ������ �ϴ� ���� �ƴ�����, ��ü���� �ڽ��� Ʈ���� �ý��� �ν��Ͻ��� ���� �� �ִٸ� ��ü �ȿ� ������ ĸ��ȭ�ϴ� ������ ������ �Ǹ� �ý����� �� �� �����ϰ� ��ü�������� �� �� �ִ�. ���� Ʈ���Ŷ�� �� ��ü�� Ư�� ��ü�� ���� �۵��ϰ� �ǹǷ�, �÷��̾ ������ ��� ������ ������ �ȴ�.
�������� �ٰ����� ������ ������ ����� �����غ���. ���� ����� ���� ������ �ȿ��� �����ϰ� �ű ������ ������ �ൿ�� �����ϴ� �ϳ��� Ʈ���� ���Ǹ� �ο��Ѵ�. ���� �����̳ʳ� �÷��̾ ������ ���� ���� ���� ��յ��� ��ġ�ϸ�, �����ϰԵ� �ǵ��ߴ� ����� ����� �� �� �ְ� �ȴ�. �̴� Ʈ���� �ൿ�� ��ü�� ���� �����Ǿ� �ֱ� ������ ������ ���̴�. �̷� ��Ŀ����� ��� ������Ʈ�� ��ü, ����Ʈ�� �������� �ش� ��ü���� ���� �����ϴ� �ڽŸ��� ������ Ʈ���� �ý����� ���� �� �ִ�.
���� �ȿ��� ����ȭ�� �� �ִ� �̺�Ʈ�� ���¶�� ��� ���̶� ������ �� �� �ִ�. ������ ���� ���� �ȿ� ���������� �μ����̳� ���� �����⸦ ���ؼ� ������ �� �ִ� ������ �ſ� ũ��. ������ ������ �� ���� ���ǵ��̴�.
���ǵ��� AND, OR, NOT, XOR ���� �ο� �����ڵ�� ������ �� �ִٸ� ���ǵ��� �� �� �������� �� �ִ�. ���� ��� �÷��̾ ������, ��������, ���������� �����ؾ߸� � ���� ������ �Ǿ� �ִٸ� ���ǵ��� AND�� ���յǾ�� �Ѵ�. �� � ���� �÷��̾ �����質 �ذ� �� �ϳ��� ������ �־ ���� �� �ִٸ� ���ǵ��� OR�� ���յǾ�� �Ѵ�. �� 3.5.1�� 3.5.2�� ���� ���ǵ��� Ʈ�� ������ ǥ���� ���̴�.
AND ���̸� Ʈ���� �ߵ� �� ���� ������ ���� �������� ���� �������� ����
�� 3.5.1 �� ���� ��� �������̸� ���� ������.
OR ���̸� Ʈ���� �ߵ� �� ���� �����踦 ������ ���� �ذ踦 ������ ����
�� 3.5.2 �� �� �ϳ��� �������̸� ���� ������.
�� �� ������ ����, �÷��̾ ������, ��������, ���������� �����ϰ� ������ ������ �Ǵ� �ذ踦 ������ �־�� ���� ������ �ȴٸ� ��� �ɱ�? �� 3.5.3�� ���� ���ǵ��� ǥ���� ���̴�.
�̿� ���� ������ ���� �ð�ȭ�� �ڵ带 ����ȭ�ϴ� ���� ����� �����Ѵٴ� ������ �߿��� ���Ǹ� ���´�. �� ��Ұ� �ϳ��� Ŭ������ ��� �� ������ Ŭ������ �ʿ��ѵ�, �ϳ��� Operator Ŭ�����̰� �� �ϳ��� Condition Ŭ�����̴�. Operator Ŭ������ ������ �ο� ������ó�� �۵��ϵ��� ������ �� ���̴�. ���� ���� ������, �ǿ����ڵ��� ���Ե� ǥ������ ��Ÿ���� ���ؼ��� �ٸ� Operator �ν��Ͻ����̳� Condition �ν��Ͻ������ �����͵��� ��ϵ� ��ƾ� �Ѵ�. Condition Ŭ������ ������ ���� ������ ���ǵ��� ���� �� �־�� �ϸ�, ������ Ŀ����ȭ�� ���� �μ����� ��ƾ� �Ѵ�.
AND ���̸� Ʈ���� �ߵ� �� ���� ������ ���� �������� ���� �������� ���� OR �����踦 ������ ���� �ذ踦 ������ ����
�� 3.5.3 ���� �� �� ������ ���ǵ�
���� �ȿ��� �����ϰ��� �ϴ� ���³� �ൿ�̶�� ��� �͵� ������ �� �� �ִ�. ���ǰ� ����������, ���� ��ü�� ���� ���� �ȿ� ���������� �μ��� �Ǵ� ���� �����⸦ ���ؼ� ������ �� �ִ�. ������ ������ �������� ����̴�.
Ư�� ���ǵ��� ������ �����Ǹ� �� �ش��ϴ� ������ ����ȴ�. �̸� �� �ϳ��� ������ �ƴ϶� ���� ���� �������� �������� Ȯ���� ���� �ִ�. ���� �ϸ� �ϳ��� Ʈ���� �ߵ��� ���� ���� �͵鿡 ���ÿ� ������ ��ġ�� �� ���� �ְ�, ���� ������ �� ������ ���� ����ǵ��� �� ���� �ִ�.
Ʈ���ſ� ���ǵ��� ���ǵǾ��ٰ� �� ��, �������� �ʿ��� ���� �� Ʈ������ ���ǵ��� ���ؼ� �ߵ� ���θ� �Ǵ��ϴ� �����̴�. �켱 ������ ����, Ư�� ������ �̺�Ʈ �ֵ�������(Ʈ���� �ý��ۿ� �̺�Ʈ�� �����DZ⸦ ��ٸ��� ��) �ƴϸ� ���� ���踦 �ֱ������� �����ؾ� �ϴ����� �����ϴ� ���̴�. �� ��� ��� �����ϴ� ���� �������� ������ �ȴ�.
�̺�Ʈ �ֵ����� ������ ���, �̺�Ʈ�� Ʈ���� �ý��ۿ� ������ �� �ֵ��� �ϴ� �������̽��� �ʿ��ϴ�. ���� ������ ����� �̺�Ʈ ������ ����ϴ� ���̴�. �̺�Ʈ ������ ���� �̺�Ʈ�� ������ �̺�Ʈ�� ���õ� ��Ÿ ������ ������ �����ȴ�. �̺�Ʈ ������ ���� �� �� �ڼ��� ������ [Rabin02]�� �����ϱ� �ٶ���.
�ֱ��� ���� ����� �����̶��, Ʈ���� �ý��� �ȿ��� ������ ���ǵ��� �����ϴ� ��� ���� �Լ��� ȣ���ϴ� ��Ŀ� ���� �����غ� �� �ִ�. �� �Լ����� �̺�Ʈ �ֵ��� ���ǵ鿡 ���� ������ �Ͼ�� �ʾƾ� �Ѵ�.
�̺�Ʈ ������ �ֱ��� ���� ������ Ʈ���� �ý��ۿ� ���Դٸ�, �װ��� ���ǵ鿡�� �����ؾ� �Ѵ�. �� 3.5.4�� �̺�Ʈ ������ �ֱ��� ���� ��θ� �䱸�ϴ� �ϳ��� ���� ������ ���̴�. ���� ������ �浹 �̺�Ʈ�� ��ٸ��� �ݸ�, �ݸ� ������ ������ �ֱ��� ���� ������ ������ �� ������ �����Ѵ�.
�̺�Ʈ ������ �ֱ��� ���� ������ Ʈ���� �ý��ۿ� ������, �װ��� �� Ʈ������ ��Ʈ Operator �ν��Ͻ��� �����Ѵ�. Operator�� �װ��� �ڽ��� �ڽĵ鿡�� �Ѱ��ָ�, �ڽĵ��� �� ���� �Ǵ� ����� ������ �Ǵ� ������������ �����ش�. �� �ڽ� ���� ���� ��û�� �ڽ��� �ڽĵ鿡 �Ѱ��ش�. ���� ��û�� ���� ���ǿ� �����ϸ� ��/���� ������ �Ͼ�� �ǰ�, �� ������� ���� Operator �ν��Ͻ��� �ö� �ο� �����ڿ� ���� ��/���� ������ �Ͼ��. �� ������ ��/������ ��Ʈ���Ա��� �ö� �������� ����� ���������.
�̺�Ʈ ���� �� �ֱ��� ���� ���� AND ���̸� Ʈ���� �ߵ� �� 10 ���� ���� �÷��̾ 10 ���� �̳� �÷��̾��� �ǰ��� 50% �̻�
�� 3.5.4 �ϳ��� Ʈ���Ű� �̺�Ʈ �ֵ��� ����(�Ʒ� ����)�� �ֱ��� ���� ����� ����(�Ʒ� ������)�� ��� ���� ��
Operator Ŭ������ �ڽĵ��� ó���� �� ���� ��(lazy evaluation)�� ����ؾ� �Ѵٴ� ���� �����ϱ� �ٶ���. ��� ������ �ش� �����ڿ� ���� �������� ���� ���, Ʈ������ ������ �� �������� ������. ���� ��� �� 3.5.4���� ��� �̺�Ʈ ������ ���� ���ǿ� ���ǰ� �װ��� ������������ �����Ǿ��ٸ� ������ �������δ� �� �̺�Ʈ ������ ������ �ʵ��� �ϴ� ���̴�. �̷��� �ϸ� ó�� �ð��� ���̴� �� ������ �ȴ�.
�� �ٸ� �߿��� �� �ϳ���, �̺�Ʈ �ֵ��� ������ ��� ������ ���������� �缳���DZ� �������� �̺�Ʈ���� ����ϰ� �־�� �Ѵٴ� ���̴�. �� 3.5.4�� �������� �÷��̾ 10���� �̳��� �����ϸ� �浹 �̺�Ʈ�� Ʈ���ſ� ���Ǿ�� �Ѵ�. ���� ������ �� �̺�Ʈ�� ����� �ΰ�(�÷��̾ 10 ���� �ٱ����� ������ ��������), ������ �̺�Ʈ ������ �ֱ��� ���� ���ſ� ���� �� �������� ������� �Ѵ�.
��� ��������, Ư�� Ʈ������ ���ǵ��� ��� ���� �����شٸ� Ʈ���Ű� �ߵ��ȴ�. Ʈ���Ű� �ߵ��Ǹ� �ߵ��Ǿ��ٴ� ����� ����ؼ� ���� �ٽ� �ߵ��Ǵ� ���� ������ �ؾ� �Ѵ�.
��� Ʈ���ŵ鿡�� �߰������� �� ���� �Ӽ����� �� �ʿ��ϸ�, �� �Ӽ����� �����̳ʰ� �����ϰ� �ȴ�.
bool SingleShot; // Ʈ���Ű� �� ���� �ߵ��Ǿ�� �ϴ����� ���� float ReloadTime; // Ʈ���Ű� ���� �� �ߵ��Ǿ�� �ϴ� ���, // �缳���DZ������ �ð�
�� �� �Ӽ����� Ʈ���Ű� �� �� �̻� �ߵ��� �� �ֵ��� �Ѵ�. SingleShot �Ӽ��� Ʈ���Ű� �� ���� �ߵ��Ǿ�� �ϴ��� �ƴϸ� ���� �� �ߵ��� �� �ִ����� ���θ� ����Ų��. SingleShot�� ���������� ��, ReloadTime�� Ʈ���Ű� �� �� �ߵ��� �� �ٽ� �ߵ��� �� ���� ������, �� ���ǵ��� �ʱ�ȭ�ϰ� �ٽ� �̺�Ʈ�� �ް� �� ������ �ɸ��� �ð��� �����Ѵ�.
Ʈ���ŵ��� �Բ� ���յ� �� ��������, �ý��� ���� ��� Ʈ���ŵ��� ������ �� ������ ��� ������ �� �ִ� ���µ��� �����ؾ� �Ѵ�. ���� Ʈ���� �ý����� �ߵ��� Ʈ���ŵ��� ���¸� ������ �� �ִ� �Ϸ��� �÷���� ī���͵��� ���� �ʿ䰡 �ִ�. �̸� �ִ��� �Ϲ�ȭ�ϱ� ����, ������ Ʈ���Ű� ���ڿ� �̸����� ������ �� �ִ� ������ �÷����� ���� �� �ֵ��� ����. Ʈ���� �ý����� �÷��� �̸��� ������ �� �÷��� �����ϰų�, �����Ǿ� �ִٸ� �ƴϸ� �÷��� �����Ѵ�. ������ �÷��״� �ý����� ����� ������ �����ȴ�.
������ ���� ���ο� ���ǵ��� �����غ���.
�̷� ���ǵ��� �߰��ȴٸ�, ������ ���� ���ο� �������� �ʿ��� ���̴�.
�̷��� �÷���� ī���͵��� ������ Ʈ���� �ý����� Ư�� �̺�Ʈ�� ǥ�ø� �ϰų� �ߵ� Ƚ���� �� �� ������, �̸� ���ؼ� ���� ��� �÷��̾ Ư�� ������ �鸰 Ƚ�� ���� �� �� �ִ�. ���� �̺�Ʈ���� Ư���� ������ ������ ������(���� ��� �� ���� Ÿ�ϵ��� Ư���� ������ ����� �� ��) Ʈ���Ű� �ߵ��ǵ��� �� ���� �ִ�. �̷��� �÷���� ī���͵��� ���� ������ �����Ƿ�, �� �� ���� ������ Ʈ���ŵ��� ����������.
�� 3.5.5�� �÷��̾ � ���� ���� ���ؼ� Ư�� ������ �ݺ������� ã�ƿ��� ��쿡 �� ��� ���� �ܼ��� �����ϴ� ���̴�. �� ���� �������� Ʈ���ŵ��� ��Visited����� �̸��� ī���� ���ؼ� ���� ���������� �۵��Ѵٴ� ���� �ָ��ϱ� �ٶ���.
AND "Visited"�� ���� AND "Visited"�� ���� �÷��̾ "Visited"�� �÷��̾ "Visited"�� ���� A �ȿ� ���� ¦�� ���� C �ȿ� ���� Ȧ�� AND �� D�� ���� �ܼ��� ����߸� "Visited"�� �� D�� 8�� ���� �����
_�� 3.5.5 �� ���� Ʈ���ŵ��� ��Visited"��� �̸��� ī���� ���ؼ� �Բ� �۵��ϴ� ��. �÷��̾ �� D�� ���� ���� ä�� ���� A�� C�� ������ 8�� �湮�ϸ� �ܼ��� ���õȴ�.
�÷��� ī���Ͱ� �߰��Ǹ�, Ʈ���� �ý����� ���´� ���� ��Ű����[Isla02]�� �ſ� ���������. �÷���� ī���͵��� ������ �ǰ� Ʈ���ŵ��� ������ ������ �����ϴ� ���� ��õ(knowledge source)�� ������ �ϰ� �Ǵ� ���̴�. ���� Ʈ���ŵ��� ��κ� ������ �ܺηκ��� ��Ե� �����Ϳ� ���� �ۿ��ϹǷ�, ������ ���ؼ� Ʈ���� �ý����� �� ���� ��Ű������ ���� �ƴϴ�.
Ʈ���� �ý����� ��ɼ��� ��ũ���� ����� ��ɼ��� ����ϴٴ� ���� ��ġ æ ���ڵ� ���� ���̴�. Ư�� ���� ������ �߰��Ǹ� ���� ���������. �� ���� ��ɼ��� ��ġ�� �κе� �����ϳ�, ������ ����� ���� ��ũ���� �� ���� Ʈ���� �ý����� ������ ���� �������� ������.
�� �ۿ��� ���� �� �ý����� �ֵ� �Ѱ�� �Ը𰡺���(scalability)�� ���� �ʴٴ� ���̴�. ���� �̷��� ������ ������ Ʈ���ŵ��� �ɷ����� �߰����� �ڵ带 ���ؼ� �ذ��� �� �ִ�. �������� ���� ���ܴ� �̹� �� ȿ���� ������� �����Ǿ���.
�� �ٸ� �Ѱ�� ���ǵ�� �������� �����ϱ� ���� ���ְ� �������� �ȿ� �����Ǿ� �ִٴ� ���̴�. ������� ������ �ڵ�� �����ϴ� �κ��� ���α����� ���� ���ľ� �Ѵ�. �̴� ������ ������ �Ǵ� �Ҽ��� �ǵ��� �������κ��� ��ȣ�� �� �ִٴ� ������ �DZ �ϴ�.
������ ���� ������ �ô��� ���� �����ڵ鿡�� �־� Ȯ�强 �ִ� Ʈ���� �ý����� ���� ���� ��ġ������ ������ ���� ���� ���̴�. ���� ������ ��ŭ�� ��ġ�� ���̸� ���ӿ� �ο��� �� �ִٴ� ���� ���� ���ƾ� �� ���̴�. Ȯ�强�ִ� Ʈ���� �ý����� ���� ���α��� �ɷ��� ������ ���� ���� �����̳ʵ� ������ ������ �� �ְ� �ϴ� ȿ������ �����̴�. ��� ���� Ʈ���� �ý����� �ʹ� ������ �ذ�å���� ������ ���� �ְ�����, ��ǥ�� �����̳ʿ� �÷��̾�� �� ���� �ɷ��� �ο��ϴ� �� ������ �ؾ�� �� �ȴ�. ����� ���� ���� ������ �����ϴ� ����� ����� ������� ������ ���� Ȯ��ǰ� �÷��̾�� �� ���� ��̸� ���� �� �ִ�.