AI Assignment 1 - Pathfinding and Steering Behaviours


In this assignment, I had to implement a finite state machine, steering behaviours and pathfinding. There were also extra marks for how well they work together. We also had to do a write up on why we used the techniques we did and why we didn't use other methods of doing things.


Getting the groundwork for this assignment wasn't too hard as I had already gotten finite state machine done, my grid drawer was done and I understood how I had to do pathfinding. I also had a very simple steering behaviour project.

All I had to do to finish the assignment was add the 3 pathfinding techniques, change my pathfinding project to work with SFML (this would allow me to use images a lot easier than with glut, which is what my pathfinding portfolio project used), and add all of the parts together to make my final assignment.

For the theme of my project, I decided I wanted to have a plane that would attempt to get to the next airport, avoiding clouds in its path. there would be some white clouds that would have a higher weight than the plain sky, and also storm clouds which would have to be completely avoided.


I started this assignment a long time before the hand in so I never really felt too stressed by it. I started in November by implementing breadth-first search. Then I upgraded the grid drawer to allow me to click on nodes so that I can edit levels by clicking on the program rather than in the code. This wasn't needed for the final project but it wasn't wasted time because it allows me to quickly test different scenarios while adding the other pathfinding techniques, it also looks good in my portfolio.

During December I focused on getting my graphics assignment finished, so I didn't make any progress with my AI assignment.

When January came, I was ready to start working on the AI again, for the first couple of weeks, I worked purely on pathfinding, Dijkstra's and A* were easily the 2 most difficult things I have done since starting university, this is because I had to figure out the theory of them, as well as parts of the c++ as I was still quite new to it.

Breadth-first, Dijkstra's and A* Search.

In the end, my implementation of Dijkstra's worked perfectly, it would consider weights and avoid obstacles then make find the shortest path. Unfortunately, I was unable to make A* work exactly as it should, it would take what was technically the shortest path in the number of nodes it went through, but in actual distance, it was not the longest.

Once my pathfinding was done is when I started putting my projects together. I made a new SFML project and added all of the steering behaviours that I had made previously for my portfolio assignment. Next, I added the pathfinding, luckily, SFML has OpenGL support, this meant I was able to put the code into the new project and convert it to work with SFML functions gradually, Instead of having to spend ages changing the code before seeing any progress in the program.

By the time I had finished with adding all my pathfinding, it was the day before the hand in, this meant I had less than 24 hours to implement a finite state machine, and actually having all of the components interact with one another. Implementing my finite state machine wasn't hard as I already had a fully functioning state machine from my portfolio assignment. This took me 3-4 hours to do, then all I had to do was make the grid generate weights and obstacles randomly, then have the plane follow the path made.

I managed to add all the features I wanted by around 4am, so I had about 8 hours to polish my program. I started by changing the UI before it was all in front of the grid which made it hard to see, so I shifted the grid down a bit and showed all of the information above it. I also added the ability to show which state the plane was in, as well as its current fuel. Unfortunately, as I was so tired by this point I didn't realise that the text for both my flying state and refuelling state, were both set up to say "Refuelling", hopefully, I don't get marks taken off for that but that's what I get for doing it at 4am.



I really liked this assignment, it was a good challenge that helped me learn a lot about the theory of pathfinding as well as C++. If I had more time, I would go back and fix the mistakes I made, I would also add more steering behaviours as I only have 1 in this project. I will be revisiting all of these projects to improve them for my portfolio in the next few months.

You can find the project here on my Github: https://github.com/ElliotChester/Portfolio

Comments