Hello everyone and welcome back to the We Got Dungeons dev log!

Today we will be talking about path-finding!

First of all, let's talk about why we need path-finding. Let's see what happens if we just completely throw path-finding out of the window and try to move the character somewhere on the screen.

As you can see the character decides he had enough of this rather poorly decorated basement and that going home is the best option considering the circumstances.

This happens because we are using the same code for a single step movement. The destination coordinates are set and the character moves one pixel at a time until that destination is reached. But when the target destination is not on the same axis with the character, they continue moving forever since they can never "turn" and reach the breaking condition.

So obviously we need a way of telling the character to "turn". Going straight in one direction and turning at a right angle is one option but a problem arises when there's an obstacle in the way. That's where a path-finding algorithm comes in very handy. In addition, path-finding is a crucial part of the enemy AI; after all a monster can't eat your face if it gets stuck on a box.

So the basic idea of the path-finding algorithm is to progressively check an expanding circle of nodes around the starting position called a front. Then, we pick a node from the front, we check the neighboring nodes and if they haven't been already visited, we order them based on the shortest distance and add them to the front. In addition, we store the information about the originating node (denoted as a superscript on the drawing below). Then we repeat until the destination is reached or we have no more nodes to add to the front.

Note that the order in which we add the nodes in the front, and in turn the order in which we pick the next node, is very important. Here we go with a simple shortest distance heuristic.

Now let's talk about the implementation. Once we understand the algorithm implementation is relatively simple (and that is why it took me over a week to do so). We use a struct to store the nodes' information. The graph here is a simple matrix of nodes.

After we go through the path-finding algorithm all we do is go backward from our destination, following the originating node information until we reach our starting point. As we do this we store the direction in which the character has to move in in a simple array.

Then we use the same code for single-stepping but we just chain the directions from the array.

And the final result is:

Wonderful isn't it? Look at him go, its almost as if he has a mind of his own.

So in conclusion; path-finding rocks.

See you all next time in part 5 of our series!