Логика работы такова: луч — линия вида (y-player.y)/(x-player.x)=tan(alpha), а блок — квадрат размера 1×1 с координатами левого нижнего угла (I, j). Посчитать их пересечение можно аналитически, за пару сложений-вычитаний-делений, вместо сотен-тысяч шагов. Потом выбираем только те пересечения, что "перед нами", т.е. (x-player.x)/cos(alpha)>0, и из них выбираем такое, которое ближе всех (минимально (y-player.y)^2+(x-player.x)^2). Это и есть искомое пересечение, найденное за O(n).
Тонкий момент с O(n). Мой код — линейный относительно разрешения, но относительно размеров поля он O(nm). Код tiniraycaster O(1) относительно размера поля и O(n^2) относительно разрешения(больше разрешение — меньше нужен шаг для того чтобы не было ступенек). Разрешение как правило сильно больше размеров поля, так что ассимптотика по нему, по идее, важнее.
Заранее извиняюсь, если не прав, поправьте
Шагать по лучу — O (n) операций. У меня операций константное число на луч. Да, я ищу пересечения луча с каждым блоком, если они есть. То есть, в том проекте не считаются заведомо невозможные клетки, у меня — считаются, но каждая клетка обсчитывалится сильно быстрее
Новый интернет? Полностью анонимный и безопасный? И зафейливший?
ушёл смотреть кремниевую долину
Простите, обожаю свой т9
Да, скорее всего, так и надо сделать. Можкто быть, серебристый месяц будет ещё одна статья...
Логика работы такова: луч — линия вида (y-player.y)/(x-player.x)=tan(alpha), а блок — квадрат размера 1×1 с координатами левого нижнего угла (I, j). Посчитать их пересечение можно аналитически, за пару сложений-вычитаний-делений, вместо сотен-тысяч шагов. Потом выбираем только те пересечения, что "перед нами", т.е. (x-player.x)/cos(alpha)>0, и из них выбираем такое, которое ближе всех (минимально (y-player.y)^2+(x-player.x)^2). Это и есть искомое пересечение, найденное за O(n).
Тонкий момент с O(n). Мой код — линейный относительно разрешения, но относительно размеров поля он O(nm). Код tiniraycaster O(1) относительно размера поля и O(n^2) относительно разрешения(больше разрешение — меньше нужен шаг для того чтобы не было ступенек). Разрешение как правило сильно больше размеров поля, так что ассимптотика по нему, по идее, важнее.
Заранее извиняюсь, если не прав, поправьте
Шагать по лучу — O (n) операций. У меня операций константное число на луч. Да, я ищу пересечения луча с каждым блоком, если они есть. То есть, в том проекте не считаются заведомо невозможные клетки, у меня — считаются, но каждая клетка обсчитывалится сильно быстрее
Спасибо, стоит попробовать