Internship - Week 10 - Cockroach upgrade
Hey there,
Now that we have the basics for the AI working, it is time to introduce some more complicated behaviors and make the creatures a lot smarter. At this point they lack any capability to navigate and walk around like a chicken without a head, Now lets change it.
Image 1: A* pathfinding on https://qiao.github.io/PathFinding.js/visual/.
This week it was time to teach the creatures some path finding, this way they are able to detect food and walk towards it (we don't want our little guys to starve to death). Previously they were only able to find food when they were standing right on top of it.
For our first iteration of the path finding, we will implement the A* algorithm. "A* is a computer algorithm that is widely used in path finding and graph traversal, it is the process of plotting a efficient path between two points, called nodes."(thanks Wikipedia). For us these two points are the creatures location and the location of the food. I won't exactly explain how A* works in this blog, this has been done a thousand times before. If you have no idea how A* works, I advice you to have a look at one of these sites:
Or do a simple google search yourself.
Just a little heads up when checking if the neighbors of the current tile are walkable or not, you can either cut the corners(image 2) or you can walk around them (image 3). I saw that not every website talks about it so let me do that very quickly. The solution most people want for their AI is to walk around the walls. For this you need to do an extra check when you are looking at the diagonal neighbors(image 4 - purple). You need to check if the horizontal(image 5 - H) and vertical(image 5 - V) neighbors next to it are walkable.
Image 2: path with corner cutting.
Image 3: path without corner cutting.
Image 4: starting tile with diagonal neighbors.
Image 5: connected neighbors to the diagonal tile
Now lets have a look at the final result we achieved:
GIF 1: creature path finding through maze.
