Моя проблема сегодня заключается в следующем:
У меня много гражданских, которые ходят, это классы, хранящиеся в архиве.
Идея в том, что когда они увидят очередную гражданскую панику, они начнут паниковать, и она распространится.
Сначала я вызываю Step()
функцию каждого класса , проходя через итератор. Затем в Step()
функции он проходит через другой цивиллианский итератор. При прохождении он пытается определить, может ли он видеть другой цивиллиан в итераторе, и здесь время выполнения составляет от 0 до 50 миллисекунд при наличии 100 цивиллиан.
Это проблема, которую мне нужно решить, я попытался найти простой способ определить, находятся ли какие-либо объекты на пути точка а в точку б.
Вот код для прямой видимости:
public static Object LOS(int x, int y, int x2, int y2, String Scan, Object Me, Object You) {
DirectionX = (x-x2)/Quality;
DirectionY = (y-y2)/Quality;
CurrentX = x;
CurrentY = y;
String[] ScanArray = Scan.split(":");
for(int I=0;I<=Quality;I++) {
for(String Type: ScanArray) {
if(Type.equals("Boxs")) {
Iterator it=Level.Boxs.iterator();
while(it.hasNext()) {
Box Box = (Box)it.next();
if(Me!=Box&&You!=Box) {
//Collision = Tools.Collision((int)(CurrentX-(Width/2)), (int)(CurrentY-(Width/2)), Width, Width, Box.GetX(), Box.GetY(), Box.GetWidth(), Box.GetHeight(), 1);
boolean Col = Tools.BasicCollision((int)(CurrentX-(Width/2)), (int)(CurrentY-(Width/2)), Width, Width, Box.GetX(), Box.GetY(), Box.GetWidth(), Box.GetHeight());
}
}
}
}
CurrentX-=DirectionX;
CurrentY-=DirectionY;
}
return null;
}
Если у вас болит голова, основные принципы:
Он вычисляет 10 точек между ними и определяет, находится ли он внутри, используя BasicCollision
:
public static boolean BasicCollision(int x, int y, int width, int height, int x2, int y2, int width2, int height2) {
if(x<x2+width&&x+width>x2&&y<y2+height&&y+height>y2) {
return true;
} else {
return false;
}
}
Мой вопрос: есть ли более простой способ обнаружить эту линию взгляда, которая не окажет серьезного влияния на мою производительность в больших количествах? Есть отзывы?
источник
LOS.txt
2. Мы не хотим видеть весь ваш код. Предоставить SSCCE .Ответы:
Одной из мыслей было бы сохранить непаниковавших и паниковавших людей в отдельных списках N и P, а затем ограничить количество проверок LOS <n, p> ∈ N × P. Таким образом, вы никогда не проверяете людей с одинаковым состоянием, что ускорит процесс вверх.
Еще одна вещь (которую вы, возможно, уже делаете - не уверен) заключается в том, чтобы убедиться, что, как только вы определите, что непаникатель стал паникером, немедленно остановите оставшиеся проверки для этого бывшего непаникателя. Это поможет вашему алгоритму масштабироваться с увеличением численности населения для фиксированной карты. Когда популяция становится очень большой, вы должны довольно быстро сходить в сторону 100% паники, что означает, что больше никаких проверок не требуется, как отмечено в комментариях ниже.
источник
Из вашего описания кажется, что ваш код перебирает каждую возможную пару двух гражданских лиц. Чертеж предполагает, что это не нужно. Вы можете использовать какую-то геометрическую индексацию, чтобы отслеживать близлежащих гражданских лиц. Тогда проверьте их сначала. Если они в ЛОС, то паникуйте. В противном случае проверить гражданских лиц подальше.
источник
У вас есть несколько вариантов:
А) Предположим, что люди могут паниковать и слышать крики других людей, поэтому код прямой видимости не так важен, как XD.
Б) В случае, если А не вариант, вы должны сделать это для каждого гражданского лица:
Вы должны выполнить 1 до 2, потому что это значительно уменьшает объем работы, учитывая, что 2 является самым дорогим вычислением. Кроме того, вы должны учитывать некоторую «память» о вычислениях, которые вы уже сделали, например: Если вы только что обработали сегмент C1-C2, не делайте снова C2-C1.
В дополнение к этому, вы должны оптимизировать 2. Тестирование, если сегмент пересекается с прямоугольником, эквивалентно тесту, если данный сегмент пересекается с 4 сегментами. Когда вы пересеклись с одним из них, мы уверены, что гражданские лица не видят друг друга, поэтому нет смысла обрабатывать оставшиеся сегменты в прямоугольнике.
Поскольку это типичная геометрическая проблема, известная как проблема пересечения отрезков , вы можете найти множество открытого исходного кода в Интернете. Большинство людей используют алгоритм строчной развертки вместе с некоторой структурой данных.
источник
Если вы рассматриваете комнаты как зоны, к которым присоединяются порталы , вам нужно только выполнять сканирование видимости внутри каждой комнаты и тех частей смежных комнат, которые видны через предварительно определенные порталы.
Ваша прямая видимость, вероятно, не учитывает направление, в котором стоит гражданское лицо? В таком случае, если вы разделите комнаты, в которых есть препятствия, такие как колонны или огибающие углы, на отдельные выпуклые зоны и при условии, что все гражданские лица в одной зоне видны друг другу. Вы можете пойти дальше, имея перекрывающиеся вогнутые зоны и позволяя гражданским лицам находиться в более чем одной зоне одновременно, чтобы найти как можно больше в той же зоне, что и другие гражданские лица, чтобы избежать всех других проверок видимости.
Если ваш рельеф неровный и у вас большое количество агентов, вас может заинтересовать этот O (n) развертка (где N - гранулярность сетки, на которую вы разбили ландшафт):
источник