## Pathfinding Thesis Complete

WOOT! My thesis, the bane of my existence for the last 2 years, is finally done! Its basically a review of the video game pathfinding field as well as presenting a novel grid map search technique: the spatial grid A*. The version linked below is the final draft that is being submitted to my faculty.

## A Robust Explosion Hit Check Technique

In a recent technical interview I got asked the following question: “if an explosion occurs i.e. from a grenade, how would you determine which characters in the game are affected”. This was a question that I couldnt answer at the time which annoyed the hell out of me and it’s been sitting in the back of my head for the last few weeks. So I decided to discuss it (and my proposed solution) on my blog as an “academic” exercise. I would really appreciate any feedback or comments on this discussion. This is far from being a solved problem for me and while my solution may potentially work quite well, there may be a simpler technique available which I don’t know about.

Coming back to the question. Well the naive answer to that question is to simply do a collision detection check with the explosion area of effect/blast radius (sphere) and any nearby characters’ bounding boxes. Read more of this post

## Optimizing the A* algorithm

So I’ve recently completed my MSc thesis on video game pathfinding and I guess it’s a little weird for someone who spent the last year focusing on game AI and pathfinding to not actually spend much time blogging about it. I figured that I spent the time today and write a short post on optimizing the A* algorithm. The A* algorithm pretty much sums up video game pathfinding as a whole. Even advanced techniques like hierarchical pathfinding algorithm make use of A* in searching the various abstraction levels.  So today I’m going to just discuss optimizing the algorithm, not a low level implementation but rather the some of the high level issues. I’m assuming that readers will have some degree of familiarity with the A* algorithm so I’m not going to waste time explaining it.

A*’s computational cost is primarily divided between two components, the heuristic function and the open list and so these are the components that I’m going to focus on. Read more of this post

## Final Simulation Results

Final Simulation Results for BGMAPS benchmark

Final Simulation Results for Custom RTS Maps

I recently posted about some preliminary results for my prototype algorithm, I now have the final results for both BGMAPs and my own set of RTS style game maps. Both sets of maps were sized at 512×512. The RTS maps are simple island style maps which I made more complex that the average RTS map found today just to increase the difficulty of the problem. In increasing the complexity I’ve also reduced the length of straight line paths available at which my prototype excels in that way I’ve handicapped it a little. Even so on RTS style maps my silly algorithm kills A*, furthermore there the memory costs are over 10x lower than required by A*. Unfortunately my RTS maps are artificial and so I cannot state that my approach will work beyond a doubt in real world RTS maps (even though I’m pretty sure it would ).

The initial prototypes I presented had some flaws and were not complete algorithms in the sense that they wouldn’t always return a solution if one existed. My new versions are complete in that sense. There was a lot of tweaking, prodding and changing necessary to achieve this and the search times have gone up marginally.

The performance of the prototypes isnt bad on the BG maps test set but unfortunately the graph doesnt show the full picture, there are certain rare cases in which the solution returned by my approach is GROSSLY sub-optimal (over 100% suboptimal in fact) and the time take to find this “amazing” solution is nearly double the time needed for A*. This poor behavior is due to the spatial layout of the BG maps, which focus on numerous dead end winding tunnels.

I would like to investigate the efficiency of the algorithm within real world RTS maps as well as on FPS maps so if any game devs reading this post can send me some top down JPGs of their game levels I would really appreciate it. I now just need to finish writing up my last chapter of my thesis and submit it. I will be posting the full thesis on this blog which will include all the necessary info on my prototypes which I’m naming the Spatial A* algorithm.

PS! it is necessary to mention that these results are pre-smoothing and so the path optimality will be greatly improved with a post-processing smoothing step.

## Preliminary Pathfinding Results for my Prototype Algorithm

The preliminary results of my prototype pathfinding algorithm - run on a basic set of 8 BG maps.

It’s been a while since I’ve posted about anything pathfinding related. I’m currently wrapping up my thesis and once I finish work on this prototype algorithm all I need to do is write up my results and my thesis is complete.

My prototype algorithm is based on a pretty stupid premise so I wont go into much detail here ;) sufficed to say its basically an abstract search without an abstraction layer. I have three versions of the basic algorithm:

• P1 – this is the naive version (the same one I showed at GDC)
• P2 – performs basic trimming on the refinement step as discussed at the AI dinner (thanks Alex, Marc and Joel!!)
• P3 – attempts to improve path optimality by picking a new end goal for the search and using that to reach the final goal.

These are the results of a very basic run on 8 Baldur’s Gate 2 maps scaled up to 512 x 512 (around 10000 search problems). My algorithm makes use of the exact same A* implementation it is compared against. There is still one problem with the P2/P3 variants that needs to be corrected and a P4 variant is also in the works. I hope to have all 4 variants complete by the weekend and all my simulations completed by next week monday. That gives me a week to do the final write up and submit my thesis!

The path optimality listed is pre-smoothing, with smoothing, the optimality greatly increases but so does the total time for the “pathfinding action”. I still have to find an efficient (read very very FAST) path smoothing algorithm before I can actually bother doing any smoothing experiments.

## The NMD Engine – A work in progress

The original NMD toolkit

I’ve been rather quiet of late, I made some rather large changes in the direction of my master’s thesis and have spent a lot of time on replanning and restructuring my work. I initially intended to do my thesis on real-time pathfinding in dynamic environments, this is still the case but I realised during my research that there was a large gap present in the academic literature regarding the actual implementation  and execution of a pathfinding system within a game engine.  So while the topic of my thesis remained the same, the overall structure and contributions did not. I have struggled with my thesis for the past two years mainly due to a lack of a focussed goal, I had initially intended on doing a more generl overview of the various pathfinding algorithms and techniques present in the academic literature today and perform a comprehensive comparison of them in regards to memory usage, solution optimality and search speed.

## Some Graph Performance Observations

I’m doing my masters thesis on game pathfinding and this pretty much boils down to implementing comparing graph search algorithms (and hopefully developing a new algorithm). Now to implement and test the various algorithm I need to maintain a level of consistency  in the implementations so my first step was to start planning and development on a pathfinding test framework that would  provides a common search interface for the various algorithms and will be able run automated test routines.

So I started with the idea that since all the algorithms are graph search algorithms I need a nice generic graph container than can store the various types of nodes that each algorithm required. This meant creating a nice flexible graph design with a whole node inheritance hierarchy and node factories to create the various node types and on and on and on… From a software engineering viewpoint, the design was very flexible and extensible, from a performance and implementation standpoint it was a mess. For each new graph type it was necessary to create a new node child class and a new node factory child class, all just to add in a few data members to a node.

First attempt at a generic graph implementation

## Pathfinding Work

The first version of my pathfinding visualization

I’m currently doing my masters degree in video game pathfinding, and progress has unfortunately been rather slow, I spent most of last year planning my pathfinding framework and doing my literature survey, so far I’ve written a basic map generator, a very rough framework with a working (but not optimized A*)  and a very rough visualization app so I can see the results of the pathfinding algorithms. The visualization app still needs a lot of work so that I can use it to quickly swap between algorithms (A*, IDA*, SMA*, HPA*, etc) and so that I can swap out the heuristics that the algorithms use. Read more of this post

## C++ Back Propagation Neural Network Code v2

There was a lot of feedback on my neural network implementation, mostly regarding architectural suggestion so i sat down and rewrote my neural network implementation, its pretty elegant now. I seperated the training of the network from the actual network itself and so i have a basic feed forward network, a data set reader and a neural network trainer. I also renamed several data structures to make things more understandable, also i wasnt lazy and used proper header files and includes

Below is an updated class diagram of the new version:

Here’s the updated implementation (with a VS2k8 solution):

The original tutorials can be found here:

## Basic Neural Network Tutorial : C++ Implementation and Source Code

So I’ve now finished the first version of my second neural network tutorial covering the implementation and training of a neural network. I noticed mistakes and better ways of phrasing things in the first tutorial (thanks for the comments guys) and rewrote large sections. This will probably occur with this tutorial in the coming week so please bear with me. I’m pretty overloaded with work and assignments so I haven’t been able to dedicate as much time as I would have liked to this tutorial, even so I feel its rather complete and any gaps will be filled in by my source code.