آلات محدودة-الدولة: النظرية والتطبيق

جهاز الدولة محدود نموذج يستخدم لتمثيل، والتحكم في تدفق التنفيذ. أنها مثالية لتنفيذ منظمة العفو الدولية في الألعاب، وتسفر عن نتائج كبيرة دون رمز معقدة. ويصف هذا البرنامج التعليمي نظرية وتنفيذ واستخدام آلات الدولة محدودة بسيطة والمستند إلى المكدس.

كل الرموز التي قدمها لورك، ومتاح على http://game-icons.net.

ملاحظة: على الرغم من أن تتم كتابة هذا البرنامج التعليمي باستخدام AS3 وفلاش، يجب أن تكون قادراً على استخدام نفس الأساليب والمفاهيم في ما يقرب من أي بيئة تطوير اللعبة.

ما هو جهاز الدولة محدودة؟

آلة الدولة محدودة، أو ولايات ميكرونيزيا الموحدة لفترة قصيرة، نموذج لعملية حسابية استناداً إلى آلة افتراضية لدولة واحدة أو أكثر. سوى دولة واحدة يمكن أن تكون نشطة في نفس الوقت، حتى الجهاز يجب الانتقال من دولة إلى أخرى بغية تنفيذ إجراءات مختلفة.

فسمس تستخدم عادة لتنظيم وتمثيل تدفق تنفيذ، ومفيدة لتنفيذ منظمة العفو الدولية في الألعاب. "عقل" للعدو، فعلى سبيل المثال، يمكن تنفيذها باستخدام ولايات ميكرونيزيا الموحدة: كل دولة تمثل أحد إجراءات، مثل الهجوم أو التهرب من:

يمكن أن يمثله ولايات ميكرونيزيا الموحدة إلى الرسم بياني، حيث العقد هي الدول والحواف الانتقالات. وقد كل حافة تسمية إعلام عندما يجب أن يحدث الانتقال، مثل اللاعب بالقرب من التسمية في الشكل أعلاه، مما يشير إلى أن الجهاز سوف تمر بمرحلة انتقالية من التجول للهجوم إذا كان اللاعب بالقرب من.

تخطيط الدول وانتقالها

ويبدأ تنفيذ ولايات ميكرونيزيا الموحدة مع الدول، والتحولات التي سيكون لها. تخيل ولايات ميكرونيزيا الموحدة التالية، يمثل دماغ نملة تحمل يترك المنزل:

نقطة البداية هي الدولة أوراق البحث، الذي سيبقى نشطاً حتى النمل يجد الورقة. وعندما يحدث ذلك، هو انتقلت الدولة الحالية العودة إلى الوطن، الذي يبقى نشطاً حتى يحصل على النمل المنزل. عندما تصل النمل أخيراً إلى المنزل ، تصبح الحالة النشطة ورقة مرة أخرى ، لذلك تكرر النمل رحلتها.

إذا كانت الحالة النشطة أوراق البحث والنهج مؤشر الماوس النملة، هناك مرحلة انتقالية إلى التشغيل الدولة بعيداً. في حين أن الدولة نشطة، سيتم تشغيل النمل بعيداً عن مؤشر الماوس. عندما لا يكون المؤشر تهديدًا بعد الآن ، يكون هناك انتقال إلى حالة البحث عن الأوراق.

منذ ذلك الحين وهناك انتقالات ربط أوراق البحث واهرب، النمل سيتم تشغيل دائماً بعيداً عن مؤشر الماوس عند ذلك النهج طالما النمل هو العثور على الورقة. أنه لن يحدث إذا كانت الحالة النشطة الذهاب الصفحة الرئيسية (راجع الشكل الوارد أدناه). وفي هذه الحالة النمل سوف المشي المنزل دون خوف، فقط الانتقال إلى الدولة أوراق البحث عندما تصل إلى الصفحة الرئيسية.

تنفيذ من ولايات ميكرونيزيا الموحدة

ويمكن تنفيذها ولايات ميكرونيزيا الموحدة ومغلفة في فئة واحدة، باسم ولايات ميكرونيزيا الموحدة على سبيل المثال. والفكرة أن تنفذ كل دولة من الدول كدالة أو أسلوب، باستخدام خاصية تسمى activeState في الفئة لتحديد الدولة التي تكون نشطة:

public class FSM {
  private var activeState :Function; // points to the currently active state function

	public function FSM() {
	}

	public function setState(state :Function) :void {
		activeState = state;
	}

	public function update() :void {
		if (activeState != null) {
			activeState();
		}
	}
}

نظراً لكل دولة دالة، بينما تنشط دولة محددة تمثل الدالة التي تكون الدولة التذرع بكل لعبة التحديث. الخاصية activeState مؤشر إلى دالة، حيث أنها تشير إلى الدالة الحالة النشطة.

يجب أن يكون الأسلوب update () من الفئة ولايات ميكرونيزيا الموحدة استدعاء كل إطار اللعبة، ذلك لأنه يمكن استدعاء الدالة يشير بواسطة الخاصية activeState. سيتم تحديث هذه الدعوة الإجراءات التي تتخذها الدولة النشط حاليا.

الأسلوب setState() سوف تمر بمرحلة انتقالية ولايات ميكرونيزيا الموحدة لدولة جديدة التي تشير الخاصية activeState إلى وظيفة دولة جديدة. وظيفة الدولة لا يجب أن تكون عضوا في ولايات ميكرونيزيا الموحدة؛ أنها يمكن أن تنتمي إلى فئة أخرى، الأمر الذي يجعل فئة ولايات ميكرونيزيا الموحدة أكثر من عام والقابل لإعادة الاستخدام.

باستخدام FSM

باستخدام فئة FSM الموصوفة بالفعل ، فقد حان الوقت لتنفيذ "الدماغ" للشخصية. سوف تستخدم النمل سبق شرحه وتسيطر ولايات ميكرونيزيا الموحدة. ما يلي تمثيل للدول والتحولات، مع التركيز على التعليمات البرمجية:

يتم تمثيل النملة من قبل طبقة النملة ، التي لها خاصية تسمى الدماغ وطريقة لكل ولاية. خاصية الدماغ هي مثال لفئة FSM:

public class Ant
{
	public var position   :Vector3D;
	public var velocity   :Vector3D;
	public var brain      :FSM;

	public function Ant(posX :Number, posY :Number) {
		position 	= new Vector3D(posX, posY);
		velocity 	= new Vector3D( -1, -1);
		brain		= new FSM();

		// Tell the brain to start looking for the leaf.
		brain.setState(findLeaf);
	}

	/**
	 * The "findLeaf" state.
	 * It makes the ant move towards the leaf.
	 */
	public function findLeaf() :void {
	}

	/**
	 * The "goHome" state.
	 * It makes the ant move towards its home.
	 */
	public function goHome() :void {
	}

	/**
	 * The "runAway" state.
	 * It makes the ant run away from the mouse cursor.
	 */
	public function runAway() :void {
	}

	public function update():void {
		// Update the FSM controlling the "brain". It will invoke the currently
		// active state function: findLeaf(), goHome() or runAway().
		brain.update();

		// Apply the velocity vector to the position, making the ant move.
		moveBasedOnVelocity();
	}

	(...)
}

لدى فئة النمل أيضا خاصية السرعة والموقع ، كلاهما يستخدم لحساب الحركة باستخدام تكامل أويلر. يسمى أسلوب التحديث () كل إطار لعبة ، لذلك سيتم تحديث FSM.

للحفاظ على الأمور بسيطة ، سيتم حذف الرمز المستخدم لنقل النمل ، مثل moveBasedOnVelocity (). يمكن العثور على مزيد من المعلومات حول ذلك في سلسلة "فهم سلوكيات القيادة".

فيما يلي تنفيذ كل حالة ، بدءًا من findLeaf () ، وهي الدولة المسؤولة عن توجيه النملة إلى موضع الورقة:

public function findLeaf() :void {
	// Move the ant towards the leaf.
	velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);

	if (distance(Game.instance.leaf, this) <= 10) {
		// The ant is extremelly close to the leaf, it's time
		// to go home.
		brain.setState(goHome);
	}

	if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
		// Mouse cursor is threatening us. Let's run away!
		// It will make the brain start calling runAway() from
		// now on.
		brain.setState(runAway);
	}
}

حالة goHome () ، تستخدم لتوجيه المنزل النمل:

public function goHome() :void {
	// Move the ant towards home
	velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);

	if (distance(Game.instance.home, this) <= 10) {
		// The ant is home, let's find the leaf again.
		brain.setState(findLeaf);
	}
}

وأخيرا ، فإن حالة runAway () ، تستخدم لجعل النملة الفارة من مؤشر الفأرة:

public function runAway() :void {
	// Move the ant away from the mouse cursor
	velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);

	// Is the mouse cursor still close?
	if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
		// No, the mouse cursor has gone away. Let's go back looking for the leaf.
		brain.setState(findLeaf);
	}
}

والنتيجة هي نملة يتحكم فيها "دماغ" FSM:

تحسين التدفق: ولايات ميكرونيزيا الموحدة المستندة إلى المكدس

تخيل أن النمل تحتاج أيضا إلى تشغيل بعيداً عن مؤشر الماوس عند ذلك هو الذهاب إلى المنزل. يمكن تحديث ولايات ميكرونيزيا الموحدة إلى ما يلي:

يبدو أنه تعديل بسيط ، إضافة إلى انتقال جديد ، لكنه يخلق مشكلة: إذا تم تشغيل الحالة الحالية ولم يعد مؤشر الماوس قريبًا ، فما هي الحالة التي يجب أن ينتقل إليها النمل: العودة إلى المنزل أو البحث عن الأوراق؟

الحل لهذه المشكلة هو FSM المستندة إلى مكدس. بخلاف FSM الموجود لدينا ، تستخدم FSM المستندة إلى مكدس a مكدس للتحكم في الحالات. يحتوي الجزء العلوي من المكدس على الحالة النشطة؛ يتم التعامل مع التحولات عن طريق دفع أو تفرقع حالات من المكدس:

يمكن أن تحدد الحالة النشطة حاليًا ما يجب فعله أثناء عملية النقل:

يمكن أن البوب نفسه من المكدس ودفع دولة أخرى ، مما يعني انتقال كامل (تماما مثل ما فعلته FSM بسيطة). يمكن أن ينبثق من الكدسة ، مما يعني أن الحالة الحالية قد اكتملت وأن الحالة التالية في الكومة يجب أن تصبح نشطة. وأخيرًا ، يمكنها فقط دفع حالة جديدة ، مما يعني أن الحالة النشطة حاليًا ستتغير لبعض الوقت ، ولكن عندما تنبثق من الرصة ، فإن الحالة النشطة سابقًا سوف تتولى أمرها مرة أخرى.

تنفيذ FSM المستندة إلى المكدس

يمكن تنفيذ FSM المستندة إلى مكدس باستخدام نفس الأسلوب كما كان من قبل ولكن هذه المرة باستخدام صفيف من مؤشرات الدالة للتحكم في المكدس. لم تعد هناك حاجة إلى خاصية activeState ، نظرًا لأن قمة الحزمة تشير بالفعل إلى الحالة النشطة حاليًا:

public class StackFSM {
	private var stack :Array;

	public function StackFSM() {
		this.stack = new Array();
	}

	public function 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);
		}
	}

	public function getCurrentState() :Function {
		return stack.length > 0 ? stack[stack.length - 1] : null;
	}
}

تم استبدال أسلوب setState () بطريقتين جديدتين: pushState () و popState ()؛ يضيف pushState () حالة جديدة إلى الجزء العلوي من المكدس بينما يزيل popState () حالة في أعلى المكدس. يقوم كلا الطريقتين آليًا بنقل الجهاز إلى حالة جديدة ، نظرًا لأنهما يغيران الجزء العلوي من المكدس.

باستخدام FSM المستندة إلى مكدس

عند استخدام FSM المستندة إلى مكدس ، من المهم ملاحظة أن كل حالة مسؤولة عن popping نفسه من المكدس. عادةً ما تقوم الحالة بإزالة نفسها من الرصة عندما لا تكون هناك حاجة إليها ، كما لو أن الهجوم () نشط ولكن الهدف قد مات.

باستخدام مثال النملة ، هناك بعض التغييرات المطلوبة لتكييف التعليمة البرمجية لاستخدام FSM المستندة إلى مكدس. الآن هو حل مشكلة عدم معرفة الدولة بالانتقال إلى بسلاسة بفضل طبيعة ولايات ميكرونيزيا الموحدة القائمة على المكدس:

public class Ant {
	(...)
	public var brain :StackFSM;

	public function Ant(posX :Number, posY :Number) {
		(...)
		brain = new StackFSM();

		// Tell the brain to start looking for the leaf.
		brain.pushState(findLeaf);

		(...)
	}

	/**
	 * The "findLeaf" state.
	 * It makes the ant move towards the leaf.
	 */
	public function findLeaf() :void {
		// Move the ant towards the leaf.
		velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);

		if (distance(Game.instance.leaf, this) <= 10) {
			// The ant is extremelly close to the leaf, it's time
			// to go home.
			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) {
			// Mouse cursor is threatening us. Let's run away!
			// The "runAway" state is pushed on top of "findLeaf", which means
			// the "findLeaf" state will be active again when "runAway" ends.
			brain.pushState(runAway);
		}
	}

	/**
	 * The "goHome" state.
	 * It makes the ant move towards its home.
	 */
	public function goHome() :void {
		// Move the ant towards home
		velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
		
		if (distance(Game.instance.home, this) <= 10) {
			// The ant is home, let's find the leaf again.
			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) {
			// Mouse cursor is threatening us. Let's run away!
			// The "runAway" state is pushed on top of "goHome", which means
			// the "goHome" state will be active again when "runAway" ends.
			brain.pushState(runAway);
		}
	}
	
	/**
	 * The "runAway" state.
	 * It makes the ant run away from the mouse cursor.
	 */
	public function runAway() :void {
		// Move the ant away from the mouse cursor
		velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
		
		// Is the mouse cursor still close?
		if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
			// No, the mouse cursor has gone away. Let's go back to the previously
			// active state.
			brain.popState();
		}
	}
	(...)
}

والنتيجة هي نملة قادرة على الهروب من مؤشر الفأرة ، والانتقال إلى الحالة النشطة السابقة قبل التهديد:

الاستنتاج

الأجهزة ذات الحالة المحدودة مفيدة لتنفيذ منطق الذكاء الاصطناعي في الألعاب. يمكن تمثيلها بسهولة باستخدام الرسم البياني ، مما يسمح لمطوّر البرامج بمشاهدة الصورة الكبيرة وتغيير النتيجة النهائية وتحسينها.

إن تطبيق FSM باستخدام وظائف أو طرق لتمثيل الدول بسيط ولكنه قوي. يمكن تحقيق نتائج أكثر تعقيدًا باستخدام FSM قائم على الكدسة ، والذي يضمن تدفق التنفيذ بشكل سهل ومختصر دون التأثير سلبًا على الشفرة. لقد حان الوقت لجعل جميع أعدائك اللعبة أكثر ذكاء باستخدام FSM!