Оптимальный способ рассортировать точки в 2D по таблице?

Kalombyr, У вас на картинке у ячеек разная высота в разных строках. Это проблемы рисунка, или вы допускаете такое решение?

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

В чём разница в скорости работы между перебором всех состояний игры и функций Шпрага-Гранди?

dalbio, В том смысле, что любая функция заданная на ациклическом графе - это ДП.

В чём разница в скорости работы между перебором всех состояний игры и функций Шпрага-Гранди?

dalbio, Не совсем ясно выразился. Ее можно подсчитать для меньших m x n. В этой задаче обычно двумя циклами считают функцию гранди для состояний i x j. Для вычисления этого состояния перебирают все разломы, и берут xor уже известных двух меньших прямоугольников.

Можно рекурсивно с мемоизацией считать - не важно. Главное, что вам надо считать функцию не для множества плиток, а только для одной.

Можете помочь с алгоритмом сортировки?

Yermek, Используйте цикл while. Не умею в го, но что-то типа такого там можно записать:

while (i1 < len(a1) && i2 < len(a2)) {
  if (a1[i1] < a2[i2]) {
    r[k++] = a1[i1];
  } else {
    r[k++] = a2[i2];
  }
}
while (i1 < len(a1)) r[k++] = a1[i1];
while (i1 < len(a2)) r[k++] = a2[i2];

Первый цикл выбирает меньгий эелемнт, пока есть оба массива. Далее остатки одного из двух массивов просто копируюутся в ответ.

Какие существуют алгоритмы для потоковый обработки сетевых данных?

Ваш вопрос не содержит основной информации. Какая именно обработка вам нужна.

Сам алгоритм потоковой обработки прост - берем данные из входного буфера, обрабатываем, кладем в выходной буфер. Тут вам никто ничего лучшего не подскажет.

Попробуйте убрать всю логику обработки - пусть ваше приложение тупо ничег ос данными не делает. Читает их до места, где у вас логика, и сразу же возвращает. Если тормозит уже это, то это проблема не в обработке, а в чтении, выводе сетевых данных. Тут нужно смотреть на вашу реализацию, может где-то буфиризацию прикрутить надо, может проблема с мультитредингом и локами.

Если такое демо не тормозит, то пишите, что вы конкретно с данными делаете.

Как найти кратчайший путь с минимальным количеством поворотов(повороты в приоритете)?

Перебираем вообще все всевозможные пути достижения цели.

Знаете, сколько их? Количество сочетаний из W+H по H, где W,H - размеры карты. И это только кратчайшие пути. А ведь можно же еще зигзагами ходить... Короче, это ОЧЕНЬ много.

Плохая идея. Это - задача поиска кратчайшего пути. Она тысячу раз решена в computer science. Только при прочтении "кратчайший путь" у вас сразу же должна быть мысль о теории графов. И не надо городить велосипеды, надо просто знать теорию.

Как считывать несколько переменных в языке C?

rifat2125, Погуглил за вас: https://stackoverflow.com/questions/31522555/read-...

Как мне задать десятичкную дробь в моем коде?

guzya007, Код в студию, пожалуйста.

Как создать программу перевода из 8-ричной СС в 10-ричную?

Alexandr_202, Ну вот - пишите цикл, который походится по цифрам и домножает их на степени. Если число может быть дробным, то сначала циклом найдите . и от нее потом гоните 2 цикла в разные стороны. Коэффициенты - степени можно пересчитывать в цикле. При переходе к следующей цифре влево надо домножить степень на 8. При переходе вправо - поделить.

Как создать программу перевода из 8-ричной СС в 10-ричную?

Alexandr_202, Вы знаете, что такое циклы?

Где и для чего используют кучу (heap)?

alex4answ,

> Но и в куче не выйдет бин поиск использовать,

Но в куче и не нужен бин поиск. Она же недо-сортированный массив поддерживает. Туда можно легко вставлять новые элементы (дописали в конец, и подняли по дереву, пока надо).

Где и для чего используют кучу (heap)?

alex4answ, Потому что в очередь добавляются элементы постоянно. Если бы вам были даны все значения сразу же, то вы бы просто отсортировали их и все. Но нет, как, например, в алгоритме Дейкстры - новые элементы в очередь добавляются потом и мы их заранее не знаем. В сортированный массив вставлять новые элементы очень долго - надо сдвинуть кучу элементов, чтобы освободить место для нового. Если же вы будете сортированный список делать, то на нем не получиться делать бинпоиск и найти место для вставки уже станет долго.

Можно ли как-то оптимизировать/ускорить этот код?

Фокс Йовович, Определение касательной - это прямая, которая имеет с данной фигурой одну точку пересечения. Иными словами, прямая касается фигуры. Тут полигон - не кривая, а выпуклое замкнутое множество на плоскости.

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

Можно ли как-то оптимизировать/ускорить этот код?

Фокс Йовович, Смотрите - тут полигоны - выпуклые множества. Касательная - это прямая, которая имеет с этим множеством ровно одно пересечение. Это математическое определение.

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

Вот поэтому автору и нужны именно касательные.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Да, важный момент - отрезки между полигонами можно смотреть только касательные к обоим полигонам. Это можно до пересечения с чем-то еще проверить, что отрезок касается того полигона, с которого вы касательные опустили на второй. Обычно таких касательных всего 4 (если полигоны не пересекаются). Но их может быть и сколько угодно, если полигоны торчат друг из друга всеми вершинами (представьте правильные k-угольники с общим центром, но чуть чуть повернутые вокруг центра).

Еще одна хорошая оптимизация - это bounding box. Не надо проверять на пересечение полигоны, если добавляемое ребро не пересекается с его обрамляющим прямоугольником. Можно еще дальше пойти и запилить Rtree на полигонах. Оно не сильно ускоряет на случайно сгенерированных полигонах, но может сильно помочь если есть структура у карты.

И еще, мое предложение о раздутии не очень хорошее. Если есть острые углы, то путь будет обходить их очень далеко. Но можно их усечь. Лучший вариант - вместо одной вершины добавлять 2, тоже на сдвинутых на r сторонах. Добавлять их так, что прямая меджду ними отстоит от вершины на r. Тут если порисовать вылезает tg(a/4). Посмотрите в код на Polygon::Inflate в Polygon.cpp в архиве внизу. Еще хорошо видно, как оно обходит, если включить прорисовку ребер.

Я запилил демку на C++ (не умею в JS) - строит граф 16мс для 100 полигонов по 10 вершин. Дальше ищет путь мгновенно. Т.е. если у вас карта не обновляется, то можно один раз в начале вызвать AddPolygons. Иначе можно допустить просадку по кадрам при обновлении карты. Еще можно разбить AddPolygons на этапы (добавлять ребра для трети/половины полигонов за раз. Или смотреть по тайм-лимиту). И не строить пути, пока нужное количество вызовов не наберется. Тогда просадки по кадрам не будет, но боты не будут двигаться первые несколько кадров.

Там в архиве екзешник и код для Visual Studio 19. Если не запуститься, гуглите visual studio redistributables.

Как пользоваться демкой: там меню. В debug->Generate polygons можно заполнить карту полигонами. Еще в debug можно переключать прорисовку ребер и bounding boxes. Еще там можно отключить rtree, вряд ли вы его захотите реализовывать.

Можно перетаскивать начало или конец мышкой. Можно в меню Move выбрать что вы хотите подвинуть и кликнуть куда. В меню polygon можно выбрать добавление или удаление. При добавлении клики добавляют вершину к текущему полигону. Правый клик - добавляет его на карту. Еще один выключает режим добавления. При удалении левый клик удаляет все полигоны вокруг курсора (они красным подсвечены). Правый клик выключает режим удаления.

Вверху пришется, что за режим сейчас. Слева рисуется время за последний кадр на весь расчет путей и отдельно сколько из этого было построение графа (геометрические вычисления). Сама прорисовка медленная и тоже занимает еще +16мс, наверно. Не ждите от этой демки 60фпс.

Вы заметите, что там всегда 0, если двигать начало или конец. Но при нажатии generate polygons, если после этого не двигать мышку, вы заметите 16мс (двигание мышки вызывает перерисовку, которая моментальная).

Структура кода: Vec, Segment, Polygon - геометрические примитивы. PathFinder строит граф и ищет по нему пути. NavMesh - интерфейс и основная логика. Остальное - артефакты от visual studio.

Как реализовать поиск в глубину не рекурсией и если много кольцевых связей?

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

Как перебрать из массива до тех пор, пока совпадают даты?

Lynn «Кофеман», Если элементы не отсортированы, то вы никак не сможете выбрать элементы за определенную дату, не пройдясь по им всем.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, А в вашем скрипте ошибка тут:

var angle = ( vec_1.x * vec_2.x + vec_1.y * vec_2.y )/r*r;
var num =  1/(Math.cos(angle/2)*Math.sqrt(2+2*Math.cos(angle)))

В angle у вас храниться значение cos(a), а не угол. А вы потом от этого значения косинуса еще берете косинус.

Может еще где что-то есть.

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Magneto903, Все проще, если у вас полигон задан в порядке обхода против часовой стрелки (можно и по, но надо, чтобы все полигоны так были заданы). Можно понять, в каком порядке задан полигон, если посмотреть на знак векторного произведения двух соседних векторов-сторон. Далее, трюк - можно индексы брать по модулю. Если у вас n точек в полигоне, то они пронумерованы от 0 до n-1 в массиве. И следующая за последней будет ((n-1)+1)%n = 0.

Дальше, мы хотим подвинуть i-ую веришину. Проще создавать раздутый полигон в новом массиве. Предыдущая имеет номер j=(i+n-1)%n, следующая k=(i+1)%n.

Далее, вектора нормалей можно взять просто повернув вектора стороны на 90 градусов влево. Если первая сторона имеет вектор (x[i]-x[j], y[i]-y[j]), то нормаль наружу будет (y[i]-y[j], -(x[i]-x[j])). На бумажке проверьте, что это так, например, для вектора (1,0) - нормаль наружу будет идти вниз (0, -1). Точно так же, вторая нормаль будет (y[k]-y[i], -(x[k]-x[i])). Да, эти вектора еще надо обязательно сделать длиной r - на сколько у вас боты обходят полигоны. Поделите на sqrt(vx*vx+vy*vy) и умножте на r все координаты.

Далее, формулу надо сначала преобразовать через cos(a) и sin(a) - их можно получить, если взять векторное/скалярное произведения нормалей и поделить на длины нормалей):

1/(cos(a/2)*sqrt(2+2cos(a)) = 1/(1+cos(a)). Внезапно сильно сократилось. И эта формула имеет смысл. Если нормали совпадают, то надо сдвинуться на вектор длины 1. А значит сумму двух нормалей надо будет поделить на 2. И действительно, при a=0, формула даст 1/2. Если нормали перпендикулярны, то они образуют квадрат со сдвинутыми сторонами и их сумма как раз даст диагональ. Надо домножить сумма на 1. Если же нормали прямо в разные стороны смотрят (a=180), то пересечение как-бы в бесконечности (стороны-то параллельны). И действительно, формула даст 1/0.

Вот вы знаете нормали (длины 1). Взяли их скалярное произведение, получили cosa. И потом к текущей точке прибавьте эти 2 нормали, домноженные на 1/(1+cosa). Не забудьте новую точку считать в новом массиве. Иначе вы для следующей точки будете стороной считать вектор с уже сдвинутой вершины.

Почему простой файл на c# детектится как троян?

ShiyanoTetsu, Денег легких захотелось? Имейте ввиду, таких хакеров регулярно сажают. У вас, судя по вопросу, знаний маловато, так что вас точно поймают.