The Ant Colony Optimization and Particle Swarm Optimization are two Swarm Intelligence algorithms often utilized for optimization. Swarm Intelligence relies on agents that possess fragmented knowledge, a concept not often utilized in games. The aim of this study is to research whether there are any benefits to using these Swarm Intelligence algorithms in comparison to standard algorithms such as A* for pathfinding in a game. Games often consist of dynamic environments with mobile agents, as such all experiments were conducted with dynamic destinations. Algorithms were measured on the length of their path and the time taken to calculate that path. The algorithms were implemented with minor modifications to allow them to better function in a grid based environment. The Ant Colony Optimization was modified in regards to how pheromone was distributed in the dynamic environment to better allow the algorithm to path towards a mobile target. Whereas the Particle Swarm Optimization was given set start positions and velocity in order to increase initial search space and modifications to increase particle diversity. The results obtained from the experimentation showcased that the Swarm Intelligence algorithms were capable of performing to great results in terms of calculation speed, they were however not able to obtain the same path optimality as A*. The algorithms' implementation can be improved but show potential to be useful in games.


    Access

    Download


    Export, share and cite



    Title :

    Utilizing Swarm Intelligence Algorithms for Pathfinding in Games


    Contributors:

    Publication date :

    2017-01-01


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629




    Swarm Intelligence Algorithms and its Types

    Ramya S. I., Anto / N., Mageswari | BASE | 2017

    Free access


    PATHFINDING SYSTEM, METHOD AND PROGRAM

    MUTSUGA KATSUHIKO / MOCHIZUKI ATSUSHI | European Patent Office | 2016

    Free access

    Discretized Quaternion Constrained Attitude Pathfinding

    Kjellberg, Henri C. / Lightsey, E. Glenn | AIAA | 2015