Расчет прохождения.

[Abuhamed]

Вот есть две точки. А и Б. Как по квадратикам рассчитать траекторию от одного пункта к другому? Думал может сделать на js типо линейки и протянуть от одного пункта к другому и выделить те квадратики над которыми прошла линия. За самую оптимальную идею дам 200р
Вот два примера что я хочу
http://s1.my-app.co.cc/1.jpg
http://s1.my-app.co.cc/2.jpg

[ssdm]

У вас координаты точек на сетке есть ?
Рассчитать траекторию - это выделить квадратики между точками ?

[Виталий Желтяков]

Есть стандартные алгоритмы поиска пути. Не судьба ими воспользоваться?

[veniside]

если препятствий нет, то все слишком просто, чё там вобще думать )

[Abuhamed]

Да. Сетка поделена на координаты. Вот:
http://s1.my-app.co.cc/1.jpg
А и Б - это игроки. Мне нужно просто рассчитать координаты по которым будет лететь пуля. И потом сделать проверку на препятствия. И если на данных координатах нету препятствий нанести урон игроку.

[Виталий Желтяков]

Могу рассказать как это делается с примерами кодов на JS и PHP, но за это Вы пожертвуете ваши 200р форуму. Идёт?

[Abuhamed]

Конечно. Для такого форума 200р не жалко, и я обещал тому кто поможет 200р)

[Виталий Желтяков]

Ну значит поехали...

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

Дано: Объект А и Б находятся на игровом поле. В данном случае прямоугольная сетка. Объект А делает выстрел в объект Б.
Рисунок 1.

Требуется: определить дальность, т.е. возможность достижения цели, учитывая препятствия на пути.

Решение:
- Каждой ячейке задаём отдельный номер, как показано на рисунке 2. Почему каждой ячейке отдельный номер, а не две координаты? Потому что передавать меньше данных и перебирать ячейки легче.

- Создаём массив связей ячеек друг с другом. По принципу:

PHP код:

$map_cell['1']['1'] = 2; // Ячейка 1 связана с ячейкой 2
$map_cell['1']['2'] = 10;  // Как Я понял у Вас ходить можно и по диагонали
$map_cell['1']['3'] = 9;
$map_cell['2']['1'] = 1;
$map_cell['2']['2'] = 3;
$map_cell['2']['3'] = 11;
$map_cell['2']['4'] = 10;
$map_cell['2']['5'] = 9;
.... 


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

- Дополняем массив связи ячеек полем для расчёта пути. В нём мы отражаем какие объекты находятся на карте и в нём производим расчёт пути. Для пустых ячеек мы ставим номер 101, для препятствий - 102, для атакующего игрока (игрок А) - 100, для цели - 0 (игрок Б). Должен получиться массив типа такого:

PHP код:

$map_cell['1']['1'] = 2; 
$map_cell['1']['2'] = 10;  
$map_cell['1']['3'] = 9;
$map_cell['1']['path'] = 101; // Ячейка пустая
$map_cell['2']['1'] = 1;
$map_cell['2']['2'] = 3;
$map_cell['2']['3'] = 11;
$map_cell['2']['4'] = 10;
$map_cell['2']['5'] = 9;
$map_cell['2']['path'] = 101;
..
$map_cell['41']['path'] = 100; // Атакующий игрок А
... 


Должно получиться как на рисунке 3.
Это сделать достаточно просто, т.к. все данные у нас есть. Цель определяет игрок. Числа 100, 101, 102 - условные можете использовать любые больше числа ячеек.

- Далее применяем над полученным массивом магическую рекурсивную функцию:

PHP код:

//-------------------------- Процедура поиска пути ---------------------------//
function calcstep($ni, $map_cell) {
    if ($ni>40) return -1;
    // Перебираем все ячейки арены
    for ($i=1; $i<=56; ++$i) {
        // Если ячейка начала текущего поиска
        if ($map_cell[$i]['path']==$ni){
            // Перебираем связи найденой ячейки
            foreach ($map_cell[$i] as $j) {
                // Если мы нашли конечую ячейку, то возвращаем количество щагов до неё - 1 шаг
                if ($map_cell[$j]['path']==100) return $ni;
                // Если ячейка, по которой можно идти, то в path записываем удалённость от конца
                if ($map_cell[$j]['path']==101) $map_cell[$j]['path']=$ni+1;
            }
        }
    }
    // Если конечная ячейка не найдена, то повторяем процедуру для ячеек следующего шага
    return calcstep($ni+1, $map_cell);
}
//----------------------------------------------------------------------------//

$steps=calcstep(0, $map_cell); 


Это рекурсивная функция, производящая поиск пути от конечной точки к начальной и выдающая как результат количество шагов минус 1 шаг (-1 - цель недосягаема). Функция в процессе выполнения помечает ячейки вокруг конечной точки пути количеством шагов от неё, пока не будет найдена начальная. Входной параметр текущее количество рекурсий или шагов и массив.
Почему ищем от цели к началу? Дабы избежать глубокой рекурсии если цель недосягаема.
Какой будет результат на нашем примере?
Функция изменит параметр массива path на значения как на рисунке 4 и выдаст в качестве результата 6 (7-1 шагов). Ячейки функция перебирает в данном случае по часовой стрелке, поэтому остались необработанные ячейки с меткой 101.

Замечания:
- Данный алгоритм универсален. Его нужно без особых изменений применять и на сервере (php) и на клиенте (js) для расчёта возможности достижения цели.
- Хоть и в примере не было препятствий, он легко обрабатывает их находя путь в обход. Для этого приведённый алгоритм менять не надо.
- Как рассчитать, что препятствие загораживает нам путь? Очень легко...
Сначала мы производим расчёт шагов с препятствиями по данному алгоритму. Затем производим расчёт шагов без препятствий по данному алгоритму. Сравниваем результаты - если они различаются, то препятствие преграждает нам путь.
- Скорость алгоритма феноменальная (проверенно).

Вроде бы всё. Если есть вопросы, то задавайте.

[Abuhamed]

Виталий Желтяков
Мне нужно - получить координаты квадратиков по которым будет лететь пуля от А до Б.

$map_cell['1']['1'] = 2;
$map_cell['1']['2'] = 10;
$map_cell['1']['3'] = 9;

$map_cell[x][y] - так что ли?
Не понял откуда вы берете значения к примеру :

$map_cell['1']['2'] = 10;

Если $map_cell[x][y]= значение то тогда на (1;2) будет значение 9 а не 10. А для 10 координаты (2;2) x - 2, y - 2.

P.S. Дайте ссылку на тему с помощью для форума. Не могу найти.

[Виталий Желтяков]

Мне нужно - получить координаты квадратиков по которым будет лететь пуля от А до Б.

Точного ответа на этот вопрос нет, т.к. путей может быть несколько. Например, для вашего случая существует 125 решений.

$map_cell[x][y] - так что ли?

Читаем внимательно:

- Каждой ячейке задаём отдельный номер, как показано на рисунке 2. Почему каждой ячейке отдельный номер, а не две координаты? Потому что передавать меньше данных и перебирать ячейки легче.

Использовать две координаты не практично. Придётся использовать многочисленные двойные циклы.

Дайте ссылку на тему с помощью для форума. Не могу найти

Там указаны кошельки