Есть карта размером 600х300(180 000 клеток) Два типа местности суша и вода Нужно сделать алгоритм передвижения для наземных и морских юнитов по карте, учитывая скорость каждого юнита. Вся карта храниться в БД(MySQL) Чтобы не обращаться каждый раз к БД для проверки типа местности, сделал файл в котором 180 000 единиц(суша) и нолей(вода) PHP: $section = file_get_contents('includes/map_type.txt', FALSE, NULL, $loc_id - 1, 1); If($section == 0) { //Вода }else { //Суша } Напишите с чего начать, что подучить или сделайте за меня(не беспласплатно естественно) Карту можно посмотреть здесь: ondottr.ho.ua
Я бы карту перевел в вид массива cell[a,b]=N, a-col, b-row, N- число 0-255(т.к. направлений всего 8, то 255 = 11111111 - кругом суша, 0 = 00000000-кругом вода). И в зависимости от текущей ячейки знал бы возможный следующий ход. А хранить это в базе или в файле или в оперативной памяти держать, это другой вопрос
https://drive.google.com/file/d/1rVr38G78c6LkBqYIvQDH51BLFIaNMjpN/view?usp=drivesdk Как сделать так что бы войска двигались от точки А к точке Б по синему маршруту я знаю, а вот что бы по оптимальному маршруту без понятия
@Ondottr, определяешь расстояние между точкой начала А и следующей точкой В, потом от этой точки шагаешь еще один раз С, а потом сравниваешь если АС короче АВ+ВС, то точку В выкидываешь нафиг.
Вообще тут умение работать с БД ни при чем. Тут нужно иметь небольшое представление о теории графов и алгоритмах поиска кратчайшего пути. Кроме ячеек потребуется функция поиска соседних ячеек и дополнительный массив для поиска пути. А использовать можно алгоритм "заливка". Берется исходная ячейка (она помечается как пройденная). Загоняется все в цикл while(), из которого можно выйти либо по достижении требуемой ячейки, либо при невозможности добавить еще одну ячейку в список пройденных. Находятся соседние с пройденными ячейками. Они добавляются в массив и помечаются из какой ячейки в них осуществлен переход. За каждую итерацию цикла внутри этих ячеек делается шаг Когда в ячейке сделано необходимое количество шагов - она помечается как пройденная. Снова находятся соседние (но не все, а только те, на которых еще не ступала нога) ячейки и для каждой алгоритм повторяется. Когда будет достигнута требуемая ячейка - путь получится при движении в обратную сторону по меткам в каждой ячейке - откуда в нее попали. Вот тут еще есть алгоритмы. Если использовать ООП и паттерн "Компоновщик", то можно обойтись без массива.
Как сделать это все я разобрался) Большое спасибо за это @Maputo Есть еще один вопрос как лучше проверять тип местности, через файл или через массив Для меня разницы никакой, подходит два способа. Но может поиск по массиву происходит быстрее чем по файлу?? Ну или наоборот... пример массива: array(6) { [0]=>int(0) [1]=>int(1) [2]=>int(1) [3]=>int(0) [4]=>int(0) [5]=>int(1) } индекс как id клетки карты(180000 клеток) => тип местности(0 или 1) а в файле просто цифры 1/0
Хороший вопрос. Реализация ложится на ваши плечи. Данный пример я привел к тому, что ваша задача схожа на нахождение пути в лабиринте. И так как тема мне немного знакома привел вам демонстрацию примеров. Не забывайте, про большое количество алгоритмов для решения задачи. Выбор (написание своего) ложится на ваши плечи
А еще можно использовать прегенерированную карту оптимальных маршрутов от каждой клетки в каждую клетку, чтобы не париться с пасфайндингом в реальном времени. Карту как раз можно хранить в БД. В качестве ключей использовать стартовую и финальную клетку, составным индексом. Если подразумевается, что на протяжении всего маршрута от А до Б каждый шаг оптимален, то, как следствие, оптимальный маршрут от А до Б протяженностью N клеток включает в себя N оптимальных маршрутов. Подвозим деревья или бор и хранилище стало более оптимизированным.