## 2 Literature Review
[PERSON]'s work revolutionized the calculation of shortest paths and has had a profound impact on various fields, including transportation networks and computer networks [22]. However, this algorithm is not a good fit for this scenario because it does not consider the requirements of visiting each node exactly once. 2. _A* search algorithm_ [PERSON] et al. [23] introduced the A* algorithm, which is a combination of [PERSON]'s algorithm and Best-First Search, using a heuristic function to guide the search process. The authors established the formal basis for A*, proving its correctness and discussing its optimality and efficiency. Their work laid the foundation for A* as a widely adopted algorithm in pathfinding and optimization problems. [PERSON] et al. [24] presented a study on dynamic route optimization in a grocery store using the A* algorithm with heuristic techniques. They proposed an efficient system architecture and conducted experiments that demonstrated significant reductions in users' travel distances during grocery shopping. [PERSON] et al. [25] also explored item mapping and route optimization in a grocery store using the Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms. Their study applied these algorithms to improve navigation efficiency and propose a framework for optimizing shopping routes. As of now, grocery shoppers do not accomplish their shopping within the optimal time because shoppers' paths tend to deviate from the optimal TSP path [26]. The research aims to enhance the shopping experience by controlling the pathfinding behavior of grocery shoppers so that they follow the optimal TSP route. The behavior of our character in the grocery shopping environment in terms of their movement between locations or nodes is based on the shortest route available, leveraging the use of the A* search algorithm provided by Unity game engine. [PERSON] et al. [27] revealed in their study that the pathfinding of individual grocery shoppers results in 'hot-spot' areas, essentially specific locations in the store that are frequently traveled through more than other areas. The researchers, assisted by the Sorensen Associates and their PathTracker devices, utilized RFID trackers attached to shopping carts that would 'blink' in 5-second intervals and send the two-dimensional coordinates of the shopping cart to a central processing station. The initial data collection was visualized and revealed a web-like network of lines indicating the paths grocery shoppers took. Looking at this visualization, one can be overwhelmed by the sheer convolutedness of the dataset. As such, the researchers employed a modified version of the k-means clustering algorithm called the k-medoids clustering algorithm that was developed to account for outliers in clustering [28]; running this algorithm simplified the graphical illustration of the dataset. The k-medoids clustering algorithm allowed the researchers to analyze the dataset more effectively and also revealed trends and patterns that were not originally represented in the raw dataset. This concept of identifying clusters in consumers' pathfinding has the potential to structurize the pathfinding of shoppers. Instead of pinginging the location of the grocery shopper, the proximity of items can be determined whenever the shopper picks an item up; the time gap between the first item and second item denotes how close or far away both items are. For items with small time gaps, it can be assumed that the grocery shopper picked up items in close proximity to one another [29], as such these can then be considered clusters or'sections' of the grocery store. Furthermore, natural clustering phenomena can serve as the baseline for developing a sorting algorithm that leverages cluster data to identify the most efficient route for navigating through the supermarket.