Доброе время суток, господа, дамы и товарищи!

Презентую Вам на суд свою новую разработку: алгоритм поиска пути DExeik, воплощенный тэк-скээть в бетаверсию подключаемой к Блицу ДЛЛ-библиотеки.

Тестите, рецензируйте и юзайте на здоров!
Сообщите мне, пожалуйста, о всех багах, глюках, крешах и катастрофах, возникших при работе с библиотекой, а также о своих идеях по их- библиотеки или даже самого алгоритма- улучшению. Буду просто дико рад такой поддержке.

____________
Архив удален. Обновления см. ниже.

Учитесь как надо делать демки-тесты. Всё работает.
Только вот у меня не всегда удалялись меши-вейпоинты маршрута бота

Неплохо :super:

А можно в библиотеку добавить еще упрощенный алгоритм передвижения в четырех направлениях (исключить передвижение по диагоналям)?

Нашел один глюк: при попытке направить игрока в мертвую зону несколько раз, игрок бежит к неизчезнувшим кубикам прямо через стены и идет по ранее пройденному пути, который не исчез.

Done!

Fixed!


Спасибо за помощь!
Обновление качать там же.

Работает :) . Респект за библиотеку! :super:

А можно эту библиотеку потом в Bombers3D использовать?...


Вобщем есть пожелание: заменить функции ExeikSetMap%(X%,Z%,Value%) и ExeikFillMapBank%(Bank*) на ExeikSetMapBank%(Bank*). В этом случае по мойму не будет ограничений в размере карты... хотя незнаю (честно пока незнаю как с банками работать не в блитце...) Если не трудно, то в двух словах объясни как он в памяти организован (банк)... буду очень признателен :)

прикольно :)
алгоритм мне вроде как понятен ;) но иногда его колбасит

Странный баг: игрок останавливается в тунеле недойдя до конца пути... да... в примере все еще остаются вейпоинты при направлении на новое место...

Можно конечно! Для чего ж я ёё и выкладывал! :)
Только лицензии на Пурик у меня нет (пока нет), так что если решишь продать игру- как-то ночью могут приехать на черном "воронке".
Впрочем, возможно ли отличить либу на платном Пурике от либы на бесплатном ДевС- доподлинно неизвестно.

Нет, ограничение по размерам от этих ф-й не зависит: они сделаны просто как два различных независимых метода заполнения карты- один удобный и универсальный, другой быстрый. А вообще, ограничение по размерам крайне условно: я использую переменные и массивы word (так называется int в Пурике- от -32767 до +32767), а не, скажем, long, что экономит память вполовину, но и алгоритму не дает работать с большим количеством клеток.
Но если нужно, я могу изменить десяток строк и максимальный размер карты выростет до... щас... э-э-э... 46000х46000. Беда одна: для обработки понадобится что-то около 16Гб оперативной памяти :))

Ну, это очень глупый алгоритм. Колбасня- это его верный друх и жыздненный спутнег. Но если поставить высококачественный режим поиска- 1 или даже 0 (впрочем, это излишний перегиб), колбасить будет поменьше...
Цена ДЕкзейка (да и Екзейка тоже) ведь в его скорости: 8мс на карте 128х128- ИМХО неплохо. Помню как несколько лет назад мы вострогались либой на ассемблере, которая считала карту 32х32 за 2мс. :)

:( Ёй-ёй. Не должно так быть. И бага у меня не воспроизовдится. Расскажи, пожалуйста, поподробнее... Где, как, в каком режиме поиска, на какой карте?.. И как, ёё воспроизвести.

Так они не остаются: они просто не перемещаются. Это ведь просто декорация для наглядности: создаваемый вначале примера массив из моделей кубиков, где количество элементов равно максимальной указанной пользователем длинне курса. Когда курс проложен, кубики расставляются вдоль пути. В результате, в случае, если проложенный функцией курс оказывается короче максимального указанного- ну добрались уже до точки, некуда дальше прокладывать- часть "лишних" кубиков просто остается на старых местах. К процессу поиска и прохождения пути модельки вейпоинтов отношения не имеют.

а как запустить-то :@

2 PAX: Бага найдена. Полностью рабочую библиотеку выложу на днях.

2 ZanoZa: Просто помести "DExeik.decls" в папку "Userlibs" Блица и запускай "Sample.bb".

P.S. Сори, что не выкладываю патч сегодня: поймал какого-то виря. Температура ядра мозга поднялась с 36.6 до каких-то невиданных высот... Сейчас ищу антивирус и кряк к нему. Как только верну себе умение ориентироваться в пространсве и связно мыслить- закончу работу над либой. :)
В любом случае- пишите. И спасибо за помошь в доводке.

А можно не заполняя массив из банка просто пользоваться этим банком? просто если на карте будет одновременно 10-20 врагов, то боюсь каждый раз заполнять массиб будет проблематично... можно ли непосредственно с банком из блитца работать?


А мой проект бесплатный ;) я же от него исходники выложил :)

Да забыл про баг... в предидущем примере по умолчанию карта Map2.bmp, в первом длинном тунеле останавливается... на 1-ускоренном цикле и 2- упрощенном по четырем направлениям цикле. На 0-полном цикле все нормально...

Вот еще одно пожелание:

Можно усовершенствовать алгоритм (чтобы включалось опционально) так, чтобы "игрок" обходил углы под прямым углом.

Примерно так:

Как я понимаю это алтернатива A*, так?

Наконец родимая Булка снова в строю!

Итак, примеры, которые я не успел запостить раньше.

В прикрепленно файле DExeik.rar - стандартный сампл с колобком и лабиринтом. Функция обновлена и работает лучше (см. intro.txt)

Архив Tanks.rar содержит маленькую игрушку-пример, описывающую нелегкие будни танкистов и являющую собой примитивнейший пример практического применения ДЕкзейка.

По идее проблеммы возникать не должны. Возможно пример tanks.rar поможет.

К сожалению, только в режиме поиска по 4 направлениям. :(

Ни в коей мере не собирался создавать "убийцу Астара", или "конкурента ВолновогоАлгоритма" ! У ДЕкзейка своя специфика, своя область применения и свои недостатки. ИМО, он просто немного дополняет полупустую нишу алгоритмов, которые могут производить поиск пути на больших картах с регулярной сеткой относительно быстро и относительно правильно.

Аууу! Люди! :)
За два дня так никто ни разу не скачал, и даже не зашел!

я скачал.
пригодицца :)
Родина тебя не забудет !

DExeik.decls - забыл вложить, со старым не работает

Просто все на сессии ;-)

Fixed!:)
|
V

А танчики прикольные, а самое главное рвботают!!! Спасибо за пример, буду после сессии делать ИИ для Bombers3D :)

Если найду баги, сообщу. ;-)

Re: Dexeik
 

Есть идея как увеличить максимальные размеры карты.

Пусть карта будет произвольного размера, но когда DExeik получает координаты точек, между которыми надо найти путь, он автоматически будет выбирать верхние и нижние границы области поиска в пределах всей области... например есть карта 300х300, а надо найти путь из точки 1х1 в точку 300х300, пусть например DExeik проложит путь сначала в области (1,1; 150,150) а потом дальше...

Надеюсь идею понятно изложил... конечно для этого придется придумать интелектуальеую систему выбора границ области поиска, так чтобы она уместилась в область с размерами 181х181, но и можно было бы найти путь... например чтобы найти путь из точки (150,150), в точку (180,180) границы выбирались примерно такие: (60,60; 240,240) или что-то подобное...

Извини если отнял у тебя время :)

Re: Dexeik
 

Не катит, имхо.
А если стартовая точка в огромном зале ( утрированый вариант) - куда прокладывать и где гарантия, что не придёться прокладывать обратно?
Т.е. нельзя быть уверенным что выбранный маршрут правильный, не рассмотрев всю карту.
Или я тебя не понял.

Re: Dexeik
 

Гарантии конечно нет, но зато будет возможность использования Dexeik'а на неогриниченной размерами карте, конечно и так можно... но перезаполнять каждый раз карту не катит.
Можно просто добавить возможность самостоятельного задания границ поиска, чтобы неверный поиск пути был на совести пользователя а не разработчика библиотеки ;)

Re: Dexeik
 

В архиве нет .decls файла.

Re: Dexeik
 

Re: Dexeik
 

Diplomat, а эту библиотеку можно использовать с террайном, если да, то не мог бы сделать проооостнеький пример, а дальше если че я сам разберусь

Re: Dexeik
 

Если подразумевается, что террайн- это просто карта с разностями высот и проходимыми/непроходимыми зонами- то можно.
Реализуется это точно так же, как и без террайна, поскольку ось Y для DExeik-а не играет ни малейшей роли.

Re: Dexeik
 

Diplomat, подскажи пожалуйста как изменить твой код с танками, чтобы они ездили по террайну, у меня чето не получается.

Re: Dexeik
 

Да что ж такое-то? При чём здесь вообще ДЕкзейк к террайнам?

Танкам назачаешь коллизию с террайном, и в цикле ставишь иммитацию силы тяжести: ТранслейтЁнтити вниз. Если хочешь- можешь АлайнТоВектор-ить их к террайну, чтоб они кренились на изгибах местности. Всё!

И это самое... Предупреждаю: вопросы класса "А как назначить коллизию?", "А у меня не коллизится!", "А что такое Алайн?"- будут расценены как оффтоп и снесены из темы. Если хочешь- можешь создавать вопросы в соответствующем разделе.
Удачи!

Re: Dexeik
 

да просто надо создать тему "Вопросы по Dexeik"

Re: Dexeik
 

Re: Dexeik
 

ну я не про этот, а в общем

Re: Dexeik
 

Автору огромный респект, т.к. избавил большое кол-во людей от нелегкой работы, я б ему орден Красной Звезды дал бы!:)

Re: Dexeik
 

Дикзейк рулит!!!

Re: Dexeik
 

Прошу простить мою тупость, но я не нашёл самого файла с исходником, который можно скачать

Re: Dexeik
 

Radomir
http://www.boolean.name/showpost.php...2&postcount=14
библиотека распространяется без исходного кода

Re: Dexeik
 

2 jimon: Опередил!
А ты про деклс забыл, как он без него пример запустит.
http://www.boolean.name/attachment.p...4&d=1150092985

Re: Dexeik
 

Спасибо

Re: Dexeik
 

у меня вопрос.
можете объяснить принцип алгоритма ПП по вейпоинтам.. а то вдруг я его не так понимаю..
я сейчас сам его пишу.

Re: Dexeik
 

Либо я не так понял либо алгоритм косячный. Вот скрин Вложение 3652. Ниже прелагаю схему по каторги все происходит. Красный это стены, зеленый начало пути, синий конец пути, розовым путь который строит алгоритм, серым путь который должен быть (просьба не предератся к точности серого пути, так как рисовал на скорую руку и не высчитывал детали) вот сама Вложение 3653. Всем кто желает проверить вот вам файл с картой Вложение 3654

Re: Dexeik
 

WaReZ_MEN: Нет, ты всё понял правильно, и это действительно "алгоритм косячный".
Как было неоднократно упомянуто ранее- DExeik далеко не всегда ищет кратчайшие пути. Эта его особенность является не багом, но платой за среднестатистически высокую производительность. В крайних версиях ситуация несколько улучшилась, но картина в целом осталась неизменной.

Re: Dexeik
 

Diplomat а решить эту проблему никак нельзя?

Re: Dexeik
 

2 WaReZ_MEN:
Можно.
1. Использовать одну из "двойных" версий ДЕкзейка, что не является эффективным решением;
2. Использовать другой алгоритм путенахождения. Для регулярных сеток рекомендую АСтар (см.).

Re: Dexeik
 

Я так понимаю что для этого алгоритма не надо разбивать мапу на квадраты? а то я стратегу пешу - там квадраты не прокатят

Re: Dexeik
 

What is "мапу на квадраты"?
Пожалуйста, определись с сутью вопроса.

Если ты интересуешься, поддерживает ли библиотека нерегулярные сетки, то могу с уверенностью заявить- нет, данная библиотека не поддерживает нерегулярные сетки.

Если же ты говоришь о разбиении карты на разного рода кластеры и двухэтапным поиском - по кластерам, а потом внутри кластеров- то ни ДЕкзейк вообще, ни представленная библиотека фактически не ограничивают фантазию в этом плане. Хочешь- разбивай, не хочешь- соответственно не разбивай.

Dixi.

Ответ: Dexeik
 

Обновил архивчик

Вложение 18550