I had this conversation with someone on reddit the other day and thought it might make a useful blog post.
tl;dr stop searching through Lua tables. There are very few instances where you should be using a
for loop to look for a particular element in a Lua table. Instead, you should be using some kind of identifying information as the key and element as the value in the table.
For example, in LÖVE, the physics collision callbacks return three things: 2 fixtures (physics elements) and a contact (an object representing containing collision information). Lets say you’ve set up your physics and your collision callbacks and everything is working. But fixtures probably aren’t the object you want to operate on when there’s a collision happening. You probably want the body that owns that fixture or maybe even some other table that owns that body! You now have three options:
1) You can loop through every body in your game and check its fixtures until you find the ones you’ve just had collide. This is simple and easy to understand but it’s going to get pretty slow when you’ve got a lot of object colliding often. You probably need something speedier.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2) You can use Fixture:setUserData and set the user data as whatever parent element you want. This is a fast solution but it’s not a pattern that we can follow everywhere and it’s not immediately obvious that fixture user data should always be physics bodies. This is good but we can do better.
1 2 3 4
3) The best way is have another table that uses the fixtures as the key and a parent element as the value. You’ll have to manually clean up these references if you destroy the fixture but it’s fast and something that you have complete control over, unlike the user data method.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
This type of pattern is something that you can use everywhere and generally cuts down your operation complexity from O(n) to O(1). The only time you can’t use this is if you absolutely need the elements to be ordered or if you need to know the size of the list. Every other time you should strongly consider using a hash in this pattern.