I'm making a game that has an inventory. This inventory will have multiple things to click on (different slots, options, etc.). i want to know if there is an efficient way to check what the mouse has clicked on.

 

My code right now is checking every single clickable thing in the inventory to see if it was clicked on. I can already see this will be inefficient when more options are added. The code is something along the lines of:

For (Item in Inventory)
{
    if (mouseCoordinates == ItemCoordinates)...
}

How do games that have a ton of clickable things handle this?

Either through elaborate GUI systems or something as simple by transforming the coordinates into an index into a list of items.

My initial take is; it does not "matter" for this. How may inventory items will you have? Even few hundred and iterating over them, would not show up in profile.

My initial take is; it does not "matter" for this. How may inventory items will you have? Even few hundred and iterating over them, would not show up in profile.

I was probably only going to have about 20+ slots. I guess you're right. I'm underestimating the power of a CPU...

For simple & lightweight GUI, your approach is ok.

More complex GUIs are usually managed hierarchically as in there are containers/views, which clip down recursively and so on.

Ascii drawing to clarify:
+-------+

|V1 |

|-----+ |

|V2 | |

|-----+ |

| |

+-------+

V2 gets clipped by V1 and in a more complex setup, v1 could contain many more sub views and those in turn can contain some too.. You get the point I think.

One optimization that is being done is to check whether (x, y) is in the clipping rect of a node (e.g. ctrl or V1).

If its not, then you can skip recursively checking which it actually hit - with this, you can potentially skip thousands of controls.

Thats usually enough, I have never personally experienced a bottleneck on GUI systems.

My homebrew UI library uses multiple Displays. Each display takes up some part of the screen space. A display can be a child of another display. Then, each display holds a number of components(the actual visible/interactive UI elements). So you can Pick your display first(only a few would normally exist), than iterate through the components that only belong to that display(aka a few as opposed to all of the existing components on the screen).

Edit: Basically what Aphton said.

Either through elaborate GUI systems or something as simple by transforming the coordinates into an index into a list of items.

Interesting, I never really though of transforming a cursor position to an index value. My immediate though though would be what if you wanted to move the ui element? Would you have to remap it each time? But i guess that could be handled by the element itself?

Use a quad tree to store the UI components and travel down the tree based on the position of the cursor.

This should have O(log4(n)) complexity.

Alternatively, like fastcall said,

xIndex = mouse.x % (number of horizontal boxes);

yIndex = mouse.y % (number of vertical boxes);

UI[xIndex][yIndex].processClick();

The downside here is your UI must fit into a regular grid, the quad tree method would be an irregular grid, and probably more trouble than it's worth :P

I assure you a modern PC can calculate thousands of if(mouse.x < uiElement.width+uiElement.x && mouse.x > uiElement.x) per frame though... No one would ever know that you used anything less than the most efficient code possible in this case.

edit --

Roughly 1190476 UI elements could be processed per frame on a 1GHz cpu at 60fps >.>

In practice, probably more than that, I was pretty generous with an estimate of 14 instructions for two of those if statements... (7 each, one addition, two comparisons, one logical and, and three movs (mouse positions will be assumed to have an effectively permanent register), in fact, I think my assembly for that is pretty inefficient, and the compiler would do better work >.>

The clearner solution is checking it by modulo the number of items in a line or a column.

This article breaks down the efficiency of several different solutions, though in relation to a different problem.