D
да, но я БФС вызываю 1-2 раза за тик, а ты для каждого юнита
Size: a a a
2020 December 23
SF
Alexander Dudin
Для A* нужна приоритетная очередь, и это всю производительность убивает на корню
Нипанятна, бинарная куча оч быстрая штука, а если мы говорим про такие крошечные карты, то всё равно вся твоя очередь в кешах оседает и там нет особо разницы между приоритетнйо очередью и обычной
AN
да, но я БФС вызываю 1-2 раза за тик, а ты для каждого юнита
Но у тебя приближенный маршрут получается, а у меня точный. И как ты таким способом ищешь ближайший ресурс для рабочего? Я вот тоже BFS вызываю для этого, но только от каждого рабочего, чтоб найти ближайшую точку добычи.
D
Alexander N
Но у тебя приближенный маршрут получается, а у меня точный. И как ты таким способом ищешь ближайший ресурс для рабочего? Я вот тоже BFS вызываю для этого, но только от каждого рабочего, чтоб найти ближайшую точку добычи.
для рабочих заливаю карту ресурсов
D
AN
для рабочих заливаю карту ресурсов
ммм... ПП, вкусно, но не точно.
D
Alexander N
ммм... ПП, вкусно, но не точно.
БФС )
SF
D
Респектос, я поленился так сделать 🌚
заставить бы это работать
AN
ну значит я неправильное значение в ПП вкладываю. Для меня это что-то вроде полей притягивания/отталкивания. А у тебя по сути это и получается - идти туда, где меньше цифра и придёшь к ресурсам
D
ато куча заливок и расчётов...
D
Alexander N
ну значит я неправильное значение в ПП вкладываю. Для меня это что-то вроде полей притягивания/отталкивания. А у тебя по сути это и получается - идти туда, где меньше цифра и придёшь к ресурсам
ПП этотнемного другое
AD
Нипанятна, бинарная куча оч быстрая штука, а если мы говорим про такие крошечные карты, то всё равно вся твоя очередь в кешах оседает и там нет особо разницы между приоритетнйо очередью и обычной
Ну а карта для BFS (6400 байт) поместиться в 100 кэш линий первого уровня, быстрее уже некуда. A* все таки нужен в первую очередь для больших и сложных карт.
AN
в Rewind нельзя текст рисовать, это очень печалит. Я бы тоже что-нибудь подписывал
LS
Alexander N
Померил сейчас скорость в моих реализациях:
BFS заливка полной карты: 266 мс за 1500 вызовов
A* поиск из угла в угол: 256 мс за 1500 вызовов
и ничего не сжирает приоритетная очередь. Когда нужен поиск к конкретной точке с возможностью пробиться сквозь ресы - астар вполне норм
BFS заливка полной карты: 266 мс за 1500 вызовов
A* поиск из угла в угол: 256 мс за 1500 вызовов
и ничего не сжирает приоритетная очередь. Когда нужен поиск к конкретной точке с возможностью пробиться сквозь ресы - астар вполне норм
Из угла в угол плохой кейс, тут у а* никаких плюсов. Из центра в угол по идее сильно меньше узлов должно быть
SF
Alexander N
ну значит я неправильное значение в ПП вкладываю. Для меня это что-то вроде полей притягивания/отталкивания. А у тебя по сути это и получается - идти туда, где меньше цифра и придёшь к ресурсам
Даже если идти просто туда, где меньше цифра, ты придёшь к ресурсу кратчайним образом, очевидно
D
Alexander N
в Rewind нельзя текст рисовать, это очень печалит. Я бы тоже что-нибудь подписывал
у меня своя 👀
AN
Lev Simonov
Из угла в угол плохой кейс, тут у а* никаких плюсов. Из центра в угол по идее сильно меньше узлов должно быть
ну вот и хорошо, значит я получу ещё больший прирост, выбрав астар
SF
Alexander Dudin
Ну а карта для BFS (6400 байт) поместиться в 100 кэш линий первого уровня, быстрее уже некуда. A* все таки нужен в первую очередь для больших и сложных карт.
Я согласен, что тут оптимизировать почти нечего 🌚 Тем не менее с А* ты найдёшь путь за значительно меньшее число итераций, т.е. тебе даже меньше к кешу надо обращаться
AN
Даже если идти просто туда, где меньше цифра, ты придёшь к ресурсу кратчайним образом, очевидно
и очевидно там будет чаще всего занято ))