NCrashed
offline
Опыт:
13,553Активность: |
[cJass] WayLib - система поиска пути по дорогам
Эта библиотека реализует знаменитый алгоритм A* поиска оптимального пути в варе. В отличие от стандартного pathing, моя система учитывает стоимость каждого вида местности. Юнит не побежит через поле, а пойдет через обходную дорогу. Также можно указать какие тайлы непроходимы.
Импорт
ИспользованиеЧтобы просчитать путь, надо:
,где u - ваш юнит tx,ty - координаты точки цели, которая находится на дороге.
В качестве примера обработки я написал доп. библиотеку Poter, пример ее использования можно посмотреть в триггере "DBPoter" и, собственно, следует посмотреть саму эту библиотеку.
ПримечаниеСистема еще не релизная, считает все правильно, но долго из-за задержек. Без них происходит один большой лаг. В следующих версиях этого не будет, так как путь будет считаться сразу с 2х сторон и юзаться 2х уровневый pathing, +перейду на binary heaps ака бинарные кучи, они в 10 раз быстрее хештаблиц на длинных путях. Отредактировано NCrashed, 02.11.2009 в 14:58. |
29.10.2009, 17:55 | #1
+1/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
Может обход графа в ширину? В глубину - это на ацикличность. |
29.10.2009, 18:15 | #2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
В глубину. |
29.10.2009, 18:16 | #3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
Чёт ты гонишь, нахождение наикратчайшего пути - это в ширину называеца. |
29.10.2009, 18:17 | #4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
Если представить точку начала пути за вершину графа, то это будет поиск в глубину. |
29.10.2009, 18:19 | #5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
читай
Rinegan добавил: Меня не переспоришь)) |
29.10.2009, 18:20 | #6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
Идеологический момент здесь не очень важен, оцените саму систему. |
29.10.2009, 18:20 | #7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
XOR
offline
Опыт:
38,284Активность: |
В длину. Ну а так норм, только немного неудобно твои системы собирать по отдельности) я так понимаю исключается возможности вылета за конец карты? И почему только с квадратными |
29.10.2009, 18:22 | #8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
Ок, ща посмотрю. хотя всёже в ширину=) |
29.10.2009, 18:22 | #9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
Все убедил, поиск в ширину =). Не буду с тобой спорить.
NCrashed добавил:
XiMiKs, главная библиотека WayLib. А библиотека Poter нужна только для теста =). Ее конечно можно переделать под себя и использовать. С квадратными легче вычислить номер тайла по координатам, иначе нужно писать собственную функцию для x и y координат. В итоге получим 4 функции вместо 2х. А так как неквадратные карты редко используются, то я упростил задачу. NCrashed добавил: Вылет за пределы проверяется. |
29.10.2009, 18:26 | #10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
Чёто у тебя всё так сложно написано. Не втом смысле, что сама задача сложная, а ты как-то её уж больно усложнил. Если ты не против, я попробую тоже самое написать? |
29.10.2009, 18:30 | #11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
Попробуй, задача на самом деле непростая, можно попытаться построить путь не циклом, а рекурсией, но я не стал так издеваться над своими (и пользовательскими) мозгами |
29.10.2009, 18:32 | #12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
Нет, рекурсия здесь будет очень долгой, если задача из одного края карты размером 480х480 перейти в другой. Здесь списком делать надо.
Rinegan добавил:
оО Это что за изврат?!
|
29.10.2009, 18:37 | #13
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
инт с там лишнее, забыл удалить, это вычисление остатка от деления |
29.10.2009, 18:52 | #14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
ну ты извращенец.....
А DIV то зачем? стандартное деление 19/5 и есть div, и выдаст оно 3. Rinegan добавил:
Во-первых это делается не циклом. Во-вторых есть нормальная BJ функция ModuloInteger
|
29.10.2009, 18:54 | #15
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
Оно выдаст с дробной частью а при округлении можно получить не то значение, например при округлении 13.8
NCrashed добавил: Не люблю бж функции, не доверяю я им, все равно также сделана |
29.10.2009, 18:57 | #16
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
local integer i = 19/5 i будет равно 3 проверь сам. |
29.10.2009, 18:58 | #17
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Toadcop
offline
Опыт:
54,313Активность: |
Цитата:
пфффф олололол... n/c у интов есть дробная чясть... |
|
29.10.2009, 19:00 | #18
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Rinegan
offline
Опыт:
895Активность: |
ничё не также, она нормально сделана, проверь. |
29.10.2009, 19:00 | #19
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
NCrashed
offline
Опыт:
13,553Активность: |
Ладно есть такая фича, но быстрее работает мой вариант. По-другому на аппаратном уровне не вычисляется. И вообще что ты придрался к этим двум функциям =) ? Див вроде там всего 1 раз используется.
NCrashed добавил: В джаззе есть неявное приведение типов? 0_o |
29.10.2009, 19:02 | #20
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|