Как сделать двоичное дерево

сейчас сделал заглушку в виде memcpy,

Аккуратней с этим в геймдеве! Ёжик может начать неестественно хрипеть.

Какая связь между memcpy и поиском? И вообще непонятно что ты хочешь.

Сейчас локации хранятся в HIF_Location ** locations. Если ёж вышел по горизонтали за пределы 1вой размерности массива то создаётся новый массив через new. А потом данные ( указатели ) старого через memcpy копируются в новый. Таким образом имеем постоянный рост мира.

spatial hash попробуй сделать, оно лучше подойдёт. Будешь вести поиск только по сетке в пределах области видимости окна и только того что рядом с ёжиком, а не по всему миру прыгать. Генерируй хоть бесконечность, просто заноси данные только в сетку расположенную в области экрана, убирай исчезнувшее, добавляй появившееся и всё.

Ты локацией квадратный кусок карты что ли называешь? Можно сделать хеш-таблицу по чему-нить вроде (x*13+y*19) и искать эти квадраты по ней. Дервео конечно тоже можно сделать, но оно алгоритмически муторнее, а преимуществ по сравнению с хеш-таблицей почти не даст.

Спасибо за советы. Попробую spatial хэш.

Если карта это равномерная 2D сетка, то можно сделать хэш таблицу где ключем ID ячейки (скажем x+y*64000) а значением что в ячейке лежит.

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

Если на карте надо отмечать только горибочки/ягодки а весь лес одного цвета (и нет препятствий), то в хэш таблицу можно только грибочки/ягодки заносить.

Есть такая игра Path, про красную шапочку, которая должна в зависимости от своего возраста найти «своего» волка в лесу. После того, как тропинка исчезает из виду, если с неё сойти, то вернуться на неё невозможно, постоянно петляешь кругами.

В C++ есть std::map, в C есть несколько либ для хештаблиц (в первом приближении пойдёт вместо дерева). Плюс обычно процедурный мир делят на чанки и выгружает слишком далёкие (либо вообще, либо на диск, если юзер может что-то менять в них).

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

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