Вопрос по алгоритмам

Почему-то сразу вспомнилась игра «Сапёр».

А поконкретнее? Если нужно что-то визуализировать, в openGL есть возможность выбора объектов - удобная штука. Если же нужно только хранить, то придется вам о деревьях подумать каких-нибудь.

http://ru.wikipedia.org/wiki/R-дерево

Что есть «сосед» в твоем понимании ?

Поконкретнее. Будет игра на SDL. Без использования OpenGL. Сцена набита объектами у которых в свойствах есть их положение на поле(х,у) и их boundingRect. Гипотетическая ситуация: объект «ракета» летит в заданом направлении, с заданной скоростью, с каждым вызовом цикла обработки игровой логики она будет перемещаться с точки (x,y) в точку (x+dx, y+dy). Перед перемещением ее в точку (x+dx, y+dy) нужно проверить не упёрлась ли она в какой-либо другой объект и, если уперлась, взорвать ее и дамагнуть всех, кто есть вокруг ее текущей позиции. Пока что я надумал самый тупой вариант: запихуем указатели на все объекты в вектор, перед движением объекта пробегаем весь вектор и составляем список тех объектов, координаты, которых лежат в промежутке от x до x+dx и от y до y+dy. Как-то так.

Шикарно. Спасибо за наводку.

R-дерево избыточно сложно для твоей задачи. Для сильно меняющихся сцен оно также подходит плохо. Думаю тебе нужна матрица «свободных/занятых» участков сцены.

>Есть двумерная сетка координат.

Зачем делать «лисапеды»? Используй готовые геоинформационные системы: GRASS GIS, Quantum GIS, gvSIG.

>объект «ракета» летит в заданом направлении

Можно «грабить корованы» © запускать ракеты по реальным картам :)

Я ни слова о геоинформационных системах ни сказал. Почитай мой комент выше.

ты только что пальнул из плазменной гаубицы по тараканам

>из плазменной гаубицы по тараканам

Дык, «на вопросы смотреть надо ширше»! ©
Когда ТС надоест клепать игры, он сможет программировать полётные задания для настоящих «тополей», «булав», «лайнеров», ..., пользуясь опытом и заделом по ГИС. И зарабатывать кучу неигрушечных денег :)

игрушка попадет под экспортные ограничения :)

http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Comput...

http://en.wikipedia.org/wiki/Quadtree