توليد مستويات كهف عشوائي باستخدام الآلات الخلوية

() translation by (you can also view the original English article)

مولدات المحتوى الإجرائية هي أجزاء من التعليمات البرمجية المكتوبة في لعبتك والتي يمكنها إنشاء أجزاء جديدة من محتوى اللعبة في أي وقت - حتى عندما تكون اللعبة قيد التشغيل! حاول مطورو اللعبة أن يولدوا كل شيء من عالم ثلاثي الأبعاد إلى الموسيقى التصويرية الموسيقية. إضافة بعض جيل إلى اللعبة طريقة رائعة لسد العجز في قيمة إضافية: اللاعبين أحبها لأنها تحصل على محتوى جديدة وغير متوقعة ومثيرة في كل مرة كانت تلعب.

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

الوظائف ذات الصلة

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

مرحبا بكم في الكهوف!

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

إلقاء نظرة على العرض التوضيحي أدناه لمعرفة أنواع الإخراج عليك أن تكون قادراً على الحصول على. انقر فوق 'العالم الجديد' لإنتاج كهف جديد أن ننظر إلى. سنتحدث عن إعدادات مختلفة ما فعله في الوقت المناسب.

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

دعونا نبدأ بسؤال بسيط: ما هو على وجه الأرض هو إنسان خلوي ، على أي حال؟

الابتداء مع الخلايا

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

تم تطبيق أربعة قواعد لكل خلية في كل خطوة من المحاكاة:

إذا كان للخلية الحية أقل من جارين حيين ، فإنها تموت.
إذا كان للخلية الحية اثنين أو ثلاثة من الجيران الحيين ، فإنها تبقى حية
إذا كان للخلية الحية أكثر من ثلاثة جيران أحياء ، فإنها تموت.
إذا كان للخلية الميتة ثلاثة جيران حيين ، فإنها تصبح حية.

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

ونحن ذاهبون لتنفيذ نظام مشابه جداً للحياة، ولكن بدلاً من إنتاج أشكال وأنماط مضحك، هو الذهاب إلى إنشاء نظم الكهف مذهلة للألعاب.

تنفيذ إنسان الخلوية

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

في ما يلي نبدأ بتهيئة شبكتنا من الخلايا:

1	boolean[][] cellmap = new boolean[width][height];

تلميح: لاحظ أن الفهرس الأول هو اﻻحداثي السيني للمصفوفة، والمؤشر الثاني هو اﻻحداثي ص. وهذا يجعل الوصول إلى الصفيف أكثر طبيعية في التعليمات البرمجية.

في معظم لغات البرمجة ، سيتم تهيئة هذا المصفوفة مع ضبط جميع قيمها على false. وهذا ما يرام بالنسبة لنا! إذا كان فهرس الصفيف (س ، ص) غير صحيح ، فسنقول إن الخلية فارغة ؛ إذا كان صحيحًا ، سيكون هذا البلاط صخرة صلبة.

كل واحد من هذه المواقف الصفيف يمثل واحداً من 'الخلايا' في شبكة الهاتف الخلوي لدينا. الآن نحن بحاجة إلى إعداد شبكة لدينا حتى نتمكن من البدء في بناء الكهوف لدينا.

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

float chanceToStartAlive = 0.45f;

public boolean[][] initialiseMap(boolean[][] map){
  for(int x=0; x<width; x++){
		for(int y=0; y<height; y++){
			if(random() < chanceToStartAlive){
				map[x][y] = true;
			}
		}
	}
	return map;
}

Our random cave before any cellular automaton simulation steps — لدينا كهف عشوائي قبل أي خطوات محاكاة automaton الخلوية.

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

تنمو لدينا الكهوف

تذكر القواعد التي تحكم الخلايا في لعبة الحياة؟ في كل مرة تمر فيها المحاكاة خطوة واحدة ، تتحقق كل خلية من قواعد الحياة وترى ما إذا كانت ستتغير إلى أن تكون حية أم ميتة. سنستخدم نفس الفكرة بالضبط لبناء كهوفنا - سنقوم بكتابة وظيفة الآن تعمل على كل خلية في الشبكة ، وتطبق بعض القواعد الأساسية لتقرير ما إذا كانت تعيش أو تموت.

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

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

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

عفوا! هذا ليس ما نريده على الإطلاق. لذلك في كل مرة نقوم فيها بحساب قيمة خلية جديدة ، بدلاً من وضعها في الخريطة القديمة ، سنكتبها إلى خريطة جديدة.

لنبدأ بكتابة الدالة doSimulationStep () ، ثم:

1	public doSimulationStep(boolean[][] oldMap){
2	boolean[][] newMap = new boolean[width][height];
3	//...

نريد أن تنظر كل خلية في الشبكة بدورها، وكيف العديد من جيرانها بحي وميت. يعد عد جيرانك في مصفوفة واحدة من تلك الأجزاء المملّة من الكود سيكون عليك كتابة مليون مرة. وهنا تنفيذ سريع لها في وظيفة لقد دعا countAliveNeighbours ():

//Returns the number of cells in a ring around (x,y) that are alive.
public countAliveNeighbours(boolean[][] map, int x, int y){
	int count = 0;
	for(int i=-1; i<2; i++){
		for(int j=-1; j<2; j++){
			int neighbour_x = x+i;
			int neighbour_y = y+j;
			//If we're looking at the middle point
			if(i == 0 && j == 0){
				//Do nothing, we don't want to add ourselves in!
			}
			//In case the index we're looking at it off the edge of the map
			else if(neighbour_x < 0 || neighbour_y < 0 || neighbour_x >= map.length || neighbour_y >= map[0].length){
				count = count + 1;
			}
			//Otherwise, a normal check of the neighbour
			else if(map[neighour_x][neighbour_y]){
				count = count + 1;
			}
		}
	}
}

هناك شيئان حول هذه الوظيفة:

أولاً ، الحلقات غريبة قليلاً إذا لم تقم بشيء كهذا من قبل. الفكرة هي أننا نريد أن ننظر إلى كافة الخلايا التي يتم حول النقطة (x, y). إذا نظرت إلى الرسم التوضيحي أدناه ، يمكنك أن ترى كيف أن المؤشرات التي نريدها هي واحدة أقل ، مساوية ، وأكثر من فهرس أصلي واحد. لدينا اثنين من الحلقات يعطينا ذلك فقط ، بدءا من -1 ، والتكرار من خلال +1. ثم نضيف ذلك إلى الفهرس الأصلي داخل الحلقة للعثور على كل جارة.

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

الآن ، دعنا نعود إلى وظيفة doSimulationStep () الخاصة بنا ونضيف بعض الشفرات الأخرى:

public boolean[][] doSimulationStep(boolean[][] oldMap){
	boolean[][] newMap = new boolean[width][height];
	//Loop over each row and column of the map
	for(int x=0; x<oldMap.length; x++){
		for(int y=0; y<oldMap[0].length; y++){
			int nbs = countAliveNeighbours(oldMap, x, y);
			//The new value is based on our simulation rules
			//First, if a cell is alive but has too few neighbours, kill it.
			if(oldMap[x][y]){
				if(nbs < deathLimit){
 					newMap[x][y] = false;
  				}
 				else{
 					newMap[x][y] = true;
  				}
  			} //Otherwise, if the cell is dead now, check if it has the right number of neighbours to be 'born'
  			else{
  				if(nbs > birthLimit){
					newMap[x][y] = true;
				}
				else{
					newMap[x][y] = false;
				}
			}
		}
	}
	return newMap;
}

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

كل ما تبقى في النهاية لمسة نهائية للعودة تحديث خريطة. تمثل هذه الوظيفة خطوة واحدة لقواعدنا التلقائية للخلية - والخطوة التالية هي فهم ما يحدث عندما نطبقه مرة واحدة أو مرتين أو أكثر على خارطة البداية الأولية.

التغيير والتبديل وضبط

دعونا ننظر إلى ما يشبه رمز الجيل الرئيسي الآن ، وذلك باستخدام الرمز الذي كتبناه حتى الآن.

public boolean[][] generateMap(){
	//Create a new map
	boolean[][] cellmap = new boolean[width][height];
	//Set up the map with random values
	cellmap = initialiseMap(cellmap);
	//And now run the simulation for a set number of steps
	for(int i=0; i<numberOfSteps; i++){
		cellmap = doSimulationStep(cellmap);
	}
}

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

حتى الآن لقد وضعنا هذه المتغيرات:

تحدد chanceToStartAlive مدى كثافة الشبكة الأولية بالخلايا الحية.
ستارفاتيونليميت هي الحد الأدنى للجار الذي يبدأ خلايا الموت.
أوفيربوبليميت هو الحد الأعلى الجار الذي يبدأ خلايا الموت.
رقم الولادة هو عدد الجيران التي تتسبب في أن تصبح الخلية الميتة حية.
numberOfSteps هو عدد المرات التي نؤدي فيها خطوة المحاكاة.

Our random cave after two cellular automaton simulation steps — لدينا كهف عشوائي بعد خطوتين محاكاة إنسان الخلوية.

يمكنك كمان مع هذه المتغيرات في العرض في الجزء العلوي من الصفحة. ستغير كل قيمة العرض التوضيحي بشكل كبير ، لذا يمكنك اللعب حوله ومعرفة ما يناسب.

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

Our random cave after six cellular automaton simulation steps — لدينا كهف عشوائي بعد ست خطوات محاكاة إنسان الخلوية.

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

استمرارا له

إذا كنت يحدق في المولدات الخاصة بك الكهف جميلة، وأتساءل ماذا يمكن أن تفعل معها، إليك بضعة أفكار التعيين 'الائتمان إضافية':

استخدام تعبئة الفيضان لفحص الجودة

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

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

وضع الكنز السريع والبسيط

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

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

public void placeTreasure(boolean[][] world){
	//How hidden does a spot need to be for treasure?
	//I find 5 or 6 is good. 6 for very rare treasure.
	int treasureHiddenLimit = 5;
	for (int x=0; x < worldWidth; x++){
		for (int y=0; y < worldHeight; y++){
 			if(!world[x][y]){
 				int nbs = countAliveNeighbours(world, x, y);
  				if(nbs >= treasureHiddenLimit){
					placeTreasure(x, y);
				}
			}
		}
	}
}

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

الاستنتاجات ومزيد من القراءة

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

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

إذا كنت تريد المزيد من المعلومات حول إنشاء المحتوى الإجرائي أو Cellular Automata ، فإليك إصدارًا رائعًا عبر الإنترنت من Game Of Life (على الرغم من أنني أوصي بشدة بكتابة "Conway's Game Of Life" في Google). قد ترغب أيضا في Wolfram Tones ، تجربة ساحرة في استخدام الأوتوماتية الخلوية لتوليد الموسيقى!