что такое коллизия в информатике
Box2d: анатомия коллизий
Что такое коллизии?
В Box2D принято считать, что друг с другом сталкиваются тела, однако на самом деле при расчете коллизий используются фикстуры (fixtures, переводы слова существуют, но я не уверен, есть ли среди них устоявшийся). Объекты могут сталкиваться разными способами, поэтому библиотека предоставляет большое количество уточняющей информации, которая может быть использована в игровой логике. Например, вы можете захотеть узнать следующее:
Все настроено таким образом, чтобы нижняя часть треугольника столкнулась с верхним углом квадрата. Тонкости реализации этого процесса выходят за рамки статьи — основное внимание уделим тому, какую информацию можно извлечь на каждом этапе столкновения. Если есть желание самостоятельно запустить предлагаемый пример, исходный код прилагается.
Получении информации о столкновении
Информация о столкновении содержится в объекте типа b2Contact. Из него можно узнать, какие именно фикстуры сталкиваются, и определить их положение и направление результирующих импульсов. Существует два способа получения объектов b2Contact в Box2D. Первый — перебрать текущий список контактов каждого тела объекта, второй — использовать слушатель контактов. Рассмотрим каждый из них, чтобы дальше было понятнее, о чем идет речь.
Проверка списка контактов
В любой момент можно перебрать все контакты мира (имеется в виду b2World)
или получить контакты тела определенного объекта
Если выбран этот подход, очень важно помнить, что наличие контакта в этих списках не означает, что фикстуры соприкасаются — это значит только, что пересекаются их AABB. Если требуется убедиться, что контактируют сами фикстуры, воспользуйтесь методом IsTouching(). К этому вопросу мы еще вернемся.
Слушатели контактов
Проверка списка контактов становится неэффективной в ситуациях, когда столкновения происходят часто и в больших количествах. Устанавливая слушателей контактов, вы отдаете поручение Box2D сообщать, когда происходит что-то интересное, вместо того, чтобы вручную следить за началом и завершением столкновений. Слушатель контактов — это объект класса b2ContactListener, часть функций которого замещается при необходимости.
Должен заметить, что в зависимости от ситуации, некоторые события дают нам не только объект b2Contact. В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас. Практическое использование «обратных вызовов при коллизиях» рассматривается в отдельной статье. Здесь мы все внимание сосредоточим на том, что можно узнать, обрабатывая события столкновений.
В общем случае я рекомендую метод слушателей контактов. На первый взгляд он может показаться несколько неуклюжим, однако он более эффективен и полезен в долгосрочной перспективе. До сих пор мне не встречалась ситуация, когда проверка списка контактов давала бы ощутимый выигрыш.
Вне зависимости от способа получения контактов, они содержат одинаковую информацию. Наиболее важные данные о пересекающихся фикстурах можно получить так
Когда происходит обход списка контактов определенного объекта, возможно, одна из фикстур коллизии известна, но если используется слушатель контактов, придется полностью положиться на эти функции, чтобы понять, что с чем сталкивается. Четко заданного порядка фикстур не существует, так что часто приходится устанавливать пользовательские данные (user data), чтобы понять, какому именно объекту принадлежит фикстура или тело. Располагая объектом фикстуры, можно воспользоваться методом GetBody(), чтобы получить ссылку на тело.
Столкновение шаг за шагом.
Теперь давайте подробнее рассмотрим последовательность событий, происходящих при столкновении. Надеюсь, картинок с описанием каждого шага будет достаточно для понимания материала. Возможно, вы захотите загрузить исходники к уроку, чтобы запускать их во время чтения. Тестовая программа позволяет ставить симуляцию на паузу, перезапускать и выполнять ее по шагам.
Начнем с ситуации, когда AABB фикстур не пересекаются, так мы сможет проследить историю полностью. Кликните флажок «AABBs», чтобы увидеть фиолетовые прямоугольные области вокруг каждой фикстуры.
AABB фикстур начинают перекрываться
Несмотря на то, что сами фикстуры еще не пересеклись, на этом этапе уже создается экземпляр b2Contact и добавляется в список контактов мира и списки каждого тела. Если вы просматриваете эти списки, то по наличию объектов b2Contact можно судить о том, что в принципе контакт возможен, хотя фикстуры не обязательно пересеклись.
Результат: контакт существует, но IsTouching() возвращает ложь
Продолжаем симуляцию, пока не пересекутся непосредственно фикстуры…
Фикстуры начинают пересекаться.
Приблизив верхний угол квадрата, можно увидеть переход, как на следующих изображениях
Шаг n
Шаг n+1 (не bullet-объекты)
Все это происходит за один шаг симуляции, значит, реальную точку пересечения (к которой ведет пунктирная линия на рисунке выше), мы проскочили. Это происходит потому, что Box2D сначала смещает все тела и только потом проверяет пересечения, по крайней мере, это его поведение по умолчанию. Если вам нужна реальная точка соприкосновения, то нужно сделать следующее
Шаг n+1 (треугольник — bullet-объект)
Bullet-тела, расходуют больше процессорного времени на расчеты и для большинства приложений не требуются. Просто помните о том, что при обычных настройках, иногда коллизии могут пропускаться — в нашем примере, если бы треугольник двигался достаточно быстро, он мог бы пролететь сквозь угол квадрата, не инициировав столкновения. Если у вас есть очень быстро перемещающиеся тела, контакты которых не должны пропускаться, например, мммм… пули 🙂 тогда их нужно объявлять как bullet-объекты. Дальнейшее изложение будет вестись для не-bullet-тел.
Точки столкновения и нормаль
К этому моменту в нашем контакте присутствует реальное соприкосновение, что дает возможность ответить не некоторые вопросы в начале статьи. Для начала давайте получим нормаль и точку касания. Предполагается, что приведенный далее код вызывается или из метода BeginContact слушателя контактов или из вашего метода после предварительного получения контакта из списка.
Объект контакта содержит информацию о коллизии в локальных координатах тел сталкивающихся объектов, а это не совсем то, что нам нужно. Однако можно запросить у контакта более полезную структуру b2WorldManifold, которая содержит позицию коллизии в мировых координатах.
Полученные точки будут использованы Box2D для расчета реакции на столкновение для вычисления импульса, который направит фикстуры в противоположные стороны. Это будут неточные места соприкосновения фикстур (если только вы не использовали bullet-объекты), хотя на практике их обычно достаточно для расчетов столкновений в игровой логике.
Далее рассмотрим нормаль коллизии, которая направлена от фикстуры A к B:
Похоже на то, что для этого столкновения самый быстрый способ избавиться от перекрывающихся объектов, это оттолкнуть угол треугольника вверх и влево, а квадрата — вниз и вправо. Хотелось бы обратить ваше внимание на то, что нормаль — это просто направление, она не привязана ни к какой точке контакта — я изобразил ее проходящей через points[0] для удобства.
Важно также помнить, что нормаль столкновения не определяет угол между фикстурами (ведь треугольник двигается вообще горизонтально) — она лишь задает направление, следуя которому быстрее всего компенсируется перекрытие объектов. Например, представьте, что треугольник двигается немного быстрее, и перекрытие выглядит так:
Тогда самый быстрый способ разделить фикстуры — оттолкнуть треугольник вверх и вправо. Так что использовать нормаль для расчета угла между объектами нецелесообразно. Если требуется узнать направления, по которым будут разделяться фигуры, можно воспользоваться следующим кодом:
Он позволит получить относительную скорость реакции всех точек столкнувшихся тел. В нашем простом случае можно было бы ограничиться линейной скоростью треугольника, так как известно, что квадрат неподвижен, а треугольник не вращается. Но вышеуказанный код будет учитывать и случаи, когда оба дела движутся или вращаются.
Также нужно заметить, что не при каждом столкновении будет именно две точки коллизии. Я намерено остановился на достаточно сложном примере, когда перекрываются два угла многоугольников, но чаще бывает только одна такая точка. Вот несколько примеров столкновений, для которых достаточно одной точки
Итак, только что мы рассмотрели, как определить точки и нормаль коллизии, на основе которых Box2D будет рассчитывать реакцию, направленную на компенсацию перекрытий. Теперь вернемся к последовательности событий.
Реакция на столкновение
( (b2Contact::Update, b2Island::Report))
Шаг_столкновения
Шаг_столкновения + 1
Шаг_столкновения + 1
Когда фикстуры перекрываются, реакция Box2d по умолчанию — приложить импульс к каждой из них, чтобы направить в разные стороны. Однако это не всегда удается сделать за один шаг моделирования. Как показано на рисунках для нашего примера, две фикстуры будут перекрываться на протяжении трех шагов, пока отскок не состоится, и они окончательно не разделятся.
В это время мы можем вмешаться и настроить поведение модели, как нам захочется. Если используется подход со слушателем контактов, методы PreSolve и PostSolve будут вызываться на каждом шаге, пока фикстуры перекрываются, давая возможность модифицировать контакт перед тем, как он будет обработан стандартными средствами реакции на коллизию (PreSolve), и узнать, какие импульсы были приложены Box2D (PostSolve)
Для большей наглядности приведу вывод printf, которая помещена в в функцию Step и каждый метод слушателя контактов:
Результат: PreSolve and PostSolve вызываются несколько раз
PreSolve and PostSolve
Оба эти метода получают в качестве параметра указатель на b2Contact, так что мы имеем доступ к той же информации о точках и нормалях, что и в BeginContact. PreSolve дает на возможность изменить характеристики контакта перед расчетом реакции на столкновение и даже отменить реакцию полностью. PostSolve позволяет получить информацию о вычисленной реакции.
В PreSolve можно сделать следующие настройки объекта контакта:
Вызов SetEnabled(false) деактивирует контакт, значит, реакция на столкновение просчитываться не будет. Это может понадобиться, когда необходимо временно позволить объектам пролетать друг сквозь друга. Классический пример — односторонняя стена или платформа, когда игрок может пройти сквозь обычно непроходимый объект при определенных условиях, которые можно проверить только во время выполнения — например, позиция игрока или направление его движения.
Важно помнить, что на следующей итерации контакт снова активируется, так что если нужно отключить его на продолжительное время, придется делать это на каждом шаге.
Кроме ссылки на контакт, PreSolve содержит второй параметр, из которого можно получить характеристики коллизии (точки и нормаль) с предыдущего шага моделирования. Если кто-то знает, зачем это может пригодиться — расскажите мне 😀
PostSolve вызывается после того, как реакция на столкновение была рассчитана и применена. У метода есть второй параметр, содержащий информацию о приложенном в результате импульсе. Обычно он используется для проверки, не превысила ли реакция некоторое пороговое значения, в результате чего объект можно разрушить и т.п. В статье » sticky projectiles» содержится пример использования функции PostSolve для определения, должна ли стрела застревать в мишени.
Возвращаемся к сценарию столкновения
Фикстуры больше не перекрываются
(b2Contact::Update)
AABB все еще перекрываются, так что контакт пока остается в соответствующих списках мира и тела.
(увеличенный масштаб)
AABB фикстур не перекрываются
(b2ContactManager::Collide)
Результат: контакт удаляется из списка контактов мира и тела.
Метод EndContact получает указатель на b2Contact, когда фикстуры уже не соприкасаются, так что в нем уже не содержится актуальной информации. Тем не менее EndContact является неотъемлемым элементом слушателя контактов, так как позволяет контролировать, когда игровые объекты покидают зону соприкосновения.
Коллизия в сети
Что такое коллизия в сети (collision)? Сегодня мы разберем само понятие коллизий в локальной сети, возможные причины их возникновения и как бороться с подобным явлением? Также узнаем, что такое домен коллизий?
Наша статья, будет состоять из двух частей: в первой (теоретической) мы рассмотрим основные понятия и термины, которые нам пригодятся в дальнейшем, а во второй части я покажу Вам (на примере), какие могут быть проблемы в реальной сети и к чему нужно быть готовым?
Проиллюстрируем возникновение коллизии в компьютерной сети на простенькой схеме:
Учитывая скорости движения данных в сети, вряд ли возникновение коллизии возможно в случае соединения только двух компьютеров? НО! Если компьютеров становится больше?
Случайный характер алгоритма доступа к среде передачи данных, принятый в технологии Ethernet, нельзя назвать идеальным. При большом количестве запросов на доступ к среде передачи, генерируемых узлами в случайные моменты времени, вероятность возникновения коллизий также возрастает, что приводит к неэффективному использованию всего канала. Время обнаружения коллизии и время ее обработки составляют дополнительные временные затраты, а интервал в течение которого канал предоставляется в распоряжение каждому узлу, становится все меньше.
Подобный случай мы рассматривали в статье, о возможности образования петли в локальной сети организации.
Давайте с Вами рассмотрим, какие же бывают разновидности коллизий?
Чтобы покончить с обязательной терминологией, давайте рассмотрим еще одно нужное нам словосочетание: домен коллизий (Collision Domain).
Какие же есть методы, позволяющие предотвратить ситуацию, когда коллизия в сети может стать массовым явлением, что (со временем) приведет к полной ее неработоспособности?
Абсолютно идентично и с компьютерами! Их ведь люди создали, вот и «ведут» они себя так же 🙂
Также нужно четко понимать, что некоторую часть доступной пропускной способности сети отнимает у пользовательских данных широковещательный служебный трафик, который является неотъемлемой частью практически всех стеков протоколов, работающих в локальных сетях.
Несмотря на все эти сложности, принцип разделяемой среды используется достаточно часто. Такой подход, реализован в широко распространенных стандартных технологиях локальных сетей, например: Ethernet, Token Ring, FDDI. Почему? Наверное, из за простоты и дешевизны его конечной реализации (дешево и сердито) 🙂
Коллизия
Термин коллизия (от лат. collisio — столкновение) имеет несколько значений:
См. также
 | Список значений слова или словосочетания со ссылками на соответствующие статьи. Если вы попали сюда из другой статьи Википедии, пожалуйста, вернитесь и уточните ссылку так, чтобы она указывала на статью. |
Полезное
Смотреть что такое «Коллизия» в других словарях:
КОЛЛИЗИЯ — (лат. collisio, от colligere столкнуться). Столкновение различных сил, чувств, взглядов, непосредственно предшествующее борьбе. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. КОЛЛИЗИЯ [лат. collisio] острое… … Словарь иностранных слов русского языка
коллизия — См … Словарь синонимов
КОЛЛИЗИЯ — [оли], коллизии, жен. (лат. collisio) (книжн.). Столкновение противоположных сил, стремлений, интересов в области человеческих отношений. Коллизия экономических интересов. Нравственная коллизия. Толковый словарь Ушакова. Д.Н. Ушаков. 1935 1940 … Толковый словарь Ушакова
КОЛЛИЗИЯ — (от лат. collisio) столкновение противоположных сил, стремлений, взглядов, интересов. Коллизия долга – столкновение одного долга с другим, при этом выполнение одного из них исключает выполнение другого: преимуществом обладает тот долг, выполнение … Философская энциклопедия
Коллизия — наложение сигналов, возникающее, когда два устройства начинают передачу данных одновременно. Коллизия приводит к потере передаваемых данных. По английски: Collision Синонимы: Столкновение См. также: Множественный доступ Финансовый словарь Финам … Финансовый словарь
Коллизия — (от лат. collisio столкновение) в общем смысле столкновение противоположных сил, стремлений, интересов, взглядов. В праве коллизия законов означает противоречие друг другу формально действующих нормативных актов, изданных по одному и тому же… … Политология. Словарь.
коллизия — и, ж. collision f., нем. Kollision <лат. collisio столкновение, сотрясение. 1. Столкновение противоположных взглядов, стремлений, интересов. СИС 1985. Я еще теперь не могу решиться, какия именно лекции буду слушать. В некоторых есть у меня… … Исторический словарь галлицизмов русского языка
Коллизия — (англ. clash, collision) столкновение противоположных сил, интересов, стремлений. В праве см. Юридическая коллизия; Коллизионная норма; Коллизия правовых актов … Энциклопедия права
Коллизия — см. Конфликт. Литературная энциклопедия. В 11 т.; М.: издательство Коммунистической академии, Советская энциклопедия, Художественная литература. Под редакцией В. М. Фриче, А. В. Луначарского. 1929 1939 … Литературная энциклопедия
Коллизия — расхождение, противоречия, несоответствие между собой законов, норм, постановлений или содержащихся в них положений. Словарь бизнес терминов. Академик.ру. 2001 … Словарь бизнес-терминов
КОЛЛИЗИЯ — (от латинского collisio столкновение), столкновение противоположных сил, стремлений, интересов, взглядов … Современная энциклопедия
Коллизия (базы данных)
В базах данных коллизия — событие, когда один пользователь запускает на выполнение транзакцию по изменению содержимого базы данных, а другой – на выборку из нее данных.
Суть явления
Сетевые, параллельные и распределенные базы данных обслуживают множество пользователей, работающих одновременно. Поэтому высока вероятность возникновения события, когда один пользователь запускает на выполнение транзакцию по изменению содержимого базы, а другой – на выборку из нее данных. В этой ситуации второй пользователь получит неактуальные данные. Если же два или более пользователей одновременно будут пытаться модифицировать и удалять одно и то же подмножество таблицы с данными, то возникнет коллизия, которая может привести к безвозвратной потере информации.
Блокировки
Решение проблемы возникновения коллизий обеспечивается механизмом блокировок, т.е. передачей во временное эксклюзивное пользование одному пользователю или процессу объекта или фрагмента базы данных для выполнения транзакции. Объектом блокировки может быть база данных целиком, отдельная таблица, фрагмент таблицы, запись (строка) или ячейка. Блокирование может быть полным (запрещены все виды транзакций) или READONLY (разрешена выборка данных по запросу с помощью оператора SELECT).
См. также
Полезное
Смотреть что такое «Коллизия (базы данных)» в других словарях:
Агат (компьютер) — У этого термина существуют и другие значения, см. Агат (значения). «Агат» первый советский серийный универсальный 8 разрядный персональный компьют … Википедия
Игровое искусство — Кинематограф (от греч. κινημα, род. п. κινηματος движение и греч. γραφω писать, изображать) отрасль человеческой деятельности, заключающаяся в создании движущихся изображений. Иногда также упоминается как синематограф (от фр. cinématographe,… … Википедия
Игровой фильм — Кинематограф (от греч. κινημα, род. п. κινηματος движение и греч. γραφω писать, изображать) отрасль человеческой деятельности, заключающаяся в создании движущихся изображений. Иногда также упоминается как синематограф (от фр. cinématographe,… … Википедия
Кинематографист — Кинематограф (от греч. κινημα, род. п. κινηματος движение и греч. γραφω писать, изображать) отрасль человеческой деятельности, заключающаяся в создании движущихся изображений. Иногда также упоминается как синематограф (от фр. cinématographe,… … Википедия
Кинематография — Кинематограф (от греч. κινημα, род. п. κινηματος движение и греч. γραφω писать, изображать) отрасль человеческой деятельности, заключающаяся в создании движущихся изображений. Иногда также упоминается как синематограф (от фр. cinématographe,… … Википедия
Художественные фильмы — Кинематограф (от греч. κινημα, род. п. κινηματος движение и греч. γραφω писать, изображать) отрасль человеческой деятельности, заключающаяся в создании движущихся изображений. Иногда также упоминается как синематограф (от фр. cinématographe,… … Википедия
MD5 — Проверить информацию. Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье. На странице обсуждения должны быть пояснения … Википедия
N-Hash — Криптографическая хеш функция Название N Hash Создан 1990 Опубликован 1990 Размер хеша 128 бит Число раундов 12 или 15 Тип хеш функция N Hash криптографическая … Википедия
Судья — У этого термина существуют и другие значения, см. Судья (значения) … Википедия
Электронная цифровая подпись — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии. Электронная подпись (ЭП) информация в электронной форме, присоединенная к другой информации в электронной… … Википедия
Коллизия хэш-функции
Коллизией хеш-функции H называется два различных входных блока данных x и y таких, что H(x) = H(y).
Содержание
Коллизии криптографических хеш-функций
Мерой криптостойкости хеш-функции является вычислительная сложность нахождения коллизии. Так как криптографические хеш-функции используются для подтверждения неизменности исходной информации (например, для создания цифровой подписи), то найти коллизию для них должно быть сложно (не проще чем полным перебором).
Для криптографических хеш-функций различают два типа стойкости к нахождению коллизий:
Также ключевым свойством хеш-функций является их необратимость:
На этом свойстве основано большинство методов применения хеш-функций в криптографии. В качестве примера можно рассмотреть простую процедуру аутентификации пользователя: при регистрации в системе пользователь вводит свой пароль, к которому применяется хеш-функция и результат записывается в базу данных; далее при каждом вводе пароля, он хешируется и результат сравнивается с тем, который записан в БД. При таком подходе даже если злоумышленник получит доступ к базе данных, он не сможет восстановить исходные пароли пользователей (при условии того, что обеспечено свойство необратимости хеш-функции). Однако, если злоумышленник умеет находить коллизии для этой хеш-функции, ему не составит труда найти поддельный пароль, который будет иметь хеш одинаковый с паролем пользователя.
Разрешение коллизий в хеш-таблицах
Коллизии осложняют использование хеш-таблиц, так как нарушают однозначность соответствия между хеш-кодами и данными. Тем не менее, существуют специальные методики для преодоления возникающих сложностей: