Had the week 9 review with the second marker. Discussed the lit review and aims of the project and received feedback on the project.
Feedback
Changes heading on lit review section Artificial intelligence in games to pathfinding algorithms in games.
Add a section on dijkstra's algorithm.
Test cases need to be well designed, Take as many timings as possible and get an average and use t testing to determine if the data sets are significantly different from one another.
Overall the feedback was positive and constructive, the project is on track and has clear goals about what needs to be achieved for the project to be successful.
Implemented a simple application in which agents seek out food items within a maze using the collaborative diffusion algorithm to find the quickest path to the nearest item. The yellow cubes represent the agents, green spheres are food objects and orange cubes are walls which are impassable.
Collaborative Diffusion Explanation
Traditionally
in a game each agent will have its own pathfinding routine that will be called
any time an agent needs to find a path to a specific goal state. Typically in
the majority of games this will call the A* algorithm, this works well in most
cases but as the number of agents increases the time spent pathfinding also
increases which can have a detrimental effect on the performance of the game.
To combat
this collaborative diffusions works on the idea of antiobjects, an antiobject
is a type of object that appears to do the opposite of what we would generally
think the object would be doing (Repenning, 2006).
For example in the game Pac man (Pac-Man, 1980) the objective of each ghost is to find
Pac man. Using traditional pathfinding like A*, each ghost would run its own
pathfinding algorithm every time it needed a new path. From an object
orientation stand point this makes sense to many programmers that the
responsibility of finding a path would be down to each agent, however by
removing the computation from the objects that typically appear to do the
search, it allows the computation to be redistributed in a parallel fashion to
the objects that define the space to be searched instead.
Diffusion is a gradual
process in which physical and conceptual matter, such as molecules, heat,
light, gas, sound and ideas are spread over an N-dimensional physical or
conceptual space over time (Repenning, 2006), within collaborative diffusion this
idea is used to transfer the scent of a goal state throughout the world in
which pathfinding will be taking place. This diffusion value is calculated
using the following equation.
Where:
D = diffusion value
n = number of neighbours
a = diffusion value of
neighbour.
Typically
the world is organised as a grid representing either a 2D or 3D environment and
each neighbour is defined according to the Moore neighbourhood (Moore Neighbourhood, 2013) which comprises of
the eight cells surrounding a central cell.
Each goal
state is given an initially high diffusion value which is used as the starting
state as shown by the green tile in Figure 2 below.
During the
first iteration the diffusion value for all the tiles are calculated using the
diffusion equation. After this iteration the tiles surrounding the goal state
now have a larger diffusion value than they had initially and the ‘scent’ of
the goal state is beginning to move toward the agent as shown in Figure 3 below.
This process
continues again for all of the tiles in the world during the next iteration, as
the diffusion value is calculated again for all the tiles it begins to spread
out further from the goal state expanding the ‘scent’ of the goal further
across the grid and towards the agent. During this iteration the diffusion
value of the tiles surrounding the goal state becomes larger making the goal
state appear more attractive to an agent. This second iteration is shown in Figure 4 below.
At each
iteration the diffusion process repeats expanding further and further outwards
across the tiles. Eventually the ‘scent’ produced by the tiles will reach an
agent at which point a path can be found to the goal state.
Once the
‘scent’ has reached the agent, it is possible for a path to the goal state to
be found, unlike pathfinding algorithms like A* which use a back tracking
algorithm to find a path from the starting state to the goal state all the
agent simply has to do is look up the diffusion values of the tiles
neighbouring the tile it is currently on and move to whichever one has the
highest diffusion value.
As shown in Figure 5 during the third iteration our agent
is able to pick up the ‘scent’ of the goal state, by simply moving to the
neighbour with the highest diffusion value our agent is able to find the
quickest path to the goal as represented by the green tiles.
Collaborative
diffusion allows agents to collaborate together to complete objectives in a
very simple manner. In his paper collaborative diffusion: programming
antiobjects, Alexander Repenning states that there are four different types of
agents that allow collaboration to occur:
1Goal Agents: Goal agents are pursued by other
agents and can be either static or mobile.
2Pursuer Agents: A pursuer agents is an agent that is
interested in one or more of the goal agents. Multiple pursuer agents may be
interested in the same goal and may collaborate or compete with one another.
3Path Environment Agents: A path environment agent allows
pursuer agents to move towards a goal agent and participates computationally in
the diffusion process. In a simple arcade game this could be a floor tile in a
maze.
4Obstacle Environment Agents: Work in a similar manner to path
environment agents but rather than helping an agent to reach the goal they
interfere with the agents attempt to reach a goal. This could be represented by
a wall or obstacle in a room.
Making use
of these different types of agents Repenning noticed that agents would appear
to collaborate with one another to reach a goal. He also states that the
collaboration between the agents is an emergent behaviour as no code is
explicitly responsible for orchestrating a group of agents but is instead a
result of the diffusion process and the way in which pursuer agents find a path
to goal agents through the path environment agents. Another interesting
observation by Repenning is that as the number of agents is increased the time
taken to perform the pathfinding remains constant (Repenning, 2006).
By its very nature collaborative diffusion lends
itself very well to a data parallel implementation on the GPU, as the GPU works
by splitting the work across a number of threads and having each thread perform
the same task it should be more than possible to split the work of the tiles
across a number of threads as each tile performs the same diffusion
calculation.
Bibliography
Pac-Man.
(1980). Retrieved October 26, 2013, from Pac-Man:
http://pacman.com/en/pac-man-history/
Repenning, A. (2006). Collaborative Diffusion:
Programming Antiobjects. Boulder: University of Colorado.
Not much work was done on the background for the project this week due to other coursework deadlines.
Went over techniques that could help with the flow of the document as it is felt that this could be better. This includes writing everything up and then going back at the end and adding in a couple sentences to each section to help with the flow. It may also be helpful to create a flow diagram for each section and follow this.
Also discussed the existing work chapter, rather than having a heading for each paper instead talk about the main points of the paper and use the paper as a reference. For example talk about parallel AI and some of the considerations that need to be taking into account as referenced in the paper by Timothy Johnson and John Rankin and then talk about a* pathfinding and reference the paper by Owen Mcnally. Rather than talking about the paper on collaborative diffusion in this section, discuss it in the section on diffusion.
The week 9 meeting is scheduled to be for Friday the 8th if the second marker is available. For this the draft of the background is to be sent to the second marker the day before and a 1 to 2 page report on the technical work needs to be written up.
Went over the current draft of the background. Agreed that this should be completed by Friday 1st of November to be sent to second marker in time for the week 9 review.
For the week 9 review need to complete a report on what other work has been carried out during the project, including any practical work or other research, also need to create a revised plan of what work is to be done and estimated dates of when this will be completed.
Received feedback from IPO. Main feedback was that the project could be too complex a project for honours level, it is important to establish where this project is re-implementing existing algorithms or develops new ones.
Went over the work that has been done on the lit review, agreed that it is along the right tracks and to continue with it, with the aim to be completed by week 9 review. Agreed that more detail is needed on the working of the GPU as this will be specific to the implementation.
Found an A* CPU implementation that has been used in professional triple A games. This will be modified to suit the needs of the project and used as a benchmark to compare the GPU implementation of a diffusion based algorithm.
Asked to get a copy of the work on pathfinding from the computational intelligence module as this may be helpful.
Still wait on feedback from IPO from second marker.
Presented a draft of the sections that are to be included in the lit review. Agreed that don't need to go into too much detail about the different types of parallel systems only need to give a brief overview.
Look more closely at why using the GPU and why the particular technology could be useful for running pathfinding algorithms. highlight the differences and the advantages/disadvantages over the CPU.
Look at the different APIs that are available for programming on the GPU and give a justification about the chosen API.
Look at the different types of pathfinding algorithms which are available and what is traditionally used in games.
Highlight the advantages/disadvantages in the context of the project and look at the existing work that has been done and pick out what the findings/conclusions are and how they relate to the current project.
Discussed how the algorithms are going to be compared and what the best method of comparing the algorithms would be. Decided that A* is going to be very difficult to paralyze and that the best method if running a GPU implementation of A* would be to test it for a large number of agents and look at the scalabilty in comparison to the GPU. This has already been a few times in the past so it may be better to compare a CPU implementation of A* for a large number of agents against a GPU implementation of a diffusion based algorithm and see which has the better scalabilty and performance. The reason for this is that a CPU A* implementation is what is traditionally used in games so by comparing it against a different algorithm implemented on the GPU it may be possible to find a better algorithm for performing pathfinding within games?
Discussed how rendering could be effected by running the algorithms on the gpu for a large number of agents. Concluded that rendering is not important as the problems are the same for the CPU and GPU implementation, at this stage is has been decided that no rendering of agents will be carried out however if the project is successful and there is time left over it is something that could be implemented to make the application more visually appealing.
Aims for the coming week are to complete a first draft of the lit review in preparation for the week 9 meeting.
Went over Gantt chart and reviewed dates and times for each section. Agreed that the write up should be a continual process throughout the entire project and not just at the end of the project. Gantt chart will be updated to reflect this.
Discussed how data structures and the chosen heuristics could affect the implementation of A* if done poorly. One possible solution to this is to find an implementation of A* that is assumed to be efficient and use it for comparisons.
Began a sequential implementation of A* for a 2D map during the week, aim is to complete this for Friday 11th October and then continue work on it to lead to pathfinding over a dynamic 3D map.
Look into papers about parallel AI and continue with writing up lit review.
