Internship - Week 15 - Solving and creating problems
Hey there,
To solve problems we have to create them first. Last week, I said that we were going to fix the problems with the path finding, which we introduced last week. This is exactly what we will do, but like my first sentence states, we'll introduce some extra problems first.
In my efforts to make an easy to use and robust system, I designed a system were each creature type has a list of tiles. every tile in the list also has properties like: "Digable", "Walkable" and/or "Diagonally Traversable". This way it is possible to define the "Wall" tile as "Walkable" for the Dwarf but not for the Cockroach. Now when we try to find a path to the food, the path finding algorithm request all the tiles with the "Walkable" property from the creature.
Normally you would have only one list of tiles with properties, this list would not be added to each creature individually. This means that all the tile properties would be the same for each creature. In most cases this is completely fine and would work great, however this is not the case for our AI and I'll show you why.
Lets say there is only one list of tiles. the "Wall" tile would have the "Digable" property and the "Path" tile would have the "Walkable" property. To make this work with the creatures we would give the Dwarf a "_canDig" variable which we will set to true. With this implemented, we could make it possible for the Dwarf to find a path which digs walls, but then we remember that the cockroach can also dig random wall pieces, so we also set the "_canDig" variable for the cockroach to true. Now we have the problem were the cockroach will also have paths which go through walls. For this reason, I gave each creature their own list of tiles.
Sure, I could have used an ugly work around and made it work that way, but if I have to do this every time a new creature with different behavior gets added, our code will become a mess. I would rather use a solutions that solves all my problems than a temporary fix.
With my solution implemented and working, it is time to make the necessary changes to all my AI code. Before, it was using the "bad" example that I gave earlier, so it took quite a bit of time to change it all around and use the new system. This was completely worth it though, when everything was working. It is easy to use, you only have to add the tiles that need different behavior from the tiles that are used by all creatures(these are stored in the parentObject all creatures inherit from). The path finding code only has to request all tiles from the creature that have the "Walkable" property, which made the code slightly simpler.
Now it is finally time to get back to the original problem at hand. the dwarf is able to dig diagonal walls which does not make a lot of sense and it looks kinda weird.
Gif 1: Dwarf digging diagonally to food.
Luckily for us we can now give tiles properties, so lets give our "Path" tile the "Diagonally traversable" property. Using this we can change the path finding to only give back straight paths, but nothing is ever as simple as it seems. My first idea was to just stop JPS from searching diagonally when it was on a "Wall" tile. Sounds pretty good right, but this will completely destroy the JPS algorithm. let me give you a simple example:
When going diagonally is allowed it will find the food without a problem, but if we only allow it to search straight, dead-ends is the only thing we encounter. JPS will never get to the food.
Well, what do we change then? We can't change the algorithm that finds all the jump points but we should be able to change the algorithm that retrieves the path. The jump points are allowed to go diagonal but we should change it in a way that the final path can only go horizontal or vertical on a tile without the "Diagonally traversable" property. It's easier to show you than to try and explain it, so let me do that:
Image 1: diagonal path Image 2: diagonal path
which only goes straight.
In between adding every diagonal tile to the path, we need to implement an extra step which adds either the horizontal or vertical neighbor in the same direction to the path.
Diagonal path
Image 3: Diagonal jump points. Diagonal path between jump points.
Image 4: Diagonal step 1. Diagonal step 2. Diagonal step 3.
straight path
Image 5: Diagonal jump points. Straight path between jump points.
Image 6: Extra horizontal step 1. Diagonal step 1. Extra horizontal step 2.
This blog is already long enough so lets change the last things and call it quits for this week. When adding an horizontal or vertical neighbor to the path, we should check if one of them has the "Walkable" property. If one of the neighbors does, that is the one we want to add. The path finding will be faster than way because we don't have to dig that tile before walking.
If there is any important lessons to takeaway from this, it is that you should never blindly implement the first thing you can think off. It is very likely that you will find a better solution if you give yourself some time to think about it.
