Page 1 of 2
Подскажите ходилку ?
Posted: 2006-09-24 14:35:50
by Destruction
Ни у кого случаем не завалялось ходилки, которая замечательно бегает, если известны тайлы, по которым можно ходить? (Хождение обычно происходит в не очень больших регионах - вот я и решил забить все тайлы в массиви, замечательно забиваются, а ходить пока не умеем..)
Posted: 2006-09-25 03:18:28
by Destruction
Ладно, прочитал про аглоритмы, много думал..
Понял, что это слишком круто для меня - т.к. не понял сути алгоритма, буду сидеть вникать
http://pmg.org.ru/ai/stout.htm#a_star - есть желающие воплотить ?
Posted: 2006-09-25 06:43:20
by Nmy
Destruction wrote:Ладно, прочитал про аглоритмы, много думал..
Понял, что это слишком круто для меня - т.к. не понял сути алгоритма, буду сидеть вникать
http://pmg.org.ru/ai/stout.htm#a_star - есть желающие воплотить ?
неа
Posted: 2006-09-25 08:53:03
by Edred
Destruction wrote:http://pmg.org.ru/ai/stout.htm#a_star
Ага, нашел все-таки эту статью? Молодец. Умная статья. Но я тебе скажу так: в самой УО алгоритм патчфинда, быустрее всего, по алгоритму Дийстры. Так что тоже не самый крутой.
Re: Подскажите ходилку ?
Posted: 2006-09-25 09:25:51
by DerMeister =)
Destruction wrote:Ни у кого случаем не завалялось ходилки, которая замечательно бегает, если известны тайлы, по которым можно ходить? (Хождение обычно происходит в не очень больших регионах - вот я и решил забить все тайлы в массиви, замечательно забиваются, а ходить пока не умеем..)
А чё, разве нельзя карту УО каким нить алгоритмом "оцифровать"? Или тебя прёт вручную?
Posted: 2006-09-25 10:33:59
by Destruction
Всмысле оцифровать ?
Проходимость тайлов можно дёргать через изю или через массив, мне важно точность - пути генеряться (каждый раз новые) и кэшируются.
Posted: 2006-09-25 15:05:55
by Nmy
наверно сканировать окружность нереально... или ? проверить несмогу- но идея в том что можно пробовать сканировать окружность и заранее придумавать пусть в пункт Б ... звучит сложно
Posted: 2006-09-25 19:31:00
by dmitrykit
klient derzhit v pamjati radius v 80 kletok.
Re: Подскажите ходилку ?
Posted: 2006-09-25 20:15:54
by Savage
Destruction wrote:Ни у кого случаем не завалялось ходилки, которая замечательно бегает, если известны тайлы, по которым можно ходить? (Хождение обычно происходит в не очень больших регионах - вот я и решил забить все тайлы в массиви, замечательно забиваются, а ходить пока не умеем..)
В сам кодить разучился чтоли?
Re: Подскажите ходилку ?
Posted: 2006-09-26 07:00:01
by Destruction
Savage wrote:Destruction wrote:Ни у кого случаем не завалялось ходилки, которая замечательно бегает, если известны тайлы, по которым можно ходить? (Хождение обычно происходит в не очень больших регионах - вот я и решил забить все тайлы в массиви, замечательно забиваются, а ходить пока не умеем..)
В сам кодить разучился чтоли?
Мне бы найти описание попроще, а то там - не для моего ума! -(
Posted: 2006-09-26 10:00:47
by dmitrykit
Gdeto v internete vstrechal ochenj krasivoje opisanije algaritma Astar8 na russkom jazyke, neponjat' prosto nevozmozno. po4ti realizoval, no zabrosil.
Posted: 2006-09-26 10:37:32
by Destruction
dmitrykit wrote:Gdeto v internete vstrechal ochenj krasivoje opisanije algaritma Astar8 na russkom jazyke, neponjat' prosto nevozmozno. po4ti realizoval, no zabrosil.
Похвастался ?
А терь дай ссылку.
Он будет искать оптимальный путь ? Не как Дейкстра или как его.. ? Меня вполне устраивает А*, но я хз.
Posted: 2006-09-26 15:16:43
by Nmy
как ты собираешся с помощю алгоритма подсчитать сколько пеньков или стен ему надо обойти ?
Posted: 2006-09-26 15:50:14
by Edred
NMY wrote:как ты собираешся с помощю алгоритма подсчитать сколько пеньков или стен ему надо обойти ?
А по ссылке что выше зайти лень? и почитать про алгоритмы?
Posted: 2006-09-26 16:04:39
by Nmy
этот алгоритм будет работать если он знает что иго ждёт в переди а это означает либо знает заранее либо сканировать окружность
Эдред незлись, я только спросил...
Posted: 2006-09-26 22:19:47
by Edred
NMY wrote:этот алгоритм будет работать если он знает что иго ждёт в переди а это означает либо знает заранее либо сканировать окружность
А теперь прочитай первые посты Деста...
Он уже отсканировал все тайлы в местности на проходимость. То есть есть матрица вида
Code: Select all
ООООХХХХОООО
ОООХХХХООООО
ООХХХХХХХХХОО
ООООООХООООО
ОООООООООООО
и необходимо "всего лишь" написать правильную ходилку по "О", оптимально обходя "Х".
Posted: 2006-09-27 15:26:49
by CONDOMchick
а зачем ходилка нужна такая?)
Posted: 2006-09-27 17:06:28
by Nmy
значит надо выучить алгоритм и написать формулу на языке инжектора... хмм... мож помогу
Posted: 2006-09-27 17:31:26
by Destruction
NMY wrote:значит надо выучить алгоритм и написать формулу на языке инжектора... хмм... мож помогу
Буду благодарен, я впринципе напряг одного человека - качает ультиму
CONDOMchick wrote:а зачем ходилка нужна такая?)
Как таковая ходилка не нужна - нужно лишь банально нарисовать маршрут. А дальше можно юзать вариант от Edred'а с мелким обходом препятствий.
Posted: 2006-09-27 17:52:27
by Nmy
можеш выложить как ты задёргал тайлы- как они выглядят и как с ними можнобудет оперировать....
если я понел правильно то Листинг 3 надо вплотить ввиде кода:
Листинг 3
приоритетная очередь Open
список Closed
ПоискАЗвездочка
s.g = 0 // s - стартовый узел
s.h = ЭвристическаяОценка( s )
s.f = s.g + s.h
s.родитель = null
добавить s в Open
пока очередь Open не пуста
извлечь n из Open // n - узел с наименьшей стоимость в Open
если n целевой узел
сконструировать путь
выйти с кодом "успешное завершение"
для каждого наследника n' узла n
newg = n.g + стоимость(n,n')
если n' в Open или Closed, и n'.g <= newg
пропустить n'
n'.родитель = n
n'.g = newg
n'.h = ЭвристическаяОценка( n' )
n'.f = n'.g + n'.h
если n' в Closed
удалить n' из Closed
если n' не в Open
положить n' в Open
положить n в Closed
выйти с кодом "путь не найден"
у меня идея не по алгоритму но такога:
если цель дальше видимости, тогда выставлять временный пункт Б
потов делаем прямую линию до пункта Б
если на линие есть тайл Х тогда иё изгебать пока она несодержыт тайл Х
небудет корочайщий но будет четкий путь
потом придумать как иго заставить изгибать корочаищий путь...
когда путь готов- начинаем шагать