Comparison of A*, Euclidean and Manhattan distance using Influence map in MS. Pac-Man
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Context An influence map and potential fields are used for finding path in domain of Robotics and Gaming in AI. Various distance measures can be used to find influence maps and potential fields. However, these distance measures have not been compared yet.
ObjectivesIn this paper, we have proposed a new algorithm suitable to find an optimal point in parameters space from random parameter spaces. Finally, comparisons are made among three popular distance measures to find the most efficient.
Methodology For our RQ1 and RQ2, we have implemented a mix of qualitative and quantitative approach and for RQ3, we have used quantitative approach. Results A* distance measure in influence maps is more efficient compared to Euclidean and Manhattan in potential fields.
Conclusions Our proposed algorithm is suitable to find optimal point and explores huge parameter space. A* distance in influence maps is highly efficient compared to Euclidean and Manhattan distance in potentials fields. Euclidean and Manhattan distance performed relatively similar whereas A* distance performed better than them in terms of score in Ms. Pac-Man (See Appendix A).
Place, publisher, year, edition, pages
Ms. Pac-Man, algorithm, influence maps, potential fields, distance measure, A*, Euclidean, Manhattan, optimal parameter space
IdentifiersURN: urn:nbn:se:bth-11800OAI: oai:DiVA.org:bth-11800DiVA: diva2:918778
Subject / course
DV2566 Master's Thesis (120 credits) in Computer Science
DVACS Master of Science Programme in Computer Science
Lundberg, Lars, professorJohansson, Stefan
Boldt, Martin, universitetslektor