[How to] Binary Search Tree for FiveM

FiveM Resource Development & Modding Modding Tutorials
,
1

Introduction
Binary Search Trees (BSTs) are fundamental data structures used for efficient searching, insertion, and deletion operations. In this blog, we will explore the concept of BSTs, understand their working principles, and discuss their effectiveness in searching nodes within large lists, particularly in the context of FiveM Lua scripting.

  • Understanding Binary Search Trees:
    A Binary Search Tree is a hierarchical data structure in which each node has at most two children, commonly referred to as the left child and the right child. These nodes are organized in a manner that allows for efficient search, insertion, and removal operations. The tree follows a particular ordering property, where the value of every node in the left subtree is less than its parent, while the value of every node in the right subtree is greater than or equal to its parent.

  • Working Principle and Efficiency:
    The efficiency of a Binary Search Tree lies in its ability to quickly locate a specific node within a large list, even when the number of nodes exceeds 10,000. The searching process in a BST involves comparing the target value with the value at the current node and recursively traversing either the left or right subtree based on the comparison result. This binary partitioning of the tree ensures that the search space is halved at each step, resulting in a time complexity of O(log n), where n represents the number of nodes.

  • Example of Efficiency Improvements:
    Lets take an example of building a housing resource. You want to draw a marker when a player is near a property. In your server, their are 10,000 properties. As we know, the EndTextCommandDisplayText and DrawMarker needs to be run every frame. If we use a for loop that iterates the entire existing property table and finds the nearest property, the time complexity for the search is O(n), which means for each frame you need to search 10,000 times to find the nearest property in the worst case. However, if we use the BST, the time complexity for the search is O(log n), which means for each frame you only need to search log2(10000) ≈ 13.8 = 14 times in the worst case.

Implementing a Binary Search Tree

  • Building the BST:
    To start, you would populate the BST with your coordinate data. Each coordinate becomes a node in the tree, where the left and right children are determined based on their respective values. The construction of the BST ensures that the left subtree of any node contains only smaller values, while the right subtree contains only larger values.

  • Searching the Nearest Coordinate:
    To find the nearest coordinate to the player, the BST provides an optimized approach. By comparing the player’s current position with the root node’s coordinate, you can determine whether to traverse the left or right subtree. This process is repeated until the nearest coordinate is found.

  • Time Complexity:
    The beauty of BST lies in its time complexity for searching operations. In a balanced BST, the time complexity for searching, insertion, and deletion is O(log n), where n is the number of nodes in the tree. Even with a large number of nodes (e.g., nodeCount > 10,000), BST can quickly locate the nearest coordinate, making it a perfect fit for efficient gameplay experiences.

Example Implementation
For a hands-on experience, you can find an example implementation using BST for nearest coordinate search in this link. In this example, each node can hold both the coordinate and other data, such as a table or a value, in your original data structure (table). An additional feature has been added to find a list of coordinates within a specified range.

Note

  • Please be aware that all example code provided in this blog post has been initially generated using ChatGPT, a language model developed by OpenAI. While efforts have been made to ensure the accuracy and functionality of the code, it is essential to review and modify the examples according to your specific requirements and coding standards.

  • Remember that while BSTs are efficient for searching and retrieval operations, they might not always be the best choice for every scenario. It is crucial to evaluate the characteristics of your data and the specific requirements of your application to determine if a BST is the optimal data structure for your use case.

3 Likes
2

I love the idea of bringing out more performance related topics with explanations! Thank you for taking the time to do so :slight_smile:
And I hope this doesn’t come over as a rant but rather improvements that can be made.




As much as I like optimizing code, asking ChatGPT is not the best way to do so. Especially when you did not try it out for yourself. That being said, you can definitely tackle complex problems with ChatGPT, but you really need to hold its hands when it comes to the actual working code it produces.

I’ll give you some examples and how they could be fixed:

  • Your example code won’t work out of the box. Vector3.new (...) is not a valid function in lua and FiveM doesn’t provide it either (it is just vector3(...) or vec(...)). It is a common example of ChatGPTs lack of understanding actual programming (it is basically making assumptions of what could come next).

  • The compareVectors(...) function is also not a good example. Comparing floating point values is always bad as it is extremely easy to run into precision errors which will result in wrong results (58100 * 0.01 can result in 581.0000000001 and stuff like that).

  • table.insert(...) is not good regarding performance. Try to use a direct assignment. E.g.:

-- instead of
table.insert(nodes, node)
-- do this
nodes[#nodes + 1] = node
  • The same goes for the use of ipairs. While it might be really useful, it is actually not good for performance when you are talking about like 10,000 nodes as you are constantly assigning a value.
-- instead of
for _, node in ipairs(nodesWithinDistance) do
-- do this
for i = 1, #nodesWithinDistance do

For more Lua performance related things, checkout this site: Lua Performance - Spring

Naming conventions:

  • You should always be using the same names for the same things. The code uses coordinate and position. Why? Stick to one. Makes it so much easier to read. (also I hate the fact that GTA uses “Coords” everywhere :smiley: )

  • Some functions are prefixed with an underscore which I presume to be internal functions that should not be used by someone on its own? Still a little awkward (in my opinion) and you could just make them proper internal functions without access from the outside considering the OOP approach.

Next logical step would be Quad or even Octrees :wink:

1 Like
3

Thank you for your thorough feedback and the time you took to provide it! It’s incredibly valuable to continually improve the quality of the content shared here. I apologize for the confusion caused by any errors in the code examples and I’ll be sure to address these points in future posts. :smile: