How We Taught A Bear To Turn

This blogpost was written – but not published – a month ago. I finally had some time to prepare the images which hopefully makes this post a little bit easier to understand.

The first prototype of MPIs had already featured a bear and a working pathfinding implementation. Unfortunately, it only worked because it was incomplete and the bear itself was smaller. Nowadays though, the bear (and the MPIs, more on that later) has received a facelift and increased in size – from a 2×2 object on the map to a big 2×3 object. Unfortunately, this change led to a problem that was known in advance but postponed for a prototype at a later date (read: now) to deal with. So, what’s the issue? Objects can turn; they also have a “front” (their face, basically). Now try to turn a square around its center – it remains in the same position, albeit the front is facing another direction. Now do it again and turn a big 2×3 object around – the position of the object changes:

The old bear didn’t turn. It would always look in one direction and would walk either forwards, sidewards or backwards but it would never turn around – and it didn’t need to, as the bear in the first prototype had a 360 degrees field of view, not 90 degrees. What I was working on over the last couple of days was to make the bear turn around; to create a more pleasant, more natural looking path.

This turned out to be not as straight forward as people might think. The old pathfinding algorithm was working but the grid system had several shortcomings. Pathfinding basically boils down to how you visit your current neighbours and rank them relative to your actual goal. Before you can rank each neighbour, you also have to make sure that it’s actually free. That was slow in the old system because it basically moved the complete entity (which is several cells big) and tried to place it on the new coordinate – if it succeeded, the cell than would be ranked, if not, the cell was not picked as a candidate. Let me tell you, that is a lot of overhead: the more cells an object covers, the longer this check would take. I was banging my head against the table looking for another option, and it came in form of a method called clearance-calculation.

According to the article, a cell’s clearance value defines which object of what size fits in that specific spot. If a cell has a clearance value of 8, every object with the size of 8×8 or less can be moved without issues to the cell in question. Instead of checking each of the object’s cells, one only needs the size of the object and the positon it wants to move to, check the clearance value of the cell and decide accordingly.

There’s a catch though: it only works for square objects, but our bear grew to 2×3 which ain’t one. Using a clearance value of 3 doesn’t work all the time, since there can be areas where a 3×3 object wouldn’t fit, but a 2×3 one would, so the information available with the given clearance value is not complete.

Based on the clearance value, I was thinking about ways to pre-calculate if an object fits a particular position and ended up at calculating a clearance value for each unique layout per map. The 2×3 layout is moved to any non-blocked cell to see if it fits. If yes, save a clearance value of 1 for this cell or 0 when it doesn’t, then continue with the next one. That’s still not enough information though as the 2×3 is, when turned around, a 3×2, so I had to do the above again for a 3×2 layout and merge those values together: if both 2×3 and 3×2 fit in one cell, it has a clearance value of 3, if only 2×3 fits, it’s 1 and if only the other one fits it has a level of 2 – so the bear could fit into that specific spot if it would turn around before.

The next issue on the list I had to fix was object blocking. Objects block each other, meaning they need to be taken into account when calculating a cell’s clearance values. As the current calcuation only works for static stuff like buildings (since they’re placed in advance and cannot move), the clearance map needed to be updated every time an object got placed on the map (e.g. player) and moved around to be useful for pathfinding. Luckily updating the clearance value is straight forward and only cells to top left need to be recalculated:

(12 = clearance value of 3 (1 + 2))One thing I wasn’t paying attention to up until now was the object’s positioning on the grid. Every object has a center of rotation which is also used as the coordinates to place the object on the grid – the other cells which an object covers are relative to the rotation center. The rotation center is, who would’ve guessed, in the center of an object – on the other hand, the clearance value does not specify that the rotation center, but the top-left cell that an object occupies. Easy solution: either move the calculation to the rotation center or let the layout reference the top-left corner in each direction. I chose the latter one, problem solved.

With all these pre-calculated and dynamically updated clearance values I finally was able to go back to the actual problem: letting the bear turn around. As I stated earlier, it boils down to the neighbour-selection and ranking for each possible neighbour. Instead of only considering the neighbours of the direction the bear is facing, I also visited the neighbours of the other directions, adding them to the list of possible candidates. Unfortunately, that wasn’t enough as the rotation was calculated as an additional step which reduced the likelyhood of being chosen. The bear kept going sideways. I was able to remove the additional step due to the fact that I now visit the other direction’s neighbour instead of the direction itself. Theoretically this should increase the amount of checks but it practically decreases them as a valid path is found faster with less traversing. I also heavily increased the likelyhood of choosing one of those direction neighbours as the next waypoint if the direction the bear has to walk (e.g. left) and the directional neighbour would face to same direction (e.g. both would go left), so the bear turns around and goes left instead of sidewards.

Colorcode – green: walking north, yellow: walking east, blue: walking south, red: walking west. Also for the following images. The yellow area at the start is just the starting point though.
Almost the way I’d like it to be, but do you catch one last issue? The bear has a tendency to go upwards and I was scratching my head why it would like to do that. It came down to a default value: if the bear moves diagonally, the directional value was set to 1 (= facing upwards) as a diagonal direction is not supported. This means every time it moves diagonally, it sometimes would highly prefer to face to the north and go down from there.

How to resolve that issue? If I wasn’t able to calculate a natural looking direction for the next waypoint, I just used the direction the bear should face relative to the actual target. If a bear’s target was south from its current standpoint, the default direction would be 3 (= south) – this little tweak reduced the occurance of weird behaviour to a minimum!

Are we done yet? No, the algorithm still needs some tweaking as there are still some weird issues where the bear moves in the proper direction but then decided to do a quickturn before going back on the orignal, good-looking path.

Also, in the current version, there is an issue with AI finding a proper goal to walk towards – where the pathfinding actually can find a way – to. However in the last month we have been focusing on the frontend instead which you can see every now and then when our Community Manager Joony leaks a screenshot on facebook, the MPIs are covered in the latest Innogames TV.