Traverse large arrays or other data structures by range

Imagine in the game of Snake, there are a lot of food on the map, and the program needs to detect whether the snake's head collides with the food (according to the coordinates on the map).
If you use an array to store food information, you need to traverse the array. But if there are many foods (the array is large), a complete traversal is not necessary, because only foods within a certain range may collide.
The problem is how to find the food that may collide based on the coordinates without traversing the entire array.

What I can think of is using array_filter, but essentially it's still traversing.
If there is a way to use other data structures (without arrays), you can also provide it.
Maybe friends who have played games will have good solutions.

Reply content:

Imagine in the game of Snake, there are a lot of food on the map, and the program needs to detect whether the snake's head collides with the food (according to the coordinates on the map).
If you use an array to store food information, you need to traverse the array. But if there are many foods (the array is large), a complete traversal is not necessary, because only foods within a certain range may collide.
The problem is how to find the food that may collide based on the coordinates without traversing the entire array.

What I can think of is using array_filter, but essentially it's still traversing.
If there is a way to use other data structures (without arrays), you can also provide it.
Maybe friends who have played games will have good solutions.

redis’ sort set type can meet your needs http://redis.readthedocs.io/e...

I think it looks like this:

• First of all, the food in the greedy snake is a ball. The array that stores the food should store . There is a map available in C++;

• Then, you can open an array called Map. The size of the array is w h of the map. Suppose there is such food <(x,y), r>, then Map needs to be assigned like this: Map[wx + y] = r; record a maxR thing, which represents the maximum radius of the food, maxR=max(r).

• Finally, determine the collision. Let the position of the snake head be (a, b). What you need to do is to traverse all the coordinates (x, y) of the circle with (a, b) as the center and radius maxR, and then take out r = Map[w*x + y], compared with now_r = dis((a,b), (x,y)), if r>=now_r, it means the snake will eat this food, if it is less than, it means it will not eat it. Arrive, continue to judge the next coordinate.

• Actually, I estimate that when actually doing it, it should be to traverse all the food. After all, greedy snakes don’t have that much food.