Поиск пути для "многоклеточных объектов"

← →
Warchief (2005-07-25 17:13) [0]

Как реализовать? Все материалы, которые я видел описывают только поиск пути для "одноклеточных" объектов по полю, с размерами клетки как у объекта. А как сделать для объектов которые занимают, напрмер, 2x2 клетки - непонятно ( Можно конечно для таких объектов хранить отдельное поле с размерами клетки под размер объекта и уже там искать, но этот способ некорректно работает в некоторых ситуациях (

← →
Wonderfulday © (2005-07-25 18:44) [1]

А если сделать клеткам свойство какой ширины персонаж на них может стоять? Ну типо для узкого прохода максимальная ширина персонажа 1 клетка, а для широкого - 5?

← →
XProger © (2005-07-25 20:22) [2]

А если дать каждому объекту сферу и выталкивать всё что в неё попадает при передвижении?

← →
Xeno © (2005-07-26 05:53) [3]

Ещё можно изменять размер ячейки сетки поля по размеру объекта,с пеносом на новую сетку расставленных на ней объектов и соответственно применить ,к примеру, стандартные алгоритмы поиска пути уже к изменнённому размеру поля.

← →
Zer0 © (2005-07-26 20:56) [4]

алгориим тот же что и для одноклеточного перса - только вот на каждом шаге придется проверять проходимость не одной а сразу нескольких клеток.

← →
A22 © (2005-07-26 21:15) [5]

по-моему, вариант, предложенный Wonderfulday будет лучше всех. Немного больше предварительной работы, разо разницы в реализации на 1 строчку (соотв. и в скорости потерь никаких)

← →
Warchief (2005-07-27 20:00) [6]

>А если сделать клеткам свойство какой ширины персонаж на них может >стоять? Ну типо для узкого прохода максимальная ширина персонажа 1 >клетка, а для широкого - 5?
Не понял o_O

← →
ViK © (2005-07-28 00:10) [7]

Обычный алгоритм поиска, только надо проверять сможет ли объект поместиться в заданной клетке. Особенно легко если объект квадратный с нечетным размером сторон (чтобы центр был).
Но если объект произвольной формы, то все сильно усложняется

← →
WonderfulDay © (2005-07-28 01:31) [8]

XProger, если персонаж 2*2, то какая будет сфера ;) ?
Xeno, тогда неточная карта получится, ответ тоже будет неточный.
2 WarChief
>Обычный алгоритм поиска, только надо проверять сможет ли объект поместиться в заданной клетке.
если свойство клетки "3", а персонаж имеет ширину квадрата >3, то он не может пройти, а если <=3, то может.

← →
WonderfulDay © (2005-07-28 01:32) [9]

Забыл слово "например" в последнем предложении :)

← →
Xeno © (2005-07-28 05:53) [10]

Не забудьте ещё про то что персонаж,при передвижении, может иметь возможность также перепрыгивать некоторые препятствия...:)

← →
XProger © (2005-07-28 09:50) [11]

WonderfulDay, будет радиуса 2 ;)

← →
Warchief (2005-07-28 12:59) [12]

> если свойство клетки "3", а персонаж имеет ширину квадрата >3, то он не может пройти, а если <=3, то может.
Ну, это понятно. Только вот как рассчитывать это свойство клеток?

← →
A22 © (2005-07-28 13:43) [13]

данное свойство клетки равно расстоянию от нее до ближайшего препятствия (непроходимой клетки).

>A22 © (28.07.05 13:43) [13]
>данное свойство клетки равно расстоянию от нее до ближайшего
>препятствия (непроходимой клетки).

Не согласен. Рассмотрим карты

XXXX
X00X
X00X
0000

и

XXX
X0X
000

0-проходимя клетка
X-не проходимая.

В обоих случая все нули в тупике будут иметь параметр = 1 , хотя в первом случае объект ширины 2 должен заползти :)

Да, все равно свойство клеток рассчитать легко... хз сейчас только думать лень :)

Какая максимальная сторона вписывающегося квадрата - такое и свойство, это ж из определения вытекает :)
Впиши сначала квадрат со стороной 1, потом 2, потом 3 и т.д. пока можно вписывать.

Для каждой клетки храним два параметра: расстояние до клетки по оси X (в положительном направлении!) и по оси Y (также в одном направлении).

Т.е. для карты
XXXX
X00X
X00X
XXXX

Получим:

(0, 0) (0, 0) (0, 0) (0, 0)
(0, 0) (2, 2) (1, 2) (0, 0)
(0, 0) (2, 1) (1, 1) (0, 0)
(0, 0) (0, 0) (0, 0) (0, 0)

Будем искать путь не для центра объекта (Т.к., уже выяснили, что для объекта размером 2х2 центр найти сложно :) ), а для крайней, точнее, левой-верхней точки!
Условие, возможности встать на клетку:
(Cell.FreeX >= Object.SizeX) and (Cell.FreeY >= Object.SizeY)
где SizeX - полная(!) ширина объекта, а не 1/2 её часть.

Неплохие идеи, даже можно забацать локальную оптимизацию - если обьект стоит на клетке X, а ему нужно топать до клетки Y и расстояние для ближайшей стены (значение FreeX и FreeY )больше, чем расстояние между Ч и Y то обьект должен переть по прямой и даже не задумываться о наличии препятствий.
Однако у такого метода есть один недостаток - он не real time, для создания такой карты проходимости нужно значительное время. (по прикидкам что-то вроде O( (Карта_По_X*Карта_По_Y)^2 ).

Ошибочка, можно O( Карта_По_X*Карта_По_Y*4 ) сделать.

Всем спасибо

Поиск пути для "многоклеточных объектов" Найти похожие ветки