Evaluating techniques of finding a path in a dynamic digital search domain
MetadataShow full item record
Moving from one point to another in an efficient yet effective manner has always been a problem for people. The same problem can be related to mathematical graph theory, where moving from one co-ordinate to another generates similar frustration. The term” pathfmding” is used to describe a process which is purposely designed to solve this problem. Pathfmding is used in many computer applications, not just limited to games, but within games is where its use is most apparent. Within this context this document initially sets out to examine and critically review pathfmding algorithm.. Special attention is focused upon the A* algorithm, due to it being one the most widely used algorithm to solve the pathfmding problem. These algorithms are analysed in the terms of processing speed and efficiency and from this conclusions are drawn up. It was determined that A* was the best overall algorithm over a set of standard problems that where tested. The players of digital games have come to expect that the games developed have the latest game technology and programming techniques powering them. With this in mind the dynamic pathfmding process was investigated, Dynamic pathfmding is standard pathfmding, but it is done in a domain where the domain is likely to change of the course of the game. Using similar techniques employed to test the non dynamic algorithms, a dynamic algorithm was analysed and was found out to be very accurate but caused unnecessary processing and memory expense. In an effort to remedy the discovered problems and add some closure to this research a custom algorithm was developed. The algorithm was tested using the same tests as the other dynamic algorithm and was found to have less processing and memory overheads at the expense of the accuracy of the algorithm.
The following license files are associated with this item: