A
A
Alexander2015-01-06 21:11:17
Algorithms
Alexander, 2015-01-06 21:11:17

What structure would you recommend for storing spatial data?

Good day.
As part of my coursework at the university, I am developing a simple online game a la World of Tanks. The question arose about storing the position of the players in space.
Tell me if there are such data structures that:
1) They store spatial data
2) Allow you to update data in a reasonable time (i.e. do not delete / add new values, namely update those that already exist)
3) Detect collisions between objects that are rectangles and, for the most part, rotated by some angle
Perhaps the fact that the coordinates of the objects are two-dimensional will help.
If there are no such structures, then I will be glad if you share possible solutions to this problem.
Thank you.
UPD. I beg your pardon, but I forgot about one more important condition
4) It is necessary to find all objects in some given area.

Answer the question

In order to leave comments, you need to log in

2 answer(s)
A
Armenian Radio, 2015-01-06
@Syxov

BSP - tree. Specifically for your task. Carmack and Abrash approve.

U
uvelichitel, 2015-01-07
@uvelichitel

If we are talking about two-dimensional, then most likely it will be
Structure or stupid (depending on the language)

Point{
abcissa Integer
ordinata Integer
}

Array or sheet (depending on the language)
Structure or stupidity (depending on the language)
Object{
Position Point //Положение в абсолютных координатах
Contur [Point] //В координатах относительных к положению
Scale Integer //Коэффициент масштабирования
Turn Integer //Угол поворота
}

And as @Armenian Radio rightly pointed out - BSP tree. In two-dimensional, QuadTree is usually used specifically, something like this
Quad{
Position Point
Size Point
Objects [Object] //Массив или лист объектов лежащих полностью в четверти Quad 
NordOst *Quad //Четыре дочерних четверти
NordWest *Quad //Это как правило рекурсивная структура
SudOst *Quad
SudWest *Quad
}

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question