Login | Register

Group Pathfinding Using Group Division


Group Pathfinding Using Group Division

Saeidianmanesh, Mehdi (2015) Group Pathfinding Using Group Division. Masters thesis, Concordia University.

[thumbnail of Saeidianmanesh_MCompSc_S2015.pdf]
Text (application/pdf)
Saeidianmanesh_MCompSc_S2015.pdf - Accepted Version
Available under License Spectrum Terms of Access.


Pathfinding is an important problem in video games. Good pathfinding strategy, for both player characters and non-player characters is one of the key differences between a good game and a less successful one. Finding the shortest path for one character unit in a given environment is a very well-known problem for which there exist many solutions. When a group of units wants to pass through the map, the problem becomes more complicated. This thesis introduces the Reduced Wait Time (RWT) algorithm which is a multi-unit path planning algorithm where units can take several paths instead of just the shortest one to reduce the overall waiting time of the units in queues along the path and therefore reduces the total time needed to pass all units through the map.
The main goal of this thesis is propose the pathfinding algorithm RWT to reduce the total time for a group of units to pass a route. The simulation results shows that the RWT algorithm not only reduces the time to pass by decreasing the waiting time, but also can reduce the number of collisions between units which reduces the CPU usage which is another important consideration for games. Using the RWT algorithm also gives an opportunity to the level designers to be able to implement strategic pathfinding in games. Different routes have different strategic advantages and disadvantages over each other; being able to send units through different paths enables designers to consider strategic path-planning.
The RWT algorithm was implemented using the Unity game engine and tested on a number of randomly generated example maps. The experimental results were compared with the results from other related algorithms such as Local Repair A* and Maximum Flow to show that the RWT algorithm works better than other studied algorithms.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Saeidianmanesh, Mehdi
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:April 2015
Thesis Supervisor(s):Fevens, Thomas and Mudur, Sudhir
ID Code:980032
Deposited On:13 Jul 2015 14:23
Last Modified:18 Jul 2019 15:21
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top