Jump to navigation
Heuristic Path Finding Method for Online Game Environment.
Jia-jia Tang (author)Liang Chen (Thesis advisor)University of Northern British Columbia (Degree granting institution)
Master of Science (MSc)
Number of pages in document: 105
Pathfinding is one of the main problems for computer gaming. It has long been a bottleneck for system performance in the online game industry. Due to the vast amount of pathfinding requests and attributes of game maps, many pathfinding methods that work well for the console game environment have failed the challenges of online games. In order to obtain a satisfactory performance, the background processing system has to sacrifice either efficiency or accuracy otherwise it would require a hardware improvement. Therefore, after investigating possible solutions to resolve these common issues of pathfinding, we have designed a Heuristic Path Finding Method. Under this method, designers analyze the game map structure and build area information first. The online game system will then generate path templates for in-game usage based on the map information. As the templates are being generated, the system's pathfinding Artificial Intelligence (AI) will pick a path from the templates and adjust it accordingly to produce a real path. This method improves pathfinding tasks with higher accuracy, is less time consuming and requires fewer resources from the game system. We have also created a testing system as a tool for testing and evaluating pathfinding related work. We carried out a series of experiments with the testing system on the online game service, and showed us that our method is a better solution than a few known algorithms.--P. i.
Computer games -- Programming.Artificial intelligence.Electronic data processing -- Evaluation.Computer algorithms.