{"id":{"repo_id":"windsor","oai_identifier":"oai:uwindsor.scholaris.ca:20.500.14776/7931"},"canonical_url":"https://search.dev.ndltd.org/etd/windsor/oai:uwindsor.scholaris.ca:20.500.14776/7931","repository":{"repo_id":"windsor","name":"University of Windsor","base_url":"https://uwindsor.scholaris.ca/server/oai/request"},"display":{"title":"Performance Evaluation of Competing Data Structures in Pathfinding","abstract":"Pathfinding is an essential part of many applications, including video games and robot navigation. A pathfinding algorithm usually finds a path from the given starting point to the endpoint. Many different implementations of pathfinding solutions exist in the industry. One of the most known and used of these algorithms is A*. A* will find the shortest path from the starting point to the endpoint. Classic A* algorithm can guarantee the shortest path to the desired destination which was introduced in 1968 by Hart, Nilsson, and Raphael. A* is widely used in the game industry to solve the shortest path problem. The A* algorithm utilizes two data structures. A* explores the nodes in the graph from the start position one by one and assign them a value of F which is the sum of G cost and H cost. G Cost is the actual cost of exploring the node from the starting position to the current node, and H cost is the estimation of the cost of from the current node to the goal node. The Open List keeps all of the nodes that are not explored at each iteration of the algorithm. In each iteration, the algorithm removes the node with the least value of F cost and run the algorithm. If the node is not the goal, it will be added to the closed list. Interactions with the open list, which are insert (current node) and remove Min, are the costliest part of the algorithm. It is well known that using a priority queue will increase the performance of this algorithm. A number of priority queues have been used to implement A* and improve the performance of this algorithm. We propose to use a Lazy binary heap and evaluate its performance compared to other data structures. We expect that due to decreasing the size of the current open list, it will outperform other binary heaps.","abstract_html":"Pathfinding is an essential part of many applications, including video games and robot navigation. A pathfinding algorithm usually finds a path from the given starting point to the endpoint. Many different implementations of pathfinding solutions exist in the industry. One of the most known and used of these algorithms is A*. A* will find the shortest path from the starting point to the endpoint. Classic A* algorithm can guarantee the shortest path to the desired destination which was introduced in 1968 by Hart, Nilsson, and Raphael. A* is widely used in the game industry to solve the shortest path problem. The A* algorithm utilizes two data structures. A* explores the nodes in the graph from the start position one by one and assign them a value of F which is the sum of G cost and H cost. G Cost is the actual cost of exploring the node from the starting position to the current node, and H cost is the estimation of the cost of from the current node to the goal node. The Open List keeps all of the nodes that are not explored at each iteration of the algorithm. In each iteration, the algorithm removes the node with the least value of F cost and run the algorithm. If the node is not the goal, it will be added to the closed list. Interactions with the open list, which are insert (current node) and remove Min, are the costliest part of the algorithm. It is well known that using a priority queue will increase the performance of this algorithm. A number of priority queues have been used to implement A* and improve the performance of this algorithm. We propose to use a Lazy binary heap and evaluate its performance compared to other data structures. We expect that due to decreasing the size of the current open list, it will outperform other binary heaps.","abstract_has_math":false,"creators":["Tavakoli, Mohsen"],"institution":"University of Windsor","degree_name":"M.Sc.","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["mita@uwindsor.ca"],"advisors":["Goodwin, S."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-12-12","date_published":"2018-12-12","updated_at":"2026-07-27T22:04:47Z","subjects":[],"languages":["en_CA"],"rights":[],"rights_urls":["http://creativecommons.org/licenses/by-nc-nd/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14776/7931","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["mita@uwindsor.ca"]},{"key":"dc:contributor.advisor","label":"Advisor","values":["Goodwin, S."]},{"key":"dc:creator","label":"Author","values":["Tavakoli, Mohsen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-07-03 14:05"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-03-31 20:22","2025-07-03T18:05:02Z"]},{"key":"dc:date.issued","label":"Date","values":["2018-12-12"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/masterThesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.Sc."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Windsor"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_CA"]},{"key":"dc:rights","label":"Dc Rights","values":["http://creativecommons.org/licenses/by-nc-nd/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14776/7931"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Pathfinding is an essential part of many applications, including video games and robot navigation. A pathfinding algorithm usually finds a path from the given starting point to the endpoint. Many different implementations of pathfinding solutions exist in the industry. One of the most known and used of these algorithms is A*. A* will find the shortest path from the starting point to the endpoint. Classic A* algorithm can guarantee the shortest path to the desired destination which was introduced in 1968 by Hart, Nilsson, and Raphael. A* is widely used in the game industry to solve the shortest path problem. The A* algorithm utilizes two data structures. A* explores the nodes in the graph from the start position one by one and assign them a value of F which is the sum of G cost and H cost. G Cost is the actual cost of exploring the node from the starting position to the current node, and H cost is the estimation of the cost of from the current node to the goal node. The Open List keeps all of the nodes that are not explored at each iteration of the algorithm. In each iteration, the algorithm removes the node with the least value of F cost and run the algorithm. If the node is not the goal, it will be added to the closed list. Interactions with the open list, which are insert (current node) and remove Min, are the costliest part of the algorithm. It is well known that using a priority queue will increase the performance of this algorithm. A number of priority queues have been used to implement A* and improve the performance of this algorithm. We propose to use a Lazy binary heap and evaluate its performance compared to other data structures. We expect that due to decreasing the size of the current open list, it will outperform other binary heaps."]},{"key":"dc:title","label":"Title","values":["Performance Evaluation of Competing Data Structures in Pathfinding"]}]}],"canonical_facts":{"dc:contributor":["mita@uwindsor.ca"],"dc:contributor.advisor":["Goodwin, S."],"dc:creator":["Tavakoli, Mohsen"],"dc:date.accessioned":["2025-07-03 14:05"],"dc:date.available":["2019-03-31 20:22","2025-07-03T18:05:02Z"],"dc:date.issued":["2018-12-12"],"dc:description.abstract":["Pathfinding is an essential part of many applications, including video games and robot navigation. A pathfinding algorithm usually finds a path from the given starting point to the endpoint. Many different implementations of pathfinding solutions exist in the industry. One of the most known and used of these algorithms is A*. A* will find the shortest path from the starting point to the endpoint. Classic A* algorithm can guarantee the shortest path to the desired destination which was introduced in 1968 by Hart, Nilsson, and Raphael. A* is widely used in the game industry to solve the shortest path problem. The A* algorithm utilizes two data structures. A* explores the nodes in the graph from the start position one by one and assign them a value of F which is the sum of G cost and H cost. G Cost is the actual cost of exploring the node from the starting position to the current node, and H cost is the estimation of the cost of from the current node to the goal node. The Open List keeps all of the nodes that are not explored at each iteration of the algorithm. In each iteration, the algorithm removes the node with the least value of F cost and run the algorithm. If the node is not the goal, it will be added to the closed list. Interactions with the open list, which are insert (current node) and remove Min, are the costliest part of the algorithm. It is well known that using a priority queue will increase the performance of this algorithm. A number of priority queues have been used to implement A* and improve the performance of this algorithm. We propose to use a Lazy binary heap and evaluate its performance compared to other data structures. We expect that due to decreasing the size of the current open list, it will outperform other binary heaps."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14776/7931"],"dc:language.iso":["en_CA"],"dc:rights":["http://creativecommons.org/licenses/by-nc-nd/4.0/"],"dc:title":["Performance Evaluation of Competing Data Structures in Pathfinding"],"dc:type":["info:eu-repo/semantics/masterThesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["M.Sc."],"thesis:institution_name":["University of Windsor"]},"updated_at":"2026-07-27T22:04:47Z"}