A * improvements

For this weeks work I looked into improving my A* path-finding algorithm. I did this by adding the ability for the algorithm to generate nodes on different Y values so that the AI could path on stairs and platforms at different heights. I also looked into getting the AI to rotate towards where he is walking.

When working on changing on how the nodes generate the first thing I had to look at was how I was going to generate the nodes without adding too much of an impact on the performance of the algorithm. The next thing I did when adding the nodes was set the code to only check nodes that are possible for the AI to get to. This was to stop the AI trying to move to a node that is floating in the scene without a platform below it and stops unnecessary calculations being made. I got this working by checking the location around the node when it is generated to see if it is colliding with it an object. If the node is touching an object it then looks at if that object is possible to be walked on. After implementing this system the AI was still unable to path up or down stairs due to how the nodes were being generated on them. This was being caused by the algorithm picking nodes generated inside the stairs that it couldn't reach. I had a look online and in several books however I couldn't find anything mentioning how I could handle this. I eventually fixed this by adding a unique tag to stair objects so nodes that were touching the stairs had additional checks before they are set active. Once a stair is found it checks the nodes above to see if it is also generating within a step. If the node is touching a stair then the node is disabled as the current node is inside the stairs and if the node above isn't touching the stairs then it should be at the top of a step. After testing this the AI managed to manoeuvre around my scene without having any problems on the stairs/obstacles placed in it.

Next I looked at changing the rotation of the AI. After getting the AIs rotation to translate towards the player the AI worked fine with only a few small problems. These problems happened when walking up stairs and trying to move to nodes at different Y values. I tried stopping the AI from rotating on its Y axis however it continued to do this.

For next week I will be looking to improve the AIs movement so it walks in a smoother path when transitioning between nodes. I will be doing research into some different approaches that I could handle this and deciding on the best approach. I will also look into fixing the bug mentioned earlier with the AI rotating when walking up and down stairs.

Adding A* to AI and meeting

For this weeks work I started by adding in my A* algorithm in place of the Unity navMesh on the AI script. I did this so I could test and see how well it works and see what changes I would need to make to get it to a usable state. After implementing the algorithm there were a few key things that I noticed that I needed to implement. These were the ability to move up/down stairs, generate nodes at different heights, rotate the AI to face where its walking and to smooth the path the AI takes when walking to each node. These are some additions that would greatly improve my algorithm.

After adding my algorithm to the AI script I decided to quickly tidy up the code for the AIs attacking mechanics. I decided to do this as it was half finished and was causing me a few small problems when working on the AI script. The code for this doesn't work perfectly but no longer causes me any problems when working on anything else now. I may come back at a later date to see what additional improvements I can make to this however it is not a priority.

After planning what I wanted to add I had a meeting with Chris to discuss my project. I had this meeting to decided if it was worth making these changes to my algorithm as even with these changes it is likely that Unity's built in navMesh will still be better than my version. We decided that I should continue to work on it and after making the small changes that I mentioned previously compare the two again. Even if the changes do not improve it to a stage that is as good as Unity's navMesh I will have a lot more experience and work to add to my CV. This is important as this was a key reason as to why I decided to do this project in the first place. We also discussed a few different ways that I could go about implementing these changes.

For next week I will be researching into how I can make the algorithm work for stairs, platforms at a different heights, having the AI rotate towards where it is walking and to smooth the path that the AI walks across. Once I have researched this I will begin adding these changes into my project.

More A*

For this weeks work I continued to work on my A* path-finding algorithm. I started by reviewing my work from last week to make sure I understood where I was and what I needed to do next. For this week I needed to have the algorithm check what the quickest path was and then have the AI element move across that path. When I began adding the code to check the path I realised that how I was handling the nodes didn't actually work due to the amount of information each node needed to store. I though about different ways I could handle this but couldn't think of any good way of handling this that wouldn't cause me more problems later. After having a look at some resource materials I went back to a YouTube tutorial I looked at when starting my algorithm showing a way to program your own version of A* inside of Unity (Lague, S. 2014). After watching the first 3 videos in this series I noticed the mistake I was making was that I could be storing all the information in a class and then store that into an array. Watching these videos helped give me a much better understanding on what I needed to do next and how I could go about handling it. I went on to use this to help direct me whenever I had a problem while implementing the algorithm.

Once I had the algorithm calculate the path I noticed that the path that was being calculated was very inefficient and instead of going directly to the target position it would go around almost all the other nodes before reaching the target. After a while of debugging and looking back over my research materials I noticed I had mistakenly placed a > instead of a < sign. This meant that the algorithm would pick the least efficient node to move to instead of the most efficient.

Next week I plan to start implementing this into the main AI script and seeing how this compares to using Unity's built in navMesh. Although Unity's navMesh has more features (such as allowing the navMesh agent to jump between navMesh paths) I would like to see how much my own version of A* works. I will also look to see what other things I can add to the algorithm to improve it. Some things that I will be trying to add is support for stairs and generating the node on platforms that are not at the same starting height as the target/player at the start of the game.

References
Lague, S (2014) A* Pathfinding. Available at: https://www.youtube.com/watch?v=-L-WgKMFuhE

A* Star

For this week I started with implementing my own version of the A* pathfinding algorithm.I began with going back to the resources that I looked at last week to make sure I knew what I was doing. I did this because I have no previous experience in programming my own pathfinding algorithm so wanted to make sure that I knew what I needed to do. Once I re-read my research material I began programming it into Unity. I started by programming the code that generates the different nodes. The algorithm will use these nodes to calculate the distance between the AI's current locations and their destination. I spent a little bit of time planning the best way of handling the different nodes. This was because I wanted an efficient method but still keep it easy to customise if I needed to at a later date. I first looked at using a 2-dimensional array however I realised this would stop me having holding different variable types. I then looked at using a list however I couldn't hold both the position of the node and whether the node position was/wan't being blocked by any other obstacles. I then decided to go with a dictionary. This was because I could add nodes at run time like a list but was also able to store both node variables together.

The only big problem I had with trying to implement was trying to figure out where the AI was on the node grid. This was because checking the node positions again the players position would never match as the player position would be several decimal places out from being exactly on a nodes centre. I tried rounding the node position and AI position but this caused the AI to be on multiple different nodes at the same time. I finally decide to run through a for each loop which checked the distance from the AI and the node finding the closes one. Having tested this in game it didn't cause  negative impact on performance so I will keep using this method.

For next week I will be trying to implement the rest of the algorithm and begin testing it in the scene. To complete the algorithm I need to start calculating the path the AI needs to take and start moving the AI according to the path generated.

Picture of the the node grid that is generated showing walk-able areas, un-walk-able areas and where the AI is positioned.