Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Warchief © (2005-07-25 17:13:00)
Как реализовать? Все материалы, которые я видел описывают только поиск пути для "одноклеточных" объектов по полю, с размерами клетки как у объекта. А как сделать для объектов которые занимают, напрмер, 2x2 клетки - непонятно ( Можно конечно для таких объектов хранить отдельное поле с размерами клетки под размер объекта и уже там искать, но этот способ некорректно работает в некоторых ситуациях (

Warchief (2005-08-01 19:20:00) [1]
Всем спасибо

Zer0 (2005-08-01 18:51:00) [2]
Ошибочка, можно O( Карта_По_X*Карта_По_Y*4 ) сделать.

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

Goorus (2005-08-01 04:36:00) [4]
Для каждой клетки храним два параметра: расстояние до клетки по оси 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 её часть.

WonderfulDay (2005-07-31 00:05:00) [5]
Какая максимальная сторона вписывающегося квадрата - такое и свойство, это ж из определения вытекает :)
Впиши сначала квадрат со стороной 1, потом 2, потом 3 и т.д. пока можно вписывать.

Kobik (2005-07-28 20:12:00) [6]
>A22 © (28.07.05 13:43) [13]
>данное свойство клетки равно расстоянию от нее до ближайшего
>препятствия (непроходимой клетки).

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

XXXX
X00X
X00X
0000

и

XXX
X0X
000

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

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

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

A22 (2005-07-28 13:43:00) [7]
данное свойство клетки равно расстоянию от нее до ближайшего препятствия (непроходимой клетки).

Warchief (2005-07-28 12:59:00) [8]
> если свойство клетки "3", а персонаж имеет ширину квадрата >3, то он не может пройти, а если <=3, то может.
Ну, это понятно. Только вот как рассчитывать это свойство клеток?

XProger (2005-07-28 09:50:00) [9]
WonderfulDay, будет радиуса 2 ;)

Xeno (2005-07-28 05:53:00) [10]
Не забудьте ещё про то что персонаж,при передвижении, может иметь возможность также перепрыгивать некоторые препятствия...:)

WonderfulDay (2005-07-28 01:32:00) [11]
Забыл слово "например" в последнем предложении :)

WonderfulDay (2005-07-28 01:31:00) [12]
XProger, если персонаж 2*2, то какая будет сфера ;) ?
Xeno, тогда неточная карта получится, ответ тоже будет неточный.
2 WarChief
>Обычный алгоритм поиска, только надо проверять сможет ли объект поместиться в заданной клетке.
если свойство клетки "3", а персонаж имеет ширину квадрата >3, то он не может пройти, а если <=3, то может.

ViK (2005-07-28 00:10:00) [13]
Обычный алгоритм поиска, только надо проверять сможет ли объект поместиться в заданной клетке. Особенно легко если объект квадратный с нечетным размером сторон (чтобы центр был).
Но если объект произвольной формы, то все сильно усложняется

Warchief (2005-07-27 20:00:00) [14]
>А если сделать клеткам свойство какой ширины персонаж на них может >стоять? Ну типо для узкого прохода максимальная ширина персонажа 1 >клетка, а для широкого - 5?
Не понял o_O

A22 (2005-07-26 21:15:00) [15]
по-моему, вариант, предложенный Wonderfulday будет лучше всех. Немного больше предварительной работы, разо разницы в реализации на 1 строчку (соотв. и в скорости потерь никаких)

Zer0 (2005-07-26 20:56:00) [16]
алгориим тот же что и для одноклеточного перса - только вот на каждом шаге придется проверять проходимость не одной а сразу нескольких клеток.

Xeno (2005-07-26 05:53:00) [17]
Ещё можно изменять размер ячейки сетки поля по размеру объекта,с пеносом на новую сетку расставленных на ней объектов и соответственно применить ,к примеру, стандартные алгоритмы поиска пути уже к изменнённому размеру поля.

XProger (2005-07-25 20:22:00) [18]
А если дать каждому объекту сферу и выталкивать всё что в неё попадает при передвижении?

Wonderfulday (2005-07-25 18:44:00) [19]
А если сделать клеткам свойство какой ширины персонаж на них может стоять? Ну типо для узкого прохода максимальная ширина персонажа 1 клетка, а для широкого - 5?

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »