| dc.description.abstract | 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. | en |
