Передвижение игрового персонажа по лабиринту (часть 1)

в 8:17, , рубрики: game development, RTS, Алгоритмы, искусственный интеллект, Песочница, метки: , , ,

Здравствуйте. Меня зовут Дархан и я закончил 3 курс в Алматинском Университете Энергетики и Связи по специальности «Информационные Системы». И где-то месяц назад мой друг и одногруппник сказал мне что видел одну вакансию на hh.kz где одна IT компания приглашает юниоров. Но чтобы попасть туда надо решить некоторые задачи. Одна из задач была такая

У вас есть матрица NxN причем N>10. Матрица представляет собой лабиринт. Проход закодирован null или 0, стена 1. Реализуйте алгоритм выхода из точки А в точку B.

И это задача мне показалось очень интересной. Я начал искать что-то подобное в сети и наткнулся на вот эти посты раз два три где описывается как реализовывается движение персонажа по карте. Советую почитать. Но я решил пойти дальше и дать танку интеллект. Мой танк старается делать как можно меньше шагов для достижения место назначения.
Передвижение игрового персонажа по лабиринту (часть 1)

Логику будем реализовывать на JavaScript а рисование на HTML+CSS. Код состоит из двух основных частей. Первая отвечает за карту, а вторая за танки. Я не русский и не живу в России, поэтому если предложения плохо составлены извините меня.

Ну, поехали

У нас будет три файла: index.html, style.css, main.js. На странице есть два блока: левая — навигация и правая — карта. Все действия происходят внутри тега <div id=’map’ > <div>.

Код карты

Перед тем как приступить сделаем некоторые функции более короткими:

function get(d){  // возвращает HTML элемент по id или сам объект
if(typeof d == 'string')	return document.getElementById(d); 
else return d;
}
function cssl(d, par, val){ // устанавливает CSS стиль 
eval("get(" + d + ").style." + par + " = '" + val + "';");
 } 
function remove(d) { // удаляет заданный HTML тег 
 get(d).parentNode.removeChild(get(d)); 
}

Карта

Так как карта у нас будет одна на всех мы не будем создавать класс для него а просто создадим сам объект с свойствами и методами. Создадим объект карты map:

var map = {
	cell: [[0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0],[0,1,0,1,1,0,1,0,0,0,1,0,1,0,1,1,0,0,1,0,0,1,0],[0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0],[0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0,1,0,1,1,0],[0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0],[0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,1,1,1],[0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0],[0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0],[0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0],[0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0],[0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0],[0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0],[0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,0,1,0,0,1,0],[0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0],[0,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1],[0,1,0,1,1,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1],[0,1,0,0,1,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0],[0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0],[0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0]], // это значения плиток карты. 0 – пусто, 1 – стена 

	size: 23, // Размер карты в клетках,

	curY: false, // это номер клетки по оси Y, При клике на карте вычисляется координаты мыши на карте и номер клетки по оси Y. Нужен для обращения к массиву map.cell  

	curX: false, // такой же но по оси X

	changing: true, // если это свойство равно true то можно изменять карту  вставляя или удаляя стены

	unitsCol: 0, // количесство элементов на карте (стены и танки)   

	selectedUnit: 0, // id выделенного элемента. Можно по нему  указывать танкам новые цели

	units: new Array(), // массив который хранит все элементы карты (стены и карты)

	newUnit: false, // если это свойство равно true то при клике на пустое место вставляется новый танк

	cellSize: 30, // размер клетки в пикселях. Можно было бы задать в ручную, но я хочу в будущем сделать размеры по больше

Метод init() – рисует на карте стены опираясь на значения массива map.cell, 0 — пусто, 1 – стена. Метод проходит в цикле по массиву map.cell, если значение клетки равно 1 то устанавливает значения свойств map.curY, map.curX на координаты этой клетки и вызывает метод map.createWall() – который рисует на странице стену.

	init: function(){ // метод рисует на карте стены опираясь на значения массива map.cell, 0 -  пусто, 1 - стена
		remove('startButton'); // удаляем кнопку запуска игры
		cssl('saveMap', 'display', 'block'); // показывает кнопки управления
		for(var i=0; i< this.size; i++) // по оси Y
		{
			for(var j = 0; j < this.size; j++) // по оси X
			{
				if(map.cell[i][j] == 1) // если это стена
				{
					map.curX = j; // захват номера клетки по оси Х
					map.curY = i; // захват номера клетки по оси У
					map.createWall(); // рисуем стену
				}
			}
		}		
	},

Метод map.createWall – рисует стену на странице просто вставляя тег с нужным margin и id (который формируется так: wall_номер_стены в массиве map.units). После вставки стены он ещё и увеличивает значение количества элементов карты map.unitsCol. В будущем хочу сделать так чтобы вид стены зависел от его соседей. Например, если это стена угловая то она должна рисовать угловую стену а не простую

createWall: function(){ 
		map.unitsCol++; // увеличиваем количество элементов карты
		map.cell[map.curY][map.curX] = 1; // указываем в массиве карты что здесь теперь стена. Это строка бесполезна при вызове через <b> map.init() </b>. Но нужно при вставке новой стены самим пользователем. 
		get('map').innerHTML+= "<div class='walls' id='wall_" + map.unitsCol + "' onclick='map.deleteWall(" + map.unitsCol + ", " + map.curY + ", " + map.curX + ");'><img src='image/wall.png' /> </div>"; // вставка HTML тега с картинкой стены
		
		cssl(('wall_' + map.unitsCol), 'margin', (map.curY * map.cellSize) + 'px ' + (map.curX * map.cellSize) + 'px'); // установка позиции		
	},

Если вы заметили, в тег мы добавили обработчик onclick = ‘map.deleteWall()’. Т.е. при редактировании карты клик по стене удаляет эту стену из карты.
Метод Map.deleteWall() – удаляет стену на карте. Он принимает три аргумента:

id – id элемента в массиве map.units
y – номер клетки по оси Y
x – номер клетки по оси X

После удаления метод останавливает всплытие события клика чтобы клик не сработал на карте.

	deleteWall: function(id, y, x){ 
		if(map.changing) // если редактирование карты включено
		{
			map.cell[y][x] = 0; // ставим пусто в массиве карты
			remove('wall_' + id); // удаляем тег
			event.stopPropagation(); // останавливаем всплытие
		}
	},

Метод map.setCurrentCell() – при клике на карте преобразует координаты мыши в пикселях на клеточные. Т.е. устанавливает свойство map.curY и map.curX. При клике на стену или танк объект Event ссылается на этот тег а не на тег карты. Я не профи в JavaScript, поэтому не смог решить эту задачу более компактно. Да и не было желания гуглить так как я был занят идеей реализации ИИ танка.

	setCurrenCell: function(e){
		if(e.target == get('map')) // если кликнули на пустое место, т.е. на саму карту а не на его дочерные элементы
		{
			map.curX = ((e.offsetX - (e.offsetX % map.cellSize))/map.cellSize); // преобразуем координаты в пикселях на клеточные по оси Х
			map.curY = ((e.offsetY - (e.offsetY % map.cellSize))/map.cellSize);  // преобразуем координаты в пикселях на клеточные по оси Y
		}
		else // если кликнули дочерным элементам тега (тег стен и танков)
		{
			var x = e.target.parentNode.offsetLeft + e.offsetX; 
			var y = e.target.parentNode.offsetTop + e.offsetY; // ссылаемся на родитель картинки, потому что теги у нас лежат так <div><img/></div>. Т.е. кликнутые элемент тег <img/>

			map.curX = ((x - (x % map.cellSize))/map.cellSize); //  преобразуем координаты в пикселях на клеточные по оси Х
			map.curY = ((y - (y % map.cellSize))/map.cellSize); // преобразуем координаты в пикселях на клеточные по оси Y
		}
	},

Метод map.changeMap() – устанавливает свойство map.changing в true что означает карта изменяется. Т.е. при клике на карте вставляется или удаляется стена

	changeMap: function(){
		map.changing = true;
		cssl('saveMap', 'display', 'block');
		cssl('changeMap', 'display', 'none');
	},

После того как изменения внесены нужно сохранить карту. За это отвечает метод – map.saveMap

	saveMap: function(){
		map.changing = false; // останавливаем редактирование
		cssl('saveMap', 'display', 'none'); // кнопка навигации
		cssl('changeMap', 'display', 'block'); //  // кнопка навигации
	},

Передвижение игрового персонажа по лабиринту (часть 1)

Вот мы подошли к главному методу роутеру – map.run(). Этот метод срабатывает при клике на область карты.
Если на данный момент карта редактируется (map.changing = true) и кликнутая клетка пуста, то запускает метод вставки новой стены. Если кликнута стена этот метод не сработает, потому что метод map.deleteWall() останавливает всплытие события клика на родительский тег. В коде мы все ровно проверяем пуста ли кликнутая клетка, так как клик может быть сделан по танку.
А если редактирование карты отключена, то переходим к танкам. С танками у нас могут быть три случая:

  • нажата кнопка и никакой танк на карте не выбран
  • танк выбран
  • ничего не выбрано и сделан простой клик

Разберем первый случай. Ничего на карте не выбрано и нажата кнопка «Добавить танк». Значит нам нужно создать новый элемент карты, зарегистрировать его по адресу map.curY, map.curX в массиве карты map.cell, нарисовать его на странице вызвав метод map.setTank();. Значения массива map.cell могут содержать 0-пусто, 1-стена или id танка в глобальном массиве карты для хранения списка элементов карты map.units.
Передвижение игрового персонажа по лабиринту (часть 1)

Во втором случае мы должны установить танку место куда он должен пойти вызвав метод танка map.units[map.selectedUnit].setDestination();. Здесь мы ссылаемся на танк через глобальный массив map.units.
Передвижение игрового персонажа по лабиринту (часть 1)

А в третьем случае ничего не делаем.
А теперь посмотрим на всё это в коде:

	run: function(e){
		map.setCurrenCell(event); // устанавливаем фокус на это клетку
		if(map.changing == true) // если карта изменяется
		{
			if(map.cell[map.curY][map.curX] == 0) // проверяем пуста ли клетка
			{
				map.createWall(); // если да, то вставляем новую стену
			}
		}
		else // иначе переходим к методом связанные с танками
		{
			if(map.selectedUnit == 0 && map.newUnit == true ) // если нажата кнопка «Добавить танк» и  ничего на карте не выбрано
			{
				map.setTank(); // то создаём новый танк
			}
			else if(map.selectedUnit > 1) // а если танк уже создан и ему нужно указать место прибытия
			{				
				if(map.cell[map.curY][map.curX] == 0) // если клетка пуста
				{
					map.units[map.selectedUnit].setDestination(); // устанавливаем место прибытия
					map.newUnit = false; // и говорим карте что танк уже установлен
				}	
			}
		}
	},

Последний метод карты это выше упомянутый метод – map.setTank(). Здесь всё просто, увеличиваем количество элементов карты на один, создаем новый танк с помощью функции конструктора newTank() и устанавливаем фокус карты на этот танк.

	
	setTank: function(){
		if(map.cell[map.curY][map.curX] == 0) // если клетка пуста
		{
			map.unitsCol++; // увеличиваем количество элементов карты на один
			map.units[map.unitsCol] = new newTank(map.unitsCol); // создаем новый танк
			map.selectedUnit = map.unitsCol; // устанавливаем фокус карты на этот танк
		}
	}	

} 

Вроде все про карту. Пост получился не такой короткий, но это только малая часть приложения. В следующей статье я разберу ИИ танка и там очень много кода, поэтому для него нужен отдельный пост.

Как все работает можно посмотреть здесь. Продолжение будет через несколько дней. Спасибо за внимание.

Автор: docxplusgmoon

Источник

Поделиться

* - обязательные к заполнению поля