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.