Войти
ПрограммированиеФорумОбщее

Детские вопросы по Unity ( В чем преимущество Scriptable Object как переменных? ) (10 стр)

Страницы: 16 7 8 9 10 11 Следующая »
#135
(Правка: 13:31) 13:25, 19 янв. 2019

skalogryz
Понял. Ну, в txt  там особо делать нечего. А своя xml сериалазция звучит страшно, тем более словаря. Но я почитаю на эту тему.

А не, я считерил. Кто-то уже сделал SerializableDictionary.

https://weblogs.asp.net/pwelter34/444961

Усе работает!


#136
19:29, 19 янв. 2019

Jeaniro
> А не, я считерил. Кто-то уже сделал SerializableDictionary.
как видишь, это не то что "страшно", а очень даже элементарщина

#137
10:36, 20 янв. 2019

А использовать DataContractSerializer не судьба? Или вообще protobuf.net, это еще веселее, но формат не текстовой.

#138
17:45, 20 янв. 2019

ShadowTeolog
> А использовать DataContractSerializer не судьба?
Не знал про него, спасибо.

#139
(Правка: 1 мар. 2019, 1:22) 14:08, 25 янв. 2019
+ Показать
#140
(Правка: 1:26) 1:10, 1 мар. 2019

———

Дошли наконец руки до боевки. И, так как я нашел художника - решил уходить от чистого текстового формата и сделать бои пошаговыми, а-ля герои.

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


Игровое поле 11х11, каждый ход враг ( или враги ), просчитывает ближайший путь к игроку и, в зависимости от разных факторов ( дистанция атаки оружия, кол-во очков движения в раунде и пр. ), либо подходят вплотную, либо тратят только часть очков движения, либо проводят дистанционную атаку, ну или любое другое действие.

Граф взвешенный, но не сильно) В том смысле что весов всего два - 1 для ребра, соединяющего вершины напрямую и 1.4 по диагонали. Местность и прочее пока не берем во внимание.

Вот примерная схема :

+ Показать

Сейчас проще всего мне кажется алгоритм Дейкстры.
На бумаге несколько раз уже просчитывал ( на карте 5 на 5 ) - вроде все работает. Оно конечно часто находит несколько равнозначных путей до конечной точки, но это не проблема.

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


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

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

#141
(Правка: 3:51) 3:50, 1 мар. 2019

UPD:

Хотя, нашел вот пример A* где как раз то что мне и нужно - 10 обычное передвижение, 14 - диагональ.

https://vitalissius.github.io/A-Star-Pathfinding-for-Beginners/


Изображение

И в эвристической функции там просто манхэттенкое расстояние, ничо страшного.
Выходит, Дейкстру не стоит использовать?

#142
4:24, 1 мар. 2019

Jeaniro
На такой крохотной карте - должно быть пофиг.

Алгоритм A* - это наворот над Дейкстрой.
Другими словами: Дейкстра - это частный случай A*, с нулевой эвристикой.
Дейкстра, видимо, чуть проще и на такой крохотной карте - не факт, кто медленнее. Да и, повторюсь, пофиг.

Собственно, в твоём случае даже алгоритм Флойда-Уоршелла может быть разумным по времени (116=1771561 операций), особенно если не каждый кадр считать.

> Матрица смежности для 11*11 вершин - это жесть.
Почему?
114=14641, копейки.

#143
4:32, 1 мар. 2019

Jeaniro
> 11^4=14641, копейки.
Сорри, это я больше про хранение результатов (рассотяние от точки A до точки B).
Информацию о рёбрах хранить халява - у каждой вершины не более 8 соседей, вот в каждой вершине и храним массив на 8 элементов (и хранить реальное количество рёбер, или забить "лишние" ячейки в массиве специальным значением "недостижимая вершина").

#144
(Правка: 4:41) 4:37, 1 мар. 2019

Спасибо, про Флойда-Уоршелла почитаю.
Не знаю, мне A* как-то больше приглянулся.

FordPerfect
> Почему?
> 114=14641, копейки.
дык... я наверное жутко туплю, но пока не понимаю как это все дело заполнить нужными весами?
Все 14641 ячейки. Можно же как-то заполнить все циклом, но пока не додумался какая закономерность в чередовании 10 и 14 веса ребер.

Иначе даже 5*5 вручную - это такой треш :

+ Показать
#145
4:40, 1 мар. 2019

FordPerfect
> Информацию о рёбрах хранить халява - у каждой вершины не более 8 соседей, вот в
> каждой вершине и храним массив на 8 элементов (и хранить реальное количество
> рёбер, или забить "лишние" ячейки в массиве специальным значением "недостижимая
> вершина").

Вот, я сейчас как раз пробую так с А*.
Правда тогда нужно будет где-то и вес отдельно хранить. В матрице удобно тем что сразу виден и вес и смежная вершина.

#146
4:40, 1 мар. 2019

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

#147
(Правка: 4:55) 4:54, 1 мар. 2019

FordPerfect
> Собственно, соседей явно хранить вообще не обязательно: в данном случае они
> находятся из координат вершины.

Соседа-то можно найти, но надо же как-то чтоб оно понимало что ребро к этому соседу - 10, а к другому -14. Чтобы потом уже ставить метки расстояние соседям исходя из диагонального их расположения или обычного.

Хотя это тоже можно из вершины вычислить.
Я сейчас попробовал, вроде выходит.

+ Показать

Вот исходя из рисунка - если у соседней клетки [x,y] индекс x будет равен x текущей клетки - значит всегда будет вес 10 до нее. Или если по игрику совпадают - тоже 10. А вот если не совпадают ни x ни y - значит клетка диагональная.

#148
(Правка: 6:14) 5:54, 1 мар. 2019

FordPerfect

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

Ага и еще добавил ту самую "страшную" эвристическую функцию, меня просто слово испугало)

Код хромает понятное дело, но в целом все вроде работает.
Спасибо!

+ Показать

#149
6:02, 1 мар. 2019

Jeaniro
Забота о производительности вряд ли уместна.
Вот мой код, совсем тупой алгоритм Дейкстры за O(V^2):
https://rextester.com/ACYBBP95590

20 микросекунд.

Страницы: 16 7 8 9 10 11 Следующая »
ПрограммированиеФорумОбщее